$\texttt{DoStoVoQ}$: Doubly Stochastic Voronoi Vector Quantization SGD for Federated Learning
Authors: Louis Leconte
Aymeric Dieuleveut
Edouard Oyallon
Eric Moulines
Gilles PAGES
Venue: NeurIPS 2021 Submitted (2021)
Keywords: federated learning
distributed optimization
quantization
voronoi

Abstract: The growing size of models and datasets have made distributed implementation of stochastic gradient descent (SGD) an active field of research. However the high bandwidth cost of communicating gradient updates between nodes remains a bottleneck;  lossy compression is a way to alleviate this problem. We propose a new  $\textit{unbiased}$ Vector Quantizer (VQ), named $\texttt{StoVoQ}$, to perform gradient quantization. This approach relies on introducing randomness within the quantization process, that is based on the use of unitarily invariant random codebooks and on a straightforward  bias compensation method. The distortion of $\texttt{StoVoQ}$  significantly improves upon existing quantization algorithms. Next, we explain how to combine this quantization scheme within a Federated Learning framework for complex high-dimensional model (dimension $>10^6$), introducing $\texttt{DoStoVoQ}$. We provide theoretical guarantees on the quadratic error  and (absence of) bias of the compressor, that allow to leverage strong theoretical results of convergence, e.g., with heterogeneous workers or variance reduction. Finally, we show that training on convex and non-convex deep learning problems, our method leads to significant reduction of bandwidth use while preserving model accuracy.

DoStoVoQ: Doubly Stochastic Voronoi Vector Quantization SGD for Federated Learning
Anonymous Author(s)
Affiliation
Address
email
Abstract
The growing size of models and datasets have made distributed implementation of stochastic gradient descent (SGD) an active field of research. However the high bandwidth cost of communicating gradient updates between nodes remains bottleneck; lossy compression way to alleviate this problem. We propose a new unbiased Vector Quantizer (VQ), named StoVoQ, to perform gradient quanti- zation. This approach relies introducing randomness within the quantization process, that is based on the use of unitarily invariant random codebooks and on a straightforward bias compensation method. The distortion of StoVoQ signif- icantly improves upon existing quantization algorithms. Next, we explain how to combine this quantization scheme within Federated Learning framework for complex high-dimensional model (dimension > 10%), introducing DoStoVoQ. We provide theoretical guarantees on the quadratic error and (absence of) bias of the compressor, that allow leverage strong theoretical results of convergence, e.g., with heterogeneous workers or variance reduction. Finally, we show that training convex and non-convex deep learning problems, our method leads to significant reduction bandwidth use while preserving model accuracy.
10
11
12
14
16
Introduction
18
In this paper, we consider the Federated Learning framework, in which a potentially large number K of workers cooperate solve the following problem:
K
min BERD
(M))),
(1)
20 where each function fx D IR represents the empirical risk on worker & [K] (where
21
[K] ... K}) and D is the ambient dimension of our problem. Each worker potentially holds fraction of the data, and can share information with a central server, which progressively aggregates
22
23
and updates the model accordingly [18 [7].
24
Stochastic gradient algorithms 28 are particularly well suited in the large scale learning setting [6]
25
Z). The methods easily be adapted to the distributed (and more generally federated) learning framework; see [17 and the references therein. For synchronous distributed Stochastic Gradient
26
Descent, every iteration, given the current parameter 0r, each worker computes unbiased estimate ( of the gradient of the local loss function ft. The central server then aggregates those oracles and performs the update.
28
29
30
Communicating the gradients from the local workers to the central server is often a major bottleneck. The drastic increase both in the number of parameters and of workers over the last years, has made this problem even more acute. Alleviating the communication cost is one of the crucial challenges of
32
Submitted to Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

33
federated learning [17 Sec. 3.5]. A central idea to tackle this issue is communication compression, which consists in applying lossy compression to the parameters or gradients to be transmitted. Since compression alters the message transmitted, the number of iterations required to reach a given accuracy may increase, therefore compression of interest in situations where the communication gains are large relative to the increase of communication rounds. The design of new compression schemes (see among others 30 4 5
34
35
36
37
38
34] and the adaptation of the learning algorithms to this 22
setting (see e.g. [32 | 35 active field of research.
33 36
26 12
21 and the references therein) are an extremely
40
41
Our main contribution is to introduce a novel unbiased vector quantization procedure allowing to reach tigh-compression rate, with small computational overhead. More precisely, our contribu- tions are as follow: first, we introduce StoVoQ, a vector quantization algorithm based on unitarily invariant random codebooks to automatically obtain directionally unbiased gradient oracles, and introduce a scalar correction function, that makes compression operator unbiased for very modest computational cost. We further provide theoretical guarantees on the distortion of the compressor. In summary, StoVoQ algorithm is based on the following points, that are developed in Section 2
42
43
44
45
46
1. Vector quantization The input vector x E R2 is mapped onto its nearest neighbor in codebook EM = {(
48
49
50
Random codebook. A new codebook is sampled every time new quantization operation is performed. The proposed approach is different from classical random VQ which typically uses a random codebook, but which is sampled once and then kept fixed.
51
52
53
3.
Bias removal. By relying on unitarily invariant distribution for the codewords generation, the quantized value of each vector x E Rd is directionnally unbiased. The bias only depends on the number and distributions of the random of codewords and on ||-||- This key property allows to derive a simple way to remove the quantization bias.
54
55
56
57
Then, we describe how to use StoVoQ within the FL framework: this yields the algorithm DoStoVoQ. We prove that this process satisfies strong assumption on the compression process, that allows to automatically derive fast convergence rates. In Section 3 we describe DoStoVoQ, i.e., how we solve the optimization problem (I dimension D.
58
59
60
61
4. Splitting and renormalizing gradients. First, we split each gradient to compress into buckets (z4))=1...... of dimension Re, use StoVoQ for each bucket.
5. Synchronisation of random sequences of codebooks. We ensure that those codebooks are independent, each step and between each machine, by generating new codebook each time. To avoid any subsequent communication cost, we synchronously generate the codebooks on the central and local servers, by initially sharing random seeds.
63
85
86
67
Remark that point was also used in Dai et al. [8. Points to and 5 are novel ideas that have not been leveraged in the FL framework. Finally, we demonstrate the effectiveness of random codebook quantization for gradient compression by extensive experiments in Section on standard benchmarks like ImageNet or CIFAR1O.
69
2
StoVoQ algorithm
72 Several compression operators 34
have been introduced recently as bandwidth reduction for distributed learning became major challenge. In this section, we first discuss the importance of unbiasedness of compression operators in Subsection[2.1 We then present the StoVoQ compression scheme in Subsection 2.2 Finally, we compare StoVoQ competing approaches, both theoretically and empirically on a small scale example with high compression rate.
27
10
8 36 37
74
76
77
2.1
Unbiased gradient estimate mitigate high compression rates
78 We here discuss an important property to mitigate high compression rates in FL settings. A compres- sion operator Comp is (random) mapping on R... Consider the following assumption:
80 A1 (Unbiased Compression with relatively bounded variance). compression operator Comp is unbiased for any x E RR, E[Comp(z)] z. It is said to have w-bounded relative variance,
for some 0, if satisfies, for all Rd, [[][[omp((z) z||²| < w||

---

83
The most classical compressors, especially Q-SGD and Rand H satisfy A [ with different w, see Subsection 2.3 and Table ! On the other hand, some compression operators are biased, i... E. [[Comp(2z] 7 for some E R. Those operators are often deterministic, as is the case for Top-H H compressor. The most classical assumption for biased operators, is the following contractive property along the direction of descent [1):
84
85
86
87
88
A2 (Biased Compression with contraction). For 5 > 0, a compression operator is said to be 1/ 6) conttracte for any x E TRd, we have R[][Comp(*) - =II] s (1 -1-1/(1 + 0))[[=
89
90
Constants w and ó from these two assumptions are both positive, and become larger as the compression rate increases. Alternative assumptions for the biased case have been introduced in [5].
91
Impact of unbiasedness on the compression of a single vector!] To understand the interaction be- tween the number of workers K and the compression error, a simple situation is the case in which the workers use independent and identically distributed compression operators (Comps) K to compress into K
92
93
94
95 the same vector x E Rd. The central node aggregates { {Compx(<))) bias- decomposition of the quadratic error gives:
Σ ===1 Comp
96
-IIK--E Compa(x) - x =| = [|E[oomp (1:) - x=|2 K
- ==|²].
The variance of the aggregated vector is reduced by factor K-1 when averaging the messages
97
98
send by the K workers, while the bias is independent of K. For example, if we use an unbiased
39 compressor satisfying T
we get
E
K
Σ 1==1 Comp = I.
K E -|I=-K- - km
K
Comp, (1] S (w/ (o//K]al)) (2)
while for a deterministic biased compressor, we obtain that K Ex=n (z) Comp, (z)
100
101
has the same error as any of the individual compressed vector. We therefore pay particular attention to obtaining an unbiased compressor in the following.
102
103
2.2
StoVoQ definitions and main properties.
Algorithm 1: StoVoQ with distribution p
104
The basic idea behind VQ is to quantize a vector rather than each of its coordinates. A Vector
Input : E RRd, p. M, P. seed
Output: Codeword index ic, value i, Sample Es ~ P with seed s
105
108
Quantizer is a mapping VQ(-, (xx) Id +
/s ganerate
107
Es which maps x E Rd to an element of a codebook Es, which is finite subset of Rd
codebook distribution
c = VQ(x, Ehr);
108
/+ parforn Varanai quant. o/
109
with M elements. The code of StoVoQ is pro-
i. = index of c;
/+ get index codsuard
110
vided in Algorithm [ and its crucial steps are
= Th (|æ=]]);
/+ rind radial biar table +/
111
described hereafter: we introduce the notion of
i, (Q)r=1);
quantize
112
(a) Voronoi quantization scheme before describ-
113
ing more precisely (b) random codebooks, (c) whose distributions are invariant by unitary transforms. Then, (d) a method to obtain an unbiased Voronoi scheme presented and finally (e) its asymptotic
114
115
properties (as M + 20) are given.
Voronoi Quantization. Voronoi quantization from EM, i.e.:
23
25 aims at selecting the closest codeword
117
VQ(x, EMT) argmin. ||= cll
118
Unfortunately, for any given EM, the Voronoi quantizer is not unbiased: indeed it is deterministic and (Q(x, Exr) A x if & Ev.. A classical approach to construct bias-free VQ is to use the optimal "dual" VQ (or Delaunay quantization) 24), but this approach is numerically expensive (see Subsection 2.3 To mitigate the bias, we rather use random codebooks.
119
120
121
122
(b) Random Codebook. A key ingredient of StoVoq is the use of a random codebook within the quantizer. We assume Ea = [C1, Cas] where the codewords MMM are i.i.d. random vectors distributed according to p. the codeword distribution pdf. We denote 'bs ~ p and use boldface to stress that Ess is random. When quantizing a sequence of vectors { 1.00
123
124
{ C Rdd we sample for each f E N a new codebook '6 ~ p. compute VQ(x, '6M,e) and transmit the index of the corresponding codeword is [M.] The codebook EM, is not transmitted: the transmitter and the
125
126
127
128
receiver use the same seeds so that the same codebooks '6M, can be reconstructed on both sides.
The impact of unbiasedness for obtaining optimal convergence complexities in FL is discussed in Section 3
3

---

129
(c) Unitary invariant Codewords. Denote by U(d) - 10,0" = II the set of unitary transforms
over RRd. We assume in the sequel that the codeword distribution p is unitary invariant, meaning that: A3. The distribution of the codewords p is invariant under the unitary group, i.e. for all U U(d), and any E IR,,, p(Ux) p(a).
130
132
133
Examples of such distributions include isotropic Gaussian distributions (p NN Ig), 0² > 0) and the uniform distribution on the Sphere (which is specifically discussed in Appendix D.I.. Under there exists non-negative function Prad on R2 such that, for all E IR p(æ) = Prad (|==l)).
134
135
196
() The quantization bias is radial. Under A 3 we have the following crucial unitary invariance property. For A C Rd, and U E U(d), we write U UA = {Uz,z E A}.
Lemma 1. Assume A For any nonnegative measurable function J. any U E U(d) and x E TRd
138
E. up [fQQ((VVV 6 RRexrrpp (Q Ub 11l.
139
140
The proof postponed to Appendix A.3 Tak- ing ((x) = x. the previous result implies that for any I E Rd and U E U(d), it holds that
142
Eg [VQ(Ux, bxτ)]= = UEEssrp/[VQ [VQ((r, U6 ((6r)) ] A direct consequence of the elementary Lemma 3 is
38-
143
144
3.-
145
that the quantization error is radial:
28
146
Theorem (Quantization bias). Assume A
3 Then, R4 H
for all M E N, there exists a function P
15-
147
R. such that for all Rd, BeseeplVQQ 6m)]
148
Radius
Th (I]=
149
Figure 1: function rM for d = (dashed) and d 16 (solid), p (0, Ia) and M = (orange, and M = 2 13 (green).
150
The proof is postponed to Appendix A.4
151
In words, the expectation of the quantized vec- tor VQ(x, (6r) is colinear to the vector x, i.e.
152
(a 6N) is directionally unbiased. Moreover, this radial bias only depends on ||=||, M and the distribution p. This function is intractable. but it is straightforward to pre-compute it using Monte- Carlo method. We display rh, for p = (0, Ia) in Figure Consequently, we can remove the bias of (Q '6x) by re-scaling the corresponding codeword by 1/r%r (I]=
153
154
155
156
157
We now analyze the quantization distortion for a given x E Rd vector. We need to strengthen the assumption about the distribution of the codewords. Consider the following assumption
44. (1) there exists > O such that f (raat < oo (2) for some ô > O, ms = inf, <8 (r) > O, and (3) Prad is unimodal, i.e. the super level sets fr E (R.,Paa(r)) 2 t). for 2 are convex subsets of R4.
159
161
is obviously satisfied if we take p= :00000 I2) for any o² > 0.
162
Theorem 2. Assume A A A 7 Define Ct = π - 'I( + 2/ + d/2)2/d, Then, for every a e Rd.
163
lim 2 E Bexrplll VQ(x,, 6M) 20| || Cap 22/4 ([|=]]). M-000
164
The proof is postponed Appendix C.I Note that C2 d d/ (2Te) hence Co grows only linearly with the dimension d. We can now exploit this result to control the radial bias as a function of ||
185
Since Ir" (1]=1]) - 1| < ||=|| (E<,.< |Il VQ(z, (bN) - 1// Theorem 2 shows that
186
sup / (1==1) 1| s Prad
-1/4 ( (1|=11)/||=]]]
M
187
In other words, for any E Rd, the radial bias rhe (II==l) approaches 1 as M + oc with rate O(M-1/d) We use an a scalar quantizer SQ to transmit
Because the range of values taken by 1/r ([ı==]) is limited, a small number of bits 1 is sufficient (we typically use P = 3 bits). The total number of transmitted bits is log, ) + logg (P). We use random unbiased scalar quantizer (see e.g. I. Eq. (2))), a random mapping for RR + Sp an ordered subset of IR with P for all r E R. Assuming that SQ is independent of Car, we get for all x E Rd, E[SQ(111Q) (I==+)))) (VQ() [6)] = x. To save space, we present the details of the scalar quantization (based on nonuniform random dither) methods is presented in Appendix B.
169
171
172
elements. A scalar quantizer is said to be unbiased if E[SQ(r)]
174

---

178 (e) Random vs. Optimal codebooks: We finally motivate the choice of random codebooks and
177
describe how choose the codevector distribution p. For given pdf q of the imput the (quadratic) distortion is defined as:
178
Dist(q, Ems)
- (Q((, ((x) da Ex-gl1X VQ(X, {.)1)
/ 11 3dd
(4)
179
We stress that in this case the expectation is taken w.r.t. the input distribution q. the codebook being deterministic in (4). A Voronoi optimal codebook 6 is a minimizer of the distortion over the set of codebooks: Dist(q, "%"") = ming6
180
181
Dist(g, Gx)) Zador's theorem [13] gives the
182
distortion of the Voronoi optimal codebook in the limit of M - oo; see Appendix C.I for precise statement. Denote for 3 E R2+ and a function ʃ on Rd |I/ = (f
1/P It is known that and Ja is a universal constant Ja satisfying Ja Ed-oo d/2me (see Appendix C.2 for the exact constant).
183
if 1 (144) (d+2) < 20, then as M + DC, Dist(q. Ex ) ~ M Jall//alll
184
185
Using Theorem 2 we can quantify the loss between random codebook distributed according to p and the Voronoi optimal codebook for given input distribution when M - oc. Define
187
C(g. p. d) f p(x) 2/d -(x))21i q(x)rx.
(5)
188
If 14l)))(a+2) < 0o, using the Hölder inequality with negative exponents (see 15 p. 191] and
189
Appendix C. holds that C(g. p. d) 2 [|qlaa((+22)
Theorem 3. Assume that satisfies A 3 [|lla/((+2) < co, Sa g())dr < oo for some
190
181
5 > O, and C(g,p,)) < co. Then,
lim Begye (Dist(q, Bas)l / (i G11 = CaJa C(g P. d) 2 4/(d+2)) M-00
(6)
with Ca defined in Theorem 2 Moreover, assume that input distribution q satisfies A 3 and set the
192
codeword distribution Pq.d. (d)((+2)(()) I (1114+)) (z)dz.. Then, C(g, Pq.d,
193
194
The proof is postponed to Appendix C.2 In words, under general assumptions, the distortion achieved by a random quantizer VQ(-, EM). Es ~ p is rate optimal (with rate M -22dd) If in addition g is unitarily invariant and unimodal, then random codebook distributed accord- ing to Pq.d, reaches the optimal distortion bound, up to universal constants (depending only on the dimension d). Moreover, as d + oc, then CaJz E and the efficiency gap van- ishes. As an illustration, assume that the input distribution is standard Gaussian g (0, La) and set the codeword distribution to be Pa = =N(0, a² La) where a² E R.. If a > 2, then 2) and [I,( (2) = (2x)
195
196
197
198
199
200
CON L,,, a² la),d) d) = 2Taa (add/(a²t 2/d/ The function a C(N(O, No, a² La), d) has unique minimum at o² = 2/d for which (O, Wo), a3 d2) [1 (2+4422 showing that a random codebook sam- pled from
az La) is optimal. is interesting to note that the variance of the codeword distribution N/O,, from.N((,,
should be (1 2/ larger than the variance of the input distribution (O,O Ia).
205
206
2.3
Related works
We compare StoVoQ with competing (random) compressors; additional details given App. A.I
208
QSGD. Alistarh et al. compresses each coordinate of the scaled vector x I|||=||| on s + codewords.
QSGD is a scalar quantizer which requires O(vd (Vllogg))) (d)) bits in its highest compression setting (s 1, only two possible levels for each coordinate). The vector norm is transmitted with full
209
precision ||ж]|| (16 or 32 bits). This is in general substantially higher than the number of bits used by VQ methods. In deep learning problems, it reduces the communication cost by a factor of 4 to [2]
211
213
Sec. 5].
214
Top-H/Rand H. Achieving higher compression rates is possible through sparsification operators, that only transmit a few coordinates. The most popular schemes are Top-Hf H and Rand-H compressors, that respectively map the vector to either its H largest coordinates, or random subset of cardinality H, rescaled by d/ H to ensure unbiasedness. Top- H is biased operator, and the performance of
215
217
Rand-H H are poor on deep learning tasks [5] Figures 4 and 5].
5

---

Table 1: Per iteration communication complexity of most frequently used algorithms in dimension d. Constants H and M respectively correspond to a number of coordinates to be transmitted and a number of codewords, they are chosen by the user.
Unoomp
Scalar Quamizationn
Vector Quamization
SGD
Sign
COGD 221
Top-If 32H
Rand H
Polytope 10
BSQ span [
399 greed (
Stotoo (ag)(Ar)
DeStoolog Inttl (4)
32
xy (
323
loey(Sd))
(ogg(MM)
koga (4)
Usbiasod
va/s
4/B
O 218)
17
6/H
MinmnnC3 (C)
219
HyperSphere Quantization (HSQ). HSQ was introduced by Dai al. [8] Two versions are consid- ered: (1) a greedy- Voronoi VQ referred to as uiQ-greed in Table which is biased, and for which the theoretical guarantee provided the paper (in their Lemma 3 and Theorem which corresponds to variant of A and the subsequent convergence rate) worsens as M increases, making it mostly vacuous; (2) an unbiased version VQ (HSQ-span), which uses a minimum- norm decomposition of E Span (8M) ) the linear subspace generated by the codewords- this version suffers from a large
220
221
222
223
224
225
variance (see Table and potentially an ill ill-conditioning. Moreover, the performance of HSQ-span
226
does not improve with M.
227
StoVoQ builds on HSQ-greed, that achieves high compression factors (up 60-100 to obtain close to SOTA performance on CIFAR1O), while preserving a good flexibility w.r.f. the compression level. StoVoQ approach allows to remove its inherent bias and provide a much stronger convergence analysis: our approach is the first vector quantization scheme to provably benefit from an increasing number of elements in the codebook M (and obviously benefits from the number of
228
229
230
231
232
workers K, as it is unbiased).
Dual Quantization and Cross-polytope. An approach to constructing unbiased VQ is use the dual VQ, also referred to as Delaunay Quantization (DQ); see [24]. DQ is unbiased for any ConvHull the convex hull of 6.. DQ requires compute the barycentric coordinates 236 for x E (BMM) that is to solve Af.....,$3
234
235
argmin Aas | Σ A under The quantizer is obtained by drawing codeword o with Computing the barycentric coordinates is in general very demanding unless Es has very simple structure (see Appendix B for details). The Cross-Polytope method Gandikota et al. [10] is a simple instance of DQ, with a codebook & composed of the
the constraints A; 2 0, E
238
probability
239
240
2d canonical vectors { + dde; (0..... 0, Vd, 0 0), E [d]] that relies the inclusion B2 1) C (0: vd) ConvHull( The barycentric decomposition can then easily be computed. Unfortunately, this method suffers from large variance, as the quantization error VQCP (ar, EMr) æ:| of any x is lower bounded by /d - 1, which means the error has the same quadratic error than the Rand-1 compressor.
242
245
Table I Summmrrzes the number of bits required to exchange the compressed value of a vector E RR for the compression methods considered in this Section, well the assumptions they satisfy.
246
247
Numerical comparisons: In Table we compare the distortions achieved by the compression methods given in Table [ a communication budget of 16 bits for d = 16 and assuming that the input distribution is q (0 La). The compression factor is 32 (assuming 32 bits floating point per coordinate). Such a compression rate is out of reach for QSGD, that requires, even for
249
250
251
at least Vd log(d) + R bits, where R is the number of bits to encode the norm (32 in ( For QSGD we have quantized the norm (using an uniform quantizer) on bits and obtained an averaged distortion of 36.10 (for K 1) and 1.82 for (K = 20)- the total number of bits is 19-, We use H = 2 for To and Rand-/í and use a scalar quantizer with 8 bits. For HSQ, we use bits for the norm, using the unbiased uniform quantizer given in g and a Voronoi optimal codebook for the uniform distribution on the unit-sphere with M = 20 codewords. For StoVoQ we use random codebook with M = 2 codewords: the codewords are sampled from a (0, (1 + 2/d) IJ), and 3 bits are allocated for the scalar quantization of 1/r², (the inverse of the radial bias). Finally, we average the result of 2 independent compressions for Polytope (following the replication technique described in
252
253
254
255
256
257
258
259
10). We use = 10 vectors, and report in Table 2 the distortion and sample variance. For StoVoQ 261
with K = 20, the codebooks of the different workers are independent.

---

Table 2: Distortion for Gaussian inputs, for fixed budget of 16 bits with d = 16.
Method
Sign 4
Top-2
Rand-2
Polytope
10
HSQ span S
BBQ BBQ-greed [
StoVeq
Bits (obj=16)
x
log, (2 16) x 6
log. (2 +
log.(2"")
loga
Unbiased
<
K 1
6.21 (0.02)
8.40 (0.04)
102.8 (0.9)
113.9 (0.6)
146.9 (0.6)
9.03 (0.04)
6.97 (0.02):
20
6.26 (0.02)
8.76 (0.04)
5.40 (0.04)
5.98 (0.03)
7.58 (0.04)
9. (0.04)
0.838 (0.005)
DoStoVoQ algorithm
263
264
We illustrate how the StoVoQ compression scheme can be implemented in FL. To avoid cumbersome technical details, we focus here on the Federated-SOD algorithm. At iteration + 1, each worker
265
266
computes a stochastic gradient 9 of the loss fx at the current model 8,, compresses it into
267
0 = (omp( and send it to the central server, that performs the update step 0g
0 - / k=1 Ik.t- The code of the resulting algorithm, DoStoVoQ-SGD, is given in Algorithm
268
269
At iteration 1, the crucial steps are:
270
1. Worker h E [K] computes the norm I19k,++1l of the D x gradient 9k,t+1 and then splits
the scaled gradient 9k,t+1 x VD/llat.eal into L-buckets of size d: gk,++1 VD/ 11/1 = [bk.44....., b/,++1 The norm [|9t.4+1l| || is transmitted to the central node using high-resolution scalar quantizer (or without quantization).
271
272
273
2. Fach worker quantizes the buckets (0h.e41.-..,bb.... using StoVoQ. Independent codebooks (. ( are used to ensure that the quantizers remain conditionally independent (see below for precise statement). The double stochasticity (each worker uses random codebooks, which are independent between workers and across iterations) motivates the name DoStoVoQ. At iteration t, the same codebook is used for all buckets of worker k. Formally, for & E [L] we apply (in parallel) StoVoQ k.++11 P. M, P, sk,t-1), with a sequence of different seeds )E(K)))) This sequence is shared between the workers and the central node at initialization.
275
276
277
278
279
280
3. The central node computes (ūk,t+1)ke from all messages received, performs the update (0)(2 and broadcasts 4.+1 to the workers.
282
These steps would similarly allow to incorporate StoVoQ within any of the advanced FL algo- rithms, and Theorem is the crucial assumption to derive the convergence rates, as described in Section 2 Natural extensions to DoStoVoQ-Fed-Ayy DoStoVoQ-DIAMD and DoStoVoQ -VR-VVVAAVV---AAAA are provided in Appendix D.22
284
286
Bias and variance of the pressed gradient with K workers.
Algorithm 2: DoStoVoQ-SGD over T iterations
288
Input :T nb of steps. (11)e20 LR, 9g p. M, P
Consider the two filtrations (Fi)r20
Output:(6;)) (6x) for t = 1...., T do
290
and (G. (r0 defined recursively as fol-
281
lows Fo
(0) and for L >
Wig sends 0,- and different seeds Sk,t to each wA:
292
9:41 = Fe V V. oll E (K]})
for 1: = ... K do
293
and Fi+1 Ge-1 V o((Gx.141, &
Compute local gradient Jk.t at 0:-1;
294
K]}). With these notations, for any
Split Jk.t x /D/llgx..t on .b. bb,,]: for 1...., L (in parallel) do
295
0. 0g F.maaaurable.
296
Theorem 4. At any iteration +
( k.. StoVoQ U... P. M, P, sk.))
287
1 in DoStoVol, the K compressed
end
stochastic gradients (gR.41)
298
Send (Ilga.ell, (iE- (t.k:()eezz)) to wn: end Reconstruct (ŌK,t)kEK:
289
are (i) independent conditionally
300
to G4t1 (ii) conditionally unbiased,
10
301
i.e. for all k [K]. we have
11
302
E @r. 19+1] gk.e+1. (iii) sat-
12
Update: 0, = 0,-1 7 Σk= g
303
isfy the relatively bounded error con-
13
end
304
dition of A i.e. there exists a con-
stant WM such that, for all le E [K]: E [[l0k,441 - Ik,t+1 1|2 G4t1] S ww lig.
305
Moreover, WM decreases with the number of codewords M and the P, as as = 0(M--114)+0(2-)
306
[the dependence on p. d, and D is made explicit in the proof].
7

---

308
The first statement stems from the fact that each bucket is quantized using StoVoq which is unbiased. The second statement is more challenging; proof postponed to Appendix [A.6] We stress that this result differs from Theorem 2
309
310
which corresponds to the distortion of source with distribution q-
Convergence results. Theorem proves that our compression method satisfies the assumptions needed to obtain fast convergence rate, for DoStoVoQ-SGD, and for its variants DoStoVoQ- DIANA. Consider a Smooth and Strongly Convex (SSC) function F = =E= Sk. with condition number k > 1. We measure the complexity of the algorithm by the number iterations I required to obtain a model 0r such that [0.) mingo F I The result of VR-DIANA [66, which
312
314
315
provides a complexity of OR-400 (K (1 + WM K) log(e")) [6 Corollary 2], applies to DoStoVoQ-
318
317
VR-DIANA.
318
Convergence rates for DoStoVon-DIAM can be obtained from Horváth et al. [T6 Corollary 1,3,4]. As in the strongly-conee case, complexities increase by a factor depending on (1 + +w// K) w.r.t. uncompressed algorithm. Intuitively, the impact on the optimization complexity of a high compression is miligated by the number of workers, which
(without VR), and on non-convex optimization problems
320
321
supports the use of independent and unbiased compressors when the number of workers is large and
322
323
high compression factors are required.
324
Indeed, these complexities can be compared to: (1) the one of uncompressed variance reduced
distributed methods [9] that achieve complexity of Ox oc (k ()) (in the SSC case); (2) the complexity for biased compression operators satisfying A 2 Beznosikov et al. [5] Theorem 13] that obtain Ox- + 8) log(c-))) for compressed GD (independently of the number of workers); (3) the complexities of compressed SGD methods with error feedback in [I] that also have no
326
328
329
dependency the number of workers. Overall,the unbiased character is crucial to mitigate the variance increase resulting from high compression rates.
330
Numerical experiments
331
332
4.1
Least Squares Regression (LSR)
333
We consider least squures problem with n 2 samples, a bucket size d = 16, D = 2", and K- 32 workers; each worker has access
334
10a
335
trgfaceerttann lass)
336
subset m 2 samples (picked with replace- ment) to introduce a dependency in the data used by the workers. For i E [n]. we assume X, ~
10:
337
338
100
329
(0, Ip) and Y; ~ A(X, w., 1) where w. E
RD. We solve iRR Ee -|Ti w|2 via gradient descent with step size 1/al. where is fine-tuned for each quantization method and s 2n is the smoothness constant. We use DoStoVo with M = 23 codewords sam- pled from (0, (1 2/d) Ia) for DoStoVoQ and M = 20 on the unit Sphere for HSQ s.t. the
340
10-1
342
10
343
Number Berations
344
Comparison between GD (blue), (orange) and DoStoVoQ (green), on a LSR problem in dimension D 29.
Figure 2:
345
346
347
number of bits transmitted at each round by the
348
worker is set to 16 (see T) Figure
349
the excess-log of the train loss over T 10 iterations, for a standard GD. DoStoVoQ outperforms HSQ- greed: indeed the linear convergence rate of distributed GD is faster for an unbiased compressor than for the biased approach.
351
352
4.2
Applications to Deep Neural Networks training
353
Setting. We now describe our experimental framework for training two standard models of Deep Neural Networks: VGG-16 16 BI] and ResNet- 18 [14. We follow the standard procedure of training those models both on CIFAR- 10 and ImageNet; the hyper- parameertssssrss are fine-tuned to optimize the accuracy without quantization. We do not compress the affine constant part of the affine convolutional
354
356
authors provide complexities for 10 algorithms in Table 1, with Error Feedback and under A
8

---

Table 3: Average accuracy over 5 experiments, after 100 epochs on CIFAR-10.
Algorithm
SGD
QSGD
QSGD
QSGD
HSQ
HSQ
Dos.
Dos.
2 bits
4 bits
8 bits
d d= 16
=
8
d d= 16
d = 8
Raw bits per bucket
32d
vd log(d)
log(d)
Effective Compression factor
13
34
17
K worker
91.9
91.7
92.1
91.9
92.0
92.0
92.0
92.1
K- 8 worker
92.0
91.8
91.8
92.0
91.8
92.0
91.8
92.1
Table 4: Distortion for on subset of the gradients of a layer of CIFAR-10, for a fixed budget of 16 bits with d = 16.
Method
Top-2
Rand-2
Polytope [0]
HSQ-span B
HSQ greed g
DaStoVoQ
Bits (obj =16)
2 x 8
2 x
12
16) x x
log, (2 ) +
(2 10 +
1ogg(2 +
Unbiased
V
K-
0.0022
0.025
0.028
0.034
0.0021
0.0026
357
layers and batch normalization layers. We apply independent DoStoVoQ on batches of 32 buckets of size d = 16 (i.e. we transmit a high-resolution norm for D = 32- 16 = 512 coefficients).
358
359
CIFAR-10. We use the implementation of HSQ [8] the batch size 256 for CIFAR-10, the total number of epochs is 100, the initial learning rate is 0.1, which is divided by 10 and 50 at epochs 51 and 71. We report the accuracy of DoStoVoQ, QSGD, and HSQ- greed in table By design, the compression factor of Q-SCD for d 16 is 13, which is significantly less than HSQ or DoStoVoQ. Both HSQ and DoStoVoQ perform similarly and the accuracy gap between the two methods are under the sample variance (computed over 5 seed and about 0.2). In Table 4 we report the distortion of
380
381
362
363
364
random subset of gradients G {9.. t E [[II] (with |9 103. d 16,
2 d) obtained
385
from given layer of VGG on CIFAR- 10, i.e.: 191-' K | - DK- (9x.t gr,t) !|? where
366
(9k. )) ke(k) correspond to & independent workers compressing their own gradient Jk. The choice of the layer does not affect significantly the results. Even with the actual gradient distribution, DoStoVoQ outperforms for given compression factor each unbiased method. This is pair with the observation that the gradients of a Deep Neural Network are approximately Gaussian distributed 3 36 4 Additional experiments can be found in the Appendix.
368
370
372
ImageNet. For ImageNet, we use different bucket sizes, the standard batch size of 256, and only K = worker for energy savings (recall Imagenet training last about day for single worker on academic hardware). An initial learning rate of 1 is divided by 10 at epoch 30 and 60, while the model is trained for 90 epochs. A ResNet here obtains 69. 69.9%, and with compression factor of 8, the performance drops by 2.5%. Using = 16, we reach a compression factor of 38, while the Top-1 accuracy drops by only 4.8%: this is substantially higher compression rate than the concurrent work QSGD on the ImageNet dataset.
374
376
378
Computational impact. In the case of deep Neural Networks, our training procedure requires neither a substantial modifications of standard pipelines, nor a modification of the hyper-parameter which allows save computational resources. Green Algorithm ([20) shows that this work generated around 1 15kg of CO2, and require 400 kWh. A typical experiment lasted few hours on
380
382
383
CIFAR-10 and about days ImageNet, which is in the standard range for this type of prototypical
384
codes. This work could have future impact on FL., to reduce their electrical consumption.
Broader impact. Federated learning enables multiple actors build common model without 386
data sharing, hence respecting privacy. However classic FL methods consume an important amount of energy in transmitting information. Our method DoStoVol can be adapted any FL framework while enabling important bandwidth savings. These savings highly counterbalance the computational impact of our experiments.
387
388
389

---

References
390
391
[1] Naman Agarwal, Ananda Theerthh Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Brendan distributed SGD. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 7564-7575. Curran Associates,
392
McMahan. cpSGD: Communication-effiiinee and differentially-prite
393
394
395
Inc., 2018.
396
[2] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication-Efinn Efficient SGD via Gradient Quantization and Encoding. Advances in Neural Information Processing Systems, 30: 10:1779-17220 1720, 2017.
397
398
[3] Ron Banner, Itay Hubara, Elad Hoffer, and Daniel Soudry. Scalable methods for 8-bit training of neural networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 5151-5159, 2018.
400
402
[4] Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference Machine Learning, pages 560-569. PMLR, 2018.
404
[5] Alcksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On Biased Compression for Distributed Learning. arXiv:2002. 12410 [cs, math, stat), February 2020.
406
arXiv: 2002.
408
[6] Léon Bottou. On-line learning and stochastic approximations. 1999. doi: 10.1017/
CBO978051 15699900003699
410
[7] Léon Bottou. Large-Scale Machine Learning with Stochastic Gradient Descent. In Yves Lechevallier and Gilbert Saporta, editors, Proceedings of COMPSTAT pages 177- 186, Heidelberg, 2010. Physica-Verlag HD. ISBN 978-3-7908-2604-3, doi: 10.1007/ 978-3-7908 20188-2004333111 3_16.
412
413
414
[8] Xinyan Dai, Xiao Yan, Kaiwen Zhou, Han Yang, Kelvin KW Ng, James Cheng, and Yu Fan. Hyper-sphere quantization: Communication-efficii sgd for federated learning. arXiv preprint 1rXiv:1911.04400 2019.
415
416
417
[9] Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: fast incremental gradient method with support for non-strongly convex composite objectives. In NIPS, 2014.
419
[10] Venkata Gandikota, Daniel Kane, Raj Kumar Maity, and Arya Mazumdar. vqsgd: Vector quantized stochastic gradient descent. In International Conference on Arlificial Intelligence and Statistics, pages 2197-2205. PMLR, 2021.
421
[11] Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik. Linearly Converg- ing Error Compensated SGD. arXiv:2010.12292 [cs. math], October 2020. arXiv: 2010.12292
423
[12] Eduard Gorbunov, Konstantin Burlachenko, Zhize Li, and Peter Richtárik. Marina: Faster non-convex distributed learning with compression. arXiv preprint arXiv:2102.07845, 2021.
425
[13] Siegfried Graf and Harald Luschgy. Foundations of quantization for probability distributions. Springer, 2007.
427
428
[14] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for im- age recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
429
430
[15] Edwin Hewitt and Karl Stromberg. Real and abstract analysis: modern treatment of the theory of functions of a real variable. Springer-Verlay Verlag, 2013.
432
[16] Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik. Stochastie Distributed Learning with Gradient Quantization and Variance Reduction. arXiv:1904.05115 [math], April 2019. arXiv: 1904.05115.
434
10

---

436
[17] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. I.. D D'Oliveira, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Alcksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakommaa Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang. Felix X. Yu, Han Yu, and Sen Zhao. Advances and Open Problems in Federated Learning. arXiv:1912.04977 [cs, stat/, December 2019. Xrviv: 1912.04977.
437
439
440
441
443
445
447
448
[18] Jakub Konečný, H. Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated Optimization: Distributed Machine Learning for On-Device Intelligence. arXiv:1610.02527 [cs], October 2016. arXiv: 1610.02527.
449
450
[19] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images.
452
2009.
453
[20] Loic Lannelongue, Jason Grealey, and Michael Inouye. Green Algorithms: Quantifying the carbon emissions of computation. 1rXiv:2007.07610 [cs], October 2020. arXiv: 2007.07610.
454
[21] Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtarik. Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization. In International Conference on Machine Learning, pages 5895-5904. PMLR, November 2020. ISSN: 2640-3498.
455
456
457
458
[22] Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed
Learning with Compressed Gradient Differences. 1901.0900 [cs, math, stat), June 2019. arXiv: 1901.09269.
460
481
[23]
Gilles Pagès and Jacques Printems. Optimal quadratic quantization for numerics: the gaussian case. Monte Carlo methods and applications, 9(2):135-165, 2003.
462
465
[24]
Gilles Pagès and Benedikt Wilbertz. Sharp rate for the dual quantization problem. Séminaire de Probabilités XLIX, volume 2215 of Lecture Notes in Math., pages 405-454. Springer, Cham, 2018.
465
466
[25] Gilles Pagès and Benedikt Wilbertz. Sharp rate for the dual quantization problem. In Séminaire de Probabilités XLIX, pages 405-454. Springer, 2018
467
468
[26] Constantin Philippenko and Aymeric Dieuleveut. Artemis: tight convergence guarantees for bidirectional compression in Federated Learning. arXiv:2006.1455 [cs, stat], November 2020. arXiv: 2006. 14591.
469
470
471
[27] Ali Baanezani-Kebryee Fartash Faghri, and Daniel M Roy. Nuqsgd: Improved communication efficiency for data-parallel sgd via nonuniform quantization. arXiv preprint arXiv: 2019.
473
474
[28] Herbert Robbins and Sutton Monro. A Stochastic Approximation Method. Annals of Math- ematical Statistics, 22(3):400 407, September 1951. ISSN 0003-4851, 2168-8990. doi:
475
476
10. (0.2114/amm/117772958 Number: Publisher: Institute of Mathematical Statistics.
[29] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjcev Satheesh, Sean Ma. Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115()):11-252: 2015.
478
480
[30] Seide, H. Fu, Jasha Droppo, G. Li, and D. Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech DNNs. pages 1058-1062, January 2014.
481
482
483
[31] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 14X9:v1449.1150 2014.

---

485
[32] Sebastian U. Stich and Sai Praneeth Karimireddy. The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication. urXiv:I909.0533 [cs, math, stat], September 2019. arXiv: 1909.05350.
486
[33] Sebastian U Stich, Jean-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 31, pages 4447-4458 Curran Associates, Inc., 2018
489
491
492
[34] Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. Powersgd: Practical low-rank gradient compression for distributed optimization. Advances in Nearal Information Processing Systems, 32: 1255944244,,6, 2019.
483
484
485
[35] Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient Sparsification for Communication-Effiiii Distributed Optimization. Advances Neural Information Pro- cessing Systems, 10112229999999 2018.
496
497
498
[36] An Xu, Zhouyuan Huo, and Heng Huang. Optimal gradient quantization condition for communication--fficieent distributed training. arXiv preprint vrXiv22022.11082 2020.
499
500
[37] Hantian Zhang, Jerry Li, Kaan Kara, Dan Alistarh, Ji Liu, and Ce Zhang. The zipml framework for training models with end-to-end low precision: The cans, the cannots, and a little bit of deep learning. arXiv preprint arXiv: 1.0144002 2016.
502
Checklist
503
504
1. For all authors...
505
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Section 2 for quantization and Section for
507
associated experiments.
508
(b) Did you describe the limitations of your work? [Yes] See broader impact and Appendix.
509
(c) Did you discuss any potential negative societal impacts of your work? [Yes] Detailed
510
experiments carbon footprint can be find in Section 4
511
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results... 513
514
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
515
(b) Did you include complete proofs of all theoretical results? [Yes] Also see Appendix in Supplemental Material.
516
517
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] Code available in Supplementary Material.
519
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 4
522
523
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] In particular Table 2 presents standard deviations, and variances of NN model accuracies from Section can be found in Appendix.
524
(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 4 for further references.
527
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
530
(a) If your work uses existing assets, did you cite the creators? [Yes] As mentioned in Section 4 code is partly inspired from [8]
531
532
(b) Did you mention the license of the assets? [Yes] Only open source and/or Academic assets are used.
12

---

534
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] Radial biases already computed available Supplemental Material.
535
536
(d) Did you discuss whether and how consent was obtained from people whose data you'le re using/curating? [N/A] Use of publicly available data (CIFARIO [9] and Imagenet (29)).
538
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
510
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
543
644
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
547
13


Reviews:
[{"review_id": "zGOY9vXAVi", "reviewer": "Reviewer_jQuP", "summary": "This paper presents DoStoVoQ, a vector quantization method based on Voronoi quantization. It is claimed that the compression method is designed specifically for federated learning applications. Both theoretical analysis and empirical results are provided to show the effectiveness of DoStoVoQ.", "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": "Pros:\n1. The paper is well-written and the idea is easy to follow. Improving the communication efficiency of federated learning is a promising research direction. \n2. The scales of the experiments are large enough to provide valid evidence on the performance of DoStoVoQ. \n\nCons:\nThe major concern is that by looking at the results, I am not sufficiently convinced that DoStoVoQ works well in practice, e.g., it leads to 2.5% accuracy loss on ImageNet (line 376), which is not acceptable in practice. In my view, the latest communication efficiency method achieves almost the same final accuracy and does not require compressing the gradient [1] (though DoStoVoQ has the potential to achieve higher compression rates). Maybe one way to improve DoStoVoQ is to adopt the error feedback scheme, but more experiments are required to be done.\n\nOther concerns are elaborated below:\n1. It is claimed that DoStoVoQ is for FL. But both of the formulation and experiment settings are about normal distributed SGD. How to make DoStoVoQ compatible with FedAvg/FedProx [2-3]? How does DoStoVoQ perform under data heterogeneity? \n\n2. Vector quantization is not new in communication efficient distributed training. How does DoStoVoQ compare to [4]? \n\n3. In some sense, DoStoVoQ is similar to the low-rank based compression methods, e.g., PowerSGD, GradiVeQ and Atomo [5-7]. How does DoStoVoQ compare to them? \n\n4. As mentioned above, how to make DoStoVoQ compatible with error feedback? Intuitively, it should be easy to achieve. \n\n5. In the experiments, only compression rates are reported. Please also report the end-to-end wall clock time. \n\nMinor comments:\nMissing references [6-7].\n\n[1] https://arxiv.org/abs/2103.03936\n\n[2] https://arxiv.org/pdf/1602.05629.pdf\n\n[3] https://arxiv.org/abs/1812.06127\n\n[4] https://arxiv.org/abs/1911.07971\n\n[5] https://arxiv.org/abs/1905.13727\n\n[6] https://arxiv.org/pdf/1811.03617.pdf\n\n[7] https://arxiv.org/abs/1806.04090\n\n\n=========== Post rebuttal ==============\nAfter carefully reading the authors' response, part of my concerns is addressed. Thus, I increase my overall evaluation score from 4 to 5. However, I still have the concern on the real speedup that the proposed method can achieve. Please refer to my comments below.\n====================================", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "My major suggestions are summarized in the “Cons” of “Main review”. Please take a close look at it. Overall, the proposed method can be improved to attain better results on real-world large-scale ML tasks. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "uKx3GrY37G", "reviewer": "Reviewer_Td65", "summary": "The paper presents a new unbiased gradient (vector) quantization method for communication efficient distributed optimization. \nThe authors establish bounds on expected quantization error and give convergence guarantees in convex optimization settings.", "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": "There has been considerable interest in techniques for communication compression in distributed optimization. This is motivated by increase in size of datasets and models as well as new paradigms like Federated learning. Thus, the topic that the paper considers is important and of wide interest.\n\nThe paper proposes a new vector quantization method which is as follows: the method first samples a random codebook from some appropriate probability distribution. Then a vector is mapped to its nearest point in the codebook (hence the term voronoi quantization). \nThe paper deals with design of unbiased methods, however the aforementioned point has a directional bias. Therefore, finally, an appropriate scaling is done for debiasing. Hence, what is communicated is the index of the point in the codebook as well as the scaling factor.\nThe paper is mostly well-written. The authors present a thorough theoretical and empirical analysis. \n\n**Biased vs unbiased:**: The authors motivate the design of unbiased methods by the fact that with unbiased compression, there is a benefit from averaging due to variance reduction. \nThere is a typo in the equation after line 96: the second term should be $K^{-1}E\\Vert \\text{Comp}_1(x) - E[\\text{Comp}_1(x)]\\Vert^2$.\nThe authors say that to correct the directional bias, theyneed to compute the quantity $r_M^p$, which is intractable, but can be approximated by Monte-carlo methods. This approximation error therefore contributes to a (small?) bias in the gradient estimation, hence the method is not *fully* unbiased.\n\n**Empirical comparison with biased compression methods**:\nThe empirical results support the proposed method over other unbiased methods. However, I wonder how does it perform compared to biased compression methods, like top $k$?\n\n\n**Improvement over scalar quantization?** The authors prove upper bounds on expected quantization error (Theorem 2). However, it seems to me that in order to get constant error, we need to set $M$ such such $\\log M \\approx d\\log{d}$. Hence the communication size is $O(d\\log d)$. Scalar quantization methods instead, for constant accuracy communicate $O(d)$ bits. Am I misunderstanding something here?\n\n**DoStoVoQ: Impact of parameter $L$**: The only change in the second algorithm ``DoStoVoQ\" is that it partitions the gradient vector into $L$ buckets and vector quantizes each. However, in the quantization error guarantee, there is no dependence on $L$? Why is it so? If there is indeed no dependence, why do we care about this algorithm at all?\n\n**What if we repeat codebooks?** \nIn the method presented, a new codebook is sampled i.i.d. everytime a new vector is compressed. What is the issue if we repeat the same codebook, say among all workers, in an iteration? \n\n**Convergence guarantee**: In line 316, the authors mention the convergence rate of DoStoVoQ-VR-DIANA (a variant in the appendix), however there is no mention of the the convergence rate of DoSToVoQ, the method in the main paper.\n\n**Return communication compression?**:\nIn the algorithm, only the communication from workers to master is compressed. There is no mention of communication of updated model back to the workers. \nDo the authors propose to compress the return communication too, or not? If yes, do the convergence guarantee still apply?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No direct societal impact", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Q5YFW0BxV6", "reviewer": "Reviewer_jsrJ", "summary": "Contribution:\n1. The paper proposed a new unbiased vector quantizer constructed from Voronoi quantization (which quantized a vector to its nearest neighbor in the codebook) and random codebook generation. \n2. Theoretical properties of the quantization scheme are studied, including relative variance and asymptotic growth of relative variance w.r.t dimension and size of codebook.\n3. The proposed quantization achieved superior performance compared with a few baseline methods on training neural nets.\n", "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": "Overall I think the paper is well-written and has a solid discussion on the theoretical properties of the proposed quantization scheme. But the experiments section can be improved.\nAdvantages:\n\n1. Thorough analysis is given to relative variance and the asymptotic growth rate of it with the increase of dimension/size of codebook. \n2. The proposed quantization is unbiased and has a lower error compared with HSQ methods (the main basline quantizers) both in theory and in experiments.\n\nDisadvantages:\n\n1.The comparison of different quantizers is only done well on training VGG on CIFAR-10. Similar comparison should be done on more dataset and/or network architectures. \n2. For the ResNet on Imagenet experiment, only the performance of the proposed quantization method is reported and the accuracy is below 70%, though with a higher compression rate than QSGD, the accuracy lower than that of QSGD (which is around 75% in the original paper).\n\n-----------------------------------------after rebuttal--------------------------------\n\nThanks for the detailed feedback and the new experiments. I encourage the authors to strengthen the experiments on imagenet but the current version looks good to me. I will keep my score.\n  \n\n ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I missed the discussions on the limitations of the work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "DHU2xG-ezf", "reviewer": "Reviewer_WPUh", "summary": "This paper proposes a new unbiased compression operator based on Voronoi vector quantization. Its theoretical properties are analyzed and the variance bound is proved. Then it is applied in the Federated Learning setting and compared to the previously proposed compressors.", "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": "Overall this is good work on vector quantization, which seems to be the first one to prove the applicability of this approach for such large models as deep neural networks. It presents a sound theoretical analysis and may give rise to further exciting research based on the proposed idea. This is mainly why I think it may deserve publication at the conference.\n\nThe submission is clearly written and well organized, though I believe it can benefit from moving some technical details on pages 4-5 to the Appendix. \n\nMy main concerns/requests are to explicitly and carefully say about the memory requirements and computational complexity of the proposed compression method and highlight the differences to the previous approaches. I would like the authors to measure the average time of the suggested technique required for compression and decompression. It is an important aspect, which in some cases limits the applicability of the compressors in the distributed learning [1, 2]. In addition, it is not compatible with All-Reduce, which significantly worsens the efficiency for the distributed training.\n\nBesides, there is almost no experimental study of DoStoVoQ’s performance with respect to its algorithm parameters $L, M, P$. So, I hope that the current paper will be complemented with such results.\n\nMinor issues/comments:\n\nIt seems that the authors missed a recent line of recent [3, 4] on compressors based on Kashin representation or Hadamard transform combined with stochastic quantization and the follow-up relevant papers.\n\n[1] Xu H., et al. “Compressed communication for distributed deep learning: Survey and quantitative evaluation”. [Technical report](https://repository.kaust.edu.sa/handle/10754/662495), 2020.\n\n[2] Agarwal S., et al. “On the Utility of Gradient Compression in Distributed Training Systems”. arXiv preprint arXiv:2103.00543, 2021.\n\n[3] Caldas S., et al. “Expanding the Reach of Federated Learning by Reducing Client Resource Requirements”. arXiv preprint arXiv:1812.07210, 2018.\n\n[4] Safaryan M., et al. “Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressor”. Information and Inference: A Journal of the IMA (2021).\n\n[5] Saha R., et al. “Distributed Learning and Democratic Embeddings: Polynomial-Time Source Coding Schemes Can Achieve Minimax Lower Bounds for Distributed Gradient Descent under Communication Constraints”. arXiv preprint arXiv:2103.07578, 2021.", "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": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new way to quantize SGD updates, and provides theoretical analysis and empirical validation in distributed settings (but not it seems in Federated settings where multiple updates happen at clients). The paper has several interesting contributions, but also needs a better comparison with the literature and connection to the FL setting (if that is what it is targeted for). I would encourage a resubmission to a subsequent venue with these fixes.
Decision: Reject