summaries: This work studies the problem of decentralized nonconvex optimization problems and it is relevant to the conference. The paper provides convergence analysis for an existing and well-studied algorithm -- stochastic gradient tracking algorithms, without providing any improvements. The paper prove its algorithm the same convergence compared to existing works. There are some light and limited experiments associated with the paper, but only limited to quadratic case. This paper studies the gradient tracking method for decentralized optimization. While it is widely used, its convergence rate is not optimal compared with some other methods. This paper provides a tighter analysis for nonstrongly convex problems, strongly convex problems, and nonconvex problems. Faster convergence rates are proved in this paper. The paper studies  the gradient tracking (GT) algorithm for stochastic distributed optimization problems over undirected, static graphs; nonconvex, strongly convex and weakly convex local objective functions are considered. The claimed contribution is a new line of analysis unlocking tighter (asymptotic) convergence rates than those already developed in the literature. The impact of some network parameters on the convergence rate is also discussed, and validated via some (albeit limited)  numerical results.  This paper analyzes Gradient Tracking, a very common decentralized optimization algorithm, in the stochastic setting. The authors first introduce the standard gradient tracking algorithms, along with the assumptions they use to analyze it. Then, they provide convergence results in 3 main settings: non-convex, strongly-convex and weakly-convex. In each case, the leading order term matches the rates of centralized mini-batch SGD, meaning that the methods are fast (at least when this term dominates). It is argued that many interesting extensions naturally fit in this framework and could be adapted without too much efforts.  Then, a proof sketch is given, and highlights the importance of studying the consensus difference X_t - \bar{X_t}, where \bar{X_t} is the average over all nodes, instead of studying just X_t. The other key ingredient is that a simple recursion, can be written with the consensus difference on both GT variables. Although the operator J involved in this recursion is not contractive at each step (spectral radius greater than 1), J^i with i large enough is contractive (spectral radius smaller than 1/2), which allows to prove convergence of the recursion.  Then, the rates obtained for Gradient Tracking are compared with rates previously obtained in the literature, and they compare favorably overall. Finally, some toy experiments are given to analyze the impact of the graph-dependent constants c and p that were introduced and that appear in the higher order terms. These experiments seem to confirm the theoretical rates. 
abstractText: We consider decentralized machine learning over a network where the training data is distributed across n agents, each of which can compute stochastic model updates on their local data. The agent’s common goal is to find a model that minimizes the average of all local loss functions. While gradient tracking (GT) algorithms can overcome a key challenge, namely accounting for differences between workers’ local data distributions, the known convergence rates for GT algorithms are not optimal with respect to their dependence on the mixing parameter p (related to the spectral gap of the connectivity matrix). We provide a tighter analysis of the GT method in the stochastic strongly convex, convex and non-convex settings. We improve the dependency on p from O(p−2) to O(p−1c−1) in the noiseless case and from O(p−3/2) to O(p−1/2c−1) in the general stochastic case, where c ≥ p is related to the negative eigenvalues of the connectivity matrix (and is a constant in most practical applications). This improvement was possible due to a new proof technique which could be of independent interest.
authors.name: Anastasia Koloskova
authors.name: Tao Lin
authors.name: Sebastian U. Stich
references.authors: Sulaiman Alghunaim Ernest Ryu Kun Yuan Ali Sayed
references.title: Decentralized proximal gradient algorithms with linear convergence rates
references.venue: IEEE Transactions on Automatic Control,
references.authors: Sulaiman A. Alghunaim Ali H. Sayed
references.title: Linear convergence of primal–dual gradient methods and their performance in distributed optimization
references.authors: Mahmoud Assran Nicolas Loizou Nicolas Ballas Michael Rabbat
references.title: Stochastic gradient push for distributed deep learning
references.venue: In Proceedings of the 36th International Conference on Machine Learning (ICML). PMLR,
references.authors: Stephen Boyd Arpita Ghosh Balaji Prabhakar Devavrat Shah
references.title: Randomized gossip algorithms
references.venue: IEEE/ACM Trans. Netw.,
references.authors: Ofer Dekel Ran Gilad-Bachrach Ohad Shamir Lin Xiao
references.title: Optimal distributed online prediction using mini-batches
references.venue: Journal of Machine Learning Resesearch (JMLR),
references.authors: J.C. Duchi A. Agarwal M.J. Wainwright
references.title: Dual averaging for distributed optimization: Convergence analysis and network scaling
references.venue: IEEE Transactions on Automatic Control,
references.authors: S. Gerschgorin
references.title: Uber die Abgrenzung der Eigenwerte einer Matrix
references.venue: Bulletin de l’Académie des Sciences de l’URSS. Classe des sciences mathématiques et na,
references.authors: Lie He An Bian Martin Jaggi
references.title: COLA: Decentralized linear learning. In Advances in Neural Information Processing Systems 31 (NeurIPS), pages 4541–4551
references.authors: Franck Iutzeler Pascal Bianchi Philippe Ciblat Walid Hachem
references.title: Asynchronous distributed optimization using a randomized alternating direction method of multipliers
references.venue: In Proceedings of the 52nd IEEE Conference on Decision and Control,
references.authors: B. Johansson M. Rabi M. Johansson
references.title: A randomized incremental subgradient method for distributed optimization in networked systems
references.venue: SIAM Journal on Optimization,
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 Hubert Eichner 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.venue: Foundations and Trends R © in Machine Learning,
references.authors: Sai P. Karimireddy Satyen Kale Mehryar Mohri Sashank J. Reddi Sebastian U. Stich Ananda T. Suresh
references.title: SCAFFOLD: Stochastic controlled averaging for on-device federated learning
references.venue: In Proceedings of the 36th International Conference on Machine Learning (ICML). PMLR,
references.authors: David Kempe Alin Dobra Johannes Gehrke
references.title: Gossip-based computation of aggregate information
references.venue: In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society,
references.authors: Anastasia Koloskova Sebastian Stich Martin Jaggi
references.title: Decentralized stochastic optimization and gossip algorithms with compressed communication
references.venue: In Proceedings of the 36th International Conference on Machine Learning (ICML),
references.authors: Anastasia Koloskova Nicolas Loizou Sadra Boreiri Martin Jaggi Sebastian U. Stich
references.title: A unified theory of decentralized sgd with changing topology and local updates
references.venue: In Proceedings of the 37th International Conference on Machine Learning (ICML). PMLR,
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: Lingjing Kong Tao Lin Anastasia Koloskova Martin Jaggi Sebastian U. Stich
references.title: Consensus control for decentralized deep learning
references.venue: In Proceedings of the 38th International Conference on Machine Learning (ICML),
references.authors: Dmitry Kovalev Anastasia Koloskova Martin Jaggi Peter Richtarik Sebastian U. Stich
references.title: A linearly convergent algorithm for decentralized optimization: Sending less bits for free
references.venue: In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics (AISTATS),
references.authors: Boyue Li Shicong Cen Yuxin Chen Yuejie Chi
references.title: Communication-efficient distributed optimization in networks with gradient tracking and variance reduction
references.venue: In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (AISTATS),
references.authors: Tian Li Anit Kumar Sahu Maziar Sanjabi Manzil Zaheer Ameet Talwalkar Virginia Smith
references.title: On the convergence of federated optimization in heterogeneous networks
references.venue: arXiv preprint arXiv:1812.06127,
references.authors: Tian Li Anit Kumar Sahu Manzil Zaheer Maziar Sanjabi Ameet Talwalkar Virginia Smith
references.title: Fed- DANE: A federated Newton-type method
references.venue: arXiv preprint arXiv:2001.01920,
references.authors: Xiang Li Kaixuan Huang Wenhao Yang Shusen Wang Zhihua Zhang
references.title: On the convergence of FedAvg on non-IID data
references.venue: International Conference on Learning Representations (ICLR),
references.authors: Tao Lin Sai Praneeth Karimireddy Sebastian Stich Martin Jaggi
references.title: Quasi-global momentum: Accelerating decentralized deep learning on heterogeneous data
references.venue: In Proceedings of the 38th International Conference on Machine Learning (ICML),
references.authors: Paolo Di Lorenzo Gesualdo Scutari
references.title: NEXT: In-network nonconvex optimization
references.venue: IEEE Transactions on Signal and Information Processing over Networks,
references.authors: Songtao Lu Xinwei Zhang Haoran Sun Mingyi Hong
references.title: GNSD: a gradient-tracking based nonconvex stochastic algorithm for decentralized optimization
references.venue: In IEEE Data Science Workshop (DSW),
references.authors: 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: H. Brendan McMahan Eider Moore Daniel Ramage Blaise Agüera y Arcas
references.title: Federated learning of deep networks using model averaging
references.venue: arXiv preprint arXiv:1602.05629,
references.authors: A. Nedić A. Ozdaglar
references.title: Distributed subgradient methods for multi-agent optimization
references.venue: IEEE Transactions on Automatic Control,
references.authors: A. Nedić S. Lee M. Raginsky
references.title: Decentralized online optimization with global objectives and local communication
references.venue: In 2015 American Control Conference (ACC),
references.authors: Angelia Nedić Alex Olshevsky
references.title: Distributed optimization over time-varying directed graphs
references.venue: IEEE Transactions on Automatic Control,
references.authors: Angelia Nedić
references.title: Distributed gradient methods for convex machine learning problems in networks: Distributed optimization
references.venue: IEEE Signal Processing Magazine,
references.authors: Angelia Nedić Alex Olshevsky Wei Shi
references.title: Achieving geometric convergence for distributed optimization over time-varying graphs
references.venue: SIAM Journal on Optimization,
references.authors: Angelia Nedić Alex Olshevsky Wei Shi César A. Uribe
references.title: Geometrically convergent distributed optimization with uncoordinated step-sizes
references.venue: American Control Conference (ACC),
references.authors: Angelia Nedić Alex Olshevsky Michael G. Rabbat
references.title: Network topology and communicationcomputation tradeoffs in decentralized optimization
references.venue: Proceedings of the IEEE,
references.authors: Arkadii Semenovich Nemirovsky David Borisovich Yudin
references.title: Problem complexity and method efficiency in optimization
references.authors: Lam M. Nguyen Phuong Ha Nguyen Peter Richtárik Katya Scheinberg Martin Takáč Marten van Dijk
references.title: New convergence aspects of stochastic gradient algorithms
references.venue: Journal of Machine Learning Research,
references.authors: Shi Pu Angelia Nedić
references.title: Distributed stochastic gradient tracking methods
references.venue: Math. Program.,
references.authors: Guannan Qu Na Li
references.title: Harnessing smoothness to accelerate distributed optimization
references.venue: IEEE Transactions on Control of Network Systems,
references.authors: M. Rabbat
references.title: Multi-agent mirror descent for decentralized stochastic optimization
references.venue: In IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP),
references.authors: Wei Shi Qing Ling Gang Wu Wotao Yin
references.title: EXTRA: An exact first-order algorithm for decentralized consensus optimization
references.venue: SIAM Journal on Optimization,
references.authors: Sebastian U. Stich
references.title: Unified optimal analysis of the (stochastic) gradient method
references.venue: arXiv preprint arXiv:1907.04232,
references.authors: Sebastian U. Stich Sai P. Karimireddy
references.title: The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication
references.venue: Journal of Machine Learning Research,
references.authors: Hanlin Tang Xiangru Lian Ming Yan Ce Zhang Ji Liu
references.title: D2: Decentralized training over decentralized data
references.venue: In Proceedings of the 35th International Conference on Machine Learning (ICML),
references.authors: Hanlin Tang Xiangru Lian Shuang Qiu Lei Yuan Ce Zhang Tong Zhang Ji Liu
references.title: Deepsqueeze: Decentralization meets error-compensated compression
references.authors: John N. Tsitsiklis
references.title: Problems in decentralized decision making and computation
references.venue: PhD thesis, Massachusetts Institute of Technology,
references.authors: Isidoros Tziotis Constantine Caramanis Aryan Mokhtari
references.title: Second order optimality in decentralized non-convex optimization via perturbed gradient tracking
references.venue: In Advances in Neural Information Processing Systems (NeurIPS),
references.authors: Thijs Vogels Lie He Anastasia Koloskova Tao Lin Sai Praneeth Karimireddy Sebastian U. Stich Martin Jaggi
references.title: Relaysum for decentralized deep learning on heterogeneous data. In Advances in Neural Information Processing Systems (NeurIPS)
references.authors: Jianyu Wang Anit Kumar Sahu Zhouyi Yang Gauri Joshi Soummya Kar
references.title: MATCHA: Speeding up decentralized SGD via matching decomposition sampling
references.venue: Sixth Indian Control Conference (ICC),
references.authors: E. Wei A. Ozdaglar
references.title: Distributed alternating direction method of multipliers
references.venue: In IEEE 51st IEEE Conference on Decision and Control (CDC),
references.authors: Lin Xiao Stephen Boyd
references.title: Fast linear iterations for distributed averaging
references.venue: Systems & Control Letters,
references.authors: Ran Xin Anit Kumar Sahu Usman A. Khan Soummya Kar
references.title: Distributed stochastic optimization with gradient tracking over strongly-connected networks
references.venue: In IEEE 58th Conference on Decision and Control (CDC),
references.authors: Kun Yuan Sulaiman A. Alghunaim
references.title: Removing data heterogeneity influence enhances network topology dependence of decentralized SGD
references.venue: arXiv preprint arXiv:2105.08023,
references.authors: Kun Yuan Bicheng Ying Xiaochuan Zhao Ali H. Sayed
references.title: Exact diffusion for distributed optimization and learning - part I: algorithm development
references.venue: IEEE Trans. Signal Process.,
references.authors: Kun Yuan Bicheng Ying Xiaochuan Zhao Ali H. Sayed
references.title: Exact diffusion for distributed optimization and learning - part II: convergence analysis
references.venue: IEEE Trans. Signal Process.,
references.authors: Kun Yuan Wei Xu Qing Ling
references.title: Can primal methods outperform primal-dual methods in decentralized dynamic optimization
references.venue: IEEE Transactions on Signal Processing,
references.authors: Kun Yuan Yiming Chen Xinmeng Huang Yingya Zhang Pan Pan Yinghui Xu Wotao Yin
references.title: DecentLaM: Decentralized momentum SGD for large-batch deep training
references.venue: In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV),
references.authors: Jiaqi Zhang Keyou You
references.title: Decentralized stochastic gradient tracking for non-convex empirical risk minimization
references.venue: arXiv preprint arXiv:1909.02712,
references.authors: Minghui Zhu Sonia Martínez
references.title: Discrete-time dynamic average
references.venue: consensus. Automatica,
sections.heading: 1 Introduction
sections.text: Methods that train machine learning models on decentralized data offer many advantages over traditional centralized approaches in core aspects such as data ownership, privacy, fault tolerance and scalability [12, 33]. Many current efforts in this direction come under the banner of federated learning [17, 29, 28, 12], where a central entity orchestrates the training and collects aggregate updates from the participating devices. Fully decentralized methods, that do not rely on a central coordinator and that communicate only with neighbors in an arbitrary communication topology, are still in their infancy [24, 18].
  The work of Lian et al. [24] on decentralized stochastic gradient descent (D-SGD) has spurred the research on decentralized training methods for machine learning models. This lead to improved theoretical analyses [16] and to improved practical schemes, such as support for time-varying topologies [32, 3, 16] and methods with communication compression [45, 51, 15, 47]. One of the most challenging aspect when training over decentralized data is data-heterogeneity, i.e. training data that is in a non-IID fashion distributed over the devices (for instance in data-center training) or generated in non-IID fashion on client devices [21, 13, 22, 23]. For example, the D-SGD method has been shown to be affected by the heterogenity [16].
  In contrast, certain methods can mitigate the impact of heterogeneous data in decentralized optimization. For instance the gradient tracking (GT) methods developed by Lorenzo and Scutari [26] and Nedić et al. [34], or the later D2 method by Tang et al. [46] which is designed for communication typologies that remain fixed and do not change over time.
  ∗Current affiliation: CISPA Helmholtz Center for Information Security.
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  It is well known that GT methods do not depend on the heterogeneity of the data and that they converge linearly on distributed strongly convex problem instances without stochastic noise [26, 34]. However, when we apply these methods in the context of machine learning, we need to understand how they are affected by stochastic noise and how they behave on non-convex tasks.
  In this paper, we develop a new, and improved, analysis of the gradient tracking algorithm with a novel proof technique. Along with the parallel contribution [55] that developed a tighter analysis of the D2 algorithm, we now have a more accurate understanding of in which setting GT works well and in which ones it does not, and our results allow for a more detailed comparison between the D-SGD, GT and D2 methods (see Section 5 below).
  Our analysis improves over all existing results that analyze the GT algorithm. Specifically, we prove a weaker dependence on the connectivity of the network (spectral gap) which is commonly incorporated into the convergence rates via the standard parameter p. For example, in the strongly convex setting with stochastic noise we prove that GT converges at the rate Õ ( σ2 nε + 1 c · ( σ√ pε + 1 p log 1 ε )) where σ2 is an upper bound on the variance of the stochastic noise, and c ≥ p a new parameter (often a constant). By comparing this result with the previously best known upper bound, Õ ( σ2 nε + 1 p · ( σ√ pε + 1 p log 1 ε )) , by Pu and Nedić [39], we see that our upper bound improves the last two terms by a factor of cp ≥ 1 and that the first term matches with known lower bounds [37]. The D2 algorithm [46] only converges under the assumption that c is a constant2 and the recent upper bound from [55] coincides with our worst case complexity for GT on all topologies where D2 can be applied. We provide additional comparison of GT convergence rates in the Tables 1 and 2.
  Contributions. Our main contributions can be summarized as: • We prove better complexity estimates for the GT algorithm than known before with a new proof
  technique (which might be of independent interest). • In the non-asymptotic regime (of importance in practice), the convergence rate depends on the
  network topology. By defining new graph parameters, we can give a tighter description of this dependency, explaining why the worst case behavior is rarely observed in practice (see Section 5.1). We verify this dependence in numerical experiments. • We show that in the presence of stochastic noise, the leading term in the convergence rate of GT is
  optimal—we are the first to derive this in the non-convex setting—and matching the unimprovable rate of all-reduce mini-batch SGD.
sections.heading: 2 Related Work
sections.text: Decentralized Optimization. Decentralized optimization methods have been studied for decades in the optimization and control community [48, 30, 52, 6]. Many decentralized optimization methods
  2In D2 the smallest eigenvalue of the mixing matrix W must bounded from below: mini λi(W ) ≥ − 13 .
  [30, 11] are based on gossip averaging [14, 53, 4]. Such methods usually also work well on nonconvex problems and can be used used for training deep neural networks [3, 24, 46]. There exists other methods, such as based on alternating direction method of multipliers (ADMM) [52, 10], dual averaging [6, 31, 41], primal-dual methods [2, 19], block-coordinate methods for generalized linear models [8] or using new gradient propagation mechanisms [50].
  Decentralized Optimization with Heterogeneous Objective Functions. There exists several algorithms that are agnostic to data-heterogeneity. Notably, EXTRA [42] and decentralized primal-dual gradient methods [2] do not depend on the data heterogeneity and achieve linear convergence in the strongly convex noiseless setting. However, these algorithms are not designed to be used for non-convex tasks.
  D2 [46, 55] (also known as exact diffusion [56, 57]) and Gradient Tracking (GT) [26] (also known as NEXT [26] or DIGing [34]) are both algorithms that are agnostic to the data heterogeneity level, can tolerate the stochastic noise, and that can be applied to non-convex objectives such as the training of deep neural networks in machine learning. A limitation of the D2 algorithm is that it is not clear how it can be applied to time-varying topologies, and that it can only be used on constant mixing topologies with negative eigenvalue bounded from below by − 13 . Other authors proposed algorithms that perform well on heterogeneous DL tasks [25, 59], but theoretical proofs that these algorithms are independent of the degree of heterogeneity are still pending.
  Gradient Tracking. There is a vast literature on the Gradient Tracking method itself. A tracking mechanism was used by Zhu and Martínez [61] as a way to track the average of a distributed continuous process. Lorenzo and Scutari [26] applied this technique to track the gradients, and analyzed its asymptotic behavior in the non-convex setting with a time-varying topologies. Nedić et al. [34] analyze GT (named as DIGing) in the strongly convex noiseless case with a time-varying network. Qu and Li [40] extend the GT analysis to the non-convex, weakly-convex and strongly convex case without stochastic noise. Nedić et al. [35] allow the different stepsizes on different workers. Yuan et al. [58] analyze asymptotic behavior of GT for dynamic optimization. Pu and Nedić [39] studied the GT method on stochastic problems and strongly convex objectives. Further, Xin et al. [54] analyze asymptotic behavior of GT with stochastic noise. For non-convex stochastic functions GT was analyzed by Zhang and You [60] and Lu et al. [27]. Li et al. [20] combine GT with variance reduction to achieve linear convergence in the stochastic case. Tziotis et al. [49] obtain second order guarantees for GT.
sections.heading: 3 Setup
sections.text: We consider optimization problems where the objective function is distributed across n nodes,
  min x∈Rd
  [ f(x) := 1
  n n∑ i=1 [ fi(x) = Eξ∼Di Fi(x, ξ)
  ]] , (1)
  where fi : Rd → R denotes the local function available to the node i, i ∈ [n] := {1, . . . n}. Each fi is a stochastic function fi(x) = Eξ∼Di Fi(x, ξ) with access only to stochastic gradients∇Fi(x, ξ). This setting covers empirical risk minimization problems with Di being a uniform distribution over the local training dataset. It also covers deterministic optimization when Fi(x, ξ) = fi(x), ∀ξ.
  We consider optimization over a decentralized network, i.e. when there is an underlying communication graph G = (V,E), |V | = n, each of the nodes (e.g. a connected device) can communicate only along the edges E. In decentralized optimization it is convenient to parameterize communication by a mixing matrix W ∈ Rn×n, where wij = 0 if and only if nodes i and j are not communicating, (i, j) /∈ E. Definition 1 (Mixing Matrix). A matrix with non-negative entries W ∈ [0, 1]n×n that is symmetric (W =W>) and doubly stochastic (W1=1, 1>W =1>), where 1 denotes the all-one vector in Rn.
sections.heading: 3.1 Notation
sections.text: We use the notation x(t)i ∈ Rd, y (t) i ∈ Rd to denote the iterates and the tracking sequence, respectively, on node i at time step t. For vectors zi ∈ Rd (zi could for instance be x(t)i or y (t) i ) defined for i ∈ [n]
  we denote by z̄ = 1n ∑n i=1 zi.
  We use both vector and matrix notation whenever it is more convenient. For vectors zi ∈ Rd defined for i ∈ [n] we denote by a capital letter the matrix with columns zi, formally
  Z := [z1, . . . , zn] ∈ Rd×n , Z̄ := [z̄, . . . , z̄] ≡ Z 1n11 > , ∆Z := Z − Z̄ . (2)
  We extend this definition to gradients of (1), with∇F (X(t), ξ(t)),∇f(X(t)) ∈ Rd×n:
  ∇F (X(t), ξ(t)) := [ ∇F1(x(t)1 , ξ (t) 1 ), . . . ,∇Fn(x(t)n , ξ(t)n ) ] ,
  ∇f(X(t)) := [ ∇f(x(t)1 ), . . . ,∇f(x(t)n ) ] .
sections.heading: 3.2 Algorithm
sections.text: The Gradient Tracking algorithm (or NEXT, DIGing) can be written as( X(t+1)
  γY (t+1)
  )> = ( X(t)
  γY (t) )>( W 0 −W W ) + γ ( 0 ∇F (X(t+1), ξ(t+1))−∇F (X(t), ξ(t)) )> (GT)
  in matrix notation. Here and X(t) ∈ Rd×n denotes the iterates, Y (t) ∈ Rd×n, with Y (0) = ∇F (X(t), ξ(t)) the sequence of tracking variables, and γ > 0 denotes the stepsize. This update is summarized in Algorithm 1.
  Algorithm 1 GRADIENT TRACKING
  input Initial values x(0)i ∈ Rd on each node i ∈ [n], communication graph G = ([n], E) and mixing matrix W , stepsize γ, initialize y(0)i = ∇Fi(x (0) i , ξ (0) i ), g (0) i = y (0) i in parallel for i ∈ [n].
  1: in parallel on all workers i ∈ [n], for t = 0, . . . , T − 1 do 2: each node i sends ( x
  (t) i ,y (t) i
  ) to is neighbors
  3: x(t+1)i = ∑ j:{i,j}∈E wij ( x (t) j − γy (t) j ) . update model parameters
  4: Sample ξ(t+1)i , compute gradient g (t+1) i = ∇Fi
  ( x
  (t+1) i , ξ (t+1) i ) 5: y(t+1)i = ∑ j:{i,j}∈E wijy (t) j + ( g (t+1) i − g (t) i ) . update tracking variable 6: end parallel for
  Each node i stores and updates two variables, the model parameter x(t)i and the tracking variable y (t) i . The model parameters are updated on line 3 with a decentralized SGD update but using y(t)i instead of a gradient. Variable y(t)i tracks the average of all local gradients on line 5. Intuitively, the algorithm is agnostic to the functions heterogeneity because y(t)i is ‘close’ to the full gradient of f(x) (suppose we would replace line 5 with exact averaging in every timestep, then y(t+1)i = 1 n ∑n i=1 g (t+1) i . For further discussion of the tracking mechanism refer to [26, 34, 39].
  deg(j) for {i, j} ∈ E, see e.g. [36].
sections.heading: 3.3 Assumptions
sections.text: We first state an assumption on the mixing matrix. Assumption 1 (Mixing Matrix). Let λi(W ), i ∈ [n], denote the eigenvalues of the mixing matrix W with 1 = λ1(W ) > λ2(W ) ≥ · · · ≥ λn(W ) > −1. With this, we can define the spectral gap δ = 1−max{|λ2(W )|, |λn(W )|}, and the mixing parameters
  p = 1−max{|λ2(W )|, |λn(W )|}2 , c = 1−min{λn(W ), 0}2 . (3) We assume that p > 0 (and consequently c > 0).
  The assumption p > 0 ensures that the network topology is connected, and that the consensus distance decreases linearly after each averaging step, i.e. ∥∥XW − X̄∥∥2 F ≤ (1−p) ∥∥X − X̄∥∥2 F ,∀X ∈ Rd×n. The parameter p is closely related to the spectral gap δ as it holds p = 2δ − δ2. From this we can conclude that δ ≤ p ≤ 2δ and, asymptotically for δ → 0, p→ 2δ. Assuming a lower bound on p (or equivalently δ) is a standard assumption in the literature.
  The parameter c is related to the most negative eigenvalue. From the definition (3) it follows that the auxiliary mixing parameter c ≥ p for all mixing matrices W . The parameters p and c are only equal when |λn(W )| ≥ |λ2(W )| and λn(W ) ≤ 0. Moreover, if the diagonal entries wii (self-weights) of the mixing matrix are all strictly positive, then c has to be strictly positive. Remark 1 (Lower bound on c.). Let W be a mixing matrix with diagonal entries (self-weights) wii ≥ ρ > 0, for a parameter ρ. Then λn(W ) ≥ 2ρ− 1 and c ≥ min{2ρ, 1}.
  This follows from Gershgorin’s circle theorem [7] that guarantees λn(W ) ≥ 2ρ − 1, and hence c ≥ 1−min{2ρ− 1, 0}2 ≥ min{2ρ, 1}. For many choices of W considered in practice, most notably when the graph G has constant nodedegree and the weights wij are chosen by the popular Metropolis-Hastings rule, i.e. wij = wji = min { 1
  deg(i)+1 , 1 deg(j)+1 } for (i, j) ∈ E, wii = 1− ∑n j=1 wij ≥ 1 maxj∈[n] deg(j)
  , see also [53, 4]. In this case, the parameter c can be bounded by a constant depending on the maximal degree. Moreover, for any given W , considering 12 (W + In) instead (i.e. increasing the self-weights), ensures that c = 1. However, in contrast to e.g. the analysis in [55] we do not need to pose an explicit bound on c as an assumption. In practice, for many graphs, the parameter c is bounded by a constant (see Table 3).
  We further use the following standard assumptions: Assumption 2 (L-smoothness). Each function fi : Rd → R, i ∈ [n] is differentiable and there exists a constant L ≥ 0 such that for each x,y ∈ Rd:
  ‖∇fi(y)−∇fi(x)‖ ≤ L ‖x− y‖ . (4)
  Sometimes we will in addition assume that the functions are (strongly) convex. Assumption 3 (µ-strong convexity). Each function fi : Rd → R, i ∈ [n] is µ-strongly convex for constant µ ≥ 0, i.e. for all x,y ∈ Rd:
  fi(x)− fi(y) + µ2 ‖x− y‖ 2 2 ≤ 〈∇fi(x),x− y〉 . (5)
  Assumption 4 (Bounded noise). We assume that there exists constant σ s.t. ∀x1, . . .xn ∈ Rd
  1 n ∑n i=1 Eξi ‖∇Fi(xi, ξi)−∇fi(xi)‖ 2 2 ≤ σ2 . (6)
  We discuss possible relaxations of these assumptions in Section 4.1 below.
sections.heading: 4 Convergence results
sections.text: We now present our novel convergence results for GT in Section 4.1 and Section 4.2 below. We provide a proof sketch to explain the key difficulties and technical novelty compared to prior results later in the next Section 6.
sections.heading: 4.1 Main theorem—GT convergence in the general case
sections.text: Theorem 2. Let x(t)i , i ∈ [n], T > 2p log ( 50 p (1 + log 1 p ) )
  denote the iterates of the GT Algorithm 1 with a mixing matrix as in Definition 1. If Assumptions 1, 2 and 4 hold, then there exists a stepsize γ such that the optimization error is bounded as follows: Non-convex: Let F0 = f(x̄(0))− f? for f? ≤ minx∈Rd f(x). Then it holds
  1 T+1 ∑T t=0 ∥∥∇f(x̄(t))∥∥2 2 ≤ ε , after Õ
  ( σ2
  nε +
  σ
  ( √ pc+ p √ n)ε3/2
  + 1 + LR̃20F −1 0
  pcε
  ) ·LF0 iterations.
  Strongly-convex: Under the additional Assumption 3 with µ > 0 and weights wt ≥ 0, WT =∑T t=0 wt, specified in the proof, it holds for R 2 T+1 = ∥∥x̄(T+1) − x?∥∥2: ∑T t=0 wt WT [ E f(x̄(t))− f? ] + µ2RT+1 ≤ ε , after Õ ( σ2
  µnε +
  √ Lσ
  µ √ pc √ ε
  + L
  µpc log
  1
  ε
  ) iterations.
  General convex: Under the additional Assumption 3 with µ ≥ 0, it holds for R20 = ∥∥x̄(0) − x?∥∥2:
  1 T+1 ∑T t=0 [ E f(x̄(t))− f? ] ≤ ε , after Õ
  ( σ2
  nε2 +
  √ Lσ
  √ pcε3/2
  + L(1 + R̃20R −2 0 )
  pcε
  ) ·R20 iterations,
  where R̃20 = 1 n ∑n i=1 ‖x (0) i − x̄(0)‖2 + 1nL2 ∑n i=1 ‖y (0) i − ȳ(0)‖2.
  From these results we see that the leading term in the convergence rate (assuming σ > 0) is not affected by the graph parameters. Moreover, in this term we see a linear speedup in n, the number of workers. The leading terms of all three results match with the convergence estimates for all-reduce mini-batch SGD [5, 43] and is optimal [37]. This means, that after a sufficiently long transient time, GT achieves a linear speedup in n. This transient time depends on the graph parameters p and c, but not on the data-dissimilarity. We will discuss the dependency of the convergence rate on the graph parameters c, p more carefully below in Sections 5 and 7, and compare the convergence rate to the convergence rates of D-SGD and D2.
  Possible Relaxations of the Assumptions. Before moving on to the proofs, we mention briefly a few possible relaxations of the assumptions that are possible with only slight adaptions of the proof framework. These extensions can be addressed with known techniques and are omitted for conciseness. We give here the necessary references for completeness.
  • Bounded Gradient Assumption I. The uniform bound on the stochastic noise in Assumption 4 could be relaxed by allowing the noise to grow with the gradient norm [16, Assumption 3b]. • Bounded Gradient Assumption II. In the convex setting it has been observed that σ2 can be replaced with σ2? := 1 n ∑n i=1 Eξi ‖∇Fi(x?, ξi)−∇fi(x?)‖ 2 2, the noise at the optimum. However,
  this requires smoothness of each Fi(x, ξ), ξ ∈ Di, which is stronger than our Assumption 2. For the technique see e.g. [38]. • Different mixing for X and Y . In Algorithm 1, both the x and y iterates are averaged on the same communication topology (the same mixing matrix). This can be relaxed by allowing for two separate matrices. This follows from inspecting our proof below. • Local Steps. It is possible to extend Algorithm 1 and our analysis in Theorem 2 to allow for local computation steps. Mixing matrix would alternate between identity matrix I (no communication, local steps) and W (communication steps). However, it is non trivial to extend our analysis to the general time-varying graphs, as the product of two arbitrary mixing matrices W1W2 might be non symmetric.
sections.heading: 4.2 Faster convergence on consensus functions
sections.text: We now state an additional result, which improves Theorem 2 on the consensus problem, defined as
  min [ f(x) = 1
  n n∑ i=1 [ fi(x) := 1 2 ‖x− µi‖
  2 ]] , (7)
  for vectors µi ∈ Rd, i ∈ [n] and optimal solution x? = 1n ∑n i=1 µi. Note that this is a special case of the general problem (1) without stochastic noise (σ = 0). For this function, we can improve the complexity estimate that would follow from Theorem 2 by proving a convergence rate that does not depend on c. Theorem 3. Let f be as in (7) let Assumption 1 hold. Then there exists a stepsize γ ≤ p such that it holds 1n ∑n i=1 ∥∥x(T )i −x?∥∥2 ≤ , for the iterates GT 1 and any > 0, after at most T = Õ (p log 1 ) iterations.
sections.heading: 5 Discussion
sections.text: We now provide a discussion of these results.
sections.heading: 5.1 Parameter c
sections.text: The convergence rate in Theorem 2 depends on the parameter c, that in the worst case could be as small as p. In this case our theoretical result does not improve over existing results for the strongly convex case. However, for many graphs in practice parameter c is bounded by a constant (see Table 3 and discussion below Assumption 1).
  While we show in Theorem 3 that it is possible to remove the dependency on c entirely from the convergence rate in special cases, it is still an open question if the parameter c in Theorem 2 is tight in general.
sections.heading: 5.2 Comparison to prior GT literature
sections.text: Tables 1 and 2 compare our theoretical convergence rates in strongly convex and non convex settings. Our result tightens all existing prior work.
sections.heading: 5.3 Comparison to other methods.
sections.text: We now compare our complexity estimate of GT to D-SGD and D2 in the strongly convex case. Analogous observations hold for the other cases too.
  Comparison to D-SGD. A popular algorithm for decentralized optimization is D-SGD [24] that converges as [16]:
  Õ
  ( σ2
  µnε +
  √ L ( ζ + √ pσ )
  µp √ ε
  + L
  µp log
  1
  ε
  ) . (D-SGD)
  While GT is agnostic to data-heterogenity, here the convergence estimate depends on the dataheterogenity, measured by a constant ζ2 that satisfies:
  1 n ∑n i=1 ‖∇fi(x?)−∇f(x?)‖ 2 2 ≤ ζ2 . (8)
  Comparing with Theorem 2, GT completely removes dependence on data heterogeneity level ζ. Moreover, even in the homogeneous case when ζ = 0, GT enjoys the same rate as D-SGD for many practical graphs when c is bounded by a constant.
  Comparison to D2. Similarly to GT, D2 also removes the dependence on functions heterogeneity. The convergence rate of D2 holds under assumption that λmin (W ) > − 13 and it is equal to [55]:
  O
  ( σ2
  µnε +
  √ Lσ
  µ √ p √ ε
  + L
  µp log
  1
  ε
  ) . (D2)
  Under the assumption λmin (W ) > − 13 the parameter c is a constant, and the GT rate estimated in Theorem 2 matches (D2).
sections.heading: 6 Proof sketch of the main theorem
sections.text: Here we give a proof sketch for Theorem 2, for the special case of strongly convex objectives. We give all proof details in the appendix and highlight the main technical difficulties and novel techniques.
  Key Lemma. It is very common—and useful—to write the iterates in the form X(t) = X̄(t) + (X(t)−X̄(t)), where X̄(t) denotes the matrix with the average over the nodes. We can then separately analyze X̄(t) and the consensus difference ∆X(t) := (X(t) − X̄(t)) (and ∆Y (t) := (Y (t) − Ȳ (t))). Define W̃ = W − 11 >
  n . From the update equation (GT) we see that( ∆X(t+1)
  γ∆Y (t+1)
  )> = ( ∆X(t)
  γ∆Y (t) )> ︸ ︷︷ ︸
  =:Ψt
  ( W̃ 0 −W̃ W̃ ) ︸ ︷︷ ︸
  =:J
  +γ
  ( 0(
  ∇F (Xt+1, ξt+1)−∇F (Xt, ξt) ) (I − 11 >
  n ) )> ︸ ︷︷ ︸
  =:Et
  ,
  in short, by using the notation Ψt, J , and Et as introduced above,
  Ψt+1 = ΨtJ + γEt . (9)
  We could immediately adapt the proof technique from [16] if it would hold that the spectral radius of J is smaller than one. However, this is not the case, and in general ‖J‖ > 1. Note that for any integer i ≥ 0:
  J i = ( W̃ i 0 −iW̃ i W̃ i ) ‖J i‖2 = ‖W̃ i‖2 + i2‖W̃ i‖2 ≤ (1− p)i + i2(1− p)i , (10)
  by Assumption 1. With this observation we can now formulate a key lemma: Lemma 4 (Contraction). For any integer τ ≥ 2p log ( 50 p (1 + log 1 p ) ) it holds that ‖Jτ‖2 ≤ 12 .
  While the constants in this lemma are chosen to ease the presentation, most important for us is that after τ = Θ̃ ( 1 p ) communication rounds, old parameter values (from τ steps ago) get discounted and averaged by a constant factor. We can alternatively write the statement of Lemma 4 as∥∥ZJτ − Z̄∥∥2 F ≤ 12 ∥∥Z − Z̄∥∥2 F , ∀Z ∈ R2d×n .
  This resembles [16, Assumption 4] and the proof now follows the same pattern. A few crucial differences remain, as the result in [16] depends on a data-dissimilarity parameter which we can avoid by carefully estimating the tracking errors. For completeness, we sketch the outline and give all details in the appendix.
  Average Sequence. First, we consider the average sequences X̄(t) and Ȳ (t). As all columns of these matrices are equal, we can equivalently consider a single column only: x̄(t) and ȳ(t).
  Lemma 5 (Average). It holds that
  ȳ(t) = 1
  n n∑ i=1 ∇Fi ( x (t) i , ξ (t) i ) , x̄(t+1) = x̄(t) − γ 1 n n∑ i=1 ∇Fi ( x (t) i , ξ (t) i ) . (11)
  This follows directly from the update (GT) and the fact that X̄ = X̄W for doubly stochastic mixing matrices. The update of x̄(t) in (11) is almost identical to one step of mini-batch SGD (on a complete graph). The average sequence behaves almost as a SGD sequence:
  Lemma 6 (Descent lemma, [16, Lemma 8]). Under the Assumptions of Theorem 2 for the convex functions, the averages x̄(t) := 1n ∑n i=1 x (t) i of the iterates of Algorithm 1 with the stepsize γ ≤ 112L satisfy
  E ∥∥x̄(t+1) − x?∥∥2 ≤ (1− γµ
  2
  ) E ∥∥x̄(t) − x?∥∥2 + γ2σ2
  n − γet +
  3γL
  n n∑ i=1 E ∥∥x̄(t) − x(t)i ∥∥2, (12)
  where et = E f(x̄(t))− f?, for f? = minx∈Rd f(x).
  Consensus Distance. The main difficulty comes from estimating the consensus distance ‖Ψt‖2, in the notation introduced in (9). Note that
  ‖Ψt‖2 = 1
  n n∑ i=1 ∥∥x(t)i − x̄(t)∥∥22 + γ2n n∑ i=1 ∥∥y(t)i − ȳ(t)∥∥22 . By unrolling (9) for τ ≤ k ≤ 2τ , τ = 2p log ( 50 p (1 + log 1 p ) ) + 1 steps,
  Ψt+k = ΨtJ k + γ k−1∑ j=1 Et+j−1J k−j . (13)
  By taking the Frobenius norm, and carefully estimating the norm of the error term∥∥∑τ−1 j=1 Et+j−1J τ−j ∥∥2 F , and using Lemma 4 we can derive a recursion for the consensus distance. Lemma 7 (Consensus distance recursion). There exists absolute constants B1, B2, B3 > 0 such that for a stepsize γ < cB3Lτ
  E ‖Ψt+k‖2F ≤ 7
  8 E ‖Ψt‖2F +
  1
  128τ k−1∑ j=0 ‖Ψt+j‖2F + B1τLγ 2 c2 k−1∑ j=0 net+j + B2τγ 2 c2 nσ2. (14)
  This lemma allows to replace p with c in the final convergence rate. This is achieved by grouping same gradients in the sum ∥∥∑k−1 j=1 Et+j−1J k−j ∥∥2 F and estimating the norm with Lemma 13.
  An additional technical difficulty comes when unrolling consensus recursion (14). As iteration matrix J is not contractive, i.e. ‖J‖ > 1, then ‖Ψt+j‖2F for j < τ can be larger than ‖Ψt‖2F (up to ≈ 1p2 times as ∥∥J i∥∥2 ≤ O ( 1p2) ∀i). We introduce an additional term in the recursion that is provably non-increasing
  Φt+τ := 1
  τ τ−1∑ j=0 ‖Ψt+j‖2F .
  With this we unroll consensus recursion. Lemma 8 (Unrolling recursion). For γ < c√
  7B1Lτ ≤ 12Lτ it holds,
  E ‖Ψt‖2F ≤ (
  1− 1 64τ
  )t A0 + 22B1τLγ 2
  c2
  t−1∑ j=0 ( 1− 1 64τ )t−j nej + 20B2τγ 2 c2 nσ2 (15)
  where ej = E[f(x̄(j))− f(x?)], A0 = 16‖∆X(0)‖2F + 24γ2 p2 ‖∆Y (0)‖2F .
  It remains to combine (14) and (15) using technique from [16].
  Proof sketch of Theorem 3. Using the matrix notation introduced above, the iterations of GT on problem (7) can be written in a simple form:(
  ∆X(t+1)
  γ∆Y (t+1)
  )> = ( ∆X(t)
  γ∆Y (t) )>( W̃ γ (W − I) −W̃ (1− γ)W̃ ) ︸ ︷︷ ︸
  J′
  .
  Similar as above, also the matrix J ′ is not a contraction operator, but in contrast to J it is diagonalizable: J ′ = QΛQ−1 for some Q and diagonal Λ. It follows that ‖(J ′)t‖2 = ∥∥QΛtQ−1∥∥2 is decreasing as (1− p)t ‖Q‖2
  ∥∥Q−1∥∥2. With this observation, the proof simplifies.
sections.heading: 7 Experiments
sections.text: In this section we investigate the tightness of parameters c and p in our theoretical result.
  Setup. We consider simple quadratic functions defined as fi(x) = ‖x‖2, and x(0) is randomly initialized from a normal distribution N (0, 1). We add artificially stochastic noise to gradients as
  ∇Fi(x, ξ) = ∇fi(x) + ξ, where ξ ∼ N (0, σ 2
  d I) so that Assumption 4 is satisfied. We elaborate the details as well as results under other problem setups in Appendix C.
  We verify the dependence on graph parameters p and c for the stochastic noise term. We fix the stepsize γ to be constant, vary p and c and measure the value of f(x̄(t))− f? that GT reaches after a large number of steps. According to the theory, GT converges to the level O ( γσ2
  n + γ2σ2 pc2
  ) in a
  linear number of steps (to reach higher accuracy, smaller stepsizes must be used). To decouple the second term we need to ensure that the first term is small enough. For that, we take the number of nodes n to be large. In all experiments we ensure that the first term is at least by order of magnitude smaller than the second by comparing the noise level with GT on a fully-connected topology.
  The effect of p. First, in Figure 1 we verify the expected O (
  1 p
  ) dependence when c is a constant. For
  a fixed n = 300 number of nodes with d = 100 we vary the value of a parameter p by interpolating the ring topology (with uniform weights) with the fully-connected graph. The loss value f(x(∞)) scales linearly in 1p as can be observed in Figure 1 and the dependency on p can thus not further be improved.
  The effect of c. In Figure 2 we aim to examine the dependence of the term O
  (
  1 pc2
  )
  on the parameter
  c, in terms of 1/(pc2) and 1/(cp). We take the ring topology on a fixed number of n = 300 nodes and reduce the self-weights to achieve different values of c (see appendix for details). Otherwise the setup is as above. The current numerical results may suggest the existence of a potentially better theoretical dependence of the term c (as discussed in Section 4.2); we leave the study for future work.
sections.heading: 8 Conclusion
sections.text: We have derived improved complexity bounds for the GT method, that improve over all previous results. We verify the tightness of the second term in the convergence rate in numerical experiments. Our analysis identifies that the smallest eigenvalue of the mixing matrix has a strong impact on the performance of GT, however the smallest eigenvalue can often be controlled in practice by choosing large enough self-weights (wii) on the nodes.
  Our proof technique might be of independent interest in the community and might lead to improved analyses for other gossip based methods where the mixing matrix is not contracting (for e.g. in directed graphs, or using row- or column-stochastic matrices).
  Acknowledgments and Disclosure of Funding
  This project was supported by SNSF grant 200020_200342, EU project DIGIPREDICT, and a Google PhD Fellowship. The authors thank Martin Jaggi for his support.
title: An Improved Analysis of Gradient Tracking for Decentralized Machine Learning