Collaborative Compressors in Distributed Mean Estimation with Limited Communication Budge

We thank the reviewer for their review. We address all the weaknesses and questions.

Weaknesses

1. [Heterogeneity] The performance of our schemes degrade with increase in dissimilarity between client vectors $g_i$. However, in Section 2.1, we provide an example where the maximum dissimilarity between clients, $\max_{i,j\in [m]}\|\|g_i - g_j\|\|$, is large, however, the average dissimilarity between clients is small for large $m$ as $\Delta_{\infty} \approx \frac{c}{m}\max_{i,j}\|\|g_i - g_j\|\|$, where $c$ is a constant smaller than $c \ll m$. In such scenarios, our methods also perform well for large $m$, as $\Delta_{\mathrm{Hadamard}} \approx \sqrt{\frac{c}{m}}\max_{i,j\in [m]}\|\|g_i - g_j\|\|$, where $\Delta_{\mathrm{Hadamard}}$ has been defined in Theorem 1.

Questions

1. [New results] We have revised the abstract to mention our $4$ proposed schemes -- NoisyGD (Algorithm 1), HadamardMultiDim (Algorithm 3), SparseReg (Algorithm 4) and OneBit (Algorihtm 5). In Section 3, our contribution lies in modeling the problem of distributed mean estimation for the unit vector as halfspace learning with noise, Lemma 1. Techniques I and II are off-the-shelf techniques for halfspace learning with noise, and corresponding Theorems 1 and 2 apply their results to our problem setting.
2. Technique I has not been explicitly introduced in the paper as it is an existing algorithm for solving halfspace learning with noise. In Lines 455-460, we provide it's brief explanation.

We are happy to answer any additional questions or clarifications that the reviewer may have.

We thank the reviewer for their review. We address all the weaknesses and questions.

Weaknesses

1. [Estimates in terms of $\Delta$] We agree with the reviewer that estimates in terms of $\Delta$, are more interesting than those in terms of $B$, as $\Delta$ can be much smaller than $B$. We explain this issue in our Related Works section to establish the superiority of collaborative compressors over independent ones. For our algorithms, however, the coefficient of $B$ is $\exp(-m)$, see Theorems 1 and 2. Therefore, for large $m$, which is often the case in distributed mean estimation, the contribution of $B$ will be close to negligible and the only error term remaining will be a deviation term, $\Delta_{\mathrm{Hadamard}}$ and $\Delta_{\mathrm{reg}}$ in Theorems 1 and 2 respectively. While these terms are not exactly equal to $\Delta_2$, in section 2.1, we describe problem settings, where these quantities are comparable to $\sqrt{m}\Delta_2$. In these settings, the results of distributed optimization with PermK algorithm can be extended to our algorithms, albeit with an additional $\sqrt{m}$ scaling.

   Further, we have derived convergence rates for distributed GD with SparseReg compressor. See the global response for more details on this.

2. [Experiment] (a) (Suresh et al 2016) only test Power Iteration and KMeans on MNIST dataset and CIFAR10's features. In Figure 2, we provide experiments for Power Iteration and KMeans on MNIST and FEMNIST, a real federated dataset with real heterogeneity. Further, we also provide experiments for estimating error in different norms and for Linear regression. (b) In Appendix F, Lines 1105-1116, we explain why different baselines are used for different plots. To summarize, for different norms (Figure 2(a)-(c)) and different tasks(Figures 2(d) - (i)), we use baselines appropriate for the norm and the task respectively. There are $12$ algorithms in total, $8$ baselines and $4$ proposed methods, and we did not plot all of them in the same plot for clarity. (c) In Appendix F, we provide additional details on experiments. The communication budget for all baselines is tuned to be the same. To tune the hyperparameters for each task, we first run the task without compression for $20$ different random combinations of hyperparameters. We pick the best hyperparameters from this search and use it for all compressors. (d) Our goal is to propose compressors for distributed mean estimation. Federated learning with compression is one application of DME but not the only one. To test if our compressors for DME work in this setting, we used the simplest example of distributed gradient descent. While it is possible to use our compressors with more advanced techniques in iterative distributed optimization, for instance acceleration(Yuan & Ma, 2020), variance reduction (Condat et al 2022), intermittent use of a compressor(Gorbunov et al 2021) and communicating the model updates instead of full model weights (Haddadpour et al 2019), we would like to emphasize that these techniques are orthogonal to the design of a compressor. Further, investigating the settings where collaborative compressors work with these techniques is an interesting direction for future work.

   Additionally, we are running experiments on more problem settings. See the global response for details on this.

3. Typos : We thank the reviewer for pointing out the typos and we have fixed them in the revised version. Note that the citation style is according to ICLR style files, so we cannot change it. We address the issues related to plots specifically (e) 3) In Figure 2 (d) - (i), we plot the progress from the $1^{st}$ iteration, hence if there is sufficient progress in $1^{st}$ iteration (Fig 2 (f), (i)), the plots do not start from same point. 4) The green in plots Fig 2 (e), (h) correspond to RandKSpatial which has exactly same performance as RandKSpatialProj in this setting and is thus hidden by it.

We thank the reviewer for their review. We address the weaknesses and questions below.

Weaknesses

1. [Literature Review] We would like to emphasize that we are proposing new compressors for distributed mean estimation (DME), NOT optimization algorithms for supervised federated learning with compression. Therefore, appropriate baselines for our paper are existing compressors used in DME, which have been covered in Table 2. Further, Table 2 provides the best possible $\ell_2$ estimation errors in literature, NOT convergence rates of federated optimization algorithms with these compressors.

   Iterative federated optimization is one application of our compressors for $\ell_2$ metrics. The compressors we propose, especially for $\ell_\infty$ norm and cosine distance, can be used for applications for which no equivalent to error feedback exists, for instance, distributed KMeans, distributed PCA etc.

   Note that error feedback is a technique used in iterative federated optimization which performs DME in every round. However, this technique and several previously used techniques for iterative distributed optimization, for instance acceleration (Yuan & Ma, 2020), variance reduction (Condat et al 2022), intermittent use of a compressor (Gorbunov et al 2021) and communicating the model updates instead of full model weights (Haddadpour et al 2019) are orthogonal to the design of a compressor. Algorithmically, these techniques can be performed with most compressors, including ours, however, their theoretical benefits have been established only for simple independent compressors and certain collaborative compressors like PermK (Condat et al 2022).

   In the revised version, we mention this in our conclusion and leave the extension of error feedback to collaborative compressors as a direction for future work.

2. [Metric for evaluation] For compressors in DME, the correct metric for comparison is the estimation error from the true mean and the number of bits sent, both of which we report in Table 1. Further, we do not compute the estimation error of our algorithms under each norm, rather for each norm ($\ell_\infty, \ell_2$, cosine distance), we propose a collaborative compression algorithm that achieves small estimation error.

   The papers on DME (everything in Table 2, apart from PermK) analyze only the estimation errors of the compressor. Federated learning is just one application of these compressors.

   The key novelty in all of our compressors is the flexibility of collaboration -- a) In Section 2, full collaboration between clients for encoding obtains $\exp(-m)$ dependence on diameter of space $B$, which is the best in literature, b) In Section 3, full collaboration between clients for decoding recovers unit vector of mean at extremely low communication cost.

3. [Experiments] We are running additional experiments as suggested by the reviewer. See the global response for more details.

   Note that in experiments, see Figure 2, we do check our methods on practical tasks (Distributed KMeans, PCA and Linear regression). Further, in Lines 048-053, we describe how any distributed mean estimation algorithm, including the ones we propose, can be used for distributed gradient training. Additionally, we perform distributed gradient descent with compression for linear regression experiments.

We thank the reviewer for their review. We address all the weaknesses and questions.

Weaknesses

1. [Deviation Term not going to 0] This is actually a trade-off of using the correlation between vectors for compression. When the deviation term $\Delta$ is close to 0, collaborative compression is very effective since the other factor can decay as $\exp(-m)$. However in the schemes of Table 2, the decay is at best $O(1/m).$ In addition, independent compressors in Table 2 have dependence on $B$, the diameter of the space, and $B\gg \Delta$. Among the collaborative compressors in Table 2, RandKSpatial and RandKSpatialProj require the exact correlation between all vectors for their guarantees to hold. As for the remaining two correlated compressors in Table 2, PermK and CorrelatedSRQ, our proposed algorithms outperform them under the certain conditions, which are discussed in the paper: In Section 2.5, through a real example, we establish these conditions for our algorithm HadamardMultiDim, with a similar extension to SparseReg. Further, in Appendix B, Lines 792-802, we establish conditions under which any $\ell_2$ compressor, which includes all baselines in Table 2, performs worse than OneBit for unit vector estimation.

2. [Experiments] We are running some experiments in these directions. See the global response for more details. Since our contribution is in the mean estimation problem, and not the subsequent downstream task of optimization, we skipped such experiments so as to keep the focus on contribution.

Questions

1. Thanks for pointing this out. We will fix this in the title.

2. Yes, data heterogeneity is a major challenge in federated settings. However, such heterogeneity is not unbounded, otherwise there will not be any utility of doing federated learning.

   In particular, there are still settings, where the maximum data heterogeneity between two clients is large, but it is low on average. In such settings, using collaborative compressors, in particular, our methods, is advantageous over independent compressors. One example is mentioned in Section 2.3, where a small number of clients, $c \ll m$, have a different distribution than the rest of the clients. These two distributions, corresponding to the two sets of clients, can be very far from each other. However, the average pairwise distance between clients' distributions is small, and thus our methods achieve low error.

3. For isotropic gaussian vectors in Figure 2 (a), RandKSpatial has no advantage over RandK. Therefore, their plots overlap in this case.

4. The y-axis stands for Test MSE similar to Figure 2(f). As the responses $y$ for the synthetic dataset are generated with gaussian noise, the minimum test MSE is not $0$. Therefore, the plots are raised by large constants, which makes the decrease appear not large enough. As the reviewer correctly points out, running for more iterations will decrease the error further. If we plot the $\ell_2$ error of the trained model, it should converge to $0$.

5. We cited the Wikipedia article for the error function. We have changed it in the revised version.

6. We have fixed the typos in Lines 265 and 921 in the revised version.

We are happy to answer any additional questions or clarifications that the reviewer may have. If our rebuttal has changed the reviewer's assessment of our paper, we request them to update their score to reflect this.

There seems to be some confusion about which $\Delta$ needs to be $o(1/m)$. Note that all $\|\cdot\|$ are $\ell_\infty$ norm. For our example in Section 2.3, $\Delta_\infty = \Theta(\frac{\max_{i,j\in [m]} \|\|g_i - g_j\|\|}{m})$ and the error of method depends on $\Delta_{\rm Hadamard} = \Theta(\frac{\max_{i,j\in [m]}\|\|g_i - g_j\|\|}{\sqrt{m}})$. From the discussion in Section 2.3, specifically lines 411-412, we require $\Delta_{\infty} < \mathcal{O}(dB/(mK))$ for our methods to outperform CorrelatedSRQ. From the expression of $\Delta_{\infty} = \Theta(\frac{\max_{i,j\in [m]} \|\|g_i - g_j\|\|}{m})$ this is possible for small values of $\max_{i,j\in [m]} \|\|g_i - g_j\|\|$.

We hope this clarifies the reviewer's concerns as we do have cases where our methods outperform all baselines even theoretically.

Dear Reviewers,

We have included experiments on logistic regression on the HAR dataset in Appendix F.1. We report the test accuracy and training loss for the 4 best compressors. 3 of these are our baselines, OneBit, SparseReg and HadamardMultiDim. The closest baseline compressor is RandKSpatialProj, which is the 3rd best in terms of both test accuracy and training loss.