Collaborative  Compressors  in Distributed Mean Estimation with Limited Communication Budget
Authors: Harsh Vardhan
Arya Mazumdar
Venue: Accepted by TMLR ()

Abstract: Distributed high dimensional mean estimation is a common aggregation routine used often in distributed optimization methods. Most of these applications call for a communication-constrained setting where vectors, whose mean is to be estimated, have to be compressed before sharing. One could independently encode and decode these to achieve compression, but that overlooks the fact that these vectors are often close to each other. To exploit these similarities, recently Suresh et al., 2022, Jhunjhunwala et al., 2021, Jiang et al, 2023, proposed multiple  *correlation-aware compression schemes*. However, in most cases, the correlations have to be known for these schemes to work. Moreover, a theoretical analysis of graceful degradation of these correlation-aware compression schemes with increasing *dissimilarity* is limited to only the $\ell_2$-error in  the literature. In this paper, we propose four different collaborative compression schemes  that agnostically exploit the similarities among vectors in a distributed setting. Our schemes are all simple to implement and computationally efficient, while resulting in big savings in communication. The analysis of our proposed schemes show how the $\ell_2$, $\ell_\infty$ and cosine estimation error varies with the degree of similarity among vectors.

Published in Transactions on Machine Learning Research (10/2025)
Collaborative Compressors in Distributed Mean Estimation with Limited Communication Budget
Harsh Vardhan
Searshoardhan@rcceee edu
Deportment of Computer Science and Engineering University of California, San Diego
Arya Mazumdar
&rccdd. edu
Halicioğlu Data Science Institute University of Colifornia, San Diego
Reviewed on OpenReview: https: openrevvee.. net/ forum? id= ACCHHCOA
Abstract
Distributed high dimensional mean estimation is a common aggregation routine used often in distributed optimization methods. Most of these applications call for communictiion- constrained setting where vectors, whose mean before sharing- One could independently encode and decode these to achieve compression, but that overlooks the fact that these vectors are often close to each other. To exploit these similarities, recently Suresh et al., 2022, Jhunjhunwala et al., 2021, Jiang et al, 2023, proposed multiple correlalion-uuure compression schemes. However, in most cases, the correlat ions have to be known for these schemess to work. Moreover, a theoretical analysis of graceful degradation of these correlation-aware compression schemes with increasing dissimilarity limited only the fz-error in the literature. In this paper, we propose four different collaborative compression schemes that agnostically exploit the similarities among vectors in distributed setting. Our schemes are all simple to implement and computationally efficient, while resulting in big savings in communication. The analysis of our proposed schemes show how the f2, foo and cosine estimation error varies with the degree of similarity among vectors.
be estimated, have to be compressed
1
Introduction
We study the problem of estimating the empirical mean, or average, of a set of high-dimensional vectors in a communicttion-costtiin setup. We assume distributod problem setting, where m clients, cach with a vector gi E IRd, are connected to single server (see, Fig. Tap. Our goal to estimate their mean g the server, where
g
Σ ge. iE[m]
(1)
m
We use [m] to denote the set 21,2...., m). The clients can communicate with the server via communication channel which allows limited communication. The server does not have access to data but has relatively more computational power than individual clients.
This problem, referred to as distributed mean estimation (DME), is an important subroutine in several dis- tributed learning applications. One common application is distributed training or federated learning (McMahan) McMahan & Ramage 2017). when different clients correspond to different edge devices.
et al. 2016
The typical learning task for DME is supervised learning via gradient-based methods (Bottou & Bousquet 2007 Robbins & Monro. 1951). In this case, the vectors ge correspond to the gradient updates for each

---

Published in Transactions on Machine Learning Research (10/2025)
Server Computes = 1 D (bcode(by)- mi Cach Decode independent clients
Server Compules i = Decoda 61, bg....,... buc
Send b server
Send B to
by server
Send server
Client Client Vector g
Client é Client Vectort gi Enoode into b independent of all other clients
Encode gj into b;
Clent j Encodo gj into by based clients mm o
Client
independent all other clients
Encode gi into by besad clients./ J [m], /
(a) Independent Compression
(b) Collaborative Compression
Figure 1
Compression for Distributed Mean Estimation
client computed on its local training data, and g is the average gradient over all clients. On the other hand, distributed mean estimation also used unsupervised learning problems such as distributed KMeans (Liang et al., 2013)), distributed PCA (Liang et al. 2014) or distributed power iteration {Li et al.) 2021). In distributed KMeans and distributed power iteration, 9: corresponds to estimates of the cluster center and the top eigenvector, respectively, on the 7th client.
The naive strategy of clients sending their vectors 9i to the server for DME incurs no error; however, it has a high communication cost, rendering it burdensome in most of the real-world network applications. A principled way to tackle this to use compression: each client E [m] compresses its vector gi into an efficient encoding b, E B, which can then be sent to the server; The server forms an estimate I of the mean 9 using the encodings [Em)) We can then compule the error of the estimate ÿ and the number of bits required to communicate b, (i.e., log, [Bl) to analyze the efficiency of the compression scheme. As opposed to distributed statistical inference (Braverman et al., 2016 Garg et al.) 2014). we do not assume that 9 are sampled from a distribution, and instead the estimation error of these schemes is computed in terms of gi-
One way to approach this compression paradigm is when each client compressos its vector oblivious to others, and the server separately decodes the vectors before aggregating (Figure [a). We call this independent compression and several existing works (Konečný & Richtárik
2018 Suresh et al.] [017]] Safaryan et al.)
2021 use such a compression scheme. The 2021 Gandikota et al. 2022 Vargaftik et al. 2021 Ghosh et al.
simplest example of this scheme RandK (Konečný & Richtárik] 2018), where each client sends only K E N
coordinates as b,, and the server estimates ÿ as the average K K-sparse vectors from each client. As K < d, this scheme requires less communication than sending the full vector gi from each client E [m].
However, independent compressors suffer from significant drawback, especially when the vectors to be aggregated are similar/not /notttoofar which is often the case for gradient aggregation in distributed learning. Consider the case when two distinct clients i,j E [m] have different vectors gi j 9j. but they differ in only one coordinate. Then, independent compressors like RandK will end up sending b, and by which are very similar (in fact, same with high probability) to each other, and therefore wasting communication. Collaborative compressors (Suresh et al. 2022; Szlendak et al.) 2021: Jhunjhunwala et al., 2021 Jiang et al., 2023 can alleviate this problem. Figure lb describes collaborative compressor, where the encodings {ūi (ej)) may not be independent of each other and decoding function jointly decodes all encodings to obtain the mean estimate g. Clearly, this opens up more possibilities to reduce communication but also the error of collaborative compressors can be made to scale as the variability of the vectors.
The amount of required communication also depends on the metric for estimation error. Among the existing schemes for collaborative compressors, most provide guarantees on the & crror |g - gl12 (Suresh al. 2022: Szlendak et al. 2021 JJunjhunwala et al., 2021 Jiang et al. (202).. Also, in collaborative compressors, the error must ideally be dependent on some mensure of correlation distance among the vectors, which is indeed
2

---

Published in Transactions on Machine Learning Research (10/2025)
Compressor
Error metric
Error
# Bits/cliens
NoinySign
||@ - olooo
exp(
[lall
(Ao +
log m
(Algorithm
HadamardMuln
Dim
Blll - 9||bc]
B + A Hadamard
(Algorithm
2
SparseReg
E[| g (زااe
Ba exp (- 2m log L
Areg
log L
(Algorihhm
(L 2 1 tunable)
OueBit
arccos (ū.9)
T (Anorr +
(Algorithm
(t 2 tumable)
Table 1: Theoretical results for our proposed collaborative compression schemes.
Ae, A Hadamard, Areg and Acorr are
measures of average dissimilarity between vectors 19.hsem defined in Theorems 2
3 and Lemma respectively.
For NoisySign, > an algorithm parameter. For Hadamardduuliiim,, we assuine |19%]/oo S B,W i E [m]] For SparseReg, we assumne [|9:] la S B, Vi E [mm] and L is algorithm parameter. For OneBit, g is the unit vector along the average on Dm 9: and 9 is also unit vector.
the case for all of these schemes. In this paper, the measure of such a distance is denoted with A, with some subscript signifying the exact measure; the vectors in question have high similarity as A - 0. The estimation error naturally grows with the dimension d, and decays with the number of clients m (due to averaging). One of our major contributions is to design compression scheme that has significantly improved dependence on the number of clients m to counter the effect of growing dimension d.
If one were to estimate the unit vector in the direction of the average vector 1 Em 9s. which is often important for gradient descent. applications, using an estimate of the mean with low lg error can be highly sub-optimal as the l2 error might be large even if all the vectors point in the same direction but have different (0.9) norms. For this, the cosine distance arccos( |ill [g|l is a better measure, which has not been studied in the literature. We also give compression scheme specifically tailored for this error metric. Another interesting metric is the -ererror which has also not been studied except for in (uurehh et al., 2022). There as well, we give an improved dependence of the estimation error on m.
Further drawback of existing collaborative compressors such as, (Jhunjhunwala et al., 2021 Jiang al., 2023) is that they require the knowledge of correlation between vectors before employing their compression. Without this knowledge, their error guarantees do not hold.
Notation. We use [a, bj to denote [a, a + 1, + 2,..., for a. E N. We use g(0), E [d] to denote the th coordinate of a vector g E Rd, For a permutation on [m], p()) denotes mapping of i e [m] under p. We use Im to denote the uniform distribution over all permutations of [m]]. We use exp(a) to denote el(a) for any a R. For any matrix A E R A for l E [m] refers to the 1tth row of A.
Our contributions. We provide four different collaborative compressors, which are communicttion-eficin give error guarantees for different error metrics (62 error, fox error and cosine distance), and exhibit optimal dependence on the number of clients m and the diameter of ambient space B. To see the advantage of collaboration, we define few natural similarity metrics. All our schemes show graceful degradation of error with the similarity metric between different clients. Our schemes have three subroutines: Init which corresponds to initialization/setlieee /setting up a protocol, Encode which is performed individually at each client to obtain their encoding b,, and Decode which is performed at the server on all the encodings to obtain estimate of mean ğ.
Below main contributions are summarized. The thcoretical guarantees for our algorithms are provided in Table D For each of our proposed compressors, increasing m increases the lotal communication required (which is a product of m and the # Bits/ client), but reduces the estimation error in the appropriate error metric up to a constant A that depends on the deviation between client vectors.
1. We provide a simple collaborative scheme based on the popular signSGD (Bernstein et al. 2018a) scheme, NoisySign (Algorithm [ where sign of each coordinate of a vector sent after adding Gaussian noise. An advantage of this scheme, compared others is that we can infer the vector g with an lo error guarantee increasing with |o and decreasing with m, without the knowledge of ||g|| itself. The dissimilarity is
3

---

Published in Transactions on Machine Learning Research (10/2025)
Compressor
Error
# Bits/client
Notes
RandK
(Končný & Richtárik
2018
O B²)
32K + K Kllogd Kd
Independent
K
SRQ
(Suresh al.
2017
mIA
los
II?
Independent
Kashin
Safaryan et al.
2021
01
10VI
B²)
31 + Ad
Independent
Vī-1)
Drive
Vargaftik et al.
2021
O(B²)
32 +
Independent
PermK Szlendak et al.
2021
O((1
max {0, 1)22)
32K + K log
Collaborative
RandKSpatial (Jhunjhume hunnwla ct al.
2021
O d
Az)
32K + K log d
Needs Correlation
m
RandKSpatialPro (Jiang et al.
2023
A2)
32K + K log
Needs Correlation
Correlated SRQ
(ureeh et al.
2022
0
min
vaa K
d
2d K + K log
l|ail 2 S B, Vi E [m]
K²
Table 2: Comparison of existing independent and collaborative compressors in terms of & error and bits commu- nicated. K is the number of coordinates communicated for sparsification pethods(RandRe PermK, RandKSpatial, RaudKSpatialProo) and the number of quantization levels for quantization methods (SRQ, vgSGD, Correlated SRQ). The constant À is a parameter of the Kashin scheme. Further, B = = Em |1 A2 = #/2 -lall glla. and
Ax max]e[[] m >> 19 g It is also assumed that real is equivalent to 32 bits, which is an informal norm in this literature.
9i loo),, where is the variance of the noise added (Theorem This scheme is 0 mo Ee De = 0 described in Section
2. -Guugrrrattee) For vectors with for norm bounded by B, we propose a collaborative compression scheme, HadamardMultiDDmm (Algorithm 3) which performs wordinate-wise collaborative binary search. We obtain the best dependence on m and B for the fo error (O(B exp(-m))) while suffering from an extra error term Hadamardd which is a measure of average dissimilarity between compressed vectors. Haddmard lies in the range | max] where Ax max 1 - اأتو and Ax, = maxje maxjejd,iiimm dd.ie[m] (mmmm))))))) 9
(TTeorem 2b. In Section 3.3 we provide practical example where value of AHadamard can be approximated and use it compare theoretical guarantees of HadamardMultiDDnn with those of basclines in Table
3. ((-guuarantee) For vectors with & norm bounded by B, we provide collaborative compression scheme SparseReg (Algorithm 4 based on Sparse Regression Codes (Venkataramanan et al. 2014b|a) a). We obtain the best dependence on B and m for the & error (O(B exp(-m/dd)) while compressing to much less than d bits (in fact, to constant number of bits) per client. The error consists of a penalty for the dissimilarity, Areg: the average dissimilarity between compressed vectors which lies in the range [A2, A where A2 = 1 - 1lg - gill3 and A2,ax = max,emm]]lg - 9: 2 (see, Theorem
4. (cosine-guarantee) For unit norm vectors {g. hifmj) we estimate the unit vector g in the direction of the average n Σm For this, motivated by one-bit compressed sensing (Boufounos & Baraniuk 2008), our collaborative compression scheme, OneBit (Algorithm 5), sends the sign of the inner product between the vector 9: and a random Gaussian vector. By establishing an equivalence to halfspaco lcarning with malicious noise, we propose two decoding schemes: the first one is based on (Shen) 2023) which is optimal for halfspace learning but harder to implement and second one, based on (Kalai al. 20088 which is easy to implement. Both schemes are computationally efficient, and have extra dissimilarity term in the error, Acoer 1 Σm cos" cos- g.)), which is the appropriate dissimilarity between unit vectors (sce Theorem
5. (Experiments) We perform a simulation for DME with our schemes as the dissimilarities vary and compare the three different error metrics from above with various existing baselines (Fig 2a 2c We also used our DME subroutines in the downstream tasks of KMeans, power itcration, and lincar regression on real (and
federated) datasets (Fig 2d 21 Our schemes have lowest error in all metrics for low dissimilarity regime.
Organization. In the next subsoction, we present related works in distributed mcan cstimation. The NoisySign algorithm is given in Algorithm and its analysis can be found in Section 2 In Section we present. the two schemes obtaining optimal dependence on m, HadamardMultiDn in Subsection 3. and
4

---

Published in Transactions on Machine Learning Research (10/2025)
SparseReg in Subsection 3.2 In Section we analyze the OneBit compression scheme. Finally, in Section
we provide experimental results for our schemes.
1.1 Related Works
Compressors in Distributed Learning. Starting from (Koneený et al. 2016) most compression schemes in distributed learning involve either quantization or sparsification. In quantization schemes, the real valued input space is quantized to specific levels, and each input mapped to one of these quantization levels. A theoretical analysis for unbiased quantization was provided in (Alistarh et al., 2017). Subsequently, the distributed mean estimation problem with limited communication was formulated in (Suresh et al.) 2017) where two schemes, stochastic rotated quantization (SRQ) and variable length coding, were proposed. These schemes matched the lower bound for communication and lg error in terms of B = 1 m Σ 19 Performing a coordinate-wise sign is also a quantization operation, introduced in (Bernstein et. al. 2018b). Further
advances in quantization include multiple quantization levels (Wen et al. 2017), probabilistic quantization with
noise [Chen ct al. 2020: Jiin et al. [021] Safaryan & Richtarik] 2021), ) vector quantization (Gandikota ct al.
2022
Zhu al. 2023), and applying structured rotation before quantization (Vargaftik et al.)
2021] Safaryan 2021p. Sparsification involves selecting only a subset of coordinates communicate. Common examples
et al.
include
RandK (Konečný & Richtárik 2018), TopK (Stich et al., 2018 and their combinations [eznosikov
ct al.
2022 Note, for all independent compressors, the le error scales as B
Collaborative Compressors. PermK (Szlendak et al. 2021 was the first collaborative compressor, where each client would send a different set of K coordinates. Their error scales with the empirical variance, 11g: - 9112- If Ag is known, or one of the vectors 9i is known, the lattice-basod quantizer in (Davies et al. 2021 and correlated noise based quantizer in (Mayekar et al. 2021 obtains lg error in terms of Ag. Further, Rpatial (Jhunjhuwaala et al., 2021) and RandKSpatialProo) (Jiang et al. 2023 utilize the correlation information to obtain the correct normalization coefficients for RandK with rotations, obtaining guarantees in terms of A2. In absence of correlation information, they propose a heuristic. A quantizer also based on correlated noise, was proposed in (Suresh et al. 2022) which achieves the lower bound for scalars. However, for d-dimensional vectors of fz-norm at most B, their dependence on dimension and number of clients m can be improved by our schemes.
Ag 20
We provide summary of existing compressors in Table 2 along with their error guarantees.
2 NoisySign for unbounded ||9:l
In this section, we utilize collaborative compression to use sign compressor when ||9//lo unbounded. The sign-compressor (Bernstein et al. 2018a) applies the sign function coordinato- -iise where sign(x) +1 if x 2 0 and -1 herwise. For this section, we will focus on single coordinate j e [d]. Note that for any E [m]) sig)(g)) ()) does not have information about [/. Existing compressors (Karimireddy et al. 2020 remedy this by sending !o!") separately, assuming that ! is bounded by some constant B (Safaryan & &Richtarik 2021 Jiin et al. 2023 Tang et al.] 2023). In the second case, the maximum error that can be incurred is 5- This can be improved by adding uniform symmetric noise before taking signs (Chen et al.,
2020
Chzhen & Schechtman 2023) depending on g. However, if no information is available about [01 we
cannot provide estimate of 9, (7)
We utilize the concept of adding noise before taking signs, however, to accommodate possibly unbounded ( we add symmetric noise with unbounded support. One choice for such noise is the Gaussian distribution (5) + =(5)) as the encoding. Note that [ = &=(((")), where (t) = 2 (0 2 -1} - eri( (/z),, and erf is the error function for the unit normal distribution. A single // gives us information about o/²²) however, using it to decode gf might incur a very large variance. However, assuming that all ( are close to g(O) for E [m], 1 good estimator for (.) So, to estimate g(t), we can use 1 Em 8(0)). This scheme performed
NO o²) for some E I. For c ~ o(00,"), we send 6,5)) sign (o.")
m Em 8(0)) is
5

---

Applying --- to estimate makes our scheme collaborative, as an independent scheme would have individually decoded each client's b/ and thus would not take advantage concentration over m machines. To gain insight into the error, note that (1- - z)- = z, for small æ. The error increases with the increase in llglls as we are compressing unbounded variables Ji into the bounded domain [-1, 1] which is the range of the function @ PoeThe number of clients determines the resolution with which we can measure on this domain, as the oo, the -eror approaches áØ exp( [ Note that As determines the average separation between vectors in Published in Transactions on Machine Learning Research (10/2025)
coordinate-win wise is the NoisySign algorithm described in Algorithm 1 recovering 9 using this scheme.
We provide estimation error for
Theorem (Estimation error of noisy sign). With probubility estimation enror of Algorithm
2dm " for some constant > 0, the
Do + 2o log
π
11 gl1oo S
=V2
a(l |
1
(2)
1 Ei=1 L (g) t (اااو) and a(u) a - 1--10o (o).). Further, for small As and lall
where Dg maxje(d] and large
| م| :0 (exp((lo11B//0)) (A + vlogm/m))
value m Σ b; can only be in multiples of 1. Therefore, increasing decreases the error. As m
terms of the 4 operator. vectors 9j are similar to each other, As is small, and the error small as a result. Further, Aş can bounded by more interpretable quantities if the average separation between and g is small:
2
1
A S
Σ
l1g: glloo.
(4)
mo
+E[m)
Note that As is always S 2, so the average error in terms of ls norm is much smaller than a, then the above bound makes sense. Combining Eq I with Eq (3), we can find an asymptotic expression for the estimation error. A large value of can help reduce this upper bound AS well as the impact of a(Ilg])<d) on the estimation error. One can tune the value of if additional information is known, for instance large upper bound on || and 1 >x gloo.. However, even without this information, our algorithm. In contrast, the value of max l99 is required to even run vanilla sign compression algorithms. Additionally, yields a constant error of O(max4ejm) (991ll=), (99llloo))))))))))))) as each sign would need to be accurate. If an upper bound known for max || then the error scales with this upper bound. In contrast, for large m and small Ag, knowledge of a large upper bound helps our collaborative compressor performs much better. Proofs for this section are provided in Appendix
can run
set large and thus
Algorithm NoisySign
Algorithm 3 HadamardMMultiim
Encode Eg,)
Init()
Sample & M/ 2a))) 6, = sign = Es)
Sample a random permutation p Imm Clients and server share p.
return b,
Encode (g:)
Decode (fbo ((b))ie(m)
for j E [d] do
(00 + 4- ( Em 6, (,6)), =l.... l....,d
6. (1) < Hadamard1DEnoogg p())
return g
end for return 62
Decode (16. for j [d] do
Algorithm 2 Hadamard1DEne
g00 Σm #==1 05 (1) B
Input: Scalar Level K
20
S - - [ - B + (2k+1)
2&B
end for return g
return if s E Sx clsc +1

---

Published in Transactions on Machine Learning Research (10/2025)
For NoisySign, collaboration ensured concentration m. In the next section, we utilize collaboration to obtain optimal dependence m.
3 Optimal Dependence on m
If |/ ||g|22 is bounded, schemes that obtain optimal lo ( by modifying the sign compressor) and l2 error dependence in terms of m and the diameter of the space B. The proofs for this section are provided in Appendix B
obtain an almost optimal exponential decay with We provide two
3.1 HadamardMultiDim
When the vectors have bounded fo norm, instead of obliviously using the sign compressor every coordinate every client, one may be able to divide their range and cleverly select bits to encode the most information. We call our algorithm Hadamard scheme, because the binary-search method involved is akin to the rows of a Hadamard-type matrix.
Assumption 1 (Bounded domain).
|| S B, Vi [m).
This would imply that for any j E [d] 9. E B B) E [m]. Now, consider the 5th client and the scalar 9, (3) and assume that by performing binary search the range [-B, BJ] for 9 sending one bit per level of the binary search. However, this scheme is not collaborative. To obtain collaborative scheme, for some permutation p on the set of clients [m]) the jth client. can perform binary search until level p(9) and sends its decision at level p()) In this case, each client sends only bit per coordinate. To decode g()), we take a weighted sum the signs obtained from different clients weighed by their coefficients -- This is the core subroutine (Algorithu 2 The full compression scheme for d coordinates applies this foordinate-wist in Algorithm 3 Note that the clients and the server should share the permutation P before encoding and decoding, which need not change over different instantiations of the mean estimation problem. To understand the core idea of the scheme, consider the case when all vectors 9i = Then, sending a different level from a different. client is equivalent. doing full binary search to quantize g. As long as gis are close to I, we hope that this scheme should give us a good estimate of g. Let 3162 denotes the encoding of 9," at level k Vi, k E [m], E [d]. Therefore, if
allowed encode this using m bits. The best error that can achieve is B
2=-T;
BB we were to use binary search to encode , then E 2 would be it's decoded value.
Theorem 2 (HadamardMulttiimm Error). Under Assumptions the estimation error for Algorithm S is
B
E En- Illğ gllool < 2m-1 + min ( A Hadlamard A Aoo.maxh.
(5)
BB6 8()) 2 24
where Aaddmmar maxye(d]
ΣΣ 15igi5m
Σ
and A max maxxe(d,se|m[lss (r))
m
As we allow full collaboration between clients, in the worst case, we might have incur a cost A which is the worst case dissimilarity among clients. However, if client vectors close, might end up paying much lower cost of Hadamard
3.2 Sparse regression coding
In this part, we extend the coordinate-wise guarantee of the HadamardMultiDDm & error between d-dimensional vectors of bounded fz-norm.
Assumption 2 (Norm Ball). l|gılla < B, B, [m].
To extend the idea of binary search and full collaboration from HadmardMultiDin, we first need a compression scheme which performs binary search on d dimensional vectors with & error guarantees. Sparse Regression codes (Venkataramanan et al. 2014b a which are known to achieve the optimal rate-distortion tradeoff
7

---

Published in Transactions on Machine Learning Research (10/2025)
for Gaussian source, fit our requirements. Let A E Rm be matrix for some parameter L >> O, where Ag denotes the kth row of A. To compress a single vector g by Sparse Regression codes with the matrix A, we use m log L bits to find the closest vector to in the first L rows of A; say the index of this vector is by. Similar to binary search, we subtract C from 9. where 01 is given in (9) to obtain an updated g. We repeat the process using the next set of L rows. Here, each set of L rows corresponds to a single level of binary scarch, with the coofficients 6; obtained from Eq (9) having a decaying exponent. Although Venkataramanan al. 2014b) requires to be random matrix with iid Gaussian entries, if A satisfies the following definition, then can apply the theoretical guarantees of (Venkataramanan et al. 2014b).
Definition 1 ((5), 62. D)-Cover). matriz A E R.LLdd is a (61, D)-Cor for 51, 82 E (0, 1) and > 0, if for each & E [m], 7k,, T E R, such that
max JE((A- 1,64
|Apl2 S vd(1 +x)) jAy' 12
max
|A, Ar Tk
VU E Sd-1
(o, 2 / 2log L + tc), max
JE((A- ([(K-I)(+I,RD)
lexl
81,
m S 62,
and max I' r. kE|m]
m
By the above definition, for each & E mm] the L consecutive rows of A, which correspond to {Ay.j e
V 2(1 2log 4 By show that this scheme obtains & error B exx((mm) as long A is a (61, 82, -ovvvr. Note that the matrix A is deterministically constructed with m sets of c-ncts. The choice of Gaussian A in (Venkataramanan et al.) 2014b) can now be understood from the fact that such random Gaussian matrices are in fact s-nels. The following remark summarizes this.
[kk - 1)L + 1, kL]}. form a E-net (Vershynin 2018 Chapter 4.2) of gd-1 with E
carefully selecting the parameters in the proof of (Venkataramanan et al. 2014b Theorem 1),
Remark (Gaussian A). If each entry of the matrix A is sampled tid from (O0, then, for any d₁ 82 63 E 10, and _ 2d + + log( Ag + 4 logg mLl), ), the matria A is (ō1, 82, l')-Cover with probability 83
2m Le
da2 x
222
log
Note that the expressions for 51, 82 can be obtained from (Venkataramanan et al., 2014b) and the proof for P is provided Appendix B.3] For d = M(log m), the probability of error the above Remark can be made arbitrarily close 1 for large m.
We now extend the scheme based sparse regression codes in Venkataramanan et al. 2014b) to setting of distributed mean estimation, similar to HadamardMultiiim.. Each client i E [m] encodes at level p( where is permutation on [m] and the server computes the weighted sum of the encodings from each client with corresponding coefficients C,6)- Hore, by, denotes the encoding of g; at level k Vi, k E [m]] If we were to use Sparse Regression codes to encode only 9i then Σx= (-A(K-1)L+E,, would be it's decoded value. The full scheme described in Algorithm 4 and we compute it's Eg estimation error in the next theorem. In this scheme, each client only needs to send a single index b As p is known to the server, this index is in the range [L] and each client uses only log L bits for communicttion
Theorem 3 (SparseReg Error). Under Assumption Algorithm for any matriz A E RmLxxd
g the following statements hold for g, the output of
Ep-il 1llg - 1 = 11g g12 + Areg
(6)
m
A AA 1)Ltb,, and ğ = 1 m m
where, Arog m (jEmm)iijj
ΣΣ Σ
Ck (k-
1)L+br,
m
k=1
In addition, if the matria A is (ō1, -ooerr,, then,
8

---

Published in Transactions on Machine Learning Research (10/2025)
Pm m |l|g -glē) SAA + m,xx: and,
11 g1β S A,
(7)
10 L mlr (81 + 82)
2
2 log L
where, A= B² 1+
1
d
d
A Aog I
T log
ΣΣ ( k=1
2 log L
h-1
10 + bz.)).
(8)
d'm2
Remark 2 (Growth of with m). By exponding the squares, we can see that can be bounded by 3 terms.
A B 2m lox
20 log L (81 + 82)e m + d2
100 log" L (6) + +2)2
d
The first and the second terms decrease exponentially with m. The third term is a small constant independent of m, depending on 81, 62 < 1 that con be made arbilrarily small.
The proof is provided in Appendix B.2 Similar to HadmardMultiDim, the first term in the estimation error, A, has an exponential dependence on m and is obtained from the existing results of Sparse Regression Codes from Venkataramanan et al. 2014b). In torms of & error this dependence on m is better than all the prior methods. Note that if our mairix a (0, 0, Coveer,, i.., 61 = 62 = O, then decreases exponentially with m. As mentioned in Remark we can can achieve very small (but nonzero) values for ò1 62 with Gaussian matricos.
By combining Eqs 6 and 7 we can bound the squared l2 estimation error by A + min (Arg, 4 m,, Note that this error resembles Theorem [] as it contains an exponentially decreasing term of m along with a minimum of two terms, one of which is the maximum deviation between any client and the other( max) and the other the average difference of encoded values across all pairs of clients (Areg)). Further, even the dissimilarity term Areg has a similar structure to Hadamard as is the pairwise difference between encodings of two different vectors at all levels, where the difference at level k is proportional to e If the client vectors are not close to each other, might incur the worst possible error A but if they are close, will pay average price in terms of Areg.
The upper bound on Areg in Eq (8) depends on A only via the encoded values (b, J. For this upper bound, the corresponding terms for each level, here denoted by k, decrease geometrically with k. The term 2B"r" Log ensures that Areg is of the correct scale as in the worst case when all encodings are different for d'mm²
all pairs of clients, the summation gives us ① Ozzigz) which results in an overall Areg of the scale of B², From Venkataramanan et al. 20144),, for each h E [m²] all encodings upto and including the hth encoding, i.e., (be Ik's. form an estimate of 9i that has crror scaling as Be lox Lik 1) which is similar to the error scaling
of HadkmmaddMultiiim for a single dimension.
While both the HadmardMultiiim and SparseReg schemes achieve very low communication rate, that comes at the price of 0mm) computing in the Encode step. This higher cost in computing is to be expected when one wants to exploit the full potential of collaborative compression (e.g., (Jiang et al. 2023), where the Decode step takes ((m²) time).
3.3 Benefits of HadmardMultiDim and SparseReg
We now provide example to show that for practical scenarios, the error terms Areg and AHadamard are much smaller than their worst case values Aoc,max and A max and have similar behavior as their average values,
1 m (gg[") (r respectively. Consider the scenario of A = I > Cammlles llg. - gli2 and Ax = maxxe[e] m
m
Theorem
2 (Eee error) and set d Assume that the first vectors are gi and the remaining m vectors an )9r - L2 R lgi - -g'l. while Aoo R 2e lg %/1-
are 1/2 for some constant c & m. Tn this case, Aoc,max = this scenario, the compressed values b for gí and g according to the Hadamardduuliiin differ at
m
k E K. C [m]] levels, then, A Hadamard RJ V 4 EREx (B/22-132
cBa Σ 2-2(k-1) < V
4e B 3m
I, where
9

---

Published in Transactions on Machine Learning Research (10/2025)
k* mingex & and upper bound the sum over the set K. by the sum of a geometric series. As Hadamard averages over all machines, it decreases with similar to A2 and should be much smaller than ma, The only case when it is not smaller than Ao. is when o and 32 are very close, so that Do mmax max = O(Vm-T), but the first level where they differ (min k) is very small. One such example is when the quantized values of gj in the set K sorted by the levels in increasing order are (+,,-1,-1,,- and that of 9/2 are (-1,+1,+1,+1)
As the vectors are extremely close in this case, the estimation error with A max is not very large. Further, if we assume a distributional assumption on the vectors Di, similar to how we generate Figure 2b obtaining vectors where AHadamard >
max happens with low probability.
Algorithm 4 SparseReg
2og L
2log L i-1
= BV
d2 1
(9)
Clients and server share A E ImLx and a per- Init()
d
mutation p~ Im.
Algorithm 5 OneBit
(g.
Init()
g/ 4 9i for j E [ do
Clients and server share unit vectors {zilve())
Encode (g:)
brg t arg re() (AG- o
b, +- --sign((00 (9;,))) 24)
gf + d4 ej 11
return bj
end for
b. 6 b ,00
Decode ((b he(m))
return b
Shen 2023 Algorithm 1) (Tech. I)
Decode (b. (bmmm)
g
1= 2,6; (Tech. II)
9 Zi Cpis) A 1669
Using this example, we can compare the error of our proposed schemes to baselines mentioned in Table 2 Assume a modification of the above example where each vector is d-dimensional, and all of it's coordinates are cither &f or 322 Consider any l compressor whose error is cither proportional to v B or 1/ and it sends & bits/client for some constants 1h v 0. The & error is defined as Elllō ]قااو and the loc error is defined as E[llğ ب[lاا]e therefore the corresponding fo error of these compressors is v or / A2. Now, consider the example that we just presented with d > I and all coordinates being equal for each vector. Therefore, A2 = lloo If and plugging this in, the bg error of the schemes is / VVB or
V M ad set v d. For RandK, this would mean setting K d'+log Now, if 1 1961 ze B but 9 oí < B, then B+ VdB. Using these approximations, the error of RandK is /(32 log djdB as v d 32 log d. This is much larger than the lo error of HadamardMultiDim as the first term is B 2 and the second term Hadamard ~ v v/ 192 ví.. A similar argument holds for all independent compression schemes, as their tx0 error scales as B, which in the worst case is vdB.
m l9'2 s'l. HadamardMultiDimm sends d bits/client; therefore, to compare with any of these schemes, we
For compressors whose error scales as D (PermK, RandKSpatial, RandKSpatialProo), we obtain the same number of bits/client as HadamardMultiDinn scheme by setting K 324logd- Consider RandKSpatialProjj
where V = 32+logd and the error for our example is / (32+log d'd 19'2-111- As long as dl > m, this error is larger m
than AHadamard by constant terms. similar argument holds for RandKSpatial and PermK. Additionally, note that the theoretical guarantoes for RandKSpatial and RandKSpatialProo do not hold if the correlation is unknown. Without this information, the heuristics they use do not result in theoretical guarantees, and their error might be bad as RandK. CorrelatedSRQ achieves the lower bound for collaborative compressors for d 1, and is based on coordinate-wise scheme, hence the Ax in its error guarantees. However, for d > 1, its error scales poorly. For the example described above, l|g:|12 I VdB, therefore, the lo error for CorrelatedSRQ is V 1 min dad B d' ). Even for K 2, correlated SRQ requires double the number of bits/ client as HadamardMultiDim. The first term of HadamardMultiDim is B - 2 which is much smaller than any of these terms, while AHadamard FS Ax for our example. Therefore, as long
K
10

---

Published in Transactions on Machine Learning Research (10/2025)
Pn2K 1/(2d-1) cd
VtdB mk. Hadamard is smaller than &o error of CorrolatedSRQ, The size of this interval for Ao increases d increases.
as
00
With the above example and analysis, we have specified the exact scenarios when HadamardMultiDin outperforms baselines, and this can be easily extended to SparseReg.
4 One-bit Schemes
In this section, our vectors are assumedd to belong on the unit sphere gd-1, Further, our goal is to recover the unit vector in the direction of the average vector g ( Lie(m) g:) m Eie(m Assumption 3 (Unit vectors). 9i sd-1,vi [m].
- 9:l12-
Consider the collaborative compressor where each client has sample 2, ~ Unif(S (which are also available to the server apriori). Client i sends the single bit b, = sign( (gi, 2)) to the server. To recover g, consider the trivial case when all vectors 9;8 were equal. Then, cach b; sign( (g. (1). and recover g. the server needs to learn the halfspace corresponding to y from set of labeled datapoints. Applying the same method to when 9&8 are not all the same, we can estimate by solving the following optimization problem.
min 1 + (z, gESa-1
(10)
Here, 1(-) denotes the indicator function. We intuitively view 10 halfspace learning problem with groundtruth g, but in the presence of noise, as 9i # g. Learning halfspaces in the presence of noise is hard in general (Guruswami & Raghavendra] 2006). In our setting, if we sample from the intersection of the halfspaces with normal vectors g and gi. then the label is sign zi)), otherwise, is -sign( (g, 2i)). We can consider this to be under the malicious noise model, wherein a fraction of datapoints are corrupted.
Lemma 1 (Malicious Noisc). If 2 Unif(S and 6; sign((#;, gi)), Vi E [m], then, with probability 1 O(exp(-mAcor)) S, the fruction of the set of dalapoints {(=,, by) [semm] salisfying sign( gi)) o sign( (g. =;) is equal to O @(Acarr) where Acorr &
mm Em arccos (gt,
The proof of the lemma is provided in Appendix C.1 Our methods will use Apor to measure the deviation between clients. For small Acorr: we obtain better performance. If (g. gi) 0, vi [m], then
T C
2 m
ΣΣ (gr 95) ISicjsm
(11)
As long as the corruption level, 2: we can hope recover the halfspace g. We provide two techniques Techniques T and II, to recover 9, thus yielding two corresponding Decode procedures.
The first decoding procedure (Technique I) is a lincar time algorithm for halfspace learning in the presence of malicions noise (Shen 2023 Theorem 3) that provides optimal sample complexity and noise tolerance.
Theorem 4 (Error of Technique 1). If Ç defined in Lemma is less than 1/2 after running Algorithm 5
with Technique with probability 1 - d 0(exp(-mAcox)) we obtain hyperplane ğ such that, (ō. (..g)
cos(T((Aus) + in polylog(d, 1, 1)).
The algorithm itself is fairly complicated. It assigns weights to different points based how likely they are to be corrupted. The algorithm proceeds in stages, wherein each stage decreases the weights of the corrupted points and solves the weighted version of [10.. The key technique is to use matrix multiplicative weights update (MMWU) (Arora et al.) 2012) to yield linear time implementation of both these steps, instead of Awasthi et al. 2017) which used polynomial time linear programs for this purpose.
Technique II the simple average algorithm of (Servedio) 2002), which obtains suboptimal error guarantecs for halfspace learning.
11

---

Published in Transactions on Machine Learning Research (10/2025)
Theorem 5 (Error of Technique II). If Ç defined in in Lemma 1 is less than 2, after running Algorithm with Technique II, with probability 1 - 8 - (corr)))) we obloin hyperplane y such that, (ū. g) cos(TT( cos(T(VdDcom + Vm (ogg())).
d
The performance of both techniques improves with decrease in Acorr- Since we have only m bits to infer a d-dimensional veclor, we require m d, with Technique II requiring m d. If we send & bits per client in OneBit, then the number of samples for the halfspace learning is mt, thus obtaining the guarantee in Table I The main benefit of OneBit schemes is their extreme communication efficiency. Existing quantization and sparsification schemes require sending at least log K or log d, where K is the number of quantization levels.
The proofs for this section are provided in Appendix C
Comparison to ly compressor. Note that, we can use compressor for lg error to first decode the mean and then normalize it to obtain its unit veclor. If such scheme uses bits and has &g error either AA2 (o.0) 2 1 or A then its cosine similarity TT
2|o for llg'lle = 12, where g' 1 E 9i and ğ is the estimate of g'. To compare this with OneBit Technique I, we send À bits per client to obtain the same communication budget. The cosine similarity of this scheme is cos(T + +.).. We can lower bound da this similarity by 2 22m + 2nT² m² as cos(x) 2 1 I. Comparing this cosine similarity with that obtained for f2-compressor, as long as 2 corr 2n² m²B < A, OneBit Technique I performs better. For mK If we set t = 32K + K log d, OneBit Technique outerperforms the sparsification scheme as long as Dcore small.
A
de
any sparsification scheme sending K coordinates, A is at least d
5 Experiments
Setup. To compare the performance of our proposed algorithms, we perform DME for three different. distributions which correspond to the three error metrics covered by our schemes l2 foo and cosine distance. Then, we run our algorithms as the DME subroutine for four different downstream distributed lcarning tasks KMeans, power iteration, linear regression and logistic regression. K.Maans and power iteration are run on MNIST [Leunn & Cortes 2010 and FEMNIST (Caldas et al., 2018) datasets, and we report the KMeans cost and top eigenvalue as the metrics. For linear regression, we run gradient descent on UJIndoorLoc (Torres Sospedra et al., 20144) and a Synthetic mixture of regressions dataset, with low dissimilarity between the mixture components, and report the test MSE. For logistic regression, we run gradient descent on the HAR (Reycs-Ortiz et al., 2012 datasct and report the training loss and test accuracy for binary classification. We compare against all baselines in Table 2 for 5 random seeds and report the methods which perform the best. For DME experiemnts, the shaded corresponds to 2 standard deviations around the mean, while for all downstream tasks, it corresponds to 1 standard deviation. The results for KMcans, power iteration and lincar regression are reported in Fig 2 while the results for logistic regression are reported in Fig Additional details for our experimental setup are deferred to Appendix D
Results. Distributed Mean Estimation. From Fig 2a and 2b HadamardMultiDim and SparseReg, whose error is optimal in m, obtain the best performance in terms of loo and lg error for low dissimilarity. Especially, for HadamardMultiDim in Fig 2b the gap in for error to next best scheme is very large. NoisySign obtains competitive performance to other baselines as we use a large a. The performance of OneBit for cosine distance metric (Fig 2c shows that compressors with lz ertor guarantees perform poorly in terms of cosine distance. For all collaborative compression schemes, including our proposed schemes, performance degrades as dissmilarity increascs. From Fig 2a and 2b the rate of this decrcase more severe for SparseReg than HadamardMultiDim.. For large dissimilarity, HadamardMultiDim and SparseReg can perform worse than certain baselines.
KMeans and Power iteration. For MNIST dataset, where dissimilarity is low, HadamardMultiDin performs best for KMeans and close to the best baseline for power iteration (Fig 2d and 2e). Most of our collaborative compression schemes do not perform as well as RandK on FEMNIST, due to higher client dissimilarity. OneBit is very communictiion-cficiiii ensures that it still remains competitive for KMeans(Fig 2g) By increase in confidence intervals for the same baselines from MNIST to FEMNIST, we can see that FEMNIST dataset is much more heterogeneous.
so running it for the same communication budget as our basclines
12

---

Published in Transactions on Machine Learning Research (10/2025)
6, vi's Je sdith 2 and doviationa for gazaiaa
C. oreer v/a A., with atd deziatiors for vectun from lypercabe
Cosine distance v/' A.r with 2 doviation for unit veckors
114
Kinds
Dren
WP-
Sod Pog
Karie
327
SRQ
Spritting
Certrox thQ
327
Coine GREANO
09
17
Conward Consired ar
01
yeg
297
.7
(a) DME with & error.
(b) DME with for error.
(c) DME for cosine distance.
KMRans on dataset mnier
Power Iteration on dataset mnist
inear Reginesion rottase vilddoode
Drive
Sard Pvo
Necamen
Sponehiig
2.0
00"
Oneeit:
2.0
DedimardHuutii
107
SearseReg
2.6
1.4
Spette
Sparweligg
SRC
15
1.2
Band
10
0
10
25
10
15
20
25
30
Borations
Eorations
(d) KMeans on MNIST.
(e) Power iteration on MNIST.
(f) Lin. Reg. on UJndoorLocc.
Lincar Regression dataset synthetic
famist
Powcr Beration detact lamii
x19*
1160
SpansRig
10-
1140-
12
OvdEi.
CB-
1120
1100-
[4-
1060
35-
C3-
540
1060-
iacamardM B RonicSpetteiin Spersckee
1010
0
20
29
10
20
30
40
50
baatiess
Berations
(g) KMeans on FEMNIST.
(h) Power iteration on FEMNIST.
(i) Lin. Reg. on Synthetic.
Figure 2: Performance of DME(Distributed Mean Estimation), KMeans, Power iteration and linear regression for the same communication budget. For each experiment, we report the best compressors. Lin. Reg. refer to Linear Regression. For power iteration, higher top eigenvalue is better. For all other experiments, we report the error, so lower better.
Linear Regression. From Fig 21 and 2i all collaborative compressors perform better than independent compressors as UJIndoorLoc and synthetic datasets have low dissimilarity among clients as compared to FEMNIST. Our schemes can take full advantage of this low dissimilarity, so HadamardMulliDin and SparseReg outperform baselines on both datasets. As the Synthetic dataset has lower dissimilarity than UJIndoorLoc,, even the NoisySign performs better than other basclines. Further, OneBit obtains best performance.
Logistic Regression. From Fig our compressors, Onebit, Sparsereg, and HadamardMulltDmm, are the best, second, and fourth best compressors, respectively, in terms of both training loss and test accuracy. Further, among the top 4 best-performing schemes, only one baseline, RandKSpatialProoj comes in third. This shows the benefit of using collaborative compressors.
Stability of Our Algorithms. Among all our proposed algorithms, OneBit and SparseReg are the most stable with respect to different random seeds followed by HadamardMultiDim and NoisySign. The most stable algorithms among all baselines seems to be RandKSpatialPojj. OneBit and Sparsereg are slightly less stable
13

---

Published in Transactions on Machine Learning Research (10/2025)
Logislic Regression on dalasel har
Logistic Regression on dalasel har
HadarardMMult
95
"seReg
Training Loss
0.5
RandKSpelaalPro
Test accuracy
90
0.4
80-
HadamardMMthiimm
0.3
OneBit
75
SparseReg
0.2
kendk-petiallroi
70
50
100
150
200
0
50
100
150
200
Iterations
Iterations
Figure 3: Performance of compressors for Logistic regrossion on HAR RReyes Ortiz et al. Training Logistic loss, Right Test Accuracy.
2012 datasct. Left:
than it. However, all our algorithms except NoisySign are much more stable than most other baselines like SRQ, Correlated SRQ and RandK.
6 Conclusion
We proposed four communication-efiiienn collaborative compression schemes to oblain error guarantees in fz-error (SparseReg), fo-error (NoisySign, HadamardMuitiiinm) and cosine distance (OneBitAvg). The estimation error of our schemes improves with number of clients, and degrades with increasing dissimilarity between clients. Our schemes are biased and our dissimilarity metrics (Areg, AHadmmara) depend on the quantization levels. However, these drawbacks can be removed by using existing techniques for converting biased compressors to unbiasod oncs [Beznosikov al., 2022), and adding noise before quantization (Tang et al. 2023; Chzhen & Schechtmani 2023). Schernes such as error feedback (Karimireddy al., 2019) reduces the error of independent compressors, and it will be interesting to check if it works for our collaborative compressors.
This work is supported in part by NSF awards 2217058 (EnCORE) Inst.), 2112665 (TILOS Inst.), and a grant from Adobe Research.
Acknowledgment.
References
Ahmad Ajallocian and Sebastian U. Stich. Analysis of SGD with biased gradient estimators. abs/2008.00051, 2020.
CoRR,
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication Efficient SGD via Gradient Quantization and Encoding. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: meta-algorithm and applications. Theory Comput., 8:121-164, 2012.
Pranjal Awasthi, Maria Florina Balcan, and Philip M. Long. The power of localization for efficiently learning linear separators with noise. ACM, 63(6), jan 2017. ISSN 0004-5411, doi: 10.1145/3006384.
Jeremy Bernstein, Yu-Xiang Wang. Kamyar Aviwadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning, pp. 560 569. PMLR, 2018a.
Jeremy Bernstein, Yu- Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signSGD: Compressed optimisation for non-convex problems. In Jennifer Dy and Andreas Krause (eds.), Proceedings
14

---

Published in Transactions on Machine Learning Research (10/2025)
of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 560-500 560-569..00 PML.R, 10-15 Jul 2018b.
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On Biased Compression for Distributed Learning, December 2022. arXiv:2002.124: 12410 [es, math, stat].
Léon Bottou and Olivier Bousquet. The Tradeoffs of Large Scale Learning. In J. Platt, D. Koller, Y. Singer, and S. Roweis (eds.); Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007.
Petros T Boufounos and Richard G Baraniuk. 1-bit compressive sensing. In 2008 42nd Annual Conference on Information Sciences and Systems, pp. 16-21. IEEE, 2008
Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, and David Woodruff. Communication lower bounds for statistical estimation problems via distributed data processing inequality. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, pp. 1011 1020, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450341325. doi: 10.1145/ 10.1145/2897518,... 289772
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Found. Trends Mach. Learn., 8(3-4): 231 337, November 2015. ISSN 1935-8237. doi: 10. 1a.1151/220 /2200000050.
Sebastian Caldas, Peter Wu, Tian Li, Jakub Konečný, H. Brendan McMahan, Virginia Smith, and Ameet Talwalkar. LEAF: A benchmark for federated settings. CoRR, abs/1812.01097, 2018.
Sook-Ho Chang, Pamela C. Cosman, and Laurence Milstein. Chernoff-type bounds for the gaussian error function. IEEE Transactions on Communications, 59(1))22939 2944, 2011. doi: 1.1109/TCOMM.20111
072011.10004..
Xiangyi Chen, Tiancong Chen, Haoran Sun, Steven Z. Wu, and Mingyi Hong. Distributed Training with Heterogeneous Data: Bridging Median- and Mean-Based Algorithms. In Advances in Neural Information Processing Systems, volume 33, pp. 21616-21626. Curran Associates, Inc., 2020.
Evgenii Chzhen and Sholom Schechtman. SignSVRG: fixing SignSGD via variance reduction, May 2023. arXiv:2305.13161 [math, stat].
Peter Davies, Vijaykrishna Gurunanthan, Niusha Moshrefi, Saleh Ashkboos, and Dan Alistarh. New bounds for distributed mean estimation and variance reduction. In International Conference on Learning Representations, 2021.
Venkata Gandikota, Daniel Kane, Raj Kumar Maity, and Arya Mazumdar. vqsgd: Vector quantized stochastic gradient descent. IEEF Transactions on Information Theory, 6877):4573-4587, 2022. doi: 21..109//TT.2022..111
Ankit Garg, Tengvu Ma, and Huy Nguyen. On Communication Cost of Distributed Statistical Estimation and Dimensionality. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
Avishek Ghosh, Raj Kumar Maity, Swanand Kadhe, Arya Mazumdar, and Kannan Ramchandran. Commmication--ffiieett and byzantine-robust distributed learning with error foedback. IEEE Journal on Selected Areas in Information Theory, 2(3):942-953) 953,, 2021.
Venkatesan Guruswami and Prasad Raghavendra. Hardness of learning halfspaces with noisc. In 2006 47th Annual IEFE Symposium on Foundalions of Computer Science (FOCS pp. 543 552, 2006. doi: FAA.L09/FOCSS20066..3
Divyansh Jhunjhunwla,, Ankur Mallick, Advait Gadhikar, Swanand Kadhe, and Gauri Joshi. Leveraging spatial and temporal correlations in sparsified mean estimation. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 14280 14280-14292. Curran Associates, Inc., 2021.
15

---

Published in Transactions on Machine Learning Research (10/2025)
Shuli Jiang, Pranay Sharma, and Gauri Joshi. Correlation aware sparsified mean estimation using random projection. In Thirlg-seventh Conference on Newral Information Processing Systems, 2023.
Richeng Jin, Yufan Huang, Xiaofan He, Huaiyu Dai, and Tianfu Wu. Stochastic-Sigh SGD for Federated Learning with Thcoretical Guarantoes, September 2021. arXiv:2002.19940 [cs, stat].
Richeng Jin, Xiaofan He, Caijun Zhong, Zhaoyang Zhang, Tony Quek, and Huaiyu Dai. Magnitude Matters: Fixing SIGNSGD Through Magnitude-AWe Aware Sparsification in the Presence of Data Heterogeneity, February 2023. 4rXiv22302.96634 [cs].
Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio. Agnostically Learning Halfspaces. SIAM Journal on Computing, 377)):1777-1805, January 2008. ISSN 0097-5397. doi: 10.1137/ 060649057. Publisher: Society for Industrial and Applied Mathematics.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. In Kamalika Chaudhuri and Ruslan Salakhutdinov (ods.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 3252 3261. PMLR, 09-15 15 Jun 2019.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 1143. PMLR, 13-18 Jul 2020.
Jakub Konečný, H Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimization: distributed machine learning for on-device intelligence. arXiv preprint arXiv:1610. 1x1::6600.0227,, 2016.
Jakub Konečný and Peter Richtárik. Randomized Distributed Mean Estimation: Accuracy vs. Communication. Frontiers in Applied Mathematics and Statístics, 4, 2018. ISSN 2297-4687.
B. Laurent and P. Massart. Adaplive estimation of quadratic functional by model selection. The
Annals of Statistics, 28(5), October 2000, ISSN 0090-5364. doi: 10. 10.1214/aos /014///0/11155553//5 URL http: 7/dx. do1. dow..oroo..oo..o.ooooo...oo..o.. org/ 10. 1214 2221///000015957355
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010.
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In International Conference Learning Representations, 2020.
Xiang Li, Shusen Wang, Kun Chen, and Zhihua Zhang. Communcation--ffiiieet distributed svd via local power iterations. In International Conference on Machine Learning, pp. 6504-6514. PMLR, 2021.
Yingyu Liang, Maria-Florina Balcan, and Vandana Kanchanapally. Distributed pea and k-means clustering. 2013.
Yingyu Liang, Maria-Florina F Balcan, Vandana Kanchanapally, and David Woodrulf. Improved distributed principal component analysis. Advances in neural information processing systems, 27, 2014.
S. Lloyd. Least squares quantization in pem. IEFE Transactions Information Theory, 282:1129113 1982. doi: 10.1109/TIT.198)
Prathamesh Mayekar, Ananda Theertha Suresh, and Himanshu Tyagi Wyner-Zih Ziv Estimators: Efficient Distributed Mean Estimation with Side-Inforration. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, pp. 5502-3510. PMLR, March 2021. ISSN: 2640-3498.
Brendan McMahan and Daniel Ramage. Foderatod learning: ing without centralized training data. 2017.
Collaborative machine learn-
16

---

Published in Transactions on Machine Learning Research (10/2025)
H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effcienn learning of deep net works from decentralized data. arxie preprint or Xiv: 05629, 2016.
Jorge Keyes-Ortiz, Davide Anguita, Alessandro Ghio, Luca Oneto, and Xavier Parra. Human Activity Recogni- tion Using Smartphones. UCI Machine Learning Repository, 2012. DOI: https:///oi.orr/ 22442//C54S4K
Herbert Robbins and Sutton Monro. Stochastic Approximation Method. The Annals of Mathematical Statistics, 22(3):400 407, 1951. doi:
Mher Safaryan and Peter Richtarik. Stochastic Sign Descent Methods: New Algorithms and Better Theory. In Proceedings of the 38th International Conference on Machine Learning, pp. 9224 9234. PMLR, July 2021. ISSN: 2640-3498.
Mher Safaryan, Egor Shulgin, and Peter Richtárik. Uncertainly principle for communication compression in distributed and federated learning and the search for an optimal compressor. Information and Inference: A Journal of the IMA, (2))5555--580, 04 2021. ISSN 2049-8772. doi: 10000//maaa//aaaaaaaaa
Rocco A. Servedio. Perceptron, winnow, and pac learning. SIAM Journal on Computing, 31(5):1358 1369, 2002. doi: 00.1137/00097733773300022
Jie Shen. Pac learning of halfspaces with malicious noise in nearly linear time. In Francisco Ruiz, Jennifer Dy, and Jal-Willem van de Meent (eds.), Proceedings of The 26th International Conference on Artificial Intelligence and Slatislics, volume 206 of Proceedings of Machine Learning Research, pp. 30-46. PMLR, 25 25-27 Apr 2023.
Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with Memory. In Advances in Neurol Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Ananda Theertha Suresh, Felix X. Yu, Sanjiv Kumar, and H. Brendan McMahan. Distributed Mean Estimation with Limited Communication In Proceedings of the 34th International Conference Machine Learning, pp. 3329 3337. PMLR, July 2017. ISSN: 2640-3498.
Ananda Theertha Suresh, Ziteng Sun, Jae Ro, and Felix Yu. Correlated Quantization for Distributed Mean Estimation and Optimization. In Proceedings of the 39th International Conference Machine Learning, pp. 20856 20876. PMLR, June 2022. ISSN: 2640-3498.
Rafal Szlendak, Alexander Tyurin, and Peter Richtárik. Permutation compressors for provably faster distributed nonconvex optimization, 2021.
Zhiwei Tang, Yanmeng Wang, and Tsung-Hui Chang. Sig-SignFedAAv: A Unified Stochastic Sign-baser Compression for Federated Learning. February 2023.
Joaqun Torres-Sospedra, Raul Montoliu, Adolfo Martnez-Us, Us, Tomar Arnau, and Joan Avariento. UJLindoorLoc. UCI Machine Learning Repository, 2014. DOI: https://doi.orr//I 11..1.132///////
Shay Vargaftik, Ran Ben-Basat, Amit Portnoy Gal Mendelson, Yaniv Ben-Itzhak, and Michael Mitzenmacher. DRIVE: One- bit Distributed Mean Estimation. In Advances in Neural Information Processing Systems, volume 34, pp.
Curran Associates, Inc., 2021.
Ramji Venkataramanan. Antony Joseph, and Sekhar Tatikonda. Lossy Compression via Sparse Linear Regression: Performance Under Sinimum-Distanee Encoding. IEEE Transactions Information Theory, 60())33254-3264, Junc 2014a. ISSN 1557-9654. doi: 10.1109/TTT.22 2TT..2211..1302....
Ramji Venkataramanan, Tuhin Sarkar, and Sekhar Tatikonda. Lossy Compression via Sparse Linear Regression: Computationally Efficient Encoding and Decoding. IEEE Transcction on Information Theory, 60(6):3265-322) -278,, June 2014b. ISSN 1557-9654. doi: 10.1109/TTT.2014..2 46776
Roman Vershynin. High- Dimensinnl Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018
17

---

Published in Transactions on Machine Learning Research (10/2025)
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Terngrad: ternary gradients to reduce communication in distributed deep learning. In Proceedings of the 31st Intervational Conference on Neural Information Processing Systems, NIPS117, pp. 1508 1518, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964.
Heng Zhu, Avishek Ghosh, and Arya Mazumdar. Optimal compression of unit norm vectors in the high distortion regime. In 2023 IEEE International Symposium on Information Theory (ISIT), pp. 719 724. IEEE, 2023.
A Proofs for Section 2
A.1 Proof of Theorem 1
As all operations are woordinate-wise, restrict our focus to only single dimension j E [d].
Eg, 10,10:0011 $ (1)) E [m]
Note that (1) erl( ( and (1) 22a (t). By Hoeffding's inequality for bounded random variables we have,
/2
Pr[
(6, (1)
(1) 2 S 2e
If we set = / cclog(m) m
for some c > 0 in the above incquality, then with probability 1 2m we have,
(6. (
We can represent EmT = (g) as 2a is an invertible function. To find the difference between ğ and g, find the difference & (g) (g) With probability 1 2m - we have,
Φ (g6d) (g <
$ (1 {1(g0)))+
To remove the terms of Po we can apply the function Φ= on goo) As क5 not Lipschitz, we need to perform its Taylor's expansion around (g) to account for the linear terms in the error. Tf A I Em (1))) D (1)) then we obtain,
max WE (0)) Do 1, (g60)++
(0.)((u)(Ao +t)
(12)
We now obtain an appropriate upper bound on (Φ=1y(u) as we do not have a closed-form expression for it. We will use the properties of erf obtain a suitable bound. First, note that Φ and Φ- are both odd functions, therefore, | "w)) | ((u)), we consider the bound for O. Note that (4 (4-1)(u) = 3 (w]) For u O, we have,
1 - l-er((u) =u- u²
erf(u) 21 e =u²
erf (r)) SV log(1 u)
Φ-1 (u) = /2o erf (uu) So 1 2log(( [ - u)
(6- (--)(()= T
(0- (w)) 1202) s 2
2lo ww-
- 2
18

---

Published in Transactions on Machine Learning Research (10/2025)
For the first step, the fact that if [(x I g(x), then (v) 2 (y))
upper bound the complementary error function. For the third step,
Using the following upper bound in Eq 12 we obtain,
Ao +
(g - g(o|l -
max (g
9. (06))
+
1 - |u|
A.. +
SV 2 max (g(1)))) Ds
t/ (g(1)) + Do +
We use max max (1)) Do 14. (b(()0) Ao + 11 - )b(10(01) + Do + +1, as D is increasing odd function.
As + (19601))) 1g(0 - 900و S )1-1-00(000))
-11
We exlend the bound to d dimensions by laking union bound, yielding a probability of error 2dm
A.2 Proof of Equation
(3
First, note that the term of required for this are As to be small and both m and a(]])]>>)) to be large. Note that a(19[1>>>) क (1gg)) I>]), so it is small when the ratio ||al is small. The bound on estimation error after this step is the following.
- S ((x) when x S c for some constant c E [0, 1]. The conditions
Ao + V - m
log
| gllxx =0 =0
a(l191loo)
Now, we lower bound the term a(Il9llo=). Note that a(z) = 1 D (x) [1 erf( (io for any E R4 where erf is the error function. Here, 1 erf(()) is the complementary error function for any æ 2 and it is Plugging in this lower bound, we complete the
lower bounded by Q( =xx²) -(x="'z²) for 3 1 Chang et al. 2011
proof for a B = ///222 2"
1
A.3 Proof of Equation (4)
The proof follows from using the triangle incquality and Taylor's expansion for each ( around g Note that, for some v.()) between g(و) and of we have,
2 (g 9 (
L (1)) = (g +
σ
(لاوو
bb (g( Φ ((او) x
(1 20
We use the fact that
1. By using triangle incquality for any coordinate E [m], obtain,
Ao < max
c g
(1)
max jE(d]
(g.
(g(
jEld] m
m
[m
[m
2
ا0وو
(j)
2 1
l|g - gz
max jEid
EE [7)
19

---

Published in Transactions on Machine Learning Research (10/2025)
B Proofs for Section 3
B.1 Proof of Theorem 2
To prove this Lemma, we first consider single dimension j [d]. Note that the collaborative compression scheme has precision 2m-1- Since, for each client g. lics in the range [g Amax, g max),, therefore, we must. decode one of the elements which has error atmost A Amax Tm-T- Since this is true for each coordinate individually, therefore, holds for the foo norm.
Consider a single dimension j E [d]- Let 9: be the jth coordinate of 9i and Pj be the permutation selected for the coordinate j. We omit j from g/6)) and Pj to simplify the notation. Let bt.p be the estimate of 9i after decoding it for p levels where p E [m]] Therefore, the estimator ğ = m b B 24 Let gi Σk=
b 2 be the
decoded value of 9: till level m and g 1 m - Σi= B where b% m
E b
We compute the expected error for coordinate j, where the expectation is wrt the permutation Pj- Note that Ep [i]
1m 11g 9] / (Ep 11g T11)² S E Ep
-|
E Ep- 19 g) + lg g
m
I Ep-in.. 19 -g|2 + - -
- gil + V E Ep 18 - g
1=1
B
< 2 + EpwiII 2
We use Jensen's 's inequality for the first inequality. For the second inequality, we use bias-variance decomposition for the random variable ÿ. where the first term is its variance, and the second term is its bias wrt the term g- We then use Va - < vā + vb for any a, 2 0. To handle the term Ig - G), we expand both terms as a summation over m clients, followed by a triangle inequality. As each estimator 9. is least B 2m away from
B gs, cach term in the difference 9i ğil has the upperbound 2m-1-
We now bound the variance term separately. Note that
Bp-1ip lğ -gl² 1. |/|2 2
20

---

Published in Transactions on Machine Learning Research (10/2025)
We first evaluate the second moment Ep-.... 19
bi,ps
1
82 1
bi,.. 6g.03
Bp--IT,, |0|
B²
20:
220:
20:
203 -1
Isifssm
B
Brips
BL.s
22k-2
B
ps
E pp-.I..
20-1
20: 20:-1
Ip
k=1
ISijjsm
B
bi.p.
1
ر
B
Epp
22k-2
20:
1=1.Ip 171
21
Isijism
B
B
bick
m
ΣΣ>
2
m(m 1)
2h-1
21-1
k=1
15t#)Sm
1= 1=1,
B
BLABBB Σ
Σ
b 2
22k-2
m(m IsifIs
2
k=1
1
m BZ
m(m
1)
22k-2
Icifj jm
m
B2
m
BBbbabbjk
Felhi
22k-2
mmm 1)
m(m
22k-2 2
k=1
Isifjsm
15 Sm k=1
m²
1g|2
Σ 1= 19:1?
Bi + 1bjj bb,.))
m(m- 1)
m(m 15isjs k=1
22k-1
Ei=1
10:
1
m ΣΣ>
B(bi, bzik)
m m(m 1) +
|01
2m(m - 1) Igifjsm k=1
2
Note that we expand the square of the sum of terms where 8ū = 1. For the second term, we use the law of total expectation by conditioning on the value of pt- To evaluate the inner expectation, we note that Pj can take any value other than that of p; with equal probability. To evaluate the outer expectation, note that Pi can take any value in [m] with equal probability. In the fourth equation, we subtract the term where == Then, we can factorize the remaining terms to obtain ğ and ğj. Note that the sum of the product terms 9:9j can be expressed as E 0al?, with the square terms subtracted. Further, we express the term B² ΣΣ B² +bb2
1b 1. Finally, we complete the squares for each term k.
228-2
226-1
Using the above value of second moment E Ep ? we can compute the variance,
m 10s12 1=
M
B(b kg,k) 2
E Ep 1/ - = E PT II... 1312 1
ΣΣΣ
Σ
m
2m(m 1),
ISiF)S k=1
BiDiR (y 2
2m
-
15ifjsm k=
We use g² ~ L > 10 1-
ΣΣΣE
2m
2m
15if55
15iff5m
To simplify this bound, we need to incorporate the difference in the actual gradient vectors. For this purpose, we try to bound the differences bb., - by in terms of Aij A lg. gol- II Aij lg Ijl, then be = -,,e, vk 2 log A.
B
21

---

Published in Transactions on Machine Learning Research (10/2025)
B.2 Proof for Theorem 3
We first show how to obtain the coefficients a and the bound on the term A in Eq (7) To obtain the
coefficients Gi we replace set L = m, = d, R = mogg and x² Eq 2). Note that the terms 61 and d2 can be directly applicd in (Venkataramanan et al., 2014b] Section V with the same values of eg and "t- Note that the bound on A in is for gaussian sources with fixed variance, however, their proof in (Venkataramanan et al. 2014b Section
B² =²=B"n in /Venkataramaaan et al. 2014b
(Venkalaramanaa al. 2014b, Theorem 1)
V) only uses the fact that the squared l norm of the source is bounded, which is exactly case from Assumption 2
The proof of Eq is same as Theorem 2 for a single dimension, with the coefficients श replaced by and b1r) replaced by A Following Appendix B.1 we can write down the &g error.
B
E 1T 11 21 = Ep-H |l|g E. 1 1 + E I| Ep- [7]
E = g 1
m Di=10 Is, where gi Σド= Cf By triangle inequality, the first term is m Em
9. 1.1. which is bounded individually by A (1 10 L las (61 + 82))² (1 log I L = m, = d, R= mlogL ,² d
d
by setting
Da and 60 = 0 in Venkataramanan et al. 2014b, Theorem 1).
For the second term, we need to bound B||@11]]
m m
A 1111)4tb 112
m
Ep-nI..
A(=()) 1)
m Isijss
m
EppTI. (G100))/AA(0)) Auee
m(m
m3llg/13 Ex 1|
m
Σ of All - -(R- m(m 1) mi
ΣΣ
m(m 1)
The remainder of the proof follows proof of Theorem 2 with |-|2 replaced by 11-112
For the first equation in Eq since the collaborative compression scheme has precision A, for each client, the vector 9: lics in ball around of radius A2, maxie[m] gll2- Therefore, if we sparse regression codes to individually encode each vector Ji, it's decoded value must lie either in the same ball or be at most A l2 distance away from some vector in this ball. Since this set is convex, and the vector g is also obtained as a convex combination of vectors inside this ball or at most A away from it, the vector ğ also lies inside this ball or is at most A away from it.
This proves Eq
B.3 Proof of Equation 8 and Remark 1
To bound Areg, we need bound the terms of the form [| - A 1)2 113 for clients i [m] and at level & E (m]. Note that if by, be,s, then this difference is O. If by # ba then this is r2 from the
22

---

Published in Transactions on Machine Learning Research (10/2025)
definition of (61, 82, Cover.. This results in the following upper bound for Areg.
22 log L
ΣΣ 11
log L
k-1
A reg
10 + bzx))
1lbax # bz.k)
dem
d
1.j k=1
k=1
2r B² log L
k-1 2 L
ΣΣ>
1 + bz.k)
dm?
1=1
We use the value of C₁ in the second incquality and then simplify the terms.
To prove the bound of I for the case of Gaussian A in Remark 1 note that T is an upper bound on the the squared & norm of the difference of two gaussian random vectors. For any 71, E [4] with ri * rg. A(k-1)I++ - (I--11)++ ~ (0, 2II) as each vector is d-dimensional, they are sampled independently, and each element in each vector is sampled from a unit normal. Therefore, 1 {(1A(x-1)L+n - -(x=1))+rr)
l1 is xa random variable. Note that the scaling of & is to normalize the covariance to Ia. By concentration of Xa random variables from (Laurent & Massart 2000), we know that, with probability 1 1-
[|((-1)E+T - A(t-1)ttra1 s 2d + 4v dlog(1//)) 4log(1/8)
Since r1, [Z], we take union bound over all 1(L-1) unique pairs of (r1, Further, we can take union bound over all levels & E [m]] These would set the probability of error to mL(L-1)6 Setting d3 to this value, we obtain IL[L-1j
2
2
26g and the following bound Vk [m], + [4],
mL? || A(k- 1) 111 2d + V d
mL?
+ 4log(
a p
53
83
We upper bound L(L-1) by T.2.
B.4 Improving HadamardMultiDim and SparseReg with Repetitions
Let ğn n ER ğ(r) be estimator after R repetitions where ū(r) is the estimator after 1 repetition of either HadamardMMlliDDi or SparseReg. To compute the error for both Theorem 2 and Theorem 3 we use a bias-variance decomposition of the squared estimation error. Consider SparseReg where we bound Ep- [1g - glßž]. Note that even with the new definition of ÿ, it's mean wrt remains the same as Ep-nt., [ = Σ [((r) E = This contributes to the term with exponential dependence on and it remains the same. Note that the variance term, however, decreases with R.
1
A
Bp |l@
E EI lllā(r) 01 R
BP- (1((1) - g
R 1=1
R
Similarly for HodamardMultiDim, the term Aademard replaced by Atadlmand we take square root of the vR variance in it's analysis. Note that the A2,axx and max terms are not affected by R as it's analysis does not use p.
C Proofs for Section 4
C.1 Proof of Lemma 1
To prove this Lemma, note that b. = sign( =)) F sign((g, 21)) only if is sampled from the symmetric difference of and g. The probability that a z; sampled uniformly from gd-1 lies in this symmteric difference is given by so.)). If we set Acar = - Exe(m) arccos( g.)))
Let { be the fraction 2, such that b, # sign((g. 2)). Then, by Chernoff bound, we have,
7mmocex 247
Pr|s 2 (1++))ccol) <
23

---

Published in Transactions on Machine Learning Research (10/2025)
By setting y to be any small constant, we obtain, with probability 1 O(exp((mAmear atmost Ç ((cco)) fraction of datapoints are not generated from the halfspace with normal g and are thus corrupted.
C.2 Proofs of Theorem and 5
To prove Theorem
utilize the guarantees of (Shen 2023
Theorem 3), where the sample complexity Theorem 3) obtains error guarantee linear The error guarnntee is in terms of the
requirement ensures that the error is ) Further, (Shen 2023
in the noise rate of the samples which is obtained from Lemma symmetric difference between Ò and wrt the uniform distribution on the unit sphere. Since this is equal to the angle between these two vectors divided by æ, this gives us a bound on the inner product of these two unit vectors.
To prove Theorem from Kalai et al. 2008 Theorem 12), the sample complexity provides the term Vm while the noise tolerance provides the term VdDcorr-
C.3 Proof of Equation
To prove this remark, note that arccos(æ) is concave for x 2 0. Therefore, by applying Jensen's 's incquality, we obtain,
A AcOrT
arccos (gi. 9)) $ x
1
arccos
1 m
Σ gr.
m
arccos
|1 " 16 9ell2
( m
Mr ic[m]
π
1
Eie(m (9t, gt)
Σ
2
ΣΣ (ot, (لو 9ل)ll
arccos
arccos
m²
m²
iE|m]
Isicism
arecos
1
ΣΣ ISKgss
(gr.g5)
m
D Additional Experiment Details
Baselines We implement all the baselines mentioned in Table 2 As all these baselines are suited to & error, for the DME experiment on gaussians, where & error is the correct metric, compare SparseReg (Algorithm to all these baselines. For lo error uniform distribution, we implement NoisySign (Algorithm HadamardMuuliDim (Algorithm 3) and compare it to Correlated SRQ (Suresh et al. 2022), as it's guarantees hold in single dimensions. We also add comparisons to its independent variant, SRQ (urrehh et al. 2017) and Drive (Vargaftik et al.] (2021), which performs coordinate- wise signs. For the unit vector case, we implement OneBit (Algorithm Technique II) and SparseReg( Algorithm 4 and compare it with one independent compressor (SRQ (Suresh et al. 2017)) and one collaborative compressor (RandKSpatialProo) (Jiang et al. Note that we set d 512 throughout our experiments and tune the parameters (number of coordinates Jhunjhunwala et al.) 2021) or the quantization levels in (Suresh et al.) 2022 so that all compressors have the same number of bits communicated. For compressors without tunable parameters, we repeat them to match the communication budget. The communication budget is 2375 25 bits/client for each compressor every round. It often not possible for two different forms of compressors, like sparsification methods and quantization methods to achieve the exact same communicat tion budget even after tuning hence allow small range of communication budgets.
and
2023
sent
Konečný & Richtárik 2018
2017
Datascts For the distributed mean estimation task, we generate d dimensional vectors on m 100 clients.
To compare f error, we generate g with | = 100. Then, each client generates from a ( A3), where A₂ E 0.000, To compare loo error, we generate uniformly from a hypercube [-B, B]d where = 100. Each client generates 9. from smaller hypercube |- A,, centered at where A. E [10-3 3, 102). To compare cosine distance, we generate g uniformly from the unit sphere, and each client generates 9i uniformly from the set of unit vectors at cosine distance Acorr from the g, Here, Aporr E (0.01.0.4]
24

---

Published in Transactions on Machine Learning Research (10/2025)
For KMeans and power iteration, set = 50. FEMNIST is real federated dataset where each client has handwritten digits from different person. We apply dimensionality reduction to set d = 512. We run 20 iterations of Lloyd's algorithm (Lloyd] 1982) for KMeans and 30 power iterations. For distributed linear regression, the Syuthetic dataset is a mixture of linear regressions, with one mixture component per client. The true model w, E Rd for each component obtained from DME setup for gaussians with 4g = Then, we generate n = 1000 datapoints on each client, where the features are sampled from standard normal, while the labels y are generated as y (w;, .²) + E, where & is the zero-mean gaussian noise with variance 10-2. For UJIndoorLoc, for UJIndooLLoe dataset is to predict the longitude of a phone call. For both the linear regression datasets, we run 50 iterations of GD. For MNIST and UJIddooLooc, we split the dataset uniformly into m chunks one per client.
the first d 512 of the 520 features following (Jiang et al. 2023). The task
For logistic regression for binary classification, we select the last classes of the HAR and label them with +1. We split the datasct into m = 20 clients iid. HAR datasct has 561 features which we reduce by PCA to d = 512. We run distributed gradient descent with learning rate 0.001 for T 200 iterations on the logistic loss, where the logistic loss for any data point (a, y) E H x [+1} is defined E(w, (z, y)) log(1 + exp(-((wx)) y) for any weight w E Rd.
Metrics With the same number of bits, we can directly compare the error of baselines. For mean estimation, we measure & error, loo error and cosine distance for gaussian, uniform and unit vectors respectively. For KMeans, we report the KMaans objective. For power iteration, we report the top eigenvalue. For linear regression, we provide the mean squared error on a test dataset. For logistic regression, we report the training logistic loss and test accuracy for binary classification. For all experiments except power iteration and test accuracy logistic regression, lower value of the reported metric implies better performance. For power iteration, higher implies better performance, as we need to find the eigenvector corresponding to the top eigenvalue. For logistic regression, higher test accuracy implies better performance.
We provide the code in the supplementary material and all the experiments took days to run on a single 20 core machine with 25 GB RAM.
E Distributed Gradient Descent with SparseReg Compressor
This section uses our i compressor, SparseReg, for running FedAvg. Each client i E [m] contains a local objective function fi : W + R. We define the global objective function f(w) Em f((w), Vw E W C Rd. The goal to find w* E arg min ((w). Note that Vs(w) = # Σ V((w), therefore, our case, the vector gi correspond to fiw).. We describe the algorithm in Algorithm
Algorithm Distributed Projected Gradient Descent with SparseReg compressor
Require: Initial iterate w E W, Step size >>
Server
SparseReg-Ints (nit() for 1= to - do
Send w² to all clients i E [m]. Receive 6,' from clients E [m]. g' f- Rearse ( ((6/)e
w+ + projw n(g')
end for
Client (i) at iteration f Receive w from server. b, + SparseReg-Enneeeeeeeeee (((')) Send B to server.
We first state the assumptions required for applying the SparseReg compressor. Assumption 4 (Bounded Gradient). For all W, i [m), we assume that [[V)(()) < B.
25

---

Published in Transactions on Machine Learning Research (10/2025)
By this assumption, we ensure that for each iteration in Algorithm 6 |1 = Further, bounded gradients imply that each Ji is Lipschitz. By triangle inequality, we can also establish the following corollary.
f/ is bounded.
Corollary 1. The objective function (ww) is B-Lipschilz, Ve E W.
From the above assumptions, it clear that local objective functions need to be Lipschitz. From [Bubock 2015 Theorem 3.2), if the domain of ilerates, W bounded and f(w)) is also convex, then gradient descent can couverge at a rate O(IvVT). We use these two assumptions, and establish a ((/vVT) rate along with a error obtained from Theorem 3 We define rrgg(t) and 22. (t) from Theorem 3 to be the corresponding errors for 9: V fww"), Vi [m] for any t 0.
Assumption 5 (Bounded domain). The set W is closed and convex with diameter R², Asummptio 6 (Convexity). The objective function (w) is convex Vw E W.
We now state our convergence result. Theorem 6. Under Assumptions
4
5
6
running Algorithm 0 for T iterations with step size t BVT' -
R
with probability 1 2m LTT expeeepppoop
we have, d5d/1////0 m.
1,262
log L.
R(2B² +11)
1 T T
B[f(w")] - f(ww)(
VTIR,
where,
w
2B
1i = B² 1+ 10 L
m mlog L (81 + +do))
(1 (1-
2 log L
m
(13)
exp
d
d
12
max 15(0.1.....TT1
ming (maxx
From the above theorem, we can see that the high probability terms and F1 and P2 are obtained from Theorem 3 Note that I' = O exp(-m/d), therefore, for large m, the additional bias term of RvTi is very small. Further, the tcrm I2 B², therefore, I2 only affects constant terms in the convergence rate 2od 7), the final convergence rate of Algorithm 6 is (RB/vVT) which is the rate for distributed GD without compression.
due to vT in the denominator. If exp(-m/d) = (L/VTT)
We provide the proof for the above theorem, which modifies the proof of (Bubeck] 2015 Theorem 3.2) to handle a biased gradient oracle. We can also extend our analysis to other function classes, for instance strongly convex functions, by using existing works on biased gradient oracles (Ajallocian & Stich 2020 Extending the proof to FedAvg from distributed GD would require using biased gradient oracles in (Li et al. 2020). Further, these proofs can also be extended to Hadamardlultiiin compressor, with an additional vd factor in the corresponding error terms from Theorem 2 to account for conversion from loo to Eg norm.
E.1 Proof of Theorem 6
At any iteration t > 0, we use g' to denote the estimate of ff(w"). From the proof of Theorem [|=,[0'] (l("))l S vT, and Var,(g')w") < T2 Vt. > O, where E, and Var, are the expectation and variance wrt the randomness in the SparseReg compressor itcration We take union bound over the high probability terms in Theorem over all iterations 1 = to -
We can write the following equation by convexity of f(w*).
f(w') - f(w)) S(V s(V((w"), w² - -w*) = (0',, w² - )*) + (V](w') - g" w² - -w*)
(11w0- w0113 - -1|w²* ng" w0 w11 nll 113/111122211/ 2 + (Vf(w²) - -g', w² w²)
S 2m
26

---

Published in Transactions on Machine Learning Research (10/2025)
In the second line, use 2(a, b) ||ll2 + ||6| ||a blß. Now, taking expectation wrt the randomness in SparseReg at iteration i, obtain,
1 (1lw² w0 E.[/w' ng" w w01l))) 1 l|| 12//
B.[f(w']] - f(w")
2m
+ (V (wc") Eelo"), w² =w-)
1
(1/w² -w"12 1.1l ++1 w" (121) + B - Var, (02))/2
21)
+ || f E 11/0 w0112
1 (1lw² w" w²
w"
(121 nB2 + +22)/2 VIR
21
In the second line, I|proiw - ng" - w2)l,,, the decomposition of 2nd moment into square of mean and variance, and cauchy- schwartz inequality. In the third line, we plug in bounds of T1, 22 diameter of the set and by triangle inequality, argue that E[ğ')] also lies in an & ball of radius B.
the non-expannsiveness of projections
convex set, I|w² ng¹ w"ll2 2
Finally, we take expectations wrt all random variables, unroll the recursion from = 0 to T, and divide both sides by
R² 2n/T
nTB +12)
R(2B² +11).
Σ [[S(w")]] - f(w)))
RRs
2BVT + VTR
We obtain the final inequality by plugging in the step size n we obtain,
R B/T
By convexity of J, for w" --i-0 w²,
T-1
R(2B² +T1)
B]f(w")] f(w)) -
Σ
2BvT + VTR
T
27


Reviews:
[{"review_id": "pN26huxeHT", "reviewer": "Reviewer_utZ3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n* Novelty: The paper proposes new collaborative compressors (NoisySign, HadamardMultiDim, SparseReg, OneBit) that are simple, computationally efficient, and effective under limited communication budgets.\n\n\n* Diverse Error Metrics: Unlike most prior works that focus solely on $\\ell_2$ error, this work provides guarantees for $\\ell_{\\infty}$ and cosine error, expanding the applicability of the techniques.\n\n\n* Theoretical Guarantees: Error bounds are rigorously derived and expressed in terms of natural dissimilarity metrics. Two schemes obtain optimal dependence on  number of clients $m$.\n\n\n* No Prior Correlation Assumptions: Unlike existing collaborative schemes, the proposed methods do not require prior knowledge of client similarity, making them more practical in real-world scenarios.\n\n### Weaknesses\n\n* Limited Discussion of Technical Novelty: While the proposed compressors achieve strong theoretical guarantees, several techniques (e.g., sparse regression coding, one-bit compressed sensing) are based on well-established ideas. It would strengthen the paper to more clearly articulate the novel aspects of each method.\n\n\n* Assumptions on Low Dissimilarity: The effectiveness of the proposed methods relies on the assumption that client vectors are sufficiently similar. It would be better to provide a detailed discussion on the practical reasonableness of this assumption. Furthermore, it would be valuable to include more empirical or theoretical analysis of how the compressors behave under high dissimilarity.\n\n\n* Optimality Claims: In Section 3, the authors claim that their methods achieve optimal dependence on the number of clients $m$. Is there any references or lower bounds that can support this claim?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes four novel collaborative compression schemes for distributed mean estimation (DME). Unlike independent compression methods, these schemes exploit inter-client similarity without requiring explicit correlation knowledge. The proposed methods are measured by different estimation error metric—$\\ell_2$, $\\ell_{\\infty}$, and cosine distance—and includes theoretical error bounds that degrade gracefully with the degree of dissimilarity between clients. The authors support their theoretical claims with extensive experiments across various tasks including KMeans, power iteration, and linear/logistic regression.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Suggestions for Improvement\n\n* Clarity and Organization: The paper is difficult to follow on a first read due to organizational issues. Key algorithm descriptions are introduced in the Introduction section with minimal explanation, forcing the reader to backtrack when the algorithms are formally presented later. A clearer structure with all technical content reserved for the main body would improve readability.\n\n\n* Equation Placement: Equation (6) is introduced abruptly in Section 3.1 without explanation, even though it is used in Algorithm 4 (Section 3.2). It would be better to either move or defer this equation until its relevant context is established.\n\n\n* Writing Details: Several small writing issues should be addressed. For example, there is an unnecessary period following “Theorem 2.” Careful proofreading would help polish the presentation.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "dHROilKrcE", "reviewer": "Reviewer_AeEf", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper merits rejection in my view.\n\nIt has several deep flaws that outweigh the scope of work that is typical in revisions. While it is well written and the story of the paper is clear, these scientific issue are too big to overlook.\n\nMost centrally, I find the theory in this paper very unsatisfactory and essentially incomplete. Some parts of the theoretical results are even seemingly meaningless or misleading as stated. The empirical results are not strong enough to convince me that the paper's algorithms are super strong despite the existing issues in the theory.\n\nI will now elaborate.\n\n---\n\n### Issue 1: Vacuous / Mal-posed Error Bounds\n\nLet us examine Theorem 3 on page 8. This theorem provides an upper bound on the error of the $\\texttt{SparseReg}$ algorithm.\nThis upper bound depends on the minimum of the terms $\\Delta_{\\rm reg}$ and $\\Delta_{2,\\max}$. The latter term, $\\Delta_{2, \\max}$ is only small when every single clients' vector $\\vec g_i$ is close to the average vector $\\vec g$, which is a really strong assumption. By triangle inequality, it requires that literally all clients' vectors are within $2\\Delta_{2,\\max}$ of each-other in $\\ell_2$ norm.\n\nSo, set this aside and focus on the other term, $\\Delta_{\\rm reg}$.\nAt a glance, this term might seem better as it is a mere average of terms, which might be much better behaved than $\\Delta_{2,\\max}$.\nHowever, the definition of $\\Delta_{\\rm reg}$ depend on the matrix $A$, which is a _random Gaussian matrix_.\nSo, it's not clear how large the norms are, nor how they're scaled, nor if this algorithm is scale-invariant in $A$.\n\nI find it pretty un-interpretable to give an error bound that depends on the values of a random Gaussian matrix without giving a useful high probability or expectation bound on this term.\nThey do offer equation (7) to help here, but this is a **lower bound** on $\\Delta_{\\rm reg}$, which is clearly useful in any way.\nIt's a lower bound on the upper bound of the error.\n\nI have a similar concern about Theorem 2 on page 7, which has a term $\\Delta_{\\rm Hadamard}$ which depends on variable $b_{i,j}^{(r)}$ which _might_ be random variables. This isn't clear from context.\n\n> (_Extended note on this point for the authors._) At a cursory read of the paper, I cannot tell which of the following two definitions accurately describes $b_{i,j}^{(r)}$:\n> Is it:\n> 1. $b_{i,j}^{(r)} = (-1)^{g_{i,k}^{(r)}}$ where g_{i,k}^{(r)} is the $k^{th}$ bit in the binary representation of the number $g_{i}^{(r)}$, or is\n> 2. $b\\_{i,j}^{(r)} = (-1)^{g\\_{i,k}^{(r)}} \\mathbf{1}\\_{[\\rho [i] = k]}$ where $\\mathbf{1}\\_{[\\rho [i] = k]}$ indicates the use of the random permutation $\\rho$ used in $\\texttt{HadamardMultiDim}$ (see Algorithm 3 on page 5)\n> \n> Crucially, it's unclear to me if this loss metric is or isn't a random variable.\n> If it is a random variable (case 2 above), then there exists a pretty trivial expectation analysis that lets us exactly compute $\\mathbb E[\\Delta_{\\rm Hadamard}^2]$. I do not know why such an analysis is not presented.\n> If it is not a random variable (case 1 above), then we want an upper bound on $\\Delta_{\\rm Hadamard}$, but only a lower bound is given.\n\n---\n\n### Issue 2: Rates are not interpretable\n\nWe already saw this with Theorems 2 and 3, which failed to give error bounds in an easily interpretable form. But let's turn our attention to examine Theorem 1.\n\nTheorem 1 is suppose to estimate the vector $\\vec g$ to good additive error in the $\\ell_\\infty$ norm _without_ requiring any assumption that the norms $\\|\\| \\vec g_i \\|\\|\\_\\infty$ are bounded by some constant $B$.\n\nTheorem 1 purports to show that Algorithm 1 achieves such a guarantee. However, it depends implicitly on how similar or different the Gaussian error function is when applied to the entries of various $\\vec g_i$ vectors. This is subsumed in the $\\Delta_\\Phi$ variable. It also depends on the value of the gaussian error function evaluated at $$\\|\\|\\vec g\\|\\|_\\infty$.\n\nI take issue with the utility of this theorem statement in two directions.\nFirst, while they do not explicitly require a bound $B$ on $\\|\\|\\vec g\\|\\|_\\infty$, they do implicitly require it to make this upper bound non-vacuous, as the upper bound clearly does depend on this norm.\nSecond, the shown result is not interpretable.\nI have no clue at a glance how the input parameter $\\sigma$ changes the error bound or how many clients $m$ I need to make this error at most $\\varepsilon$. A big-Oh notation would go a long way here.\n_Even more broadly, it's not even clear at a glance that this error bound is scale invariant._\n\nDo some approximations and give me a usable big-Oh. The authors partially do this in the text below the theorem, but I do not understand how big I need to take $m$ to get this analysis to kick in and I don't really see at a glance how to think about the error function of $\\|\\|\\vec g\\|\\|_\\infty$.\n\n---\n\n### Issue 3: We should be able to make the error go to zero with increased communication.\n\nI should note that I'm not an expert in distributed algorithms at all. I just know randomized algorithms. But I would assume that algorithms should, with sufficient communication, be able to achieve an amount of error that gets arbitrarily close to zero.\n\nIt's not clear to me with algorithms in this paper have this property.\n\nThis is perhaps most clear in Theorem 1 again, where simplifying assumptions allow the authors to approximate the upper bound of the error in the limit as the number of clients $m \\rightarrow \\infty$ is roughly $\\text{Error} \\leq O(\\frac{\\sigma}{\\alpha(\\|\\|\\vec g\\|\\|_\\infty)}) \\frac1m \\sum_{i=1}^m \\|\\|\\vec g_i - \\vec g\\|\\|_\\infty$. This upper bound approaches a horizon of error as $m$ grows larger. It's not obvious a prior from what's written in the text that repetitions via (e.g.) Monte Carlo sampling would improve this.\n\nThe other results in this paper suffer from this same concern, which is unacknowledged in this paper. Though, it seems more likely at a glance that monte carlo estimation will suffice to make these methods converge to zero error.\n\n---\n\n### Milder Issue: Seeming error in the \"practical scenario\" analysis\n\nThe authors do make some efforts to make their results more interpretable. One place they do this is in Section 3.3 on page 8. They simplify the setting a bunch and estimate the value of some of the above error bounds, including $\\Delta_{\\rm Hadamard}$. As far as I can tell, they incorrectly compute $\\Delta_{\\rm Hadamard}$, where the very last line of page 8 shows them upper bounding a sum of terms with the maximum term. This seems to be a significant change in their bounds in the worst case (formally, when the first $k$ bits of $g_1'$ and $g_2'$ are different).\n\n--- \n\n### Milder Issue: Empirics are Lacking\n\nI'm treating this paper as principally theory, so I'm being gentler on the expectations from the empirical results. However, some parts of these results are insufficiently explained and analyzed.\n\nFirst off, the algorithm have only been run for 3 trials, and there are no error bars. For methods with as much randomness as these, I expect far more trials with some sorta error bars (say, 25th and 75th quantiles?).\n\nSecond, it is not clear why only some methods are presented between these experiments. I would expect that for all four downstream applications (KMean, Power Iteration via Lloyd's, Linear Regression, Logistic Regression), all 9ish methods for distributed mean estimation (4 from this paper 5 from the prior work) would be used. Instead, many of the downstream applications only use 4 or 5 of these methods. This absence seems to be carried by the phrase \"We ... report the methods which perform the best.\" which is strange and vague. What is the precise criteria used? Why are they omitted from the plots?\n\nThird, it is just sorta declared that some algorithms on some datasets have lower \"dissimilarity\" (second and third paragraphs on page 12). How was this computed? How small were the metrics?\n\nFourth, you don't seem to ever declare how many bits are communicated by the various algorithms presented. The appendix mentions that all methods communicate the exact same number of bits. How much is that?\n\n---\n\n### Conclusion\n\nI find the writing issues to be pretty intense in this paper.\n\nI don't know the rates achieved by the algorithm in any approachable way.\n\nAt least one of the upper bounds depends on a random quantity that's not bounded.\n\nThe empirics don't save the paper either.\n\nThe writing is nice, and there's very likely conceptual merit to the algorithms. The math is likely all correct. It's just not really usable in the form presented.\n\nMajor revisions are needed.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes four new methods for mean estimation in distributed computing. They focus on the client/server setting, where the $m$ clients each have a vector $\\vec g_i$, and where the server wants to compute the average vector $\\vec g = \\frac1m \\sum_{i=1}^m \\vec g_i$.\nThese methods assume (under a variety different mathematical formalisms) the setting where the various $\\vec g_i$ vectors are similar, which therefore leads one to hope that few bits of communications are needed. This is the titular \"Collaborative Compressor\" setting.\n\nThese four different methods target different error metrics and technical assumptions: Do we recover $\\vec g$ in the $\\ell_\\infty$, $\\ell_2$, or cosine distance? Do we assume the clients' vectors $\\vec g_i$ are bounded uniformly?\n\nThese four estimators are given theoretical analysis and some empirical analysis too. They do not assume any generative distribution for the clients' vectors, and instead give guarantees in terms of the \"closeness\" of the clients' vectors.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Crucially:\n\nGive upper bound on the error in big-oh notation that lets me easily understand how many bits I need to communicate (or how many clients I need or whatever) in order to get a good guarantee. Don't bury hard-to-understand terms like $\\alpha$ in these, and instead make simplifying assumptions like $\\|\\|\\vec g\\|\\|_\\infty \\leq B$.\n\nClarify the definition of $\\tilde b_{i,j}^{(r)}$.\n\nRemove lower bounds of the upper bounds, both in the introduction (e.g. pargraphs at the bottom of page 3) and in the body of the text. If you can make them into upper bounds, go ahead and do that.\n\nReassure me that I instead made an error when reading Section 3.3, or correct it if I am correct.\n\nRerun your experiments and give me error bars.\n\nClarify how you determine how some experiments have high/low dissimilarity.\n\nClarify how you determine which methods to include in which plots.\n\nTheorem 4 and 5 should clarify the role of $\\delta$. What happens in the limit as $\\delta \\rightarrow 0$?\n\nMaybe:\n\nClarify the rates needed to get error at most $\\varepsilon$.\n\nI think there's an error in the definition of $S_k^-$ in Algorithm 2? The numerator and denominator don't seem to line up correctly?\n\nDiscuss why some of the distributed methods, especially for power iteration and linear regression, seem to produce pretty terrible results. Many of the power iteration methods get stuck suggesting an eigenvalue that's far-from-optimal. The synthetic linear regression seems to have highly variable performance, and it's non obvious if any method is doing a good job. Discuss this please.\n\nThe citations in this paper are missing parentheses. This makes reading much harder in some places.\n\nSuggested minor edits (you don't need to respond to these, and you can ignore anything in here without telling me)\n\n1. Extra comma after \"Note that\" near top of page 7.\n2. Extra period after Theorem 2\n3. [Page 8 near top] \"achieve rate-distortion function for a Gaussian\" feels like grammar is wrong\n4. [Page 8 near bottom] Missing a 2 in the approximation of $\\Delta_\\infty$\n5. [Page 8 near bottom] Say \"at levels $\\mathcal K \\subseteq [m]$\"\n6. [Page 9 near bottom] Justify why the server can a prior know the unit vectors in $\\mathbb R^d$ on each machine despite not being able to communicate the vectors $\\vec g_i$ from the machines effectively.\n7. [Page 9 last line] Replace $\\frac1m$ with a summation symbol.\n8. [Lemma 1 discussion] Clarify the relationship between $\\zeta$ and $\\cos(\\pi \\Delta_{\\rm corr})$. If we had a constant of 1 relating them, we'd want $\\cos(\\pi \\Delta_{\\rm corr}) \\geq \\cos(\\pi\\zeta) \\geq \\cos(\\frac\\pi2) = 0$, motivating equation 9. But I'm betting that's not a constant of 1, so I don't know how big we actually want $\\cos(\\pi \\Delta_{\\rm corr})$ to be.\n9. [Page 10 last paragraph] Remove comma after \"Note that\"\n10. All plots: Improve legibility -- make text much larger. Maybe remove the log-scale from figure(i)?\n11. [Page 12 discussion of fig2c] Idk about this -- RandKSpatialProj seems to do pretty darn good still.\n12. [Page 12 Linear Regression paragraph] Missing space after \"and\"", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "hf9WacEcSM", "reviewer": "Reviewer_mSMu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nThe paper considers distributed mean estimation under three distinct error metrics and provides a different compression techniques that can be applied to a wide range of distributed learning problems under different error metrics. Each proposed method is well-motivated, computationally efficient, and suitable for practical deployment.\nThe paper provides rigorous theoretical guarantees for the proposed schemes, including how estimation error scales with inter-client similarity, number of clients, and the dimension of vectors. This analysis is more comprehensive than prior work, which often focuses only on $\\ell_2$ error, or assumes known correlations or bounded vectors.\n\n**Weaknesses**\n\nThere might be multiple technical errors and ambiguities in the paper that need to be addressed.\n- Some equations contain errors or inconsistencies that may mislead readers or hinder reproducibility.\n- Certain algorithm descriptions are either incorrect or incomplete.\n- There are ambiguous statements that need to be clarified.\nPlease see the next section for details.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers the problem of communication-efficient distributed mean estimation (DME) which is an essential component in many distributed optimization or training methods. The authors focus on collaborative compression schemes, where encoding at each client may be independent or coordinated, but decoding at the server is performed jointly to exploit the similarities between vectors at the clients.\n\n**Compression Algorithms:**\n\nThe authors proposed multiple compression schemes for different metrics:\n- $\\ell_{\\infty}$ norm metric:\n  - NoisySign: Adds independent Gaussian noise to each vector component and transmits only the sign. Hence, for a d-dimensional vector it requires only d bits for data transmission.\n   - HadamardMultiDim: A variant of nested 1-bit quantization for the 1D signals, applied to each elements of the vectors at each client.\n- $\\ell_2$ metric:\n  - SparseReg: A scheme based on sparse regression codes (by Venkataramanan et al., 2014), tailored for the DME problem.\n- Cosine similarity:\n  - OneBit: Sends the sign of the inner product between the data vector and a shared random Gaussian vector, preserving directional information.\n\n**Theoretical Analysis:**\n\nThe paper provides rigorous analysis of the proposed schemes, characterizing how estimation error (in terms of $\\ell_2$, $\\ell_\\{infty}$ or cosine similarity) varies based on the dissimilarity among client vectors, number of clients, and dimension of the vectors.\n\n**Empirical Evaluation:**\n\nThe authors conduct experiments on four DME tasks: K-Means clustering, power iteration, linear regression, and logistic regression.\nThese tasks are evaluated on MNIST, FEMNIST, UJIndoorLoc, and HAR datasets.\nResults show that the proposed methods outperform or closely match the other considered compression schemes when the dissimilarity among clients' data is low. However, as expected, performance degrades on highly heterogeneous datasets like FEMNIST, highlighting the limitations of correlation-agnostic approaches in such settings.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. *Clarify the Definition of Collaborative Compression*: The distinction between collaborative and independent compression is not clearly established. As defined in Figure 1, the proposed algorithms, except NoisySign, can be interpreted as independent compression schemes, since the final aggregation is simply an average over decoded values of the clients' outputs.\n\n2. *Relevance of Federated Learning*: Since collaborative compression relies on the clients' similarity, including federated learning scenarios, where client data is often highly heterogeneous, may not be appropriate. The observed failure of the proposed methods in such settings is expected and does not provide new insight.\n\n3. *NoisySign Algorithm*:\n   1) It would be valuable to analyze how the estimation error behaves as the noise parameter $\\sigma$ becomes large ($\\sigma\\rightarrow\\infty$ in Theorem 1).\n   2) In the proof of Theorem 1 (Appendix), Using Hoeffding's inequality for the bounded and *independent* random variables $|\\tilde{b}_i^{(j)}|\\=1$ results in the exponent $mt^2/2$. However, there is an extra term in the equation. Please clarify this.\n   3) Equation (10) should be justified as a result of the bounded variation of a differentiable function over a closed interval, or as the approximation error of a degree-0 Taylor expansion.\n   4) The sentence following Equation (3) states that the error function is bounded by 1.  However,  since $-1\\leq \\Phi_{\\sigma}(.)\\leq 1$, it implies that $\\Delta_{\\Phi} \\leq 2$.\n\n4. *HadamardMultiDim Algorithm*:\nThis method resembles nested quantization in 1D case. It would be valuable if the authors discuss some prior works on (dithered) nested quantization for correlated sources (both in communication theory and distributed training). However, as far as I know, the majority of work consider the $\\ell_2$ metric and did not consider $\\ell_{\\infty}$ norm in their analysis.\n - In Algorithm 3, the role of the permutation is unclear. The restriction that the number of quantization levels equals the number of clients seems unnecessary and limits flexibility. In standard nested quantization, clients can use different resolutions.\n\n5. *SparseReg*: Proof of Theorem 3 in the appendix, the value for R is not consistent with the reference paper. The correct value seems to be $R = m \\log(L) / d$.\n\n6. *OneBit Algorithm*: One general question regarding theorem 5: Since the cosine function is periodic, for large values of $\\Delta_{corr}$ or $d$, the cosine similarity between the original and recovered vectors might increase unexpectedly. How the constraint $\\zeta<1/2$ prevents this from happening?\n\n7. *Experimental Evaluation*:\n    1) The simulations are relatively basic and may not reflect realistic distributed computation scenarios. More complex or large-scale experiments would strengthen the empirical validation.\n    2) The labels and legends of the plots are too small and hard to read, especially in print.\n    3) In performance evaluation of the Power Iteration (Figures 2e and 2h), there is no indication of the metric and how the plots should be interpreted. Is the convergence speed to 5 or 1.2 is the indicator of performance? Further, what should the algorithm converge to, i.e., what is the actual largest eigenvalue?", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)