Leveraging Spatial and Temporal Correlations in Sparsified Mean Estimation
Authors: Divyansh Jhunjhunwala
Ankur Mallick
Advait Harshal Gadhikar
Swanand Kadhe
Gauri Joshi
Venue: NeurIPS 2021 Poster (2021)
Keywords: Communication-Efficient Mean Estimation
Vector Sparsification
Distributed Optimization

Abstract: We study the problem of estimating at a central server the mean of a set of vectors distributed across several nodes (one vector per node). When the vectors are high-dimensional, the communication cost of sending entire vectors may be prohibitive, and it may be imperative for them to use sparsification techniques. While most existing work on sparsified mean estimation is agnostic to the characteristics of the data vectors, in many practical applications such as federated learning, there may be spatial correlations (similarities in the vectors sent by different nodes) or temporal correlations (similarities in the data sent by a single node over different iterations of the algorithm) in the data vectors. We leverage these correlations by simply modifying the decoding method used by the server to estimate the mean. We provide an analysis of the resulting estimation error as well as experiments for PCA, K-Means and Logistic Regression, which show that our estimators consistently outperform more sophisticated and expensive sparsification methods.

Leveraging Spatial and Temporal Correlations in Sparsified Mean Estimation
Divyansh Jhunjhunwala Carnegie Mellon University Pittsburgh, PA 15213 d jhunjhuuandrrew. cmu. edu
Ankur Mallick Carnegie Mellon University Pittsburgh, PA 15213 amalli meallic@@andrew cmu edu
Advait Gadhikar
Swanand Kadhe
Carnegic Mellon University Pittsburgh, PA 15213
University of California Berkeley
Berkeley, CA 94720 swanand kadhe@berkeley, edu
agadhika@andrew cmu. edu
Gauri Joshi
Carnegie Mellon University
Pittsburgh, PA 15213 gaurij@andrew cmu edu
Abstract
We study the problem of estimating central server the mean of vectors distributed across several nodes (one vector per node). When the vectors are high- dimensional, the communication cost of sending entire vectors may be prohibitive, and it may be imperative for them to use sparsification techniques. While most existing work on sparsified mean estimation is agnostic the characteristics of the data vectors, in many practical applications such as federated learning, there may be spatial correlations (similarities the vectors sent by different nodes) or temporal correlations (similarities in the data sent by a single node over different iterations the algorithm) in the data vectors. simply modifying the decoding method used by the server estimate the mean. We provide an analysis of the resulting estimation error as well as experiments for PCA, K-Mean and Logistic Regression, which show that estimators consistently outperform more sophisticated and expensive sparsification methods.
leverage these correlations by
Introduction
Estimating the mean of set of vectors collected from distributed system of nodes is subroutine that at the core of many distributed data science applications. For instance, a fusion server performing inference may seek estimate the mean of environmental measurements made by geographically distributed sensor nodes. While inference may be one-shot task, model training is often inherently iterative in nature. For instance, model training using a federated learning framework [19] 35) is
divided into communication rounds, where in each round, the central server has to estimate the mean of model updates or gradients sent by edge clients. Other examples of such iterative methods include principal component analysis (PCA) using the power iteration methods and K-Means.
In most such distributed learning and optimization applications, the nodes sending the data highly resource-constrained and bandwidth. limited edge devices. Hence, sending high-dimensional vectors be prohibitively expensive and slow. A simple yet effective solution to reduce the communication
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

cost is to send a sparsified vector containing only a subset of the elements of the original vector 30]. The Rand-k sparsification scheme chooses a subset of & elements uniformly at random, while the Top-k scheme selects the k highest magnitude indices. Other more advanced schemes such as
34 66 optimize the weights assigned by a node to different elements of its vector when sparsifying
it and sending it to the central server.
common thread in the existing techniques [36] 34 21 is that they are agnostic the fact that in many practical applications, the vectors sent by the nodes are correlated across different nodes and over consecutive rounds of iterative algorithms that use mean estimation as a subroutine. For example, in sensor data fusion applications, sensor nodes in close promixity will make similar environmental measurements and their resulting data vectors will be correlated. In a federated learning application. model updates sent by a node tend to be similar across consecutive communication rounds. The focus of this work to take into account these spatial and temporal correlations when combining sparsified vectors sent by nodes and estimating their mean.
1.1 Main Contributions
In this work, we carefully design the aggregation method used by the central server to estimate the mean of sparsified vectors received from different nodes. This approach does not introduce additional memory requirement
computation at the nodes. As result, our proposed mean estimators are compatible with any sparsification method used by the nodes. For the purpose of this paper and the theoretical analysis of the estimation error. we consider random sparsification at the nodes and focus on unbiased mean estimation. However, other sparsification techniques including Top-k sparsification and the methods proposed in 34 36 can also be used by the nodes, albeit at the cost of additional local computation. Finally, while our goal is to leverage temporal and spatial correlations, we present methods that do not explicitly need information about the correlation; the estimators only consider the fact that such correlation exists. By following this design philosophy of requiring little or no side information and additional local computation, this paper makes the following contributions:
1. Leveraging Spatial Correlation: In random sparsification, a randomly chosen subset of k out of d elements of the vector is sent by node to the central server. The standard approach is for the server to decode via simple averaging of the vectors assuming the missing values to be zero, and scaling with an appropriate constant to get an unbiased mean estimate. Instead, in Section 3 we propose a family of estimators called Rand-k-Spatia that adjust the weights assigned to different vectors according to a parameter that represents the amount of spatial correlation. When the correlation parameter is not known, we propose an average-case estimator that works well in practice.
Leveraging Temporal Correlation: If the vectors sent by a node are similar across iterations, previously sent elements of the vectors can be used to fill in the missing elements of sparsified vector. In Section 4 we build on this idea of leveraging these temporal correlations and propose the Rand-k-Temporal estimator. While estimator requires additional memory at the central server, does not add or change any computation or storage at the nodes, which are more likely to be resource-constrained.
Along with designing these estimators and theoretically analyzing their mean squared error, in Section we present experiments showing that the estimator error can be drastically reduced when there are spatial and temporal correlations.
1.2 Related Work
The problem of coammunication-effciiee mean estimation when the data is distributed across several nodes is considered in [4 13
10 24 Among them, [40 13 7 consider statistical mean estimation assuming i.idd data distribution across nodes. Works [33 10 24 [7] consider empirical mean estimation without assuming any statistical distribution on the data, and quantize the vectors to small number of bits. There is significant recent interest in considering the communication efficient (empirical) mean estimation problem in the context of distributed stochastic gradient descent, see e.g., [1] [2, 12
7 33
4 23 6 14 27]. These works can broadly be partitioned into three categories: (i) Quantization: encoding each element of the vectors to small number of bits [8]
5 37
36
34
20
(ii) Sparsification: sending only subset of elements of the vectors 2 36 (iii) Generic compression operators: defining class of compressors (with specific
1 12 5 37 20
23
27
properties such unbiasedness, bounded variance) that encompass quantization and sparsification as

---

special cases 20 [1]. We focus our attention to sparsification since it is orthogonal to quantization and the two can also be combined, see e.g., 4 To the best of our knowledge, spatial correlation across nodes has not yet been considered in the context of quantized and sparsified mean estimation.
Temporal correlation has been considered in some recent sparsification works [27] 14 and error-
feedback (20, 30]. However, these methods change the sparsification method at the nodes and require additional memory and local computation. In contrast, we only modify the server-side aggregation method. See Section 4 for more details of prior work on exploiting temporal correlation.
2 Problem Formulation
System Model and Notation. We consider a setup consisting of n geographically distributed nodes, and a central server. Each node generates d dimensioon vector x; [ "tal" for i= -,...,, n, where Zij denotes the j element of node i's vector x; Note that we do not assume any specific distribution from which these vectors are generated. Spatial correlations between the vectors in Section 3 are measured using the sum of their inner products. In Section 4 we measure temporal correlations by considering the T22 distance between the vectors sent by node in different iterations. The central server seeks to estimate the mean of these vectors:
X
Σ X
(1)
72
In order to save communication cost, each node sends a sparsified version h, of its data vector x; to the central server. The estimated mean x is function of the hi...., h2 sent by the nodes.
Rand-k Sparsified Mean Estimation. Random sparsification [30] is simple and commonly used way to sparsify vector in order to save communication cost. In the Rand-k scheme, node i selects k elements of x, uniformly random and sends these (along with their position information) to the central node. Thus, the 5th element of the sparsified vector h, is hay Ziz if node i sends coordinate j (with probability k/d) and is otherwise. The central node computes the mean estimate as
d k
x
h 1=1
(2)
The scaling factor & ensures that E [h:] x; and therefore E [X] 8, i.e., the estimate is unbiased. For the purpose of this paper, we will focus on unbiased random sparsification at the nodes. However, our techniques for leveraging spatial and temporal correlations can be applied to biased sparsification methods such as Top-k as well.
Estimation Error Metric. As done in most previous works, measure the quality of the estimator in terms of the mean squared eгror (MSE) E& || x|] where the expectation is taken over the choice of the indices that are retained by each of the nodes when sparsifying their data vectors x,,
see, e.g., (3 12 10). The following result, known in folklore, quantifies error in estimating the true
mean x (proof in Appendix A).
Lemma (Rand-k Estimation Error), The mean squared error (MSE) of estimate produced by the Rand-k sparsification scheme described above is given by
E
-|x-x||?
(d
d
-
R
(3)
n²
where R1= En ||x+|| the sum of the squared magnitudes of the data vectors.
3 Improving Random-k by Leveraging Spatial Correlations
where node i sparsifies its vector x to h, by retaining only is randomly chosen elements and setting the rest to 0, and sends h, to the server. The sampled coordinates are scaled by factor of d/ to get an unbiased estimate of each node vector. However, consider the case where each node has the same vector, i.e., X1 = X2 ... X,- If M, > 0 nodes send their jth coordinate, then the 7th coordinate of the mean be exactly estimated
Consider Rand-k sparsification protocol (described in Section 2)

---

Rand- estimation averages elements, including zeros, and scales with d/ k
Node 1
Node 2
Spursify
3
Node
6
Rand- & Spatial
averuges only elements and scales according correlation
Figure I: To estimate each element of the mean, the standard Rand-k: estimator averages the values received from all nodes, including zeros. Our rand-k-spatial estimator only averages non-zero elements and scales the average according to the degree spatial correlation.
2, -E, hig) On the other hand, the scaling factor of d/k in the Rand-k estimator can introduce a large error depending on the value of M, (e.g., if M, = 1 but d/k 10).
The above example suggests that there are scenarios in which the Rand-k estimator, despite being unbiased, can incur a large MSE. In this section, we will introduce the Rand-k-Spatial family of unbiased mean estimators (illustrated in Fig. T whose members compute mean estimates depending on the amount of correlation between the data at the nodes. We will show that the conventional Rand-k estimator is member of this family and gives the lowest MSE (among the family) only when the data is uncorrelated, while other members of the family can yield lower values of MSE depending upon the level of correlation. We will also describe how to obtain the estimator from this family that minimizes the MSE when the correlation between the data is known and present an estimator that gives lower MSE than Rand-k average when correlations
unknown.
The Rand-I-Spatial family estimators. Let Mj be the number of nodes that send their 7th coordinate. Observe that M, is binomial random variable that takes values in the range (0, 1...., . with Pr(M; m) (m) (1 p)-- for all j. where p k/d. Instead of scaling each element by the constant d/k as in Rand-k (cf. (2)) we propose the Rand-k-Spatie family of estimators wherein the scaling is computed as a function of M, and the level of spatial correlation between the vectors. In particular, propose the following estimate for the jth coordinate of the mean,
1
hij
(4)
T(M))
where B a (5EMj (T(),) 1)- The function T(M,) changes the scaling of hij depending on My. the number of nodes that send the 7th coordinate.
Lemma 2 (Rand-k-Spatie K-Spttial estimator Unbiasedness). Following the definition of 3, we have that the Rand-k SSaatiall estimator in (4) is unbiased, i.e.
E
Fij
(5)
1=1
Observe that the Rand-kk-sttimtor of can be obtained by setting T(M,) = 1 LM, 2 The estimator described the beginning of this Section for the where all the x; vectors identical can be obtained (up to a constant) by setting T(M,) = M, YM, 2 (the constant scaling by 3 is required for unbiasedness). In general, the estimators obtained by the different settings of T T(M;) form the Rand-k- -Saatiala family of estimators.
Our goal now is to find the best estimator from this family for the task of mean estimation. Towards this end, we first evaluate the mean estimation error for members of this family, and then show how the best choice of T TM,)) is function of the amount of spatial correlation.

---

100
1.1
1.0
80
MSE
60
Rt/R:
0.8
....
Rand-k
Rand-k (Max)
Rund-k- Soaii----pptilllaa (vg
0.6
20
Rand-k (ppt)el(OOt.))
0 PENIST TD FXINST Non-lll CIEAR- di CIFAT-I6 Nom-ID
Ra/Ra
Dato Setting
(a)
(h)
Figure 2: (a): MSE v/s R2/ Rí for k/d 0.1 for the Rand-I-Spatial family of estimators. Kand-k-Spatiall Avg) significantly outperforms Rand-k and Rand-I-Spatial(Man
the regime where each is sub-optimal (high and low R2/Ra respectively). while closely tracking performance of the best (unrealistic) estimator Rand Spatial-Opt computed as in (9) with knowledge of Rs/ Ri. (b): Ra/ R& values for single iteration of distributed Power Iteration on FMNIST and CIFAR datasets (IID & non-lID splits) across 100 nodes. Clearly. R2/ Rh is significantly larger than 0 and thus MSE will not be minimized by Rand-k.
Theorem 1 (Rand-k-Spatial Estimation Error). The mean squared error of any member of the Rand-k k- Spatial family is given by
/d n² h
E
| 1
- R1 + n (a - c2
(6)
where R₁
Ei= ||x;
and Ro = 2 23 2j=it1
(x,, x1). The parameters 01, og depend on the
choice T()
C1 = 32
n
b:
m-1
k
d
d (m)
m -
d
d
k
m=1
and
2
n -
2
h
1 nm
=
1
(8)
d2
d
Choosing the best estimator. Comparing (6) with 3 we see that if the data ...... X, and function T() is such that e₂ R2 call, then the MSE of the corresponding estimator the Rand-k-SSptial family is guaranteed to be lower than the Rand-k estimator of Section 2 In general, since the MSE depends on the function (.) through 0 and C22 we can find the T(.) that minimizes the MSE as shown below.
Theorem (Rand-k- -Spatial minimum MSE). For any set of data vectors ,,,...,X,, the ratio R always lies [-1, n 1). and the estimator within the Rand-k spatial family of estimators that minimizes the MSE in 66 can be obtained by setting
R2 m 1
T =
for m 100=1.... ,,...,
(9)
R1 n 1
Thus, the best mean estimator from the Rand-k-family changes as the data (and consequently R1, R₂) changes. We now discuss certain special cases of this.
1. Rand-k (Best when R//Ri 0) The conventional Rand-k estimator (corresponding to T (m) 1. Vm) minimizes the MSE only in special case which is, in fact, the case when Rg = 2 Σx E (x,, x²) 0. natural setting where this could occur is when the node vectors are orthogonal to each other, i.e.. (x,, x,) 0 V [r]]. such cases, can said that the conventional Rand-k estimator is, in fact, the best out of the Rand-k-Spatial family of estimators.
However, when R2/ R * 0, Rand-k not the best estimator, and for each value of R2/ Ri, different estimator (corresponding different value of I" (.)) minimizes the MSE.
5

---

2. Cand-k-Spattia(MMM (Best when R2/R1 = n 1) Recall the example described at the begin- ning of this section where x; = x, Vi,j E [n]. In this case, R2/Re n 1, and T (m) = m, Vm gives the optimal estimator. We will call this the Rand-K-Spatial(Mayy estimator since it corresponds to the maximum value of R2/ Rg. Thus, the optimal estimators are very different when the vectors are uncorrelated as opposed to when the vectors are highly correlated.
Saandd--patia(AAgg) (Best on Average) At this point is quite clear that no single value of T(.) will minimize MSE for all datasets. However, from (9) it is also evident that to derive the best T() we need to know the exact values of R2/ R1 at the central server which does not seem possible without communicating the entire vector at each node (particularly for computing R2) which we wish to avoid. Therefore, we propose the following choice of T()) as default setting, and subsequently show empirically that it does better than either of the above two extremes on average.
1 T(m) 1 + 1ー
(10)
Comparing with ( we see that this is the best estimator when R2/Rt RR - n/2 which is the mid-point of the interval in which R2/ R2 lies (as per Theorem 2. It can also be shown that this minimizes the expectation over MSE if R2/ Rı is distributed uniformly over its range. We will now present simulations to show that this estimator gives close to the best MSE across the entire range of Rg/ R1. and will show in Section 3 that it can outperform -fate-of-the-eee baselines for real distributed mean estimation tasks.
To illustrate the discussion above, we performed mean estimation for n = 10 di0-dimensi vectors using k/d 0.1. Since 10, R2/Ri E [|-1,9] 9] (Theorem D. We vary Ra/Ri over the entire range by starting with 5 all-1 vectors and 5 all-(-1) vectors (Ra R2 - 1) and then changing the signs of the elements (one a time) of the 5 all-(-1) vectors, until they are all- 1 [Ry/R1 = 9). For details, see Appendix B. We plot the MSE of the Rand-k, Rand-k- Sonddd--Sptiil and Rand-k-S Sass-ppaallAvaaa
Simulations.
estimators in Fig. 2a We also add an estimator corresponding to the best T()) as in (9) and call it Saadd--SSpatiall Opt). While knowing R2/Rt R2 at the central server is unrealistic in practice, it illustrates the best-case scenario. In Fig. 2a we see that Rand-k- Landdk-SpptialAAyy is in general quite close to Land---Spptial(OPpp i.e., it works well for all values of Rs! R1, whereas work well only in the special cases where R2/ R = and
Rand-k and Cand-k-Spattal(MMM) R2/ R, 9.
To check if Ra/Ro RR can indeed take large values for which Rand-k would be suboptimal, we consider distributed power iteration which is common protocol that uses distributed mean estimation Mm
The objective of the central server here is to estimate the top eigenvector of a matrix whose rows partitioned among nodes. To simulate this, we partition the FMNIST and CIFAR- 10 datasets among 100 nodes, either in an IID or Non-IID fashion and plot R2/ R2 for the vectors the first round of distributed power iteration on this data. Fig. 2b shows that R2/ R, is significantly larger than 0 in these cases, thus indicating that the data well correlated. The values of R R₁ continue remain large even in subsequent round (see Appendix B), thus justifying the need for using estimators other than the conventional Rand-k each round. In Section 5 we show that the Rand-k- LonndkkSpall --ppatial(Avgg) estimator can outperform Rand-k and various other baselines for distributed power iteration.
R2
4 Improving Random-k by Leveraging Temporal Correlations
iteration
iteration 2
iteration 3
X;
Spunsify
Spursify
Spursify
Server Memory b,
Figure 3: Each node sends its Rand-k sparsified vector to the server. The server stores previously seen coordinates of the vector in its memory and uses it to fill-in unsampled coordinates in future iterations.
Mean estimation is an important subtask in several iterative algorithms such as power iteration and SGD. We propose mean estimation technique that leverages temporal correlations in the vectors

---

x obtained by node i, where is the iteration index of the algorithm. In Rand-k sparsification, each node i samples out of coordinates of its vector x; to create a sparsified vector ( and sends to the server. In standard Rand-k sparsified mean estimation, the d - k unsampled coordinates of xj are treated as 0 by the server when computing the mean estimate (see 22). Instead, we propose to allow the server to substitute the zeros with values from its memory that better represent the unsampled coordinates.
Filling-in Unsampled Coordinates of a Sparsified Vector. Let by b/a by be n vectors stored in the server memory whose elements serve as substitutes for unsampled coordinates of x Since these b are stored at the server, there is no added computation or storage costs at the nodes. These b(d)s can correspond to predicted values of x based on the temporal correlation across iterations. A natural idea is to set b; (t) in iteration to previously sampled coordinates, instead of just
substituting zeros. Based on this intuition, we propose the following strategy for updating by² at the end of iteration t. Let b,") 0 for all E [m]. As illustrated in Fig. update by() for t 2 1 as follows:
(1+1)
if node does not send zij
(11)
(1) if node sends zij
One can further refine this approach by enforcing staleness constraints on b or by setting b, to a sliding window average of previously sampled coordinates.
The Band-k-Tempoon estimator. We now propose the server to get an unbiased estimate of the mean x for any arbitrary stored vectors b; used to fill in the unsampled coordinates of x,. We omit the iteration index here for the purpose of brevity and because this estimator can be used even in non-iterative settings where the server knows a predicted value b, of the vector x,. Given the sparsified vector h, received from node i, the server can fill in the unsampled coordinates and create the vector h whose j-th coordinate is defined as:
estimator that enables the
baj bey ( b1)) big) if node sends Zij
if node does not send Ttj
M3
(12)
By definition, Mi is an unbiased estimate of Tij, because E [ky = (1 16 + (b,s + (
byy)) Zij. Using these filled-in vectors h' obtained from the sparsified vectors h, and the vectors b; stored in server memory, we propose that the server computes the following mean estimate
&
(13)
We see that when b, = for all i, then the Land-k-Tempont estimator reduces to the Rand-k estimator.
Since h1 is an unbiased estimate of x, follows that the proposed mean estimate x is also unbiased, that is E [x] x. In the following theorem, we evaluate the estimation error of this kand-k-Temppor estimator terms of the b,s.
Theorem 3 Rand-k-Teempor Estimation Error). The mean squared error of the Rand-k: T-emporal estimator is given by,
E |1
x|3
1 n²
xx bi1l2
(14)
T
By comparing the above result with the Rand-k estimation error given Lemma [ we see that Rand-k- Bonn---TTepprrll effectively reduces the dependence of the MSE on ||x,|| to ||x, - byll² Thus, the Rand-k-Tempore estimator can significantly reduce the estimation error of the Rand-k estimator when b,s are close x:S, resulting in ||x, b ||x
Reducing Storage Cost at the Server. In the naive implementation of the proposed Rand-k- Temporal estimator, we need (nd) storage/memory at the server store vector b, from each
7

---

10"
10
Moan Estauation Erroe
10-2
10-3
10
10-3
Uncompreseed
Rani
10-5
Rond
10-11
Rund& ((Waggu))
Rund-A(Waaguu)
Compossor (oeviola)
Compossor(Hevvdii
14
Cenr---Temperr
Runs---Teeqpooll
30
150
200
150
200
Beration No.
Heraaion No.
(a)
(b)
Figure 4: Simulated results for our objective defined in 15 where e; (O), n 15 and d = 1000.
We set 0.1 and k/d 0.1. We compare with more sophisticated schemes than Rand-k-Tempon such as CompressorrHoováiii [44 that take into account coordinate magnitude during sparsification. (a) We see that Rand-k-Temport effectively converges the true optima while other
Land-&(Waangee and (36] and Induced
sparsification schemes are unable to do so. (b) The mean estimation error for Rand-k- Temporal decreases sharply as iterations proceed while other sparsification schemes continue to have a high error floor.
device practice, this memory cost can be easily reduced at the expense of a slightly higher MSE, Note that our result in Theorem 3 holds for arbitrary b, and thus the b, do not have to be necessarily different for each device. natural idea to reduce the memory requirement at the server just (d)
is to set b [++1) = (*) for all i E [n], where x()) is the previous mean estimate. Further details and experimental results confirming the effectiveness of this strategy are shown in Appendix
Obbjeriic-Objective Case Study. Even with the simple choice of b, given in (TT. Rand-k- Temporal estimation gives order-wise improvement the over standard Rand-k estimation. We demonstrate this via the following case study of performing gradient descent on quadratic objective. Consider that each node has quadratic local objective function given by Fi(w) ||w ell where e; E Rdd is the local minimum of node i. The local minima are different across nodes due to heterogeneity of their objectives. The goal of the server is to minimize the global objective F(w) given by,
F(w)
F. (w)
w eil which is minimized by w"
e
(15)
7
n
Our simulation result in Fig. 4b shows how the mean estimation error for these node gradients changes as training progresses. For schemes that do not utilize temporal information, we see a non-zero estimation error due to the unsampled coordinates at all steps. effectively allows the mean estimation error of the node vectors to converge to zero, by utilizing previous and current information on all coordinates while decoding. A consequence of this, show in the theorem below, that Rand-k Temmporal converges to the true optima w for a sufficiently small learning rate 77.
on the other hand,
Theorem 4. For our objective defined as in 15) Gradient Descent using the Rand-k- -emmporl
estimator with S min
converges to the true optima w as follows,
(1+ 2d
- w-1l]] - s
E [
(1- w' - Σ [VF((w*))) ?
(16)
where the expectation is taken over the randomness in the sparsification protocol across all steps.
Comparison with Error-Feedbant and Gradient Difference methods: The notion of error feedback 28 31 is considered for compressed gradient methods in 29
20 6 In error-feedback, each node locally stores the difference between the actual and the compressed vector each iteration (known error), and adds to the vector generated at the next iteration (feedback). For Rand-k
30

---

sparsification, error-feedback corresponds to locally storing the unsampled coordinates for each iteration, and adding them back the next iteration. Note that, with error-feedback, the server still utilizes the information on only k coordinates from each client, albeit with accumulated history. On the other hand, Sand-k-Tempora allows the server to leverage temporal correlations by utilizing historical data to substitute for unsampled coordinates. Another line of work [26] 15 22 proposes that nodes quantize the difference of their current gradient and a local state to reduce the variance caused by quantization. Note that similar to crror-feedback, these works require nodes to maintain a local state and perform extra computation to update the local state. This can incur significant overhead for ssoouree-costrringg nodes in many applications such SGD for deep learning models with millions of parameters.
Comparison with r and Induced Compressor: In practice, biased compressors such as Top- are observed to perform better due to their low empirical variance, however error-feedback the only known mechanism to ensure convergence 30 20 6 [4] r'Top-k [3] proposes to first find the top r magnitude coordinates of a vector and then randomly sample ie out of these r coordinates. Note that rTop-k is still a biased compressor and is usually implemented with error feedback. The work of [14] proposes a general mechanism called induced compressor for constructing an unbiased compression operator from any biased compressor such as Top-k. The induced compressor first computes the error between the actual and compressed vector obtained using a biased compressor, compresses the error using unbiased compressor, and sends it along with the compressed vector. Unlike Rand-k- -Temporal, the induced compressor only operates on the vectors for the current iteration, and does not leverage temporal correlations.
seek to utilize temporal correlation to reduce communication. In particular, LAG adaptively skips node-to- server communication by identifying slowly varying gradients, thereby reusing old gradients over time. Unlike Rand-k- Temppral,, LAG is not sparsification scheme and incurs an extra computation cost to determine whether or not a node sends their vector to the server.
Comparison with Lazily Aggregated Gradient (LAG) Methods: LAG methods R 32
5 Experiments
We evaluate our proposed sparsification schemes on the following three tasks: i) Power Iteration, ii) K-Means, and iii) Logistic Regression. In all setups, we compare the performance with Rand-k and the two more sophisticated sparsification schemes, Rand-k (Wangni) (36, and Induced Compressor [4]. We use the code from [16) for both. For the Induced Compressor, we use Top-k with Rand-k as in We present representative results here and defer additional results to Appendix C.
Power Iteration. We estimate the principal eigenvector of the covariance matrix of the data dis- tributed across 100 nodes by the power iteration method. The data consists of images from the Fashion-MNIS, (38) dataset split IID across the nodes. At each iteration, the nodes send a 10x compressed version of their local eigenvector estimates to the server based on a single local power iteration. The server estimates the mean (global eigenvector estimate) and communicates it back to the nodes for the next round. Results in Fig. 5) show that Sand-k-SSpatil(AA (Section[4) 4) significantly outperform all baselines both in terms of convergence to the true eigenvector (Fig. 5a) and in terms of the mean estimation error (Fig. (dd) across iterations.
(Section 3 and
K-Means Clustering. We perform K K-Means clustering (with 10 clusters) using Lloyd's algorithm on Fashion-MNIST images distributed across 100 nodes in IID fashion. Each node computes its local cluster centers and sends a 10x compressed version to the server, which estimates the mean (global centers) and sends it back to the nodes for the next round. Results in Fig. 5b and Fig. 5c show that Rand-A-Sa Aa-Spaiia(AAgg (Section 3) and Rand-k- -Temporrl (Section 4 significantly outperform all baselines both in terms of minimizing the K-Means objective (the average distance to cluster centers) and in terms of the average mean estimation error averaged over the 10 cluster means.
Logistic Regression. We train a logistic regression model for classification of CIFAR-10 images split across 10 nodes in non-lID fashion (following the splitting procedure in (25)). Each node computes local gradients and sends a 100x compressed version to the server, which estimates the mean (global gradient) and sends it back to the nodes for the next round. Results show that Rand-k-Temporn achieves the lowest training loss (Fig. and order-wise lower mean estimation error (Fig. 55) among all sparsification schemes training progresses. We note that Rand-A-Spatio is not able to beat the

---

10
Tead
Bosie
27.3
incoaed Conpenoa (beosts) Seate
25.0
Treppodd
Thin Loon
Road Spatsa/Ang)
10
20.0
Falied Cxppenaniioncal
10
Frad phepoea
10
20
10
10
31
30
Ronckn No.
bentiin No.
Epoch No.
(a) Power Iteration
(b) K-Means
(c) Logistic Regression
201
Meen Extmanten Frree
Moin Betimation
Menn Betmatzon
Telged Beee
201
Tanpel-Thaperl
Ran't (aaaotoo
Reald
lalpall Coaperoon Harotl
Idtend Caapenoni
Real SpuialAoy
30
Banation No.
Basala No.
Dpoch So.
(d) Power Iteration
(e) K-Means
(l) Logistic Regression
Figure S: Experimental Results showing task objective and Mean Estimation Error for Power Iteration (a.d), K-Means (c,c), and Logistic Regression (c,f). hand-k-Temporal outperforms baselines in all cases while Rand-k-SSatial outperforms baselines in 2/3 cases.
baselines here potentially because the non-III split might be reducing spatial correlation. We plan to investigate this further in future work.
Conclusion
We considered the problem of estimating the mean of d-dimensional vectors received from nodes, which sparsify their vectors to k elements in order to reduce the communication cost. When there are spatial correlations across nodes and temporal correlations over time between the vectors, the standard approach of simple averaging the sparsified vectors can lead to high estimation error. We propose the Rand-k-Si --Spttial and
estimators that provably reduce the estimation error while keeping the estimate unbiased and also perform exceptionally well in experiments. Although we focus on Rand-k sparsification here, the insights for leveraging correlations can be extended to other sparsification and compression methods.
Acknowledgments
This research was generously supported part by the NSF Award (CNS-2112471), the NSF CRII Award (CCF-1855))) 1850029), the NSF CAREER Award (CCF-2045694), the NSF MLWINS Award the Qualcomm Innovation fellowship and the CMU Dean't 's fellowship.
References
[1] D. Alistarh. D. Grubic, Li, R. Tomioka, and M. Vojnovic. Qsgd: Communication efficcient sgd via gradient quantization and encoding. In I. Guyon, U. V. Luxburg, S. Bengio. H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL, htR..httpss:/// httptt:ssppppo.oeeddeeee neuriss http:///00./1eeee000000022eeeed.
pdff
[2] D. Alistarh, T. Hoefler, M. Johansson, Konstantinov, S. Khirirat, and C. Renggli. The conver- gence of sparsified gradient methods. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
10

---

[3] L. P. Barnes, H. A. Inan, B. Isik, and A. Özgür. rtop-k: A statistical estimation approach to distributed sgd. IEEE Journal on Selected Areas in Information Theory, 1(3):89-9077, 2020.
[4] D. Basu, D. Data, C. Karakus, and S. Diggavi. Qsparse-local-sgee Distributed sgd with quanti- zation, sparsification and local computations. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[5] J. Bernstein, Y.-X. Wang, K. Azizzadenesheli, and A. Anandkumar. signSGD: Compressed optimisation for non-convex problems. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 560-569. PMLR, 10-15 Jul 2018.
[6] A. Beznosikov, S. Horváth, P. Richtárik, and M. Safaryan. On biased compression for distributed learning. arXiv preprint arXiv:2002.124100 2020.
[7] M. Braverman, A. Garg, I. Ma, H. L. Nguyen, and D. P. Woodruff. Communication lower bounds for statistical estimation problems via a distributed data processing inequality. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing. STOC '1. page 101 1-200 New York, NY, USA, 2016. Association for Computing Machinery. ISBN 978 9781450341325.
[8] Chen, G. Giannakis, T. Sun, and W. Yin. Lag: Lazily aggregated gradient for communication- efficient distributed learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[9] T. Chen, Y. Sun, and W. Yin. Lasg: Lazily aggregated stochastic gradients for communication- efficient distributed learning, arXiv preprint arXiv:2002.11366 2020.
[10] W.-N. Chen, P. Kairouz, and A. Özgür. Breaking the communication wtwpiiicctttiiiiivccceeeeeee accuracy trilemma. arXiv preprint arXiv:2007. 1707, 2020.
[11] Davies, V. Gurunathan, N. Moshrefi, S. Ashkboos, and D. Alistarh. Distributed variance reduction with optimal communication. arXiv preprint arXiv:2002.09966. 092668, 2020.
[12] V. Gandikota, D. Kane, R. K. Maity, and A. Mazumdar. vqsgd: Vector quantized stochastic gradient descent. arXiv preprint 1xXiv:191..0797) 2019.
[13] A. Garg, T. Ma, and H. Nguyen. On communication cost of distributed statistical estimation and dimensionality. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, editors, Advances Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
[14] S. Horváth and P. Richtárik. A better alternative to error feedback for communication-effccieent distributed learning. arXiv preprint arXiv:2006. 1000006..10000 1107,, 2020.
[15] S. Horváth, D. Kovalev, K. Mishchenko, S. Stich, and P. Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. arXiv preprint 154:::100 2019.
[16] S. Horváth. Compressed sgd pytorch, 2020. URL httts:://gtthhiae Sepppressed_SSD_Pyyyee
[17] Z. Huang, Y. WANG, K. Yi, et al. Optimal sparsity-sensitive bounds for distributed mean estimation. Advances in Neural Information Processing Systems, 32:6371-6381, 2019.
[18] D. Jhunjhunwala, A. Gadhikar, G. Joshi, and Y. C. Eldar. Adaptive Quantization of Model Updates for Ceaamunication--ffiiieee Federated Learning. In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing (ICASSP), May 2021.
[19] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji. K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, et al. Advances and open problems federated learning. arXiv preprint 1rXiv:1912.04997, 2019.

---

[20] S. P. Karimireddy, Q. Rebjock, S. Stich, and M. Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3252-3261. PMLR, 09-15 Jun 2019.
[21] J.
Konečný and P. Richtárik. Randomized distributed mean estimation: Accuracy vs. communi- cation. Frontiers in Applied Mathematics and Statistics, 4:62, 2018.
[22] X. Liu, Li, J. Tang, and M. Yan. A double residual compression algorithm for efficient distributed learning. International Conference on Artificial Intelligence and Statistics, pages 133-143, PMLR, 2020.
[23] Mayckar and H. Tyagi. Ratq: A universal Exee-llngth quantizer for stochastic optimization. In S. Chiappa and R. Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 1399-1409. PMLR, 26-28 Aug 2020.
[24] P. Mayekar, A. Theertha Suresh, and H. Tyagi. Wyner-ziv estimators: Efficient distributed mean estimation with side-information. In A. Banerjee and K. Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 3502 3510, 13-15 Apr 2021.
[25] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas. Communication--ffiien learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pages 1273-1282. PMLR, 2017.
[26] K. Mishchenko, E. Gorbunov, M. Takáč, and P. Richtárik. Distributed learning with compressed gradient differences. arXiv preprint 10kiv:9901.099 2019.
[27] E. Ozfatura, K. Ozfatura, and D. Gunduz. Time-correlated sparsification for communication- efficient federated learning, 2021.
[28] Seide, H. Fu, J. Droppo, G. Li, and D. Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns. In Fifleenth Annual Conference of the International Speech Communication Association, 2014.
[29] S. U. Stich and S. P. Karimireddy. The error-feedback framework: Better rates for sgd with delayed gradients and compressed communication. arXiv preprint 1rXiv:1909.05350 2019.
[30] S. U. Stich, J.-B. Cordonnier, and M. Jaggi. Sparsified SGD with memory. In Advances in Neural Information Processing Systems, pages 4447-4458, 2018
[31] N. Strom. Scalable distributed dnn training using commodity gpu cloud computing. In Sixteenth Annual Conference of the International Speech Communication Association. 2015.
[32] J. Sun, T. Chen, G. B. Giannakis, and Z. Yang. Communication-efficienn distributed learning via lazily aggregated quantized gradients. arXiv preprint arXiv:1909.0758. 2019.
[33] A. T. Suresh, X. Y. Felix, S. Kumar, and H. B. McMahan. Distributed mean estimation with limited communication. In International Conference on Machine Learning, pages 33377. PMLR, 2017.
[34] H. Wang, S. Sievert. S. Liu, Z. Charles, D. Papailiopoulos, and S. Wright, Atomo: Communication-efficeen learning via atomic sparsification. Advances in Neural Information Processing Systems, 31:9850-9861. 2018
[35] J. Wang, Z. Charles, Z. Xu, G. Joshi, H. B. McMahan, et al. A field guide to federated optimization, 2021.
[36] J. Wangni, J. Wang J. Liu, and T. Zhang. Gradient sparsification for communication-effin efficccc distributed optimization. Advances in Neural Information Processing Systems, 31:1299-1309, 2018.
12

---

[37] W. Wen, C. Xu, F. Yan, C. Wu, Y. Wang, Y. Chen, and H. Li. Tergradd Ternary gradients reduce communication in distributed deep learning. In I. Guyon, U. V. Luxburg, S. Ben- gio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[38] H. Xiao, K. Rasul, and R. Vollgraf. Fashion-mnin mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07745 2017.
[39] J. Zhang and O. Simeone. Lage: Lazily aggregated gradient coding for straggler-tolerant and communicaiin--fficcent distributed learning. IEEE transactions on neural networks and learning systems, 2020.
[40] Y. Zhang, Duchi, M. I. Jordan, and M. Wainwright. Information-theerrtiee lower bounds for distributed statistical estimation with communication constraints. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
13


Reviews:
[{"review_id": "xI2tmKQMOiz", "reviewer": "Reviewer_6xmC", "summary": "This paper studies the problem of distributed \"Mean Estimation\". Authors provide new insight for the sparsified approach and propose a new method that exploits the data correlation. They show that theoretically, their proposed approach for the special cases of random K outperforms the available technique. Finally, theoretical findings are supported by experiments.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Positive aspects: \n\n- I think the paper is well-written and it is easy to follow.\n- There is some novelty in the way authors try to use the correlation in the data to increase the sparsity of transmitted vectors.\n- Experiments look reasonable. \n\nDownsides:\n\n- While Theorem 2 provides some theoretical insight regarding the connection between data correlation and optimal sparsification scheme, I think the result in the distributed setting is not useful as it depends on the cross product of the date which is not available at the server. So, It is difficult to consider this result as remarkable.\n\n- My major concern about this paper is the additional storage cost required at the server. In essence, the server is iteratively is trying to reconstruct the data at the devices, which has three major issues when it comes to applications such as Federated Learning as pointed out by authors. First, in FL setting there could be a huge number of devices, therefore storing a vector associated with each device could be impractical and also this brings us to the second point that if the server can store as many as vectors why do we need to do this process distributedly. In other words, given this extra storage at the server, devices can send their data and the server can easily take the average. Third (and least importantly), roughly speaking as vectors $b_i$ represents the data point at the server, this could be considered as the violation of data privacy by the server, especially in Federated Learning.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above comments!", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours more or less"}, "extra_text": {}}, {"review_id": "ok10-da6FF6", "reviewer": "Reviewer_3MWC", "summary": "The paper proposes two new sparsification methods for the distributed mean estimation problem. One of the proposed strategies, Rand-k-Spatial, uses the spatial correlation of different nodes to have an unbiased estimator. The other strategy, Rand-k-Temporal, uses the temporal correlation of local vectors at consecutive iterations to fill the sparsified elements without an extra computation or storage cost at the resource-constrained nodes. The authors show that both methods outperform Random-k and Top-k sparsification methods empirically.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I liked the methodology and enjoyed reading the paper. Although the proposed methods might seem incremental upon Random-k, the way authors get use of temporal and spatial correlations to improve Random-k is neat and theoretically sound. I also agree with the authors that the approach is applicable to other sparsification methods as well. Here, I list some more specific comments and questions:\n\n- The paper refers to top-k and random-k frequently and compares the methods' strengths and weaknesses. However, I think they miss a strategy, rTop-k [1], that combines these two methods and enjoys both top-k's and random-k's benefits. \n\n- Although the concept of spatial correlations is not new, temporal correlations have recently started getting attraction. And I like the way how authors benefit from temporal correlations. \n\n- It is interesting that the authors were able to outperform top-k with the modified version of random-k. The discussion on rand-k-temporal and error feedback seems important to me given that many sparsification methods do not perform well without error feedback, hence they suffer from high storage costs at the nodes.\n\n- Do the authors have an explanation as to why rand-k-spatial does not perform well in logistic regression experiments in Figures 5(c,f)? Is this because the data is non-IID for that experiment? Then, does that mean that rand-k-spatial does not work well with non-IID data? If so, then the proposed method is not very useful for practical federated learning settings. Can the authors clarify if I am missing something here?\n\n[1] Barnes, Leighton Pate, et al. \"rTop-k: A statistical estimation approach to distributed SGD.\" IEEE Journal on Selected Areas in Information Theory 1.3 (2020): 897-907.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not mention limitations or the potential negative societal impact of their work. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "KdlwqNFvpa", "reviewer": "Reviewer_vqXw", "summary": "This paper studies the distributed mean estimation problem. In this problem, each node holds a d-dimensional vector and the goal is to compute the mean of all vectors.\nThe communication cost is the resource to be optimized. The authors propose to exploit spatial and temporal correlations in real world data sets to improve the MSE.\nTo do so, a new estimate is proposed and analyzed.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nWeakness:\n1. My main concern is about the estimate (4). The authors claim without proof that it is unbiased. However, it seems that the authors implicitly assume that $M_j$\nis independent of $h_{ij}$. But $M_j$ has non-trivial correlation with $h_{ij}$'s. The same problem happens in the proof of Theorem 1. In the proof, the authors use the law of\ntotal expectation, but for different values of $M_j$, the conditional expectation of $h_{ij}$ are all claimed to be the same, which seems incorrect to me. So the authors should provide\nan explanation on this issue in the rebuttal.\n\n2. The second concern is that the estimate (4) is only for the case when all coordinates are sampled with the same probability. However, the uniform sampling scheme often has much worse MSE than schemes using sampling probabilities that depend on the value of each coordinate, e.g., [1].\n\n3. The motivation to utilize spatial and temporal correlations is valid, however the solution proposed is quite simple (if not straightforward). \nSo I think the technical depth of the paper is below the bar of NeurIPS.\n\nReferences\n[1] D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic. Qsgd: Communication-efficient sgd via gradient quantization and encoding", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "GysF2os277Z", "reviewer": "Reviewer_87xK", "summary": "This paper proposed new estimator that leverages spatial and temporal correlations between vectors in randomized k-sparsified mean estimation procedures. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper proposed new estimator that leverages spatial and temporal correlations between vectors in randomized k-sparsified mean estimation procedures. The presentation is easy to follow, and the ideas are clearly described. The intuition behind the new estimator that utilizes the spatial and temporal correlations is sound under the distriubted learning senario, and the proposed estimator is very simple to understand and implement. Theoretical analysis are presented which clearly show under the strong spatial and temporal correlation cases, the new estimator significantly improves the standard randomized k-sparsified estimator.  Empiricla studies on various datasets and models demonstrated that the proposed technique is a simple and effective way to improve the communication efficiency in distributed learning.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N.A.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "N.A."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies communication efficient estimators for the distributed mean estimation problem. The paper presents two methods that exploit either spatial or temporal correlations of the data, with the goal to improve communication efficiency. The MSE of the two estimators is studied analytically, and numerical benchmarks demonstrate that the proposed techniques can improve the communication efficiency in distributed learning.

The reviewers spotted a few inaccuracies in the proofs, but following the author's response they believe that these issues can be addressed in the final version.

On the one hand, the reviewers emphasized the simplicity of the method, but on the other hand, they found the contribution to be 
slightly incremental. At the end, the good experimental results were the deciding factor in the discussion.

The reviewers believe that this work inspire future work (including attempts to address current limitations regarding practicality in distributed settings) and will be of interest to the community.

The authors are strongly encouraged to take the reviewer's feedback into account when preparing the final version, including the already proposed changes, and perhaps also to include a discussion on lower bounds from an information-theoretic perspective (as guides for follow-up work).
Decision: Accept (Poster)