Preserved central model for faster bidirectional compression in distributed settings
Authors: Constantin Philippenko
Aymeric Dieuleveut
Venue: NeurIPS 2021 Poster (2021)
Keywords: Federated Learning
Bidirectional Compression
Data Heterogeneity
Optimization

Abstract: We develop a new approach to tackle communication constraints in a distributed learning problem with a central server. We propose and analyze a new algorithm that performs bidirectional compression and achieves the same convergence rate as algorithms using only uplink (from the local workers to the central server) compression. To obtain this improvement, we design MCM, an algorithm such that the downlink compression only impacts local models, while the global model is preserved. As a result, and contrary to previous works, the gradients on local servers are computed on perturbed models. Consequently, convergence proofs are more challenging and require a precise control of this perturbation. To ensure it, MCM additionally combines model compression with a memory mechanism. This analysis opens new doors, e.g. incorporating worker dependent randomized-models and partial participation.

Preserved central model for faster bidirectional compression in distributed settings
Constantin Philippenko Aymeric Dieuleveut CMAP, École Polytechnique, Institut Polytechnique de Paris [f [fistname] [lastname] @polytechnique. edu
Abstract
We develop new approach tackle communication constraints in distributed learning problem with central server. We propose and analyze new algorithm that performs bidirectional compression and achieves the same convergence rate as algorithms using only uplink (from the local workers to the central server) compression. To obtain this improvement, the downlink compression only impacts local models, while the global model is preserved. As result, and contrary to previous works, the gradients local servers are computed on perturbed models. Consequently, convergence proofs are more challenging and require a precise control of this perturbation. To ensure it, MCM additionally combines model compression with a memory mechanism. This analysis opens new doors, e.g. incorporating worker dependent randomized-models and partial participation.
design MCM, algorithm such that
Introduction
Large scale distributed machine learning is widely used in many modern applications [1, 6, 28). The training is distributed over a potentially large number of workers that communicate either with a central server [see 17, 22, on federated learning], using peer-to-peer communication [9, 34, 32].
In this work, we consider setting using a central server that aggregates updates from remote nodes. Formally, we have number of features E N", and convex cost function F Rd + IR We want to solve the following distributed convex optimization problem using stochastic gradient algorithms [25, 5]: min,eR" F (ww) with F(w) = & ΣN FÚ (ws). where (F)) is a local risk function (empirical risk expected risk in streaming framework). This applies to both instances of distributed and federated learning.
An important issue of those frameworks is the high communication cost between the workers and the central server [16, Sec. 3.5]. This cost is a concern from several points of view. First, exchanging information can be the bottleneck in terms of speed. Second, the data consumption and the bandwidth usage of training large distributed models can be problematic; and furthermore, the energetic and environmental impact of those exchanges is growing concern. Over the last few years, new algorithms were introduced, compressing messages in the upload communications (i.e., from remote devices to the central server) in order to reduce the size of those exchanges [29, 3. 36, 2, 35, 31, 30, 23, 18]. More recently, a new trend has emerged to also compress the downlink communication: this is bidirectional compression.
The necessity for bidirectional compression can depend on the situation. For example, single uplink compression could be sufficient in asymmetric regimes in which broadcasting message to N workers ("one N") faster than aggregating the information coming from each node ("N to one"). However, in other regimes, e.g. with few machines, where the bottleneck is the transfer time of a heavy model (up several GB in modern Deep Learning architectures) the downlink communication cannot be disregarded, as the upload and download speed are of the same order [24].
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Furthermore, in situation in which participants have to systematically download an update (e.g.. on their smartphones) to participate in the training, participants would prefer to receive a small size update (compressed) rather than heavier one. To encompass all situations, we consider algorithms for which the information exchanged is compressed in both directions.
To perform downlink communication, existing bidirectional algorithms [33, 38, 26, 19, 24, 14, 37, I1] first aggregate all the information they have received, compress them and then carry out the broadcast. Both the main "global" model and the "local" ones perform the same update with this compressed information. Consequently, the model hold on the central server and the one used on the local workers (to query the gradient oracle) are identical. However, this means that the model on the central server has been artificially degraded: instead of using all the information it has received, it is updated with the compressed information.
Here, focus on preserving (instead of degrading) the central model: the update made on its side does not depend on the downlink compression. This implies that the local models are different from the central model. The local gradients are thus measured on a "perturbed model" (or "perturbed iterate") "): such an approach requires a more involved analysis and the algorithm must be carefully designed to control the deviation between the local and global models [21]. For example, algorithms directly compressing the model or the update would simply not converge.
We propose MCM- Model Compression with Memory- new algorithm that 1) preserves the central model, and 2) uses a memory scheme to reduce the variance of the local model. We prove that the convergence of this method is similar to the one of algorithms using only unidirectional compression.
Potential Impact. Proposing an analysis that handles perturbed iterates is the key to unlock three major challenges of distributed learning run with bidirectionally compressed gradients. First, show that it is possible to improve the convergence rate by sending different randomized models to the different workers, this Rand Secondly, this analysis also paves the way to deal with partially participating machines: the adaptation of Rand-MOM to this framework is straightforward: while adapt- ing existing algorithms [26] to partial participation not practical. Thirdly, this framework is also promising in terms of business applications, c.g., in the situation of learning with privacy guaranteess and with a trusted central server. We detail those three possible extensions in Subsection 4.1.
Broader impact. This work is aligned with a global effort to make the usage of large scale Federated Learning sustainable by minimizing its environmental impact. Though the impact of such algorithms is expected to be positive, at least environmental concerns, cautiousness is still required, as a rebound effect may be observed [12]: having energetically cheaper and faster algorithms may result in an increase of such applications, annihilating the gain made by algorithmic progress.
Contributions. We make the following contributions:
1. We propose new algorithm MCM, combining memory process to the "preserved" update. To convey the key steps of the proof, we also introduce an auxiliary hypothetical algorithm, Ghost. 2. For those algorithms, we carcfully control the variance of the local models w.r.t. the global one. We provide a contraction equation involving the control on the local model's variance and show that MCM achieves the same rate of convergence as single compression in strongly-conve convex, convex and non-convex regimes. We give comparisons of MCM's rates with existing algorithms in Table 2.
3. We propose a variant, Rand-MCM incorporating diversity into models shared with the local workers and show that it improves convergence for quadratic functions.
This is the first algorithm for double compression to focus on a preserved central model. We underline, both theoretically and in practice, that we get the same asymptotic convergence rate for simple and double compression which is a major improvement. Our approach is one of the first to allow for worker dependent model, and to naturally adapt worker dependent compression levels.
The rest of the paper is organized as follows: in Section we present the problem statement and introduce MCM and Rand-MCM. Theoretical results these algorithms are successively presented in Sections 3 and 4. Finally, we present experiments supporting the theory in Section 5.
2 Problem statement
We consider the minimization problem described in Section 1. In the convex case, we assume there exists an optimal parameter w., and denote F. = F(w.). We use ||-I| to denote the Euclidean norm. To solve this problem, we rely on a stochastic gradient descent (SGD) algorithm. A stochastic gradient g is provided at iteration k in N to the device in [1, This gradient oracle can be
2

---

Table I: Features of the main existing algorithms performing compression. eú (resp. Ex) denotes
the of error-feedback uplink (resp. downlink). hi (resp. H₂) denotes the of memory at uplink (resp. downlink). Note that Dist-EF-SGD is identical to Subble-Squeeze but has been developed simultaneously and independently.
Compr.
11
Ex
H
Rand.
update point
Qegd [3]
one-way
ECQ [36]
one-way
/
Diana [23]
one-way
Dore [19]
two-way
degraded
Double-Squeeze [33], Masst-EF-SG [38]
two-way
degraded
Artemis [24]
two-way
degraded
MCM
two-way
non-degraded
Rand-MCK
two-way
non-degraded
computed on a mini-batch of size b. This function is then evaluated at point wa. In the classical centralized framework (without compression), for a learning rate % SGD corresponds to:
N
Wk++1
1
Σ 1=1
8 (wx).
(1)
N
We now describe the framework used for compression.
2.1 Bidirectional compression framework
Bidirectional compression consists in compressing communications both directions between the central server and remote devices. We use two different compression operators, respectively Cup and Cawn to compress the message in each direction. Roughly speaking, the update in eq. (1) becomes:
Wk+1 = W'k - 7Cdwn
Σ Cup Cup(Ea+1(uu))
However, this approach has major drawback. The central server receives and aggregates information 1 Em= ( (wx)). But in order to able to broadcast back, it compresses it, before N
applying the update. We refer to this strategy the "degraded update" approach. Its major advantage simplicity, and was used in all previous papers performing double compression. Yet, it appears to be waste of valuable information. In this paper, update the global model wx+11 independently of the downlink compression:
Wk++1 wx AN > Σ Cup (1)+1(10)))
2)
xh+1 = Cáwn (wk+1)
However, blumtly compressing Wx+11 in eq. (2) hinders convergence, thus the second part of the update needs be refined by adding memory mechanism. We describe both communication stages of the real MCM, which is entirely defined by the following uplink and downlink equations.
Downlink
Uplink
Mu+t1 I Wk+1 1 Hi
E [L, A =g
ge (wk) hi
(3)
Wh+1 = H₁. + Cawn (1++1) H8+1 HE addn (1x+1).
Wh+1 N Ei= Cup (Ap( ) + h
hi = hi, Cup (A))
Downlink Communication. We introduce downlink memory term (Hz) which is available on both workers and central server. The difference lx+11 between the model and this memory is compressed and exchanged, then the local model is reconstructed from this information. The memory then updated as defined on left part of eq. (3), with a learning rate Qdwn-
Introducing this memory mechanism is crucial to control the variance of the local model W To the best of our knowledge MCM the first algorithm that uses such memory mechanism for downlink compression. This mechanism was introduced by Mishchenko et al. [23] for the uplink compression but with the other purpose of mitigating the impact of heterogeneity, while we use here to avoid divergence of the local model's variance.
3

---

Uplink Communication. The motivation to introduce an uplink memory term hig for each device i N] is different, and better understood. Indeed, for the uplink direction, this mechanism is only necessary (and then crucial) to handle heterogeneous workers [i.e., with different data distributions, see e.g. 24]. Here, the difference A between the stochastic gradient g at the local model Wj (as defined in eq. (3)) and the memory term is compressed and exchanged. The memory is then updated as defined on right part of eq. (3) with a rate O'dwn-
Remark 1 (Rate Odwnn.. It is necessary to addwn 1. Otherwise, the compression noise tends to propagate and is amplified, because of the multiplicative nature of the compression. In Figure I we compare MCM, with 3 other strategies: compressing only the update, compressing wk Wk-1,, (i.e., Odwn = 1), and compressing the model (i.e., H2 = 0), showing that only MCM converges.
Remark 2 (Memory vs Error Feedback). Error feedback is another technique, introduced by Seide et al. [29]. In the context of double compression, it has been shown to improve convergence for a restrictive class of contracting compression operators (which are generally biased) by Zheng et al. [38], Tang et al. [33]. However, we note several differences to our approach. (1) For unbiased operators- as considered in Dore, it did not lead to any theoretical improvement [Remark 2 in Sec.
4.1., 19]. (2) Moreover, only a fraction (namely (1 + wäwn) of the "error" WK+1 Wk+1 can be preserved in the EF term (see line 18 in algo in Liu al.). It is thus impossible to recover the central preserved model as a function of the degraded model and the EF term. (3) [38] consider biased operator and the same compression level for uplink and downlink compression. They also rely on stronger assumptions on the gradient (uniformly bounded) and only tackle the homogeneous case.
In Table I we summarize the main algorithms for compression in distributed training. As downlink communication can be more efficient than uplink, we consider distinct operators Cawas Cup and allow the corresponding compressions levels to be distinct: those quantities are defined in Assumption 1. Assumption 1. There exists constants Wap Wawn E R, such that the compression operators Cup and Cawn satisfy the two following properties for all w in Rd: IE(upp/ww((u) = w, and B[[[Cup/dwn((/) (w) - w |2] S Wap/dwnll | The higher is w, the more aggressive the compression is. We only consider unbiased operators, that encompass sparsification, quantization and sketching. References and discussion those operators, and possible extensions of our results to biased operators are provided in Appendix A.I.
Remark 3 (Related work on Perturbed iterate analysis). The theory of perturbed iterate analysis was introduced by Mania et al. [21] to deal with asynchronous SGD. More recently, it was used by Stich and Karimireddy [30], Gorbunov al. [11] to analyze the convergence of algorithmss with uplink compressions, error feedback and asynchrony. Using gradients at randomly perturbed points can also be seen as a form of randomized smoothing [27], point we discuss in Appendix A.2.
2.2 The randomization mechanism, Rand-MCM
In this subsection, we deseribe the key feature introduced in Rand-MCM: randomization. It consists in performing an independent compression for each device instead of performing a single one for all of them. As consequence, each worker holds different model centered around the global one. This introduces some supplementary randomness that stabilizes the algorithm. Formally, we will consider N mutually independent compression operators Cawn, instead of a single one Cawns and the central server will send to the device i at iteration k + 1 the compression of the difference between its model and the local memory on worker i: Cdwn, modification are discussed in Section 4.
Hi). The tradeoff's associated with this
The pseudocode of Rand-MCM is given in Algorithm 1 in Appendix A. It incorporates all components described above: 1) the bidirectional compression, 2) the model update using the non-degraded point, 3) the two memories, 4) the up and down compression operators, 5) the randomization mechanism.
3 Assumptions and Theoretical analysis
We make standard assumptions on F Rdd + TR. We first assume that the loss function F is smooth. Assumption 2 (Smoothness). F is twice continuously differentiable, and is L-smooth, that is for all vectors W1, W2 in R4: [[V)( - (1 < L|[w] - well
Results in Section 3 are provided in a convex, strongly-convex and non-convex setting.
Assumption 3 (Strong convexity). F is j-strrongyy convex (or convex Jf = 0), that is for all vectors W1, W2 in dd; F(w2)= 2 F(w1) + (w2 - w.)'VF((.) + I|w - w 113.

---

Next, we present the assumption on the stochastic gradients.
Assumption 4 (Noise over stochastic gradients computation). The noise over stochastic gradients for a mini-batch size b, is uniformly bounded: there exists a constant a E RR,,, such that for all in N, for all i in [1, and for all w in E we have: Elllgg (w) - VF(()))( ( [|²] - o²/
We here provide guarantees of convergence for MCM. MCM incorporates designed to handle heterogeneous workers. To highlight our main contributions, that concerns the downlink compression, we present the results in the homogeneous setting, that is with F; F3 and aup = O. Similar results (almost identical, up to constant numerical factors) in to the heterogeneous setting are described in Appendix G. Experiments are also performed on heterogeneous workers. We provide here convergence results in the strongly-convex, then convex case.
uplink memory term,
Notations and settings. For k in N. we denote T4 = || H H and define V/2 = Bl|lux w.1l"] + 32 Wn,
E[ which serves as Lyapunov function. V42 is composed of two terms: the first one controls the quadratic distance to the optimal model, and the second controls the variance of the local models viz. For both theorems, we choose Odwn (8wlaw))
We denote
((7)= = (1 + wap) (1 + 64>Taaqmm)
Limit learning rate: There exists maximal learning rate to ensure convergence. More specif- ically, we define "max == min( dww TTT 7max). where I == (2L (1 + wup/N)) corre- sponds to the classical constraint on the learning rate in the unidirectional regime [see 23, 24], dwn :- (8Lwawn) is a similar constraint coming from the downlink compression, and Tmax
Tmax = (8v2Lwawm v SwJdwn + Wup/N) -1 is combined constraint that arises when control- ling the variance term Y. 1 Overall, this constraints are weaker than in the "degraded" framework [19, 24], in which T < (8L(1 + wawn) + Wup/N)) Especially, in the regime in which dup.dwn > oc and Wdwn = Wup =: w. the maximal learning rate for MCM is (T==3/3)-1 while it is (Lw²)-² in [19, 24]. Our Ymax is thus larger by a factor vw, see Table 2. We define such that Tmax = (2L)-
Theorem (Convergence of MCM in the homogeneous and strongly-convex case). Under Assump-
tions to 4 with μ > O, for k in N. for any sequence (Tk) S "/mxx have:
V& S (1 - 7h/) MB (F[[F(K-1)) - F(w.)] +
(4)
Nb
Consequently, (1) if = 0 (noiseless case). for 7Ik = "max we recover a linear convergence rate: - 1ml=maa)))VV (2) > 0, taking for all K in N. "KK = 22/(((K + L),
E[[lws- - w.11 &
for the weighted Popper- average WK = =EK, A EE dE. with d == (7k-1)
11 + 2L
(1+ 6ALwaWn In(KK + [i)
E [F((K) - F(w.)) S 4uk² |wo
w.112 -w,,
μKNb
HK
(5)
Limit Variance (Equation (4)). For constant 7, the variance term (i.e., term proportional to o²) The impact of the downlink compression is attenuated by a factor 7 As 7 decreases, this makes the limit variance similar to the one of Diana, i.e., without downlink compression [23, Eq. 16 in Th. 2] and much lower than the variance for previous algorithms using double compression for which the variance scales quadratically with the compression constants as 7 (1 whp) + wdww)/N: (1) for Dore, see Corollary 1 in Liu et al. [19] (who indicate (1 - p) 2 (1 + Wap/ (N)( wdwn)) D), (2) for Artemis see Table 2 and Th. 3 point 2 in [24], (3) for [11], see Theorem 1.1. (with >D' a >0*
in Equation (4) is upper bounded by 3²00 No (1 (1+ (1 + 64
+ wwp) (1 + wdwn) )/N).
Bound 5 has quadratic dependence Wawn, but the corresponding term is divided by an extra factor K, the number of iterations. For example in experiments, for w&a using quantization with s = 20, we have wawn ~ 17, and after only 50 epoch with batch size b 12, we have K 2500. Hence, the term w² K is vanishing through iterations and we asymptotically recover a rate of convergence equivalent to algorithms using unidirectional compression.
'The dependency in ~ 3/2 is similar to the one obtained by Horváth et al. [15] in unidirectional compression in the non-convex (Theorem 4).
5

---

Convergence and complexity: With decaying sequence of steps, we obtain convergence rate scaling O(K-²) in Equation (5), without dependency on the wawn in the dominating term. which only appears in faster decaying terms scaling as K K-2 The iteration complexity (i.e., number of iterations to achieve expected error) is thus at first order Oz-so( O (( Again, this matches the complexity of Diana [15, see Theorem and Corollary 1] and is smaller by a factor + wdwn than the one of Artemis, Dore, DIANAsr-DQ (see Corollary 1.1. in [11]). Next, give convergence result in the convex case.
McNb
Theorem (Convergence of MCM, convex case). Under Assumptions to 4 with = 0. For all
k > 0, for any S "/max. we have. for Ty = Ei=o
B ((wk-11)) F(w.)] S V V/ 777)
Vo
7a 3 p())
((F(())) - F.] S
(6)
Nb
pk
Nb
Consequently, for in N large enough, a step-size 7
(I+wup -K we have:
100 w.ll arw..l111 IINbb
[(F(wK) - F.] s 21 Ww
w.ll wap +O(K-1).
(7)
Nbk
Moreover of (noiseless case), we recover a faster convergence: E[F(WK) O(K-)(K)))) Limit Variance (Eq. (6)). The variance term identical to the strongly-convex case.
Convergence and complexity (Equation (7)). The downlink compression constant only appears in the second-order term, scaling 1/K. In other words, the convergence rate is equivalent to the
convergence rate of Diana, in the non-strongly-convex. As K increases, this complexity scales as independently of the downlink compression. Again, for previous algorithms with double
(1+w)g))
ne
compression the complexity is least O (1+mup)[+uaa (see Corollary I.2 in [11]).
ne.
Control of the variance the local model.
We here present the backhone Lemma of MCM's s proof. It allows to control the variance of the local model [E[] Wx - wx|] [ws]] (which is upper-
Insu/Fion) Fivil
(vo) F(n.]l
(inn)
bounded by wdw. [[| (xx) and to build the Lyapunov function defined in Theorems and 2.
-2
14:34
This result highlights the impact of the downlink memory term. Without memory, i.e., with Odwa O, the variance of the local model | - wg I| increases with the number of iterations. On the other hand, if wawn is too large (close to 1), this variance diverges. This behavior is illustrated on two real datasets on Figure 1. This phenomenon is similar to the divergence observed in frameworks involving error feedback, when the compression operator is not contractive.
Number poooos
300
4541
002
Number of pe00ees
300
000
Figure 1: Comparing MCM on two datasets with three other algorithms using non-degraded update, y 1/L. Artemis- stands for Artemis with a non-degraded update.
Theorem 3. Consider the MCM update in eq. (2). Under Assumptions I, 2 and with μ 0. if S (8widwn T.)- and a & (Aw'ww) -1, then for all is in N:
[IVF( ||3 27 02 wap)
E [TA] (1-
Odwn
JE [ +2,
Wup
2
Olawn
Nb
This bound provides recursive control on TR. Beyond the adwn) contraction, the bound comprises the squared-norm of the gradient at the previous perturbed iterate, and a noise term.
Summary of rates. In Table 2, summarize the rates and complexities, and maximal learning rate for Diana, Artemis, Dore and MCM. For simplicity, we ignore absolute constants, and provide asymptotic values for large waps Wawn, and complexities for e - 0.
Proof in the heterogeneous case. To extend Theorems to in the heterogeneous setting for convex objective (Appendix G), we assume that there exists constant B in R,, s.t.:

---

Table 2: Summary of rates the initial condition, limit variance, asympt. complexities and Yimax-
Problem
Diana
Attemis, Dore
MCM. Rand-MCM
Liimax Oc
1/(1 + wap)
1/(1 + 21p +1++ wowe))
1/(1 wann) V wop A A1(11+ wup)
Lim, var. or 7202 /ux
(1 wup)
(1 - wap)(1 + manu))
+ u1 + g1a0gm))
Str-ccovvex
Rute on init, cond. (SC)
(1 -1-10 paye
(1 - Jui+
(1 - w1)"
Complexity
(1 + Wpp
(1 Hamm)( (1 + ManN
+ Hupl/peN
Convex
Complexity
(Mkp + 1)/c2
(1 w1g)(1 wawe)//?
(usp + 11/62
VF((w))) where for all i in []. This term is recursively controled [23, 24] and combined into the Lyapunov function.
EN (w.))l = B², We further define Ex = A E Iig
N
N
Proofs. To convey the best understanding of the theorems and the spirit of the proof, we introduce a Ghost algorithm (impossible to implement) in Appendix D.I. A sketch of the proof describes the main steps in the case of Ghost, those steps are similar for MCM. Fundamentally, our proof relies on a tight analysis, related to perturbed iterate analysis [21]. Proofs of Theorems I to 3 are given in Appendix E. Th. S11 Appendix E,4 ensures convergence for non-convex F. Note that the proof for non-convex follows a different approach than the one in Theorems 1 and 2.
As mentioned in the introduction, our analysis of perturbed iterate in the context of double com- pression opens new directions: in particular, it opens the door to handling different model for each worker. In the next section, we detail those possibilities, and provide theoretical guarantees for Rand-MCM, the variant of MCM in which instead of sending the same model to all workers, the compression noises are mutually independent.
Remark 4 (Communication budget). How to split given communication budget between uplink and downlink to optimize the convergence is an open question which is intrinsically related to the situation. Indeed it depends
many factors like the selected operators of compression, the upload/downlink speed or the number of participating workers at each iteration. However, our approach provides some insights on this question. Because asymptotically the impact of double compression is marginal, for a fixed budget, Theorem suggests to strongly compress on the downlink direction (which leads large Wdwn), but perform weaker compression in the uplink direction.
4 Extension to Rand-MCM
4.1 Communication and convergence trade-off's
In Rand-MCK, we leverage the fact that the compressions used for each worker need not to be identical. On the contrary, it is possible consider independent compressions. By doing so, we reduce the impact of the downlink compression.
The relevance of such a modification depends on the framework: while the convergence rate will be improved, the computational time can be slightly increased. Indeed, N compressions need to be computed instead of one: however, this computational time is typically not bottleneck w.r.t. the communication time. A more important aspect is the communication cost. While the size of each message will remain identical, different message needs to be sent to each worker. That is, go from a "one to N configuration to N "one to one" communications. While this is a draw drawback, it is not issue when the bandwidth/rranseer time are the bottlenecks, as Rand-MCH will result in better convergence with almost no cost. Furthermore, we argue that handling worker dependent models is essential for several major applications. Rand-MCM can directly be adapted to those frameworks.
Worker dependent compression. A first simple situation is the case in which workers are allowed to choose the size (or equivalently the compression level) of their updates.
2. Partial participation (PP). Similarly, having N different messages to send to each worker may be unavoidable in the case of partial participation of the workers. This is a key feature in Federated Learning frameworks [22]. In the classical distributed framework (without downlink constraints) is easy to deal with it, as each available worker just queries the global model to compute its gradient on it [see for example 14]. On the other hand, for bidirectional compression, to ensure that all the local models match the central model, the adaptation to partial participation relies on a synchronization step. During this step, each worker that has not participated the last S steps receives the last S corresponding messages as long as it costs less to send this sequence than a full uncompressed model. This is described in the deseription of the adaptation to partial participation in [24], in the remark preceding Eq. (20) in [26] and by Tang et al. [33, v2 on arxiv for the distributed case], who use
7

---

buffer. On the contrary, Rand-MCM naturally handles different model, memory and update per worker. The adaptation to partial participation is thus straightforward. Though theoretical results are out of the scope of this paper, we provide experiments on PP in Appendix B.1.1 and fig. 4.
One drawback is the necessity store the N memories (EN) instead of one, which results in an additional memory cost. To circumvent this issue we propose two independent solutions. 1) Keep and use single memory H N- Σi= H (as suggested in [24]). It is then necessary to periodically reset the local memories H on all workers to the averaged value H3 (rarely enough not to impact the communication budget). This is illustrated in fig. 2) Use Rand-MCM with an arbitrary number of groups G' < N of workers. In each group 9g. 9 E [G], all workers share the same memory (Hg) and receive the same update Cawn.g (1 H We call this algorithm Rand-MCM-G.
clients). Another business advantage of MCM and Rand-Mo MMMM is that providing degraded models to the participants can be used to guarantee privacy, or to ensure the workers participate in good faith, and not only to obtain the model. This issue of detecting ill ill-intentioned clients (free-rider)) that want to obtain the model without actually contributing has been studied by Fraboni et al. [10].
Remark 5 (Protecting the global model from monest-but-cuufe
4.2 Theoretical results
In this Section, we provide two main theoretical results for Rand-MCM. First Theorem 4 ensures that the theoretical guarantees are least as good for Rand-MCM as for MCM. Then, in Theorem 5, we provide convergence result for both MCM and Rand-MCM in the case of quadratic functions.
Theorem 4. Theorems 1 to 3 are valid for Rand-MCH and Rand-MCH- C.
The improvement in Rand-MCM comes from the fact that we are ultimately averaging the gradients at several random points, reducing the variance coming from this aspect. The goal is obviously to reduce the impact of wdwn. Keeping in mind that the dominating term in the rate is independent of wäwn, we can thus only expect to reduce the second-orde term. Next, the uplink compression noise increases with the variance of the randomized model, which will not be directly reduced by Rand-Mo As consequence, we only expect the improvement to be visible in the part of the second-order term that does not depend on Wup (that is, the effect would be the most significant if Wup is small or 0).
This intuition is corroborated by the following result, in which we show that the convergence im- proved when adding the randomization process for quadratic function. Extending the proof beyond quadratic functions is possible, though requires an assumption on third or higher order derivatives of F (e.g., using self-concordance [4]) to control of E. [[/V F(Wx-1) - F(V ))]l wx-1].
Theorem 5 (Convergence in the quadratic case). Under Assumptions 1 to 4 with 0. if the function is quadratic, after running K > O iterations, for any 7 S Tmax and we have
Vu
7 (x)
[[F(wK) - F.] <
+
K
Nb
with (R)( (1 + Wup) (1 + 1. ( Rand-MCH- and C- for MCM.
and C N for Rand-KCM, C G
This result derived in Appendix F. We can make the following comments: (1) The convergence rate for quadratic functions is slightly better than for smooth functions. More specifically, the right hand term in & is multiplied by an additional 7 ( + Shp (w.r.t. Theorem 2), which is decaying at the same rate as y Besides, the proof for Rand-MCM substantially modified, as E. [ F ( an unbiased estimator of V ((Wx-1). (2) Moreover, the randomization in Rand (resp.
further reduces by a factor N (resp. G) this term. Depending on the relative sizes of Wup and N, this can lead to significant improvement up to factor of N. In practice the impact of Rand-MCM is noticeable, as illustrated in the following experiments.
5 Experiments
In this section, we illustrate the validity of the theoretical results given in the previous section on both synthetic and real datasets, on (1) least-squares linear regression (LSR), (2) logistic regression (LR), and (3) non-convex deep learning. We compare MCM with classical algorithms used in distributed settings: Diana, Artemis, Dore and of course the simplest setting SGD, which is the bascline.
8

---

loc, (.Fo)) F(s..)
In (Pag) Plas.
lec Toen lon)
22
Jen,Uleii loee
-0.3
-10
10.0
10
10
DC
Conmmnecatttd Stts
Canman indill
(d)
FE-MNIST with
(a) 0² #0,7=
(b) -0,
(c) MNIST with CNN
CNN
Figure 2: Convergence neural networks.
In these experiments, we provide results on the log of the excess loss F(wx) F., averaged 5 runs (resp. 2) in convex settings (resp. deep learning), with errors bars displayed on each figure (but not in the "zoom square"), corresponding to the standard deviation of logio (F (F(w): F.). On Figure 3, the X-axis is respectively the number of iterations and the number of bits exchanged.
Each experiment has been run with N = 20 workers using stochastic scalar quantization [3], w.r.t. 2-norm. To maximize compression, we always quantize on single level (s 2"), unless for PP (s = 2 and neural network (the value of depends on the dataset).
We used 9 different datasets.
One toy dataset devoted to linear regression in an homogeneous setting. This toy dataset allows to illustrate MCM properties in simple framework, and in particular ilustrate that when o² 0, recover a linear convergence", see Figure 2b.
Five datasets commonly used in convex optimization (a9a, quantum, phishing, superconduct and w8a); see Table S1 for more details. Experiments were conducted with heterogeneous workers obtained by clustering (using 7SNE [20]) the input points.
Four dataset in a non-convex settings (CIFAR10, Fashion-MNIST, FE-MNIST, MNIST); see Table $2 for more details.
All experiments are performed without any tuning of the algorithms. (e.g., with the same learning rate for all algorithms and without reducing it after certain number of epochs). Indeed, our goal is to show that our method achieves a performance close to the inddrectionallcomprssiii framework (Diana), while performing an important downlink compression. More details about experiments be found in Appendix B.
On Figure 3, we display the excess loss for quantum and a9a w.r.t. the number of iteration and number of communicated bits. The plots of phising, superconduct and w8a are not provided but can be found on our github repository. We only report their excess loss after 450 iterations in Table 3.
Table 3: MCM- convex experiments, is the batch size
Excess loss after 450 epochs
SCD
Diana
MCM
Dore
Ref
a9a (b = 50)
33.5
-2.7
-2.7
-..8
quantum (b = 400)
33.4
-3.2
-3.2
-2.6
[7]
phishing 50)
-3.7
-3.5
-3.4
-2.7
[8]
superconduct (b = 50)
-1.6
-1.6
-1.55
-1.45
[13]
w8a = 12)
3.5
-3.0
-2.5
-1.75
[8]
Compression
uni-dir
bi-dir
bi-dir
Saturation level. All experiments are performed with constant learning rate to observe the bias (initial reduction) and the variance (saturation level) independently. Stochastic gradient descent results in fast convergence during the first iterations, and then reaches saturation level proportional to a² Theorem states that the variance of MCM is proportional to wup- this is experimentally observed on Tables 3 and 4 and figs. 2 and MCM meets Diana while Artemis s and Dore saturate at a higher level (scaling as Wup X Wawn). These trade-off's are preserved with optimized learning rates.
given
2 EEven stronger, show in experiments that recover linear rate if we have a. = 0 (the noise over stochastic gradient computation at the optimum point w.).

---

(Pa)) Plo.3
Je. (P Plo.l
36 of 1oo
-3
150
330
020
300 430
10'
Number of pooes cn data
Commeneaated brs
Number poicos deta
Oommonmottdd bots
(a) Quantum in Hiter.
(b) Quantum in #bits
(c) A9A in fiter.
(d) A9A in #bits
Figure 3: Experiments real dataset with 1/L, quantization with
1, LSR (a.b), LR (c.d).
Linear convergence when o² O. The six algorithms present a linear convergence when x² 0. This is illustrated by Figure 2b: we ran experiments with full gradient descent. Note that in these settings MCM has a slightly worse performance than other methods; however, this slow-down compensated by Rand-MCM.
-2
-3
Impact of randomization. The impact of randomization noticeable on Figures 2b and S5b. Randomization helps stabilise convergence of it reduces the variance of the rums and when x² = 0, it performs identically SGD. Figure illustrates the impact of using a single memory, instead of N, to alleviate the memory cost in the PP setting (Subsection 4. 4.1), with without periodic reset. Without reset, performance are slightly degraded, but with it, we recover previous results.
paaa takm
Comceriisttdd
Figure 4: Rand-MCM (PP) on quantum with single memory (s 2).
Deep learning. Table 4 and figs. 2c and 2d illustrate experiments with neural networks, details dataset settings and networks architecture are given in Appendix B.2. Again, MCM meets Diana rates stated by Theorem S11 (theorem in the non-convex case).
Table 4: Accuracy and train loss in non-convex experiments, detailed settings can be found in Table $2
Algorithm
MNIST
Fashion MNIST
FE-MNIST CIFAR-I0
Accuracy after 300 epochs
SGD:
99.0%
92.4%
99.0%
69.1%
Diana:
98.9%
92.4%
98.9%
64.0%
MCM:
98.8%
90.6%
98.9%
63.5%
Artemis:
97.9%
86.7%
98.3%
54.8%
Dore:
97.9%
87.9%
98.5%
56.3%
Train loss after 300 epochs
SGD:
0.025
0.093
0.026
0.909
Diana:
0.034
0.141
0.031
1.047
MCM:
0.033
0.209
0.030
1.096
Artemis:
0.075
0.332
0.052
1.342
Dore:
0.072
0.300
0.048
1.292
Overall, these experiments show the benefits of MCM and Rand-MCM, that reach the saturation level of Diana while exchanging at 10x to 100x fewer bits. More experiments with partial participation for Rand-MCM given in Appendix B.1.1. All the code is provided github repository.
Conclusion
In this work, we propose new algorithm to perform bidirectional compression while achieving the convergence rate of algorithms using compression in single direction. One of the main application of this framework is Federated Learning. With MCM stress the importance of degrading the global model. In addition, we add the concept of randomization which allows to reduce the variance associated with the downlink compression. The analysis of MCM is challenging as the algorithm involves perturbed iterates. Proposing such an analysis is the key to unlocking numerous challenges distributed learning, e.g., proposing practical algorithms for partial participation, incorporating Dewacy-preserving schemes after the global update is performed, dealing with local steps, etc. This approach could also be pivotal in non-smooth frameworks, as can be considered as a weak form of randomized smoothing.
10

---

Acknowledgments
We would like to thank Richard Vidal, Lacticia Kameni from Accenture Labs (Sophia Antipolis, France) and Eric Moulines from École Polytechnique for insightful discussions. This research was supported by the SCAJ: Stutistics and Computation for AI ANR Chair of research and teaching in artificial intelligence, by Hi!Paris, and by Accenture Labs (Sophia Antipolis, France).
References
[1] Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg. Rajat Monga, Sherry Moore, Derek G. Murray, Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: system for large-scale machine learning. In Proceedings of the 12th USENIX conference on Operating Systems Design and Implementation, OSDI 16, pages 265-283, USA, November 2016. USENIX Association. ISBN 978-1-931971-33-1.
[2] Naman Agarwal, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Brendan McMahan. cpSGD: Communication-efficee and differentially private distributed SGD. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Advances in Neural Information Processing Systems 31, pages 7564-7575. Curran Associates, Inc., 2018.
and R. Garnett, editors,
[3] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication-Efffieee SGD via Gradient Quantization and Encoding. Advances in Neural Information Processing Systems, 30: 19:19-79720 2017.
[4] Francis Bach. Self-concordant analysis for logistic regression. Electronic Journal of Statistics, 4(none):384-411 January 2010. ISSN 1935-7524, 1935-7524. doi: 11214/09-EJS522 Publisher: Institute of Mathematical Statisties and Bernoulli Society.
[5] Léon Bottou. Large-Scale Machine Learning with Stochastic Gradient Descent. In Yves Lechevallier and Gilbert Saporta, editors, Proceedings of COMPSTAT'2010, pages 177- 186, Heidelberg, 2010. Physica-Verlag HD. ISBN 978-3-7908-2600 2600-3... 19883-7700-26660
doi: 10.1007/
16.
[6] Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H. Brendan McMahan, Virginia Smith, and Ameet Talwalkar. LEAF; Benchmark for Federated Settings. arXiv:1812.01097 [cs, stat], December 2019, arXiv: 1812.01097.
[7] Rich Caruana, Thorsten Joachims, and Lars Backstrom. KDD-Cup 2004: results and analysis. ACM SIGKDD Explorations Newsletter, 6(2):95-108, December 2004. ISSN 1931-0145. doi:
10.1 1,.114///444456. 1046470.
[8] Chih-Chung Chang and Chih-Jen Lin. LIBSVM: library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2(3):27:1-27:27, May 2011. ISSN 2157- 6904. doi: 10. 145/1961 (89.1966 199.
[9] Igor Colin, Aurelien Bellet, Joseph Salmon, and Stéphan Clémençon. Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions. International Conference on Machine Learning, pages 1388 1396. PMLR, June 2016. ISSN: 1938-7228.
[10] Yann Fraboni, Richard Vidal, and Marco Lorenzi. Free-rider attacks on model aggregation in federated learning. In International Conference on Artificial Intelligence and Statistics, pages 1846-1854. PMLR, 2021.
[11] Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtarik. Linearly Con- verging Error Compensated SGD. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 20989. Curran Associates, Inc., 2020.

---

[12] M. Grubb. Communication Energy efficiency and economic fallacies. Energy Policy, 18(8): 783-785, October 1990. ISSN 0301-4215. doi: 10.1016/0301 000160000000-1155099900000---030
[13] Kam Hamidich. A data-driven statistical model for predicting the critical temperature of superconductor. Computational Materials Science, 154:346-35, November 2018. ISSN 0927-0256. doi:
[14] Samuel Horváth and Peter Richtárik. A Better Alternative to Error Feedback for Communication- Elficient Distributed Learning. arXiv:2006. 1077 [cs, stat], June 2020. arXiv: 2006.11077.
[15] Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sehastian Stich, and Peter Richtárik. Stochastic Distributed Learning with Gradient Quantization and Variance Reduction. arXiv: 1904.0990..51111 15 [math], April 2019. arXiv: 1904.05115.
[16] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurelien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D' D'Oliveira, Salim EI 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ý, Aleksandra 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, Pranceth Vepakomma, 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.0497 [cs, stat], December 2019. Xiv: 1912.04977.
[17] 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.
[18] 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.
[19] Xiaorui Liu, Yao Li, Jiliang Tang, and Ming Yan. A Double Residual Compression Algorithm for Efficient Distributed Learning. In International Conference on Artificial Intelligence and Statistics, pages 133-143, June 2020. ISSN: 1938-7228 Section: Machine Learning.
[20] Laurens der Maaten and Geoffrey Hinton. Visualizing Data using t-SNE. Journal of Machine Learning Research, 9(Nov):2579-22 2606, 2008. ISSN ISSN 1533-7928.
[21] Horia Mania, Xinghao Pan, Dimitris Papailiopoulos, Benjamin Recht, Kannan Ramchandran, and Michael I. Jordan. Perturbed Iterate Analysis for Asynchronous Stochastic Optimization. arXiv:1507.06970 [cs, math, stat], March 2016. arXiv: 1507.06970.
[22] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication Efficiiet Learning of Deep Networks from Decentralized Data. Artificial Intelligence and Statistics, pages 1273-1282. PMLR, April 2017. ISSN: 2640-3498.
[23] Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed Learning with Compressed Gradient Differences. 1901v:1011.090 [cs, math, stat], June 2019. arXiv: 1901.09269.
[24] Constantin Philippenko and Aymeric Dieuleveut. Artemis: tight convergence guarantees for bidirectional compression in Federated Learning. (1X1v:2006.1459 [cs, stat], November 2020. arXiv: 14591.
[25] Herbert Robbins and Sutton Monro. A Stochastic Approximation Method. Annals of Math- ematical Statistics, 2203):40-4077 September 1951. ISSN 0003-4851, 2168-8990. doi: 10.1114aams/111772990 Number: Publisher: Institute of Mathematical Statistics.
12

---

[26] Felix Sattler, Simon Wiedemann, Klaus-Robert Müller. and Wojciech Samek. Robust and Communication- Efffuiication-Effcient Federated Learning From Non-i..d Data. IEEE Transactions on Neural Networks and Learning Systems, pages 1-14, 2019. ISSN 2162-2388. doi:
10.1 and Learning Systems.
Conference Name: IEEE Transactions on Neural Networks
[27] Kevin Scaman, Francis Bach, Sebastien Bubeck, Laurent Massoulié, and Yin Tat Lec. Optimal Algorithms for Non-Smooth Distributed Optimization in Networks. Advances in Neural Information Processing Systems, 31:2740-2749) 2018.
[28] Frank Seide and Amit Agarwal. CNTK: Microsoft's Open-Source Deep-Learning Toolkit. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '16, page 2135, New York, NY, USA, August 2016. Association for Computing Machinery. ISBN 978- 177-1-45003-422-22 doi: 10. 10.114///39972222455999
[29] Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training speech dons. In Fifleenth Annual Conference of the International Speech Communication Association. Citeseer, 2014.
[30] Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for SGD with delayed gradients and compressed updates. Journal of Machine Learning Research, 21:1-36, 2020.
[31] 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
[32] Hanlin Tang. Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. $D^2S: Decentralized Training over Decentralized Data. International Conference on Machine Learning, pages 4848 4856. PMLR, July 2018. ISSN: 2640-3498.
[33] Hanlin Tang, Chen Yu, Xiangru Lian, Tong Zhang, and Ji Liu. DoubleSqueeze: Parallel Stochas- tic Gradient Descent with Double-pass Ftroo-Compensated Compression. In International Conference Machine Learning, pages 6155-6165. PMLR, May 2019. ISSN: 2640-3498.
[34] Paul Vanhaesebrouck, Aurélien Bellet, and Mare Tommasi. Decentralized Collaborative Learn ing of Personalized Models over Networks. In Artificial Intelligence and Statisties, pages
509- 517. PMLR, April 2017. ISSN: 2640-3498.
[35] Jianqiao Wangni. Jialei Wang, Ji Liu, and Tong Zhang. Gradient Sparsification for Communication iittiiccatton--fffiennnt Distributed Optimization. Advances in Neural Information Pro- cessing Systems, 31:1999-1309, 2018.
[36] Jiaxiang Wu, Weidong Huang, Junzhou Huang, and Tong Zhang. Error Compensated Quantized SGD and its Applications to acrge-scale Distributed Optimization. In International Conference on Machine Learning, pages 5325-5333. PMLR, July 2018. ISSN: 2640-3498.
[37] An Xu, Zhouyuan Huo, and Heng Huang. Training Faster with Compressed Gradient. 2008v [cs, stat], August 2020. arXiv: 2008.05823.
[38] Shuai Zheng, Ziyue Huang, and James Kwok. Communication- Distributed Blockwise Momentum SGD with ErrorFeeebbck.. In Advances in Neural Information Processing Systems, volume 32, Curran Associates, Inc., 2019.
13


Reviews:
[{"review_id": "cQAxq1fd7iW", "reviewer": "Reviewer_NENJ", "summary": "This paper proposed to compress model different for improving downlink compression. The theoretical analysis on convex problems shows that the dominant term does not depend on the compression error of the downlink, thus improving upon on the existing results on two-way compression.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the idea is interesting and the paper is well written. However, I have a few concerns:\n\n1. One motivation of the paper is that the downlink communication is cheaper than the uplink one. This depends on the actual network topology. If we consider a mesh topology, recursive doubling allows us to perform broadcasting faster.  But if we consider a general server-worker bipartite graph (Jiang, Yimin, et al., 2020), the uplink and downlink communication can be overlapped and the downlink one is not more efficient than the uplink one.\n\n2. The theories of  Zheng et al. [41] and Tang et al. [36] are for nonconvex problems. What is the convergence result of the proposed method for nonconvex objective? Can we still remove \\omega_{dwn} from the dominant term? And, Corollary 2 in Tang et al. [36] also shows that \\omega_{up/dwn} is in a higher order term 1/T^{2/3}.\n\n3. Bound (5) has a quadratic dependency on \\omega_{dwn}, which is worse than the bound for two-way compression.\n\n4. Given a fixed communication budget, how do we distribute it over uplink and downlink to optimize the convergence rate?\n\n5. How does the distribution of the difference of gradient differ from the one of model? And, how does this difference affect the choice of the uplink and downlink compressors?\n\n6. What does d=20 mean in Figure 2?\n\n7. The experimental setup is weak, i.e., synthetic dataset and small image classification problems. \n\nJiang, Yimin, et al. \"A Unified Architecture for Accelerating Distributed {DNN} Training in Heterogeneous GPU/CPU Clusters.\" OSDI. 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "ayvZ24py9WL", "reviewer": "Reviewer_TFWi", "summary": "This paper proposed a new method: MCM for bidirectional compression in federated learning. Convergence analysis showed that linear convergence can be achieved with the proposed method. Empirical results also show the method could achieve non-trivial performance with high compression rate.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I'm a bit concerned with the novelty of this work. Compression with memory method has been previously proposed, but only in the uplink case. This paper seems simply applying it during downlink and analyze the convergence behavior. Hence, I wonder that the contribution is a bit incremental here.\n\nIn terms of the experiment section, the compression operator being used is specifically s-quantization. However, there are other naive unbiased compression methods like random masking. To show the generality of this method, multiple compression operators for C_up and C_down should also be presented in the main experiment section. Other than that, biased compression methods like top-k masking without using MCM are also interesting to compare with.\n\nIn practice, people would also care about generalizability as well as convergence. Hence, I suggest adding test metrics(loss/accuracy) for cifar and mnist to compare the performance of MCM with baselines.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations and suggestions are listed in the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5hr"}, "extra_text": {}}, {"review_id": "ZPUqI557kkY", "reviewer": "Reviewer_VLMx", "summary": "The paper proposes a bidirectional compression algorithm for parameter-server-based distributed training.\nTwo variants, MCM and Rand-MCM, are proposed to achieve the same improvement as the uplink-compression-only compression algorithm, where the downlink-compression-only impacts local models while the global model is preserved.\nThe Rand-MCM also introduces the concept of (simulated) random smoothing via model compression.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Advantages\n* The paper has been written well and is theoretically sound.\n* The use case for introducing downlink and uplink compression is critical and could have significant consequences.\n* The concept of using different compressed worker models to perform random smoothing is intriguing.\n\n\n### Disadvantages\n1. The paper's convergence analysis results were not fully validated (through some numerical results).\n    1.  The memory mechanism is crucial for controlling the variance of the local model, but I cannot find a detailed (empirical) discussion related to $\\alpha_{\\text{dwn}}$. Figure 1 is insufficient to justify the trade-off of the different hyper-parameter choices; some numerical results are required here to justify the tightness of the convergence rate.\n    2. Similar issues appeared in the $\\omega_{\\text{up}}$. Hyper-parameters associated with different levels of $\\omega_{\\text{up}}$ should be included, and studied, for example, in terms of complexity.\n    3. It is a good idea to use a constant learning rate to observe the bias and variance independently. However, the current results in Figures 2 & 3 are hard to tell the difference, e.g., (1) it is difficult to determine whether all curves enter the saturation level or not due to the log-scale visualization, (2) why the Rand-MCM results are omitted in Figure 2c & d, and (3) for MCM results in Figures 2d & 3d, the reached training loss values are far behind other baselines and I am not sure if prolonging the training period can close this gap or not. It is necessary to provide a more detailed illustration.\n    4. The numerical evaluations only take into account a fixed number of workers and a fixed level of compression/quantization. Because of the limited experimental setups, understanding the empirical behavior of the proposed algorithms, as well as the alignment between numerical results and convergence analysis, is difficult.\n2. The concept of using the perturbed model in distributed training to perform random smoothing is not novel; the authors should at the very least include a brief discussion with [1, 2, 3, 4]. It would be great if the authors could use the insights of improved gradient Lipschitz in [5] to further justify the gain of their proposed Rand-MCM algorithm.\n\n### Reference\n1. SmoothOut: Smoothing Out Sharp Minima to Improve Generalization in Deep Learning, https://arxiv.org/abs/1805.07898\n2. Gradient Noise Convolution (GNC): Smoothing Loss Function for Distributed Large-Batch SGD, https://arxiv.org/abs/1906.10822\n3. Extrapolation for Large-batch Training in Deep Learning, https://arxiv.org/abs/2006.05720, ICML 2020\n4. Sharpness-Aware Minimization for Efficiently Improving Generalization, https://arxiv.org/abs/2010.01412, ICLR 2021\n5. Randomized smoothing for stochastic optimization, https://arxiv.org/abs/1103.4296, SIAM Journal on Optimization.\n\n\n=== review update ===\nI am happy with the responses and I will raise my score to 6.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please check the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "7Q8pQvsIaEv", "reviewer": "Reviewer_9w9P", "summary": "The paper proposes MCM ~ algorithm to perform bidirectional compression in distributed setting. The authors claim similar convergence guarantees as vanilla setting. \nThey introduce the notion of sending different models to different clients while keeping the global model preserved. \n", "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": "Overall, the presentation has cyclomatic complexity. Its hard to read and the main idea is not clear at a fast glance. I would strongly encourage improving the presentation and writing.\n\nFor example, using algorithmic blocks would greatly help. \n\nNovelty:\nI have concerns regarding the novelty of the algorithm. The idea of error feedback is leveraged in both client and server to deal with bidirectional compression degradation. While client EF is common, server EF is less common but not new [1] \n\nAlso, using EF at both end seems like a natural approach and not very novel or insightful .\n\nThe main contribution of the paper is thus the analysis. However, I find the analysis straightforward extensions of EF-SGD [2] proof technique. \n\nExperiments :\nThe experiments are tiny. MNIST , using simple toy like datasets \nI would strongly encourage performing experiments on sufficiently large models and more sophisticated datasets. \n\nThe deep learning exp in appendix show S11(a) slower convergence.\n\nTime Complexity:\nNote that computing the server memory etc has computational overhead and it would be great to run experiments wrt wall clock time. \nAlso, a precise asymptotic complexity analysis might be useful \n\n[1] https://arxiv.org/pdf/2106.08882.pdf\n[2] https://arxiv.org/abs/1901.09847", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See Above ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "-K-tw4dNM9o", "reviewer": "Reviewer_T3QV", "summary": "In this paper, the authors propose MCM, a new algorithm achieves bidirectional compression with better convergence rate. Theoretical analysis is provided. The empirical results show good performance.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "The paper is well-written. The theorems give detailed analysis in strongly convex, convex, and non-convex cases. The experimental results show that MCM can achieve better convergence when using the same communication overhead as the baselines.\nAlso, I like the idea of calculating the carbon footprint in the appendix.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The experiments are still not large enough. In distributed training, we usually focus on large-scale problems like imagenet. Cifar100 or some NLP tasks are also recommended. However, since I believe that this paper focuses mostly on the theoretical analysis, I don’t think this is a big issue.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work proposes MCM, a method that performs bidirectional (i.e., both uplink and downlink) compression in distributed learning. A benefit of the approach is that it is able to match convergence rates of methods that use compression in only a single direction. The reviewers were generally in agreement that the work was well-written and motivated. However, many of the reviewers were unclear about the novelty of the approach, and there were a significant number of additional experiments included as part of the discussion period (e.g., relating to test metrics, new datasets). I believe the paper will be significantly strengthened if the authors carefully incorporate the discussed changes (specifically, more clearly outlining the main contributions/novelty and including the additional experiments that have been run since the time of submission). Although one reviewer finds the results unsurprising, this view was not shared by others, and I agree with the remainder of the reviewers that this work provides a solid contribution in communication-efficient learning.
Decision: Accept (Poster)