DoStoVoQ: Doubly Stochastic Voronoi Vector Quantization SGD for Federated Learning
Year: 2021

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

The growing size of models and datasets have made distributed implementation1 of stochastic gradient descent (SGD) an active field of research. However the2 high bandwidth cost of communicating gradient updates between nodes remains3 a bottleneck; lossy compression is a way to alleviate this problem. We propose a4 new unbiased Vector Quantizer (VQ), named StoVoQ, to perform gradient quanti-5 zation. This approach relies on introducing randomness within the quantization6 process, that is based on the use of unitarily invariant random codebooks and on7 a straightforward bias compensation method. The distortion of StoVoQ signif-8 icantly improves upon existing quantization algorithms. Next, we explain how9 to combine this quantization scheme within a Federated Learning framework for10 complex high-dimensional model (dimension > 106), introducing DoStoVoQ. We11 provide theoretical guarantees on the quadratic error and (absence of) bias of the12 compressor, that allow to leverage strong theoretical results of convergence, e.g.,13 with heterogeneous workers or variance reduction. Finally, we show that training14 on convex and non-convex deep learning problems, our method leads to significant15 reduction of bandwidth use while preserving model accuracy.16
1 Introduction17
In this paper, we consider the Federated Learning framework, in which a potentially large number K18 of workers cooperate to solve the following problem:19
min θ∈RD K∑ k=1 fk(θ), (1)
where each function fk : RD → R represents the empirical risk on worker k ∈ [K] (where20 [K] = {1, . . . ,K}) and D is the ambient dimension of our problem. Each worker potentially holds a21 fraction of the data, and can share information with a central server, which progressively aggregates22 and updates the model accordingly [18, 17].23
Stochastic gradient algorithms [28] are particularly well suited in the large scale learning setting [6,24 7]. The methods can easily be adapted to the distributed (and more generally federated) learning25 framework; see [17] and the references therein. For synchronous distributed Stochastic Gradient26 Descent, at every iteration, given the current parameter θt, each worker computes an unbiased estimate27 gk,t+1(θt) of the gradient of the local loss function fk. The central server then aggregates those28 oracles and performs the update.29
Communicating the gradients from the local workers to the central server is often a major bottleneck.30 The drastic increase both in the number of parameters and of workers over the last years, has made31 this problem even more acute. Alleviating the communication cost is one of the crucial challenges of32
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.
federated learning [17, Sec. 3.5]. A central idea to tackle this issue is communication compression,33 which consists in applying a lossy compression to the parameters or gradients to be transmitted.34 Since compression alters the message transmitted, the number of iterations required to reach a given35 accuracy may increase, therefore compression is of interest in situations where the communication36 gains are large relative to the increase of communication rounds. The design of new compression37 schemes (see among others [30, 2, 4, 5, 34]) and the adaptation of the learning algorithms to this38 setting (see e.g. [32, 1, 35, 33, 36, 22, 26, 12, 11, 21] and the references therein) are an extremely39 active field of research.40
Our main contribution is to introduce a novel unbiased vector quantization procedure allowing to41 reach high-compression rate, with a small computational overhead. More precisely, our contribu-42 tions are as follow: first, we introduce StoVoQ, a vector quantization algorithm based on unitarily43 invariant random codebooks to automatically obtain directionally unbiased gradient oracles, and44 introduce a scalar correction function, that makes compression operator unbiased for a very modest45 computational cost. We further provide theoretical guarantees on the distortion of the compressor. In46 summary, StoVoQ algorithm is based on the following points, that are developed in Section 2.47
1. Vector quantization The input vector x ∈ Rd is mapped onto its nearest neighbor in a codebook48 CM = {ci}Mi=1.49 2. Random codebook. A new codebook is sampled every time a new quantization operation is50 performed. The proposed approach is different from classical random VQ which typically uses a51 random codebook, but which is sampled once and then kept fixed.52 3. Bias removal. By relying on unitarily invariant distribution for the codewords generation, the53 quantized value of each vector x ∈ Rd is directionnally unbiased. The bias only depends on the54 number and distributions of the random of codewords and on ‖x‖. This key property allows to55 derive a simple way to remove the quantization bias.56
Then, we describe how to use StoVoQ within the FL framework: this yields the algorithm DoStoVoQ.57 We prove that this process satisfies a strong assumption on the compression process, that allows to58 automatically derive fast convergence rates. In Section 3, we describe DoStoVoQ, i.e., how we solve59 the optimization problem (1) in dimension D.60
4. Splitting and renormalizing gradients. First, we split each gradient to compress into buckets61 (xi)i=1,...,L of dimension Rd, to use StoVoQ for each bucket.62 5. Synchronisation of random sequences of codebooks. We ensure that those codebooks are63 independent, at each step and between each machine, by generating a new codebook each time.64 To avoid any subsequent communication cost, we synchronously generate the codebooks on the65 central and local servers, by initially sharing random seeds.66
Remark that point 1 was also used in Dai et al. [8]. Points 2 to 3 and 5 are novel ideas that have not67 been leveraged in the FL framework. Finally, we demonstrate the effectiveness of random codebook68 quantization for gradient compression by extensive experiments in Section 4 on standard benchmarks69 like ImageNet or CIFAR10.70
2 StoVoQ algorithm71
Several compression operators [34, 27, 10, 4, 8, 36, 37] have been introduced recently as bandwidth72 reduction for distributed learning became a major challenge. In this section, we first discuss the73 importance of unbiasedness of compression operators in Subsection 2.1. We then present the StoVoQ74 compression scheme in Subsection 2.2. Finally, we compare StoVoQ to competing approaches, both75 theoretically and empirically on a small scale example with a high compression rate.76
2.1 Unbiased gradient estimate to mitigate high compression rates77
We here discuss an important property to mitigate high compression rates in FL settings. A compres-78 sion operator Comp is a (random) mapping on Rd. Consider the following assumption:79
A1 (Unbiased Compression with relatively bounded variance). A compression operator Comp80 is unbiased if for any x ∈ Rd, E[Comp(x)] = x. It is said to have a ω-bounded relative variance,81 for some ω > 0, if it satisfies, for all x ∈ Rd, E[‖Comp(x)− x‖2] ≤ ω‖x‖2.82
The most classical compressors, especially Q-SGD and Rand-H satisfy A 1 with different ω, see83 Subsection 2.3 and Table 1. On the other hand, some compression operators are biased, i.e.,84 E[Comp(x)] 6= x for some x ∈ R. Those operators are often deterministic, as is the case for85 Top-H compressor. The most classical assumption for biased operators, is the following contractive86 property along the direction of descent [32, 5, 11]:87 A2 (Biased Compression with contraction). For δ > 0, a compression operator is said to be88 1/(1 + δ)-contractive if for any x ∈ Rd, we have E[‖Comp(x)− x‖] ≤ (1− 1/(1 + δ))‖x‖.89
Constants ω and δ from these two assumptions are both positive, and become larger as the compression90 rate increases. Alternative assumptions for the biased case have been introduced in [5].91
Impact of unbiasedness on the compression of a single vector.1 To understand the interaction be-92 tween the number of workers K and the compression error, a simple situation is the case in which the93 workers use independent and identically distributed compression operators (Compk) K k=1 to compress94
the same vector x ∈ Rd. The central node aggregates {Compk(x)}Kk=1 into K−1 ∑K k=1 Compk(x).95 A bias-variance decomposition of the quadratic error gives:96
E[‖K−1 ∑K k=1 Compk(x)− x‖2] = ‖E[Comp1(x)]− x‖2 +K−1‖E[Comp1(x)]− x‖2].
The variance of the aggregated vector is reduced by a factor K−1 when averaging the messages97 send by the K workers, while the bias is independent of K. For example, if we use an unbiased98 compressor satisfying A 1, we get99
E [ K−1 ∑K k=1 Compk(x) ] = x, E [∥∥x−K−1∑Kk=1 Compk(x)∥∥2] ≤ (ω/K)‖x‖2, (2) while for a deterministic biased compressor, we obtain that K−1 ∑K k=1 Compk(x) = Comp1(x)100 has the same error as any of the individual compressed vector. We therefore pay particular attention101 to obtaining an unbiased compressor in the following.102
2.2 StoVoQ definitions and main properties.103 Algorithm 1: StoVoQ with distribution p Input : x ∈ Rd, p, M , P , seed s Output : Codeword index ic, value ir
1 Sample CM ∼ p with seed s ; /* generate codebook with distribution p */ 2 c = VQ(x,C pM ); /* perform Voronoi quant. */ 3 ic = index of c; /* get index of codeword */ 4 r = rpM (‖x‖); /* find radial bias in table */ 5 ir = SQ(r −1) ; /* quantize r on P bits */ The basic idea behind VQ is to quantize a vector104 rather than each of its coordinates. A Vector105 Quantizer is a mapping VQ(·,CM ) : Rd →106 CM which maps x ∈ Rd to an element of a107 codebook CM , which is a finite subset of Rd108 with M elements. The code of StoVoQ is pro-109 vided in Algorithm 1, and its crucial steps are110 described hereafter: we introduce the notion of111 (a) Voronoi quantization scheme before describ-112 ing more precisely (b) random codebooks, (c) whose distributions are invariant by unitary transforms.113 Then, (d) a method to obtain an unbiased Voronoi scheme is presented and finally (e) its asymptotic114 properties (as M →∞) are given.115 (a) Voronoi Quantization. Voronoi quantization [23, 25], aims at selecting the closest codeword116 from CM , i.e.:117 VQ(x,CM ) , argminc∈CM ‖x− c‖ . (3) Unfortunately, for any given CM , the Voronoi quantizer is not unbiased: indeed it is deterministic118 and VQ(x,CM ) 6= x if x 6∈ CM . A classical approach to construct a bias-free VQ is to use the119 optimal “dual" VQ (or Delaunay quantization) [24], but this approach is numerically expensive (see120 Subsection 2.3). To mitigate the bias, we rather use random codebooks.121
(b) Random Codebook. A key ingredient of StoVoQ is the use of a random codebook within the122 quantizer. We assume CM = [C1, . . . , CM ] where the codewords {Ci}Mi=1 are i.i.d. random vectors123 distributed according to p, the codeword distribution pdf. We denote CM ∼ p and use boldface124 to stress that CM is random. When quantizing a sequence of vectors {xt}∞t=0 ⊂ Rd we sample125 for each t ∈ N a new codebook CM,t ∼ p, compute VQ(x,CM,t) and transmit the index of the126 corresponding codeword ic,t ∈ [M ]. The codebook CM,t is not transmitted: the transmitter and the127 receiver use the same seeds so that the same codebooks CM,t can be reconstructed on both sides.128
1The impact of unbiasedness for obtaining optimal convergence complexities in FL is discussed in Section 3.
(c) Unitary invariant Codewords. Denote by U(d) = {U,U∗U = I} the set of unitary transforms129 over Rd. We assume in the sequel that the codeword distribution p is unitary invariant, meaning that:130 A3. The distribution of the codewords p is invariant under the unitary group, i.e. for all U ∈ U(d),131 and any x ∈ Rd, p(Ux) = p(x).132
Examples of such distributions include isotropic Gaussian distributions (p = N (0, σ2 Id), σ2 > 0)133 and the uniform distribution on the Sphere (which is specifically discussed in Appendix D.1). Under134 A 3, there exists a non-negative function prad on R+ such that, for all x ∈ Rd, p(x) = prad(‖x‖).135 (d) The quantization bias is radial. Under A 3, we have the following crucial unitary invariance136 property. For A ⊂ Rd, and U ∈ U(d), we write UA = {Ux, x ∈ A}.137 Lemma 1. Assume A 3. For any nonnegative measurable function f , any U ∈ U(d) and x ∈ Rd,138 ECM∼p[f(VQ(Ux,CM ))] = ECM∼p[f(U VQ(x, UCM ))].139
The proof is postponed to Appendix A.3. Tak-140 ing f(x) = x, the previous result implies that141 for any x ∈ Rd and U ∈ U(d), it holds that142 ECM∼p[VQ(Ux,CM )] = UECM∼p[VQ(x, UCM )].143 A direct consequence of the elementary Lemma 3 is144 that the quantization error is radial:145 Theorem 1 (Quantization bias). Assume A 3. Then,146 for all M ∈ N, there exists a function rpM : R+ 7→147 R+ such that for all x ∈ Rd, ECM∼p[VQ(x,CM )] =148 rpM (‖x‖)x.149
The proof is postponed to Appendix A.4.150
In words, the expectation of the quantized vec-151 tor VQ(x,CM ) is colinear to the vector x, i.e.,152 VQ(x,CM ) is directionally unbiased. Moreover, this radial bias only depends on ‖x‖, M and153 the distribution p. This function is intractable, but it is straightforward to pre-compute it using154 Monte-Carlo method. We display rpM for p = N (0, Id) in Figure 1. Consequently, we can remove155 the bias of VQ(x,CM ) by re-scaling the corresponding codeword by 1/rpM (‖x‖).156
We now analyze the quantization distortion for a given x ∈ Rd vector. We need to strengthen the157 assumption about the distribution of the codewords. Consider the following assumption158 A 4. (1) there exists > 0 such that ∫ r2+ prad(r)dr < ∞ (2) for some δ > 0, mδ =159 infr≤δ prad(r) > 0, and (3) prad is unimodal, i.e. the super level sets {r ∈ R+, prad(r) ≥ t},160 for t ≥ 0 are convex subsets of R+.161
A 4 is obviously satisfied if we take p = N (0, σ2 Id) for any σ2 > 0.162 Theorem 2. Assume A 3-A 4. Define Cd = π−1Γ(1 + 2/d)Γ(1 + d/2)2/d. Then, for every x ∈ Rd,163
lim M→∞
M2/dECM∼p[‖VQ(x,CM )− x‖2] = Cdp −2/d rad (‖x‖) .
The proof is postponed to Appendix C.1. Note that Cd ud→∞ d/(2πe) hence Cd grows only linearly164 with the dimension d. We can now exploit this result to control the radial bias as a function of ‖x‖.165 Since |rpM (‖x‖)− 1| ≤ ‖x‖−1{ECM∼p[‖VQ(x,CM )− x‖2]}1/2, Theorem 2 shows that166
lim sup M→∞
M1/d|rpM (‖x‖)− 1| ≤ C 1/2 d p −1/d rad (‖x‖)/‖x‖ .
In other words, for any x ∈ Rd, the radial bias rpM (‖x‖) approaches 1 as M → ∞ with a rate167 O(M−1/d). We use an a scalar quantizer SQ to transmit 1/rpM (‖x‖). Because the range of values168 taken by 1/rpM (‖x‖) is limited, a small number of bits P is sufficient (we typically use P = 3169 bits). The total number of transmitted bits is log2(M) + log2(P ). We use a random unbiased scalar170 quantizer (see e.g. [8, Eq. (2)]), a random mapping for R → SP an ordered subset of R with P171 elements. A scalar quantizer is said to be unbiased if E[SQ(r)] = r for all r ∈ R. Assuming that172 SQ is independent of CM , we get for all x ∈ Rd, E[SQ(1/rpM (‖x‖))]ECM∼p[VQ(x,CM )] = x. To173 save space, we present the details of the scalar quantization (based on nonuniform random dither)174 methods is presented in Appendix B.1.175
(e) Random vs. Optimal codebooks: We finally motivate the choice of random codebooks and176 describe how to choose the codevector distribution p. For a given pdf q of the input the (quadratic)177 distortion is defined as:178
Dist(q,CM ) = ∫ Rd ‖x−VQ(x,CM )‖2 q(x) dx = EX∼q[‖X −VQ(X,CM )‖2] . (4)
We stress that in this case the expectation is taken w.r.t. the input distribution q, the codebook179 being deterministic in (4). A Voronoi optimal codebook C q,∗M is a minimizer of the distortion over180 the set of codebooks: Dist(q,C q,∗M ) = min|CM |=M Dist(q,CM ). Zador’s theorem [13] gives the181 distortion of the Voronoi optimal codebook in the limit of M →∞; see Appendix C.1 for a precise182 statement. Denote for β ∈ R+ and a function f on Rd, ‖f‖β = ( ∫ |f(x)|βdx)1/β . It is known that183 if ‖q‖d/(d+2) < ∞, then as M → ∞, Dist(q,CM ) u M−2/dJd‖q‖d/(d+2), and Jd is a universal184 constant Jd satisfying Jd ud→∞ d/2πe (see Appendix C.2 for the exact constant).185 Using Theorem 2, we can quantify the loss between random codebook distributed according to p and186 the Voronoi optimal codebook for a given input distribution q when M →∞. Define187
C(q, p, d) = ∫ Rd p(x)−2/dq(x)dx . (5)
If ‖q‖d/(d+2) < ∞, using the Hölder inequality with negative exponents (see [15, p. 191] and188 Appendix C.3),it holds that C(q, p, d) ≥ ‖q‖d/(d+2).189
Theorem 3. Assume that p satisfies A 3-A 4, ‖q‖d/(d+2) < ∞, ∫ Rd ‖x‖
2+δq(x)dx < ∞ for some190 δ > 0, and C(q, p, d) <∞. Then,191
lim M→∞
ECM∼p[Dist(q,CM )]/Dist(q,C q,∗ M ) = CdJ −1 d C(q, p, d)‖q‖ −1 d/(d+2). (6)
with Cd defined in Theorem 2. Moreover, assume that input distribution q satisfies A 3-A 4, and set the192 codeword distribution pq,d,∗ = qd/(d+2)(x)/ ∫ qd/(d+2)(x)dx. Then, C(q, pq,d,∗, d) = ‖q‖d/(d+2).193
The proof is postponed to Appendix C.2. In words, under general assumptions, the distortion194 achieved by a random quantizer VQ(·,CM ), CM ∼ p is rate optimal (with rate M−2/d). If195 in addition q is unitarily invariant and unimodal, then a random codebook distributed accord-196 ing to pq,d,∗ reaches the optimal distortion bound, up to universal constants (depending only197 on the dimension d). Moreover, as d → ∞, then CdJ−1d ud→∞ 1 and the efficiency gap van-198 ishes. As an illustration, assume that the input distribution is standard Gaussian q = N (0, Id)199 and set the codeword distribution to be pα = N (0, α2 Id) where α2 ∈ R∗+. If α2d > 2, then200 C(N (0, Id),N (0, α2 Id), d) = 2πα2{α2d/(α2d − 2)}d/2 and ‖N (0, Id)‖(2+d)/2 = (2π)(1 +201 2/d)1+2/d. The function α→ C(N (0, Id),N (0, α2 Id), d) has a unique minimum at α2d = 1 + 2/d202 for which C(N (0, Id),N (0, α2d Id), d) = ‖N (0, Id)‖(2+d)/2 showing that a random codebook sam-203 pled fromN (0, α2d Id) is optimal. It is interesting to note that the variance of the codeword distribution204 should be (1 + 2/d) larger than the variance of the input distribution N (0, Id).205
2.3 Related works206
We compare StoVoQ with competing (random) compressors; additional details are given App. A.1.207
QSGD. Alistarh et al. [2] compresses each coordinate of the scaled vector x/‖x‖ on s+ 1 codewords.208 QSGD is a scalar quantizer which requires O( √ d log2(d)) bits in its highest compression setting209 (s = 1, only two possible levels for each coordinate). The vector norm is transmitted with full210 precision ‖x‖ (16 or 32 bits). This is in general substantially higher than the number of bits used by211 VQ methods. In deep learning problems, it reduces the communication cost by a factor of 4 to 7 [2,212 Sec. 5].213
Top-H/Rand H. Achieving higher compression rates is possible through sparsification operators, that214 only transmit a few coordinates. The most popular schemes are Top-H and Rand-H compressors,215 that respectively map the vector to either its H largest coordinates, or a random subset of cardinality216 H , rescaled by d/H to ensure unbiasedness. Top-H is a biased operator, and the performance of217 Rand-H are poor on deep learning tasks [5, Figures 4 and 5].218
HyperSphere Quantization (HSQ). HSQ was introduced by Dai et al. [8]. Two versions are consid-219 ered: (1) a - greedy- Voronoi VQ referred to as HSQ-greed in Table 1, which is biased, and for which220 the theoretical guarantee provided in the paper (in their Lemma 3 and Theorem 3, which corresponds221 to a variant of A 2 and the subsequent convergence rate) worsens as M increases, making it mostly222 vacuous; (2) an unbiased version VQ (HSQ-span), which uses a minimum-norm decomposition of223 x ∈ Span(CM ) the linear subspace generated by the codewords - this version suffers from a large224 variance (see Table 2) and potentially an ill-conditioning. Moreover, the performance of HSQ-span225 does not improve with M .226
StoVoQ builds on HSQ-greed, that achieves high compression factors (up to 60-100 to obtain close227 to SOTA performance on CIFAR10), while preserving a good flexibility w.r.t. the compression228 level. StoVoQ approach allows to remove its inherent bias and provide a much stronger convergence229 analysis: our approach is the first vector quantization scheme to provably benefit from an230 increasing number of elements in the codebook M (and obviously benefits from the number of231 workers K, as it is unbiased).232
Dual Quantization and Cross-polytope. An approach to constructing unbiased VQ is to use233 the dual VQ, also referred to as Delaunay Quantization (DQ); see [24]. DQ is unbiased for any234 x ∈ ConvHull(CM ), the convex hull of CM . DQ requires to compute the barycentric coordinates235 for x ∈ ConvHull(CM ), that is to solve (λx1 , . . . , λxM ) = argminλ1,...,λM ‖x− ∑M i=1 λici‖2, under236
the constraints λi ≥ 0, ∑M i=1 λi = 1. The quantizer is obtained by drawing a codeword ci with237
probability [λx1 , . . . , λ x M ]. Computing the barycentric coordinates is in general very demanding238 unless CM has a very simple structure (see Appendix B for details). The Cross-Polytope239 method Gandikota et al. [10] is a simple instance of DQ, with a codebook CCP2d composed of the240 2d canonical vectors { ± √ dei = ±(0, . . . , 0, √ d, 0 . . . 0), i ∈ [d] } , that relies on the inclusion241
B2(0; 1) ⊂ B1(0; √ d) = ConvHull(CCP2d ). The barycentric decomposition can then easily be242 computed. Unfortunately, this method suffers from a large variance, as the quantization error243 ‖VQCP(x,CM )− x‖ of any x is lower bounded by √ d− 1, which means the error has the same244 quadratic error than the Rand-1 compressor.245
Table 1 summarizes the number of bits required to exchange the compressed value of a vector x ∈ Rd246 for the compression methods considered in this Section, as well as the assumptions they satisfy.247
Numerical comparisons: In Table 2, we compare the distortions achieved by the compression248 methods given in Table 1 for a communication budget of 16 bits for d = 16 and assuming that the249 input distribution is q = N (0, Id). The compression factor is 32 (assuming 32 bits floating point250 per coordinate). Such a compression rate is out of reach for QSGD, that requires, even for s = 1 at251 least √ d log(d) +R bits, where R is the number of bits to encode the norm (32 in [2]). For QSGD we252 have quantized the norm (using an uniform quantizer) on 3 bits and obtained an averaged distortion253 of 36.10 (for K = 1) and 1.82 for (K = 20) - the total number of bits is 19-. We use H = 2 for254 Top-H and Rand-H and use a scalar quantizer with 8 bits. For HSQ, we use 6 bits for the norm,255 using the unbiased uniform quantizer given in [8] and a Voronoi optimal codebook for the uniform256 distribution on the unit-sphere with M = 210 codewords. For StoVoQ we use a random codebook257 with M = 213 codewords; the codewords are sampled from a N (0, (1 + 2/d) Id), and 3 bits are258 allocated for the scalar quantization of 1/rpM (the inverse of the radial bias). Finally, we average the259 result of 2 independent compressions for Polytope (following the replication technique described in260 [10]). We use n = 104 vectors, and report in Table 2 the distortion and sample variance. For StoVoQ261 with K = 20, the codebooks of the different workers are independent.262
We illustrate how the StoVoQ compression scheme can be implemented in FL. To avoid cumbersome264 technical details, we focus here on the Federated-SGD algorithm. At iteration t+ 1, each worker265 computes a stochastic gradient gk,t+1 of the loss fk at the current model θt, compresses it into266 ĝk,t+1 = Comp(gk,t+1) and send it to the central server, that performs the update step θt =267 θt−1−γt/K ∑K k=1 ĝk,t. The code of the resulting algorithm, DoStoVoQ-SGD, is given in Algorithm 2.268 At iteration t+ 1, the crucial steps are:269
1. Worker k ∈ [K] computes the norm ‖gk,t+1‖ of the D × 1 gradient gk,t+1 and then splits270 the scaled gradient gk,t+1 × √ D/‖gk,t+1‖ into L-buckets of size d: gk,t+1 × √ D/‖gk,t+1‖ =271 [b1k,t+1, . . . , b L k,t+1]. The norm ‖gk,t+1‖ is transmitted to the central node using a high-resolution272 scalar quantizer (or without quantization).273 2. Each worker quantizes the buckets {b1k,t+1, . . . , bLk,t+1} using StoVoQ. Independent codebooks274 {CM,k,t+1}k∈[K] are used to ensure that the quantizers remain conditionally independent (see275 below for a precise statement). The double stochasticity (each worker uses random codebooks,276 which are independent between workers and across iterations) motivates the name DoStoVoQ. At277 iteration t, the same codebook is used for all buckets of worker k. Formally, for ` ∈ [L] we apply278 (in parallel) StoVoQ(b`k,t+1, p,M,P, sk,t+1), with a sequence of different seeds (sk,t+1)k∈[K],t≥0.279 This sequence is shared between the workers and the central node at initialization.280 3. The central node computes (ĝk,t+1)k∈K from all messages received, performs the update on281 (θt)t≥, and broadcasts θt+1 to the workers.282
These steps would similarly allow to incorporate StoVoQ within any of the advanced FL algo-283 rithms, and Theorem 4 is the crucial assumption to derive the convergence rates, as described in284 Section 2. Natural extensions to DoStoVoQ-Fed-Avg, DoStoVoQ-DIANA and DoStoVoQ-VR-DIANA285 are provided in Appendix D.2.286
Algorithm 2: DoStoVoQ-SGD over T iterations Input :T nb of steps, (γt)t≥0 LR, θ0, p, M , P ; Output :(θt)t≥0
1 for t = 1, . . . , T do 2 w0 sends θt−1 and different seeds sk,t to each wk; 3 for k = 1, . . . ,K do 4 Compute local gradient gk,t at θt−1; 5 Split gk,t × √ D/‖gk,t‖ on [b1k,t, . . . , bLk,t] ; 6 for ` = 1, . . . , L (in parallel) do 7 (it,k,`c , i t,k,` r ) = StoVoQ(b ` k,t, p,M,P, sk,t) 8 end 9 Send (‖gk,t‖, (it,k,`c , it,k,`r )`∈[L]) to w0 ;
10 end 11 Reconstruct (ĝk,t)k∈K ; 12 Update: θt = θt−1 − γt 1K ∑K k=1 ĝk,t ; 13 end Bias and variance of the com-287 pressed gradient with K workers.288 Consider the two filtrations (Ft)t≥0289 and (Gt)t≥0 defined recursively as fol-290 lows F0 = σ(∅) and for t ≥ 0,291 Gt+1 = Ft ∨ σ({gk,t+1, k ∈ [K]})292 and Ft+1 = Gt+1 ∨ σ({ĝk,t+1, k ∈293 [K]}). With these notations, for any294 t ≥ 0, θt is Ft-measurable.295 Theorem 4. At any iteration t +296 1 in DoStoVoQ, the K compressed297 stochastic gradients (ĝk,t+1)k∈[K]298 are (i) independent conditionally299 to Gt+1 (ii) conditionally unbiased,300 i.e., for all k ∈ [K], we have301 E [ ĝk,t+1 | Gt+1] = gk,t+1, (iii) sat-302 isfy the relatively bounded error con-303 dition of A 1, i.e. there exists a con-304 stant ωM such that, for all k ∈ [K]: E [ ‖ĝk,t+1 − gk,t+1‖2
∣∣Gt+1] ≤ ωM‖gk,t+1‖2.305 Moreover, ωM decreases with the number of codewordsM and the P , as ωM = O(M−2/d)+O(2−P )306 [the dependence on p, d, and D is made explicit in the proof].307
The first statement stems from the fact that each bucket is quantized using StoVoQ which is unbiased.308 The second statement is more challenging; proof is postponed to Appendix A.6. We stress that this309 result differs from Theorem 2, which corresponds to the distortion of a source with distribution q.310
Convergence results. Theorem 4 proves that our compression method satisfies the assumptions311 needed to obtain fast convergence rate, for DoStoVoQ-SGD, and for its variants DoStoVoQ-(VR)-312 DIANA. Consider a Smooth and Strongly Convex (SSC) function F = ∑K k=1 fk, with condition313 number κ > 1. We measure the complexity of the algorithm by the number of iterations t required314 to obtain a model θt such that E[F (θt)] − minRD F ≤ . The result of VR-DIANA [16], which315 provides a complexity of Oκ→∞ ( κ (1 + ωM/K) log( −1) )
[16, Corollary 2], applies to DoStoVoQ-316 VR-DIANA.317
Convergence rates for DoStoVoQ-DIANA (without VR), and on non-convex optimization problems318 can be obtained from Horváth et al. [16, Corollary 1,3,4]. As in the strongly-convex case, complexities319 increase by a factor depending on (1+ωM/K) w.r.t. uncompressed algorithm. Intuitively, the impact320 on the optimization complexity of a high compression is mitigated by the number of workers, which321 supports the use of independent and unbiased compressors when the number of workers is large and322 high compression factors are required.323
Indeed, these complexities can be compared to: (1) the one of uncompressed variance reduced324 distributed methods [9] that achieve a complexity of Oκ→∞ ( κ log( −1) ) (in the SSC case); (2) the325 complexity for biased compression operators satisfying A 2, Beznosikov et al. [5, Theorem 13] that326 obtain Oκ→∞(κ(1 + δ) log( −1)) for compressed GD (independently of the number of workers);327 (3) the complexities of compressed SGD methods with error feedback in [11]2, that also have no328 dependency on the number of workers. Overall,the unbiased character is crucial to mitigate the329 variance increase resulting from high compression rates.330
4 Numerical experiments331
4.1 Least Squares Regression (LSR)332
We consider a least-squares problem with n =333 214 samples, a bucket size d = 16, D = 29, and334 K = 32 workers; each worker has access to a335 subset m = 211 samples (picked with replace-336 ment) to introduce a dependency in the data used337 by the workers. For i ∈ [n], we assume Xi ∼338 N (0, ID) and Yi ∼ N (X>i ω∗, 1) where ω∗ ∈339 RD. We solve infω∈RD ∑n i=1 ‖Yi−X>i ω‖2 via340 a gradient descent with step size 1/αL where341 α is fine-tuned for each quantization method342 and L ≈ 2n is the smoothness constant. We343 use DoStoVoQ with M = 213 codewords sam-344 pled fromN (0, (1+2/d) Id) for DoStoVoQ and345 M = 210 on the unit Sphere for HSQ s.t. the346 number of bits transmitted at each round by the347 worker is set to 16 (see Table 2). Figure 2 reports348
the excess-log of the train loss over T = 10 iterations, for a standard GD. DoStoVoQ outperforms349 HSQ-greed: indeed the linear convergence rate of distributed GD is faster for an unbiased compressor350 than for the biased approach.351
4.2 Applications to Deep Neural Networks training352
Setting. We now describe our experimental framework for training two standard models of Deep353 Neural Networks: a VGG-16 [31] and a ResNet-18 [14]. We follow the standard procedure of training354 those models both on CIFAR-10 and ImageNet; the hyper-parameters are fine-tuned to optimize the355 accuracy without quantization. We do not compress the affine constant part of the affine convolutional356
2authors provide complexities for 10 algorithms in Table 1, with Error Feedback and under A 2.
layers and batch normalization layers. We apply independent DoStoVoQ on batches of 32 buckets of357 size d = 16 (i.e. we transmit a high-resolution norm for D = 32 · 16 = 512 coefficients).358
CIFAR-10. We use the implementation of HSQ [8]: the batch size is 256 for CIFAR-10, the total359 number of epochs is 100, the initial learning rate is 0.1, which is divided by 10 and 50 at epochs360 51 and 71. We report the accuracy of DoStoVoQ, QSGD, and HSQ-greed in table 4. By design, the361 compression factor of Q-SGD for d = 16 is 13, which is significantly less than HSQ or DoStoVoQ.362 Both HSQ and DoStoVoQ perform similarly and the accuracy gap between the two methods are under363 the sample variance (computed over 5 seed and about 0.2). In Table 4 we report the distortion of364 a random subset of gradients G = {gt, t ∈ [|G|]} (with |G| = 102, d = 16, D = 25 × d) obtained365 from a given layer of a VGG on CIFAR-10, i.e.: |G|−1 ∑ gt∈G
∥∥K−1∑Kk=1(gk,t − ĝk,t)∥∥2, where366 (ĝk,t)k∈[K] correspond to k independent workers compressing their own gradient gk,t. The choice367 of the layer does not affect significantly the results. Even with the actual gradient distribution,368 DoStoVoQ outperforms for a given compression factor each unbiased method. This is on pair369 with the observation that the gradients of a Deep Neural Network are approximately Gaussian370 distributed [3, 36, 4]. Additional experiments can be found in the Appendix.371
ImageNet. For ImageNet, we use different bucket sizes, the standard batch size of 256, and only372 K = 1 worker for energy savings (recall Imagenet training last about 1 day for a single worker on373 academic hardware). An initial learning rate of 0.1 is divided by 10 at epoch 30 and 60, while the374 model is trained for 90 epochs. A ResNet here obtains 69.9%, and with a compression factor of 8,375 the performance drops by 2.5%. Using d = 16, we reach a compression factor of 38, while the Top-1376 accuracy drops by only 4.8%: this is a substantially higher compression rate than the concurrent work377 QSGD on the ImageNet dataset.378
Computational impact. In the case of deep Neural Networks, our training procedure requires379 neither a substantial modifications of standard pipelines, nor a modification of the hyper-parameters380 which allows to save computational resources. Green Algorithm ([20]) shows that this work381 generated around 15kg of CO2, and require 400 kWh. A typical experiment lasted few hours on382 CIFAR-10 and about 3 days on ImageNet, which is in the standard range for this type of prototypical383 codes. This work could have future impact on FL, to reduce their electrical consumption.384
Broader impact. Federated learning enables multiple actors to build a common model without385 data sharing, hence respecting privacy. However classic FL methods consume an important amount386 of energy in transmitting information. Our method DoStoVoQ can be adapted to any FL framework387 while enabling important bandwidth savings. These savings highly counterbalance the computational388 impact of our experiments.389
References390 [1] Naman Agarwal, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Brendan391 McMahan. cpSGD: Communication-efficient and differentially-private distributed SGD. In392 S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors,393 Advances in Neural Information Processing Systems 31, pages 7564–7575. Curran Associates,394 Inc., 2018.395
[2] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD:396 Communication-Efficient SGD via Gradient Quantization and Encoding. Advances in Neural397 Information Processing Systems, 30:1709–1720, 2017.398
[3] Ron Banner, Itay Hubara, Elad Hoffer, and Daniel Soudry. Scalable methods for 8-bit training399 of neural networks. In Proceedings of the 32nd International Conference on Neural Information400 Processing Systems, pages 5151–5159, 2018.401
[4] Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar.402 signsgd: Compressed optimisation for non-convex problems. In International Conference on403 Machine Learning, pages 560–569. PMLR, 2018.404
[5] Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On Biased405 Compression for Distributed Learning. arXiv:2002.12410 [cs, math, stat], February 2020.406 arXiv: 2002.12410.407
[6] Léon Bottou. On-line learning and stochastic approximations. 1999. doi: 10.1017/408 CBO9780511569920.003.409
[7] Léon Bottou. Large-Scale Machine Learning with Stochastic Gradient Descent. In Yves410 Lechevallier and Gilbert Saporta, editors, Proceedings of COMPSTAT’2010, pages 177–411 186, Heidelberg, 2010. Physica-Verlag HD. ISBN 978-3-7908-2604-3. doi: 10.1007/412 978-3-7908-2604-3_16.413
[8] Xinyan Dai, Xiao Yan, Kaiwen Zhou, Han Yang, Kelvin KW Ng, James Cheng, and Yu Fan.414 Hyper-sphere quantization: Communication-efficient sgd for federated learning. arXiv preprint415 arXiv:1911.04655, 2019.416
[9] Aaron Defazio, Francis R Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient417 method with support for non-strongly convex composite objectives. In NIPS, 2014.418
[10] Venkata Gandikota, Daniel Kane, Raj Kumar Maity, and Arya Mazumdar. vqsgd: Vector419 quantized stochastic gradient descent. In International Conference on Artificial Intelligence420 and Statistics, pages 2197–2205. PMLR, 2021.421
[11] Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik. Linearly Converg-422 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: Faster424 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.426 Springer, 2007.427
[14] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for im-428 age recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern429 Recognition (CVPR), June 2016.430
[15] Edwin Hewitt and Karl Stromberg. Real and abstract analysis: a modern treatment of the431 theory of functions of a real variable. Springer-Verlag, 2013.432
[16] Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter433 Richtárik. Stochastic Distributed Learning with Gradient Quantization and Variance Reduction.434 arXiv:1904.05115 [math], April 2019. arXiv: 1904.05115.435
[17] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar-436 jun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings,437 Rafael G. L. D’Oliveira, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett,438 Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang439 He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri440 Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi441 Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer442 Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn443 Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr,444 Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu,445 and Sen Zhao. Advances and Open Problems in Federated Learning. arXiv:1912.04977 [cs,446 stat], December 2019. arXiv: 1912.04977.447
[18] Jakub Konečný, H. Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated448 Optimization: Distributed Machine Learning for On-Device Intelligence. arXiv:1610.02527449 [cs], October 2016. arXiv: 1610.02527.450
[19] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images.451 2009.452
[20] Loïc Lannelongue, Jason Grealey, and Michael Inouye. Green Algorithms: Quantifying the453 carbon emissions of computation. arXiv:2007.07610 [cs], October 2020. arXiv: 2007.07610.454
[21] Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtarik. Acceleration for Compressed455 Gradient Descent in Distributed and Federated Optimization. In International Conference on456 Machine Learning, pages 5895–5904. PMLR, November 2020. ISSN: 2640-3498.457
[22] Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed458 Learning with Compressed Gradient Differences. arXiv:1901.09269 [cs, math, stat], June 2019.459 arXiv: 1901.09269.460
[23] Gilles Pagès and Jacques Printems. Optimal quadratic quantization for numerics: the gaussian461 case. Monte Carlo methods and applications, 9(2):135–165, 2003.462
[24] Gilles Pagès and Benedikt Wilbertz. Sharp rate for the dual quantization problem. In Séminaire463 de Probabilités XLIX, volume 2215 of Lecture Notes in Math., pages 405–454. Springer, Cham,464 2018.465
[25] Gilles Pagès and Benedikt Wilbertz. Sharp rate for the dual quantization problem. In Séminaire466 de Probabilités XLIX, pages 405–454. Springer, 2018.467
[26] Constantin Philippenko and Aymeric Dieuleveut. Artemis: tight convergence guarantees for468 bidirectional compression in Federated Learning. arXiv:2006.14591 [cs, stat], November 2020.469 arXiv: 2006.14591.470
[27] Ali Ramezani-Kebrya, Fartash Faghri, and Daniel M Roy. Nuqsgd: Improved communication471 efficiency for data-parallel sgd via nonuniform quantization. arXiv preprint arXiv:1908.06077,472 2019.473
[28] Herbert Robbins and Sutton Monro. A Stochastic Approximation Method. Annals of Math-474 ematical Statistics, 22(3):400–407, September 1951. ISSN 0003-4851, 2168-8990. doi:475 10.1214/aoms/1177729586. Number: 3 Publisher: Institute of Mathematical Statistics.476
[29] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng477 Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual478 recognition challenge. International journal of computer vision, 115(3):211–252, 2015.479
[30] F. Seide, H. Fu, Jasha Droppo, G. Li, and D. Yu. 1-bit stochastic gradient descent and its480 application to data-parallel distributed training of speech DNNs. pages 1058–1062, January481 2014.482
[31] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale483 image recognition. arXiv preprint arXiv:1409.1556, 2014.484
[32] Sebastian U. Stich and Sai Praneeth Karimireddy. The Error-Feedback Framework: Better485 Rates for SGD with Delayed Gradients and Compressed Communication. arXiv:1909.05350486 [cs, math, stat], September 2019. arXiv: 1909.05350.487
[33] Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with Memory.488 In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors,489 Advances in Neural Information Processing Systems 31, pages 4447–4458. Curran Associates,490 Inc., 2018.491
[34] Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. Powersgd: Practical low-rank492 gradient compression for distributed optimization. Advances in Neural Information Processing493 Systems, 32:14259–14268, 2019.494
[35] Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient Sparsification for495 Communication-Efficient Distributed Optimization. Advances in Neural Information Pro-496 cessing Systems, 31:1299–1309, 2018.497
[36] An Xu, Zhouyuan Huo, and Heng Huang. Optimal gradient quantization condition for498 communication-efficient distributed training. arXiv preprint arXiv:2002.11082, 2020.499
[37] Hantian Zhang, Jerry Li, Kaan Kara, Dan Alistarh, Ji Liu, and Ce Zhang. The zipml framework500 for training models with end-to-end low precision: The cans, the cannots, and a little bit of deep501 learning. arXiv preprint arXiv:1611.05402, 2016.502
Checklist503
1. For all authors...504 (a) Do the main claims made in the abstract and introduction accurately reflect the paper’s505 contributions and scope? [Yes] See Section 2 for quantization and Section 4 for506 associated experiments.507
(b) Did you describe the limitations of your work? [Yes] See broader impact and Appendix.508 (c) Did you discuss any potential negative societal impacts of your work? [Yes] Detailed509 experiments carbon footprint can be find in Section 4.510 (d) Have you read the ethics review guidelines and ensured that your paper conforms to511 them? [Yes]512 2. If you are including theoretical results...513
(a) Did you state the full set of assumptions of all theoretical results? [Yes]514 (b) Did you include complete proofs of all theoretical results? [Yes] Also see Appendix in515 Supplemental Material.516 3. If you ran experiments...517
(a) Did you include the code, data, and instructions needed to reproduce the main experi-518 mental results (either in the supplemental material or as a URL)? [Yes] Code available519 in Supplementary Material.520
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they521 were chosen)? [Yes] See Section 4.522
(c) Did you report error bars (e.g., with respect to the random seed after running experi-523 ments multiple times)? [Yes] In particular Table 2 presents standard deviations, and524 variances of NN model accuracies from Section 4 can be found in Appendix.525
(d) Did you include the total amount of compute and the type of resources used (e.g.,526 type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 4 for further527 references.528
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...529 (a) If your work uses existing assets, did you cite the creators? [Yes] As mentioned in530 Section 4, code is partly inspired from [8].531 (b) Did you mention the license of the assets? [Yes] Only open source and/or Academic532 assets are used.533
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]534 Radial biases already computed available in Supplemental Material.535
(d) Did you discuss whether and how consent was obtained from people whose data536 you’re using/curating? [N/A] Use of publicly available data (CIFAR10 [19] and537 Imagenet [29]).538
(e) Did you discuss whether the data you are using/curating contains personally identifiable539 information or offensive content? [N/A]540
5. If you used crowdsourcing or conducted research with human subjects...541 (a) Did you include the full text of instructions given to participants and screenshots, if542 applicable? [N/A]543 (b) Did you describe any potential participant risks, with links to Institutional Review544 Board (IRB) approvals, if applicable? [N/A]545 (c) Did you include the estimated hourly wage paid to participants and the total amount546 spent on participant compensation? [N/A]547

Review summaries:
Contribution: 1. 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.  2. 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. 3. The proposed quantization achieved superior performance compared with a few baseline methods on training neural nets. 

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.

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.