DRIVE: One-bit Distributed Mean Estimation
Authors: Shay Vargaftik
Ran Ben-Basat
Amit Portnoy
Gal Mendelson
Yaniv Ben-Itzhak
Michael Mitzenmacher
Venue: NeurIPS 2021 Poster (2021)
Keywords: Distributed Mean Estimation
Stochastic Approximation
Federated Learning
Distributed Leaning
Communication Efficiency
Bandwidth Reduction

Abstract: We consider the problem where $n$ clients transmit $d$-dimensional real-valued vectors using $d(1+o(1))$ bits each, in a manner that allows the receiver to approximately reconstruct their mean. Such compression problems naturally arise in distributed and federated learning. We provide novel mathematical results and derive computationally efficient algorithms that are more accurate than previous compression techniques.  We evaluate our methods on a collection of distributed and federated learning tasks, using a variety of datasets, and show a consistent improvement over the state of the art.

DRIVE: One-bit Distributed Mean Estimation
Shay Vargaftik *
Ran Ben Basat
Amit Portnoy *
VMware Research shayv@vmware.c com
University College London
Ben-Gurion University ami tport@post. bgu. ac il
r. benbasat@cs www.ucl...... ac uk
Gal Mendelson Stanford University galmen@stanfore edu
Yaniv Ben-Itzhak
Michael Mitzenmacher
VMware Research
Harvard University mi chaelmeeecs hawvard. edu
ybeni Pbenitzhak@vmwaree
Abstract
We consider the problem where n clients transmit d-dimensional real-valued tors using d(1 + o(1) bits each, in a manner that allows the receiver to approx- imately reconstruct their mean. Such compression problems naturally arise in distributed and federated learning. We provide novel mathematical results and derive computationally efficient algorithms that are more accurate than previous compression techniques. We evaluate our methods on a collection of distributed and federated learning tasks, using a variety of datasets, and show a consistent improvement over the state of the art.
Introduction
In many computational settings, one wishes transmit d-dimensional real-valued vector. For example, in distributed and federated learning scenarios, multiple participants (a.k.a. clients) in distributed SGD send gradients parameters accordingly [1] In these applications and others (e.g.. traditional machine learning methods such K-Means and power iteration (2) or other methods such as geometric monitoring (.), sending approximations of vectors may suffice. Moreover, the vectors' dimension d is often large (e.g., neural networks, can exceed a billion 5 6), so sending compressed vectors is appealing.
parameter server that averages them and updates the model
Indeed, recent works have studied how to send vector approximations using representations that use small number of bits per entry (e.g., 2 g T0 IT). Further, recent work has shown direct training time reduction from compressing the vectors to one bit per coordinate [12). Most relevant to our work solutions that address the distributed mean estimation problem. For example, [ uses the randomized Hadamard transform followed by stochastic quantization (a.k.a. randomized rounding). When each of the n clients transmits ((d) bits, their Normalized Mean Squared Error (NMSE) bounded by O log They also show a O bound with (d) bits via variable-length encoding, albeit at a higher computational cost. The sampling method of (10) yields an O (--R) NMSE bound using d(1 + o(1)) bits in expectation, where r is each coordinate's 's representation length and R is the normalized average variance of the sent vectors. Recently, researchers proposed to Kashin's representation [T] 14]. Broadly speaking, it allows representing a d-dimensional vector in (a X²
higher) dimension À for some
using small coefficients. This results in an O (VX-1)'
NMSE bound, where each client transmits X d(1 + of (()) bits [14]. A recent work (15) suggested an algorithm where if all clients" vectors have pairwise distances of at most E IR (i.c., for any client pair Ci, C,, holds that ((()) FF(ea) 2 y), the resulting MSE is Oly2) (which is tight with respect
Equal Contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

y) using (1) bits per coordinate on average. This solution provides stronger MSE bound when vectors are sufficiently close (and thus y is small) but does not improve the worst-case guarantee.
We step back and focus on approximating d-dimensional vectors using d(1 + o(1) bits (e.g., one bit per dimension and a lower order overhead). We develop novel biased and unbiased compression techniques based on (uniform as well as structured) random rotations in high-dimensional spheres. Intuitively, after a rotation, the coordinates are identically distributed, allowing to estimate each co- ordinate with respect to the resulting distribution. Our algorithms do not require expensive operations, such as variable-lengle encoding or computing the Kashin's 's representation, and are fast and easy im- plement. We obtain an O (H) NMSE bound using d(1 + o(1) bits, regardless of the coordinates' rep- resentation length, improving over previous works. Evaluation results indicate that this translates to consistent improvement over the state of the art in different distributed and federated learning tasks.
2 Problem Formulation and Notation
1b- Vector Estimation. We start by formally defining the 1b- vector estimation problem. A sender, called Buffy, gets a real-valued vector x E IR and sends it using a d(1 + o()) bits message (i.e., asymptotically one bit per coordinate). The receiver, called Angel, uses the message to derive an estimate & of the original vector x. We are interested in the quantity || E| which is the sum of squared errors (SSE), and its expected value, the Mcan Squared Error (MSE). For ease of exposition, we hereafter assume that x * 0 as this special case can be handled with one additional bit. Our goal
-|[1--
is to minimize the vector-NMSE (denoted vNMSE), defined as the normalized MSE, i.c.,
The above problem naturally generalizes to the lb Distributed Mean Estimation problem. Here, we have a set of n N clients and a server. Each client [1...., has its own vector z({) E Rd, which it sends using a d(1 ((1)))))-bbbl message to the server. The server then produces estimate Favg E Rd of the average Zavg Σe_ Zi(e) with the goal of
1b- Distributed Mean Estimation.
minimizing its NMSE, defined as the average estimate's MSE normalized by the average norm of the
clients' original vectors, i.e., B[1
Notation. We use the following notation and definitions throughout the paper: Subscripts. H; denotes the i'th coordinate of the vector x, to distinguish from client c's vector ((e)-
Binary-sign. For a vector x E Rdd we denote its binary-sign function as sign(x), where sign(z), = 1 if 2 0 and sign(x); -1 if < O.
Unit vector. For any (non-zero) real-valued vector x E Rd, we denote its normalized vector by 3 b That is, & and x has the same direction and it holds that ||
Rotation Matrix. A matrix R E Rdxd is rotation matrix if R R = I. The set of all rotation matrices denoted as (d). follows that VR E (d): det(R) 1-1, and Vr RR: ||= ||
Random Rotation. A random rotation R. is a distribution over all random rotations in (d)) For case of exposition, we abuse the notation and given x E Rd denote the random rotation of x by R(x)= Rr, where R is drawn from R. Similarly, R [x) R x R² is the inverse rotation. R-1(()))
Rotation Property. A quantity that determines the guarantees of our algorithms is c ||()) d (note the use of the L1 norm). We show that rotations with high C values yield better estimates.
Shared Randomness. We assume that Buffy and Angel have access to shared randomness, e.g., by agreeing on common PRNG seed. Shared randomness is studied both in communication complexity (e.g., (66) and in communication reduction in machine learning systems (e.g.. 7). In our context, means that Buffy and Angel can generate the same random rotations without communication.
3 The DRIVE Algorithm
We start by presenting DRIVE (Deterministically RoundIng randomly rotated VFctors), novel lb- Vector Estimation algorithm. Later, extend DRIVE to the 1b- Distributed Mcan Estimation

---

Algorithm DRIVE
Buffy:
Angel: 1: Compute R(x) = sign (R(x)).
1: Compute R(x), S.
2: Send (S, (ign)((((())))) Angel.
Estimate R- (R(x)).
problem. In DRIVE, Buffy uses shared randomness sample rotation matrix R R and rotates the vector x Rd by computing R(x) = Rr. Buffy then calculates S, a scalar quantity we explain below. Buffy then sends (S, (ig)()())) to Angel. As we discuss later, sending (S, sign (R()))) requires d(1 o()) bits. In turn, Angel computes R(x) S sign(R(x)) E {-S,+S)* It then uses the shared randomness to generate the same rotation matrix and employs the inverse rotation, i.., estimates 2 R (R(x)). The pseudocode of DRIVE appears in Algorithm
The properties DRIVE depend on the rotation R and the scale parameter S. We consider both uniform rotations, that provide stronger guarantees, and structured rotations that are orders of magnitude faster to compute. As for the scale = S(x, R). its exact formula determines the characteristics of DRIVE's estimate, e.g., having minimal vNMSE or being unbiased. The latter allows us to apply DRIVE to the 1b- Distributed Mean Estimation (Section 4.2) and get an NMSE that decreases proportionally the number of clients.
We now prove a general result on the SSE of DRIVE that applies to any random rotation R and any vector x Rd. In the following sections, we this result to obtain the vNMSE when considering specific rotations and scaling methods as well as analyzing their guarantees.
Theorem 1. The SSE of DRIVE is: || 1ir-fll 21l ||~|1
2 S S [R(x)]] + dd. S².
Proof. The SSE in estimating R(x) using R(x) equals that of estimating using c. Therefore,
|| - 2 2 = RR( 2) = [[(x)) R( = R(x) R(x))
= ||(2z)]12 2 ( R(xx) R(x) R(x) = ||0|| R(x)), R(x)) R(x)
(1)
Next, we have that,
R(x), R(x) - R(x); R(x), = S. Σi= R(x), sign (ign(R(x))) = S S-I((1))l 2
(2)
2 - R(x), = 52
R(x))
(3)
Substituting Eq. and Eq. G3 in Eq. ①I yields the result.
4 DRIVE With a Uniform Random Rotation
We first consider the thoroughly studied uniform random rotation (e.g., 17 18
19 20
21 1. which
we denote by Ry. The sampled matrix is denoted by Ry ~ Ru, that is, Ru appealing property of uniform random rotation is that, show later, it admits scaling that results in a low constant vNMSE even with unbiased estimates.
Rg x. An
4.1 1b Vector Estimation
Using Theorem I we obtain the following result. The result holds for any rotation, including Ru-
Lemma 1. For any x E Rd. DRIVE's SSE is minimized by S R(()] (that is. S
|| is
d
determined after R R is sampled). This yields a vNMSE of R. -[[|=-ajd] E [[(kk,]
Proof. By Theorem T to minimize the SSE we require
2s 2| 2 2 S. [R(x)]] d- s2) -2 [[(x))] + 5 S=
3

---

leading to S | Then, the SSE of DRIVE becomes:
|| 2 = |0:1| S
[[(x))
(1)] || + d S ||=|| 2 - 2. [[)(1 dd. [
||01|2
|
|0l| Ia 1-
( ||>1|2
|
d
- ---91 Co
Thus, the normalized SSE is
Taking expectation yields the result.
Interestingly, for the uniform random rotation, 4e follows the same distribution for all x. This is because, by the definition of Rv, it holds that Rx(#) is distributed uniformly over the unit sphere for any æ. Therefore DRIVE's vNMSE depends only on the dimension d. We next analyze the vNMSE attainable by the best possible S, as given in Lemma[] when the algorithm uses Ry and is not required be unbiased. In particular, we state the following theorem whose proof appears in Appendix A.I (all appendices appear in the Supplementary Material and the extended paper version (22)).
Theorem 2. For any x E Rd, the vNMSE of DRIVE with = [Re((t)) is (1 - 2) (1-
d
4.2 1b Distributed Mean Estimation
An appealing property of DRIVE with a uniform random rotation, established in this section, is that with proper scaling parameter S, the estimate is unbiased. That for any E RR our scale guaran- lees that IE [ x. Unbiasedness is useful when generalizing to the Distributed Mean Estimation problem. Intuitively, when clients send their vectors, any biased algorithm would result in an NMSE that may not decrease with respect to n. For example, if they have the same input vector, the bias would remain after averaging. Instead, an unbiased encoding algorithm has the property that when all clients act (e.g., use different PRNG seeds) independently, the NMSE decreases proportionally to n.
Another useful property of uniform random rotation is that its distribution is unchanged when composed with other rotations. We use in the following theorem's 's proof, given Appendix A.2
Theorem 3. For any E Rd, set S
|
Then DRIVE satisfies B.
T.
Now, we proceed to obtain vNMSE guarantees for DRIVE's unbiased estimate.
Lemma 2. For any x E Rd, DRIVE with S = [Re(=)]]
||
has a vNMSE of
RU.
Proof. By Theorem I the SSE of the algorithm satisfies:
|
||
||0|12 S. |R : æ/11 + S² - ||=11|
Re =/11 +
|R
[Res . will
||
|
= d.
| Ry #1l - || d
| = ||=113
[ - xII
-1)
|
Normalizing by | and taking expectation over Ry concludes the proof.
Our goal is to derive an upper bound on the above expression and thus upper-bound the vNMSE. Most importantly, we show that even though the estimate unbiased and we use only single bit per coordinate, the vNMSE does not increase with the dimension and is bounded by a small constant. In particular, Appendix A.3 we prove the following:
Theorem 4. For any EE R4, the vNMSE of DRIVE with S
|
satisfies:
(R)l
(i) For all d > 2, it is most 2.92. (ii) For all d > 135, it is at most z
(G 12 In d+11
This theorem yields strong bounds on the vNMSE. For example, the vNMSE is lower than for d > 4096 and lower than 0.673 for d > 105. Finally, we obtain the following corollary,
Corollary 1. For any E Rd, the vMMSE tends ~ 0.571 as d 0

---

Recall that DRIVE's above scale S is function of both x and the sampled Ry. An alternative approach is to deterministically set S to |
[[]R As we prove in Appendix A.4 the resulting
scale | (all--d-1)-BBE-
where B is the Beta function. Interestingly, this scale no longer depends on but only on its norm. In the appendix. we also prove that the resulting vNMSE is bounded by f any d. In practice, we find that the benefit marginal.
2d
Finally, with a vNMSE guarantee for the unbiased estimate by DRIVE, we obtain the following key result for the lb- Distributed Mcan Estimation problem. whose proof appears in Appendix [A.5 We note that this result guarantees (c.g., see (23) that distributed SGD, where the participants' gradients are compressed with DRIVE, converges at the same asymptotic rate as without compression.
Theorem 5. Assume clients, each with its vector I(c) E ER. Let each client independently |
sample RU, ~ Ry and set its scale | Then, the server average estimate's 's NMSE
satisfies:
oNMSE T2
where vNMSE is given by Lemma 7 and is bounded by Theorem
To the best of our knowledge, DRIVE the first algorithm with a provable NMSE of O for the 1b Distributed Mean Estimation problem (i.., with d(1 + o(1)) bits). In practice, only + (1) bits to implement DRIVE. We use the d(1 + o(1)) notation to ensure compatibility with the theoretical results; see Appendix B for discussion.
5 Reducing the vNMSE with DRIVE
To reduce the vNMSE further, we introduce the DRIVE* algorithm. In DRIVE*, we also use scale parameter, denoted S+ = S (zx R) to differentiate from the scale S of DRIVE. Here, instead of reconstructing the rotated vector in symmetric manner, i... R(z) S 13
have
that R(x) E S (ci, e2) where CI, are computed using K-Means clustering with K = 2 over the d entries of the rotated vector R(x). That is, C1 C2 are chosen to minimize the SSE over any choice of two values. This does not increase the (asymptotic) time complexity over the random rotations considered in this paper as solving K-Means for the special case of one-dimensional data is deterministically solvable in Old log d) (e.g., (24)). Notice that DRIVE still requires d(l + o()) bits as we communicate (S+ C1, St o2) and single bit per coordinate, indicating its nearest centroid. We defer the pscudocode and analyses of DRIVE to Appendix C We show that with proper scaling, for both the 1b- Vector Estimation and 1b Distributed Mean Estimation problems, DRIVE yields guarantees that are at least as strong as those of DRIVE.
6 DRIVE with a Structured Random Rotation
Uniform random rotation generation usually relies on QR factorization (e.g., see 2.5 which requires Odd²) time and Odd)) space. Therefore, uniform random rotation can only be used in practice to rotate low- oww-dimesionnal vectors. This is impractical for neural network architectures with many millions of parameters. To that end, we continue to analyze DRIVE and DRIVE with the (randomized) Hadamard transform, a.k.a. structured random rotation 2 26 that admits a fast in- place, parallelizable, Odd log d) time implementation 27 29).
We start with few definitions.
Definition 1. The Haish--addmard matrix (l30)) H2* {+1, 1122h1122xxh x2" is recursively defined via: Hzk-1 -Hge-1
Hzh-1 Hy = Hzh-1
and H1= Also, (2 11)===== and det( (2ll) E 1-111
Definition 2. Let Ry denote the rotation matrix HD &Rdxd where H is a Walsh-Haddamadd matrix Jd
and D is a diagonal matrix whose diagonal entries are i.i.d. Rademacher random variables (i.e., taking values uniformly in +1). Then RH(z) RH
D is the . is the inverse transform. randomized Hadamard transform of x and R H (x) = RT x vd
Jall (x1 Dii....,
DH
5

---

6.1 1b- Vector Estimation
Recall that the vNMSE of DRIVE, when minimized using Lemma DT. We now bound this quantity of DRIVE with structured random rotation.
d [ is 1 E
[
(see
Lemma 3. For any dimension d > 2 and vector R the wNMSE of DRIVE with structured
random rotation and scale [R)ll is: 1 - E [ n E
d
Proof. Observe that for all i, E ( = _ 3. Di Dii I. Since D i [d]] are i..d. Rademacher random variables we can use the Khintchine inequality [31 321 which implies that
V2d ||||| < E [ [x)x < v ||æl|2 (see [33 (4] for simplified proofs). We conclude that:
E [ - R ( 2
E [I]
1 (Ex 1= V2d
This bound is sharp since for d > 2 we have that C = 1 for x 42 v2 0, .,......7 0)
Observe that unlike for the uniform random rotation, E. [ depends x. We also note that this bound of 1 applies to DRIVE* + (with scale S = 1) as we show in Appendix C.2
2
6.2 1b- Distributed Mean Estimation
For an arbitrary x E IRd and R. and in particular for Ru, the estimates of DRIVE cannot be made unbiased. For example, for x (G: ()))) we have that sign(Rn (1)) (D11, Dn) and thus
(x)x) = S- (D11, D11)". This implies that 2- RH (R)()) /2 V DD..,) (2-5-
D H-S. (D11, Dn1)²=
O, Therefore, E * x regardless of the scale.
Nevertheless, we next provide evidence for why when the input vector high dimensional and admits finite moments, a structured random rotation performs similarly to uniform random rotation, yielding all the appealing aforementioned properties. Indeed, it is common observation that the distribution of machine learning workloads and, in particular, neural network gradients are governed by such distributions (e.g., lognormal 355 or normal 36 37).
We seek to show that at high dimensions. the distribution of R (1) is sufficiently similar to that of Ry)x). By definition, the distribution of (x) is that of uniformly at random distributed point on a sphere. Previous studies of this distribution for high dimensions (e.g.. [38 (39 40, (T) have shown that individual coordinates of R& (x) converge to the same normal distribution and that these
coordinates are "weakly" dependent in the sense that the joint distribution of every ((1)-sized subset of coordinates similar that of independent normal variables for large
We hereafter assume that & (Z1...., F.). where the I;S are i.i.d. and that E[x]] = o² and B[ p op for all j. We show that R (z); converges to the same normal distribution for all i, Let F (x)) be the cumulative distribution function (CDF) of 1 (- and & be the CDF of the stan- dard normal distribution. The following lemma, proven in Appendix D.I. shows the convergence.
Lemma 4. For all i, R1) converges a normal variable: suPzeR [Fa(()) +(x)
0.409-p
oa/d
With this result, we continue to lay out evidence for the "weak dependency" among the coordinates. We do so by calculating the moments of their joint distribution in increasing subset sizes showing that these moments converge to those of independent normal variables. Previous work has shown that a structured random rotation on vectors with specific distributions results in "weakly dependent" normal variables. This line of research [42 43 44] utilized the Hadamard transform for different purpose. Their goal was develop a computationally cheap method to generate independent normally distributed variables from simpler (e.g., uniform) distributions. We apply their analysis to our setting.
We partially rely on the following observation that the Hadamard matrix satisfies.
Observation (142)) The Hadamard product (coordinate-wir product), H(g Hey two two rows Ho,, Hee, in the Hadamard matrix yields another row at the matrix H o Ha) = H Here, (i 1)@( (e - 1) is the bitwise xor of the (log d'-sized binary representation of 1) and (E- - 1). It follows that - HijHes
Σ Hee))s -iz H1+ (11)0

---

(0,1
Lognormal (0.1)
Exponentio (1)
Empirical NMSE
(n= 10 clients)
0.10
0.10
0.10
0.05
0.05
0.05
0.00
2
2
0.00
2
2
2
0.00
2
2
2
Dimension
Dimension
Dimeusion
DRIVE (Ruslssee)
DRIVE (Kaslomae))
(2/2- 1)/10 0.0771
DRIVE (Uniken)
DRIVE (Unifoem)
Figure I:
Distributed mean estimation comparison: each data point is averaged over 10 trials. In each trial, the same (randomly sampled) vector is sent by 10 clients.
We now analyze the moments of the rotated variables, starting with the following observation. It follows from the sign-symmetry of D and matches the joint distribution of i.i.d. normal variables. Observation 2. All odd moments containing R (2) entries are O. That is, Vige E N. Vii,.... 12q+1 E (I....,d) d) E
RH (a)( 0.
Therefore, need to examine only even moments. We start with showing that the second moments also match with the distribution of independent normal variables.
Lemma 5. For all i it holds that E [R x); (RH x)el O. whereas E [R x) o?.
Proof. Since {Djj 1 (1, (1,...,d)) d)) sign-symmetric and i..d., B[(RH r); (RH x){]
B nd --1 2 12 15) (E)- 1 He E [x}] E Hig Notice that Σ H1j = d
and 2j-1 j-1 Hig = 0 for all > 1. Thus, by Observation we get O if i o and 0² otherwise.
We have established that the coordinates are pairwise uncorrelated. Similar but more involved analysis shows that the same trend continues under the assumption of the existence of z's higher moments. In Appendix [.2 we analyze the 4th moments showing that they indeed approach the 4th moments of independent normal variables with rate of 2; the reader is referred to [42) for further intuition and higher moments analysis. We therefore expect that using DRIVE and DRIVE with Hadamard transform will yield similar results to that of a uniform random rotation at high dimensions and when the input vectors respect the finite moments assumption.
In addition to the theoretical evidence, in Figure [ we show experimental results comparing the mea- sured NMSE for the lb- Distributed Mean Estimation problem with n 10 clients (all given the same vector so biases do not cancel out) for DRIVE and DRIVE+ using both uniform and structured random rotations over three different distributions. The results indicate that all variants yield similar NMSEs in reasonable dimensions, in line with the theoretical guarantee of Corollary [ and Theorem 5
Evaluation
We evaluate DRIVE and DRIVE* comparing them to standard and recent state-of-the oh-thc-art techniques. We consider classic distributed learning tasks as well federated learning tasks (c.g., where the data distribution is not i.i.d. and clients may change over time). All the distributed tasks are implemented over Py 445 and all the federated tasks are implemented over TensorFlow Federated [46]. We focus our comparison on vector quantization algorithms and recent sketching techniques and exclude sparsification methods (e.g.. [47 48 (5)) and methods that involve client-side memory since these can often work in conjunction with our algorithms.
Datasets.
We use MNIST 51 52 EMNIST (53 CIFAR-10 10 and CIFAR-100 [54] for image clas-
sification tasks; a next-character-pue prredictonn task using the Shakespeare dataset (55): and next-word- prediction task using the Stack Overflow dataset [56] Additional details appear in Appendix E.1
Algorithms. Since our focus is on the distributed mean estimation problem and its federated and distributed learning applications,
DRIVE and DRIVE+ with the unbiased scale quantities
We compare against several alternative algorithms: (1) FedAvg I that uses the full vectors (i.e., each coordinate is represented using a 32-bit float); (2) Hadamard transform followed by 1-bit stochastic
7

---

Hadamard
Kashin
Drive
Drive
Drive
Drive
Dimension (d)
+ 1-hit SQ
+ 1-hit SQ
(Uniform)
(Uniform) 0.0547, 40.7
(Hadamard)
(Hadamard)
128
0.5308, 0.34
0.2550, 2.72
0.0567, 40.4
0.0591, 0.36
0.0591, 0.72
8,192
1 1,3338, 0.57
0,3180, 3.42
0.0571, 5088
0.0571, 5101
0.0571, 0.60
0.0571, 1.06
524,288
1454,, 0.79
0.3178, 4.69
0.0571, 0.82
0.0571, 1.35
33,554,432
2.9332, 27.1
0.3179, 332
0.0571,274
0,0571. 37.8
Table 1: Empirical NMSE and average per-vector encoding time (in milliseconds, on an RTX 3090
GPU) for distributed mean estimation with n 10 clients (same as in Figure [ and Lognormal(0.1) 1)
distribution. Each entry is (NMSE, time) tuple and the most accurate result is highlighted in bold.
quantization (SQ) 2 10:: (3) Kashin's 's representation followed by 1-bit stochastic quantization |||
(4) TernGrad [8]. which clips coordinates larger than 2.5 times the standard deviation, then performs 1-bit stochastic quantization on the absolute values and separately sends their signs and the maximum coordinate for scale (we note that TernGradd is a low-bit variant of a well-known algorithm called QSGI) (9), and we use TernGrad since we found it perform better in our experiments) and
(5-6) Sketched-SGD (57) and FetchSGI) (58), which are both count-sketch 55 based algorithms designed for distributed and federated learning, respectively.
We note that Hadamard with 1-bit stochastic quantization is our most fair comparison, as uses the same number of bits as DRIVE (and slightly more than DRIVE) and has similar computational costs. This contrasts with Kashin's ' representation, where both the number of bits and the computational costs are higher. For example, standard TensorFlow Federated implementation (e.g., see "CLASS AAHHHAAADDAARREENOODAA CTOINSSSAEE hyperparameters at [60]) uses a minimum of 1.17 bits per coordinate, and three iterations of the algorithm resulting in five Hadamard transforms for each vector. Also, note that TemnGad uses an extra bit per coordinate for sending the sign. Moreover, the clipping performed by TemnGrad is heuristic procedure, which is orthogonal to work.
For each task, we use subset of datasets and the most relevant competition. Detailed configuration information and additional results appear in Appendix L We first evaluate the vNMSE-Speed tradeoffss and then proceed to federated and distributed learning experiments.
Appearing in Table the results show that our algorithms offer the lowest NMSE and that the gap increases with the dimension. As expected, DRIVE and DRIVE* with uniform rotation are more accurate for small dimensions but are significantly slower. Similarly, DRIVE is as accurate as DRIVE* and both are significantly more accurate than Kashin (by factor of 4.4x-555xx ) and Hadamard (9.3 x-3x-51x x) with stochastic quantization. Additionally, DRIVE is 5.7x-12x faster than Kashin and about as fast Hadamard. In Appendix F.33 discuss the results, give the complete experiment specification, and provide measurements on a commodity machine.
vNMSE-Speed Tradeoff.
We note that the above techniques, including DRIVE, more computationally expensive than linear- time solutions like TemGrad. Nevertheless, DRIVE's s computational overhead becomes insignificant for modern learning tasks. For example, our measurements suggest that it can take 470 ms for computing the gradient on a ResNet18 architecture (for CIFAR 100, batch size = 128, using NVIDIA GeForeeGTX 1060 (6GB) GPU) while the encoding of DRIVE (Hadamard) takes 2.8 ms. That is, the overall computation time is only increased by 0.6% while the error reduces significantly. Taking the transmission and model update times into consideration would reduce the importance of the compression time further.
Federated Learning, We evaluate over four tasks: (1) EMNIST over customized CNN architec- ture with two convolutional layers with * 1 1.2M parameters 61: (2) CIFAR-100 over ResNet- 18 (54) : (3) a mect-chaaacter-pp predicccrrreiiiiinnnn task using the Shakespeare dataset M (4) next--wor--peeiccte using the Stack Overflow dataset [62]. Both (3) and (4) use LSTM recurrent models (63] with 820K
task
and x4M parameters, respectively. We use code, client partitioning, models, hyperparameters, and
validation metrics from the federated learning benchmark of 62
For DRIVE the scale
| ||<[ع
(see Theorem For DRIVE the scale is S+
||
where T
E (c1, ca3" the vector indicating the nearest centroid to each coordinate in R(x) (see Section "When restricted to two quantization levels, TemGrad is identical to QSGD's max normalization variant with clipping (slightly better due the ability represent 0).
5.
8

---

CIFAR-100 100
EMNIST
Shakespeare
Stack Overfoow
Accuracy
.85
225
.75
.25
.42
2000
4000
6000
500
1000
1500
400
800
1200
500
1000
1500
Aceuracy
848
.555
48
815
555
244
.46
882
545
3060
1480
1500
1100
1180
1200
1460
1500
FedAvg (32-bit floats)
TernGrad
FetchSGD
Hadamard 1-bit SQ
Kashin + 1-bit SQ
Drive (Hadamaed)
Drive" (Hadamard)
Figure 2: Accuracy per round various federated learning tasks. Smoothing is done using rolling mean with a window size of 150. The second row zooms-in on the last 50 rounds.
CIFAR-10
CIFAR-10-
CIFAR-100
100
1.0
75
Accuravy
75-
89
85
25
150
200
150
125
200
250
Mini-batch. SGD (32-bit Bootss)
Tennrad
Slotched-SGD
Hodamard 1-bit SQ
Kushin + 1-bit 9Q
Drive (Hadsmard)
Drive (Hedamard)
Figure 3: Accuracy per round distributed learning tasks, with zoom-in on the last 50 rounds.
The results are depicted in Figure 2
We observe that in all tasks, DRIVE and DRIVE* have accuracy that is competitive with that of the baseline, FedAvg. In CIFAR-101 100, TernGra and DRIVE provide the best accuracy. For the other tasks, DRIVE and DRIVE* have the best ac- euracy, while the best alternative is either Kashin 1-bit SQ TemGGad, depending task. Hadamard + 1-bit SQ, which is the most similar to our algorithms (in terms of both band- width and compute). provides lower accuracy in all tasks, Additional details and hyperparameter configurations are presented in Appendix E.4
the
Distributed CNN Training. We evaluate distributed CNN training with clients in two con- figurations: (1) CIFAR-10 dataset with ResNet-9; (2) CIFAR-100 with ResNet-18 18
[54 64]. In both
tasks, DRIVE and DRIVE* have similar accuracy to FedAvg. closely followed by Kashin + 1-bit SQ. The other algorithms are less accurate, with Hadamard + 1-bit SQ being better than Seetched-SGD and TernGrad for both tasks. Additional details and hyperparameter configurations are presented in Figure depicts the results.
Appendix
E.5
Evaluation Summary. Overall, it is evident that DRIVE and DRIVE+ consistently offer markedly favorable results in comparison the alternatives in our setting. Kashin's representation appears to offer the best competition. albeit at somewhat higher computational complexity and band- width requirements. The lesser performance of the sketch-based techniques attributed to the high noise of the sketch under such a low number of counters they can use is too low, making too many coordinates map into each counter. In Appendix E.6 we also compare DRIVE and DRIVE* to state of the art techniques over K-Means and Power Iteration tasks for 10, 100, and 1000 clients, yielding similar trends.
bits) communication requirement. This is because the
Discussion
Proven Error Bounds. We summarize the proven error bounds Table 2 Since DRIVE (Hadamard) is generally not unbiased (as discussed in Section 6.2). we cannot establish formal guar- antee for the 1b DME problem when using Hadamard. It is challenging research question whether there exists other structured rotations with low computational complexity and stronger guarantees.

---

Scale
Rolation
Problem
9
Uniform
Hadamard
lb VE
R
vNMSE
(1 - (1- 5)
vNMSE
lb. DME
NMSE & f. 2.922 d 3x
135
NMSE &
(6r"-12e")
Table 2: Summary of the proven error bounds for DRIVE.
Input Distribution Assumption. The distributed mean estimation analysis of our Hadamard- based variants is based on assumption (Section 6.2 about the vector distributions. While machine learning workloads, and DNN gradients in particular (e.g., 355 36 37), were observed to follow such distributions, this assumption may not hold for other applications.
For such cases, we note that DRIVE is compatible with the error feedback (EF) mechanism 65 66 that ensured convergence and recovery of the convergence rate of con-compressed SGD. Specifically,
as evident by Lemma 3 any scale |R(x)]] & S < 2- [R(x) is sufficient to respect the compressor (i.e., bounded variance) assumption. For completeness. in Appendix [E.2] we perform EF experiments comparing DRIVE and DRIVE* + to other compression techniques that use EF.
Varying Communication Budget. with more than one bit per coordinate are not established. It is thus an interesting future work to extend DRIVE to other communication budgets and understand what are the resulting guarantees. We refer the reader to (67 for initial steps towards that direction.
Unlike some previous works, our algorithms' guarantees
Entropy Encoding. Entropy encoding methods (such as Huffman coding) can further compress vectors of values when the values are not uniformly distributed. We have compared DRIVE against stochastic quantization methods using entropy encoding for the challenging setting for DRIVE where all vectors are the same (see Table 1 for further description). The results appear in Appendix E.7] where DRIVE still outperforms these methods. We also note that, when computation allows and when using DRIVE with multiple bits per entry, DRIVE can also be enhanced by entropy encoding techniques. We describe some initial results for this setting in (67].
When the data is highly sparse, skewed, otherwise structured, can leverage that for compression. We note that some techniques that exploit sparsity or structure can be in conjunction with our techniques. For example, one may transmit only non-zero entries Top-K entries while compressing these using DRIVE to reduce communication overhead even further.
Structured Data.
Compatibility With Distributed All-Reduce Techniques. Quantization techniques, including DRIVE, may introduce overheads in the context of All-Reduce (depending on the network architecture and communication patterns). In particular, if every node in a cluster uses different rotation, DRIVE will not allow for efficient in-path aggregation without decoding the vectors. Further, the computational overhead of the receiver increases by a log factor each vector has be decoded separately before an average can be computed. It is an interesting future direction for DRIVE to understand how to minimize such potential overheads. For example, one can consider bucketizing co-located workers and apply DRIVE's quantization only for cross-rack traffic.
9 Conclusions
In this paper, we studied the vector and distributed mean estimation problems. These problems are applicable distributed and federated learning. where clients communicate real-valued vectors (c.g.. gradients) to server for averaging. To the best of our knowledge, our algorithms are the first with a provable error of O( ]) for the 1b Distributed Mean Estimation problem (i.e., with d(1 + o(1) bits). As shown in 14]. any algorithm that uses ( shared random bits (e.g., our Hadamard based variant) has vNMSE of (2(1), i.e.. DRIVE and DRIVE+ are asymptotically optimal; additional discussion is given in Appendix F Our experiments, carried over various tasks and datasets, indicate that our algorithms improve over the state of the art. All the results presented in this paper are fully reproducible by our source code, available at 29
10

---

Acknowledgments and Disclosure of Funding
MM was supported in part by NSF grants CCF-2101 140, CCF-2107078, CCF-1563710, and DMS- 2023528. MM and RBB were supported in part by gift to the Center for Research on Computation and Society Harvard University. AP was supported in part by the Cyber Security Research Center at Ben-Gurion University of the Negev. We thank Moshe Gabel, Mahmood Sharif, Yuval Filmus and, the anonymous reviewers for helpful comments and suggestions.
References
[1] H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-Effiiiee Learning of Deep Networks from Decentralized Data. In Artificial Intelligence and Statiticcs, pages 1273-1282, 2017.
[2] 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.
[3] Yuval Alfassi, Moshe Gabel, Gal Yehuda, and Daniel Keren. A Distance-Based Scheme for Reducing Bandwidth in Distributed Geometric Monitoring. In 2021 IEEE 37th International Conference Data Engineering (ICDE), 2021.
[4] Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc' aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, Quoe Le, and Andrew Ng. Large Scale Distributed Deep Networks. In F. Pereira, J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
[5] Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro. Megatron-lm: Training multi-billion parameter language models using model parallelism. arXiv preprint arXiv: 080533, 2019.
[6] Yanping Huang, Youlong Cheng, Ankur Bapna, Orhan Firat, Dehao Chen, Mia Chen, Hy- oukJoong Lee, Jiquan Ngiam, Quoc V Le. Yonghui Wu, and zhifeng Chen. GPipe: Efficient Training of Giant Neural Networks using Pipeline Parallelism. 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.
[7] Ran Ben-Basat, Michael Mitzenmacher, and Shay Vargaftik. How to Send a Real Number Using a Single Bit (and Some Shared Randomness). arXiv preprint arXiv:2010.02331, 2020.
[8] Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. TernGrad: Ternary Gradients Reduce Communication in Distributed Deep Learning. In Advances in neural information processing systems, pages 1509-1519, 2017.
[9] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communictionn-Eficicnn Sgd via Gradient Quantization and Encoding. Advances in Neu- ral Information Processing Systems, 30: 1e.1979-122) 1720, 2017.
[10] Jakub Konečný and Peter Richtárik. Randomized Distributed Mean Estimation: Accuracy vs. Communication. Frontiers in Applied Mathematics and Statistics, 4:62, 2018.
[11] Sebastian Caldas, Jakub Konečný, H Brendan McMahan, and Ameet Talwalkar. Expanding the Reach Federated Learning by Reducing Client Resource Requirements. arXiv preprint arXiv:1812.072101 2018.
[12] Youhui Bai, Cheng Li, Quan Zhou, Jun Yi, Ping Gong, Feng Yan, Ruichuan Chen, and Yinlong
Xu. Gradient compression supercharged herf--pero data parallel dnn training. In The 28th ACM Symposium on Operating Systems Principles (SOSP 2021), 2021.
[13] Yurii Lyubarskii and Roman Vershynin. Uncertainty Principles and Vector Quantization. IEEE Transactions on Information Theory, 56(7))3911-33000 2010.

---

[14] Mher Safaryan, Egor Shulgin, and Peter Richtárik. Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressor. arXiv preprini arXiv:2002.08955. 2020.
[15] Peter Davies, Vijaykrishna Gurunanthan, Niusha Moshrefi, Saleh Ashkboos, and Dan Alistarh. New Bounds For Distributed Mean Estimation and Variance Reduction. In International Conference on Learning Representations, 2021.
[16] Ilan Newman, Private vs. Common Random Bits in Communication Complexity. Information processing letters, 39(2):67-71, 1991.
[17] Francesco Mezzadri. How to Generate Random Matrices From the Classical Compact Groups. arXiv preprint mathh-ph/00090000 2006.
[18] RWM Wedderburn. Generating Random Rotations. Research Report, 1975.
[19] Richard M Heiberger. Generation of Random Orthogonal Matrices. Journal of the Royal Statistical Society: Series C (Applied Statistics), 27(2):199-200 206, 1978.
[20] Gilbert W Stewart. The Efficient Generation of Random Orthogonal Matrices With an Applica- tion Condition Estimators. SIAM Journal Numerical Analysis, 1733):03-409, 1980.
[21] Martin Tanner and Ronald A Thisted. Remark as r42: A Remark on as 127. Generation of Random Orthogonal Matrices. Journal of the Royal Statistical Society. Series C (Applied Statistics), 3102):190-19,, 1982.
[22] Shay Vargaftik, Ran Ben Basat, Amit Portnoy, Gal Mendelson, Yaniv Ben- Ben-kizhak, and Michael Mitzenmacher. Drive: One-bit distributed mean estimation. arXiv preprint arXiv:2105.08339 2021.
[23] Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. arXiv preprint 224.: 2020.
[24] Allan Grønlund, Kasper Green Larsen, Alexander Mathiasen, Jesper Sindahl Nielsen, Stefan Schneider, and Mingzhou Song. Fast Exact K- K-Means, K-Medians and Bregman Divergence Clustering in ID. arXiv preprint arXiv:1701.07204 2017.
[25] Mario Lezcano Casado. Geo'Trrch's Documentation. A Library for Constrained Optimization and Manifold Optimization for Deep Learning in Pytorch. https://geotoroee rew.thhdossa
html 2021. accessed 17-May-21.
[26] Nir Ailon and Bernard Chazelle. The Fast Nearest Neighbors. SIAM Journal on computing, 39(1) ((11))3322322) 2009.
Transform and Approximate
[27] Bernard J. Fino and V. Ralph Algazi. Unified matrix treatment of the fast transform. IEEE Transactions on Computers, 25(11):1142-1146, 1976.
[28] Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason Yosinski. Measuring the intrinsic dimension of objective landscapes. In International Conference on Learning Representations, 2018. Code available at: https::/// htttp:://githut http:////..aaaccco/o/eeeeeaaeaaa wttp://caainnniiiiiiieeeeeeeeeee
[29] Shay Vargaftik, Ran Ben Basat, Amit Portnoy, Gal Mendelson, Yaniv Ben-Itzhak, and Michael Mitzenmacher. DRIVE open source code. https://githu/ com/ /mmttort/////////////// DiWVE--Onebit-tet -i-----tttttbuteeddeeeei Mean Estimation 2021.
[30] Kathy J Horadam. Hadamard Matrices and Their Applications. Princeton university press, 2012.
[31] Alcksandr Khintchine. Über Dyadische Brüche. Mathematische Zeitschrift, 18(1):109-116. 1923.
[32] Szarek. On the Best Constants in the Khinchin Inequality. Studia Mathematica, 1958):197- 208, 1976.
12

---

[33] Yuval Filmus. Khintch using Fourier Analysis. Posted at http: // www. cs. toronto. edu/ yuvalf/ KK. pdf 2012.
[34] Rafal Latala and Krzysztof Oleszkiewicz. On the Best Constant In the Chinchin-Kahang Inequality, Studia Mathematicu, 109 109(1)101--14, 1994.
[35] Brian Chmiel, Liad Ben-Uri, Moran Shkolnik, Elad Hoffer, Ron Banner, and Daniel Soudry. Neural Gradients Are Near- Logroroog:::m::: Improved Quantized and Sparse Training. arXiv preprint arXiv:2006.081 08100 2020.
[36] Ron Banner, Yury Nahshan, Elad Hoffer, and Daniel Soudry. Post-Training 4-Bit Quantization of Convolution Networks for Hapid-Deployment. arXiv preprint (rXXiv:81000572:: 2018.
[37] Xucheng Ye, Pengcheng Dai, Junyu Luo, Xin Guo, Yingjie Qi, Jianlei Yang, and Yiran Chen. Accelerating CNN Training by Pruning Activation Gradients. In European Conference on Computer Vision, pages 322-338. Springer, 2020.
[38] Marcus Spruill et al. Asymptotic Distribution of Coordinates on High Dimensional Spheres. Electronic communications in probability, 12:234-247, 2007.
[39] Persi Diaconis and David Freedman. A Dozen de Finetti-Styy -tyll Results in Search of a Theory. In Annales de I'IHP Probabilités et statistiques, volume 23, pages 397-423, 1987.
[40] Svetlozar T Rachev, L Ruschendorf, et al. Approximate Independence of Distributions Spheres and Their Stability Properties. The Annals of Probability, 19(3):1311-133) 1991.
[41] Adriaan J Stam. Limit Theorems for Uniform Distributions Spheres in High- high-Dimensional Euclidean Spaces. Journal of Applied probability, 19(1):221-228 1982.
[42] Charles M Rader. A New Method of Generating Gaussian Random Variables by Computer. Technical report, Massachusetts Institute of Technology, Lincoln Lab, 1969.
[43] David B Thomas. Parallel Generation of Gaussian Random Numbers Using the Hable-Hadamard Transform. In 2013 IEEE 2 Ist Annual International Symposium on Field- Wield-Programmabl Custom Computing Machines, pages 161-168. IEEE, 2013.
[44] Tamás Herendi, Thomas Siegl, and Robert F Tichy. Fast Gaussian Random Number Generation Using Linear Transformations. Computing, 59(2):163-18)) 1997.
[45] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito,, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style, TiighPerffrmancee Deep Learning Library. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8026-8033 8037. Curran Associates, Inc., 2019.
[46] Google. TensorFlow Federated: Machine Learning on Decentralized Data. https://ww //www tensorflow org/ org/federated 2020. accessed 25-Mar-20.
[47] Jakub Konečný, H. Brendan McMahan, Felix X. Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated Learning: Strategies for Improving Communication Efficiency, 2017.
[48] Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary B. Charles, Dimitris S. Papailiopoulos, and Stephen Wright. ATOMO: Communication-efficinn Learning via Atomic Sparsification. In NewrIPS, pages 9872-9883, 2018.
[49] Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. PowerSGD: Practical Low-Rank Gra- dient Compression for Distributed Optimization. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 32, 2019.
13

---

[50] Sebastian U Stich. Jean- Caan-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with Memory. 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.
[51] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-Based Learning Applied to Document Recognition. Proceedings of the IEEE, 86(1 1):2278-2324, 1998.
[52] Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online Available: hllp://yann. www.ll com.exdb/miisst 2, 2010.
[53] Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. EMNIST: Extending
MNIST Handwritten Letters. In 2017 International Joint Conference on Neural Nerworks (IJCNN), pages 2921-2926. IEEE, 2017.
[54] Alex Krizhevsky, Geoffrey Hinton, al. Learning Multiple Layers of Features From Tiny Images. 2009.
[55] William Shakespeare. The Complete Works of William Shakespeare.
https://ww/ www
gutenberg..rg//book.... 1rbe///s/00//00
[56] Stack Overflow Data. htttss//ww..kaggll..c/m/ttttttts hag.gla...o/gttaoooooee/////otto cessed 01-Mar-21.
ac-
[57] Nikita Iykin, Daniel Rothchild, Enayat Ullah, Vladimir Braverman, Ion Stoica, and Ra- man Arora. Caamuuication-Efficieen Distributed Sgd With Sketching. arXiv preprint NEII::1903.044888 2019.
[58] Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, Ion Stoica. Vladimir Braverman, Joseph Gonzalez, and Raman Arora. FetchSGD: Communication-Efion Federated Learning With Sketching. In International Conference on Machine Learning, pages 8253 8265. PMLR, 2020.
[59] Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items data streams. In International Colloquium on Automata, Languages, and Programming, pages 693-703. Springer, 2002.
[60] The TensorFlow Authors. TensorFlow Federated: Compression via Kashin's rersssaanttoooo from Hadamard transform. http:://tttt...oooooooo////////t 63377fffe0077ff33366666666666660 cessed 16-May-21.
ac-
[61] Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H. Brendan McMahan, Virginia Smith, and Ameet Talwalkar. LEAF: A Benchmark for Federated Settings, 2019.
[62] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H. Brendan McMahan. Adaptive Federated Optimization, 2020.
[63] S. Hochreiter and J. Schmidhuber. Long Short-Teri Memory. Neural Computation, 9:1735- 1780, 1997.
[64] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition. pages 770-778, 2016.
[65] Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-Bit Stochastic Gradient Descent and Its Application to DatalParallel Distributed Training of Speech DNNs. In Fifteenth Annual Conference of the International Speech Communication Association, 2014.
[66] Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error Feedback Fixes SignSGD and other Gradient Compression Schemes. International Conference on Machine Learning, pages 3252-3261, 2019.
14

---

[67] Shay Vargaftik, Ran Ben Basat, Amit Portnoy, Gal Mendelson, Yaniv Sen-Itzhak, and Michael Mitzenmacher. Communication -ifirccttinnfiiienttt federated learning via robust distributed mean estima- tion. arXiv preprint arXiv: 108.00000000 088482 2021.
[68] Mervin E Muller. A Note Method for Generating Points Uniformly N-Dimensional Spheres. Communications of the ACM, 2(4):19-25 2020, 1959.
[69] George Bennett. Probability Inequalities for the Sum of Independent Random Variables. Journal of the American Statistical Association, 57(297):33 45, 1962.
[70] Andreas Maurer et al. A Bound on the Deviation Probability for Sums of Non-Negative Random Variables. J. Inequalities in Pure and Applied Mathematics, 4(1):15, 2003.
[71] Pawel J Szablowski. Uniform Distributions on Spheres in Finite Dimensional La and Their Generalizations. Journal of multivariate analysis, 64(2):103-117, 1998.
[72] Carl-Gustav Esseen. A Moment Inequality With an Application to the Central Limit Theorem. Scandinavian Actuarial Journal, 1956(2):100-170, 1956.
[73] Google. TensorFlow Model Optimization Toolkit. optimization 2021. accessed 19-Mar-21.
[74] Apache license, version 2.0. cessed 19-Mar-21.
http:///ww..ppaaaooroo/leeeeeeee ac-
[75] Pytorch license.
Bacc5996644077752277777788888812 accessed 19-Mar-21.
[76] Creative Commons Attriuttionniiiibbaaatte Alike 3.0 license.
org/
Licenses/by-sa3..0 0/| accessed -1-Mar-21.
[77] The TensorFlow Authors.
http:://ggttubb.oooo/ooooooooo/t TensorFlow Federated: EncodedSumFaattoy class.
19. wttp:///www.....///ooooooooo.o
freeectt///yyooo/ggggggooorrrrrr pttp://oooddddd...d-0------0 accessed 19-May-21.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 9
(c) Did you discuss any potential negative societal impacts of your work? [No] We do not believe there is an inherit negative societal impact in this work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material as URL)? [Yes] In the Supplemental Material. will be released as open-source after publication.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] see Section and Appendix E
(c) Did you report error bars (e.g., with respect to random seed after running experi- ments multiple times)? [No] Most experiments can be easily reproduced but require considerable execution time and compute resources. We did include error bars in
Figure where was feasible.
15

---

(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 7 and Appendix
4. If you using existing assets (e-g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section 7 and
Appendix E
(b) Did you mention the license of the assets? [Yes] See Section 7 and Appendix
(c) Did you include any new assets either in the supplemental material or as URL? [Yss] We include the source code of our algorithms the Supplemental Material. will be released as open-source after publication.
(d) Did you discuss whether and how consent obtained from people whose data 're using/curating? [N/A] We used well-known datasets whose creators use either publicly available data received proper consent.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] We used well-known datasets, which do not contain personally identifiable information offensive content.
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] We did not use crowdsourcing or conducted research with human subjects.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A] We did not use crowdsourcing or conducted research with human subjects.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A] We did not use crowdsourcing or conducted research with human subjects.
16


Reviews:
[{"review_id": "g9b3Rh8fw_I", "reviewer": "Reviewer_QoQf", "summary": "This paper studies the distributed mean estimation. In this problem, there are n clients,  each of which has a d-dimensional real-valued; the goal is to estimate their mean on the sever side using minimum communication cost. The paper focuses on 1-bit quantization methods, i.e., each client sends one bit per coordinate and d(1+o(1)) bits in total. The algorithms are standard (including the Hadamard transformation based method); the main difference is new scaling factors S. Theoretical analysis on the expectation and variance are provided. Empirical results also show some advantages of the new estimate. ", "questions": "", "limitations": "", "rating": 5, "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": "Strength:\n1. The problem studied is fundamental and well-motivated.\n2. Theoretical guarantees are proved.\n3. Empirical results show that the new estimate achieve improved MSE among 1-bit quantization methods.\n\nWeakness:\n1. All algorithms mostly use existing techniques. The \n2. The analyses are not too difficult.\n3. My main concern is that the paper only focus on 1-bit quantization, which I think is somewhat restricted. 1-bit quantization is often suboptimal; multi-level quantization could be much better, see e.g., qsgd [1]. In particular, when the vectors are sparse or skew, the budget for different  coordinates should be different. In particular [2] shows that the total communication cost can be sublinear in d for skew vectors. Moreover, the random rotation operation applied on the original vectors destroys such sparsity/skewness. Such skewness is bad for 1-bit quantization, which is why random rotation is applied to make the vector “flat”. But skewness can actually save communication provably, if multi-level quantization is used. \n4. In the experiments, multi-level quantization QSGD, variable-length coding methods [3], etc. should also be compared. \n\n\n\n\n[1] D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic. Qsgd: Communication-efficient sgd via gradient quantization and encoding.\\\n[2] Z. Huang, Y. WANG, K. Yi, et al. Optimal sparsity-sensitive bounds for distributed mean estimation.\\\n[3] A. T. Suresh, X. Y. Felix, S. Kumar, and H. B. McMahan. Distributed mean estimation with limited communication.\n", "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": "_g39rpnPaC6", "reviewer": "Reviewer_d5Wo", "summary": "The paper studies distributed mean estimation in the $d$-dimensional space where each client can use only $d(1+o(1))$ bits for communication. A crucial assumption is that the server and the $n$ clients can have shared randomness while each client can independently communicate with the server. Under such an assumption, the authors proposed two schemes and demonstrated the efficiency of their new approaches. ", "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": "Several comments are in order.\n\n\n1) Most parts of the paper read well with concise notations. In particular, I like the way of illustration that always starts with the Alice-Bob example. The proposed algorithms are also conceptually simple and easy to understand. \n\n\n2) The authors propose two schemes: One utilizing uniformly random rotation matrices, and the other uses Hadamard transforms. The first scheme (DRIVE) seems computationally inefficient but works for all cases, and the second (DRIVE$^+$) is more efficient and works for scenarios with structural assumptions. \n\n\n3) I wonder if the assumption of shared randomness is typical in the literature and practice (e.g., in Federated learning applications). In particular, the server needs to know the randomness of $\\textbf{all}$ clients, and uniformly generating rotation matrices seems to require lots of random bits. It will be great if the authors can clarify this point with quantitative statements such as how many random bits are sufficient. \n\n\n4) The $\\textbf{only}$ approach with a satisfactory theoretical guarantee is DRIVE accompanied by uniformly random rotation matrices (Theorem 5). Here, I do have concerns about the efficiency of the algorithm. \n\n     - On page 1, the authors mention that approaches via variable-length encoding have high computational costs. I thought that this hinted that the proposed schemes should be much more efficient. \n\n     However, as Table 1 demonstrates, DRIVE with a uniformly drawn rotation matrix is $1{,}000$ times slower than some existing approaches. \n\n\n5) I like the experimental results as they demonstrate that the proposed schemes lead to concrete improvements on standard test datasets. But I felt slightly overwhelmed by the list of highly compressed experiment descriptions, especially given that most relevant details appear in the supplementary. I suggest the authors pick a few experiments to include in the main paper with more information. This change should probably enhance the readability of the submission. \n\n\n6) Another comment is about the competing algorithms. It seems that Hadamard + 1-bit SQ and Kashin + 1bit SQ are not designed for the $d(1+o(1))$ setting. I am slightly concerned about the fairness of comparison (e.g., lines 321-322). I wonder if the authors can add comparisons with Hadamard/Kashin + $c$-bit SQ for some $c>1$ as a relaxation since achieving $d(1+o(1))$ may not be crucial in many applications. \n\n\n7) I appreciate the authors for being honest and providing a list of limitations of their work at the end of the submission. This part does not seem to mention the computational aspects of the algorithms. I think it might be good to state the time complexities of the proposed algorithms and some existing ones clearly at someplace. \n\n\n8) Minor comments: \n    - Is there a reason for normalizing the MSE of mean estimation by the sum of squared norms of the individual vectors (e.g., line 51)? I think it might be natural and more consistent if the normalizing factor is the squared norm of the mean. \n   - Should one increase the spacing between lines 59 and 60?\n   - Line 73: Is the word \"it\" referring to Alice?\n   - Page 3: Should Algorithm 1 have a caption? \n   - Line 227: Is there an actual application where 1.17 bits per coordinate is much worse than 1+o(1) bits?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors clearly stated the limitations of their work in the second paragraph of the Conclusion section. I do have some additional suggestions about the computational efficiency aspect. In Checklist, the authors indicated that \"we do not believe there is an inherit (inherent?) negative societal impact in this work.\"", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "RBlmljYuQPx", "reviewer": "Reviewer_sJg9", "summary": "This paper studies the problem of distributed mean estimation under a single bit (per coordinate) communication constraint. It proposes a novel compression scheme based on random rotation and sign quantization. The suggested method is applied to distributed and federated machine learning problems and shows improved results over previously studied quantization methods.", "questions": "", "limitations": "", "rating": 7, "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": "This work proposes and analyzes a compression method that is based on multiplication by rotation matrix followed by deterministic sign quantization and scaling. To make it scalable and computationally efficient for large dimensions, the authors suggest using structured randomized Hadamard transform, which is not a novel thing on its own. \nThe paper is clearly written, but it can benefit from adding a table with a summary of the obtained theoretical results and comparison to previous approaches.\n\nTheorem 5 is a simple consequence of the known fact\n$$\n\\mathrm{E} \\left\\Vert \\frac{1}{n} \\sum_{i=1}^n \\left(X_i - \\mathrm{E}\\left[X_i\\right]\\right) \\right\\Vert_2^2 = \\frac{1}{n^2} \\sum_1^n \\mathrm{E} \\lVert X_i - \\mathrm{E}\\left[X_i\\right] \\rVert_2^2,\n$$\nfor any independent random variables $X_i$. This was previously used in many analyzes of distributed optimization methods with compressed (gradient) updates.\n\n As soon as DRIVE with a structured random rotation cannot be made unbiased, I would like to point out the authors to the fact that distributed/federated optimization methods with biased compressors are not guaranteed to converge in the general case of convex functions and may even diverge exponentially [1]. That is why the Error-Feedback mechanism [2, 3] is required to guarantee the theoretical foundation of the proposed method in the optimization setting. In my opinion, this is the main weak theoretical point of the paper, but it can be fixed without a great effort with additional experiments.\n\nRegarding the experiments. Could you please comment why your experimental results contradict with findings of Caldas et al., which showed a better performance of Kashin representation in comparison to Hadamard transform? I think that more discussion regarding this would be helpful and insightful.\n \n\n**Minor issues/comments:**\n\nI would like to ask the authors to define (in the paper) the term PRNG, which was used on pages 2, 4 in the context of shared randomness.\n\nIt seems to me that the paper can benefit from moving some (technical) proofs into Appendix. For instance, the proofs of Theorem 1 and Lemma 1 are pretty simple, and their idea can be expressed in one sentence. This can free the space for a more detailed description of DRIVE$^+$.\n\n\n[1] Beznosikov A., et al. “On biased compression for distributed learning”. arXiv preprint arXiv:2002.12410, 2020.\n\n[2] Sebastian U. Stich, et al. “Sparsified SGD with memory”. In Advances in Neural Information Processing Systems (NeurIPS), 2018. \n\n[3] Richtárik P., et al. “EF21: A New, Simpler, Theoretically Better, and Practically Faster Error \nFeedback”. arXiv preprint arXiv:2106.05203, 2021.\n\n[4] Caldas S., et al. “Expanding the Reach of Federated Learning by Reducing Client Resource Requirements”. arXiv preprint arXiv:1812.07210, 2018.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations of the work were mostly addressed. Negative societal impact concerns are not applicable due to the theoretical nature of the paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "CgAuo_-H5jz", "reviewer": "Reviewer_UVT6", "summary": "The paper considers the problem of communication-efficient distributed mean estimation. This paper proposes a novel algorithm DRIVE which uses as little as almost 1 bit for each coordinate of the vector and estimate the distributed mean with bounded error. The idea is to use a uniform random rotation to minimize the vNMSE. Besides, DRIVE can use structured random rotation to accelerate the compression for high dimensional vectors. The empirical evaluation of DRIVE shows that federated learning with gradients compressed by DRIVE can achieve faster convergence than other compression schemes.", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "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, the writing of the paper is clean and easy to understand. As a majority of the evaluation is done for federated learning task, it would be better to provide a convergence result for DRIVE+SGD to show the impact of error of distributed mean estimation on the rates. Besides, there is a recent work (Davies et al., 2020) could be an interesting reference.\n\nDavies P, Gurunathan V, Moshrefi N, et al. New Bounds For Distributed Mean Estimation and Variance Reduction[J]. arXiv preprint arXiv:2002.09268, 2020.", "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": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new 1-bit mean estimation algorithm. While the idea of using random rotation matrices have been explored in this problem, the paper proposes a new elegant algorithm that has better performance both in theory and experiments. The paper is well written and I recommend acceptance.

I am curious to see how this method compares empirically to the variable length encoding presented in Distributed mean estimation with limited communication paper. I encourage authors to add this comparison and incorporate other reviewer comments in the final version.
Decision: Accept (Poster)