summaries: The paper proposes MCM ~ algorithm to perform bidirectional compression in distributed setting. The authors claim similar convergence guarantees as vanilla setting.  They introduce the notion of sending different models to different clients while keeping the global model preserved.   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. The paper proposes a bidirectional compression algorithm for parameter-server-based distributed training. Two 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. The Rand-MCM also introduces the concept of (simulated) random smoothing via model compression. 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. 
abstractText: 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.
authors.name: Constantin Philippenko
authors.name: Aymeric Dieuleveut
references.authors: 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 Xiaoqiang Zheng
references.title: TensorFlow: a system for large-scale machine learning
references.venue: In Proceedings of the 12th USENIX conference on Operating Systems Design and Implementation,
references.authors: Naman Agarwal Ananda Theertha Suresh Felix Xinnan X Yu Sanjiv Kumar Brendan McMahan
references.title: cpSGD: Communication-efficient and differentially-private distributed SGD
references.venue: Advances in Neural Information Processing Systems
references.authors: Dan Alistarh Demjan Grubic Jerry Li Ryota Tomioka Milan Vojnovic
references.title: QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
references.venue: Advances in Neural Information Processing Systems,
references.authors: Francis Bach
references.title: Self-concordant analysis for logistic regression
references.venue: Electronic Journal of Statistics,
references.authors: Léon Bottou
references.title: Large-Scale Machine Learning with Stochastic Gradient Descent
references.venue: Proceedings of COMPSTAT’2010,
references.authors: Sebastian Caldas Sai Meher Karthik Duddu Peter Wu Tian Li Jakub Konečný H. Brendan McMahan Virginia Smith Ameet Talwalkar
references.title: LEAF: A Benchmark for Federated Settings
references.authors: Rich Caruana Thorsten Joachims Lars Backstrom
references.title: KDD-Cup 2004: results and analysis
references.venue: ACM SIGKDD Explorations Newsletter,
references.authors: Chih-Chung Chang Chih-Jen Lin
references.title: LIBSVM: A library for support vector machines
references.venue: ACM Transactions on Intelligent Systems and Technology,
references.authors: Igor Colin Aurelien Bellet Joseph Salmon Stéphan Clémençon
references.title: Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions
references.venue: In International Conference on Machine Learning,
references.authors: Yann Fraboni Richard Vidal Marco Lorenzi
references.title: Free-rider attacks on model aggregation in federated learning
references.venue: In International Conference on Artificial Intelligence and Statistics,
references.authors: Eduard Gorbunov Dmitry Kovalev Dmitry Makarenko Peter Richtarik
references.title: Linearly Converging Error Compensated SGD
references.venue: Advances in Neural Information Processing Systems,
references.authors: M.J. Grubb
references.title: Communication Energy efficiency and economic fallacies
references.venue: Energy Policy,
references.authors: Kam Hamidieh
references.title: A data-driven statistical model for predicting the critical temperature of a superconductor
references.venue: Computational Materials Science,
references.authors: Samuel Horváth Peter Richtárik
references.title: A Better Alternative to Error Feedback for Communication- Efficient Distributed Learning
references.authors: Samuel Horváth Dmitry Kovalev Konstantin Mishchenko Sebastian Stich Peter Richtárik
references.title: Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
references.venue: [math],
references.authors: Peter Kairouz H. Brendan McMahan Brendan Avent Aurélien Bellet Mehdi Bennis Arjun Nitin Bhagoji Keith Bonawitz Zachary Charles Graham Cormode Rachel Cummings Rafael G.L. D’Oliveira Salim El Rouayheb David Evans Josh Gardner Zachary Garrett Adrià Gascón Badih Ghazi Phillip B. Gibbons Marco Gruteser Zaid Harchaoui Chaoyang He Lie He Zhouyuan Huo Ben Hutchinson Justin Hsu Martin Jaggi Tara Javidi Gauri Joshi Mikhail Khodak Jakub Konečný 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 Praneeth Vepakomma Jianyu Wang Li Xiong Zheng Xu Qiang Yang Felix X. Yu Han Yu Sen Zhao
references.title: Advances and Open Problems in Federated Learning
references.authors: Jakub Konečný H. Brendan McMahan Daniel Ramage Peter Richtárik
references.title: Federated Optimization: Distributed Machine Learning for On-Device Intelligence
references.authors: Zhize Li Dmitry Kovalev Xun Qian Peter Richtarik
references.title: Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization
references.venue: In International Conference on Machine Learning,
references.authors: Xiaorui Liu Yao Li Jiliang Tang Ming Yan
references.title: A Double Residual Compression Algorithm for Efficient Distributed Learning
references.venue: In International Conference on Artificial Intelligence and Statistics,
references.authors: Laurens van der Maaten Geoffrey Hinton
references.title: Visualizing Data using t-SNE
references.venue: Journal of Machine Learning Research,
references.authors: Horia Mania Xinghao Pan Dimitris Papailiopoulos Benjamin Recht Kannan Ramchandran Michael I. Jordan
references.title: Perturbed Iterate Analysis for Asynchronous Stochastic Optimization
references.authors: Brendan McMahan Eider Moore Daniel Ramage Seth Hampson Blaise Aguera y Arcas
references.title: Communication-Efficient Learning of Deep Networks from Decentralized Data
references.venue: In Artificial Intelligence and Statistics,
references.authors: Konstantin Mishchenko Eduard Gorbunov Martin Takáč Peter Richtárik
references.title: Distributed Learning with Compressed Gradient Differences
references.authors: Constantin Philippenko Aymeric Dieuleveut
references.title: Artemis: tight convergence guarantees for bidirectional compression in Federated Learning
references.authors: Herbert Robbins Sutton Monro
references.title: A Stochastic Approximation Method
references.venue: Annals of Mathematical Statistics,
references.authors: Felix Sattler Simon Wiedemann Klaus-Robert Müller Wojciech Samek
references.title: Robust and Communication-Efficient Federated Learning From Non-i.i.d
references.venue: Data. IEEE Transactions on Neural Networks and Learning Systems,
references.authors: Kevin Scaman Francis Bach Sebastien Bubeck Laurent Massoulié Yin Tat Lee
references.title: Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
references.venue: Advances in Neural Information Processing Systems,
references.authors: Frank Seide Amit Agarwal
references.title: CNTK: Microsoft’s Open-Source Deep-Learning Toolkit
references.venue: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD
references.authors: Frank Seide Hao Fu Jasha Droppo Gang Li Dong Yu
references.title: 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns
references.venue: In Fifteenth Annual Conference of the International Speech Communication Association. Citeseer,
references.authors: Sebastian U Stich Sai Praneeth Karimireddy
references.title: The error-feedback framework: Better rates for SGD with delayed gradients and compressed updates
references.venue: Journal of Machine Learning Research,
references.authors: Sebastian U Stich Jean-Baptiste Cordonnier Martin Jaggi
references.title: Sparsified SGD with Memory
references.venue: Advances in Neural Information Processing Systems
references.authors: Hanlin Tang Xiangru Lian Ming Yan Ce Zhang Ji Liu
references.title: $D^2$: Decentralized Training over Decentralized Data
references.venue: In International Conference on Machine Learning,
references.authors: Hanlin Tang Chen Yu Xiangru Lian Tong Zhang Ji Liu
references.title: DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-pass Error-Compensated Compression
references.venue: In International Conference on Machine Learning,
references.authors: Paul Vanhaesebrouck Aurélien Bellet Marc Tommasi
references.title: Decentralized Collaborative Learning of Personalized Models over Networks
references.venue: In Artificial Intelligence and Statistics,
references.authors: Jianqiao Wangni Jialei Wang Ji Liu Tong Zhang
references.title: Gradient Sparsification for Communication-Efficient Distributed Optimization
references.venue: Advances in Neural Information Processing Systems,
references.authors: Jiaxiang Wu Weidong Huang Junzhou Huang Tong Zhang
references.title: Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimization
references.venue: In International Conference on Machine Learning,
references.authors: An Xu Zhouyuan Huo Heng Huang
references.title: Training Faster with Compressed Gradient
references.authors: Shuai Zheng Ziyue Huang James Kwok
references.title: Communication-Efficient Distributed Blockwise Momentum SGD with Error-Feedback
references.venue: In Advances in Neural Information Processing Systems,
sections.heading: 1 Introduction
sections.text: Large scale distributed machine learning is widely used in many modern applications [1, 6, 28]. The training is distributed over a potentially large number N of workers that communicate either with a central server [see 17, 22, on federated learning], or using peer-to-peer communication [9, 34, 32].
  In this work, we consider a setting using a central server that aggregates updates from remote nodes. Formally, we have a number of features d ∈ N∗, and a convex cost function F : Rd → R. We want to solve the following distributed convex optimization problem using stochastic gradient algorithms [25, 5]: minw∈Rd F (w) with F (w) = 1N ∑N i=1 Fi(w), where (Fi) N i=1 is a local risk function (empirical risk or expected risk in a 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 a 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, a single uplink compression could be sufficient in asymmetric regimes in which broadcasting a message to N workers (“one to N”) is 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 to 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 (NeurIPS 2021).
  Furthermore, in a 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 a 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, 11] 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, we 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 - a 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, we show that it is possible to improve the convergence rate by sending different randomized models to the different workers, this is Rand-MCM. Secondly, this analysis also paves the way to deal with partially participating machines: the adaptation of Rand-MCM to this framework is straightforward; while adapting existing algorithms [26] to partial participation is not practical. Thirdly, this framework is also promising in terms of business applications, e.g., in the situation of learning with privacy guarantees 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 on 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 a new algorithm MCM, combining a 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 carefully 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-convex, convex and non-convex regimes. We give a 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 to worker dependent compression levels.
  The rest of the paper is organized as follows: in Section 2 we present the problem statement and introduce MCM and Rand-MCM. Theoretical results on these algorithms are successively presented in Sections 3 and 4. Finally, we present experiments supporting the theory in Section 5.
sections.heading: 2 Problem statement
sections.text: 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 ‖·‖ to denote the Euclidean norm. To solve this problem, we rely on a stochastic gradient descent (SGD) algorithm. A stochastic gradient gik+1 is provided at iteration k in N to the device i in J1, NK. This gradient oracle can be
  computed on a mini-batch of size b. This function is then evaluated at point wk. In the classical centralized framework (without compression), for a learning rate γ, SGD corresponds to:
  wk+1 = wk − γ 1
  N N∑ i=1 gik+1(wk) . (1)
  We now describe the framework used for compression.
sections.heading: 2.1 Bidirectional compression framework
sections.text: Bidirectional compression consists in compressing communications in both directions between the central server and remote devices. We use two different compression operators, respectively Cup and Cdwn to compress the message in each direction. Roughly speaking, the update in eq. (1) becomes:
  wk+1 = wk − γCdwn ( 1
  N N∑ i=1 Cup(gik+1(wk)) ) .
  However, this approach has a major drawback. The central server receives and aggregates information 1 N ∑N i=1 Cup(gik+1(wk)). But in order to be able to broadcast it back, it compresses it, before applying the update. We refer to this strategy as the “degraded update” approach. Its major advantage is simplicity, and it was used in all previous papers performing double compression. Yet, it appears to be a waste of valuable information. In this paper, we update the global model wk+1 independently of the downlink compression:{
  wk+1 = wk − γ 1N ∑N i=1 Cup ( gik+1(ŵk) ) .
  ŵk+1 = Cdwn(wk+1) (2)
  However, bluntly compressing wk+1 in eq. (2) hinders convergence, thus the second part of the update needs to be refined by adding a memory mechanism. We now describe both communication stages of the real MCM, which is entirely defined by the following uplink and downlink equations.
  Downlink Uplink{ Ωk+1 = wk+1 −Hk , ŵk+1 = Hk + Cdwn(Ωk+1) Hk+1 = Hk + αdwnCdwn(Ωk+1).  ∀i ∈ J1, NK,∆ik = gik+1(ŵk)− hik wk+1 = wk − γN ∑N i=1 Cup(∆ik) + hik
  hik+1 = h i k + αupCup(∆ik).
  (3)
  Downlink Communication. We introduce a downlink memory term (Hk)k, which is available on both workers and central server. The difference Ωk+1 between the model and this memory is compressed and exchanged, then the local model is reconstructed from this information. The memory is then updated as defined on left part of eq. (3), with a learning rate αdwn.
  Introducing this memory mechanism is crucial to control the variance of the local model ŵk+1. To the best of our knowledge MCM is the first algorithm that uses such a 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 it here to avoid divergence of the local model’s variance.
  Uplink Communication. The motivation to introduce an uplink memory term hik for each device i ∈ J1, NK 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 ∆ik between the stochastic gradient g i k+1 at the local model ŵk (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 αdwn. Remark 1 (Rate αdwn). It is necessary to use αdwn < 1. Otherwise, the compression noise tends to propagate and is amplified, because of the multiplicative nature of the compression. In Figure 1 we compare MCM, with 3 other strategies: compressing only the update, compressing wk − ŵk−1, (i.e., αdwn = 1), and compressing the model (i.e., Hk = 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 + ωdwn)−1) of the “error” wk+1 − ŵk+1 can be preserved in the EF term (see line 18 in algo 1 in Liu et 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 a 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 1 we summarize the main algorithms for compression in distributed training. As downlink communication can be more efficient than uplink, we consider distinct operators Cdwn, Cup and allow the corresponding compressions levels to be distinct: those quantities are defined in Assumption 1. Assumption 1. There exists constants ωup , ωdwn ∈ R∗+, such that the compression operators Cup and Cdwn satisfy the two following properties for all w in Rd: E[Cup/dwn(w)] = w, and E[‖Cup/dwn(w)− w‖2] ≤ ωup/dwn‖w‖2. The higher is ω, the more aggressive the compression is. We only consider unbiased operators, that encompass sparsification, quantization and sketching. References and a discussion on those operators, and possible extensions of our results to biased operators are provided in Appendix A.1. 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 et al. [11] to analyze the convergence of algorithms with uplink compressions, error feedback and asynchrony. Using gradients at randomly perturbed points can also be seen as a form of randomized smoothing [27], a point we discuss in Appendix A.2.
  2.2 The randomization mechanism, Rand-MCM In this subsection, we describe 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 a consequence, each worker holds a 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 Cdwn,i instead of a single one Cdwn, 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,i(wk+1 −Hik). The tradeoffs associated with this modification are discussed in Section 4.
  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.
sections.heading: 3 Assumptions and Theoretical analysis
sections.text: We make standard assumptions on F : Rd → R. 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 Rd: ‖∇F (w1)−∇F (w2)‖ ≤ L‖w1 − w2‖. Results in Section 3 are provided in a convex, strongly-convex and non-convex setting. Assumption 3 (Strong convexity). F is µ-strongly convex (or convex if µ = 0), that is for all vectors w1, w2 in Rd: F (w2) ≥ F (w1) + (w2 − w1)T∇F (w1) + µ2 ‖w2 − w1‖22 .
  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 of size b, is uniformly bounded: there exists a constant σ ∈ R+, such that for all k in N, for all i in J1, NK and for all w in Rd we have: E[‖gik(w)−∇F (w)‖2] ≤ σ2/b. We here provide guarantees of convergence for MCM. MCM incorporates an uplink memory term, 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 Fi = Fj and αup = 0. 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. Notations and settings. For k in N, we denote Υk = ‖wk −Hk−1‖2, and define Vk = E[‖wk − w∗‖2] + 32γLω2dwnE[Υk], which serves as Lyapunov function. Vk 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 ŵk. For both theorems, we choose αdwn = (8ωdwn)−1. We denote Φ(γ) := (1 + ωup) ( 1 + 64γLω2dwn ) .
  Limit learning rate: There exists a maximal learning rate to ensure convergence. More specifically, we define γmax := min(γupmax, γ dwn max , γ Υ max), where γ up max := (2L (1 + ωup/N))
  −1 corresponds to the classical constraint on the learning rate in the unidirectional regime [see 23, 24], γdwnmax := (8Lωdwn)
  −1 is a similar constraint coming from the downlink compression, and γΥmax := ( 8 √ 2Lωdwn √ 8ωdwn + ωup/N )−1
  is a combined constraint that arises when controlling the variance term Υ.1 Overall, this constraints are weaker than in the “degraded” framework [19, 24], in which γDoremax ≤ ( 8L(1 + ωdwn)(1 + ωup/N) )−1 . Especially, in the regime in which ωup,dwn → ∞ and ωdwn ' ωup ': ω, the maximal learning rate for MCM is (Lω3/2)−1, while it is (Lω2)−1 in [19, 24]. Our γmax is thus larger by a factor √ ω, see Table 2. We define L̃ such that γmax = (2L̃) −1.
  Theorem 1 (Convergence of MCM in the homogeneous and strongly-convex case). Under Assumptions 1 to 4 with µ > 0, for k in N, for any sequence (γk)k≥0 ≤ γmax we have:
  Vk ≤ (1− γkµ)Vk−1 − γkE [F (ŵk−1)− F (w∗)] + γ2kσ 2Φ(γk)
  Nb , (4)
  Consequently, (1) if σ2 = 0 (noiseless case), for γk ≡ γmax we recover a linear convergence rate: E[‖wk − w∗‖2] ≤ (1− γmaxµ)kV0; (2) if σ2 > 0, taking for all K in N, γK = 2/(µ(K + 1) + L̃), for the weighted Polyak-Ruppert average w̄K = ∑K k=1 λkwk−1/ ∑K k=1 λk, with λk := (γk−1) −1,
  E [F (w̄K)− F (w∗)] ≤ µ+ 2L̃
  4µK2 ‖w0 − w∗‖2 +
  4σ2(1 + ωup)
  µKNb
  ( 1 +
  64Lω2dwn µK ln(µK + L̃)
  ) .
  (5)
  Limit Variance (Equation (4)). For a constant γ, the variance term (i.e., term proportional to σ2) in Equation (4) is upper bounded by γ 2σ2
  Nb (1 + ωup)(1 + 64γLω 2 dwn). The impact of the downlink
  compression is attenuated by a factor γ. As γ 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 γ2σ2(1 + ωup)(1 + ωdwn)/N : (1) for Dore, see Corollary 1 in Liu et al. [19] (who indicate (1− ρ)−1 ≥ (1 +ωup/N)(1 +ωdwn)), (2) for Artemis see Table 2 and Th. 3 point 2 in [24], (3) for [11], see Theorem I.1. (with γD′1 ∝ γ 2σ2(1 + ωup)(1 + ωdwn)/N ).
  Bound 5 has a quadratic dependence on ωdwn, but the corresponding term is divided by an extra factor K, the number of iterations. For example in experiments, for w8a using quantization with s = 20, we have ωdwn ' 17, and after only 50 epoch with a batch size b = 12, we have K ' 2500. Hence, the term ω2/K is vanishing through iterations and we asymptotically recover a rate of convergence equivalent to algorithms using unidirectional compression.
  1The dependency in ω3/2 is similar to the one obtained by Horváth et al. [15] in unidirectional compression in the non-convex case (Theorem 4).
  Convergence and complexity: With a decaying sequence of steps, we obtain a convergence rate scaling as O(K−1) in Equation (5), without dependency on the ωdwn in the dominating term, which only appears in faster decaying terms scaling as K−2. The iteration complexity (i.e., number of iterations to achieve expected error) is thus at first order O →0( σ2(1+ωup) µ Nb ). Again, this matches the complexity of Diana [15, see Theorem 1 and Corollary 1] and is smaller by a factor 1 + ωdwn than the one of Artemis, Dore, DIANAsr-DQ (see Corollary I.1. in [11]). Next, we give a convergence result in the convex case.
  Theorem 2 (Convergence of MCM, convex case). Under Assumptions 1 to 4 with µ = 0. For all k > 0, for any γ ≤ γmax, we have, for w̄k = 1k ∑k−1 i=0 wi,
  γE [F (wk−1)− F (w∗)] ≤ Vk−1 − Vk + γ2σ2Φ(γ)
  Nb =⇒ E[F (w̄k)− F∗] ≤ V0 γk + γσ2Φ(γ) Nb . (6)
  Consequently, for K in N large enough, a step-size γ = √ ‖w0−w∗‖2Nb (1+ωup)σ2K , we have:
  E[F (w̄K)− F∗] ≤ 2
  √ ‖w0 − w∗‖2 (1 + ωup)σ2
  NbK +O(K−1). (7)
  Moreover if σ2 = 0 (noiseless case), we recover a faster convergence: E[F (w̄K)− F∗] = O(K−1). Limit Variance (Eq. (6)). The variance term is identical to the strongly-convex case.
  Convergence and complexity (Equation (7)). The downlink compression constant only appears in the second-order term, scaling as 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 (1+ωup) n 2 independently of the downlink compression. Again, for previous algorithms with double
  compression the complexity is at least O (
  (1+ωup)(1+ωdwn) n 2
  ) (see Corollary I.2 in [11]).
  Control of the variance of the local model.
  0 150 300 450 600 Number of passes on data
  −2
  0
  2
  lo g 1
  0( F (w
  k ) − F (w
  ∗) )
  Artemis-ND MCM - α = 0 MCM - α = 1 MCM
  0 150 300 450 600 Number of passes on data
  −2
  0 2 lo g 1 0( F (w k ) − F (w ∗) ) Artemis-ND MCM - α = 0 MCM - α = 1
  MCM
  Figure 1: Comparing MCM on two datasets with three other algorithms using a non-degraded update, γ = 1/L. Artemis-ND stands for Artemis with a non-degraded update.
  We here present the backbone Lemma of MCM’s proof. It allows to control the variance of the local model E[‖ŵk − wk‖2 |wk] (which is upperbounded by ωdwnE[‖Υk‖2 |wk]) and to build the Lyapunov function defined in Theorems 1 and 2.
  This result highlights the impact of the downlink memory term. Without memory, i.e., with αdwn = 0, the variance of the local model ‖ŵk − wk‖2 increases with the number of iterations. On the other hand, if αdwn 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.
  Theorem 3. Consider the MCM update as in eq. (2). Under Assumptions 1, 2 and 4 with µ = 0, if γ ≤ (8ωdwnL)−1 and α ≤ (4ωdwn)−1, then for all k in N:
  E [Υk] ≤ (
  1− αdwn 2
  ) E [Υk−1] + 2γ2 ( 1
  αdwn + ωup N
  ) E [ ‖∇F (ŵk−1)‖2 ] + 2γ2σ2(1 + ωup)
  Nb .
  This bound provides a recursive control on Υk. Beyond the (1 − αdwn) 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, we 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 ωup, ωdwn, and complexities for → 0. Proof in the heterogeneous case. To extend Theorems 1 to 3 in the heterogeneous setting for a convex objective (Appendix G), we assume that there exists a constant B in R+, s.t.:
  1 N ∑N i=0 ‖∇Fi(w∗)‖2 = B2 . We further define Ξk = 1N2 ∑N i=1 ∥∥hik −∇Fi(w∗)∥∥2, where for all i in J1, NK. This term is recursively controled [23, 24] and combined into the Lyapunov function. 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.1. 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 1 to 3 are given in Appendix E. Th. S11 in Appendix E.4 ensures convergence for a 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 compression opens new directions: in particular, it opens the door to handling a 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 a 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 on 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 2 suggests to strongly compress on the downlink direction (which leads to a large ωdwn), but to perform a weaker compression in the uplink direction.
  4 Extension to Rand-MCM
sections.heading: 4.1 Communication and convergence trade-offs
sections.text: In Rand-MCM, we leverage the fact that the compressions used for each worker need not to be identical. On the contrary, it is possible to 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 a bottleneck w.r.t. the communication time. A more important aspect is the communication cost. While the size of each message will remain identical, a different message needs to be sent to each worker. That is, we go from a “one to N” configuration to N “one to one” communications. While this is a drawback, it is not an issue when the bandwidth/transfer time are the bottlenecks, as Rand-MCM will result in a 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.
  1. 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) it 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 in 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 description 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
  a buffer. On the contrary, Rand-MCM naturally handles a 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 to store the N memories (Hik)i∈[N ] instead of one, which results in an additional memory cost. To circumvent this issue we propose two independent solutions. 1) Keep and use a single memory H̄k = N−1 ∑N i=1H i k (as suggested in [24]). It is then necessary to periodically reset the local memories Hik on all workers to the averaged value H̄k (rarely enough not to impact the communication budget). This is illustrated in fig. 4. 2) Use Rand-MCM with an arbitrary number of groups G N of workers. In each group Gg , g ∈ [G], all workers share the same memory (Hgk ) and receive the same update Cdwn,g(wk+1 −Hgk ). We call this algorithm Rand-MCM-G. Remark 5 (Protecting the global model from honest-but-curious clients). Another business advantage of MCM and Rand-MCM 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-intentioned clients (free-riders) that want to obtain the model without actually contributing has been studied by Fraboni et al. [10].
sections.heading: 4.2 Theoretical results
sections.text: In this Section, we provide two main theoretical results for Rand-MCM. First Theorem 4 ensures that the theoretical guarantees are at 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-MCM and Rand-MCM-G. 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 ωdwn. Keeping in mind that the dominating term in the rate is independent of ωdwn, we can thus only expect to reduce the second-order term. Next, the uplink compression noise increases with the variance of the randomized model, which will not be directly reduced by Rand-MCM. As a consequence, we only expect the improvement to be visible in the part of the second-order term that does not depend on ωup (that is, the effect would be the most significant if ωup is small or 0).
  This intuition is corroborated by the following result, in which we show that the convergence is improved when adding the randomization process for a quadratic function. Extending the proof beyond quadratic functions is possible, though it requires an assumption on third or higher order derivatives of F (e.g., using self-concordance [4]) to control of E [ ||∇F (ŵk−1)− E[∇F (ŵk−1)]||2
  ∣∣ wk−1]. Theorem 5 (Convergence in the quadratic case). Under Assumptions 1 to 4 with µ = 0, if the function is quadratic, after running K > 0 iterations, for any γ ≤ γmax, and we have
  E[F (w̄K)− F∗] ≤ V0 γK + γσ2ΦRd(γ) Nb ,
  with ΦRd(γ) = (1 + ωup) ( 1 + 4γ 2L2ωdwn K ( 1 C + ωup N ) )
  and C = N for Rand-MCM, C = G Rand-MCM-G, and C = 1 for MCM.
  This result is 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 γ ( 1 C + ωup N ) (w.r.t. Theorem 2), which is decaying at the same rate as γ. Besides, the proof for Rand-MCM is substantially modified, as E[∇F (ŵk−1)] is an unbiased estimator of∇F (wk−1). (2) Moreover, the randomization in Rand-MCM (resp. Rand-MCM-G) further reduces by a factor N (resp. G) this term. Depending on the relative sizes of ωup and N , this can lead to a significant improvement up to a factor of N . In practice the impact of Rand-MCM is noticeable, as illustrated in the following experiments.
sections.heading: 5 Experiments
sections.text: 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 baseline.
  In these experiments, we provide results on the log of the excess loss F (wk)− F∗, averaged on 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 log10(F (wk)− 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 a single level (s = 20), unless for PP (s = 21) and neural network (the value of s 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 a simple framework, and in particular to ilustrate that when σ2 = 0, we recover a linear convergence2, 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 TSNE [20]) the input points. • Four dataset in a non-convex settings (CIFAR10, Fashion-MNIST, FE-MNIST, MNIST); see Table S2 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 a certain number of epochs). Indeed, our goal is to show that our method achieves a performance close to the unidirectional-compression framework (Diana), while performing an important downlink compression. More details about experiments can 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.
  Saturation level. All experiments are performed with a constant learning rate γ to observe the bias (initial reduction) and the variance (saturation level) independently. Stochastic gradient descent results in a fast convergence during the first iterations, and then reaches a saturation at a given level proportional to σ2. Theorem 2 states that the variance of MCM is proportional to ωup, this is experimentally observed on Tables 3 and 4 and figs. 2 and 3: MCM meets Diana while Artemis and Dore saturate at a higher level (scaling as ωup×ωdwn). These trade-offs are preserved with optimized learning rates.
  2Even stronger, we show in experiments that we recover a linear rate if we have σ∗ = 0 (the noise over stochastic gradient computation at the optimum point w?).
  Linear convergence when σ2 = 0. The six algorithms present a linear convergence when σ2 = 0. This is illustrated by Figure 2b: we ran experiments with a full gradient descent. Note that in these settings MCM has a slightly worse performance than other methods; however, this slow-down is compensated by Rand-MCM.
  Impact of randomization. The impact of randomization is noticeable on Figures 2b and S5b. Randomization helps to stabilise convergence of it reduces the variance of the runs and when σ2 = 0, it performs identically to SGD. Figure 4 illustrates the impact of using a single memory, instead of N , to alleviate the memory cost in the PP setting (Subsection 4.1), with or without periodic reset. Without reset, performance are slightly degraded, but with it, we recover previous results.
  Deep learning. Table 4 and figs. 2c and 2d illustrate experiments with neural networks, details on dataset settings and networks architecture are given in Appendix B.2. Again, MCM meets Diana rates as stated by Theorem S11 (theorem in the non-convex case).
  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 are given in Appendix B.1.1. All the code is provided on our github repository.
sections.heading: 6 Conclusion
sections.text: In this work, we propose a new algorithm to perform bidirectional compression while achieving the convergence rate of algorithms using compression in a single direction. One of the main application of this framework is Federated Learning. With MCM we stress the importance of not 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 in distributed learning, e.g., proposing practical algorithms for partial participation, incorporating privacy-preserving schemes after the global update is performed, dealing with local steps, etc. This approach could also be pivotal in non-smooth frameworks, as it can be considered as a weak form of randomized smoothing.
sections.heading: Acknowledgments
sections.text: We would like to thank Richard Vidal, Laeticia Kameni from Accenture Labs (Sophia Antipolis, France) and Eric Moulines from École Polytechnique for insightful discussions. This research was supported by the SCAI: Statistics and Computation for AI ANR Chair of research and teaching in artificial intelligence, by Hi!Paris, and by Accenture Labs (Sophia Antipolis, France).
title: Preserved central model for faster bidirectional compression in distributed settings