An Improved Analysis of Gradient Tracking for Decentralized Machine Learning
Authors: Anastasia Koloskova
Tao Lin
Sebastian U Stich
Venue: NeurIPS 2021 Poster (2021)
Keywords: Decentralized stochastic optimization
Gradient tracking
non-iid data
decentralized optimization

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 $\mathcal{O}(p^{-2})$ to $\mathcal{O}(p^{-1}c^{-1})$ in the noiseless case and from $\mathcal{O}(p^{-3/2})$ to $\mathcal{O}(p^{-1/2}c^{-1})$ in the general stochastic case, where $c \geq 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.

An Improved Analysis of Gradient Tracking for Decentralized Machine Learning
Anastasia Koloskova EPFL mastasiaa.kloookvvdeell... ch
Tao Lin EPFL tao 1i..eeffef..hh
Sebastian Stich
EPFL"
sebastian.sticheepfl.cc
Abstract
We consider decentralized machine learning over network where the training data is distributed across agents, each of which can compute stochastic model updates on their local data. The agent's common goal find a model that minimizes the average of all local loss functions. While gradient tracking (GT) algorithms overcome key challenge, namely accounting for differences between workers' local data distributions, the known convergence rates for GT algorithms not optimal with respect to their dependence on the mixing parameter (related to the spectral gap of the connectivity matrix).
We provide a tighter analysis of the GT' method the stochastic strongly convex, convex and non-convex settings. We improve the dependency on p from Op--2) Op--1c-1) in the noiseless case and from 0pp-8/2) to Opp-1/2c-1) in the general stochastic case, where e 2 p is related to the negative eigenvalues of the connectivity matrix (and is constant in most practical applications). This improve- ment was possible due to new proof technique which could be of independent interest.
Introduction
Methods that train machine learning models on decentralized data offer many advantages over traditional centralized approaches in core aspects such data ownership, privacy, fault tolerance and scalability 122 33 Many current efforts 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 arbitrary communication topology, are still 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 improved theoretical analyses [6] and to improved practical schemes, such as support for time-varying
One of the most challenging aspect when training over decentralized data is data-heterogeneityy i.c. training data that is in non-IID fashion distributed over the devices (for instance data-center training) or For example, the D-SGD method has
topologies [32 3 16 and methods with communication compression 45 55 47
generated in non-IID fashion on client devices 11 22 23
been shown be affected by the heterogenity 16
contrast, certain methods can mitigate the impact heterogeneous data in decentralized optimiza- tion. For instance the gradient trucking (GT) methods developed by Lorenzo and Scutari (26) and Nedić al. (34), or the later D method by Tang al. [46] which is designed for communication typologies that remain fixed and do not change over time.
CCurent affiliation: CISPA Helmholtz Center for Information Security.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Table I: Important advances for Gradient Tracking in the strongly convex case. Our analysis improves upon all prior for both with and without the stochastic noise in terms of the graph parameter p.
Reference
rate of convergence to e-accuracy
considered stochastic noise
Nedić et al. 34
log
r
Alghunaim
log
log
L
Qu and Li
log
p²
a²
VL
Pu and Nedić 39
uiee
"VDDVE
VE)
d²
VTa
L
this work
log
June
Hypeo/e
ppe
' is a constant that is independent s. but can depend on other parameters, such as L.P
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 tighter analysis of the D algorithm, we now have a more accurate understanding of which setting GT works well and in which ones it does not, and results allow for more detailed comparison between the D-SGD, GT and D methods (see Section beloow.
Our analysis improves over all existing results that analyze the GT algorithm. Specifically, we prove weaker dependence on the connectivity of the network (spectral gap) which commonly incorporated into the convergence rates via the standard parameter For example, in the strongly convex setting with stochastic noise we prove that GT converges at the rate Ō
Vpe + log !)) where o² is an upper bound on the variance the stochastic noise, and c 2 a new parameter (often a constant). By comparing this result with the previously best known upper bound, Ō + ( + log ))) by Pu and Nedić [39], and that the first term matches with known lower bounds (37]. The 2 algorithm (46) only converges
ne
that upper bound improves the last terms by factor of = >
under the assumption that is constan and the recent upper bound from (55) coincides with our worst case complexity for GT on all topologies where D can be applied. We provide additional
comparison of GT convergence rates in the Tables [ and
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-asyon as-mmmtmtttic regime (of importance practice), the convergence rate depends on the graph parameters, dependency, explaining why the worst case behavior is rarely observed in practice (see Section 5.1) We verify this dependence in numerical experiments.
network topology. By defining
give tighter description of this
We show that in the presence of stochastic noise, the leading term in the convergence rate of GT is optimal-we we the first derive this in the non-convex setting- and matching the unimprovable rate of all-reduce mini-batch SGD.
2 Related Work
Decentralized Optimization. Decentralized optimization methods have been studied for decades the optimization and control community [48 30 52 (6. Many decentralized optimization methods
In D2 the smallest eigenvalue of the mixing matrix W must bounded from below: min; A:(W) 2

---

Table 2:
Important advances for Gradient Tracking in the non-convex case. Our result improves upon all existing rates in terms of the graph parameter p.
Reference
rate convergence to e-accuracy
considered stochastic noise
Lorenzo and Scutari 226
asymptotic convergence guarantees
X
Ina
Ia
Zhang and You 660
o
C
Czr
Lu et al. 27
o
g²
La²
this work
ne?
(yie
pez
"C and C2 are constants that are independent of e, but can depend on other parameters, such as or, n, L
30
are based on gossip averaging [14 53
Such methods usually also work well on non-
convex problems and can be used used for training deep neural networks B 24 46 There exists
other methods, such as based on alternating direction method of multipliers (ADMM) [22 I0, dual averaging
primal-dual methods 22 19]. block-coordinate methods for generalized linear
models g using new gradient propagation mechanisms (00.
Decentralized Optimization with Heterogeneous Objective Functions. There exists several al- gorithms that are agnostic to data-heterogeneinn 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 not designed to be used for non-convex tasks.
(also known as exact diffusion [56 57 and Gradient Tracking (GT) 26 (also known as NEXT 26 DIGing B4) 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 - Other authors proposed algorithms that perform well on heterogeneous DL tasks [25] [5), but theoretical proofs that these algorithms are independent of the degree of heterogeneity are still pending.
D2 46 55
Gradient Tracking. There is vast literature on the Gradient Tracking method itself. A tracking mechanism was used by Zhu and Martínez [6]] as way to track the average of distributed continuous process. Lorenzo and Scutari (26) applied this technique to track the gradients, and analyzed asymptotic behavior in the non-convex setting with time-varying topologies. Nedić et al. (34] analyze GT (named as DIGing) in the strongly convex noiseless case with time-varying network. Qu and Li [40] extend the GT analysis to the non-convex, weakly-conver and strongly convex case without stochastic noise. Nedić et al. (35) allow the different stepsizes different workers. Yuan et al. (58] analyze asymptotic behavior of GT for dynamic optimization. Pu and Nedić 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.
3 Setup
We consider optimization problems where the objective function is distributed across nodes,
f(x) = 1 Σ [f(x)= EEWD, Fi {)]
min XERd
(I)
where /:: . R denotes the local function available to the node i, i E [m]:= (1... n). Each f; is a stochastic function [x(x) Eę-D, (x, with access only to stochastic gradients V (x(xx E This setting covers empirical risk minimization problems with D, being uniform distribution over the local training dataset. It also covers deterministic optimization when F((x, fx(x), Ag.
3

---

We consider optimization over decentralized network, i.c. when there is an underlying communica- tion graph G = (V. E). | n. each of the nodes (e.g. a connected device) can communicate only along the edges F. In decentralized optimization it is convenient to parameterize communication by a mixing matrix W RR"x", where Wij = 0 if and only nodes and are not communicating, (i,j) $ E.
Definition 1 (Mixing Matrix), A matrix with non-negative entries W E [0, 1|nxa that is symmetric (W=W") and doubly stochastic (W1= =1=1 1, 1 W=1"), where 1 denotes the all-one vector in IR..
3.1 Notation
We use the notation x; (1) Rd y²
Rd denote the iterates and the tracking sequence, respectively, on node i at time step f. For vectors z; E IR (z, could for instance be x! or ( defined for i E [n] we denote by z ビー Z;
We use both vector and matrix notation whenever it is more convenient. For vectors z, E R defined for i E [r]] we denote by capital letter the matrix with columns z,, formally
Z = 2
zn] E _dxx
Z = Iz..... ž = 1
:Z = -- (2)
We extend this definition to gradients of TT. with ( ((1),, vf(x(1) E Rdxn;
VF(X()) ((0) = [x]] (t) ..... VF, (x( {(0)
Vf(X(9) = "f(xx")....,V(((((
3.2 Algorithm
The Gradient Tracking algorithm (or NEXT, DIGing) can be written
(
(
(x(0) (7 ) (-w { W
2) +> ( (V (VF(X(+D,,(tt)) gatt)- -V((X)) ) (GT)
matrix notation. Here and ( Rdxn denotes the iterates, y(O) E Rdxn, with Y(o) F(((()) (()) the sequence of tracking variables, and y > 0 denotes the stepsize. This update is summarized in Algorithm
Algorithm 1 GRADIENT TRACKING
input Initial values (0) E IRd on each node E [n)]. communication graph G = ([=), E) and mixing matrix W. stepsize 7. initialize y(!) (x((x)
(0) <!")), ( y
(0) in parallel for i [n].
1: in parallel all workers [n], for f 0, o.... T
do
2: each node sends (t)
(x,"
(c)
to is neighbors
3: (++1) EStiste Wiy
7y (1)
update model parameters
4: Sample <!
(1+1), compute gradient gi (t+1) VF. ((+1) {((tt)) x
5: (1+1) =Emooee wigy! + (g. (((11)
((+1) (1)
gi
update tracking variable
6: end parallel for
Each node i stores and updates variables, the model parameter x and the tracking variable y!" The model parameters are updated on line with a decentralized SGD update but using y instead of gradient. Variable (!) tracks the average of all local gradients on line 5, Intuitively, the algorithm is agnostic to the functions heterogeneity because y; is 'close' to the full gradient of fxx) (suppose
we would replace line with exact averaging in every timestep, then y ((+1) 1 ->=1 g:
((+1) For
further discussion of the tracking mechanism refer to [26] 34 39].

---

graph/topology
1/p
ring 2d-torus
O(n²)
8/9
((n)
4/5
fully connected
((1)
Table 3: Parameters p and e for some common network topologies on a nodes for uniformly averaging W, i.e. deg(s) deg(s) for {i.j} E, see e.g. [36].
Way
3.3 Assumptions
We first state an assumption on the mixing matrix.
Assumption (Mixing Matrix). Lei X:WW), E [n), denote the eigenvalues of the mixing matrix W with X1 (W) > (W) 2 2 An (W) > -1. With this, we can define the spectral gup
5 == 1- A2 (W), DAn (W)I,. and the mixing parameters
p =
max (x2x)))) Ar (W)B3
c= min m
(3)
We assume that p (and consequently >> 0).
The assumption p > ensures that the network topology is connected, and that the consensus distance decreases linearly after each averaging step, i.e. || |WW || I (1 (1-p) || [|| v. E RRdx.. The parameter p is closely related to the spectral gap it holds p 25 8². From this we conclude that 5 < p I 28 and, asymptotically for 5 + 0. p + 26. Assuming a lower bound on p (or equivalently 6) standard assumption in the literature.
The parameter is related the most negative eigenvalue. From the definition B it follows that the auxiliary mixing parameter с 2 for all mixing matrices W. The parameters p and c are only equal when (A,, (W)l [W2) and A, (W) < O. Moreover, if the diagonal entries wHe (self-weights) of the mixing matrix are all strictly positive, then has to be strictly positive.
Remark (Lower bound on c.). Let W be a mixing matrix with diagonal entries (self-weights) w/ 2 p > 0, for parameter p. Then (W) > 2p - andd 2 min 1}.
This follows from Gershgorin's circle theorem that guarantees X, (W)= 2 2p 1, and hence 2 1 - (2p - 1,0}² 2 min(2p,1}.
For many choices of W considered in practice, most notably when the graph G has constant node- degree and the weights Wij are chosen by the popular Cettrooois-Hastting rule, i.c. Way = Wj min
In this case, the parameter can be bounded by constant depending on the maximal degree. Moreover, for any given W, considering [W + I,) instead (i.e. increasing the self- self-weights), ensures that 1. However, in contrast to e.g. the analysis in [55] we do not need to pose an explicit bound on as an assumption. In practice, for many graphs, the parameter e bounded by a constant (see Table 3
dI } for (i,j) E E, Wi = 1- -ド Wij Z mmaxye(w) degG] see also 53
We further use the following standard assumptions:
Assumption (L-smoothness). Each function fo: Rd + RR i E [n]] is differentiable and there exists constant L 2 0 such that for each x,y Rd:
fv f(()) S ||x - yll
(4)
Sometimes we will in addition assume that the functions are (strongly) convex.
Assumption (j-strrnn convexity). Each function fe: Rd RR i [n) is p-sttroglyy convex for constant μ 2 0, i.e. for all x,y Rdd
ʃx(x) fuly) + 1 - -1k (V
(5)
Assumption 4 (Bounded noise). We assume that there exists constant s.f. Vx Xn Rd
ΣE B&, [[VF((x;
vs((s) 52.
(6)
We discuss possible relaxations of these assumptions in Section below.
5

---

Convergence results
We now present our novel convergence results for GT in Section 4.1 and Section 4.2 below. We provide proof sketch to explain the key difficulties and technical novelty compared to prior results later in the next Section 6
4.1 Main theorem-Gis convergence in the general case
Theorem 2.
Let x; ( [m]. T> 2 log ( [1 log ()) denote the iterates of the GT Algorithm
with mixing matrix as Definition 7 If Asssumpptios 7
hold, then there exists a stepsize
such that the optimization error is bounded as follows:
Non-convex: Let Fo = f(x(0))= - for f S minxer" f(x). Then it holds
002
+ T. Fo
El [ E, after δ + (VTC + PVN)) nE
.LFo iterations.
7+1
PCE
Strongly-comvex: Under the additional Assumption
3 with > 0 and weights 2 0, WT = Et wh specified in the proof. holds for R |x(++1) -x*1
mi Wy [E((x()) f*] + RT++ Se, after ò ( uume
+ VL
E
+
log
iterations.
MVDooV/
ppc
General convex: Under the additional Assumption 3 with 2 0, it holds for Ri = -||x(0) x+1
(02
0² ne?
VLo
L(1 Ri
R.. [x(00) - [4] s after ò
+ V/cc +
iterations,
t==
pee
where =
| 10)
x00 -
1 mI ET [yy (0) - 1100
From these results we see that the leading term the convergence rate (assuming > 0) is not affected by the graph parameters. Moreover, in this term we see a linear speedup in the number of workers. The leading terms of all three results match with the convergence estimates for all-reduce mini-batch SGD 55 4
and is optimal [37]. This means, that after 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- data-dissimilarity. We will discuss the dependency of the convergence rate on the graph parameters c, p more carefully below in Sections and 7 and compare the convergence rate to the convergence rates of D-SGD and D
Possible Relaxations of the Assumptions. Before moving on 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 could be relaxed by allowing the noise to grow with the gradient norm [6] Assumption 3b). Bounded Gradient Assumption II In the convex setting it has been observed that o² can be
replaced with o : Σm= Eg. [V E2) Vf((x)) [12 the noise at the optimum. However,
this requires smoothness of each (x E D,, which stronger than our Assumption For the technique e.g. (38).
Different mixing for and Y. In Algorithm | both the x and y iterates are averaged on the 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 I and our analysis in Theorem 2 to allow for local computation steps. Mixing matrix would alternate between identity matrix / (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 W, W2 might be non symmetric.

---

4.2 Faster convergence consensus functions
We now state an additional result, which improves Theorem 2 on the consensus problem, defined as
_ Σ [f(x) = 1 x Mill
min f(x)
for vectors μn RR, i [n]] and optimal solution x* Ei ii M₁ Note that this is special case of the general problem ( without stochastic noise (a 0). For this function, we can improve the complexity estimate that would follow from Theorem by proving a convergence rate that does not depend on
Theorem 3. Let be in 7 let Assumption hold Then there exists stepsize Y p Suchhh that 1. Ei= x (2)
holds iterations.
x S for the iterates GT and any e >> O, after at most T (plog )
Discussion
We now provide discussion of these results.
5.1 Parameter
The convergence rate in Theorem 2 depends on the parameter c, that in the worst case could be as small p. 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 constant (see Table and discussion below Assumption
While we show in Theorem 3 that is possible remove the dependency on entirely from the convergence rate in special cases, it is still an open question if the parameter e in Theorem 2 is tight general.
5.2
Comparison to prior GT literature
Tables and 2 compare our theoretical convergence rates in strongly convex and non convex settings. Our result tightens all existing prior work.
5.3
Comparison to other methods.
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 that
converges as [16]:
δ
0 Jum
0²
VL (s Vpo)
L
log
(D-SGD)
HPVe
up
While GT is agnostic to data-heterogenntty here the convergence estimate depends on the data- heterogenity, measured by constant ( that satisfies:
Σ (Vx(x')- Vf(x f(x*)
(8)
Comparing with Theorem GT completely removes dependence on data heterogeneity level Ç. when 0, GT enjoys the same rate as D-SGD for many
Moreover, even in the homogeneous practical graphs when is bounded by a constant.
Comparison to 2 Similarly to GT, D2 also removes the dependence on functions heterogeneity. The convergence rate of 2 holds under assumption that Amin (W) - and is equal to [55]:
o 0Ø²²
VLo
L
log
(D²)
uuE MVDVE
Under the assumption Amin (W) > - the parameter e is constant, and the GT rate estimated in Thcorem 2 matches D

---

Proof sketch of the main theorem
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 the form X = x (X - x where ( denotes the matrix with the average over the nodes. We can then separately analyze (() and the consensus difference A == (x x()) (and A A = (Y(0) (())).
Define W W
11_ From the update equation GTT we see that
Ax(+)) T
AX A
)
W W
0 W
0 (VF g VF(X)) (1-
+Y
in short, by using the notation V J, and Fg as introduced above,
M = V + -,
We could immediately adapt the proof technique from [16] if it would hold that the spectral radius of is smaller than one. However, this is not the case, and in general ||]]| >
Note that for any integer 2
W W
0 W
J
-
s (1 (1-p)" ((1-pp'
(10)
by Assumption D
With this observation can now formulate key lemma:
Lemma 4 (Contraction). For any integer log
50 (1+ (1+1og
b)) 1
it holds that ||
While the constants in this lemma are chosen to ease the presentation, most important for us that after r = )()) communication rounds, old parameter values (from I steps ago) get discounted and averaged by constant factor. We can alternatively write the statement of Lemma as
ZJ - 2 2 | 211
VZ E 2ddxn
This resembles 16, Assumption 4] and the proof now follows the same pattern. A few crucial differences remain, the result in [16] depends on data-dissimilarity parameter which 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 (1) and ((), As all columns of these matrices are equal, we can equivalently consider single column only: x(t) and y1).
Lemma (Average). holds that
y())
1 12 71
Σ
V ( (9))
((++1) xx(1)
1 7-
(
(II)
This follows directly from the update GT and the fact that XW for doubly stochastic mixing
matrices. The update of x(1) in (T almost identical one step of mini-batch SGD (on complete graph). The average sequence behaves almost SGD sequence:
Lemma 6 (Descent lemma,
[6 Lemma 8)). Under the Assumptions of Theorem for the convex
functions, the averages (1) satisfy
E
x()
of the iterates of Algarithm I with the stepsize 7 S T2L
E x (1+)) x1++))=xx -x11 S 711 E x01) x+1
220
3r1. Σ (1)) -x(0xxx (") (12)
ye,
n
n
where e = E)(((() - f". for f minxeRd f(x).
8

---

Consensus Distance. The main difficulty comes from estimating the consensus distance ||//l]" the notation introduced in (). Note that
in
1 n
(1)
7
n
y
(t)
y(()
2
n
By unrolling (9) for S S 2T, log
+ log 1) steps, 50
Lit = v J
E
(13)
By taking the Frobenius norm, and carefully estimating the norm of the error term |8 - Im and using Lemma 4 we can derive recursion for the consensus distance.
Lemma (Consensus distance recursion). There exists absolute constants B1, B2, Bs > 0 such that for a stepsize y B,Lr
B k-1 nettj +
B2T7 c
V
E E
+
no?.
(14)
128T
6²
==0
This lemma allows replace p with in the final convergence rate. This is achieved by grouping same gradients in the sum Σド= F and estimating the norm with Lemma 13
An additional technical difficulty comes when unrolling consensus recursion (14). As iteration matrix is not contractive, i.e. || > 1, then [|Vr+jll' I| for j < T can be larger than | I (up to ~ /
times as || non-increasing
Vi). We introduce an additional term in the recursion that is provably
T Perr
M Mets
l.
j=0
With this we unroll consensus recursion. Lemma 8 (Unrolling recursion). For y
it holds,
VTB
21r
Ao + L2 1-1
20B2ry²
E 1 < 1
ne; +
no²
(15)
64T
64T
2²
where ej = E[f(x(0) - f(x*)),, ), Ao = A6
24
|AY (0)
||
remains to combine
14 and
15)
using technique from 16
Using the matrix notation introduced above, the iterations of GT on problem 7 can be written in simple form:
Proof sketch of Theorem 3
AXT (
)
(W 1) -W W (1 - W
W
Similar as above, also the matrix J' is not a contraction operator, but contrast to diago- nalizable: J' = QAQ-! for some Q and diagonal A. It follows that [[(J')'1] = 1QAQQ is decreasing as (1 - p)1 | ||Q-'|"² With this observation, the proof simplifies.
7 Experiments
In this section we investigate the tightness of parameters and p in our theoretical result.
Setup. We consider simple quadratic functions defined as fe(x) = |x| and x is randomly initialized from normal distribution (0, 1). We add artificially stochastic noise gradients as

---

that Assumption is satisfied. We elaborate the details as well as results under other problem setups Appendix C
= where ~ (0, of
We verify the dependence on graph parameters and с for the stochastic noise term. We fix the stepsize y be constant, vary p and e and measure the value of f(x(+) f that GT reaches after large number of steps. According to the theory, GT converges the level O 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 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.
22" 2"0"
in
15
pc
The effect of p. First, in Figure 1 we verify the expected ((,) dependence when is constant. For a fixed n. = 300 number of nodes with d = 100 we vary the value of a parameter by interpolating the ring topology (with uniform weights) with the fully-connected graph. The loss value fx( scales linearly in p improved.
can be observed in Figure ] and the dependency
thus not further be
Tranning los
Traning kos
Thainnn boos
0.35
0.90
0.85
1000
0.5
1.0
1.5
2.0
2.5
102
Atp²
(a) 1/p (constant c).
(b)
1/p² (constant c).
(c) 1/p" (constant c).
Figure I: Impact of p on convergence with the stochastic noise o² = 1, when and y are kept constant. We see a linear scaling in that verifies the (z)), dependence rather than prior predicted O (+-²
The effect of In Figure 2 we aim to examine the dependence of the term O on the parameter in terms l/(p²" and l/(cp). We take the ring topology on fixed number of 300 nodes and reduce the self-weights to achieve different values of e (see appendix for details). Otherwise the setup as above. The current numerical results may suggest the existence potentially better we leave the study for future work.
theoretical dependence of the term (as discussed in Section
0.08
0.08
Training loss
Training loss
0.07
0.07
0.06
0.06
0.05
0.05
2.0
2.5
3.0
3.5
4.0
4.5
1/(pc²)
1/cp
(a) 1/(p²") (constant p).
(b) 1/(cp) (constant p).
Figure 2: Impact of on the convergence with the stochastic noise o² 1, when p and y are kept constant. We see near linear scaling in O ( while the estimate O (a²)) appears to be too conservative on this problem.
8 Conclusion
We have derived improved complexity bounds for the GT method, that improve over all previous results. We verify the tightness of the second term the convergence 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 often be controlled in practice by choosing large enough self self-weights (wy) 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- column-stochane matrices).
10

---

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.
References
[1] Sulaiman Alghunaim, Ernest Ryu, Kun Yuan, and Ali Sayed. Decentralized proximal gradient algorithms with linear convergence rates. IEEE Transactions on Automatic Control, 66(6), 2021.
[2] Sulaiman A. Alghunaim and Ali H. Sayed. [inear convergence of primal-dual gradient methods and their performance in distributed optimization Automaatiaa, 117:109003, 2020.
[3] Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Michael Rabbat. Stochastic gradient push for distributed deep lcarning. In Proceedings of the 36th International Conference on Machine Learning (ICML). PMLR, 2019.
Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. IEEE/ACM Trans. Nenw., 14(SI):2508 2530, 2006.
Randomized gossip algorithms
[5] Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao. Optimal distributed online prediction using mani-batches] Journal of Machine Learning Resesearch (JMLR), (M::)::5522222 2012.
[6] C. Duchi, Agarwal, and M. Wainwright. Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions on Automatic Control, 57(3):592-606, 2012.
[7] S. Gerschgorin. [ber die Abgrenzung der Eigenwerte einer Matrix Bulletin de l'Académie des Sciences de I'URSS. Classe des sciences mathématiques et no, 6:749 754, 1931.
[8] Lie He, An Bian, and Martin Jaggi. COLA: Decentralized linear learning In Advances in Neural Information Processing Systems 31 (NeurIPS), pages 4541 4551. Curran Associates, Inc., 2018.
[9] Wolfram Research, Inc. Mathematica, Version 12.3 2021. Champaign. IL.
[10] Franck lutzeler, Pascal Bianchi, Philippe Ciblat, and Walid Hachem. Asynchronous distributed optimiza tion using a randomized alternating direction method of multipliers In Proceedings of the 52nd IEEE Conference on Decision and Control, CDC, pages 367 1-676. IEEE, 2013.
[11] B. Johansson, M. Rabi, and M. Johansson, A randomized incremental subgradient method for distributed optimization networked systems SIAM Journal Optimization, 20(3) 2010.
[12] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mchdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafacl G. L. D' 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 Tramer, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu. Han Yu, and Sen Zhao. Advances and open problems federated learning. Foundations and Trends in Machine Learning, 14(1-2):1-210, 2021.
[13] Sai P. Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda T. Suresh. |SCAFFOLD: Stochastic controlled averaging for on-device fedcrated learning In Proceedings of the 36th International Conference on Machine Learning (ICML). PMLR, 2019.
[14] David Kempe, Alin Dobra, and Johannes Gehrke. based computation of aggregate information In Proceedings the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 2003.
[15] Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication In Proceedings of the 36th International Conference on Machine Learning (ICML), volume 97, pages 3478 3487, PMLR, 2019.

---

[16] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi. and Sebastian U. Stich. A unified theory of decentralized sgd with changing topology and local updates. In Proceedings of the 37th International Conference on Machine Learning (ICML). PMLR, 2020.
[17] Jakub Konečný, H. Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimization: Distrihuted machine learning for on-device intelligence. arXiv preprint 1210:2261..02227, 2016.
[18] Lingjing Kong, Tao Lin, Anastasia Koloskova, Martin Jaggi, and Sebastian U. Stich. Consensus control for decentralized deep learning In Proceedings of the 38th International Conference on Machine Learning (ICML), volume 139, pages 5686-5696. PMLR, 2021.
[19] Dmitry Kovalev, Anastasia Koloskova, Martin Jaggi. Peter Richtarik, and Sebastian U. Stich. A linearly convergent algorithm for decentralized optimization: Sending less bits for free! In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics (AISTA7S), volume 130, pages 4087-4095
PMLR, 2021.
[20] Boyue Li, Shicong Cen, Yuxin Chen, and Yuejie Chi. Communication--fficcenn distributed optimization in networks with gradient tracking and variance reduction In Proceedings of the Twenty Third International Conference on Artffcial Intelligence and Statisties (AISTATS), volume 108, pages 1662-1672. PMLR, 2020.
[21] Tian Li, Anit Kumar Sahu, Maziar Sanjabi, Manzil Zaheer, Ameet Talwalkar, and Virginia Smith. On the convergence of federated optimization in heterogeneous networks. arXiv preprint arXiv: 2018.
[22] Tian Li, Anit Kumar Sabu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Fed- DANE: federated Newton-type method. arXiv preprint arXiv:2001.00 019920, 2020.
[23] Xiang Li, Kaixuan Huang. Wenhao Yang, Shusen Wang, and Zhihua Zhang. On convergence of FedAvg on non-llD data. International Conference on Learning Representations (ICLR). 2020.
[24] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms' outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent In Advances in Neural Information Processing Systems 30 (NIPS), pages 5330-5340. Curran Associates, Inc., 2017.
[25] Tao Lin, Sai Praneeth Karimireddy, Sehastian Stich, and Martin Jaggi. Quasi-global momentum: Ac- celerating decentralized deep learning on heterogeneous data In Proceedings of the 38th International Conference on Machine Learning (ICML), volume 139, pages (654-6665 PMLR, 2021.
[26] Paolo Di Lorenzo and Gesualdo Scutari. NEXT: In-network nonconvex optimization. IEEE Trunsactions Signal and Information Processing over Networks, 120-160-136, 2016.
[27] Songtao Lu, Xinwei Zhang, Haoran Sun, and Mingyi Hong. GNSD: gradient-tracking based nonconvex stochastic algorithm for decentralized optimization. JEEE Data Science Workshop (DSW), pages 315-321, 2019.
[28] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communication-efficieee learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1273-1282, 2017.
[29] H. Brendan McMahan, Eider Moore, Daniel Ramage, and Blaise Aguera y Arcas. Federated learning of deep networks using model averaging arXiv preprint arXiv: 1xXx::6602.05629 2016.
[30] A. Nedić and A. Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transac- tions on Automatic Control, 54(1 34(1):48-61, -1, 2009.
[31] A. Nedić, S. Lee, and M. Raginsky. Decentralized online optimization with global objectives and local communication. In 2015 American Control Conference (ACC), pages 4497-4503. 2015.
[32] Angelia Nedié and Alex Olshevsky. Distributed optimization over time-varying directed graphs. IEFF Transactions on Automatic Control, 60(3)601-66) 1616001111,,000 2014.
[33] Angelia Nedié. Distributed gradient methods for convex machine learning problems in networks: Dis- tributed optimization. IEEE Signal Processing Magazine, 370) 2020.
[34] Angelia Nedić, Alex Olshevsky, and Wei Shi. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization. 27, 07 2016.
12

---

[35] Angelia Nedić, Alex Olshevsky. Wei Shi, and César A. Uribe. Geometrically convergent distributed optimization with uncoordinated step-sizes. In 2017 American Control Conference (ACC), pages 3950- 3955, 2017.
[36] Angelia Nedić, Alex Olshevsky, and Michael G. Rabbat. Network topology and communication- computation tradeoff's in decentralized optimization. Proceedings of the IEEE, 106(5):953 976. 2018.
[37] Arkadii Semenovich Nemirovsky and David Borisovich Yudin. Problem complexity and method efficiency in optimization. Wiley, 1983.
[38] Lam M. Nguyen, Phuong Ha Nguyen, Peter Richtárik, Katya Scheinberg, Martin Takáč, and Marten Dijk. NNww convergence aspects of stochastic gradient algorithms Journal of Machine Learning Research, 20(176):1-44 2019.
[39] Shi Pu and Angelia Nedić. Distributed stochastic gradient tracking methods. Math. Program., 187:409-455 2020.
[40] Guannan Qu and Na Li. Harnessing smoothness to accelcrate distributed optimization. IEEE Transactions on Control of Network Systems, 2017.
[41] M. Rabbat. Multi-agent mirror descent for decentralized stochastic optimization. In IEEE 6th International Workshop on Computational Advances in Multi-Sensoo Adaptive Processing (CAMSAP), pages 517-520, 2015.
[42] Wei Shi, Qing Ling, Gang Wu, and Wotao Yin. EXTRA: An exact first-order algorithm for decentralized consensus optimization. SIAM Journal on Optimization, 25(2)944-966, 2015.
[43] Sebastian U. Stich. Unified optimal analysis the (stochastic) gradient method arXiv: 19X.02990..04232. 2019.
arXiv preprint
[44] Sebastian Stich and Sai Karimireddy. The error-feedhack framework: Better rates for SGD with delayed gradients and compressed communication Journal of Machine Learning Research, 21((27):1 2020.
[45] Hanlin Tang, Shaoduo Gan, Ce Zhang, Tong Zhang, and Ji Liu. Communication compression for decentralized training] In Advances in Neural Information Processing Systems 31 (NeurlPS), pages 7663-7672 Curran Associates, Inc., 2018
[46] Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. D Decentralized training over decentralized data In Proceedings of the 35th International Conference Machine Learning (ICML), volume 80, pages 4848 4856. PMLR, 2018.
[47] Hanlin Tang, Xiangru Lian, Shuang Qiu, Lei Yuan, Ce Zhang, Tong Zhang, and Ji Liu. Deepsqueeze Decentralization meets coror-compensate compression arXiv preprint arXiv:1907.07346, 2019.
[48] John N. Tsitsiklis. Problems in decentralized decision making and computation. PhD thesis, Massachusetts Institute of Technology, 1984.
[49] Isidoros Tziotis, Constantine Caramanis, and Aryan Mokhtari. Second order optimality in decentralized non-convex optimization via perturbed gradient tracking Advances Neural Information Processing Systems (NeurlPS), volume 33, pages 1211211217 Curran Associates, Inc., 2020.
[50] Thijs Vogels, Lic Hc, Anastasia Koloskova, Tao Lin, Sai Pranceth Karimireddy, Schastian U. Stich, and Martin Jaggi. Relaysum for decentralized deep learning on heterogeneous data. In Advances in Neurul Information Processing Systems (NeurIPS). Curran Associates, Inc., 2021.
[51] Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang, Gauri Joshi, and Soummya Kar. MATCHA: Speeding up decentralized SGD via matching decomposition sampling. In 2019 Sixth Indian Control Conference (ICC), pages 299-300, 2019.
[52] E. Wei and A. Ozdaglar. Distributed alternating direction method of multipliers. In IEEE 51st IEEE Conference on Decision and Control (CDC), pages 5445-5450, 2012.
[53] Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging Systems & Control Letters, 53 (1):65-78, 2004.
[54] Ran Xin, Anit Kumar Sahu, Usman A. Khan, and Soummya Kar. Distributed stochastic optimization with gradient tracking over (CDC), pages
networks. In IEEE 58th Conference on Decision and Control
2019.
13

---

[55] Kun Yuan and Sulaiman A. Alghunaim. Removing data heterogeneity influence enhances network topology dependence of decentralized SGD. arXiv preprint arXiv:2105.08023, 2021.
[56] Kun Yuan, Bicheng Ying, Xiaochuan Zhao, and Ali H. Sayed. Exact diffusion for distributed optimization and learning part L: algorithm development IEEE Trans. Signal Process., 67(3):708 723, 2019.
[57] Kun Yuan, Bicheng Ying, Xiaochuan Zhao, and Ali H. Sayed. Exact difflusion for distributed optimization and learning part II: convergence analysis) IEEE Trans. Signal Process., 67(3):77--7,,, 2019.
[58] Kun Yuan, Wei Xu, and Qing Ling. Can primal methods outperform primal-dual methods in decentralized dynamic optimization? IEEE Transactions Signal Processing, 68:4466-4480, 2020.
[59] Kun Yuan, Yiming Chen, Xinmeng Huang, Yingya Zhang, Pan Pan, Yinghui Xu, and Wotao Yin. De- centLaM: Decentralized momentum SGD for large-batch deep training. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pages 3029-3002 3039, 2021.
[60] Jiaqi Zhang and Keyou You. Decentralized stochastic gradient tracking for non-convex empirical risk minimization, arXiv preprint (eXivv:909.022 2020.
[61] Minghui Zhu and Sonia Martínez. Discrete-time dynamic average consensus 2010. ISSN 0005-1098.
Automatica, 46(2):322-329,
14


Reviews:
[{"review_id": "n5COnreboNP", "reviewer": "Reviewer_hLSN", "summary": "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. ", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is overall well written (I found only minor typos); statement are rigorous and clear. \n\nOn the technical side, I think that the major differences from existing proofs (in particular those in [15]) are twofold:\n1. Eq.  (11) and Lemma 5 open the way to establish contraction of the error dynamics; this approach is new to my knowledge, and is of general interest. \n2. A thither analysis of the tracking error with respect to [15] is provided, which allows the authors to remove in the final error bound the dependence of data dissimilarity \nHowever, the rest of the analysis is fairly standard and does not add much to the classical roadmap followed to study such distributed algorithms. Overall the technical contribution is a bit limited. \n\nWhen it comes to the new rate bounds, I have some comments which deflect from authors' assessments.\n\n1. A key motivation provided by the authors to study GT methods is the potential heterogeneity of data across the agents. But if this is the case, the assumption that all the functions f_i have the same strong convexity constant \\mu and Liptschitz gradient constant L is quite restrictive. On the other hand, if such constants are different for each agent (which in my opinion is more compatible  with data heterogeneity) , then the convergence results would read in terms of L=\\max_i L and \\mu=\\min_i \\mu_i. If so, the claimed bound are no longer tight, as claimed by the authors. For instance, the following papers (although in the deterministic setting) provide tighter bounds for the strongly convex case (Table 1):\n\nHaishan Ye,  Ziang Zhou,  Luo Luo, Tong Zhang, \"Decentralized Accelerated Proximal Gradient Descent,\" NeurIPS 2020\n(the non acceleration comes as special case, note the dependence of the rate on the global condition number)\n\nYing Sun, Amir Daneshmand, Gesualdo Scutari, Distributed Optimization Based on Gradient-tracking Revisited: Enhancing Convergence Rate via Surrogation,\" arXiv:1905.02637\n\nincluding other non GT schemes, e.g., \n\nH Li and Z Lin \"Revisiting extra for smooth distributed optimization,\" - SIAM Journal on Optimization, 2020 \n\nI think that a much stronger contribution would be developing the analysis under different \\mu_i and L_i, still showing dependence of the rates on the parameters \\mu and L of the average loss F. However, it is not clear to me that the current analysis extend to this more general case. \n\n2. The comparison in the table can be improved. I do not think that all the rate bounds therein refers to the \"same\" optimality measure. Speaking of which, I think that characterizing the optimality of the average of the iterates does not capture directly the consensus error. I find more suitable a merit function in terms of the local agents' variables rather than just the average (which does not provide any info about the distance of the local copies from the solution). I encourage the authors to redo the analysis incorporating explicitly in the optimality matrix the consensus error. \n\n3. The authors may want to compare their result with those in \n\nK Yuan, S A. Alghunaim, B Ying and A H. Sayed \"On the Influence of Bias-Correction on DistributedStochastic Optimization,\" IEEE Trans. Signal Processing, 2020\n\nThe exact diffusion scheme there is another form of gradient correction. \n\n4. Simulations are limited. I would have expected a comparison of the GT with other distributed method employing some form of gradient correction to check whether these methods exhibit different behaviors in practice. This would also validate the tightness of the rate results. \n\n\nSome typos: \n------------------\n\n1. line 113: Hence *and*\n\n2. line 141: Section 4.1, *and .*\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some limitation in the algorithmic analysis and results are already mentioned in points 1 and 2 and 4 of my review above. I do not see other limitations. ", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "gI1kmBBUF6S", "reviewer": "Reviewer_TxXs", "summary": "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: This paper studies a widely used method and gives improved convergence rates analysis. The analysis framework follows [15]. However, a few crucial differences remain due to the specification of GT, and moreover, improved convergence rates are proved. To my best knowledge, all the previous conplexities depend on $\\frac{1}{p^2}$, while this paper improves it to $\\frac{1}{pc}$, and $c$ can be controled in practice, such as $c=1$ when we set $W$ to be $\\frac{I+W}{2}$. So I think the analysis in this paper is novel.\n\nQuality: The theory is technically solid. This is a complete work. However, I think more details of the proof should be provideded in the final version.\n\nClarity: I think this paper should be written more carefully in the final version.\n\nSignificance: I think the results in this paper are important. It provides a new way to analyze GT, and faster convergence rates are proved than previous work.\n\nComments:\n\n1. The authors claim that they improve over all known results on line 41. I suggest to cite \"Sulaiman A. Alghunaim, Ernest K. Ryu, Kun Yuan, and Ali H.Sayed. Decentralized proximal gradient algorithms with linear covnergence rates. IEEE trans. on automatic control\", which proved the $O( ( \\frac{L}{\\mu} + \\frac{1}{p^2} )log\\frac{1}{\\epsilon} )$ complexity for strongly convex problems. As a comparison, this paper only proves the $O( \\frac{L}{\\mu p} log\\frac{1}{\\epsilon} )$ one ($\\sigma=0$ and $c=1$ in (7)), which is slower when $\\frac{L}{\\mu} > \\frac{1}{p}$.\n\n2. The GT algorithm on line 112 does not lead to steps 3 and 5 in Algorithm 1. I suggest to write W on the left hand side.\n\n3. What is $\\eta_t$ in step 3 of Algorithm 1? The stepsize is $\\gamma$ in the input description.\n\n4. The authors claim that their results can be used to time-varying graphs on line 172. I am not sure whether it is correct because there are some challenges, such as the non-symmetry of $W_{l,\\tau}$ (thus, no eigenvalue decomposition exists), which is defined in Assumption 4 in [15].  Can the convergence rates still be improved over time-varying graphs? Consider (7) for example, I am interested whether the $O( \\frac{\\sigma^2}{\\mu n T} + \\frac{L\\sigma^2\\tau}{\\mu^2 p c^2 T^2} + \\frac{LR_0\\tau}{pc}\\exp(-\\frac{\\mu pcT}{L}) )$ complexity can be proved, where  $\\tau$ is the parameter in Assumption 4 in [15].\n\n5. What is $\\widetilde W$ on line 189? Is should be defiend in Section 5, rather than in Supp. A.\n\n6. What is $0<a11$ on line 555?\n\n7. How the inequality below line 571 comes? I think more details should be provided, rather than checking the proofs in [15].\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I suggest to compare with \"Sulaiman A. Alghunaim, Ernest K. Ryu, Kun Yuan, and Ali H.Sayed. Decentralized proximal gradient algorithms with linear covnergence rates. IEEE trans. on automatic control\", and discuss the complexity comparisons.", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "more than 24 hours"}, "extra_text": {}}, {"review_id": "dH6KXSYfDxA", "reviewer": "Reviewer_caUZ", "summary": "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.\n\nThen, 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.\n\nThen, 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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is globally clear and well-written, and state of the art is reviewed well. The results are significant since they show that gradient tracking, a very standard approach for linearly converging decentralized learning, achieves good rates in the stochastic setting as well. \n\nReference [14] achieves similar results with a simple decentralized SGD algorithm. Yet, I believe that this work is interesting because compared to [14], this paper gets rid of a \"data-heterogeneity\" term. This is quite important and I believe it is precisely due to using gradient tracking (or any other method that would converge to the true global minimizer without stochasticity, which is not the case of D-SGD). \n\nTime varying and local updates extensions: does it really only requires slight adaptations of the proof? If so, I believe this could significantly strengthen the results in the paper and should be included. \n\nI believe that p should be explained more in details, since it is non-standard. In particular, it would be helpful to discuss its relationship with the spectral gap of the graph: I would say from Eq (3) that it is always bigger, but of the same order of magnitude since the max of the eigenvalues should be very close to 1, but it would be good to state this explicitly. Similarly, examples on some standard graphs (ring, grid) could be given. It would also be good to do the same for parameter c, although this is partially done in Section 6.1 (but it could be useful to have it earlier). \n\nAbout Section 4.2: This seems to confirm the fact that p and delta are not so different actually. Indeed, in this case, gradient tracking converges similarly to standard (synchronous) gossip, but with delta replaced by p. Section 4.2 may be condensed into a remark to make room for more discussions on p and c. \n\nExperimental evaluation of the dependence on p and c is a good idea. I believe that linear scaling in 1/p is quite natural (if it is closely related with the spectral gap). For the c^2 term, the range of parameters considered is a bit narrow, but since it is 1/c^2 I understand it is hard to considered much wider choices of parameters.   ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No foreseeable societal impact", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "QM521g0GK8", "reviewer": "Reviewer_x8WX", "summary": "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.", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main contribution of the paper is the offering of convergence analysis for an existing and well-studied algorithm -- stochastic gradient tracking algorithms for decentralized nonconvex optimization. The problem is well-motivated and the writing is clear. There are some light simulation results thus the proposed algorithm seems work from both the theory and simulations.\n\nThe gradient tracking algorithm for decentralized nonconvex optimization is well-studied by [1], and the linear speed up rate is also well-explored by many scholars [2]. The main contribution of this work is a combination of above works into a new paper, without any convergence rate improvement [both at $\\sigma / \\sqrt{nT}$]. Also, the simulation is based on simple quadratic functions only, which is way too simple in current deep learning era and further weaken the work significance.\n\nIn short, the derived algorithm and rates seems to be correct. However, the paper is still a combine-then-twist work based on top of several existing works and show no improvement compared to existing works. The paper could be strengthened by demonstrating more significant results instead of incremental.  \n\n[1] P. Di Lorenzo and G. Scutari. Next: In-network nonconvex optimization. IEEE Transactions on Signal and Information Processing over Networks, 2(2):120–136, 2016.\n\n[2] Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. \"$ D^ 2$: Decentralized training over decentralized data.\" In International Conference on Machine Learning, pp. 4848-4856. PMLR, 2018.\n\n============================================\nAfter response period: I have carefully and thoroughly read the article and all responses and discussions. As many other reviewers also mentioned, this work is trivial and includes many typos and flaws. I keep my score unchanged.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please provide discussion on the limitations and potential negative societal impact of the work per NeurIPS' request.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies gradient tracking for stochastic decentralized learning. Their new analysis provides improved convergence rates for strongly convex functions. In particular the dependence on p (which is essentially the spectral gap) is changed to pc^2, which is always better since c>p. Moreover, as noted in the paper, c can be controlled and therefore can provide better guarantees in practice as well. This is a clean observation, and perhaps of broader interest if (11) and Lemma 5 can be used to prove contraction in other problems. 

With multiple rounds of communications a reviewer has noted that better rakes in terms of k_g can be obtained. It would be good to include that remark, and in particular emphasize that this paper does not consider multiple rounds of communication. The authors' claim about the analysis extending to time varying graphs and local updates easily are disappointing. Primarily because it is not true as one of the reviewer points out (which the authors agree to), and partly because this is a sloppiness where I am not sure if the authors even analyzed it themselves before putting this claim in the paper. At a latter point someone may think about obviousness of these things when they are unable to extend the results. 
Decision: Accept (Poster)