An Improved Analysis of Gradient Tracking for Decentralized Machine Learning
Year: 2022

Abstract:
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.

heading: 1 Introduction
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.

heading: 2 Related Work
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.

heading: 3 Setup
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.

heading: 3.1 Notation
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 ) ] .

heading: 3.2 Algorithm
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].

heading: 3.3 Assumptions
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.

heading: 4 Convergence results
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.

heading: 4.1 Main theorem—GT convergence in the general case
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.

heading: 4.2 Faster convergence on consensus functions
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.

heading: 5 Discussion
text: We now provide a discussion of these results.

heading: 5.1 Parameter c
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.

heading: 5.2 Comparison to prior GT literature
text: Tables 1 and 2 compare our theoretical convergence rates in strongly convex and non convex settings. Our result tightens all existing prior work.

heading: 5.3 Comparison to other methods.
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).

heading: 6 Proof sketch of the main theorem
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.

heading: 7 Experiments
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.

heading: 8 Conclusion
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.

Review 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.