Correlation Aware Sparsified Mean Estimation Using Random Projection
Authors: Shuli Jiang
Pranay Sharma
Gauri Joshi
Venue: NeurIPS 2023 poster (2023)
Keywords: distributed vector mean estimation
communication efficiency
cross-client correlation
TL;DR: Communication efficient sparsification based distributed vector mean estimation leveraging cross-client correlation information through random projection.

Abstract: We study the problem of communication-efficient distributed vector mean estimation, which is a commonly used subroutine in distributed optimization and Federated Learning (FL). Rand-$k$ sparsification is a commonly used technique to reduce communication cost, where each client sends $k < d$ of its coordinates to the server. However, Rand-$k$ is agnostic to any correlations, that might exist between clients in practical scenarios. The recently proposed Rand-$k$-Spatial estimator leverages the cross-client correlation information at the server to improve Rand-$k$'s performance. Yet, the performance of Rand-$k$-Spatial is suboptimal, and improving mean estimation is key to a faster convergence in distributed optimization. We propose the Rand-Proj-Spatial estimator with a more flexible encoding-decoding procedure, which generalizes the encoding of Rand-$k$ by projecting the client vectors to a random $k$-dimensional subspace. We utilize Subsampled Randomized Hadamard Transform (SRHT) as the projection matrix, and show that Rand-Proj-Spatial with SRHT outperforms Rand-$k$-Spatial, using the correlation information more efficiently. Furthermore, we propose an approach to incorporate varying degrees of correlation, and suggest a practical variant of Rand-Proj-Spatial when the correlation information is not available to the server. Finally, experiments on real-world distributed optimization tasks showcase the superior performance of Rand-Proj-Spatial compared to Rand-$k$-Spatial and other more sophisticated sparsification techniques.

Correlation Aware Sparsified Mean Estimation Using Random Projection
Shuli Jiang Robotics Institute
Pranay Sharma ECE Carnegie Mellon University pranaysh@andrev cmu edu
Gauri Joshi ECE
Carnegie Mellon University shulij jalidje@nddw.... cmu. edu
Carnegie Mellon University gauri jardrie@nneew.. cmu. edu
Abstract
We study the problem of communication-effiiieee distributed vector mean esti- mation, a commonly used subroutine distributed optimization and Federated Learning (FL). Rand-k sparsification is commonly used technique to reduce communication cost, where each client sends & < d of its coordinates to the server. However, Rand-k is agnostic any correlations, that might exist between clients in practical scenarios. The recently proposed Rand-k-Spatial estimator leverages the cross-client correlation information at the server to improve Rand-k's perfor- mance. Yet, the performance of Rand-k-Spatial is suboptimal. We propose the Rand-Proj-Spatiall estimator with more flexible encoding-decoding procedure, which generalizes the encoding of Rand-k by projecting the client vectors to a random k-dimensional subspace. We utilize Subsampled Randomized Hadamard Transform (SRHT) as the projection matrix and show that Rand- Proj-Spatial with SRHT outperforms Rand-k SSSatiill, using the correlation information more ef- ficiently. Furthermore, we propose an approach to incorporate varying degrees of correlation and suggest practical variant of Rand-Proj-Syy Proj-Spatial when the cor- relation information is not available to the server. Experiments on real-world distributed optimization tasks showcase the superior performance Kand-Proj- Spatial compared to Rand-k-Spatial and other more sophisticated sparsification techniques.
Introduction
In modern machine learning applications, data is naturally distributed across a large number of edge devices or clients. The underlying learning task in such settings is modeled by distributed optimization or the recent paradigm of Federated Learning (FL) 2 4 A crucial subtask in distributed learning is for the server to compute the mean of the vectors sent by the clients. In FL., for example, clients run training steps on their local data and once-in-a-while send their local models (or local gradients) to the server, which averages them to compute the new global model. However, with the ever-increasing size machine learning models [5 6), and the limited battery life of the edge clients, communication cost is often the major constraint for the clients. This motivates the problem of (empirical) distributed mean estimation (DME) under communication constraints, as illustrated in Figure Each of the clients holds vector X; Rd on which there assumptions. Given a communication budget, each client sends a compressed version & of its vector to the server, which utilizes these to compute estimate of the mean vector Σ X.
distributional
Quantization and sparsification are two major techniques for reducing the communication costs of DME. Quantization 7
9 10 involves compressing each coordinate of the client vector to a given precision and aims to reduce the number of bits to represent each coordinate, achieving constant reduction in the communication cost. However, the communication cost still remains O(d).
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Sparsification, on the other hand, aims to reduce the number of coordinates each clinet sends and compresses each client vector only < d of its coordinates (e.g. Rand-k (T]). As a result, sparsification reduces communication costs more aggressively compared to quantization, achieving better communication efficiency at a cost of only O(k). While in practice, one can use a combination of quantization and sparsification techniques for communication cost reduction, in this work, we focus on the more aggressive sparsification techniques. We call k, the dimension of the vector each client sends to the server, the per-client communication budget.
Most existing works on sparsification ignore the potential correlation (or similarity) among the client vectors, which often exists in practice. For ex- ample, the data of specific client in federated learning can be similar to that of multiple clients. Hence, is reasonable to expect their models (or gradients) to be similar as well. To the best of our knowledge, [12 is the first work to account for spatial correlation across individual client vectors. They propose the Rand-k k- --Spatial family of unbiased estimators, which general- izes Rand-k and achieves a better esti- mation error in the presence of cross- client correlation. However, their ap- proach is focused only on the server-side decoding procedure, while the clients do simple Rand-k encoding.
Client 1
Client 2
Client I2
E R
X2 E R
X₂ IR
Encoder
Encoder
Encoder & R
&, R
X2 E R
81
82
8.
Server
Decodo(&, &2. 8nn))
Figure 1: The problem of distributed mean estimation under limited communication. Each client E [n] encodes its vector
X; and sends this compressed version to the server. The server decodes them to compute an estimate of the true mean 1.4 E X;.
In this work, we consider more general encoding scheme that directly compresses vector from Id to R using a (random) linear map. The encoded vector consists of & linear combinations of the original coordinates. Intuitively, this has higher chance of capturing the large-magittde coordinates ("heavy hitters"") of the vector than randomly sampling & out of the coordinates (Rand-k), which is crucial for the estimator recover the true mean vector. For example, consider a vector where only few coordinates are heavy hitters. For small k; Rand-k has a decent chance of missing all the heavy hitters. But with finear-maps-basee mases general encoding procedure, the large coordinates are more likely to be encoded in the linear measurements, resulting in a more accurate estimator of the mean vector. Guided by this intuition, we ask:
Can we design an improved joint encoding decoding scheme that utilizes the correlation information and achieves an improved estimation error?
encodingddeooding
One naïve solution to apply the same random rotation matrix G E B each client vector, before applying Rand-k or Rand-k-Spatii encoding. Indeed, such preprocessing is applied to improve the estimator using quantization techniques on heterogeneous vectors [I3 [0] However, as we see in Appendix I. for sparsification, we can show that this leads to no improvement. But what happens every client uses a different random matrix, or applies random d-dimensional linear map? How to design the corresponding decoding procedure to leverage cross-client correlation? As there is no way for one to directly apply the decoding procedure of Rand-k S-Satial in such cases. To answer these guestions, procedure in which each client applies its own random linear map to encode the vector. Further, our novel decoding procedure can better leverage cross-client correlation. The resulting mean estimator generalizes and improves over the Rand-k-Spatial family estimator.
propose the Rand-Pro Peipe-roo--ppsse SpattiS family estimator. We propose flexible encoding
Next, we discuss some reasonable restrictions we expect our mean estimator to obey. 1) Unbiased. An unbiased mean estimator theoretically more convenient compared to a biased one [14] 2) Non-adaptive. We focus on an encoding procedure that does not depend on the actual client data, as opposed to the adaptive ones, e.g. Rand-k with vector-based sampling probability [T [5].
Designing data-adaptive encoding procedure is computationally expensive this might require using an itcrative procedure to find out the sampling probabilities [IT]. J. In practice, however, clients often have limited computational power compared to the server. Further, as discussed earlier, mean estimation is often a subroutine in more complicated tasks. For applications with streaming data [16]

---

the additional computational overhead of adaptive schemes is challenging to maintain. Note that both Rand-k and Rand-k-S k-Spttial family estimator [2] are unbiased and non-adaptive.
In this paper, we focus on the severely receives very limited information about any single client vector. If nk > d, see in Appendix [A.2 that the cross-client information has no additional advantage in terms of improving the mean estimate under both Rand-k-Spatial Furthermore, when nk >> d, the performance of both the estimators converges to that of Rand-k. Intuitively, this means when the server receives sufficient information regarding the client vectors, does not need to leverage cross-client correlation to improve the mean estimator.
case nk I d, when the server
Sand-Proj-Spatiee
with different choices of random linear maps.
Our contributions can be summarized as follows:
1. We propose the Rand-Proj-Spatiall family estimator with more flexible encoding-decoding procedure, which can better leverage the cross-client correlation information to achieve a more general and improved mean estimator compared to existing ones.
2. We show the benefit of using Subsampled Randomized Hadamard Transform (SRHT) as the ran- dom linear maps in Hund-Proj-Spatice in terms of better mean estimation error (MSE). We theoret- ically analyze the case when the correlation information is known at the server (see Theorems 4.3 4.4 Section 4.3). Further, propose practical configuration called Rand Srond-Pr--ppatil(AAA when the correlation is unknown.
3. We conduct experiments on common distributed optimization tasks, and demonstrate the superior performance of Hand-Proj-Spatiie compared to existing sparsification techniques.
2 Related Work
Quantization and Sparsification. Commonly used techniques to achieve communication efficiency are quantization, sparsification, or more generic compression schemes, which generalize the former two [17]. Quantization involves either representing each coordinate of the vector by small number 19 20), or more involved vector quantization techniques [21] (22). Sparsification on the other hand, involves communicating a small number k < d of coordinates, to the server. Common protocols include Rand-k I, sending & uniformly randomly selected coordinates; Top-k [27]. sending the & largest magnitude coordinates; and a combination of the two (28). Some recent works, with focus on distributed learning, further refine these communication- saving mechanisms
of bits 8 9 10 18
13 23 24
25|
26
29 by incorporating temporal correlation or error feedback 14 25
Distributed Mean Estimation (DME). DME has wide applications distributed optimization and FL. Most of the existing literature DME either considers statistical mean estimation [00 31] assuming that the data across clients is generated i.i.d. according to the same distribution, or empirical
34 35). without making any distributional assumptions on the data. A recent line of work on empirical DME considers applying additional information available to the server, to further improve the mean estimate. This side information includes cross-client correlation 12 13), or the memory of the past updates sent by the clients (36].
mean estimation 10 32
33 22
Subsampled Randomized Hadamard Transformation (SRHT). SRHT was introduced for random dimensionality reduction using sketching 37 38 39). Common applications of SRHT include faster
computation of matrix problems, such as low-rank approximation 40 41 and machine learning
tasks, such as ridge regression [42], and least square problems 43
45
SRHT has also been
applied to improve communication efficiency in distributed optimization
46 and FL 47 48
3 Preliminaries
Notation. We use bold lowerease (uppercase) letters, c.g. x (G) to denote vectors (matrices). ej Rd, for j e [d], denotes the j-th canonical basis vector. Il-1|2 denotes the Euclidean norm. For vector x, x(j) denotes its j-th coordinate. Given integer m, we denote by [m] the set 21,2,.... m).
Problem Setup. Consider geographically separated clients coordinated by central server. Each client i E [n] holds a vector x; E Rd. while the server wants to estimate the mean vector A 1
n. Σリ X;. Given a per-client communication budget of E [d], each client computes &; and sends to the central server. X; is an approximation of x; that belongs random k-dimensional
3

---

subspace. Each client also sends random seed to the server. which conveys the subspace information, and can usually be communicated using negligible amount of bits. Having received the encoded vectors { i=1 the server then computes x E IRd an estimator of x. We consider the severely communication-constaaiiin
setting where nk: Σ d, when only limited amount of information about the client vectors is seen by the server.
Error Metric. We measure the quality of the decoded vector X using the Mean Squared Error (MSE) E || - x _ where the expectation is with respect to all the randomness in the encoding-decoding scheme. Our goal to design an E| x) that minimizes the MSE, given the per-client communication budget k. To consider an example, in rand-k sparsification, each client sends randomly selected out of its coordinates to
algorithm to achieve an unbiased estimate x (i.e.
the server. The server then computes the mean estimate x (Rand-k) 1]. the MSE of Rand-k sparsification is given by
-1 E & By [12 Lemma
n
E Rand-k)
x|2]
1 n²
n
x5
The Rand-k-Spatial Family Estimator. For large values of & the Rand-k MSE in Eq. can be prohibitive. [12] proposed the Rand-k-Spatial family estimator, which achieves improved MSE, by leveraging the knowledge of the correlation between client vectors at the server. The encoded vectors } are the same in Rand-k. However, the j-th coordinate of the decoded vector given as
(Rand le Spatial) (
(j) n2 T(M)
Ex, 1=1
Here, T: R R is pre-defined transformation function of Mj. the number of clients which sent their j-th coordinate, and 3 is a normalization constant to ensure is an unbiased estimator of x. The resulting MSE is given by
E
X [Rand [Rand-k-Spaai Spattill)
X
+
C1
x
12
Xi, xi)
(3)
k
1
where C C2 are constants dependent
d, A and T, but independent of client vectors {x:)
When the client vectors are orthogonal, i.e., (x,, xi) O, for all i * 1, [12 show that with appropriately chosen T, the MSE in Eq. 3 reduces to Eq. [ However, if there exists positive correlation between the vectors, the MSE in Eq. 3 is strictly smaller than that for Rand-k Eq.
The Rand-Proj-Spatiall Family Estimator
While the Rand-k-Spatic family estimator proposed in (12) focuses only improving the decoding the server, we consider a more general encoding-decodiig scheme. Rather than simply communicating k out of the d coordinates of its vector x; the server, client i applies a (random) linear map G; E Rxd to x; and sends X; = G E R to the server. The decoding process on the server first projects the encoded vectors } back the d-dimensional space and then forms estimate x. We motivate our new decoding procedure with the following regression problem:
x (Rand-Proj) arg min Σ
||,x - G,
To understand the motivation behind Eq. first consider the special case where G, La for all i E [n], that is, the clients communicate their vectors without compressing. The server can then exactly compute the mean x x Σ x,. Equivalently, X is the solution of arg min Σn ||x In the more general setting, we require that the mean estimate & when encoded using the map G., should be "close" to the encoded vector G.x; originally sent by client i, for all clients E [r).
2-
We note the above intuition can also be translated into different regression problems motivate the design of the new decoding procedure. We discuss in Appendix B.2 intuitive alternatives which,

---

unfortunately, either do not enable the usage of cross-client correlation information, or do not use such information effectively. We choose the formulation in Eq. due to its analytical tractability and its direct relevance to our target error metric MSF. We note that it is possible to consider the problem in Eq. in the other norms, such as the sum of lg norms (without the squares) or the foc norm. We leave this as future direction to explore.
The solution to Eq. is given by X (Rand-Pri) = -E G. GL_G,,,,,, where denotes the
Moore-Penrose pseudo inverse [49]. However, while (Rand Proj) minimizes the eπror of the regression problem, our goal to design an unbiased estimator that also improves the MSE. Therefore, we make the following modifications to (Randd-Pro)); First, to ensure that the mean estimate is unbiased, scale the solution by a normalization factor - Second, to incorporate varying degrees of correlation among the clients, we propose apply a scalar transformation function T R - IR to each of the eigenvalues of -i=1 G G. The resulting Rand-Proj-Spane
family estimator is given by
(Ramd Proj Sputial)
3 =T(T()
T(
G. G.) G.G.)
Σ G.
(5)
Though applying the transformation function T in Projdd-Pj--ppaalll requires computing the eigen- decomposition of Σi=1 G. G;. However, this happens only at the server, which has more com- putational power than the clients. Next, we observe that for appropriate choice of (Gi) the Hond-Proj-Spatiie family estimator reduces to the Rand-k-Spatial family estimator [12].
Lemma 4.1 (Recovering Rand-N-Spatial), Suppose client generates a subsampling matrix E, [oi,: ej,]", where {= are the canonical basis vectors, and {ir...., ig] are sampled from {1..... d} without replacement. The encoded vectors are given as X; = E,x, Given a function T, & computed as in Eq. recovers the Rand-k Sonddk-Sppnn Spattial estimator.
The proof details are in Appendix Land-k-Spatiaa in detail in Section
We discuss the choice of T and how it compares to
Remark 4.2. In the simple case when G 's are subsampling matrices (as in Land-a-Spatial (12)) the j-th diagonal entry of G. M, conveys the number of clients which sent the j-th coordinate. Rand-k-Spatial incorporates correlation among client vectors by applying a function T to Mj. Intuitively, it means scaling different coordinates differently. This is in contrast to Rand-K which scales all the coordinates by d/k, In our more general case, apply a function T to the eigenvalues of Ei= G.¹ G; to similarly incorporate correlation in Rand- Rand-Proj-SS Proj-Spatial
To showcase the utility of the Rand-Proj-Spee maps G. to be scaled Subsampled Randomized Hadamard Transform (SRHT, e.g. (38). Assuming d to be a power of 2, the linear map G, is given as
family estimator, we propose to set the random linear
G Vd E,H. E kxd
where E, E Igixd is the subsampling matrix, H E Rdddd is the (deterministic) Hadamard matrix and D, E gdxd is diagonal matrix with independent Rademacher random variables its diagonal entries. We choose SRHT due to its superior performance compared to other random matrices. Other possible choices of random matrices for Rand- Proj--rottiii estimator include sketching matrices commonly used for dimensionality reduction, such as Gaussian 51), row-normalized Gaussian, and Count Sketch [52] as well coror-correction coding matrices, such as Low-Densit Parity Check (LDPC) [53] and Fountain Codes [54]. However, in the absence of correlation between client vectors, all these matrices suffer higher MSE.
In the following, we first compare the MSE of Rand-Proj-SSe Proj-SSaaap with SRHT against Rand-k and Rand-k- in two extreme cases; when all the client vectors are identical, and when all the client vectors are orthogonal to each other. In both cases, we highlight the transformation function used in Sand-Proj-SSpe (Eq. 5) to incorporate the knowledge of cross-client correlation. We define
Σ/= E (x1, x1)
R
Σ | B
to measure the correlation between the client vectors. Note that R I-1,n 1). R 0 implies all client vectors are orthogonal, while R = n - implies identical client vectors.
We show that it suffices for 3 to be scalar in Appendix B.1
5

---

4.1 Case I: Identical Client Vectors (R = 1)
When all the client vectors are identical (x; x), I2 showed that setting the transformation T to identity, i.e., T(m) m, for all m, leads to the minimum MSE in the Rand-k-Spatial family of estimators. The resulting estimator is called Rand-k Rand-k-Spatte S-Satiial (Max). Under the same setting, using the same transformation T in Sand-Proj-Spatial with SRHT, the decoded vector in Eq. 5 simplifies to
@Rand (Keand-Proj--ae Sputial)
3 Σ G G.G.G. E Gx 3S Sx,
(8)
where S := -i= G. By construction, rank S nk, and we focus on the case nk S d. Limitation of Subsampling matrices. As mentioned above, with G, = E,, V E [n]. we recover the Rand-k-SSatial family of estimators. In this case, S is diagonal matrix, where each diagonal entry Sj M, E [d] Mj is the number of clients which sent their j-th coordinate to the server. To ensure (S) nk, we need Sj S 1, Vj. i.e., each of the d coordinates is sent by at most one client. If all the clients sample their matrices { {E, }= independently, this happens with probability (11).
As example, for k 1, Prob(rank(S))
n)
(because d" n S
d" a!
(2)".
Therefore, to guarantee that S is full-rank, each client would need the subsampling information of all the other clients. This not only requires additional communication but also has serious privacy implications. Essentially, the limitation with subsampling matrices E, is that the eigenvectors of S are restricted to be canonical basis vectors (e, 1d jー1 Generalizing G 's to general rank k matrices relaxes this constraint and hence we can ensure that S full-rank with high probability. In the next result, we show the benefit of choosing G; as SRHT matrices. We call the resulting estimator Rand- Sand-Proj-SSattiee (Moj-S)patia(MMxx).
Theorem 4.3 (MSE under Full Correlation). Consider n clients, each holding the same vector d E IRd. Suppose we set T()) = X, B E in Eq. S and the random linear map G; at each client to be an SRHT matrix. Let be the probability that S Ei G.T G; does not have full rank. Then, for nk S d.
d
IE ||se (Rand Proj- Sparial(Max))
(1 8yyk + 8k |
The proof details are in Appendix C.1 To compare the performance of Rand-Proj-Spaatia(MM) against Rand-k, we show in Appendix C.2 that for n 2 2, as long as 8 < 3. tte MSE of Sandd-Prj-Sppatia(MM)
is less than that of Rand-k. Furthermore, in Appendix C.3 we empirically demonstrate that with E {32, 64, 128, ..., 1024} and different values of nk S d, the rank of S is full with high probability, i.e., 8 Rv 0. This implies B[[] Soond-Pooj-SpaialMMaaa
x
d - 1) W
Futhermore, since setting G; as SRHT significantly increases the probability of recovering nk coordinates of x, the MSE of Sand-Proj-Spatial with SRHT (Eq. 4 is strictly less than that of Band-k-Spatial (Eq. 3. We also compare the MSEs of the three estimators in Figure i the following setting: ||x||2 1, 1024, n E {10, 20, 50, 100} and small k values such that nk d.
10. 1024
n - 20, d 1024
50, 1024
100, d 1024
Randik
Rand-k Rand-k-SpatfalMMac
Randik
Rand-k
Rand-kk-paatin Spatial[Max]
Rand-kk- Spatia(Max)]
Rand-k SpatialMMal
Randi Prod Spatial[Max
Rand-Froj Pand-Proo-SpattaMMMa
Randi Pnoj Spatial[Max)
Rand Proj Spataa(Maa
MSF
MSE
3
2
1
0
0-
100
10
20
30
40
k
k
Figure 2: MSE comparison of Rand-k, (Madaa)SpatiialMax)) and Soand-Proj-Spatiall estimators, when all clients have identical vectors (maximum inter-client correlation).
4.2 Case II: Orthogonal Client Vectors (R- 0)
When all the client vectors are orthogonal to each other, 12 showed that Rand-k has the lowest MSE among the Rand-k-Spatial family of decoders. We show in the next result that if we set the

---

random linear maps G; at client i to be SRHT, and choose the fixed transformation T = as in [2] Boudd-Prj-Sppatiiie achieves the same MSE as that of Rand-k.
Theorem 4.4 (MSE under No Correlation). Consider n clients, each holding a vector x, E TRd Vi E [n]. Suppose we set T = 3 = d in Eg. 5 and the random linear map G3 at each client to be an SRHT matrix. Then, for nkk S d.
K
d
E
& Rond Proj- Proj-Spatial)
(10)
The proof details are in Appendix C.4
Theorem 4.4 above shows that with zero correlation among client vectors, Rand-Proj- Proj-Spatial achieves the same MSE as that of Rand-k.
4.3 Incorporating Varying Degrees of Correlation
In practice, it unlikely that all the client vectors are either identical or orthogonal to each other. In general, there is some "imperfect" correlation among the client vectors, i.e., R E (0, n - 1). Given correlation level R. [12] shows that the estimator from the Rand-k-Spatial family that minimizes the MSE is given by the following transformation.
R
T(m) = 1
(m -
(1I)
Recall from Section 4.1 (Section 4.2 that setting T(m) 1 (T(m) -m) leads to the estimator among the Rand-k-Spatial family that minimizes MSE when there is zero (maximum) correlation among the client vectors. We observe the function T defined in Eq. essentially interpolates 1] as the S = Di=1 G.¹² G; in Lund-Proj-Spatilll As we shall see in our results, the resulting Rand- SaandPPoo--Sppe Proj-Spatial family estimator improves over the MSE of both Rand-k and Rand-k-Spatial family estimator.
n E - weight. This motivates us to apply the same function T defined in Eq. Ti on the eigenvalues
between the two extreme cases, using the normalized degree of correlation
π
We note that deriving closed- form expression of MSE for Cand-Proj-Spatiae with SRHT in the general case with the transformation function T (Eq. IT is hard (we elaborate on this in Appendix [.3),, as this requires a closed form expression for the non-asymptotic distributions of cigenvalues and eigenvectors of the random matrix S. To the best of our knowledge, previous analyses of SRHT, for example in 37 eigen spectrum, or concentration bounds on the singular values, to derive asymptotic or approximate guarantees. However, to analyze the MSE of Hoand-Proj-Spatieee we need exact, non-asymptotic analysis of the eigenvalues and eigenvectors distribution of SRHT. Given the apparent intractability of the theoretical analysis, we compare the MSE of Rand-Proj-Sppe via simulations.
55 , rely on the asymptotic properties of SRHT, such as the limiting
Rand-k-Spatial, and Rand-k
In each experiment, first simulate 3 in Eq. 5 which ensures estimator is unbiased, based on 1000 random runs. Given the degree of correlation R, we then compute the squared error, i.c. | (Randd-Pooj-Spatid) - x||2. where Rand Proj--Pra-ppailll has G; as SRHT matrix (Eq. 6) and T in Eq.
Simulations.
approximation to MSE. Each client holds a d-dimensional base vector ej for some j E [d], and so two clients either hold the same orthogonal vectors. We control the degree of correlation R by changing the number of clients which hold the same vector. We consider d = 1024, n E {21, 51}. We consider positive correlation values, where R is chosen to be lincarly spaced within [0. 1). Hence, for n 21, we use R E {4, 8, 12, 16} and for n = 51, we use R E {10, 20, 30, 403. All results are presented in Figure 3 As expected, given R. Rand-Proj-Spatial consistently achieves lower MSE than the lowest possible MSE from the Band-k-Spatte family decoder. Additional results with different values of n, d, k, including the setting nk < d, can be found in Appendix B.4
I1 We plot the average over 1000 random runs
Practical Configuration. In reality, it is hard to know the correlation information R among the client vectors. [2] uses the transformation function which interpolates to the middle point between the full correlation and no correlation cases, such that T(m) = 1 + 2 m-1 Rand-k-Spatial with such T called Rand-k-SS Sondd--SSptiaa(AAA (Avg). Following this approach, we evaluate SRHT using this T, and call it Proj--Satial(AA in practical settings (see Figure
R-
Siadd-Pro-Spptiiaa with
7

---

n=
k=
4.8
2.4
1.6
4.7
2.3
1.5
1.1
4.6
2.2
1.4
1.0
4.5
2.1
1.3
0.9
Rand-k
2.0
Rand-k
1.2
Rand-e
0.8
Rand-k
4.3
PanatPrajSpatiill
Randk-SpttalDpt
Rand-Pra-Spattal
Parns-Praj-Spataall
Spatal--pab
0.7
Rand-ProjSpaatal
SpatinlOpp)
4.2
4
8
12
16
8
12
16
8
12
16
12
16
51.
n
51, k
51,
51,
5.0
2.5
1.6
4.8
2.3
1.5
55
4.7
1.4
1.0
4.6
Rand-k
2.1
Rand-k
1.3
Rand-t
0.9
Rand-k
Rand-k-SpatialOOpe) Rand Proj Spatial
Randk-SpatiilDptt Rand Proj Spatial
1.2
Rand-e- Spatill--pa
0.8
Rand-k-SpatiietOnn Rand Spatiall
4.4
1.9
1.1
Rand Proj Spatial
0.7
10
20
30
40
10
20
30
40
10
20
30
40
10
20
30
40
R
R
R
Figure 3: MSE comparison of estimators Rand-k, k. Kand-k-Spatial(Opl) Rand-Proj-SS Proj-Spaall given the degrec of correlation R. Sanni--Spptial(Op)) denotes the estimator that gives the lowest possible MSE from the Rand-k-Spatial family. We consider k values such that nk < d. In each plot, we fix n. k d and vary the degree of positive correlation R. The y-axis represents MSE. Notice since each client has a fixed ||x;|| ||2 1, and Rand-k does not leverage cross-client correlation, the MSE of Rand-k in each plot remains the same for different R.
1024, number of clients n E {21, (1,5) }, and
5 Experiments
We consider three practical distributed optimization tasks for evaluation: distributed power iteration, distributed k-means and distributed linear regression. We compare Rand- Proj-Spatial(Av)) against Rand-k, Ad-SpaaiallAAgg and two more sophisticated but widely used sparsification schemes: non-uniform coordinate-wist gradient sparsification [15] (we call it Rand-k ((aagnii) and the Induced compressor with Rand-k + Top-k [14] The results are presented in Figure
Dataset. For both distributed power iteration and distributed k-means, we use the test set of the Fashion-MMIST dataset [56) consisting of 10000 samples. The original images from Fashion-MNIST are 28 x 28 in size. We preprocess and resize each image to be 32 x 32. Re- sizing images to have their dimension as a power of 2 is a common technigue used in computer vision to accelerate the convolution operation. We use the UJIndoor dataset for distributed linear regression. We subsample 10000 data points, and use the first 512 out the total 520 features on signals of phone calls. The task is predict the longitude of the location of phone call. In all the experiments in Figure [4] the datasets are split IID across the clients via random shuffling. In Appendix D.I. we have additional results for non-lID data split across the clients.
Setup and Metric. Recall that n denotes the number of clients, the per-client communication budget, and d the vector dimension. For Rand-Proj-Spatiin
we use the first 50 iterations to estimate (see Eq. 5). Note that 3 only depends on n, k, d, and (the transformation function in Eq. 5). but independent of the dataset. We repeat the experiments across 10 independent runs, and report the mean MSE (solid lines) and one standard deviation (shaded regions) for each estimator. For each task, we plot the squared error of the mean estimator &, i.e., || x1|2. and the values of the task-specific loss function, detailed below.
Tasks and Settings:
1. Distributed power iteration. We estimate the principle eigenvector of the covariance matrix, with the dataset Snashoon-MIISS distributed across the n clients. In each iteration, each client computes local principle eigenvector estimate based on single power iteration and sends encoded version to the server. The server then computes a global estimate and sends it back to the clients. The task-specific loss here is ll,, Vtopl12. where v, is the global estimate of the principal eigenvector at iteration t, and vzop is the true principle eigenvector.
https://archive..tee uci http://ccccc.c.ee///aaaaaaaaaaaa

---

2. Distributed k-means. We perform k-means clustering [57] with the data distributed across n clients (Fashion-MMIL) 10 classes) using Lloyd's algorithm. At each iteration, each client performs single iteration of k-means to find its local centroids and sends the encoded version to the server. The server then computes an estimate of the global centroids and sends them back to the clients. We report the average squared mean estimation error across 10 clusters, and the k-means loss, i.e., the sum of the squared distances of the data points to the centroids.
For both distributed power iterations and distributed k-means, we run the experiments for 30 iterations and consider two different settings: n = 10, 102 and n = 50,
20.
Distributed Power Iteration
n=10. 100 dd1024
n=10. k-102, d-1024
n=50. k=20, d-1024
n= k= 20, d-1024
Randik i
Randix
Randk
Randic
fand is a
handli (lrrg)
Rand k Aparial
0.5
hand (p2tilAAg))
Squargd Eiror
fand kttangrii
induceed Campinesor
fand enj Spat klvg)
5.R
Induced Comp
hand whanggit
Ro nd Spor allle))
Square Eng
2.0
Rund kiMa iiiil
Rand fros Sparia
Indrueed Compressar
0.6
kand iifange))
kand Fry SpatialAgg))
Irduced Comprssorr
0.7
0
10
20
30
10
20
30
10
20
19
20
30
Iteraiion No.
Iteration No.
Iteration No.
Rteraton No.
Distributed K Means
n- 20, k-102, d-1024
n=10 k- 102 d-1024
5-50 k-20, d-1024
n- 50, k-20, d-
Rand-4-- Spatt-l-Speteetggg
Rand-kk
1.
Sansk
Randic
Sandio Spar (lpp)
2.0
Fant de Stata
Fant-k
Squard Entur
200
Rand A/Wengril
kand kiWaagn
250
hand AoMarggn)
Rand Wengggg
Induced Compinssar
Iihooed Compressor
Incuced Car pe essor Rand Spoaisslg)
2.6
Induced Compresoor
Rand Pro Spatalloug)
4
kati Froi Spariskibgg)
200
Foins Phoy Spatis (Aug)
100
1150
110
10
2.0
Iteration
Distributed Linear Regression
20. K-50, d=512
1ek n-10, K-50,
d=512
le5
n=50
k-10,
d-512
Led
50, k=100, d-512
Squared Enror
Ransilk Rannnit
(WWeng))
Tolnnre Error
A00llngn
Compresusr
2.4
Comprssaer
Pro)
2.0
30
10 20
40
10
50
Reration No.
Iteration
Iteration
Iteration No.
Figure 4: Experiment results on three distributed optimization tasks: distributed power iteration, distributed k-means, and distributed linear regression. The first two use the with the images resized to 32 x 32, hence d = 1024. Distributed linear regression uses UJIndoor dataset with d 512. All the experiments are repeated for 10 random runs, and we report the mean as the solid lines, and one standard deviation using the shaded region. The violet line in the plots represents our proposed Rand Prai--ortoososAAAAAS estimator.
dataset
3. Distributed linear regression. We perform linear regression on the UJIndoor dataset distributed across clients using SGD. At each iteration, each client computes a local gradient and sends an encoded version to the server. The server computes global estimate of the gradient, performs an SGD step, and sends the updated parameter to the clients. We run the experiments for 50 iterations with learning rate 0.001. The task-specific loss is the linear regression loss, i.c. empirical mean squared error. To have proper scale that better showcases the difference in performance of different estimators, we plot the results starting from the 10th iteration.
Results. It is evident from Figure that -wo---rort-aallllllll configuration T (see Section 4.3p that does not require the knowledge of the actual degree of cor- relation among clients, consistently outperforms the other estimators in all three tasks. Additional experiments for the three tasks are included in Appendix [D.]] Furthermore, we present the wall-clock time to encode and decode client vectors using different sparsification schemes in Figure 5 Though Rand- Soodd-Poj-SSee Spatial(Avg has the longest decoding time, the encoding time of Rand-Proj -Spatia((Aaaag is less than that of the adaptive Rand-k(Wangee sparsifier. In practice, the server has more compu-
our estimator with the practical

---

Distributed Power Iteration
n0=10, 1020 d=1024
n=10. k=102, d=1024
nw50. k-20, d=1024
n=50, ko d=1024
Randik
Encoding Time
Decodino Time
Eixcou Title
Rand & Apapr
Hand kittang
Decoding Time
Sandie-Sppt atteot
alcheg)
Indised Compresaar
Rand Pray- ael thrg!
WoWanng Campressor
Runditro
0.0
0.0
10
20
30
10
30
10
20
Iteration No.
Iteration No.
Iteration No.
Iteration No.
Distributed K Means
n=10, k=102, d=1002d-1024 1-204
n-10, k=102. d-1024
n=50. k- d-1024
n= k-20. d=1024
2.0
Eregding
Fand Spariaieeg
Decodina
Rand Rand--IFangni
Induced Comp
Induced Compreserr
Randing ScoldlAog)
Rand Prii AAur
0.4
20
10
20
30
10
20
10
20
30
Iteration
Iteration No.
Iteration No.
Iteration No.
Distributed Linear Regression
1o-1 n=10, k--50, d-512
1e-1 1m10 k=50,
1c-3
50 k-10, d-512
10-1 n= lo dw512
Band-c
Encoding Iine
Foodiin Time
fandi: Sprdaeia
lanck
Randic
Induced Comoreasrr
Randi (Aug)
9-2
Froy Spatia (hug)
lundkillanggn
Rand <ianggi
Indused Comp easor
Induced Compressr
Irduced Compuisor
Randitg Apor
land ApallskAug)
Rand hii Spor
Figure 5: The corresponding wall-clock time to encode and decode client vectors (in seconds) using different sparsification schemes, across the three tasks.
tational power than the clients and hence can afford a longer decoding time. Therefore, it is more important to have efficient encoding procedures.
6 Limitations
We note two practical limitations of the proposed Gand-Proj-Spatial
1) Computation Time of Spat-ia The encoding time of Proj-Proj-Spatial is O(kd), while the decoding time is O nk).. The computation bottleneck in decoding is computing the cigendecomposition of the x matrix Σ G² G, of rank at most rik. Improving the computation time for both the encoding and decoding schemes is important direction for future work.
2) Perfect Shared Randomness. It is common to assume perfect shared randomness between the [58]. However, to perfectly simulate randomness using Pseudo Random Number Generator (PRNG), at least log, d bits of the seed need to be exchanged in practice. We acknowledge this gap between theory and practice.
server and the clients in distributed settings
Conclusion
In this paper, we propose the Sand-Proj-Spatiall estimator, novel encoding-decoding scheme, for communication-effiiinn distributed mean estimation. The proposed client-side encoding generalizes and improves the commonly used Rand-k sparsification, by utilizing projections onto general k- dimensional subspaces. On the server side, cross-client correlation is leveraged to improve the approximation error. Compared to existing methods, the proposed scheme consistently achieves better mean estimation error across variety of tasks. Potential future directions include improving the computation time of Rand-Proj Proj-Spatial and exploring whether the proposed Rand-Proj- Proj-Spatial achieves the optimal estimation error among the class of non-udaptive estimators, given correlation information. Furthermore, combining sparsification and quantization techniques and deriving such algorithms with the optimal communication cost-estimation error trade-offs would be interesting.
10

---

Acknowledgments
We would like to thank the anonymous reviewer for providing valuable feedback on the title this work, interesting open problems, alternative motivating regression problems and practical limitations of shared randomness. This work was supported in part by NSF grants CCF 2045694, CCF 2107085, CNS-2112471, and ONR N00014-23-1-2h5 2149.
References
[1] Jakub Konečný, H Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimiza- tion: Distributed machine learning for on-device intelligence. arXiv preprint arXiv:/610.02527, 2016.
[2] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication -fficcief learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pages 1273-1282. PMLR, 2017.
[3] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, al. Advances and open problems in federated learning. Foundations and Trends Machine Learning, 14(1-2):1-210 2021.
[4] Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, Brendan McMahan, Maruan Al- Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al. A field guide to federated optimization. arXiv preprint arXiv:2107.06917, 2021.
[5] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 1rXiv:1409. 1556, 2014.
[6] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 071187771901, 2020.
[7] John A Gubner. Distributed estimation and quantization. IEEE Transactions on Information Theory, 3454))1456-111 1459,, 1993.
[8] Peter Davies, Vijaykrishna Gurunathan, Niusha Moshrefi, Saleh Ashkboos, and Dan Alistarh. New bounds for distributed mean estimation and variance reduction, 2021.
[9] Shay Vargaftik, Ran Ben Basat, Amit Portnoy, Gal Mendelson, Yaniv Ben- Itzhak, and Michael Mitzenmacher. Eden: Communication-effiienn and robust distributed mean estimation for federated learning, 2022.
[10] Ananda Theertha Suresh, X Yu Felix, Sanjiv Kumar, and H Brendan McMahan. Distributed mean estimation with limited communication. In International conference on machine learning, pages 3329-3337. PMLR, 2017.
[11] Jakub Konečný and Peter Richtárik. Randomized distributed mean estimation: Accuracy vs. communication. Frontiers in Applied Mathematics and Statisties, 4:62, 2018.
[12] Divyansh Jhunjhunwala, Ankur Mallick, Advait Harshal Gadhikar, Swanand Kadhe, and Gauri Joshi. Leveraging spatial and temporal correlations in sparsified mean estimation. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[13] Ananda Theertha Suresh, Ziteng Sun, Jae Ro, and Felix Yu. Correlated quantization for distributed mean estimation and optimization. International Conference on Machine Learning, pages 20856-20876. PMLR, 2022.
[14] Samuel Horváth and Peter Richtarik. better alternative to error feedback for communication- efficient distributed learning, In International Conference on Learning Representations, 2021.

---

[15] Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient sparsification for communication-efin efficiien distributed optimization. Advances Neural Information Processing Systems, 31, 2018.
[16] Matthew Nokleby and Waheed U Bajwa. Stochastic optimization from distributed streaming data in rate-limited networks. IEFE transactions on signal and information processing over networks, 3(1):152-161) 2018.
[17] Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qsparse-local-sgd: Distributed sgd with quantization, sparsification and local computations. Advances in Neural Information Processing Systems, 32, 2019.
[18] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication-effcieent sgd via gradient quantization and encoding. Advances in neural information processing systems, 30, 2017.
[19] Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning, pages 560-569. PMLR, 2018.
[20] Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. Fedpaq: A communication-efffieen federated learning method with periodic averaging and quantization. International Conference on Artificial Intelligence and Statistics, pages 2021- 2031. PMLR, 2020.
[21] Nir Shlezinger, Mingzhe Chen, Yonina Eldar, H Vincent Poor, and Shuguang Cui. Uveqfed: Universal vector quantization for federated learning. IEEE Transactions Signal Processing, 69:500-514, 2020.
[22] Venkata Gandikota, Daniel Kane, Raj Kumar Maity, and Arya Mazumdar. vqsgd: Vector quantized stochastic gradient descent. In International Conference on Artificial Intelligence and Statistics, pages 2197-2205. PMLR, 2021.
[23] Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cé- dric Renggli. The convergence of sparsified gradient methods. Advances in Neural Information Processing Systems, 31, 2018.
[24] Sebastian U Stich, Jean- Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. Advances in Neurul Information Processing Systems, 31, 2018.
[25] Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, pages 3252-3261. PMLR, 2019.
[26] Felix Sautler, Simon Wiedemann, Klaus-Robert Müller, and Wojeiech Samek. Robust and communication--ffiiii federated learning from non-iid data. IEEE transuctions neural networks and learning systems, 31(9):340-3443, 2019.
[27] Shaohuai Shi, Xiaowen Chu, Ka Chun Cheung, and Simon See. Understanding top-k sparsifica- tion distributed deep learning. arXiv preprint arXiv: 19l::11110022.. 2019.
[28] Leighton Pate Barnes, Huseyin A Inan, Berivan Isik, and Ayfer Özgür. rtop-k: A statistical estimation approach to distributed sgd. IEEE Journal on Selected Areas in Information Theory, 1(3):897-907, 2020.
[29] Emre Ozfatura, Kerem Ozfatura, and Deniz Gündüzz Time-correlated sparsification for communication-effiiiee federated learning. In 2021 IEEE International Symposium on Infor- mation Theory (ISIT), pages 461-466. IEFE, 2021.
[30] Yuchen Zhang, John Duchi, Michael Jordan, and Martin J Wainwright. Informatiin-theerreicc lower bounds for distributed statistical estimation with communication constraints. Advances in Neural Information Processing Systems, 26, 2013.
12

---

[31] Ankit Garg, Tengyu Ma, and Huy Nguyen. On communication cost of distributed statistical estimation and dimensionality. Advances in Neural Information Processing Systems, 27, 2014.
[32] Wei-Ning Chen, Peter Kairouz, and Ayfer Ozgur. Breaking the ceammuicatioonpprvaayyy trilemma. Advances in Neural Information Processing Systems, 33:3312-3324, 2020.
[33] Prathamesh Mayekar, Ananda Theertha Suresh, and Himanshu Tyagi. Wyner-ziv estimators:
Efficient distributed mean estimation with side-information. In International Conference Artificial Intelligence and Statittccs, pages 3502-3510. PMLR, 2021.
[34] Shay Vargaftik, Ran Ben-Basat, Amit Portnoy, Gal Mendelson, Yaniv Ben-ltzhak, and Michael Mitzenmacher. Drive: One-bit distributed mean estimation. Advances in Neural Information Processing Systems, 34:362-31) 337,, 2021.
[35] Shay Vargaftik, Ran Ben Basat, Amit Portnoy, Gal Mendelson, Yaniv Ben Itzhak, and Michael Mitzenmacher. Eden: Communication-effiien and robust distributed mean estimation for federated learning. In International Conference on Machine Learning, pages
PMLR, 2022.
[36] Kai Liang and Youlong Wu. Improved communication efficiency for distributed mean estimation with side information. 2021 IEEE International Symposium on Information Theory (ISIT), pages 3185-3190. IEEE, 2021.
[37] Nir Ailon and Bernard Chazelle. Approximate nearest neighbors and the fast johnson- lindenstrauss transform. In Proceedings of the Thirty-Eightt Annual ACM Symposium on Theory of Computing. STOC '06, page 557-563, New York, NY, USA, 2006. Association for Computing Machinery.
[38] Joel A. Tropp. Improved analysis of the subsampled randomized hadamard transform, 2011.
[39] Jonathan Lacotte, Sifan Liu, Edgar Dobriban, and Mert Pilanci. Optimal iterative sketching with the subsampled randomized hadamard transform, 2020.
[40] Oleg Balabanov, Matthias Beaupère, Laura Grigori, and Victor Lederer. Block subsampled randomized Hadamard transform for low-rank approximation on distributed architectures. working paper or preprint, October 2022.
[41] Christos Boutsidis and Alex Gittens. Improved matrix algorithms via the subsampled random- ized hadamard transform, 2013.
[42] Yichao Lu, Paramveer Dhillon, Dean P Foster, and Lyle Ungar. Faster ridge regression via the subsampled randomized hadamard transform. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
[43] Mostafa Haghir Chehreghani. Subsampled randomized hadamard transform for regression of dynamic graphs. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, CIKM '20, page 2045-2048, New York, NY, USA, 2020. Association for Computing Machinery.
[44] Dan Teng, Xiaowei Zhang. Li Cheng, and Delin Chu. Least squares approximation via sparse subsampled randomized hadamard transform. IEEE Transactions on Big Data, 8(2)446-457, 2022.
[45] Jonathan Lacotte and Mert Pilanci. Optimal randomized first-order methods for least-squares problems, 2020.
[46] Nikita Ivkin, Daniel Rothchild, Enayat Ullah, Ion Stoica, Raman Arora, et al. Communication- efficient distributed sgd with sketching. Advances in Neural Information Processing Systems, 32, 2019.
[47] Farzin Haddadpour, Belhal Karimi, Ping Li, and Xiaoyun Li. Fedsketch: Communication- efficient and private federated learning via sketching. arXiv preprint wxXiv:2008.04975 2020.
13

---

[48] Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, lon Stoica, Vladimir Braverman, Joseph Gonzalez, and Raman Arora. Fetchsgd: Communication-effiien federated learning with sketching. In International Conference on Machine Learning, pages 8253-8265. PMLR, 2020.
[49] Gene H Golub and Charles F Van Loan. Matrix computations. JHU press, 2013.
[50] Kilian Q Weinberger, Fei Sha, and Lawrence Saul. Learning kernel matrix for nonlinear dimensionality reduction. In Proceedings of the twenty-first international conference on Machine learning, page 106, 2004.
[51] Rohit Tripathy, Ilias Bilionis, and Marcial Gonzalez. Gaussian processes with built-in dimen- sionality reduction: Applications high-dimensional uncertainty propagation. Journal of Computational Physics, 321:191-22., 2016.
[52] Gregory T. Minton and Eric Price. Improved concentration bounds for count-sketch, 2013.
[53] R. Gallager. Low-density purity-check codes. IRE Transactions Information Theory, 8(1):21-
28, 1962.
[54] Amin Shokrollahi. Fountain codes. Iee Proceedigsscoommniiciions IEE PROC-COMMUN, 152, 01 2005.
[55] Zijian Lei and Liang Lan. Improved subsampled randomized hadamard transform for linear svm. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 4519-4526, 2020.
[56] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint 170.77770, 2017.
[57] Maria-Florina F Balcan, Steven Ehrlich, and Yingyu Liang. Distributed k- k-means and k-median clustering on general topologies. Advances in neural information processing systems, 26, 2013.
[58] Mingxun Zhou, Tianhao Wang, T-H. Hubert Chan, Giulia Fanti, and Elaine Shi. Locally differentially private sparse vector aggregation. In 2022 IEEE Symposium on Security and Privacy (SP), pages 422-439, 2022.
[59] Gene H. Golub. Some modified matrix eigenvalue problems. SIAM Review, 15(2)3318-334 1973.
[60] Ming Gu and Stanley C. Eisenstat. stable and efficient algorithm for the rank-one modification of the symmetric eigenproblem. SIAM Journal on Matrix Analysis and Applications, 15(4): 1266- 1276, 1994.
[61] Peter Arbenz, Walter Gander, and Gene H. Golub. Restricted rank modification the symmetric eigenvalue problem: Theoretical considerations. Linear Algebra and its Applications, 104:75- 95, 1988.
[62] H. Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communicationn-eficccenn learning of deep networks from decentralized data, 2023.
14

---

Appendices
A
Additional Details on Motivation in Introduction
A.1 Preprocssing all client vectors by the same random matrix does not improve performance
Consider clients. Suppose client holds vector x; E Rd. We want to apply Rand-k or Rand-k-Spatial, while also making the encoding process more flexible than just randomly choosing k out of d coordinates. One naïve way of doing this is for each client to pre-procee pre-process its vector by applying an orthogonal matrix E axd that is the same across all clients. Such a technique might be helpful in improving the performance of quantization because the MSE due to quantization often depends on how uniform the coordinates x; 's are, i.e. whether the coordinates of x; have values close to each other. G' is designed to be the random matrix (e.g. SRHT) that rotates x; and makes its coordinates uniform.
Each client sends the server X, E,G,, where E, E gexd is the subsamaping matrix. If we use Rand-k, the server can decode each client vector by first applying the decoding procedure of Rand-k and then rotating it back to the original space, i.c., ((Navv)) GT E E, Gx,, Note that
E E|x Narvel
B E G,Gx,
GT d d.GG.
= X,.
Hence, x
((Niive)) is unbiased. The MSE of g(Naive)
Eim &
@aNavvee is given as
E
|
x (Naive) 2 E
X
1
G E
E,Gx,
n
i=1
Σ
GT
G,
x;
2
1=1
1=1
1
Σ X;
E
Σ E
2
1-2
1
T
E
G.
+
Σ
E
E, Ex,,, GET E,Gx))
Σ x;
2
KZ
i
1=1
(12)
Next, we bound the first term in Eq.
E E. Ex, G" E G.
E E, E.E.
G' Gx)
=x k Llx:
= =x j
( EE E.)
k
- 1xx11
(13)
The second term in Eq. 12 can also be simplified follows.
B E Gx G Ef ExGi)
".''EE G'E
- G. t
15

---

h22
Xis xi).
(14)
Plugging Eq. 13 and Eq. 14 into Eq.
12 get the MSE is
E
x
x
[(Navve
1
n
12
X
2
de X2,,
(x,
xi)
Σ
x
1mi+1
d n k
1)
12:
which has exactly the same MSE as that of Rand-k. The problem that if each client applies the same rotational matrix G, simply rotating the vectors will not change the &g norm of the decoded vector, and hence the MSE. Similarly, if one applies Sand-k-Spatian one ends up having exactly the same MSE as that of Rand-k-Spatial as well. Hence, we need design new decoding procedure when the encoding procedure at the clients are more flexible.
A.2 nk > d is not interesting
One can rewrite En G G; in the Rand-Proj-Spatial estimator (Eq. 5 ET
G.
En g.g. where gj E Rd and gik, Bik+1.-... ((i-1)k are the rows of G. Since when nk >>
Ej= g E|E 8)88] due to Law of Large Numbers, one way to see the limiting MSE of
Rand-Proj- Proj-Spatial when nk is large is to approximate Σ E/= gig." by its expectation.
By Lemma 4.1 when G; E,, Hand-Proj-Spatiee recovers Rand-k-Spatial. We now discuss the limiting behavior
-Spatill when nk > d by leveraging our proposed Rand-Proj-S Spattaa In this case, each gj can be viewed random based vector ew for w randomly chosen in [d]. E="gg + D g = Σn La = unbiased estimator is computed as
nk la. And so the scalar 3 in Eq. to ensure an
nk
BEI
I
G. G.l = Ia
d
3 d
G
G.
Ia
nk
d k
nu
B=n
And the MSE is now
E
||X
x1|
=
X
3 nk
Ia
E
Ex 12
1=1
1=1
d
32
ET
E.x,
x 12
i=1
n1
Σ
E
E 12
+2 Σ
E Exx, E ExXi)) - Σ x
n
22
&
n
k2
n
x;
+2
(x,,x)) x
-11 Σg x 12
nu
2
d2
1=1+1
i=1
&
Σ 1xi122 2 n
n
n
X xi)
(x,, xi)
1=#+1
x 2
16

---

which is exactly the same MSE as Rand-k. This implies when nk is large, the MSE of Kand-k-Spatin does not get improved compared to Rand-k with correlation information. Intuitively, this implies when nk > d, the server gets enough amount of information from the client, and does not need correlation improve its estimator. Hence, we focus on the more interesting case when nk < d that is, when the server does not have enough information from the clients, and thus wants to use additional information, i.e. cross-client correlation, to improve its estimator.
B
Additional Details on the Rand-Proj-Spattal Family Estimator
B.1
3 is scalar
From Eq. in the proof of Theorem 4.3 and Eq. 25 in the proof of Theorem 4.4 it is evident that the unbiasedness of the mean estimator Rand Pruj Spanel is ensured collectively by
The random sampling matrices {E,).
The orthogonality of scaled Hadamard matrices H H = dIa HH
The rademacher diagonal matrices, with the property (D,)² = La.
B.2 Alternative motivating regression problems
Alternative motivating regression problem
Let G, E kxxd and W; E dd be the encoding and decoding matrix for client i. One possible alternative estimator that translates the intuition that the decoded vector should be close to the client's original vector, for all clients, is by solving the following regression problem,
1 n
& arg min f(W) Blll
W.G.x,
1 Σ B[W.
subject to x
(15)
where W (W1, W W.. and the constraint enforces unbiasedness of the estimator. The estimator is then the solution of the above problem. However, we note that optimizing a decoding matrix W; for each client leads to performing individual decoding of each client's compressed vector instead of joint decoding process that considers all clients' compressed vectors. Only joint decoding process can achieve the goal of leveraging cross-client information reduce the estimation error. Indeed, we show as follows that solving the above optimization problem in Eq. 15 recovers the MSE of our baseline Rand-k. Note
S(W) = [||l 20 1=1
x; W,G E(I
Σ
-
17 1=1
[I W,Gxx;11 + Σ (Ia (1-
E
(1e
(16)
n
By the constraint of unbiasedness, i.e., x = 1 " X; = - W.G.x,)) there is
X;
E W.W.G... = 0 +
Σ
0.
We now show that a sufficient and necessary condition satisfy the above unbiasedness constraint that for all i E [n]] W.G.
La-
17

---

Sufficiency. is obvious that if for all i [n], E, = Ia, then we have - = 0.
Necessity. Consider the special case that for some E [n] and [d]. x, nex, where ex is the X-th canonical basis vector, and xj O, and for all E [ \ [7). Then,
e = x x== Σ F,, - Be,,G,,ee, [B[,,G,])..
where [-lx denotes the Å-th column of matrix G.
Since our approach is agnostic to the choice of vectors, we need this choice of decoder matrices, by varying À over [d]. we see that we need E[W,G;] = Ia- And by varying i over [ni], we see that we need E [W G I for all j E [m].
Therefore, x = : E x + EiE BWW. = Ia- This implies the second term of f(W) in Eq. i6 O, that is,
(Ia W.G.)x,, (Ia W,G,)x;) = O.
1
Hence, only need solve
x
arg arg min f2(
Σ (G
(17)
W
Since each W, appears in f2( () separately, each W; can be optimized separately, via solving
min [(La W.G.)xx:lã subject E[W,G.] La-
One natural solution is to take W; = c!. vi E [n]. For i E [m]. let G, V.A,U? be its SVD, where V, Rexd and U; dddd are orthogonal matrices. Then,
W.G. U.
d " d U.S.U
where Σ is a diagonal matrix with Os and Is on the diagonal.
For simplicity, we assume the random matrix U2 follows continuous distribution. U, being discrete follows a similar analysis. Let p(U:) be the measure U.
d -
LEU.N = {1 EUE.UU [.] du(().)
W.W.G.J
d U,ELE, U.UU m(U.)
J.
d | To Ju,
U. k
IaU, dp(U.)
d k La It. k d
which means the estimator
1 -.= $ d
G.G.G satisfies unbiasedness. The MSE is now
MSE = E
||x
W.G. x [3]
1 n2
E - W.G,,,
Σ
[1x,11
E|] B| | - -E,, E(W,G()
+ -xxx,
+
18

---

B -
1xx118)
XB((W.G)) - 11x1133
12
Again, let G. V,A,UU be its SVD and consider W,G. LUEL, where Σ, is diagonal matrix with and 1s. Then,
MSE-
-|x
i=1
1xx113)
x
12
Since G3 has rank k, Eg is a diagonal matrix with out of d entries being I and the rest being 0. Let (U.) be the measure of Ug. Hence, for E [n].
BUNNU Ju: EUUN" Uildp((U))
UEE! U.UUT)(UU.)
Ju
I.. UUIAU du(,))
[ Iud)(U.) d
k
d
Ia-
Therefore, the MSE of the estimator, which is the solution the optimization problem in Eq. 15
is
MSE
n Σ
1
d
k
Lax: 1xx11
d
K 1)
1)
|x:1|2.
n
which is the same MSE as that of Rand-k. Alternative motivating regression problem
Another motivating regression problem based on which we can design our estimator is
arg min
|
Σ G
1 Σ G
(18)
n
Note that G; E IR kxd Vi [n], and the solution the above problem is
(ssolution)
Σ
G....
1=1
1=1
and to ensure unbiasedness of the estimator, we can set 3 E IR and have the estimator as
& (estimator)
=B(_ Σ G Σ Gx)).
is not hard to see this estimator does not lead to an MSE as low as Rand-Proj Proj-Spatial does. Consider the full correlation case, i.e., vi [ri], for example, the estimator is now
glestimator)
3
19

---

Note that rank( 1 Ei=1 G;) is at most k, since G; E B vi E [k]. This limits the amount of information of x the server can recover.
While recall that in this case, the Hand-Proj-Spatiee estimator is
n1
x
SRand-ato--Spattall
Σ
G G. Σ
G Gx 3S
where S can have rank at most nk:
B.3 Why deriving the MSE of Rand-Proj-Spatial with SRHT is hard
To analyze Eq. 11 one needs to compute the distribution of eigendecomposition of ا G. G Le. the sum of the covariance of SRHT. To the best of our knowledge, there is trivial closed form expression of the distribution
sigen-decomposition of even a single G. G when G; is SRHT. other commonly used random matrices, e.g. Gaussian. When G, is SRHT, since G. = D E; and the eigenvalues of E E; are just diagonal entries, one might attempt to analyze HD, While the hardmard matrix H's ss cigenvalues and cigenvectors are knowr the result can hardly be applied to analyze the distribution of singular values or singular vectors of HD.
Even if one knows the eigen- degeopeecooooitioonn of single G G, it is still hard to get the eigen- decomposition of S. The eigenvalues of matrix A can be viewed non-linewt function in the A, and hence it is in general hard to derive closed form expressions for the eigenvalues of A + B, given the eigenvalues of and that of B. One exception when and have the same eigenvector and the eigenvalues of A + B becomes sum of the eigenvalues of A and B. Recall when G; E,, Rand-Proj- Proj-Spptiial recovers Land-k-Spatial. Since E E, 's all have the same eigenvectors (i.e. same I,), the eigenvalues of S Σ E E, are just the sum of diagonal entries of E E, ss Hence, deriving the MSE for Rand-K -annd---pptiall is not hard compared the more general case when G G2's can have different eigenvectors.
Since one can also view S = En Big?" i.e. the sum of nk rank-one matrices, one might attempt to - + gn'+1g" for n' S n. One related
recursively analyze the eigen-decomposition problem is decooposcoooiiiionn of a low-rank updated matrix in perturbation analysis: Given the digen-decomposition of a matrix A, what the iigen-decompositionn of A + VVT, where V is low-rank matrix (or more commonly rank-one)? To compute the eigenvalues of A + VVT directly from that of A, the most effective and widely applied solution is to solve the so-called secular equation, e.g. (59, 60, 61.. While this can be done computationally efficiently, it is hard to get closed form expression for the eigenvalues of A + VVT from the secular equation.
The previous analysis of SRHT in e.g. 37 38 45 55 is based asymptotic properties of SRHT, such as the limiting eigen-spectrum, or concentration bounds that bounds the singular values. To analyze the MSE of Rand-Proy Poond-Pro-Spptilll however, distribution SRHT. Concentration bounds does not apply, since computing the pseudo-inverse in Eq. naturaaly bounds the eigenvalues, and applying concentration bounds will only lead to a loose upper bound on MSE.
need exact, non-asymptotic analysis of the
"See this note attpss:/core.. http::///oooee...uuoooooooooee ac..uk//ooommllaa/a//////99/02/0
20

---

B.4 More simulation results on incorporating various degrees of correlation
50
5, 100
=
150
k 200
1.2
1.8
3.8
1.0
1.6
0.6
MSE
0.8
1.4
0.4
Rand-k
Rand-K
0.6
Rand-k
Randk
Rand SpataalOutt)
1.2
Rand Spetilttt
Ra Spatial(ooti
0.2
RandkkSpattattppt
Sanat-raj-Spatiall
Rand-ProjSpatial
0.4
Rand-Proj-SSattll
Rand-Praj- Spalial
1.0
0.0
2
3
3
1.7
0.9
2.9
1.1
0.8
2.8
00
1.0
0.7
Rand-k
Rand-i
0.9
Rand-k
Randkk
SpatillOst))
Opt
Randik Spatisl(Opt Spaatta
0.6
SpatiallOpti
2.5
SpaatilrajSppataall
Spatial
0.8
Rand-ProjSpaatal
2
6
2
6
8
Figure 6: MSE comparison of estimators Rand-k; Rand-S-Spatial((Op) Rand-Proj-Spatial, given the
degree of correlation R. (and-k--patia((Opt)) denotes the estimator that gives the lowest possible MSE from the Rand-k-Spatial family. We consider d 1024, a smaller number of clients n (5, 111, and & values such that nk < d. In each plot, we fix n, k. and vary the degree of positive correlation R. Note the range of R R E [0, I]. We choose R with equal space in this range.
C All Proof Details
C.1 Proof of Theorem
Theorem 4.3 (MSE under Full Correlation). Consider n clients, each holding the same vector d Rdd, Suppose we T(X) = X, I in Eq. 5 and the random linear map G; at each client to be an SRHT matrix. Let the probability that Ei= G.f G2 does not have full rank. Then, for nk < d,
|55 (Raud-Proj-- Proje--PPj-aaaaaa Spoj-Sppatal(Maxx)
x|2
I
(1 8)nk + 8k 1 ||x|12
(19)
Proof. All clients have the same vector X1 = X2 and the decoding scheme is
Xn = x E Rd. Hence, x= 1 Σi= X,
(RanddProj-SpatiilMMMa) = Σ G. G
Σ
G 3st Sx.
where S -T G. Let - UAU be its eigendecomposition. Since S is real symmetric matrix, U is orthogonal, i.e., UTU I = - Also, S UATUT, where At is diagonal matrix, such that
1/[A]a if Aa + 0, else
[A = 10
Let de the probability that S has rank e, for E (k, + 1,..., nk: 1}. Note that 5 nnk-1 8 For vector m E Rd, we use diag (m) E Rdxd to denote the matrix whose diagonal entries correspond to the coordinates of m and the rest of the entries are zeros.
Computing 3. First, compute 3. To ensure that estimator & (Randd-Poj-SSaaiilMMaaa)) is unbiased, we need SE(st Sx] = x. Consequently,
BEJUAUT UAUT
21

---

3
Pr(U - " 1U= $ x
Pr(U= +UUEAA U - x
(4) 3
Pr(U = a dJUE|diag(m)
U 1U= = x
nk-1
(N)
Σ
Pr(u- = Φ
U 11(11-1))) - 0)
nk la +
Σ
de d (
x
d
U=
co
nk
(( 11-5) 8)
nk
8e d
d
d
(20)
(1
8)nk +
nuk-
8.c
where in (a), m E gd such that
11
if A3s > 0 else.
m
0
Also, by construction of S, rank(diag(mm) (m) S nk. Further, (b) follows by symmetry across the d dimensions.
1), there is Since 8k - Eot.' dec S 8(nk
S 8)nk + 5k
(21)
(1 (1- 8)nk 8(nk - 1)
Computing the MSE. Next, we use the value of /3 in Eq. 20 to compute MSE.
( = |[[| Proppppli)))) x x|
B|||3st Sx
x12]
= 2 /3ssst Sx),
Sx 1|
(Using unbiasedness of X (Rand Pruj Spatial(Maxi) )
3 (St) ||x
(22)
Using St UA
E|S 1 ( BUUADUNOO
= =E(UA(N)PAU")
Σ UEJA(A))N P-UU=))
U=$
nk-1
= {)
Ia+
Σ
de ls
UT Pr(U = Φ)
U=4
c=
nk-1
(1- 0) -1
nk
+
Σ
8
Σ
7
c=
U=$
nk
nk
(1 8)
+ Σ
d 7
la
d
c=kk
1
(23)
8
22

---

Substituting Eq. 23 in Eq. 22 we get
= =3xx² 1
MSE(Raan--Pa Proj--Spttiil
Z L0x
1|2 = (3 1
1
1 11 8)nk + ök 1 ||x|2
where the inequality is by 21
C.2
Comparing against Rand-k
Next, we compare the MSE of Proj-d-r--Sppiil(MMM with the MSE of the baseline Rand-k: analytically the full-correlation case. Recall that in this case.
MSE(Rand-k) = ( 1)|x1/2
We have
MSE (Roj--doo-joopppaialllll - MSE((ann-k)
- -1 ( - 1)
(1 8)nk + 5k
d n - (1 - 8)n 8
k n((1 8)n 5)
8- 6/n
n-1
e k (1 - 8)m + 8 <
n
dō(1
S k(n 1) ((1 5)n + 8)
+ dō k ((1 8)n 6)
+ dō + knō kō < kn
kn
8 d kn
8 <
km
Since nk < d, for 2 2, the above implies when
2
3
the MSE of PoonddPoo-SpppillMMaaaa is always less than that of Rand-k.
C.3 S has full rank with high probability
We empirically verify that ss 0. With d E {32, 64, 128, ... 1024} and 4 different nk value such that nk < d for each d, we compute rank(S)) for 10 trials for each pair (nk, d) values, and plot the results for all trials. All results presented in Figure 7 As can observe from the plots, rank(S) = nk with high probability, suggesting 6 0.
This implies the MSE of Land-Proj-Spatialll is
d
MSE (Roaaddd-PPoSSpaaiilMaaaaa s
( nk
1) 1)
the full correlation case.
C.4 Proof of Theorem 4.4
Theorem 4.4 (MSE under No Correlation). Consider n clients, each holding vector x; E Rdd, Vi [n]. Suppose set T = 1, 3 & in Eq. 5 and the random linear map G; each client be
23

---

64
30
nk=4
60
nk
nk=8
nk=16
RankiS)
20
Rank(S)
nk-64
20000
40000
60000
80000
100000
20000
40000
60000
80000
100000
Trials
Trials
128
256
125
250
100
nk=
200
nk=32
nk=64
nk=128
Rank(S)
Rank(S)
75
nk= 128
150
n56
50
100
25
0
20000
40000
60000
80000
100000
20000
40000
60000
80000
100000
512
1024
500
1000
nk-64
400
800
nk=128
RanksS)
Rank(S)
300
nk=128
nk= 1024
nk-256
200
nk 512
400
100
200
0
20000
40000
60000
80000
100000
20000
40000 60000
80000
100000
Trials
Trials
Figure 7: Simulation results of rank(S), where S = Σ.= G. with G; being SRHT. With {32, 64, 128....... ..... 1024] and 4 different nk values such that nk < d for each d. we compute rank(S) for 10t trials for each pairs of (nk, d) values and plot the results for all trials. When d = 32 nk 32 in all the rest
and nk 32 in the first plot, rank(S) 31 in 2100 trials, and rank(S) of the trials. For all other (nk, d) pairs, S always has rank nk in the 10 trials. This verifies that (S) nk]
an SRHT matrix. Then, for nk S d.
d n k
E | (Rand- (Rand-Prrt--ppatlal)
1
11
i=1
Proof. When the client vectors are all orthogonal to each other, we define the transformation function on the eigenvalue to be T()) 1, VA 0. We show that by considering the above constant T. SRHT becomes the same as rand k. Recall = E G. G; and let GT = UAUT be its eigendecompostion. Then,
T(S) = UT = UL.T La.
Hence, (T(S))* IJ. And the decoded vector for client i becomes
x; = 3 [ Gi) G G.x, = 3.. = E,
(24)
x n
D.
24

---

D; is a diagonal matrix. Also, E,E, E Rddd is diagonal matrix, where the i-th entry is 0 or 1.
Computing B. To ensure that x is unbiased estimator, from Eq. 24
x G G.
B D E
E,H.
ED. D T E E, HD. x;
( E, is independent of D;)
Ik/d)Ja
d JKBD. [D Xi
(: C: H =
Bk
d. Xi
(: D = I is now deterministic.)
d
+
B
(25)
k
Computing the MSE.
MSE = E
x
x
E
D.H
Σ Xi
E EHD x,
+
X
E
D
):
1=1
1
Σ
D !
Σ
(: E 8)
2
1=1
1=1
E
D. x
-
(26)
1
+2
EDD. -2
d
2m 1mi41
1mi+1
Note that in Eq.
26
E
D
E. E,HD X
D E E.H.D.D.'E,
x D E HDxx
(: H. = =dI,)
= =dx; EDD
D.H E E
HD:
X;
(E,, D; are independent;
= =E E,)
=x 112
(27)
since E[E, E,) (k//d] H
H
dIa and for i +
E.D.H E E, E.H.D
D ET E, HD = (xx,,xx) = -22(xx x1
(28)
Substituting Eq.
27
28
in Eq.
26
we get
1 MSE-
kd]|x;
112
32R2
X xxxxi)
Σ
n
xx)xxi)
n²
d
d2
(mi+1
1
Σ
n
|
2
T
which is exactly the same the MSE of rand k.
25

---

C,5 Band-Proj-SSatiall recovers Rand-k-Spatial (Proof of Lemma 4.1)
Lemma 4.1 (Recovering Rand-k- -SSptiil,,, Suppose client generates a subsampling matrix E, (ei, exe] where {ez)}=ı are the canonical basis vectors, and {i1,..., ik) are sampled
from {l,.... df without replacement. The encoded vectors are given as &; = E,x;, Given a function T, & computed in Eq. 5 recovers the Rand-k-Spatial estimator.
Proof. If client i applies E; E Rxd as the random matrix to encode x, in Land-Proj-Spatian by Eq. S client i's encoded vector is now
Pand--Pooj-Spoiial) = (T(T( E E.) E Exx;
(29)
Notice E, is diagonal matrix, where the j-th diagonal entry 1 if coordinate of x; is chosen. Hence, E. E,x; be viewed as choosing io coordinates of x; without replacement, which is exactly the same as Rand-k- Sand-k-Spatiall 's (and Rand-k's encoding procedure.
Notice Σx= -==1 E E; is also diagonal matrix, where the j-th diagonal entry is exactly Mj. i.e. the number of clients who selects the j-th coordinate as Rand-k- k-Spaiial 12] Furthermore, notice
(TEEL E. E.)) is also a diagonal matrix, where the j-th diagonal entry is T(M))) which recovers the scaling factor used in Rand-k- --Satial's decoding procedure.
Cand-Proj-Spatial computes 3 as
BE [ E E.) E
E.E,X.
Since
(T(EL, E, and E E, recover the scaling factor and the encoding procedure of RSpa-i-, and / is computed in exactly the same way as Rand-k-Spatial does, 3 will be exactly the same as in Rand-k-Spatial.
Therefore, x (Rand Proj Spatial) in Eq. 29 with E, as the random matrix at client recovers x (Rand Spatial) (Rand-Proj--
This implies Rand-Proj-Speen recovers Rand-k-Spatial in this case.
26

---

D Additional Experiment Details and Results
Implementation. All experiments are conducted a cluster 20 machines, each which has 40 cores. The implementation is in Python, mainly based numpy and scipy. All code used for the experiments can be found at battps://githmm
com/ www.fish/iihaaaaaaaaa Proo:/annndd-------- P
Data Split. For the non-III dataset split across the clients, we follow 62 to split Fashion -NIMIIST, which used in distributed power iteration and distributed k-means. Specifically, the data first sorted by labels and then divided into 2n shards with each shard corresponding to the data of particular label. Each client is then assigned 2 shards (i.e., data from classes). However, this approach only works for datasets with discrete labels (i.e. datasets used in classification tasks). For the other dataset UJIndoor, which is used distributed linear regression, we first sort the dataset by the ground truth prediction and then divides the sorted dataset across the clients.
D.1 Additional experimental results
For each one of the three tasks, distributed power iteration, distributed k--maan,, and distributed linear regression, we provide additional results when the data split is IID across the clients for smaller n. k values in Section D.I.I. and when the data split is Non-IID across the clients in Section D.1.2 For the Non-lID case, we use the same settings (i.e. n, k, d values) as in the IID case.
Discussion. For smaller n, k values compared the data dimension d, there is less information or less correlation from the client vectors. Hence, both Rand-k-SSatte and Rand-Proj-SS Projs-rrj-ppatlll perform better as nk increases. When n, small, one might notice Rand- Rand-Proj-Sypee Proj-Spatial performs worse than Rand-k- Wangni in some settings. However, Rand-k- Rand-k-Wangmi is an adaptive estimator, which optimizes the sampling weights for choosing the client vector coordinates through an iterative process. That means Rand-k--Wangni Wangni requires more computation from the clients, while in practice, the clients often have limited computational power. In contrast, our Rand-Proj-Sppe Spatial estimator is non-adaptive and the server does more computation instead of the clients. This is more practical since the central server usually has more computational power than the clients in applications like FL. See the introduction for more discussion.
In most settings, we observe the proposed Loand-Poo-Sppatiii has better performance compared to Rand-k-Spatian Furthermore. as one would expect, both Lund-k-Spatia and Rand-Proj Proj-Spatial perform better when the data split IID across the clients since there is more correlation among the client vectors in the IID) case than in the Non-llI) case.
D.1.1 More results in the IID case
Distributed Power Iteration and Distribued K-Means. We use the Fashion-MNIST dataset for both distributed power iteration and distributed k-means, which has dimension of d = 1024. We consider more settings for distributed power iteration and distributed k-means here: n 10. k (5, 25, 51), and 50, k (5, 10}.
27

---

Distributed Power Iteration
1e20
d=1024
35-
100
Randie
1.3
2.0
(patialteg)
1.2
30-
SandkiWannpn
Spadslleeg)
3.3
Squaee
fandl
2.0
Rand-c
Bandik Spraliia
Pand-c-ppatan (Prg)
0.9
Randkk(iaagg))
Rand ciianggt
Indused Compressor vasor
Indused Comprisaer
0.5
Fandithg Allgg
Rand Prri Spar (egg)
0.0
10
10
20
10
10
20
20 Iteration No.
10
Iteration
Iteration
Iteration No.
Distributed Power Iteration
1o5
n-10 10, kw51, d-1024
n-10, kw-1, 1-1024
kandik
rnducee Comoraaoor fand Proj Soattal/uut
indusee Compneesr
hand Proj (patal
5oc-
0.0
20
20
20
Reration No.
lieration No.
Distributed Power Iteration
1eB
n=50, km5, dm1024
nym 500 km5, dm1024
1x7 n= km10, dm1024
n=50, k=10. dm1024
Randi
1.2
Kandk
Randd
fand-k Spalal
Rardd--Spatia chrgi
Squared Emro
2.5
Nunn--tWanggel
3.0
Rand--tWinggi
Induced Comsreaser
induoed Compresser
Induced Compresaor
Rund fro Spaliar (Arg)
Fandl:
hand tre Spatla)A4g)
305
Rand-Prci-Spuri (Arg)
0.9
Randle Stadaiiastatiegg!
0.5
0.8
Band-Png Saaaaa////aa
Indiaeed Compaesar
Iteration
Iberation
Iteration No.
Iteration No.
Figure 8: More results of distributed power iteration on Bichion-MNIS. (IID data split) with = 1024 when n 10, E (5, 25, 51} and when n 50, k: E 10).
Distributed
n-10, d-1024
lc7
d-104
d-1024
105 n- k-25, 1024
2000
2,0
Souared Er0or
1000
induced Comp
induced Compueser
1002
Indusee
Induced
Rand frej Spat allle
Rand Sparia/Agg
750
Rand Proj Apatha)
Rand froj Statial
3,0
0.5
0
10
20
30
10
20
30
22 Rteation No.
30
Reration No.
Iteration No.
Iteration No.
Distributed K
n=100, km 57, de 1c26
lnt
n=10, kn51, de1024
Handie Sexiaiig
Namdle
252
Kardk
Kand apoiia Mog!
RandietWanggi
2.25
Chmeressor
inducaa
200
2.03
p20o
2.73
200
153
10
10
20
Bor Aeration No.
Iaer Aeration No.
Distributed K Means
n=30, km d=1024
2ed no 50, b, 1020
ni 50, 100, 1=1024
1e5
n=
k=10, 1022
Kand i
Randit
Randik
275
Randia
Squared Erot
1500
Rand- Bandl---pptaalllgg
Band chWangn0
Rand- Spacis (eg!
G02
Rand-tWanggi
Band Alg
250
Band- Spaccaliigg
Band -twangn
2000
induced Comp
Induced Comprsser
Induces saasor
225
Inouced Compreasor
2000
500
1.75
10
20
32
15
20
30
Eeration No.
Iteration No.
Iteration
No.
Beration No.
Figure 9: More results on distributed k-means on Rashion-MMISE (IID data split) with d = 1024 when n = 10, & E (5, 25, 51) and when 50.2 (10,51)

---

Distributed Linear Regression, We use the UJIndoor dataset distributed linear regression, which
has dimension of 512. We consider more settings here: n 10, k E {5,25) and 50, (1,5).
Distributed Linear Regression
107
kowS, d-512
1s4
kw-,
dw512
2c6
10,
Squared Eror
0.5
Compressor
Induced
indured Compressor
Rand- (roj wilhust
Rand
Rand Pine Sparialegg
32A
Rant Spatio
10
20
30
60
10
50
10
20
10
40
10
Iteration No.
Iteration No.
Iteration No.
Iteration No.
Distributed Linear Regression
n1 SO, kmm,, dm
n=50, km1, d=512
n=50, de
n=50, kmb, dlmb12
Squared Errer
Randllk Seenik-Ssaiaa Sperattieg?
Randlkk
Rand [[Wagee))
Rand kpod
Rand
2.0
2.5
Rand koWanggn
Rand k Spadaaldeg)
Rand K
3.00
3.25
Rond
Rand Sparia ldug!
Randlk
induneed Compreser
3.5
Rand--Pre Spal
Induceed Comprexece
2.0
Rand Pri Spanns///w)
indereed Composser
52.75
2.50
Intirned Compresser
Fox Spp (Pup)
0.5
30
50
10
20
30
40
10
20
50
Reration No.
Ior Corration No.
Iteration No.
Steration No.
Figure 10: More results of distributed linear regression on UJIndoor (IID data split) with d = 512, when n = 10. & E {5, 25} and when n = 50, k {1,5). Note when & = 1, the Induced estimator is the same as Rand-k.
29

---

D.1.2 Additional results in the Non-IID case
In this section, we report results when the dataset split across the clients are Non-IID, using the same datasets as in the IID case. We choose exactly the same set of n, values as in the IID case.
Distributed Power Iteration and Distributed K-Means. Again, both distributed power iteration and distributed k-means use the Fashion-MNIS dataset, with dimension d 1024. We consider the following settings for both tasks: n = 10, k E (5, 25, 51, 102} and n = 50, k E {5, 10, 20).
Distributed Power Iteration (Non-IID)
1+30
n=10, low,, 1=1024
7w10, kw5, d=1024
1e0 n010, kw25,, d=1024
n- kw25,, dw1024
3.0
Rand-c
Sandkk
2.5
Sandk- Spntt--Sa
SandkiWanpnn
2.00
Compesser
11.5
Spartwuugg
kand
210
Randik
Fand Spatatiee Ienrni
Rand- i -patta (hug)
0.
Rand -iianggi
3.5
0.8
Indused Comp capor Rand-ing Alggg)
9.8
Induced Compresarr Rand Proi Spor (Pgg)
5.0
20 Iteration
Iteration
Iteration No.
Iteration No.
Distributed Power Iteration (Non-IID)
1.0
n=
km d=1024
n=10, kmb3, dm1024
1o3 n=10, km102, 1024
n=10, Ion 102. dm
2.75
Bandie
1.1
fans-k
0.35
Band-k
sa.sed Error
3.50
Band setaagiii
Band Apatitieeg
100
Par SEru
Rans Sppetaattta)
Rand Wunghn)
0.80
Band kiWengee
Rand SpattatAgg)
Induced Comp casoo
incuced Compresst
0.85
Induood Compresser
Rand-PPry- Spar allhwg!
Fanc trort-roo-ssaaaaappe (Par))
0.800
Rand Prry Spatawlss)
Sparitldegg
0.75
0.70
10
10
10
20
30
Iteration No.
Iteration No.
Iteration No.
Ieeration No.
Distributed Power Iteration (Non-lID)
1:5
n-50, Jow,, 1024
n- k=5, d=1024
147
n= ko-10, d-1024
n-500 kow00, dw1024
2.0
Randic
fandk
3.3
tanc-k (pgl
Sqqurred Eiror
3.5
Induced sressr
-tWangei
1.1
Induced Compressor
kandkiltlangnn
fro Spallar
kand
kand tro Spatha)Aug)
Randik
Rand Sestalieg Randi)
RRand Spotialaat k Indunee Compencoa SanstPro-Sppats// (Pwg)
0.9
2.5
0.8
Rand-Png- SSaeaallllaa
Induned Compaesar
20 Iberation
Iteration
Iteration No.
Iteration No.
Distributed Power Iteration (Non-lID)
n=50, n=50,k=00 d 1024
p=50, k=20, d=1024
kandik fardi Spuli leg! koninggi
hand Prof Souniadjogg
hand Prre SpatialAug!
1.8
10
20 Daration No.
Rar Reradin No.
Figure 11: Results of distributed power iteration when the data split is Non-IID. n 10, k (5, 25, 51, 102) and n = 50, E (5, 10,200. 20).
Distributed Linear Regression. Again, use the UJIndoor dataset for distributed linear regression, which has a dimension d = 512. We consider the following settings: n. = 10, k E (5, 25, 50) and n 50, A (1,5, 50].
30

---

Distributed Means (Non-IID)
n=10,km5 d-1024
C-m 10, k- d-1124
1m10, 2525, d-1024
n=10 k=25,d-1024
2000
Nandiit
Band-
Bandi Rand alllog
Randic
Fand aldee!
2.0
Rand Spar
Fund Spapplieeg!
Souared En0
fand A2Wangril
Rand Liwong
Rand stttrrgnn
Ford loWargro
irduced Compresso"
land Prej-Sottttt Allg
LOSE
5.5
Induced Compremer
Rand Troj Sparittggg
RandiPhg Spattal/a)))
Induces Compressor
Rand StopSpatallArn
Induced Compressor
2000
Distributed Means (Non-lID)
d-1024
Lc5
d-1024
k-102, d-1024
k=102, 6-1024
602
3.0
250
3.6
Saqaaeed Erto
500
AtWbrigni
200
3.6
403
Induced Compreserr
Induced Comprege
Compresser
Compresur
Band Prey Aug!
Band fros Spanatifog!
150
fand Stwplaaalalall
Pryy Spatte (hag?
203
3200
100
302
15
10
20
30
30
20
30
10
20
30
Iteration No.
Iteration No.
Iteration No.
Ieeraion No.
Distributed Means (Non-IID)
n-50, d-1024
ted
d=124
Fi 50,
d-1024
led n=50 k=10,,-1000
1250
Axnd-i
h-Spat alteeg!
Rand-c
Spacial (4rg)
Randic
Band Spot algg
275
Randie
Spanalidegt
Squared Einor
and Frrer
Campresserr
Inducee
Compressor
750
Sparia//gg
500
1.72
250
150
10
20
10
20
Reeation No.
Ite rationnoonnn No.
Iteration No.
Steraiin No.
Distributed K Means (Non-IID)
Int
250
3:0
Randiccouttativg Rond-sttarrrr Insucce Comerrstorr
2.5
Kand www.aaianagee
intuced Commrren moressrr
Randkk-Spate Mog!
150
Rar Mert
200
12
10
lerration
Figure 12: Results of distributed k-means when the data split is Non-IID. n = 10, k E (5, 25, 51, 102) and n 50, k (5, 10,10,00). 20).
31

---

Distributed Linear Regression (Non-IID)
10,10, km5, de
1o4
nm10, ke5, de512
107
n=10, km25,, 512
nm10, km255, des12
Aandik
Randik
Randikk
35
Rordik
Randiik Sparaaiing
Rand SpallakAug)
Randi SSaddillldg)
Roind Sporta ldug)
Squared Crror
Roynch Wesngg)
5.5
Rand (Wangg))
Rand 1itllngnn
Pand-PPa--Soele at/i
Comp meserr
24.5
Rand mey- Spar ktA
Induced Comprreccr
Indlreed Composssor
Randi-Fiy (patlel//gg)
inturred ed Compreserr
Spe (Nug)
4.5
Squal
25
3.5
1.2
No.
Iorratin
No.
Distributed Linear Regression (Non-IID)
n--10, kv-50, d-512
n=100, Ku.50, di512
1.50
Baaz-it
Spar skllog)
Furikk
Spedtal lag!
Squared
Rand akov
Ford akovg)
10
20
10
16
Ceration No.
Ecration No.
Distributed Linear Regression (Non-IID)
100
3o4
187
let
n=50, km5,
Sporilideg) (aaaggg)
SpotiaAAgg)
Soatbll4ug)
Sporia (Arg)
Separeed Error
4.5
ktWangel)
krWa 19
1.50
kowanggi
Comp
Compressee
4.9
Squaroo
2..7
2.50
2.25
2.00
Iteration
Distributed Linear Regression (Non-lID)
50,00 k-10, d=512
n=50, 10, d=512
Roadii
Rand (l
Squared Error
Nuad hrs Spalial
Consresse
2.4
Rand (eed
Intucee Compreteor
2.2
16
20
10
20
16
60
Becation No.
Berallio ilnioo No.
Figure 13: Results of distributed linear regression when the data split is Non-lID. 10, k:
(5, 25, 50} and n = 50, A E {1, 50}.
32


Reviews:
[{"review_id": "6OfGflsXeC", "reviewer": "Reviewer_EAa8", "summary": "This paper discusses the problem of communication-efficient distributed vector mean estimation and proposes a new estimator called Rand-Proj-Spatial that improves upon existing techniques. The paper highlights the challenges of distributed optimization and Federated Learning, where communication cost can be a bottleneck, and explains how sparsification techniques can reduce this cost. The authors then introduce the Rand-k sparsification technique and show how it can be used to reduce communication cost in distributed vector mean estimation. They also propose the Rand-Proj-Spatial estimator, which combines Rand-k sparsification with a Subsampled Randomized Hadamard Transform to improve upon the performance of existing techniques. The paper concludes with experimental results that demonstrate the effectiveness of the Rand-Proj-Spatial estimator in various scenarios. Overall, the contributions of this paper include a new estimator for distributed vector mean estimation that is more communication-efficient than existing techniques, as well as insights into the challenges of communication-efficient distributed optimization and Federated Learning.", "questions": "1. What is the key difficulty/novelty in the design and analysis?\n\n2. Can you provide more detailed analysis of the trade-off between communication cost and estimation accuracy for the proposed estimator and other sparsification techniques?", "limitations": "Not.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "In terms of originality, the paper proposes a new estimator called Rand-Proj-Spatial that combines existing techniques in a novel way to improve upon the performance of distributed vector mean estimation. The use of Subsampled Randomized Hadamard Transform in the encoding-decoding procedure is a creative combination of existing ideas that has not been explored in this context before. \n\nIn terms of quality, the paper is well-written and clearly explains the challenges of communication-efficient distributed vector mean estimation and the proposed solutions. The authors provide rigorous theoretical analysis and experimental results to support their claims, which adds to the credibility of their contributions.\n\nIn terms of clarity, the paper is well-organized and easy to follow. The authors provide clear explanations of the technical concepts and use visual aids to help readers understand the proposed techniques. \n\nIn terms of significance, the paper addresses an important problem in the field of distributed optimization and Federated Learning. The proposed Rand-Proj-Spatial estimator has the potential to significantly reduce communication cost in these settings, which can have practical implications for real-world applications.", "weaknesses": "1. While the paper compare the proposed Rand-Proj-Spatial estimator with Rand-k-Spatial and other sparsification techniques, it would be beneficial to compare the proposed estimator with other state-of-the-art techniques for distributed vector mean estimation.\n\n2. While the paper briefly mentions that the Subsampled Randomized Hadamard Transform can be computed efficiently, it would be helpful to provide a more detailed analysis of the computational complexity of the proposed estimator.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "W1: See common response $\\textbf{Quantization vs. Sparsification}$. \n\nW2: See common response  $\\textbf{Computation Time}$. \n\n\nQ1: $\\textit{Two key novelties:}$ 1) the design of a general encoding-decoding algorithm that generalizes sparsification techniques and enables one to better use correlation among the client vectors to improve MSE compared to the prior work. 2) Previously, SRHT was mostly applied to reduce run time or to homogenize vector coordinates (i.e., to reduce variance). We propose a novel application of SRHT to better leverage cross-client correlation.\n\n$\\textit{Key difficulty in analysis:}$ As we have discussed in Section 4.3 and in Appendix B.2, it is hard to derive closed-form expression of MSE for Rand-Proj-Spatial with SRHT in the general case when the cross-client correlation is in between max correlation and completely orthogonal. \nThis is because the analysis requires a closed form expression for the non-asymptotic distributions of eigenvalues of SRHT, which is a hard problem by itself.\nTo the best of our knowledge, previous analyses of SRHT, rely on the asymptotic properties of SRHT, such as the limiting eigen spectrum, or concentration bounds on the singular values, to derive asymptotic or approximate guarantees. But we need an exact non-asymptotic analysis; or the resulting MSE bound is too loose.\nIn Appendix B.2, we also included several ideas we considered but did not work for deriving a closed-form MSE expression.\n\nQ2: $\\textit{Comparison to biased sparsification based estimators.}$\nIt is in general not fair to compare unbiased estimators, including our proposed Rand-Proj-Spatial, against biased estimators, including Top-$k$. As noted in prior distributed optimization literature [1] and mentioned in Section 1 line 81, unbiased estimators is more favorable to biased ones.\n\n$\\textit{Comparison to unbiased sparsification based estimators.}$\nWhen the client vectors have max correlation and have no correlation, we give detailed analysis in Section 4.1 and Section 4.2 to compare the communication cost-estimation accuracy tradeoffs of our estimator against that of the known sparsification based unbiased estimators, e.g., Rand-$k$ and Rand-$k$-Proj. \nWhen the client vectors have a correlation in between max and none, as we responded in Q1, the analysis is difficult and so we empirically compared the communication-estimation accuracy tradeoffs in Figure 3. Note the Figure 3 presents the estimation error with the communication cost for all estimators being fixed. One can see that the error of the proposed Rand-Proj-Spatial is the lowest and this implies Rand-Proj-Spatial has the best communication-accuracy tradeoff.\n\n----------\n\n[1] Samuel Horváth and Peter Richtarik. ``A better alternative to error feedback for communication- efficient distributed learning.'' In International Conference on Learning Representations, 2021.\n"}, {"review_id": "OHCFUUbBWu", "reviewer": "Reviewer_BRXu", "summary": "In distributed learning, computing the mean of the vectors sent by the clients is an important subtask. Motivated by this, the distributed mean estimation problem is studied in this paper. The two main techniques commonly used for these problems are Quantization and sparsification. Rand-K was one prominent sparsification method used earlier. In [9], this was generalized to Rand-k-Spatial to exploit the spatial correlations of the data using the server-side decoding procedure. A more general encoding scheme, Rand-Proj-Spatial is proposed in this paper which utilizes the cross-client correlation information. This uses Subsampled Randomized Hadamard Transform as random linear maps. They prove that this improves mean estimation under some assumptions and some experiments supporting their claim. ", "questions": "Is Rand-Proj-Spatial optimal or close to optimal, given the correlation information? Some intuition will be good. ", "limitations": "NA", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well presented. The problem generalizes the existing works and the results look interesting.", "weaknesses": "Their techniques are not adaptive to the client vectors. More motivation on why studying why correlation information of clients is practical will be interesting. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "W1: We gave the reason why we want our algorithm to be $\\textit{non-adaptive}$ to client vectors in Section 1 line 82 - 89. \nThe motivation of studying correlation information of clients is well explained and experimentally demonstrated in the prior work [1]. For example, in distributed optimization, clients who are geographically similar often have similar data, leading to having similar model parameters.\n\nQ1: \nWhen there is no correlation, the proposed Rand-Proj-Spatial with SRHT is very likely to be the optimal $\\textit{unbiased}$ and $\\textit{non-adaptive}$ encoder. Recall in this case, Rand-Proj-Spatial recovers Rand-$k$. \nThe evidence of Rand-$k$ being the optimal $\\textit{unbiased}$ and $\\textit{non-adaptive}$ sparsification based encoder comes from Section 6 ``Optimal Encoders'' in [2]. If one considers the probability $p_{ij}$ across the clients and coordinates in the optimization problem in Section 6, which finds the best unbiased estimator that minimizes MSE, to be the same (aka. $\\textit{non-adaptive}$), then the solution to this problem is exactly Rand-$k$. \n\nWhen there is max correlation, the proposed Rand-Proj-Spatial is also very likely to be the optimal, since by Eq.(6) in our paper, the error of the estimator in this case essentially depends on the rank of $\\mathbf{S}$. Rand-Proj-Spatial with SRHT makes $\\mathbf{S}$ achieve the max rank, i.e., $nk$. \n\nWhen the correlation is in between max and none, it is hard to derive a closed form expression for MSE. We do not know whether the current way of incorporating varying degrees of correlation by applying a transformation function $T$, which interpolates between max and no correlation, on the eigenvalues of $\\mathbf{S}$, is optimal. However, the prior work [1] shows $T$ is the optimal transformation in the special case of our estimator, i.e., in Rand-$k$-Spatial. \nHence, we believe the transformation function $T$ in Rand-Proj-Spatial, which uses a similar way to address the degrees of correlation in between max and none, should be at least close to optimal.\n\n---------\n\n[1] Divyansh Jhunjhunwala, Ankur Mallick, Advait Harshal Gadhikar, Swanand Kadhe, and Gauri Joshi. ``Leveraging spatial and temporal correlations in sparsified mean estimation.'' In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.\n\n[2] Jakub Konecny and Peter Richtárik. ``Randomized distributed mean estimation: Accuracy vs. communication.'' Frontiers in Applied Mathematics and Statistics, 4:62, 2018."}, {"review_id": "Ttbo81eyPX", "reviewer": "Reviewer_uyDa", "summary": "This work considers the problem of distributed mean estimation, wherein each node in a set of distributed nodes contains a vector, and the goal of the parameter server is to estimate the mean of those vectors. Unlike some other works, no distributional assumption is assumed over the vectors, and the error metric is the mean squared error between the true mean and the estimated mean. Each node sends a compressed version of its vector to the parameter server, and this is the sole source of estimation error. Any randomness in the estimation error arises from the randomness of the compression algorithm used at the nodes. This setup is motivated from distributed optimization / federated learning setups where the mean of the gradients is estimated at the parameter server at every iteration of the optimization algorithm. Since modern machine learning tasks deal with very high dimensional models and gradients, it becomes necessary to compress them before sending it to the parameter server, so as not to overwhelm the communication requirements between nodes and parameter server (which is often a bottleneck).\n\nThis particular work focuses on the effect of correlation between the vectors at different nodes, and considers exploiting this correlation information to design better compressors that achieve a lower mean squared error than correlation-agnostic compressors. Prior work (Jhunjhunwala et. al. (2021)) proposed the **rand-$k$ spatial family** of mean estimators that used correlation information. They did so by first compressing the vector at each node using a rand-$k$ compressor. Rand-$k$ essentially subsamples $k$ coordinates out of a $d$-dimensional vector to get a compressed $k$-dimensional vector, zeroing out the remaining coordinated and yielding a compression factor of $\\frac{d}{k}$. These compressed vectors are transmitted to the parameter server, which then decodes the mean by appropriately scaling the received vectors that ensures an unbiased estimate of the mean. When correlation information is available, the server can decode the received vectors with a different scaling mechanism, yielding a smaller estimation error.\n\nThe primary contribution of this work is a modification of the encoding strategy to incorporate random projections in the encoding step at the clients. Instead of directly applying rand-$k$ to the vector, the vector is first projected on a random subspace (more specifically, the range space of a subsampled randomized Hadamard matrix) and then subsequently rand-$k$ compressor is applied. \n\nFollowing this idea, the authors in this work propose a correlation-aware encoding and decoding strategy for distributed mean estimation under communication constraints, analytically derive upper bounds on the estimation error of their proposed scheme, and finally, numerically evaluate the performance of their scheme relative to existing benchmarks. Please let me know if I have missed anything in my understanding of the contributions of the paper. I would be more than happy to rectify any misunderstandings on my end.", "questions": "I have a few questions and suggestions for the authors, and would highly appreciate if they would take them into consideration. I would be more than happy to re-evaluate my review contingent on their response. The following are some of my concerns:\n\nThe idea of random projection + compression like rand-$k$ is not novel by itself (although it's implications in the presence of correlation as explored in this paper are, to the best of my knowledge). Accordingly, there are some very relevant references missing from the related works section and it would be highly appreciated if the authors included those:\n\n1. R. Saha, M. Pilanci and A. J. Goldsmith, \"Efficient Randomized Subspace Embeddings for Distributed Optimization Under a Communication Budget,\" in IEEE Journal on Selected Areas in Information Theory, vol. 3, no. 2, pp. 183-196, June 2022, doi: 10.1109/JSAIT.2022.3198412 (This work adopts a unified approach for studying the effects of random transforms on compressors -- it poses randomized Hadamard transform as a computationally efficient relaxation of Democratic (Kashin) representations, and also studies rand-$k$ compression (among others) with both kashin + near-kashin -- eventually showing that they attain information-theoretically optimal convergence rates for optimization).\n\n2. Mher Safaryan and others, Uncertainty principle for communication compression in distributed and federated learning and the search for an optimal compressor, Information and Inference: A Journal of the IMA, Volume 11, Issue 2, June 2022, Pages 557–580, https://doi.org/10.1093/imaiai/iaab006 (This work studies a general class of contractive compressors which includes random-projections based compressors -- they focus on Kashin compression and study different variants of accelerated distributed optimization algorithms).\n\nThese properties are not specific to subsampled Randomized Hadamard transforms, -- but extend broadly to the class of randomized matrices that belong to Johnson-Lindenstrauss embeddings and/or follow Restricted Isometry Property (RIP). These results might perhaps be helpful to the authors in deriving bounds on MSE for *rand-proj-spatial* for other classes of matrices (such as random Haar orthonormal). Once again, this is not a critical drawback, but a suggestion that will help place the work better in context with respect to existing literature.", "limitations": "I have some other minor concerns and would be happy if the authors addressed / discussed them:\n\n1. The authors mention on line $138$ *\"Each client also sends a random seed to the server, which conveys the subspace information, and can usually be communicated using a negligible amount of bits.\"* -- Is this really negligible? Can $\\mathbf{G}$ be conveyed between the nodes and server with less than $d$ bits of information? Since each node shares an independently sampled random matrix, can correlation help improve this shared randomness generation?\n\n2. The statement of Theorem 4.3 is a high probability result but the equation (9) holds in expectation -- this is slightly weird. It would be better if the authors stated the result purely as a high probability statement or purely in terms of expectation (the latter might be simpler since the failure probability is $o(1)$). If this is not possible, they should atleast explicitly specify in the statement of the theorem which random variables is the expectation computed over, and which random variables is the high probability bound over? Moreover, $o(1)$ is not explicitly defined -- is it with respect to dimension / number of nodes -- please specify?\n\nIt would also be highly if the authors had a separate limitations sections that discuss these and other concerns raised in *weaknesses* and *questions*, which are my primary concerns. I would be more than happy to re-evaluate my assessment if these concerns are addressed satisfactorily.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The following are the primary contributions of the paper:\n\n1. The authors propose the *rand-proj-spatial* family of mean estimators as a generalization of the previously proposed *rand-$k$-spatial* estimators, that uses subsampled randomized Hadamard transform to first project the vectors onto a random subspace and subsequently apply a rand-$k$ compressor with appropriate decoding at the server.\n\n2. Several numerical experiments on distributed power iteration, distributed $k$-means, and distributed linear regression have been performed to demonstrate the superiority of the proposed strategy over existing correlation-aware and correlation agnostic strategies.\n\nOne of the interesting observations made by the authors is Appendix A.1, which states that applying random projection + rand-$k$ directly to the vectors may not yield any benefit. In other words, if we apply the $\\frac{d}{k}$ scaling individually for each vector with the hope of obtaining an unbiased estimate for each nodes' vector at the server, the expected estimation error is the same as that obtained by rand-$k$ compression without the projection. However, lower MSE can be obtained if the vectors received from each of the nodes are jointly decoded as is done in the *rand-proj-spatial* estimator as proposed in eq. (5) of the paper. At a first glance, this seems a little counter-intuitive since (as the authors point out in the introduction), the motivation to take random projections stems from the idea that random projections equalize the coordinate magnitudes. \n\nHowever, a careful study reveals that when the error metric is the $\\ell_2$-estimation error, random projections do not really help, because the $\\ell_2$-norm of the vectors approximately remains preserved when an orthonormal projection is applied. However, I do believe the benefit will be apparent if other error metrics are considered, such as the $\\ell_{\\infty}$ estimation error (more remarks on why this might be the case in the *limitations* section).", "weaknesses": "I have one critical concern which is the fact that the authors have titled their paper *Correlation Aware Distributed Vector Mean Estimation* as a very generic and broad approach, whereas the contributions of the paper are focused on exploiting correlation for communication compression for a very specific class of rand-$k$ compression strategies, and it is not immediately obvious how this correlation-aware compression strategy can be extended to other classes of compressor such as top-$k$ (instead of rand-$k$), which is a biased compressor -- but is very popular and has been extensively used for distributed optimization / federated learning applications. For example, the paper by Suresh et. al. (2022) (reference [10]) also exploits correlation for quantization purposes. Please note that this is not a drawback or a comment on the technical contributions of the paper. However, the title can be slightly misleading in a sense since the paper does not focus on the benefits of correlation beyond rand-$k$ compression. For instance, correlation can be exploited for client selection, or for designing correlation-aware private mean estimation algorithms. It is my personal opinion and would be highly appreciated if the authors chose a more descriptive title.\n\nIn addition to this, the *rand-proj-spatial* family of estimators proposed in this paper is also a very specific design, and there is no indication if it is the best strategy. In other words, given that our underlying task is communication compression, is *rand-proj-spatial* the best way to exploit correlation? I understand this is not an easy question to answer since lower bounds on the estimation error have not been derived in this paper. However, when authors introduce the optimization problem in eq. (4), it seemed to me that this optimization problem was formulated with a solution in mind -- a solution which is analogous (and a generalization) to the prior work on *rand-$k$ spatial* family of estimators. A natural question to ask here is why the problem was not initially formulated more generally as follows:\n\n$\\hat{\\mathbf{x}} = argmin_{\\mathbf{W}, \\mathbf{x}} \\mathbb{E}\\left\\lVert \\overline{\\mathbf{x}} - \\sum_{i=1}^{n}\\mathbf{W}_i\\mathbf{G}_i\\mathbf{x}_i \\right\\rVert_2^2$\n\nwhere $\\overline{\\mathbf{x}} = \\frac{1}{n}\\sum_{i=1}^{n}\\mathbf{x}_i$, and $\\mathbf{W} = (\\mathbf{W}_1, \\ldots, \\mathbf{W}_n)$ are the individual decoding matrices over which optimization is done as well. Furthermore, one can solve this optimization problem subject to the unbiasedness constraint and potentially come up with a better decoding strategy than the one proposed in this paper? It would be appreciated if the authors discussed how (or under what assumptions) the optimization problem of eq. (4) relates to the this general formulation above, and what are the challenges that prevent one from solving the above general optimization problem directly. Moreover, in the above formulation, the encoding strategy is still the same, i.e., rand-proj + rand-$k$ -- one could also replace the encoding function by a more general class of (potentially biased) contractive compressors (such as top-$k$) and come up with a more very holistic approach to the problem of *correlation aware compression for distributed mean estimation* (which would justify this title).\n\nPlease note once again that this is not a weakness on the technical contributions of the paper as such -- just a suggestion that I genuinely believe would help highlight the contributions of the paper in a better context.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "W1: We indeed had a lot of discussions on the title before the submission. It is hard to give a precise yet succinct title. Other possible title candidates are \"Projection Based Correlation Aware Distributed Vector Mean Estimation\", \"Unbiased Sparsification Induced Distributed Vector Mean Estimation with Correlation\", etc. We are happy to take suggestions from the reviewers.\n\nW2:\nThe proposed optimization problem\nmight need a bit clarification: Where is the variable $\\mathbf{x}$ in the problem?\n\nOne thing to note is that to utilize cross-client correlation information, we need to design a decoding scheme that uses all client's information in decoding. For example, in Rand-$k$-Spatial [1], such cross-client information is the \\# clients who sent the $j$-th coordinate. In our Rand-Proj-Spatial, this information can be thought of encoded in the eigenvalues of random matrices $\\mathbf{G}_i$ each client uses during encoding. Each decoded \n$\\mathbf{x}_i$ is \n$\\mathbf{x}_i = (T(\\sum_{j=1}^{n}\\mathbf{G}_j^T \\mathbf{G}_j))^{\\dag} \\mathbf{G}_i^T\\mathbf{G}_i \\mathbf{x}_i$\n\n, where $\\sum_{j=1}^{n}\\mathbf{G}_j\\mathbf{G}_j^T$ is the cross-client information.\n\nSince the above optimization problem considers a single decoding matrix $\\mathbf{W}_i$ \n\nfor each client, solving this problem might still lead to individual decoding of each client, which does not use potential cross-client correlation information. \nAnother potential form of the optimization problem (Problem 2) we considered is solving \n\n$\\hat{\\mathbf{x}} = \\argmin_{\\mathbf{x}} \\|\\frac{1}{n}\\sum_{i=1}^{n}\\mathbf{G}_i \\mathbf{x}- \\frac{1}{n}\\sum_{i=1}^{n} \\mathbf{G}_i \\mathbf{x}_i\\|_2^2$. \n\nHowever, through simulations, the solution to Problem 2 is consistently worse than the one presented in the paper. \nWe can add the discussion to the Appendix.\n\nQ1: Note both references mentioned here belong to the orthogonal line of work on quantization. See the difference between quantization and sparsification in common response $\\textbf{Quantization vs. Sparsification}$. But we are happy to include the two references in our citation. While random projection + compression and leveraging correlation information across clients are well explored in quantization, these ideas are less explored in sparsification. To the best of our knowledge, the only prior work that explores cross-client correlation is [1]. And as we show in the Appendix A, unlike in quantization, applying a simple rotation in sparsification will not lead to improvement.\n\nAs discussed in Section 4.3 and Appendix B.2, we considered analysis tools such as J-L embeddings but the analysis of SRHT (and other random matrices) in current literature concerns mainly asymptotic properties. Yet, we do need an explicit distribution of the eigen-decomposition of the random matrix in Rand-Proj-Spatial in our case (which does not exist), to derive a tight MSE analysis and to compare against that of Rand-$k$-Spatial and Rand-$k$.\n\nL1: The randomness of $\\mathbf{G}_i = \\frac{1}{\\sqrt{d}}\\mathbf{E}_i \\mathbf{H} \\mathbf{D}_i$ comes from two sources: 1) the subsampling matrix $\\mathbf{E}_i$ and the diagonal matrix $\\mathbf{D}_i$ with Redamacher random variables on the diagonal. $\\mathbf{E}_i$ and $\\mathbf{D}_i$ can both be generated by some pseudorandom function (PRF) and one only needs a seed (aka. a number) to describe the PRF. The length of the seed is related to the strength of pseudorandomness and can be independent of $d$. It is possible to send the seed of the PRF with only a constant number of bits. Since the server and the clients have shared randomness, each client only needs to send an additional constant number of bits to the server so that the server can generate $\\mathbf{E}_i$ and $\\mathbf{D}_i$, and then reconstruct $\\mathbf{G}_i$. \nSee [1], for example, of how such PRF seed is applied in their distributed algorithm. \n\n-----\n\n[1] ``Locally Differentially Private Sparse Vector Aggregation''. Mingxun Zhou, Tianhao Wang, T-H. Hubert Chan, Giulia Fanti, Elaine Shi. IEEE S\\&P 2022."}, {"review_id": "oJWQUj1gEm", "reviewer": "Reviewer_2UxF", "summary": "This paper studies the distributed mean estimation (DME) problem. In particular, the paper proposes a new DME technique called Rand-Proj-Spatial. In  Rand-Proj-Spatial, each client uses SRHT for dimensionality reduction and sends the transformed lower-dimensional vector to the server. The server then recovers the mean estimate by computing a formula derived from an optimization problem designed to minimize the MSE given the client transforms and considering possible correlations among client vectors. Rand-Proj-Spatial is also unbiased, which is desired in the context of DME.\n\nThe main contribution of Rand-Proj-Spatial is that it both improves with increased correlation among client vectors and utilizes SRHT for dimensionality reduction instead of subsampling (like rand-k), achieving lower MSE than previous rand-k-based DME techniques.\n", "questions": "Can the authors address the concerns pointed out in weaknesses (1)-(4)? ", "limitations": "The authors point out a possible direction for future work. I would suggest adding disclaimers about the computational overhead and the asymptotic error-bandwidth tradeoffs compared to existing DME techniques.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe new DME technique improves upon previous rand-k-based DME techniques.\n2.\tThe reconstruction technique is interesting and not symmetric, putting the computational burden on the server.\n3.\tRand-Proj-Spatial leverages possible correlations among client vectors which can be expected and useful in some distributed scenarios.\n", "weaknesses": "1.\tThe worst-case MSE of Rand-Proj-Spatial appears to be $O(d/n)$. Namely, unless $k = \\Theta(d)$, the MSE of Rand-Proj-Spatial grows linearly with the dimension of the problem and may cause an asymptotic increase in the number of required optimization rounds in many (S)GD-based scenarios (e.g., neural network training). \n\n2.\tNo comparison to strong DME baselines, e.g., [1][2][3]: In the paper’s evaluation, the authors consider scenarios with d=1024,  21-51 clients, and k=4-40. These regimes can be readily compared to, e.g., [1][2][3] with 1-2 bits per coordinate. Moreover,  some of these support sub-bit regimes as well.\n    \n3.\tInsufficient evaluation: the evaluation considers low-dimensional (mostly convex) scenarios. It would be more convincing to demonstrate the advantage of Rand-Proj-Spatial over, e.g., neural networks with sufficient dimension and demonstrate that Rand-Proj-Spatial results in better performance than existing DME techniques considering all aspects of the algorithm (i.e., error-to-bandwidth tradeoff and computational overhead). \n\n4.\tThe encoding and decoding time of Rand-Proj-Spatial are not evaluated and compared to previous DME techniques. These times are of major importance in practical scenarios.\n\n[1] Suresh, Ananda Theertha, et al. \"Distributed mean estimation with limited communication.\" International conference on machine learning. PMLR, 2017.\n\n[2] Davies, Peter, et al. \"New Bounds For Distributed Mean Estimation and Variance Reduction.\" International Conference on Learning Representations, 2021.\n\n[3] Vargaftik, Shay, et al. \"Eden: Communication-efficient and robust distributed mean estimation for federated learning.\" International Conference on Machine Learning. PMLR, 2022.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nW1: The worst case MSE of prior works on sparsification techniques, e.g. [1] and [2],\nare also on the order of $O(d/n)$. \nNote we did not claim that our approach improves the asymptotic accuracy bounds. Just like [1], our method focuses on utilizing practically available side information to improve communication cost-estimation accuracy tradeoffs. \n\n------\n\n[1] Divyansh Jhunjhunwala, Ankur Mallick, Advait Harshal Gadhikar, Swanand Kadhe, and Gauri Joshi. ``Leveraging spatial and temporal correlations in sparsified mean estimation''. NeurIPS 2021.\n\n[2] Jakub Konecny and Peter Richtárik. ``Randomized distributed mean estimation: Accuracy vs. communication''. Frontiers in Applied Mathematics and Statistics, 4:62, 2018.\n\n------\n\nW2: \nSee common response $\\textbf{Quantization vs. Sparsification}$.\n\nW3 \\& W4: We included additional results on comparing the encoding and decoding wall-clock time of different estimators (see the pdf attachment in common response). We note our experiment setting mostly follows that of the prior work [1]. One potential way to make the decoding process more efficient is to divide the dimension $d$ into chunks, encode and decode each chunk. This is similar to layer-wise compression of NNs. We found performing Rand-$k$ on NN needs a bit of time to do hyperparameter tuning, or the optimization diverges. We will make the computational time for decoding clearer and stress it as a limitation."}, {"review_id": "IfBV1DIuO3", "reviewer": "Reviewer_R72T", "summary": "The authors propose a compression algorithm that optimizes the accuracy in a setting where each client can send $k+O(1)\\ll d$ values to the server. The algorithm leverages random projections and proposes a way to make the resulting estimate unbiased, which is valuable for DME.", "questions": "* Do you view Rand-Proj-Spatial as being orthogonal to quantization techniques? For example, what would be the impact of quantizing the $k$ values sent by each worker?\n\n* Am I correct to understand that the server's decoding requires $\\Theta(d^2\\cdot k\\cdot n)$ time? If not, what is it?\n\n* You suggest that each client $i$ would use a different projection $G_i$. This may be important for the error, but also requires the server to compute the pinverse of each client's message separately. Instead, consider using a single projection $G$ that all clients use, and thus the server could compute a single pinverse after summing the messages. How would the error bounds change in such an implementation?\n\n", "limitations": "n/a.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "+ DME is an important and well-studied problem, so advances are welcomed.\n\n+ Leveraging correlations between clients' vectors leads to significant improvement in accuracy in some cases.\n\n+ The setting of $n\\cdot k \\ll d$ is challenging and interesting.", "weaknesses": "- The decoding time at the server is not presented, may be prohibitively high in some cases, and must be discussed upfront.\n\n- The authors compare only with Rand-$k$ and Rand-$k$-Spatial. There are other solutions that leverage correlations between clients' vectors (e.g., New Bounds For Distributed Mean Estimation and Variance Reduction, ICLR 2021) and it is unclear to me whether the Rand-$*$ approaches are better or what are the tradeoffs. The authors do not cite the paper or compare with such approaches even qualitatively.\n\n- It is unclear to me that these approaches, in which each client send $k$ floats are better than quantization methods that allow sending, e.g., $32k$ values with one bit each. One example that can use as a comparison point is [33].\n\n- The authors discuss a case where $n\\cdot k \\ll d$; however, probably due to time complexity, even running it for $d \\gg 1$ seems unlikely. The evaluation only shows $d\\le 1024$ and no runtime numbers are provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "W2 \\& W3 \\& Q1: See common response $\\textbf{Quantization vs. Sparsification}$. \n\nW1 \\& W4 \\& Q2: See common response $\\textbf{Computation Time}$. Also, we included additional results on comparing the encoding and decoding wall-clock time of different estimators (see the pdf attachment in common response). We will make the computational time for decoding clearer and stress it as a limitation.\n\nQ3: As we discussed in Appendix A.1, applying the same $\\mathbf{G}$ random projection across the clients does not lead to any improvement of the MSE compared to that of Rand-$k$. The reason is that rotation does not change the $\\ell_2$ norm. \nFurthermore, we note that when $\\mathbf{G_i}$ are different for each client, it is not true that our Rand-Proj-Spatial \"requires the server to compute the p-inverse of each client's message separately\". \nRand-Proj-Spatial only requires the server to compute p-inverse once, i.e., the p-inverse of $\\mathbf{S} = \\sum_{i=1}^{n}\\mathbf{G}_i^T \\mathbf{G}_i$. \n"}]

Author rebuttal:
1. $\textbf{Quantization vs. Sparsification.}$ There are two major techniques to reduce the communication cost of distributed vector mean estimation (DME): vector quantization and sparsification. The two techniques are orthogonal to each other. Vector quantization reduces the number of bits to represent each coordinate while vector sparsification reduces the number of coordinates each client sends. As a result, the communication cost of quantizaation is on the order of $O(d)$, while the communication cost of sparsification is on the order of $O(k)$ for some chosen $k \ll d$. In short, sparsification reduces the communication cost more aggressively compared to quantization. Note Rand-$k$-Spatial and the proposed Rand-Proj-Spatial, fall under sparsification, where the focus of algorithm design is on reducing the number of coordinates, while works mentioned by the reviewers, i.e., [1], [2] ([33] in the draft) and [3], all fall under quantization, where the focus is on reducing number of bits per coordinate. We can definitely include more quantization works to the citation and highlight them as an orthogonal line of works.
In practice, one can apply a combincation of quantization and sparsification techniques to reduce communication cost. Quantizing the $k$ values sent by each worker, for example, further reduces the number of bits per coordinate, while the communication cost remains $O(k)$, and incurs additional communication-accuracy tradeoffs. 
To the best of our knowledge, the SOTA $\textit{unbiased}$ and $\textit{non-adaptive}$ sparsification methods are Rand-$k$ and Rand-$k$-Spatial, which serve as two baselines of our proposed Rand-Proj-Spatial. In the experiments, we also compare Rand-Proj-Spatial against two SOTA $\textit{unbiased}$ and $\textit{adaptive}$ sparsification techniques. 
-----
[1] Peter Davies, Vijaykrishna Gurunathan, Niusha Moshref, Saleh Ashkboos. ``New Bounds For Distributed Mean Estimation and Variance Reduction''. ICLR 2021.

[2] Shay Vargaftik, Ran Ben Basat, Amit Portnoy, Gal Mendelson, Yaniv Ben-Itzhak, Michael Mitzenmacher. ``EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning''. ICML 2022.

[3] Ananda Theertha Suresh, Felix X. Yu, Sanjiv Kumar, H. Brendan McMahan. ``Distributed mean estimation with limited communication.''. ICML 2017.

-----
2. $\textbf{Computation Time. }$
The encoding time of Rand-Proj-Spatial is $O(kd)$. The decoding time is $O(d^2\cdot n\cdot k)$, which is the time to compute the eigen-decomposition of a $d \times d$ matrix $T(\sum_{i=1}^{n} \mathbf{G}_i^T \mathbf{G}_i)$ of rank at most $nk$ and this is the computational bottleneck of the decoding process. In practice, the server has a lot more computational power compare to the clients (e.g., edge devices) and so it can afford to spend more decoding time.
We will make the computation time clearer and stress this as a limitation.

We also attached additional experimental results on the encoding and decoding time for power iteration and linear regression. As one can observe, when the number of clients $n$ is large, the $\textit{adaptive}$ encoder Rand-$k$-Wangni takes a longer time to encode compared to the other $\textit{non-adaptive}$ encoders.

Meta-review: The paper studies the problem of distributed mean estimation and proposes a new estimator called the Rand-Proj-Spatial estimator and demonstrates that the new estimator uses correlation among the vectors effectively. The paper also theoretically analyzes a few special scenarios and shows experimentally that the algorithms work on a variety of datasets. All reviewers like the paper and I recommend acceptance. I encourage authors to incorporate reviewer comments in the final version.
Decision: Accept (poster)