summaries: The authors consider accelerated training algorithms using gradient compression with error compensation. For this purpose, they incorporated gradient compression and error compensation in the Katyusha algorithm and developed ECKL. The algorithm quantizes both the SG and VR term and keeps track of the quantization error for error compensation in the next iteration.  The paper analyzed the convergence rate and iteration complexity of ECKL for the smooth convex functions and compared it with variants of DIANA both theoretically and via some simple simulations on logistic regression. The paper introduces an error compensation variant of the loopless Katyusha, ECLK. Theoretical convergence analysis is given and accelerated linear convergence rate is obtained using contraction operators. Experimental study of ECLK is given on the logistic regression problem for binary classification. This paper presents accelerated methods for communication-efficient learning applications. In particular, a loopless Katyusha strategy is introduced to attain the O(\sqrt{L/\mu}) rate for error-compensated methods using stochastic gradient information. These methods are called ECLK. In terms of theoretical iteration complexity and empirical experiments, ECLK is explicitly shown to be more communication efficient and to have a better rate than existing error compensation methods. This paper proposed an error compensated based Katyusha method for finite-sum convex problems. The proposed method achieves the same asymptotic convergence rate as its full precision accelerated counterpart. Compared to another related work ADIANA, the proposed method can be applied to contractive compressor.  This paper considers communication efficient algorithms for SGD. In this model, there are $n$ total workers and each worker has a local smooth convex loss function $f_i$ on $R^d$. The objective is for a coordinator to find an approximate global minimum for an objective function that represents the average loss across all workers while minimizing communication between the workers and the coordinator.   A common approach is for each worker to compute a sketch on their local batch of gradients that allows the coordinator to recover of the top $k$ gradients in magnitude, ideally improving the rate of convergence. However, the challenge with this approach is that the estimator formed by the coordinator using the sketches sent from the workers may not be an unbiased estimator of the overall gradient, which allows error to accumulate over multiple iterations. This paper introduces provable accelerated gradient-methods, in the sense of Nesterov momentum for contractive compressors, which are a general class of stochastic functions that form estimators of the gradient, including the top $k$ estimator. 
abstractText: Gradient compression is a recent and increasingly popular technique for reducing the communication cost in distributed training of large-scale machine learning models. In this work we focus on developing efficient distributed methods that can work for any compressor satisfying a certain contraction property, which includes both unbiased (after appropriate scaling) and biased compressors such as RandK and TopK. Applied naively, gradient compression introduces errors that either slow down convergence or lead to divergence. A popular technique designed to tackle this issue is error compensation/error feedback. Due to the difficulties associated with analyzing biased compressors, it is not known whether gradient compression with error compensation can be combined with acceleration. In this work, we show for the first time that error compensated gradient compression methods can be accelerated. In particular, we propose and study the error compensated loopless Katyusha method, and establish an accelerated linear convergence rate under standard assumptions. We show through numerical experiments that the proposed method converges with substantially fewer communication rounds than previous error compensated algorithms.
authors.name: Xun Qian
authors.name: Peter Richtárik
authors.name: Tong Zhang
references.authors: A. Agarwal J.C. Duchi
references.title: Distributed delayed stochastic optimization
references.venue: In Advances in Neural Information Processing Systems (NIPS),
references.authors: D. Alistarh D. Grubic J. Li R. Tomioka M. Vojnovic
references.title: QSGD: Communication-efficient SGD via gradient quantization and encoding
references.venue: In Advances in Neural Information Processing Systems (NIPS),
references.authors: D. Alistarh T. Hoefler M. Johansson N. Konstantinov S. Khirirat C. Renggli
references.title: The convergence of sparsified gradient methods
references.venue: In Advances in Neural Information Processing Systems (NeurIPS),
references.authors: Zeyuan Allen-Zhu
references.title: Katyusha: The first direct acceleration of stochastic gradient methods
references.venue: The Journal of Machine Learning Research,
references.authors: J. Bernstein Y.X. Wang K. Azizzadenesheli A. Anandkumar
references.title: SignSGD: Compressed optimisation for non-convex problems
references.authors: A. Beznosikov S. Horváth P. Richtárik M. Safaryan
references.title: On biased compression for distributed learning
references.venue: arXiv preprint arXiv:2002.12410,
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 (TIST),
references.authors: Eduard Gorbunov Dmitry Kovalev Dmitry Makarenko Peter Richtárik
references.title: Linearly converging error compensated SGD
references.venue: In Neural Information Processing Systems (NeurIPS),
references.authors: P. Goyal P. Dollár R. Girshick P. Noordhuis L. Wesolowski A. Kyrola A. Tulloch Y. Jia K. He
references.title: Accurate, large minibatch SGD: Training imagenet in 1 hour
references.venue: arXiv preprint arXiv:1706.2677,
references.authors: Filip Hanzely Peter Richtárik
references.title: Federated learning of a mixture of global and local models
references.venue: arXiv preprint arXiv:2002.05516,
references.authors: S. Horváth D. Kovalev K. Mishchenko S. Stich P. Richtárik
references.title: Stochastic distributed learning with gradient quantization and variance reduction
references.venue: arXiv preprint arXiv:1904.05115,
references.authors: Samuel Horváth Chen-Yu Ho L’udovít Horvath Atal Narayan Sahu Marco Canini Peter Richtárik
references.title: Natural compression for distributed deep learning
references.venue: arXiv preprint arXiv:1905.10988,
references.authors: Peter et al Kairouz
references.title: Advances and open problems in federated learning
references.venue: arXiv preprint arXiv:1912.04977,
references.authors: Sai Praneeth Karimireddy Quentin Rebjock Sebastian U Stich Martin Jaggi
references.title: Error feedback fixes SignSGD and other gradient compression schemes
references.authors: Ahmed Khaled Konstantin Mishchenko Peter Richtárik
references.title: Tighter theory for local SGD on identical and heterogeneous data
references.venue: In The 23rd International Conference on Artificial Intelligence and Statistics (AISTATS),
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.venue: arXiv preprint arXiv:1610.02527,
references.authors: Jakub Konečný H. Brendan McMahan Felix Yu Peter Richtárik Ananda Theertha Suresh Dave Bacon
references.title: Federated learning: strategies for improving communication efficiency
references.venue: In NIPS Private Multi-Party Machine Learning Workshop,
references.authors: D. Kovalev S.l Horváth P. Richtárik
references.title: Don’t jump through hoops and remove those loops: SVRG and Katyusha are better without the outer loop
references.venue: In Proceedings of the 31st International Conference on Algorithmic Learning Theory (ALT),
references.authors: Guanghui Lan Yi Zhou
references.title: An optimal randomized incremental gradient method
references.venue: Mathematical programming,
references.authors: Tian Li Anit Kumar Sahu Ameet Talwalkar Virginia Smith
references.title: Federated learning: challenges, methods, and future directions
references.authors: Zhize Li Dmitry Kovalev Xun Qian Peter Richtárik
references.title: Acceleration for compressed gradient descent in distributed and federated optimization
references.venue: In Proceedings of the 37th International Conference on Machine Learning (ICML),
references.authors: X. Lian Y. Huang Y. Li J. Liu
references.title: Asynchronous parallel stochastic gradient for nonconvex optimization
references.venue: In Advances in Neural Information Processing Systems (NIPS),
references.authors: Chenxin Ma Jakub Konečný Martin Jaggi Virginia Smith Michael I. Jordan Peter Richtárik Martin Takáč
references.title: Distributed optimization with arbitrary local solvers
references.venue: Optimization Methods and Software,
references.authors: H Brendan McMahan Eider Moore Daniel Ramage Seth Hampson Blaise Agüera y Arcas
references.title: Communication-efficient learning of deep networks from decentralized data
references.venue: In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS),
references.authors: K. Mishchenko E. Gorbunov M. Takáč P. Richtárik
references.title: Distributed learning with compressed gradient differences
references.venue: arXiv preprint arXiv:1901.09269,
references.authors: Yurii Nesterov
references.title: Introductory lectures on convex optimization: a basic course (Applied Optimization)
references.venue: Kluwer Academic Publishers,
references.authors: Xun Qian Zheng Qu Peter Richtárik
references.title: L-SVRG and L-Katyusha with arbitrary sampling
references.venue: arXiv preprint arXiv:1906.01481,
references.authors: B. Recht C. Re S. Wright F. Niu
references.title: Hogwild: A lock-free approach to parallelizing stochastic gradient descent
references.venue: In Advances in Neural Information Processing Systems (NIPS),
references.authors: F. Seide H. Fu J. Droppo G. Li D. Yu
references.title: 1-bit stochastic gradient descent and its application to data- parallel distributed training of speech DNNs
references.venue: Fifteenth Annual Conference of the International Speech Communication Association,
references.authors: S.U. Stich S.P. Karimireddy
references.title: The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication
references.authors: S.U. Stich J.B. Cordonnier M. Jaggi
references.title: Sparsified SGD with memory
references.venue: In Advances in Neural Information Processing Systems (NeurIPS),
references.authors: Sebastian U. Stich
references.title: Local SGD converges fast and communicates little
references.venue: In International Conference on Learning Representations (ICLR),
references.authors: H. Tang S. Gan C. Zhang T. Zhang J. Liu
references.title: Communication compression for decentralized training
references.venue: In Advances in Neural Information Processing Systems (NeurIPS),
references.authors: H. Tang X. Lian T. Zhang J. Liu
references.title: DoubleSqueeze: Parallel stochastic gradient descent with double-pass error-compensated compression
references.venue: In Proceedings of the 36th International Conference on Machine Learning (ICML),
references.authors: W. Wen C. Xu F. Yan C. Wu Y. Wang H. Li
references.title: Terngrad: Ternary gradients to reduce communication in distributed deep learning
references.venue: In Advances in Neural Information Processing Systems (NIPS),
references.authors: Blake Woodworth Kumar Kshitij Patel Sebastian U. Stich Zhen Dai Brian Bullins H. Brendan McMahan Ohad Shamir Nathan Srebro
references.title: Is local SGD better than minibatch SGD
references.authors: J. Wu W. Huang J. Huang T. Zhang
references.title: Error compensated quantized SGD and its applications to large-scale distributed optimization
references.venue: In The 35th International Conference on Machine Learning (ICML),
references.authors: Y. You I. Gitman B. Ginsburg
references.title: Scaling SGD batch size to 32k for imagenet training
references.venue: arXiv preprint arXiv:1708.03888,
sections.heading: 1 Introduction
sections.text: When training very large scale supervised machine learning problems, such as those arising in the context of federated learning [Konečný et al., 2016b, McMahan et al., 2017, Konečný et al., 2016a] (see also recent surveys [Li et al., 2019, Kairouz, 2019]), distributed algorithms are indispensable. In such settings, communication is generally much slower than (local) computation, which makes it the key bottleneck in the design of efficient distributed systems. There are several ways to tackle this issue, including reliance on large mini-batches [Goyal et al., 2017, You et al., 2017], asynchronous learning [Agarwal and Duchi, 2011, Lian et al., 2015, Recht et al., 2011], local updates [Ma et al., 2017, Stich, 2020, Khaled et al., 2020, Hanzely and Richtárik, 2020, Woodworth et al., 2020] and communication compression (e.g., quantization and sparsification) [Alistarh et al., 2017, Bernstein et al., 2018, Mishchenko et al., 2019, Seide et al., 2014, Wen et al., 2017].
  Communication compression. In this work, we focus on the last of these techniques: communication compression. The key idea here is to apply a lossy compression transformation/operator to the messages before they are communicated so as to save on communication time. While compression reduces the communicated bits in each communication round, it introduces errors, and this generally leads to an increase in the number of communication rounds needed to find a solution of any predefined accuracy. Still, compression has been found useful in practice, as the trade-off often seems to prefer compression to no compression.
  ∗King Abdullah University of Science and Technology, Thuwal, Saudi Arabia †King Abdullah University of Science and Technology, Thuwal, Saudi Arabia; Moscow Institute of Physics
  and Technology, Dolgoprudny, Russia ‡Hong Kong University of Science and Technology, Hong Kong
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  Contractive and unbiased compressors. There are two large families of such compression operators: contraction and unbiased compressors [Beznosikov et al., 2020]. A (possibly) randomized map Q : Rd → Rd is called a contraction compressor if there exists a constant 0 < δ ≤ 1 such that
  E [ ∥x−Q(x)∥2 ] ≤ (1− δ)∥x∥2, ∀x ∈ Rd. (1)
  Further, we say that a randomized map Q̃ : Rd → Rd is an unbiased compressor if there exists a constant ω ≥ 0 such that
  E [ Q̃(x) ] = x and E [ ∥Q̃(x)∥2 ] ≤ (ω + 1)∥x∥2, ∀x ∈ Rd. (2)
  It is well known that (see, e.g., [Beznosikov et al., 2020]) after appropriate scaling, any unbiased compressor satisfying (2) becomes a contraction compressor. Indeed, it is easy to verify that for any Q̃ satisfying (2), 1ω+1 Q̃ is a contraction compressor satisfying (1) with δ = 1/(ω+1). Thus we can construct corresponding contraction compressor from any unbiased compressor. However, there are empirically very powerful contractive compressors, such as TopK [Alistarh et al., 2018] (described below), which do not arise this way, and because of this, the class of contractive compressors is important in practice. For illustration purposes, we now define two canonical examples of contraction compressors. Let 1 ≤ K ≤ d. The TopK compressor is defined as
  (TopK(x))π(i) =
  { (x)π(i) if i ≤ K,
  0 otherwise,
  where π is a permutation of {1, 2, ..., d} such that (|x|)π(i) ≥ (|x|)π(i+1) for i = 1, ..., d − 1. The RandK compressor is defined as
  (RandK(x))i = { (x)i if i ∈ S, 0 otherwise,
  where S is chosen uniformly from the set of all K element subsets of {1, 2, ..., d}. For TopK and RandK compressors, we have δ ≥ K/d [Stich et al., 2018]. Some frequently used unbiased compressors include random dithering [Alistarh et al., 2017], random sparsification [Stich et al., 2018], and natural compression [Horváth et al., 2019b]. For more examples of contraction and unbiased compressors, we refer the reader to [Beznosikov et al., 2020].
  Related Work. If we assume that the accumulated error is bounded, and in the case of unbiased compressors, the convergence rate of error compensated SGD was shown to be the same as that of vanilla SGD [Tang et al., 2018]. However, if we only assume bounded second moment of the stochastic gradients, in order to guarantee the boundedness of the accumulated quantization error, some decaying factors need to be involved in general, and error compensated SGD is proved to have some advantage over QSGD [Alistarh et al., 2017] in some perspective for convex quadratic problems [Wu et al., 2018]. On the other hand, for contraction compressors, error compensated SGD actually has the same convergence rate as vanilla SGD [Stich et al., 2018, Stich and Karimireddy, 2019, Tang et al., 2019]. Since SGD only has a sublinear convergence rate, these error compensated methods could not get linear convergence rate. If f is non-smooth and ψ = 0, error compensated SGD was studied in [Karimireddy et al., 2019] in the single node case, and the convergence rate is of order O (1/ √ δk).
  For variance-reduced methods, QSVRG [Alistarh et al., 2017] handles the smooth case (ψ ≡ 0), and VR-DIANA [Horváth et al., 2019a], ADIANA [Li et al., 2020] handle the composite case (general ψ). However, the compressors of these algorithms need to be unbiased. Error compensation in VR-DIANA and ADIANA does not need to be used since their method successfully employs variance reduction (of the variance introduced by the compressor) instead. Recently, an error compensated method called EC-LSVRG-DIANA which can achieve nonaccelerated linear convergence for the strongly convex and smooth case was proposed in [Gorbunov et al., 2020], but besides the contraction compressor, the unbiased compressor is also needed in the algorithm.
  Error compensation. While contractive compressors can be more powerful in practice, they are not unbiased, and this leads to severe difficulties in the algorithm design space, and poses challenges for theoreticians trying to understand the convergence behavior of distributed algorithms using contractive compressors. Indeed, while there is no issue with the use of contractive compressors in the non-distributed setting (which is of course not interesting from a practical point of view) in
  combination with standard gradient-type methods, serious convergence issues arise in the distributed setting. Indeed, classical methods such gradient descent can diverge (even exponentially fast) when the TopK compressor is used to compress uplink gradient information [Beznosikov et al., 2020]. Fortunately, this issue can be resolved using the error compensation (EC)4 mechanism, which can be traced back to at least Seide et al. [2014]. However, this mechanism remained a heuristic until recently. To highlight the difficulty of analyzing EC, we remark that the first theoretical breakthroughs applied to the single node regime only [Stich et al., 2018, Stich and Karimireddy, 2019]. More recently, theoretical progress was made in the crucially important distributed setting as well [Beznosikov et al., 2020, Gorbunov et al., 2020]. However, we are still very far in our understanding of optimization algorithms using contractive compressors.
  One of the key open problems in this area—the problem we address in this paper in the affirmative— is whether it is possible to design provably accelerated gradienttype methods that work with contractive compressors.
  In this paper, we give a confirmed answer by studying error compensation in conjunction with the acceleration mechanism employed in loopless Katyusha (L-Katyusha) [Kovalev et al., 2020, Qian et al., 2019], which is a loopless variant of Katyusha [Allen-Zhu, 2017]. The acceleration in Katyusha or L-Katyusha is an extension of Nesterov’s acceleration [Nesterov, 1983, 2004] in the stochastic regime. Moreover, Katyusha and L-Katyusha can achieve the optimal iteration complexity among randomized methods for solving finite-sum strongly convex optimization problems [Lan and Zhou, 2018].
sections.heading: 2 Problem Description and Summary of Contributions
sections.text: We formally describe the distributed optimization problem we solve in Section 2.1, and then summarize our key contributions in Section 2.2.
sections.heading: 2.1 Problem Description
sections.text: We consider the composite finite-sum optimization problem
  min x∈Rd P (x) :=
  { 1 n n∑ τ=1 f (τ)(x) + ψ(x) } , (3)
  where f(x) := 1n ∑ τ f
  (τ)(x) is an average of n smooth convex functions, distributed over n compute nodes, and ψ : Rd → R∪ {+∞} is a proper closed convex function representing a possibly nonsmooth regularizer. On each node τ , f (τ)(x) is an average of m smooth convex functions, i.e.,
  f (τ)(x) = 1m m∑ i=1 f (τ) i (x), representing the average loss over the training data stored on this node.
  We denote the smoothness constants of functions f , f (τ) and f (τ)i using symbols Lf , L̄ and L, respectively.5 These constants are in general related as follows:
  Lf ≤ L̄ ≤ nLf , L̄ ≤ L ≤ mL̄. (4)
  While we specifically focus on the case when m = 1, our results are also new in the m = 1 case, and hence this regime is relevant as well. We assume throughout that problem (3) has at least one optimal solution x∗.
  We will optionally use the following additional assumption for the contraction compressor. The assumption is not necessary, but when used, it will lead to better complexity. Assumption 2.1. E[Q(x)] = δx and E[Q1(x)] = δ1x for all x ∈ Rd, where δ and δ1 are compression parameters of Q and Q1, respectively.
  It is easy to verify that RandK compressor satisfies Assumption 2.1 with δ = K/d, and 1ω+1 Q̃, where Q̃ is any unbiased compressor, also satisfies Assumption 2.1 with δ = 1/(ω+1).
  4Error compensation is also known under the name error feedback. 5Function f : Rd → R is smooth if it is differentiable, and has L-Lipschitz gradient: ∥∇f(x)−∇f(y)∥ ≤
  L∥x− y∥ for any x, y ∈ Rd. L is called the smoothness constant of f .
sections.heading: 2.2 Contributions
sections.text: We now summarize the main contributions of our work.
  Acceleration for error compensation. We develop a new communication efficient algorithm (Algorithm 1) for solving the distributed optimization problem (3) which we call Error Compensated Loopless Katyusha (ECLK). ECLK is the first accelerated error compensated method (this is true even in the non-distributed setting), which we believe is a significant contribution to the field.
  Iteration complexity. We obtain the first accelerated linear convergence rate for error compensated methods using contraction operators. Let p ≤ O(δ1), where p ∈ (0, 1] is a parameter of the method described later and δ1 is the compression parameter of Q1 in Algorithm 1 (see Assumption 2.1). Then the iteration complexity of ECLK is
  O ((
  1 δ + 1 p + √ Lf µ + √ L µpn + 1 δ √ (1−δ)L̄ µp + √ (1−δ)L µpδ ) log 1ϵ ) . (5)
  This is an improvement over the previous best known results for error compensated methods in [Beznosikov et al., 2020] and [Gorbunov et al., 2020], where nonaccelerated linear rates were obtained for the smooth case (ψ ≡ 0). Moreover, in oder to obtained a linear rate, Beznosikov et al. [2020] required the assumption that ∇f (τ)(x∗) = 0 for all τ , and also need full gradients to be computed by all nodes. The complexity of EC-LSVRG-DIANA in [Gorbunov et al., 2020] is
  O (( ω +m+ Lδµ ) log 1ϵ ) . (6)
  When the last term in (6) is dominant and the last two terms in (5) are dominant, the complexity of ECLK is better than that of EC-LSVRG-DIANA if p ≥ O
  ( (1−δ)L̄µ
  L2 + (1−δ)δµ L
  ) .
  If we invoke additional assumptions (Assumption 2.1) on the contraction compressor, the iteration complexity of ECLK is improved to
  O ((
  1 δ + 1 p + √ Lf µ + √ L µpn + 1 δ √ (1−δ)Lf µp + √ (1−δ)L µpδn ) log 1ϵ ) .
  This is indeed an improvement since Lf ≤ L̄ (see (4)), and because of the extra scaling factor of n in the last term. If δ = δ1 = 1, i.e., if no compression is used, we recover the iteration complexity of the accelerated method L-Katyusha [Qian et al., 2019].
sections.heading: 3 Error compensated L-Katyusha
sections.heading: 3.1 Description of the method
sections.text: In this section we describe our method: error compensated L-Katyusha (see Algorithm 1). Roughly speaking, ECLK is a combination of L-Katyusha, error feedback, and a learning scheme in VRDIANA [Horváth et al., 2019a].
  The search direction in L-Katyusha in the distributed setting (n ≥ 1) at iteration k is
  1
  n n∑ τ=1 ( ∇f (τ)iτk (x k)−∇f (τ)iτk (w k) +∇f (τ)(wk) ) ,
  where iτk is sampled uniformly and independently from [m] := {1, 2, ...,m} on the τ -th node for 1 ≤ τ ≤ n, xk is the current iteration, and wk is the current reference point. Whenever ψ is nonzero in problem (3), ∇f(x∗) is nonzero in general, and so is ∇f (τ)(x∗) (it could be nonzero even if ∇f(x∗) = 0 in the non-regularized case). Thus, compressing the direction
  ∇f (τ)iτk (x k)−∇f (τ)iτk (w k) +∇f (τ)(wk) (7)
  directly on each node would cause nonzero noise even if xk and wk converged to the optimal solution x∗. On the other hand, since f (τ)i is L-smooth, ∇f (τ) iτk (xk)−∇f (τ)iτk (w k) could be small if xk and wk are close enough. For the last term ∇f (τ)(wk), we introduce a vector hkτ to learn it iteratively in
  a similar way in VR-DIANA. However, we use a contraction compressor rather than an unbiased one. More precisely, we take the update
  hk+1τ = h k τ +Q1(∇f (τ)(wk)− hkτ ), (8)
  where Q1 is a contraction compressor. h0τ can be initialized by any vector in Rd. It is possible to interprete the learning procedure (8) as one step of the compressed gradient descent method applied to a certain quadratic optimization problem whose unique solution is the vector ∇f (τ)(wk). Now we would expect ∇f (τ)(wk)− hkτ could converge to zero as k → +∞. We substract hkτ from the search direction in (7) to get
  gkτ = ∇f (τ) iτk (xk)−∇f (τ)iτk (w k) +∇f (τ)(wk)− hkτ ,
  and will add hkτ back after aggregation.
  Next we apply the compression and error feedback techniques, i.e., we compress the vector ηL1 g k τ +e k τ on each node to get g̃kτ = Q( η L1 g k τ + e k τ ), where Q is a contraction compressor and L1 is a positive parameter. The accumulated error ek+1τ is updated by the compression error at iteration k. On each node, a scalar ukτ is also maintained, and only u k 1 will be updated. The summation of u k τ for 1 ≤ τ ≤ n is uk, and we use uk to control the update frequency of the reference point wk.6 Each node sends the two compressed vectors g̃kτ , Q1(∇f (τ)(wk) − hkτ ), and a scalar uk+1τ to the other nodes. After aggregating g̃k = 1n ∑n τ=1 g̃ k τ , we add the average vector h k = 1n ∑n τ=1 h k τ after multiplying the stepsize ηL1 to it to get the search direction g̃ k + ηL1h
  k. We also use the following standard proximal operator for the update of zk:
  proxηψ(x) := argmin y
  { 1 2∥x− y∥ 2 + ηψ(y) } .
  The reference point wk will be updated if uk+1 = 1. It is easy to see that wk will be updated with probability p at each iteration. All nodes maintain the same copies of xk, wk, yk, zk, g̃k, hk, and uk.
  We need the following assumptions in this section. Assumption 3.1. The two compressors Q and Q1 in Algorithm 1 are contraction compressors with parameters δ and δ1, respectively.
  Assumption 3.2. f (τ)i is L-smooth, f (τ) is L̄-smooth, f is Lf -smooth and µf -strongly convex, and ψ is µψ-strongly convex, where µf ≥ 0, µψ ≥ 0, and µ := µf + µψ > 0.
sections.heading: 3.2 Convergence analysis: preliminaries
sections.text: First, we introduce some perturbed vectors which will be used in the convergence analysis. The perturbed vector is usually used in the analysis of error compensated methods [Karimireddy et al., 2019]. In Algorithm 1, let ek = 1n ∑n τ=1 e k τ , g k = 1n ∑n τ=1 g k τ , and x̃ k = xk − 11+ησ1 e k, z̃k = zk − 11+ησ1 e k for k ≥ 0. Then ek+1 = 1n ∑n τ=1 ( ekτ + η L1 g k τ − g̃kτ ) = ek + ηL1 g
  k − g̃k, and from the optimality condition for the proximal operator, we have
  z̃k+1 = zk+1 − 11+ησ1 e k+1
  = 11+ησ1
  ( ησ1x k + zk − g̃k − ηL1h k ) − η∂ψ(z k+1 (1+ησ1)L1 )− ek+1 1+ησ1
  = 11+ησ1
  ( ησ1x
  k + zk − ek − ηL1 g k − ηL1h
  k ) − η∂ψ(z
  k+1) (1+ησ1)L1
  = 11+ησ1
  ( ησ1x̃
  k + z̃k − ηL1 g k − ηL1h
  k ) − η∂ψ(z
  k+1) (1+ησ1)L1 . (9)
  The above relation plays a vital role in the convergence analysis, and allows us to follow the analysis of original L-Katyusha. In particular, we will use z̃k to construct Lyapunov functions. Next we define some notations which will be used to construct Lyapunov functions. Define Z̃k := L1+ηµ/22η ∥z̃ k −
  6We can also use a single shared random variable uk instead.
  Algorithm 1 Error Compensated Loopless Katyusha (ECLK)
  1: Parameters: stepsize parameters η = 13θ1 > 0, L1 > 0, σ1 = µf 2L1 ≥ 0, θ1, θ2 ∈ (0, 1);
  probability p ∈ (0, 1] 2: Initialization: x0 = y0 = z0 = w0 ∈ Rd; u0τ = 0 ∈ R; e0τ = 0 ∈ Rd; h0τ ∈ Rd; u0 = ∑n τ=1 u 0 τ ; h 0 = 1n ∑n τ=1 h 0 τ 3: for k = 0, 1, 2, ... do 4: for τ = 1, ..., n do 5: Sample iτk uniformly and independently in [m] on each node 6: gkτ = ∇f (τ) iτk (xk)−∇f (τ)iτk (w k) +∇f (τ)(wk)− hkτ 7: g̃kτ = Q( η L1 g k τ + e k τ ), h k+1 τ = h k τ +Q1(∇f (τ)(wk)− hkτ ) 8: ek+1τ = e k τ + η L1 g k τ − g̃kτ , uk+1τ = 0 for τ = 2, ..., n
  9: uk+11 = { 1 with probability p 0 with probability 1− p
  10: Send g̃kτ , Q1(∇f (τ)(wk)− hkτ ), and uk+1τ to the other nodes 11: Receive g̃kτ , Q1(∇f (τ)(wk)− hkτ ), and uk+1τ from the other nodes 12: g̃k = 1n ∑n τ=1 g̃ k τ , u k+1 = ∑n τ=1 u k+1 τ 13: zk+1 = prox η (1+ησ1)L1 ψ ( 1 1+ησ1 ( ησ1x k + zk − g̃k − ηL1h k )) 14: yk+1 = xk + θ1(zk+1 − zk)
  15: wk+1 = { yk if uk+1 = 1 wk otherwise
  16: xk+1 = θ1zk+1 + θ2wk+1 + (1− θ1 − θ2)yk+1 17: hk+1 = hk + 1n ∑n τ=1Q1(∇f (τ)(wk)− hkτ ) 18: end for 19: end for
  x∗∥2, Yk := 1θ1 (P (y k) − P ∗), and Wk := θ2pqθ1 (P (w k) − P ∗) for k ≥ 0, where P ∗ := P (x∗). From the update rule of wk in Algorithm 1, it is easy to see that
  Ek[Wk+1] = (1− p)Wk + θ2q Y k, (10)
  for k ≥ 0. Let Bf (x, y) := f(x) − f(y) − ⟨∇f(y), x − y⟩ be the Bregman divergence and Ek[·] denote the expectation conditional on xk, yk, zk, wk, hkτ , u k τ , and e k τ . The following lemma reveals the evolution of the other two terms Z̃k and Yk. Lemma 3.3. If L1 ≥ Lf and θ1 + θ2 ≤ 1, then Ek [ Z̃k+1 + Yk+1 ] can be upper bounded by
  L1 L1+ηµ/2 Z̃
  k + (1− θ1 − θ2)Yk + pqWk + ( L1 2η + µf 2 ) ∥ek∥2 + ( L1 2η + µ 2 ) Ek [ ∥ek+1∥2 ] − 1θ1 ( θ2 − 2LnL1 ) Bf (w k, xk)− 1−θ1−θ2θ1 Bf (y k, xk).
  Because of the compression, we have the additional error terms ∥ek∥2 and ∥ek+1∥2 in the evolution of Z̃k and Yk in Lemma 3.3. To upper bound these error terms, we need to analyze the evolution of 1 n ∑n τ=1 e k τ and 1 n ∑n τ=1 ∥hkτ −∇f (τ)(wk)∥2 in the next two lemmas.
  Lemma 3.4. The quantity Ek [ 1 n n∑ τ=1 ∥ek+1τ ∥2 ] is upper bounded by the expression
  ( 1− δ2 ) 1 n n∑ τ=1 ∥ekτ∥2 + 4(1−δ)η2 δnL21 n∑ τ=1 ∥∇f (τ)(wk)− hkτ∥2 + 2(1−δ)η2 L21 ( 4L̄ δ + L ) Bf (w k, xk).
  Lemma 3.5. The quantity 1n ∑n τ=1 Ek[∥hk+1τ −∇f (τ)(wk+1)∥2] is upper bounded by the expression(
  1− δ12 ) 1 n n∑ τ=1 ∥hkτ −∇f (τ)(wk)∥2 + 4L̄p ( 1 + 2pδ1 ) Bf (y k, xk) + 4L̄p ( 1 + 2pδ1 ) Bf (w k, xk).
  Under the additional Assumption 2.1, we need to analyze the evolution of ∥ek∥2 and ∥hk−∇f(wk)∥2 as well, which can be found in the appendix.
sections.heading: 3.3 Convergence analysis: main results
sections.text: With the above lemmas at hand, we are ready to construct suitable Lyapunov functions which enable us to prove linear convergence. First, we construct the Lyapunov function Φk for the general case. Let L2 := 6Ln + 112(1−δ)L̄ 3δ2 + 28(1−δ)L 3δ + 224(1−δ)L̄p δ2δ1 ( 1 + 2pδ1 ) , and for k ≥ 0 define
  Φk := Z̃k + Yk +Wk + 4L1δη · 1 n n∑ τ=1 ∥ekτ∥2 + 56(1−δ) 3θ1δ2δ1L1 · 1 n n∑ τ=1 ∥hkτ −∇f (τ)(wk)∥2.
  Then we can get the linear convergence of Φk in the following theorem. Theorem 3.6. Let Assumption 3.1 and Assumption 3.2 hold. If L1 ≥ max{Lf , 3µη}, θ1 + 2θ2 ≤ 1, and θ2 ≥ L23L1 , then we have
  E [ Φk ] ≤ ( 1−min ( µ
  µ+6θ1L1 , θ1 + θ2 − θ2 q , p(1− q), δ 6 , δ1 6
  ))k Φ0, ∀k ≥ 0.
  If Assumption 2.1 holds, we define the Lyapunov function Ψk as follows. Let L3 := 6Ln + 112(1−δ)Lf
  3δ2 + 224(1−δ)L̄ δ2n + 308(1−δ)L 3δn + 224(1−δ)p δ2δ1
  ( Lf + 9L̄ n )( 1 + 2pδ1 ) , and for k ≥ 0 define
  Ψk := Z̃k + Yk +Wk + 4L1δη ∥e k∥2 + 28L1(1−δ)δηn · 1 n n∑ τ=1 ∥ekτ∥2
  + 56(1−δ)ηδ2δ1L1 ∥h k −∇f(wk)∥2 + 504(1−δ)ηδ2δ1nL1 · 1 n n∑ τ=1 ∥hkτ −∇f (τ)(wk)∥2.
  Then we can get the linear convergence of Ψk in Theorem 3.7. Theorem 3.7. Let Assumption 2.1 , Assumption 3.1 and Assumption 3.2 hold. If L1 ≥ max{Lf , 3µη}, θ1 + 2θ2 ≤ 1, and θ2 ≥ L33L1 , then we have
  E [ Ψk ] ≤ ( 1−min ( µ
  µ+6θ1L1 , θ1 + θ2 − θ2 q , p(1− q), δ 6 , δ1 6
  ))k Ψ0, ∀k ≥ 0.
  From Theorems 3.6 and 3.7, by choosing the parameters appropriately, we can obtain the iteration complexity for ECLK. Theorem 3.8. Let Assumption 3.1 and Assumption 3.2 hold. Let L1 = max (L4, Lf , 3µη), θ2 = L4 3max{Lf ,L4} , and
  θ1 =  min (√ µ L4pθ2, θ2 ) if Lf ≤ L4p min (√ µ Lf , p3 ) otherwise .
  (i) Let L4 = L2. Then with some q ∈ [ 23 , 1), we have E[Φ k] ≤ ϵΦ0 for k ≥ O ((
  1 δ + 1 δ1 + 1p + √ Lf µ + √ L2 µp ) log 1ϵ ) .
  In particular, if p ≤ O(δ1), then the iteration complexity becomes k ≥ O ((
  1 δ + 1 p + √ Lf µ + √ L µpn + 1 δ √ (1−δ)L̄ µp + √ (1−δ)L µpδ ) log 1ϵ ) . (11)
  (ii) Let L4 = L3. If Assumption 2.1 holds, then for some q ∈ [ 23 , 1), we have E[Ψ k] ≤ ϵΨ0 for k ≥ O ((
  1 δ + 1 δ1 + 1p + √ Lf µ + √ L3 µp ) log 1ϵ ) . If p ≤ O(δ1), the iteration complexity becomes
  k ≥ O ((
  1 δ + 1 p + √ Lf µ + √ L µpn + 1 δ √ (1−δ)Lf µp + √ (1−δ)L µpδn ) log 1ϵ ) . (12)
  From Theorem 3.8, it is easy to see that the optimal p for ECLK is Θ(δ1).
  Comparison to ADIANA. ADIANA [Li et al., 2020] is an accelerated and compressed distributed method with any unbiased compressor. The iteration complexity of ADIANA is O ( ω ( 1 + √ L̄ nµ ) log 1ϵ ) when n ≤ ω, and O (( ω + √ L̄ µ + √√ ω n ωL̄ µ ) log 1ϵ ) when n > ω.
  If we choose Q and Q1 in ECLK to be the contraction compressor 1ω+1 Q̃ where Q̃ is any unbiased compressor, then δ = δ1 = 1ω+1 , and thus the complexity in (12) becomes
  O (( ω + √
  Lf µ + √ (ω+1)L µn + (ω + 1) √ ωLf µ + √ ω(ω+1)L µn ) log 1ϵ ) ,
  for p = δ1. In this case, the dependency of ω of the iteration complexity of ADIANA is better than that of ECLK. However, the full gradients are computed by all nodes at each iteration in ADIANA, which could be slower than the communication when m is very large. Furthermore, the contraction compressor could be more efficient than the unbiased compressor in practice, i.e., for the same level of compression, δ could be larger than 1/(ω+1). This efficiency of the contraction compressor is the motivation to study the error compensated methods, and in numerical experiments, ECLK is comparable to ADIANA.
sections.heading: 4 Experiments
sections.text: In this section, we experimentally study the performance of error compensated L-Katyusha (ECLK) used with several contraction compressors on the logistic regression problem for binary classification,
  x 7→ log ( 1 + exp(−yiATi x) ) + λ2 ∥x∥ 2,
  where {Ai, yi} are the training data points. We use Python 3.7 to perform the experiments. We use the datasets a5a, a9a, w6a, w8a, phishing, and mushrooms from the LIBSVM library [Chang and Lin, 2011]. The regularization parameter was set to λ = 10−3. The number of nodes in our experiments is n = 20, and the optimal solution is obtained by running the uncompressed L-Katyusha for 105 iterations. More experiments can be found in the appendix.
  Compressors. We use three contraction compressors: the TopK compressor with K = 1, or the compressor 1ω+1 Q̃, where Q̃ is either the unbiased random dithering compressor with s = √ d levels [Alistarh et al., 2017] or the natural compressor [Horváth et al., 2019b]. For the Top1 compressor, the number of communicated bits for the compressed vector is 64 + ⌈log d⌉, and δ = 1/d. For the random dithering compressor with s = √ d, the number of communicated bits for the compressed vector is 2.8d + 64, and ω = 1 [Alistarh et al., 2017] . For the natural compressor, the number of communicated bits for the compressed vector is 12d, and ω = 1/8 [Horváth et al., 2019b].
  Parameter setting. In all the experiments, we search for the optimal stepsize for all tested algorithms. In particular, we use the parameter setting in Theorem 3.8 (i) for ECLK. From Theorem 3.8 (i), we know that we can set values for all parameters if we know values of µ, δ, δ1, p, and Lipschitz constants. For the tested problem, µ = λ. Q andQ1 are chosen to be the same contraction compressor for ECLK, which implies that δ = δ1, and the lower bound for δ can be obtained easily for our used compressors. We set p = δ for ECLK except in Section 4.4. We calculate the theoretical Lf , L̄, and L as Lthf , L̄
  th, and Lth, respectively. Then we choose Lf = t ·Lthf , L̄ = t · L̄th, and L = t ·Lth, and search for the best t in the set t ∈ {10−k | k = 0, 1, 2, ...}. We set p = δ for EC-LSVRG-DIANA [Gorbunov et al., 2020]. EC-LSVRG-DIANA requires the use of an additional unbiased compressor; for this we make use of random dithering.
sections.heading: 4.1 Top1 vs random dithering vs natural compression vs no compression
sections.text: First, we compare the uncompressed L-Katyusha method with ECLK with three contraction compressors: Top1, random dithering, and natural compression; see Figure 1. ECLK is orders of magnitude better in terms of communication complexity.
sections.heading: 4.2 Comparison with EC-LSVRG-DIANA and ECGD
sections.text: Next, we compare ECLK with EC-LSVRG-DIANA [Gorbunov et al., 2020] and error compensated GD (ECGD) using the Top1, random dithering, and natural compressor. Note that ECGD is a special
  case of error compensated SGD [Stich et al., 2018] with m = 1, where the full gradient ∇f (τ)(xk) is calculated on each node. Figures 2 and 3 show that ECGD can only converge to a neighborhood of the optimal solution, and that ECLK is considerably faster than EC-LSVRG-DIANA.
sections.heading: 4.3 Comparison with ADIANA
sections.text: Let us denote by ECLK-F the special case of ECLK with m = 1, i.e., the full gradient ∇f (τ)(xk) is calculated on each node. We compare ECLK-F with the accelerated variant of DIANA, called ADIANA [Li et al., 2020], for six data sets. For ADIANA we use two unbiased compressors: random dithering and natural compression. Figure 4 shows that in terms of communication complexity, ECLK-F is comparable to ADIANA, and can be better than ADIANA in some cases.
sections.heading: 4.4 Impact of the update frequency of the reference point
sections.text: Finally, we test the impact of the update frequency of the reference point p for ECLK with Top1 compressor; see Figure 5. We choose five values for p: δ/3, δ, 3δ, 9δ, and 1. Figure 5 shows that the performance of p = δ is usually better than p = δ/3. As we increase p from p = δ, the performance of ECLK could be improved. However, if p is too large, the performance of ECLK is no better than p = δ, generally.
  Acknowledgments and Disclosure of Funding
  Xun Qian and Peter Richtárik acknowledge funding by the KAUST Baseline Research Funding Scheme, the Extreme Computing Research Center at KAUST, and administrative support from the Visual Computing Center at KAUST. Tong Zhang acknowledges further funding by GRF 16201320.
title: Error Compensated Distributed SGD can be Accelerated