Convergent Adaptive Gradient Methods in Decentralized Optimization
Authors: Xiangyi Chen
Belhal Karimi
Weijie Zhao
Ping Li
Venue:  (2021)
Keywords: Adam
decentralized optimization
adaptive gradient methods

Abstract: Adaptive gradient methods including Adam, AdaGrad, and their variants have been very successful for training deep learning models, such as neural networks, in the past few years. Meanwhile, given the need for distributed training procedures, distributed optimization algorithms are at the center of attention. With the growth of computing power and the need for using machine learning models on mobile devices, the communication cost of distributed training algorithms needs careful consideration. In that regard, more and more attention is shifted from the traditional parameter server training paradigm to the decentralized one, which usually requires lower communication costs. In this paper, we rigorously incorporate adaptive gradient methods into decentralized training procedures and introduce novel convergent decentralized adaptive gradient methods. Specifically, we propose a general algorithmic framework that can convert existing adaptive gradient methods to their decentralized counterparts. In addition, we thoroughly analyze the convergence behavior of the proposed algorithmic framework and show that if a given adaptive gradient method converges, under some specific conditions, then its decentralized counterpart is also convergent. 

Under review as a conference paper at ICLR 2021
CONVERGENT ADAPTIVE GRADIENT METHODS IN DE- CENTRALIZED OPTIMIZATION
Anonymous authors
Paper under double-blind review
ABSTRACT
Adaptive gradient methods including Adam, AdaGrad, and their variants have been very successful for training deep learning models. such as neural networks, in the past few years. Meanwhile, given the need for distributed training procedures, distributed optimization algorithms are at the center of attention. With the growth of computing power and the need for using machine learning models on mobile devices, the communication cost of distributed training algorithms needs careful consideration. In that regard, more and more attention is shifted from the traditional parameter server training paradigm to the decentralized one, which usually requires lower communication costs. In this paper, we rigorously incorporate adaptive gradient methods into decentralized training procedures and introduce novel con- vergent decentralized adaptive gradient methods. Specifically, we propose a general algorithmic framework that can convert existing adaptive gradient methods to their decentralized counterparts, In addition, we thoroughly analyze the convergence behavior of the proposed algorithmic framework and show that if given adaptive gradient method converges, under some specific conditions, then its decentralized counterpart also convergent.
INTRODUCTION
Distributed training of machine learning models is drawing growing attention in the past few years due to its practical benefits and necessities. Given the evolution of computing capabilities of CPUs and GPUs, computation time in distributed settings is gradually dominated by the communication time in many circumstances (Chilimbi al., 201 4; McMahan al., 2017). As a result, large amount of recent works has been focussing on reducing communication cost for distributed learning (Alistarh al., 2017; Lin et al., 2018; Wangni al., 2018; Stich al., 2018; Wang et al., 2018; Tang et al., 2019). In the traditional parameter (central) server setting, where a parameter server is employed to manage communication in the whole network, many effective communication reductions have been proposed based on gradient compression (Aji & Heafield, 2017) and quantization (Chen et al., 2010; Ge et al., 2013; Jegou et al., 2010) techniques. Despite these communication reduction techniques, its cost still, usually, scales linearly with the number of workers. Due to this limitation and with the sheer size of decentralized devices, the decentralized training parudigm (Duchi et al., 201 lb), where the parameter server is removed and each node only communicates with its neighbors, is drawing attention. It has been shown in Lian et al. (2017) that decentralized training algorithms can outperform parameter server-based algorithms when the training bottleneck is the communication cost. The decentralized paradigm is also preferred when a central parameter server is not available.
In light of recent advances in nonconvex optimization, an effective way accelerate training is by using adaptive gradient methods like AdaGrad (Duchi et al., 201 la), Adam (Kingma & Ba, 2015) AMSGrad (Reddi et al., 2018). Their popularity are due their practical benefits in training neural networks, featured by faster convergence and ease of parameter tuning compared with Stochastic Gradient Descent (SGD) (Robbins & Monro, 1951). Despite a large amount of studies within the distributed optimization literature, few works have considered bringing adaptive gradient methods into distributed training. largely due to the lack of understanding of their convergence behaviors. Notably, Reddi et al. (2020) develop the first decentralized ADAM method for distributed optimization problems with a direct application to federated learning. An inner loop is employed to compute mini-batch gradients on each node and a global adaptive step is applied to update the global parameter at each outer iteration. Yet, in the settings of our paper, nodes can only communicate to their neighbors on a fixed communication graph while a server/worker communication is required in Reddi et al. (2020). Designing adaptive methods in such settings is highly non-trivins due to the already complex update rules and to the interaction between the effect of using adaptive learning

---

Under review as a conference paper at ICLR 2021
rates and the decentralized communication protocols. This paper is attempt at bridging the gap between both realms in nonconvex optimization. Our contributions are summarized as follows:
In this paper, we investigate the possibility of using adaptive gradient methods in the decen- tralized training paradigm, where nodes have only local view of the whole communication graph. We develop a general technique that converts an adaptive gradient method from a centralized method to its decentralized variant.
By using proposed technique, present called decentralized AMSGrad, as the decentralized counterpart AMSGrad.
decentralized optimization algorithm,
We provide a theoretical verification interface, in Theroem 2, for analyzing the behavior of decentralized adaptive gradient methods obtained result of our technique. Thus, we characterize the convergence rate of decentralized AMSGrad, which is the first convergent decentralized adaptive gradient method, to the best of our knowledge.
A novel technique in our framework is mechanism to enforce a consensus adaptive learning rates at different nodes. We show the importance of consensus on adaptive learning rates by proving divergent problem instance for a recently proposed decentralized adaptive gradient method, namely DADAM (Nazari et al., 2019), a decentralized version of AMSGrad. Though consensus is performed on the model parameter, DADAM lacks consensus principles adaptive learning rates.
After having presented existing related work and important concepts of decentralized adaptive methods in Section 2, we develop our general framework for converting any adaptive gradient algorithm in its decentralized counterpart along with their rigorous finite-tima convergence analysis in Section 3 concluded by some illustrative examples of our framework's behavior in practice.
Notations: Tt.; denotes variable x at node i and iteration t. IIlblabs denotes the entry-wise L norm of matrix, i.e. || llabs = Ei. |A,il We introduce important notations used throughout the paper: for any > 0, G. : [9t,N] where [gt.v] denotes the matrix [9 I1,2 Nt.N] (where gr,z is column
vector), M2 ;= [m,.N], 1, Xx == N.,,N], (f(x)) == ト > Vf((a)))) U2 == [ur,v]. U. == [ūr.N]
V = [Vr.N], V/2 == [0r,N]. Xx == N EN Ttii U, N
Σ iml Ue, and U. == NV Ei Ue,i-
2 DECENTRALIZED ADAPTIVE TRAINING AND DIVERGENCE OF DADAM
2.1 RELATED WORK
Decentralized optimization: Traditional decentralized optimization methods include well-know algorithms such as ADMM (Boyd et al., 201 1), Dual Averaging (Duchi et al., 201 Distributed Subgradient Descent (Nedic & Ozdaglar, 2009). More recent algorithms include Extra (Shi et al., 2015), Next (Di Lorenzo & Scutari, 2016), Prox-PDA (Hong et al., 2017), GNSD (Lu et al., 2019), and Choco-SGD (Koloskova et al., 2019). While these algorithms are commonly used in applications other than deep learning, recent algorithmic advances in the machine learning community have shown that decentralized optimization can also be useful for training deep models such as neural networks. Lian al. (2017) demonstrate that stochastic version of Decentralized Subgradient Descent can outperform parameter server-base algorithms when the communication cost is high. Tang et al. (2018) propose the D2 algorithm improving the convergence rate over Stochastic Subgradient Descent. Assran et al. (2019) propose the Stochastic Gradient Push that is more robust to network failures for training neural networks. The study of decentralized training algorithms in the machine learning community is only at its initial stage. No existing work, to our knowledge, has seriously considered integrating adaptive gradient methods in the setting of decentralized learning. One noteworthy work (Nazari et al., 2019) propose decentralized version of AMSGrad (Reddi et al., 2018) 8) and it is proven to satisfy some ntn-standard regret.
Adaptive gradient methods: Adaptive gradient methods have been popular in recent years due to their superior performance in training neural networks. Most commonly used adaptive methods include AdaGrad (Duchi et al., 201 or Adam (Kingma & Ba, 2015) and their variants. Key features of such methods lie in the use of momentum and adaptive learning rates (which means that the learning rate is changing during the optimization and is anisotropic, i.e. depends the dimension). The method of reference, called Adam, has been analyzed Reddi et al. (2018) where the authors point out emror in previous convergence analyses. Since then, variety of papers have
2

---

Under review as a conference paper at ICLR 2021
been focussing analyzing the convergence behavior of the numerous existing adaptive gradient methods. Ward et al. (2019), Li & Orabona (2019) derive convergence guarantees for a variant of AdaGrad without coordinate-wise learning rates. Chen et al. (2019) analyze the convergence behavior of a broad class of algorithms including AMSGrad and AdaGrad. Zou & Shen (2018) provide a unified convergence analysis for AdaGrad with momentum. Noticeable recent works on adaptive gradient methods can be found in Agarwal et al. (2019); Luo et al. (2019); Zaheer et al. (2018).
2.2 DECENTRALIZED OPTIMIZATION
In distributed optimization (with N nodes), we aim at solving the following problem
N
min RER
Σ M(a),
(I)
where is the vector of parameters and fü is only accessible by the ith node. Through the prism of em- pirical risk minimization procedures, fi can be viewed as the average loss of the data samples located make the following mild assumptions required
at node i, for all E [N]. Throughout the paper, for analyzing the convergence behavior of the different decentralized optimization algorithms:
AL. For all i E [N]. fo is differentiable and the gradients is L-Lipschitz, ie., for all (x,y) e Rd. V fi(z) - V S L|I yll-
A2. We assume thut, at iteration I, node i accesses stochastic grudient gt.i- The stochastic gradients and the gradients of Ja have bounded Lox norms, i.e. ||gt,al| S Goe. [[r](=) I Goo.
A3. The gradient estimators are unbiased and each coordinate have bounded variance, i.e. Elga, =
V (x(ts) and F[[[ - [((sa,))))) S o², VI,
Assumptions Al and A3 are standard in distributed optimization literature. A2 is slightly stronger than the traditional assumption that the estimator has bounded variance, but is commonly used for the analysis of adaptive gradient methods (Chen et al., 2019; Ward et al., 2019). Note that the bounded gradient estimator assumption in A2 implies the bounded variance assumption in A3. In decentralized optimization, the nodes are connected as a graph and each node only communicates to its neighbors. In such case, one usually constructs N x N matrix W for information sharing when designing new algorithms. We denote X; to be its ith largest eigenvalue and define À - max ((A2), (Aw [). The matrix W cannot be arbitrary, its required key properties are listed in the following assumption:
A4. The matrix W satisfies: (1) Σj=1 W., = 1, EN" W., = 1, Wa, 2 (m) A 1, Aal <1,
|Avl < and (II) W.,j = if node and node j are not neighbors.
We now present the failure to converge of current decentralized adaptive method before introducing our proposed framework for general decentralized adaptive gradient methods.
2.3 DIVERGENCE OF DADAM
Algorithm 1 DADAM (with N nodes)
Recently, Nazari et al. (2019) initiated an at- tempt to bring adaptive gradient methods into decentralized optimization with Decentralized
1: Input: a, current point Xt, Ug,4 = 60, cl,
mo 0 and mixing matrix W
ADAM (DADAM), shown in Algorithm 1. DADAM is essentially decentralized version
2: for /= = 1, ... .T do
3:
for all i [NV] do in parallel
of ADAM and the key modification is the use of consensus step on the optimization variable
4:
St.s < (((e + Et,
5:
m,,1 = f1m4-155 1,5 + (1 B1 gr,
& to transmit information across the network, encouraging its convergence. The matrix W is doubly stochastic matrix (which satisfies A4) for achieving average consensus of x. Introducing such mixing matrix is standard for decentraliz- ing an algorithm, such as distributed gradient descent (Nedic & Ozdaglar, 2009; Yuan et al., 2016). It is proven in Nazari et al. (2019) that DADAM admits a non-standard regret bound in the online setting. Nevertheless, whether the algorithm converge to stationary points in standard offline settings such training neural networks is still unknown. The next theorem shows that DADAM may fail to converge in the offline settings.
6:
Uz.i 3201-1.5 1.5 + -1- -(-B2))g B2)
7:
62,1 = Ag0e. + 111++1110) (1-))) max (ax v1
8:
Ee+g. ; = Σ5-1 WijJt.
9:
F1+1,1 Fe43.1 V
10: end for
3

---

Under review as a conference paper at ICLR 2021
Theorem 1. There exists a problem satisfying AI-A4 where DADAM fails to converge to a stationary
points with vX(,)) = O.
Proof. Consider two-node setting with objective function f 1/ f(c and f1()) 1|[r| I 1]2x² + [| 1](4)2] -2), f2(2) | - S
1] 111-). We set the mixing matrix W = [0.5, 0.5; 0.5, 0.5). The optimal solution is x² = 1/3. Both /1 and f2 are smooth and convex with bounded gradient norm 4 and 2, respectively. We also have L =
(defined in AI). If we initialize with I1,1 = .122 = =1 and run DADAM with 31 B3- = 83 = 0 and S I, we will get 01,1 = 16 and 01.2 = 4. Since | S 4. 99.22 I 2 due to bounded gradient. and (fr, 02,2) are non-decreasing, we have ,t,,1 = 16, 02 = 4, V 2 1. Thus, after t = 1. DADAM
equivalent to running decentralized gradient descent (DGD) (Yuan et al., 2016) with a re-sealed fi and /2. i.e. running DGD on ('(x) = Σ [1(x) with f1(x) = fi (x) and fz(x) = (z5. which unique optimal x' 0.5. Define σn = (21,1 + 22,2)/2, then by Th. 2 in Yuan et al. (2016), we
have when a < 1/4, (z)) f(x)) = ((1((at)). Since f has a unique optima x', the above bound
implies F, is converging to x' = 0.5 which has non-zero gradient on function f0.5)) = 0.5. A
Theorem shows that, even though DADAM is proven to satisfy some regret bounds (Nazari et al., 2019), it can fail to converge to stationary points in the nonconvex offline setting (common for training neural networks). We conjecture that this inconsistency in the convergence behavior of DADAM is due to the definition of the regret in Nazari et al. (2019). The next section presents decentralized adaptive gradient methods that are guaranteed to converge to stationary points under assumptions and provide a characterization of that convergence in finite-time and independently of the initialization.
CONVERGENCE OF DECENTRALIZED ADAPTIVE GRADIENT METHODS
In this section, we discuss the difficulties of designing adaptive gradient methods in decentralized optimization and introduce an algorithmic framework that can turn some existing convergent adap- tive gradient methods to their decentralized counterparts. We also develop the first convergent decentralized adaptive gradient method, converted from AMSGrad, as an instance of this framework.
3.1 IMPORTANCE AND DIFFICULTIES OF CONSENSUS ON ADAPTIVE LEARNING RATES
The divergent example in the previous section implies that we should synchronize the adaptive learning rates different nodes. This can be easily achieved in the parameter server setting where all the nodes are sending their gradients to a central server at each iteration. The parameter server can then exploit the received gradients maintain sequence of synchronized adaptive learning rates when updating the parameters, see Reddi et al. (2020). However, in our decentralized setting, every node can only communicate with its neighbors and such central server does not exist. Under that setting, the information for updating the adaptive learning rates can only be shared locally instead of broadcasted over the whole network. This makes it impossible to obtain, in a single iteration, a synchronized adaptive learning rate update using all the information in the network.
Systemic Approach: On systemic level, one way to alleviate this bottleneck is to design communi- cation protocols in order to give each node access to the same aggregated gradients over the whole network, at least periodically if not at every iteration. Therefore, the nodes can update their individual adaptive learning rates based on the same shared information. However, such solution may introduce an extra communication cost since it involves broadcasting the information over the whole network.
Algorithmic Approach: Our contributions being aforementioned problem is by letting the sequences of adaptive learning rates, present on different nodes, to gradually consent, through the iterations. Intuitively, if the adaptive learning rates can consent fast enough, the difference among the adaptive learning rates on different nodes will not affect the convergence behavior of the algorithm. Consequently, no extra communication costs need to be introduced. We now develop this exact idea within the existing adaptive methods stressing on the need for relatively low-cost and easy-to-implement consensus of adaptive learning rates.
algorithmic level, another way to solve the
3.2 DECENTRALIZED ADAPTIVE GRADIENT UNIFYING FRAMEWORK
We now develop method that implements consensus of adaptive learning rates. While each node can have different 6,,; in DADAM (Algorithm 1), one can keep track of the min/max/average of these adaptive learning rates and use that quantity as the new adaptive learning rate.
4

---

Under review as a conference paper at ICLR 2021
The predefinition of some convergent lower and upper bounds may also lead to a gradual syn- chronization of the adaptive learning rates on dif- ferent nodes as developed for AdaBound in Luo et al. (2019). In this paper, present al- gorithm framework for decentralized adaptive gradient methods as Algorithm 2, which uses average consensus of it.; (see consensus update
Algorithm 2 Decentralized Adaptive Gradient Method (with N nodes)
1: Input: initial point 21, Pinits "g.
6o mo,s = O, mixing matrix W
2:
for t = 2, ... ,T do
3:
for all E [N] do in parallel
4:
It - V (i(ass)) + Et,
in line 8 and 11) help convergence. Algo-
5:
My B1m4- 1,5 (1 B1)get
rithm 2 can become different adaptive gradient methods by specifying ry as different functions. E.g., when we choose ,τ = = - R..: Al- gorithm 2 becomes decentralized version of AdaGrad. When one chooses 6t.5 to be the adap- tive learning rate for AMSGrad, tralized AMSGrad (Algorithm 3). The intuition
6:
Gg - rilli... It,,)
7:
Fz 3. -i= Wafses
8:
ūg,1 Ej=1 W Wiy 32
9:
U1 = max (uxx; t)
get decen-
10:
2441,1 Ie+ yur,s
me,t
11:
" = ū,,i - -1-1, + 02,5
of using average consensus is that for adaptive
gradient methods such as AdaGrad or Adam, 12:
end for
गt, approximates the second moment of the gradient estimator, the average of the estimations of those second moments from different nodes is an estimation of second moment on the whole network. Also, this design will not introduce any extra hyperparameters that can potentially complicate the tuning process (c in line 9 is important for numerical stability as in vanilla Adam). The main convergence result for the framework Algorithm reads as follows:
Theorem 2. Assume Al-A4, When &
2o 16L
Algorithm 2 yields the following regret bound
T
v)(X)) U!!4
1 To
do² N
E
SC1
(B(J(Z))
min ((x)) +
T
1=1
T
+ C2a Caa + TVN
(C4 + C5a)E
||(- Vi- + ii- llabss
(2)
where || |labs denotes the entry-wise L1 norm of a matrix (i.e |Allabs = -Ei, (Ail)) (). The constants
C4 -=22(c1-60 () -1) (1-111110) 1/11-1))) 2 Cg = 16L - -))G2
C max (LLxe) C2 = -))
C= 2/(2(1 ( (1]0)))2 +4/(c((1
G)) are independent of d, T and N. In addition, which quantifies the consensus error.
N EN |r.s
s -x,l (1-x) dG2
X.||²
Theorem 2 shows how the convergence guarantee is affected by different factors. In addition, one can specify a to show convergence in terms of T, d, and N. An immediate result is by setting a = VN/ /Td,, which is shown in Corollary 2.1.
Corollary 2.1. Assume A AI-A4. Set VN VTd. When regret bound
Algorithm yields the following 16
0.5
V((X,)
Vd VTN (B[J(Z)))
N +C2 + C3 T..6
N1.5
E
SCI
min (()))
T!!!
( 1
1
Co p1..0.. E [Vr
(3)
where Vr := = II( ((-Ve-2
+ Vllbboaabe and C₁ Cz. Cz. C.. Cs are defined in Theorem 2.
Corollary 2.1 shows that if E[ oT) and U, is upper bounded, then Algorithm 2 is guaranteed to converge to stationary points of the loss function. Intuitively, this means that if the adaptive learning rates on different nodes do not change too fast, the algorithm can converge. It is shown in Chen et al. (2019) that such condition can be satisfied by AdaGrad and AMSGrad. Besides, if this condition is
5

---

Under review as a conference paper at ICLR 2021
violated, the algorithm may diverge (e.g., Adam). Later, we will show convergence of decentralized versions of AMSGrad and AdaGrad by bounding this term as ((N)) and O d log())) respectively, The intuition B[y]] o(T)) can guarantee divergence is that the correlation between ,, and a (due to their shared dependency on historical gradients) can make update direction negatively correlated with true gradient in expectation, leading to non-negligible bias in updates. However, the total bias across I" iterations introduced by such a correlation is bounded by the term [E[rr] Thus, if E[Vr] grows sublinearly with T, convergence can still be guaranteed. Furthermore, Corollary 2.1 conveys the benefits of using more nodes in the graph. When T is large enough such that the term O(VN/VTd) dominates the RHS of (3), linear speedup can be achieved by increasing N.
We now present, in Algorithm 3, a notable special case of our algorithmic framework, namely Decentralized AMSGrad, which is a decentralized variant of AMSGrad. Compared with DADAM, the above algorithm exhibits a dynamic average consensus mechanism to keep track of the average of { stored as ū ith node, and uses We, max i e) for updating the adaptive learning rate for ith node. As the number of iteration grows, even though Üt,; on different nodes can converge to different constants, the Mt,; will converge to the same number lim 1 Ei= 6z,i if the
t-000 N
This average consensus mechanism enables the consensus of adaptive learning rates on different nodes, which accordingly guarantees the convergence of the method to stationary points. The consensus of adaptive learning rates is the key difference between decentralized A.SGGrad and DADAM and is the reason why decentralized AMSGrad is convergent while DADAM is not.
limit exists.
One may notice that decentralized AMSSGrd does not reduce to AMSGrad for N 1 since the quantity u in line 10 is calculated based on 14- instead of Uz This design encourages the execution of gradient computation and com- munication a parallel manner. Specifically, line 4-7 (line 4-6) in Algorithm 3 (Algorithm 2) can be executed in parallel with line 8-9 (line
Algorithm 3 Decentralized AMSGrad (with N
nodes)
1: Input: learning rate a, initial point 21, Finit, Vg,i 0p.i = el (with e 2 0), mo, =
O, mixing matrix W
2:
for t 1,2, ... ' do
3:
for all i E [N] do in parallel
7-8) to overlap communication and computation time. If u,, depends on Dt,s which in turn de- pends on St.s. the gradient computation must finish before the consensus step of the adaptive learning rate in line 9. This can slow down the running time per-iteration of the algorithm. To avoid such delayed adaptive learning, adding
4:
It.s + (I( + Et.i
5:
m,,; = Bi 1,5 + (1 31 )9,i
6:
Ut = B2u1-1. + +(1+ - --2)99
7:
G. = max(0t-1.i) ve.i)
8:
F , = -E== Wojsees
9:
0g, Σ/=1 W, Wi
J ut, 12-1,5 + de,; before line 9 and get rid of line 12 in Algorithm 2 is an option. Similar convergence guarantees will hold since
10:
", = max(ūr,s: E)
11:
F1+1,1 1e+ yur.
ma,i.
12:
ū = ūr,i - -1-1,1 + 02,5
one can easily modify our proof of Theorem 2 for such update rule. As stated above, Algo-
13: end for
rithm 3 converges, with the following rate:
0.5 Theorem 3. Assume AI-A4. Set a = 1/VTd. When a S iet. Algorithm 3 yields the following regret bound
1
T E
V(()))
Vd TN
N (D, + (0)+ C + C% C371.5003 + C2
N1.
VN
T + C N N. T1.5
< C
T
T!!!!
t=1
where Dy Dy:=E[f(22) -[Ef(Z))) f1)) = C2 = C2. Cy Cs, C² = C.G2 and C² = CsG2.. xc
C1,C2, Ca, C4, Cs are constants independent of d, T and N defined in Theorem 2. In addition, the
consensus of variables at different nodes is given by 1 E.NIITA X.I| < N (+x) G2
Theorem 3 shows that Algorithm 3 converges with rate of O O(Vd/vT) when T is large, which is the best known convergence rate under the given assumptions. Note that in some related works, SGD admits a convergence rate of ((1/VT) without any dependence on the dimension of the problem. Such improved convergence rate is derived under the assumption that the gradient estimator have bounded T22 norm, which can thus hide dependency of Vil in the final convergence rate. Another

---

Under review as a conference paper at ICLR 2021
remark is the convergence measure can be converted to + - E
[X)) using the fact that
Elooo & Go (by update rule of Algorithm 3), for the ease of comparison with existing literature.
3.3 CONVERGENCE ANALYSIS
The detailed proofs of this section are reported the supplementary material.
Proof of Theorem 2: We now present proof sketch for out main convergence result of Algorithm 2. Step 1: Reparameterization. Similarly to Yan et al. (2018); Chen et al. (2019) with SGD (with momentum) and centralized adaptive gradient methods, define the following auxiliary sequence:
B1 1 31 XX - Xt-1),
Z, = +
(4)
with X X, Such an auxiliary sequence can help us deal with the hias brought by the momentum and simplifies the convergence analysis. An intermediary result needed to conduct our proof reads: Lemma 1. For the sequence defined in (4), we have
Ze11 Ze 0
B1
Σ
11 O
Gt
1
Wt
Lemma does not display any momentum term in N Ei= V This simplification is convenient
since it is directly related to the current gradients instead of the exponential average past gradients.
Step 2: Smoothness. Using smoothness assumption Al involves the following scalar product term:
Ni = (Vf(Z)), NV Ei //(t,://VU, which can be lower bounded by:
v)(X,) +) 0
3
VS(Z) V
3
N ΣN
N v.(((..)) -f(
1it 2 2
2
1/1
2
U2/4
The above inequality substituted in the smoothness condition f(Z(-1) f(Z,) + (Vf( Ze+1
Z+) + 2 Z 2 yields:
1
Σn
E
(x+)
S
2
E + Σ E 11
T
2 D1
2D
3D3
T
U!/4
Ta
Ta
T 81
T
where 4, ( - (( D1, D2 and D3 are three terms, defined in the supplementary material, and which can be tightly bounded from above. We first bound D3 using the following quantities of interest:
Σ Z1 - Xx
T
$ T
(
B1
2 a²d d
and Σ Σ
X1I|
< Ta
dG2
1
1=1
where À= max(1>2), |>vl) and recall that X; is ith largest eigenvalue of W.
Then, concerning the term D2, few derivations, not detailed here for simplicity, yields:
D2 <
EE
Σ
Ü.agi Haae
N
1=2
where qi is the eigenvector corresponding to /th largest eigenvalue of W and ||. llabs the entry-wise L, norm of matrices. We can also show that
A
Ürani llats S VN
o=0 1- x 11-vo-1 + Vo)
1=2
7

---

Under review as a conference paper at ICLR 2021
resulting in upper bound for D2 proportional to
Eo=o 11(-vo-1 Vo)llabs Similarly:
1
D1 G
((-V-2 Va-i)llabs
2 VN
Step 3: Bounding the drift term variance. An important term that needs upper bounding in proof the variance of the gradients multiplied (element-wise) by the adaptive learning rate:
d o² N
E
ūt,i
where 1// = 1/N Σ
(i(
Two consecutive and simple bounding of the above yields:
1
Σ E
E
r
0
Ve
Vuees
VU.
and
v
Vf(XX)) (f((
E
+
E
(6)
VU,
VU,
Then, by plugging the LHS of (6) in (5), and further bounding as operated for D2, D3 (see supple- ment), we obtain the desired bound in Theorem
Proof of Theorem 3: Recall the bound in (3) of Theorem 2. Since Algorithm 3 is special
case of Algorithm 2, the remaining of the proof consists in characterizing the growth rate of E 11(1/-22 V/-i)llaba]- By construction, V non decreasing, then it can be shown that E (- + [ Besides, since for all t, l1 |oo S Go and oe, is an exponential moving average of o. k 1,2, ,, we have [ $ Gh for all i,j. By construction of Vi, we also observe that each element of V. cannot be greater than C i.e. [[ S G for all 1, i, Given that [ 2 0, we have
E 1- Vaaeel
N
N
E Σ
(1-Vi2+-1-1)) =
IE
(60o, + (
BIG NdG.
j=1
==
Substituting into (3) yields the desired convergence bound for Algorithm 3.
3.4 ILLUSTRATIVE NUMERICAL EXPERIMENTS
In this section, we conduct some experiments to test the performance of Decentralized AMSGrad, developed in Algorithm on both homogeneous data and heterogeneous data distribution (i.e. the data generating distribution on different nodes are assumed to be different). Comparison with DADAM and the decentralized stochastic gradient descent (DGD) developed in Lian al. (2017) are conducted. We train Convolutional Neural Network (CNN) with convolution layers followed by fully connected layer on MNIST (LeCun, 1998). We set 10-6 6 for both Decentralized AMSGrad and DADAM. The learning rate is chosen from the grid [10-1 10-2, 2,103,, 10-1, 10-5, 10-6) based on validation accuracy for all algorithms. In the following experiments, the graph contains 5 nodes and each node only communicate with its two adjacent neighbors forming cycle. Regarding the mixing matrix W, we set Wi = 1/3 nodes and j are neighbors and W,, = 0 otherwise. More details and experiments can be found in the supplementary material of our paper.
dusentsliuua
decemtaalone AMSOne
trainingo loss
test accuracy
trinning Joss
DADAM
test accuracy
DGD
1.5
0.95
decentraliined AMSGro
DADAM
docennndieed AMSGrad
R2
DGD
03
DADAM
DGD
1000
800
iterations
iterations
iterations
100
iterations
(a) Homogencous data
(b) Heterogeneous data
Figure I: Training loss and Testing accuracy for homogeneous and heterogencous data
8

---

Under review as a conference paper at ICLR 2021
Homogeneous data: The whole dataset is shuffled and evenly split into different nodes. Such setting is possible when the nodes are in a computer cluster. We see, Figure [()), that decentralized AMSGrad and DADAM perform quite similarly while DGD is much slower both in terms of training loss and test accuracy. Though the (possible) non convergence of DADAM, mentioned this paper, its performance are empirically good on homogeneous data. The reason is that the adaptive learning rates tend to be similar on different nodes in presence of homogeneous data distribution. We thus compare these algorithms under the heterogeneous regime.
Heterogeneous data: Here, each node only contains training data with two labels out of ten. Such a setting common when data shuffling is prohibited, such in federated learning. We can see that each algorithm converges significantly slower than with homogeneous data. Especially. the performance of DADAM deteriorates significantly. Decentralized AMSGrad achieves the best training and testing performance in that setting as observed Figure ((b).
4 EXTENSION TO ADAGRAD
In this section, we provide decentralized version of AdaGrad (optionally with momentum) converted by Algorithm 2, further supporting the usefulness of the decentralization framework.
The required modification for decentralize AdaGrad is specify line 4 of Algorithm 2 as
01,6 = 11- + 7o..
which equivalent 64,4 = E k= P... Throughout this section, we will call this algorithm decentralized AdaGrad. There are two details in the algorithm worth mentioning. One is that the framework uses momentum my,; in updates, while original AdaGrad does not use momentum. The momentum can be turned off by setting 31 0 and the convergence results will hold. The other one is that in decentralized AdaGrad, we use average instead of sum in 6z,5. Lee or,; = + ae. This is different from original AdaGrad which should use ûz, = =it Z. The reason original AdaGrad, a constant stepsize (a independent of t or 2) used with 0z.i Σi= gh. and this is equivalent to using well-known diminishing stepsize sequence a₁ V with út,; = Σi= g..- In our convergence analysis which will be presented later, we will use a constant stepsize a = 0 +
to replace the diminishing stepsize sequence a = 0 ( Such a replacement is popularly used in SGD analysis to simplify analysis and achieving better convergence rate. In addition, it is easy to modify our theoretical framework to apply diminishing stepsize sequences such as aN = 0 (z)))
The convergence analysis for decentralized AdaGrad is shown Theorem 4.
Theorem 4. Assume A 1-44. Set a = /N/VTd. /Td When a S 16L following regret bound
2o
decentralized AdaGrad yields the
V v((x))
Civd VTN
C² + D', + T T15 + VN(11 + +og((T)
CNN5
Vd (dC's + To.5 CJ),
Σ t=1
E
J.!
T
= C2. C/ = C3. C²2 C₂ and C² C5G C2, C2, C3, Ct, Cs are defined in Theorem 2 independent of d, T and N. In addition,
where D', Eif(Zz)] min, f(2)] 02, C² C1. C2=
the consensus of variables at different nodes is given by N E 1| X, <
2 N
T
1-x
G2 1
5 CONCLUSION
This paper studies the problem of designing adaptive gradient methods for decentralized training. We propose unifying algorithmic framework that can convert existing adaptive gradient methods to decentralized settings. With rigorous convergence analysis, we show that if the original algorithm satisfies converges under some minor conditions, the converted algorithm obtained using our proposed framework is guaranteed to converge to stationary points of the regret function. By applying framework to AMSGrad, we propose the first convergent adaptive gradient methods, namely Decentralized AMSGrad. Experiments show that the proposed algorithm achieves better performance than the baselines.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Naman Agarwal, Brian Bullins, Xinyi Chen, Elad Hazan, Karan Singh, Cyril Zhang, and Yi Zhang. Efficient full-matrix adaptive regularization. In International Conference on Machine Learning. pp. 102-110,, 2019.
Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent. In Empirical Methods in Natural Language Processing, pp. 140-445, 2017.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication- efficient sgd via gradient quantization and encoding. In Advances in Neural Information Processing Systems, pp. 1709-1720, 2017.
Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Mike Rabbat. Stochastic gradient push for distributed deep learning. In International Conference on Machine Learning, pp. 344-353, 2019.
Stephen Boyd, Neal Parikh, Eric Chu, Borja Pelcato, Jonathan Eckstein, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine learning, 3(1):1-122, 2011.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of adam-type algorithms for non-convex optimization. International Conference for Learning Representations, 2019.
Yongjian Chen, Tao Guan, and Cheng Wang. Approximate nearest neighbor search by residual vector quantization. Sensors, 10(12): 2010.
Trishul Chilimbi, Yutaka Suzue, Johnson Apacible, and Karthik Kalyanaraman. Project adam: Building an efficient and scalable deep learning training system. In Symposium on Operating Systems Design and Implementation, pp. 571-582, 2014.
Paolo Di Lorenzo and Gesualdo Scutari. Next: In-network nonconvex optimization. IEEE Transac- tions on Signal and Information Processing over Networks, 123-166-33,, 2016.
John Duchi, Flad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 120u1)221112215) 201 la.
John C Duchi, Alekh Agarwal, and Martin Wainwright. Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions on Automatic control, 57(3): 592-606, 201 lb.
Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. Optimized product quantization for approximate nearest neighbor search. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 2013.
Mingyi Hong.
Davood Hajinezhad, and Ming-Man Zhao. Prox-pda: The proximal primal-dual algorithm for fast distributed nonconvex optimization and learning over networks. In International Conference on Machine Learning, pp. 1539-1538, 2017.
Herve Jegou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence, 33(1):117-228, 2010.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International
Conference on Learning Representations, 2015.
Anastasia Koloskova, Sebastian U Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning, pp. 1477-3487,, 2019.
Yann LeCun. The mnist database of handwritten digits. lutp://yann. lecun. com/exdb/mnist/, 1998.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In International Conference on Artificial Intelligence and Statistics, pp. 983-992, 2019.
10

---

Under review as a conference paper at ICLR 2021
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsich, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems, pp. $330-5340 2017.
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. International Conference Learning Reprexentations, 2018
Songtao Lu, Xinwei Zhang. Haoran Sun, and Mingyi Hong. Gnsd: A gradient-tracking based nonconvex stochastic algorithm for decentralized optimization. In 2019 IEEE Data Science Workshop (DSW), pp. 315-321, 2019.
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. In International Conference for Learning Representations, 2019.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. learning of deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp. 1273-1282, PMLR, 2017.
Communication
Parvin Nazari, Davoud Ataee Tarzanagh, and George Michailidis. Dadam: A consensus- based distributed adaptive gradient method for online optimization. arXiv preprini arXiv: 10XXxv:90100010000 2019.
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48, 2009.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00295, 2020.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400 400-407, 1951.
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.
Sebastian U Stich, Jean- Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. In Advances in Neural Information Processing Systems. pp. 4447-4458, 2018.
Hanlin Tang. Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. D2: Decentralized training over decentralized data. In International Conference on Machine Learning, pp. 4848-4856, 2018.
Hanlin Tang, Chen Yu, Xiangru Lian, Tong Zhang, and Ji Liu. Doublesqueeze: Parallel stochastic gradient descent with double-pass compensaee compression. In International Conference Machine Learning, pp. 6155-6165, 2019.
Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright. Atomo: ciammuiccation-fffcccee learning via atomic sparsification. In Advances in Neural Information Processing Systems, pp. 9850-9861, 2018.
Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient sparsification for communication efficient distributed optimization. In Advances in Neural Information Processing Systems, pp- 1299-1309, 2018.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. In International Conference on Machine Learning, pp. 6677-6686, 2019.
Yan Yan, Tianbao Yang, Zhe Li, Qihang Lin, and Yi Yang. A unified analysis of stochastic momentum methods for deep learning. International Joint Conference on Artificial Intelligence, pp. 2955- 2961, 2018.
11

---

Under review as a conference paper at ICLR 2021
Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3):1835- 1854, 2016.
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. In Advances in Neural Information Processing Systems, pp. 9793- 9803, 2018.
Fangyu Zou and Li Shen. On the convergence of weighted adagrad with momentum for training deep neural networks. arXiv preprint 1808. 03408, 2018.
12

---

Under review as a conference paper at ICLR 2021
A PROOF OF AUXILIARY LEMMAS
Lemma 1, For the sequence defined in (10), we have
31
N
9t.i
Z+t1 Zz = 0:
14 O
a
31
N
N
Proof: By update rule of Algorithm 2, we first have
N
X
2411,
N
Mass
1440.5,1
a
N
v U4,5
N
N
Σ
W
Wis
- a m4,s
N
①
Ma,i
N
Jzd
N
v Uuzi
N
mai
X
a
N
1=1
where (i) is due an interchange of summation and Σi=1 Wij = 1. Then, we have
81
31
Ze+1 Zz = -x
Xx +
(X 1+1
x,)
(x+1 X,,)
1
B1
(X++1 - X2))
(X+41
X₂)
1 B1
1
31
N
B1
N
m
1
Bi
N
1 B1
N
1
1=1
i=1
1
31 1,1 + (1 -1- -1=1)g
31
mi-
B1
N
Vilii
1
B1
v Ut=
t=1
1=1
N
81
1
1
gt.s
mi-1.
@
3
Vut
which is the desired result.
Lemma A.1. Given set of numbers "1, , On and denote their mean to be à 1. Ei as Define
(r(r) f= max(a;, r) and b(r) = E br(r). For any r and r' with r' we have
a
Σ (b((r) - b(r)) > 1=1
(b,(r") b(r')1
(8)
and when r S minieen]] ai we have
(b((r) - -(() = Σ
las a.
(9)
1=1
Proof:
Without loss of generality, assume a; S aj when < < i.e. is non-decreasing sequence. Define
h(r) = Σ (r(rr b(rr) =
max(a; r)
1
max(a;, r)
n 1=1
13

---

Under review as a conference paper at ICLR 2021
We need to prove that h is non-increasing function of First, it is easy that h is a continuous function of r with non-differentiable points r = a, E [n], thus is a piece-wise linear function.
Next, will prove that h(r) is non non-increasing in each piece. Define ((r) to be the largest index with a(((r)) < r, and s(r) to be the largest index with @x(r) < b(r). Note that we have for i & ((r). b; (r) = r and for S s() bz(r) b(r) z 0 since is non-decreasing sequence. Therefore, we have
1(r) Σ (b(r) - r)
((r)
h(r)
(6(r) a.) +
Σ - (ar) (=(
1=1
[x)+++11
and
b(r) 1 n 1(r)r Σ ai
i=((r)+1
Taking derivative of the above form, we know the derivative of l(rr at differentiable points is
(r) =((r( ((r) 1) + (s(r) ((r)) ((T) (n s(r))
(n-)()))- ((r)
1(r) ((((r) m) (s(r) - 1(r)) (n -o(r)))))
Since we have s(r) S we know (I(r) n) + (s(r) - ((r)) (n s(r)) < 0 and thus (r) 00,
which means h(r) is non-increasing in each piece. Combining with the fact that lo(r) is continuous. (8) is proven. When < a(i), we have b(i) = max(a;, r) = r, for all E [n]] and b(r) Di= ag which proves (9).
B PROOF OF THEOREM 2
To prove convergence of the algorithm, we first define an auxiliary sequence
B1
Z, Xx
Xx
X
(10)
1-31 31
with No A X,. Since E[gral
V (x(,)) and ues is a function of GI (which denotes
G1, G2, Gr-1), we have
9t.i
1
Vi((as)
EG Graa-
N
N
Uū,i
1=1
Assuming smoothness (A1) we have
L Zell
f(Ze+1) + + Zz)
7
2
Using Lemma into the above inequality and take expectation over G3 given G1--11 we have
EG./GH ([((Z+)))
<f(2)) - VS(22), vil(ar))
+
Ec,
[1 - Zg 12]
Vuls
2
1=1
( Vrrzz))
N
+ 1- B1
B1
1
Σ
m4-1, 3
N
14-1,1
Vuei
i=1
14

---

Under review as a conference paper at ICLR 2021
Then take expectation over G1:-1 and rearrange, we have
N
}
o.E
V (z()),
(11)
N
Vu,i
<B]](Z+))
(((()++))]
L
R [[] Zell²]
2
(V/(2))
N
31 E
+ a - B1
m1-1, 1,5 O
Vues
(12)
M4--1
1=1
In addition, we have
1 VS(Z,),
Vi((a))
N
Vusz
V((I)),
1
Vf((aa))
VFZZ))
NZ Σ
N
vi(ra) 0
(13)
VU,
Vuei
vU.)
and the first term on RHS of the equality can be lower bounded as
1
Va(
V((2.)
VU,
1
Vf(Z,)
EM v)((s)))
1
Vf(Z))
N E (.(
1
+
N
2
T./4
2
U./4
2
v)(X,)
1
v)(X,))
)
V.((z)) ΣM V.f((aa.))
4
T./4
4
2
J!/4
2
N Vf((z))) v((x,) 2
1
Vf(Z))
xX(,,)
2
J!/4
2
2
2
1
v((x,)
3
Vf(Z,
3
Li=l
Vf((I))) vf(x,)
(14)
2
T./4
2
2
T!/1
where the inequalities are all due to Cauchy-Schwarte Substituting (14) and (13) into (11), we get
V)(X,)
aE
<E]((Z)] - E[ 1) +
E
|1|--11 - Zrll
2
U//4
2
+
B1 E
(((z))
1
Σ
3
1
N
1
V((2)) 1
aE
Vi((Ie)))
Vuni
VU.
3
1 EN Vf(()))) - VV(X))
- -V(X))
+ o
N
T//4
15

---

Under review as a conference paper at ICLR 2021
Then over the above inequality from t to T and divide both sides by Ta/2, we have
T
U.A4
T
2
(Z1)( B[f(Zr+1)])
E
[1 I+41 - Z+ll²]
Ta
Ta 1=1
2
3
Σ
T
R
V.((Z))
1x
T1
31
N
14-1,
1=1
(15)
N o
2
E
(Zi)
(i(
T t=1
N
VU,
Vuei
1=1
D2
3
T
N
Li=1
N
Vf((s)))) V)(X,)
- -
+
T
J./1
J.A1
1=1
Now we need to upper bound all the terms on RHS the above inequality to get the convergence rate. For the terms composing D3 in (15), we can upper bound them by
f(,,) vX())
- -
T.
minjeld UU,
1
Zz 1z- X.I
(16)
minjeld U 1/2
14
and
Vf((o,)) Vx(X,,
N
U!/4
min jeld 1T//111 N
1=1
Σ
| -x,l'
(17)
minjela 10, 13
Dr
using Jensen's 's inequality, Lipschitz continuity of ft, and the fact that to bound DA and D5. Recall the update rule of XG, we have
$ Em Ss. Next we need
M = X,W*1 a Σ VU-1
1-2
M W
X, = - a
(18)
1=0 VU-
where we define W Since W a symmetric matrix, we can decompose as W = QAQT where is orthonormal matrix and A is diagonal matrix whose diagonal elements correspond to eigenvalues W in an descending order, i.c. AW = A₁ with X; being ith largest eigenvalue of W. In addition, because W is a doubly stochastic matrix, we know X and q1 eigen- dige-ddecomposition of W, we can rewrite D3 as
1x With
VN
N
| x,|1 Jx, X,1 = 1x,000 I
X
(19)
1=2
16

---

Under review as a conference paper at ICLR 2021
In addition, we can rewrite (18)
X = x
2-2
M, M k-1 Wh = X1 - a Σ Mi
t-2
QA*0"
(20)
Ui-k-1
VU-k-1
k=0
where the last equality is because 31,1 = 3i for all i and thus X,W X1. I >>1 1,
Then we have when
1-2 Mi-k-1 Q1=0"\*=0=== aa Σ X (X1 a
1-2
M qi
(21)
VUi-k-1
VU
k=
k=
since Q is orthonormal and Xıạ = 1 1/ 1 IV = 0. for all 1 1 1.
Combining (19) and (21), we have
D3-
T1,1
Xell²
Σ
| 1
Σ
a²
Mi-k Xa
(22)
Ui-
1=2
K=U
S
a
NdG
where the last inequality follows from the fact that gr S Goos us turn to D4, it can be rewritten as
||æi|| = 1, and Aul
S X < 1. Now let
1 - x, x
B1 B1 (X,- - x,_1)
31
2
1
N
M
=
a
B1
N
U4
1,
i=1
31
2
G2
O
2
(23)
B1
Now we know both D4 and D3 are in the order of ( and thus D3 is in the order of O(a²). Next we will bound D2 and D₁- Define G1 - max max4e[N] (Ir:)
G2 A max.e(r] [Z)ill,, G3 A max max lloc, and G = max G2, Gz).
Then we have
T
N
1 Vi(()))
D2
V
f(Z))
N
VU,
Up.i
1=1
T
N
d
E
G2
1=1
20
N
i=1
j=1
V [
T
N ΣΣ
d
v [Uel + v Vluul
1 N
G2
Σ
8
V UT,,
((Uel, Munsl
(24)
i=1
1
Uel Tueesls
E
G2
N
U 1) / [ur.sli + U 1l..u
121
<E
T
1
Σ
N
U+]y - [un.als
N
2.5
t=1 j=1
Do
17

---

Under review as a conference paper at ICLR 2021
where the last inequality is due to [u,,iyy 2 c, for all t, i.j. To simplify notations, define ||Allabe Eng |Atyl to be the entry-wise L1 norm of a matrix A, then we obtain
Dg
U,1 - UVlllabe
U01T - Uellabs
N
2.
N
2e1.5
t=1
G
1
|U IN1 U,QQ 1lbs
N
2e1.5
G2
T
1
Σ oeqqa Ilabe
N
2
where the second inequality is due to Lemma A.1, introduced Section A, and the fact that Ue max(U,, c) celement-wise max operator). Recall from update rule of Us, by defining V-, & Vo and
Uo & U1/2. we have for all 2 0, U4+1 (U: V2-1 V.)W. Thus, we obtain
1
ÜW + (-V--i + Vz++) = Uo Σ
+
Then we further obtain when 1 + 1,
Uaq - (Üo + -
Σ P7-1- + V)=
k=1
where the last equality is due to the definition Uo U1/2 = cla = VNelall (recall that Q1 / 1 and uf qj 0 when i # j. Note that by definition of || llabar we have for all
A, B, |A + Bllads S ||Allabe + BBbl then
2
T
N
Do S
Σ
N
2c
G2
T
N 1I- + V._x) k) Σ
Σ
ai of llabs
N
1c5
1=1
k=1
1=2
T
ai o
TTila
N
2
[=]
T
80
N
1=1
k=1
1=2
(25)
G2
T
1
d
Σ
ΣΣ
||
N
255
[=1
k=1j=1
G2
T
Σ
[1-- + Vo
N
2.1.5
k=
G2
T-1
Σ
||( ((-vo-1 + Vo) VNN-0
N
1
o=0 t=
G
1
T-1
X
Σ
11--1l(-vo + Vo)llabs:
VN
25
where x = max( |Awl). Combining (24) and (25), we have
G2
T
D2 <
E
Σ
||(- (-- + Volllabs
2
1.5
1
18

---

Under review as a conference paper at ICLR 2021
Now need to bound D1, we have
D1
E
f(Ze);
1, @
E
G
Viuniss
Vuessl + v [1l= v Lueoo + v 1,,]
Σ
E
C
(26)
R
G
1. (1u- [ueel
1
N
1= j=1
(4)
T
N
E
G
1( - [
N
2.5.5
1=1
Km j=1
1
E
11ū-1 - Ü, llabs
2
15
N
1=1
where (a) is due Lيg max((ue-1,ll) e) and the function max(-.c) 1-Lipschitz. In addition, by update rule of Ud, we have
10-1 Üzllata
Σ 1Ū--1 - -Ü0-11 V--2+ W
Σ | - QQQQ") + (-Vv-2 + Ve-1)
1 Σ a(1 + + Wlllass
N V Σ
T
Mit (1 Xx)gFFl llabs Σ ((-V-22 Vi-1)
(27)
T +
Σ 11(- + V
t=1
Vo-2 + Vo-
+
Σ
|[-- ([-v-2 + Vi-1)llabe
t=1
(1 (11 Vo-2+ Vo-
Σ
|[ (-- + Ve-1)llabs
T
A (1l (11 Vo- + Vo- VN
+
Σ
11(-V-2 + V1-1)llabe
1=1
T
1
[1(-i-2 + +Viniillaa
19

---

Under review as a conference paper at ICLR 2021
Combining (26) and (27), we have
T
D1 S G
R
1
Σ
[(-V2-2+
Ve-1)llobo
(28)
2c1.5
1
What remains is to bound Σ/=1 E
[|
Zell3.. By update rule of Ze, we have
1++1 - 2
N
a
14-15 O
a
31
111-1,
Ut
1=1
(=1
1 N
<2a
B1
my
④
+ 2nx
gr.
1- 31
Uu,
22a²
B1
2
G
2aa
1
gt.
I- 31
Vc
V (Mt-
Ut
j=1
22a²
B1
2
N
1
[ur,s] [u 1,b
+ 2a
N
gt.s
1 31
N
Ve
2e1.5
N
Ut
1=1
j=1
i=1
<2a²
B1
[ū,,i]] [ū, 1,,5 + 2a
1
Jt.i
1- 31
N
2
N
Ut.5
i=1 j=1
2
=2a
81
2
G2
1
Iú,
Út-1llads + 2a²
1
ft.s
(29)
1-
31
N
2
Ut.
where the last inequality is again due to the definition that [0r = max( (axx((u c) and the fact that max(;, t) is I-Lipschitz. Then, we have
T
B|ll Ze+1 - 1
<2a²
B1
2
T
110 - U.-1llabe
+ +2a
T
N
ft.b
1-
31
00
N 2
N
U
t=1
<a²
B1
2
G2
Σ
11- V/-1)llabs
+
2a
T
E
1
Ft.i
1-31
31
VN
2
1
N
Ut
where the last inequality is due (27).
We now bound the last term on RHS of the above inequality. trivial bound can
N
T
1 0c
dG
due to ||gr,ll S Goz. and [u.aly 2 e, for all j (verified from update rule of u,,; and the assumption that [Vr,s]j e, for all i). However, the above bound is independent of N, get better bound,
20

---

Under review as a conference paper at ICLR 2021
need a more involved analysis to show its dependency N. To do this, first notice that
gt
BG. G1:-11
N
1
fi(a,)) Eea (((()))) + Eesi
=EG Gmi-1
N
Vues
Vue.
1
(z(
1
Ees
11
BG. G
EG.GGat
N
Vue
N2
We,
(8)
1
N
Vi((a))
N
Ea.
+
N
Vüri
N2
i=
1=1
fi((a))
d d
+
N
Vüri
N NEW
where (a) is due to G [6,,]] and Éx, is independent of Ft. u, for all j. and Ej. for all j * i, (b) comes from the fact that Tr,s ue are fixed given G1a, (c) is due to BG, [( - o² and (u 2 by definition. Then we have
f
E
BGIGG.
Uf
N
Utii
1
Vi((aa))
d d N E
< EGG
N
Vuni
N
d d Nee
E
(30)
N
In traditional analysis of SGD-like distributed algorithms, the term corresponding to falees) will be merged with the first order descent when the stepsize is cho-
sen be small enough. However, our case, the term cannot be merged because it different from the first order descent in our algorithm. A brute-force upper bound is possible but this will lead to worse convergence rate in terms of N. Thus, we need more detailed analysis for the term in following.
(((E))))
E
N
ū
1
Vi(aa)))
1
1
-B
N
VU.
Vun,
U.
(l(())))
1
<2E
+ +
N
VU.
N
Vuhs
VU,
1=1
1=1
N
V((EE))
1 N
1
<2E
+ 2
V
N
VU,
N
Vua,
VT,
1=
21

---

Under review as a conference paper at ICLR 2021
N
vilaaa))
+
2E
G
VU,
Vi
Vut,i
Ut
Summing over T, we have
1
V((
Vuti
(
1
E
+
E
G
(31)
VU.
N
Vuri
U.
For the last term on RHS of (31), we can bound it similarly as what we did for D2 from (24) to (25), which yields
T
N
T
N
1
1
E
G
S
E
|u.s - -Ull
N
0z
Ve
Vue
VU,
N
VE
2e555
1=1
t=1
1=1 1
1
E
U,11
Uillaba
N
26
N Σ
1
Σ
E
G2
Ü.qqt laabs
N
00
2c
t=1
1=2
T-1
1
E
|1- vo- + Vable
2
Lo=0
(32)
Further, we have
N
Vi(aa))
E
VU.
1
1
f((i))
+ 2
E
N
VU.
VU,
1 N
Vf((X))
-2
ΣB 1=1
E
+
E
VT.
and the last term on RHS of the above inequality can be bounded following similar procedures from (17) to (22), as what we did for Dz. Completing the procedures yields
N (X,, v(((E)))
N
D1,1 - X.1
E
N
VU.
E
N
1=1
1=1
1
(33)
E
I
NdC2
1-X
20
1=1
1
=TI
dG2
i-x
22

---

Under review as a conference paper at ICLR 2021
Finally, combining (30) to (33), we get
T
E
N
9
T
E
X
+ 4TL
2
2
1
do2
N
VU.
1-X
1=1
1=1
A
+ T d 0²
+2
E
|| ||(- Vo- + Volllabs
2c
x
N
T
V
(1)
<
E
+ 4TT 2a²
(1 dG2
VC
U
1/4
-=1
A
+ TT d o²
2
E
1K-
2
Ne
where the last inequality is due to each element of U, is lower bounded by e by definition. Combining all above, we obtain
1
x
T t=1
2
(B[F(Z1)]
- B[f(ZT+1))
Ta
L
11
2 Go 00
+
EM4
T
1
1-
31
VN 2 1 1-- X
8L T Q E
1
T
(X,),
1
ΣE
+ +8L2 aaa
1- dG
(34)
VE 1
t=1
4L
1
A
d o²
G
E
Vo- + 1o)
+
2La
T VN
22
N
Lo=0
2 31
1
1
G2
E
VT
T
31
2
2 G
X
E
[Vr]
T V 2c
X
3
Σ
T
1
2
dG2
Σ
L
81
2
a²
dd
G2
T
21.
11-
31
L.5
2
(B[[(Z1) - B[f(Z++1)) + 22La d²
1 1
(((),) +)
+8La
E
To
N
VET
T:!/
1=1
+ 3a²d
(114)
31
2
+
L
Go
Go 2
31
cl.
1 1-
1 G2
1
B1
2
1
B
La
+x+
+ 2La
x
E EVrl--
Tel.5 VN 1
1
31
0.5
1-
81
e..
where Vr : Et -
||( 11(-//-2 +
Set
I
and when a
<
16r we further have
.05
veT
T
v)(X,)
27
E
T t=1
T./4
(B[f(z)) - + 4La d o² N e
<
Ta
23

---

Under review as a conference paper at ICLR 2021
(11-)
$1
2
1
2
G2
G2
+ 6o?d
+
I.
+ 1,a
B1
1
cl.5
1 x
2
G
1
B1
2 1
B1
_
1
+ TeL.
La
+ A +
+ 2La
d
E B
VN
1 A
I-
31
0.
1-B
e0.5
d d²
(B[](Z))
-min f(x) + +4aa
Ta
x
N E
11
2
G2
1
G ?
+ 6002
1 B1
+
1 1- X
L x
c1.5
+ 160 dT?
1-X
2
G
1
31
2
B
1
+ Tel5
VN
1 -
La
1 - 31
0..
+ A +
1-
+La
c0.5
E [r]]
1
do
<C
- min (x)) + a
+ +Caad
Cga
(C4 + Cga)
Ta
N
TVN
(35)
where the first inequality is obtained by moving the term SLa 1 1
vt T Et=
E
on the
RHS of (34) to the LHS to cancel it using the assumption 8La v S 2 followed by multiplying both sides by 2. The constants introduced in the last step defined as following
C mam.aa14..... 44/)
B1
G2 L 8 1
2
C2 66
1 B1
+
1-
2
1.
G
C. 16L
1- X
2
2
1
B1
C
x+
22
1.5
1-X
1-
3
2
X
C
L
L.
11
1
31
2
1
x
Substituting into Zi X, completes the proof.
C PROOF OF THEOREM 3
Under some assumptions stated in Corollary 2.1, we have that
VS(X,)
vd VTN
N
N1.
E
<C
(EL]((Z))]
min f(o))) + 02)
+ +C² + Cs T1.yu.s
U!!
T
+ C T + Co To.
E
Σ
||[- (1- + 1i-1)llabs +
(36)
where || llabs denotes the entry-wise L1 norm of a matrix (i.e ||Allabs
= Ei, (Ay)) and
Ci, C2, Ca, C4, Cs are defined in Theorem 2.
Since Algorithm 3 is a special case of 2, building on result of Theorem 2, we just need to characterize
the growth speed of E En [1(-Vr- Vr- + 1 to prove convergence of Algorithm 3. By the
24

---

Under review as a conference paper at ICLR 2021
update rule of Algorithm know V3 is non decreasing and thus
E
|I [ V + llabss
=E
10 1 [
=E
08 2,12 + [8 [0o-
:=
=E
10-1: + 1,1-
N d
=E
( oo, + [ŌT-
where the last equality is because we defined V_ - Vo previously.
Further, because =l s Go for all t, and U is exponential moving average of g 2, t, we know [[ve,elal S G for all t, j. In addition, by update rule of V2, we also know each element of Vi2 also cannot be greater than G i... |60t, S G for all t, i,j. Given the fact that [ño,a]i 2 0, we have
N
N d
E
11-v/-2 P allbos
=E
E
- [00,]] + (
SE
G
NdG
i=1 j=l
Substituting the above into (39), we have
v((x,)
vd
N
N1.5
E
<CI
(B[f(Z)))-m) min f(x)) minn +02) f())++ +O2T + +3 c3....00
U!!!!
1/4
VTN
C1 TVN
1
+ Os TI..,003
1
NdC
N VTN (IB[((Z)) - min f(x)) (())) +C + C qu.
Vd
N
C
Nd
05
C T
C/
T
(37)
where we have
=1
C22 C2
C33 C3
C2 C C= C.
(38)
and we conclude the proof.
D PROOF OF THEOREM 4
The proof follows the same flow as that of Theorem 3. Under assumptions stated Corollary 2.1, set a /N/ W/dTd, we have that
T
v((),)
<C1
Vd VTN
(IE[((Z))
- min f(x)) + +02) [(x))
N + +C2 + Ca T1.6.0.3
N1.5
U./4
1
+
((TTVV
+
Os 1..
E
[[ [[- [-vv + V(-1)llebs
(39)
25

---

Under review as a conference paper at ICLR 2021
where || llabs denotes the entry-wise L1 norm of a matrix (i.e || = Eis (igh and C1 C2, C3 C4, Cs are defined in Theorem 2.
Again, Since decentralized AdaGrad a special case of 2, we can apply Corollary 2.1 and what we need is upper bound E of decentralized AdaGrad, we have 02,5 = ? EE R. for t 2 1 and 0p = cl. Then we have for
Σ II(- V2- + Vaai) derive convergence rate. By the update rule
t t23 3,
E
Σ |[ 1(-V--2+ Vlli)s
N
-B
2 + 1sl
N
1-2
<E
gh. 1)) +
+ Ndd( -c)
2
t 1
k=
k=1
N
1-2
Σ
F .),)) +
l
+ +NdG2
t 1
k=1
T
N
d
1-2
1
1
-E
)(
Fh
19 1,1b
NdG x
(t - 1)( - 2)
t - 1
k=
N
d
2-2
1
<B
max
- 10ا
+ +N
(1- (1-1)(1 - 2)
k=1
T
G%
<
Nd
+ +
t-1 3
<NdG. log(T) + NdG2
=NdG (log 1)
where the first equality is because we defined V_ & Vo previously and ||g,,lloc S Goo by assump- tion.
Substituting the above into (39), we have
x
Va VTN (IE(((2)) - min f(x)) + +02) [xx))+0²)
+ +02 N + C3
N15
<01
UP//4
m..
Ca
1
+ Cs (
1
1)
TVN
Vd
+ C/2 N
N1.5
C
(E[f(Z))) - min f(x)) + 0²)
-22 T
+ C/ .1.5
VTN
dv N(lo((T) + +1) C5 (log(T) ( 11NNv
T
where we have
G = C2
C2 C2
C Cs C = C₂ C==oa'.
(40)
and we conclude the proof.
26

---

Under review as a conference paper at ICLR 2021
E ADDITIONAL EXPERIMENTS AND DETAILS
In this section, we compare the training loss and testing accuracy of different algorithms, namely Decentralized Stochastic Gradient Descent (DGD), Decentralized Adam (DADAM) and our proposed Decentralized AMSGrad, with different stepsizes on heterogeneous data distribution. We use nodes and the heterogeneous data distribution created by assigning each node with data of only two labels. Note that there are no overlapping labels between different nodes, For all algorithms, we compare stepsizes in the grid [10
10 10 ".
Figure shows the training loss and test accuracy for DGD algorithm. We observe that the stepsize 10-3 works best for DGD in terms test accuracy and 10-1 works best in terms of training loss. This difference is caused by the inconsistency among the value of parameters on different nodes when the stepsize is large. The training loss calculated as the average the loss value of different local models evaluated their local training batch. Thus, while the training loss is small at particular node, the test accuracy will low when evaluating data with labels not seen by the node (recall that each node contains data with different labels since
in the heterogeneous setting).
Figure shows the performance of decentralized AMSGrad with different stepsizes. We see that its best performance is better than the one of DGD and the performance is more stable (the test. performance less sensitive to stepsize tuning).
Figure 4 displays the performance of Decentralized Adam algorithm. As expected, the performance of DADAM is not as good as DGD or decentralized AMSGrad. Its divergence characteristic, highlighted Section 2.3, coupled with the heterogeneity in the data amplify its non-convergence issue in experiments. From the experiments above, we can see the advantages of decentralized AMSGrad in terms of both performance and ease of parameter tuning, and the importance of ensuring the theoretical convergence of any newly proposed methods in the presented setting.
27

---

Under review as a conference paper at ICLR 2021
0.5
0.4
0.3
0.2
0.1
(a) Training loss
(b) Test accuracy
Figure 2: Performance comparison of different stepsizes for DGD
0.8
164
2:00
3.44
X10
-10
(a) Training loss
(b) Test accuracy
Figure Performance comparison different stepsizes for decentralized AMSGrad
07
07
(a) Training loss
(b) Test accuracy
Figure 4; Performance comparison of different stepsizes for DADAM
28


Reviews:
[{"review_id": "v9ur0b0S9q-", "reviewer": "AnonReviewer3", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors attempt to use adaptive gradient methods in decentralized training paradigm. They develop a general framework to convert an adaptive gradient method from a centralized one to its decentralized variant. Specifically, they propose a decentralized AMSGrad algorithm. They also point out a potential divergent problem of an existing method and investigate the conditions to ensure convergence. Finally, they conduct some experiments to verify the performance of their algorithm.\n\nPros:\n1. This paper is the first one to use adaptive gradient method to decentralized training paradigm and the authors also provide a completed convergence analysis for their algorithm.\n2. This paper reveals a divergent problem of DADAM in offline situation by taking some intuitive examples. Based on this issue, they find a solution that makes consensus on the adaptive learning rates.\n3. This paper proposes a general framework to apply adaptive gradient methods to decentralized optimization. The authors also investigate the conditions to make sure these decentralized variants will converge.\n\nCons:\n1. In section 3.2, the paper claims AdaGrad and AMSGrad satisfy the condition to guarantee the convergence of Algorithm 2 while Adam does not. It seems not to be an obvious conclusion from the reference Chen et al. (2019). Is there more explanation or proof about why AdaGrad and AMSGrad satisfy the condition? And does it mean Adam still diverges even after using the algorithmic approach proposed in this paper?\n2. In Theorem 2, the convergence analysis result of Algorithm 2 is given. However, the convergence of common adaptive gradient methods such as AdaGrad and Adam is still not clear. Therefore, the “convergent adaptive gradient method” in the title is very misleading. Do most of the adaptive gradient methods have the same theoretical guarantees as AMSGrad?\n3. \\mathbb{E}[\\sum_{t=1}^T \\lVert (-\\hat{V}_{t-2} + \\hat{V}_{t-1}) \\rVert_{abs}] = o(T) is the key condition to ensure the convergence. But when the above equation is O(\\sqrt{T}), the convergence rate is worse than the centralized counterpart. Is that case possible?\n4. In section 3.4, the experiment is divided into homogeneous and heterogeneous data, which is very confusing. What is the reason for doing this and what will happen if we just deal with the dataset normally? The heterogeneous data is treated very intentionally. Is there any discussion about when the treatment of heterogeneous data is important?\n5. In the homogeneous data experiment, the performance of DADAM and decentralized AMSGrad are similar. What is the reason that the learning rates on different node tend to be similar? Is that a common case? Maybe the experiment on more dataset is needed to address this concern. Besides, how will such similarity among data impact the theoretical convergence?\n\nMinors:\nThe algorithm proposed in Lian et al. (2017) is called Decentralized Parallel Stochastic Gradient Descent (D-PSGD).\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "nid7RhHNq1I", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThis paper studied the decentralized adaptive gradient methods and provided convergence guarantees. Experiment on MNIST is conducted to show the effectiveness of the proposed approach.\n\n1. The theoretical result is weak. The linear speedup result is not proved as in (Lian et al. 2017), the benefits of adaptive gradient methods are also not illustrated in the bound in Theorem 2 and Theorem 3.\n\n2. The learning rate scheme is not practical and does not hold in practice. As illustrated in Theorem 2 and 3, the learning rate $\\alpha$ is set to be less than $\\epsilon^{0.5}/16L$. \n\n3. The LHS of Theorem 2 and Theorem 3 are not the standard gradient squared norm but the scaled version. It is unclear what is the bound if the LHS is the standard gradient squared norm as in (Lian et al. 2017). It is important to use the same measure as in the previous literature for fair comparison.\n\n3. The experiment is weak. Doing distributed training only on a tiny dataset on MNIST is not sufficient. I would like to see results on larger datasets such as CIFAR and ImageNet.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Tc_4hwIna-9", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper discusses the problem of adaptive acceleration in the decentralized setting. The premise is that decentralized versions, while successful in the simple SGD setting, do not extend well in the acceleration settings, e.g. Adam and Adagrad. They first present a counterexample where a simple decentralized scheme, applying Adam, converges to a nonstationary point.  (Suggestion: I would maybe add a cleaner, more flushed out version of this proof in the appendix, maybe with illustrations.) \n\nOverall, everything the paper presented seemed reasonable. The motivation and counterexample in DADAM case are solid, and the following theorems seem to suggest gradient error norm $\\to 0$ at rate $O(1/\\sqrt{T})$ which is reasonable in nonconvex optimization.  The intuition in the adjusted merging scheme is also reasonable, and makes sense that it would work better than vanilla merging schemes. However, I did not have a chance to carefully check the proofs, which are clearly the main contribution of the paper. \n\nOne thing I would suggest is a more thorough set of numerical experiments. The two examples shown, in fact all the methods converge, and while the proposed method converges faster, it isn't really verifying the paper's main point, which is that the standard distributed methods diverge and the proposed method converges. Showing this on a standard machine learning task would improve motivation.", "extra_scores": {}, "extra_text": {}}, {"review_id": "6Qe46iGaYy4", "reviewer": "AnonReviewer4", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper introduces a decentralized framework for adaptive momentum-based gradient descent optimizers, such as ADAM. The proposed method is novel and is among the first works to consider a decentralized communication graph without a master node. The author discovers the divergent properties of the recent work of DADAM (Nazari, 2019) and proposes a way to fix it by adding a similar consensus step for the adaptive learning rates of agents. The mathematical derivation seems to be correct to the best of my knowledge. Finally, the author tests their method on a simple CNN and show their superiority compared to DADAM to achieve a close to the centralized performance.\n\nHowever, I have some minor comments to improve the manuscript.\n1. The experimental evaluation of the work is quite limited. I understand the space limit but it would have been nice to see more experiments instead of showcasing Algorithm 2 with an extra example in Algorithm 3. It is important to see the convergence behavior of the method (on the training data) with respect to the DGD on various datasets/networks in practice, rather than observing how the testing accuracy behaves. Note that your method does not guarantee any specific generalization behavior and therefore I believe it is more suited to report the experiments only in terms of training performance when you are out of space.\n\n2. What are the drawbacks of this method? I can see more memory requirements for the agents due to the new variable \\tilde{u} for instance. Do you have any quantified evaluation in this respect? I suspect it can be significant especially if the trained model is large and the agents have limited memory/computational resources\n\n3. In Section 3.2, the author says \"Algorithm 2 can become different adaptive gradient methods by specifying r_t as different functions. E.g., when we choose ..., Algorithm 2 becomes a decentralized version of AdaGrad.\" This sentence is not accurate as algorithms like AdaGrad and Adadelta do not use momentum on the past gradients. They only use the squared values of the past gradients. I believe your method, as I mentioned above, is a general framework for momentum-based techniques including ADAM, AdaMax, NADAM, etc, which brings me to the next question.\n\n4. Is it possible to generalized your method for an adaptive gradient descent algorithm that does not use the momentum of the gradients? For example, take AdaGrad with a fixed learning rate of \\eta instead of m_t. How does your convergence behavior change? ", "extra_scores": {}, "extra_text": {}}, {"review_id": "4UWvZ77pRy", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper consider the decentralized adaptive algorithms. At the first glance,  I am really happy to that the adaptive methods are used for the decentralized optimization. However,  after I read the  main document, I do not think  paper actually    analyzes the decentralized adaptive algorithms.\n\nIn line 9 of Algorithm 1, the   denominator is $\\sqrt{\\hat{v}_{t,i}}$.\n\n However, in Algorithms 2 and 3, it is changed as $\\sqrt{u_{t,i}}$. In  the proofs, the authors proved the convergence based on $u_{t,i}\\geq \\epsilon$. This is actually the DSGD. The proofs can be quite simple.  And the restriction $\\alpha=O(\\sqrt{\\epsilon})$ can be easily removed.\nThis paper does not present any insights for the decentralized  adaptive methods. It only depends on $u_{t,i}\\geq \\epsilon$. The numerical results show that the proposed method is similar as DSGD. As mentioned before, it is actually DSGD but with slightly modification.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers have some following concerns: 

1) There is lack of experimental result. The experiment on MNIST with small CNN architecture is definitely not sufficient to verify the efficiency of the proposed method. Moreover, the advantage of the proposed method is not very clear due to the choices of the parameters. The choice of the learning rates is quite sensitive. 

2) It is not clear why the authors could argue that $ \mathbb{E}(V_T) = \mathcal{O}(T)$ without any theoretical and empirical support. Even if this is correct, this term could dominate the first term unless $ \mathbb{E}(V_T) \leq \mathcal{O}(\sqrt{T})$, which is too strong. If assuming $\mathbb{E}(V_T) = \mathcal{O}(T)$, the convergence results are upper bounded by some constant (note that $\epsilon$ is a constant in this scenario, not arbitrarily small). Hence, the authors failed to show the convergence to a stationary point. 

There are some suggestions to improve the paper as follows: 

1) Show $\mathbb{E}(V_T) = \mathcal{O}(T)$ and revise the theory properly to make it rigorously by showing upper bounded by some function $R(T) \to 0, T \to \infty$ rather than showing the convergence to some fixed neighborhood. (Note that $\frac{C_4}{\sqrt{N}}$ is a fixed constant). 

2) Do more experiments on various datasets and network architectures to verify the efficiency of the proposed method and show the clear advantages compared to others. 

3) Provide convergence rate comparisons with other decentralized algorithms (e.g., as a table). It would be nice if the authors also provide the assumptions and the dependent constants so that the readers could really see the differences. 

4) Explicitly derive the convergence measure based on the standard one, that is, $\frac{1}{T} \sum_{t=1}^{T} \mathbb{E} [ \| \nabla  f (  X_t )  \|^2 ] $ and add the dependency of $G_{\infty}^2$ to the bound. 

5) Revise the paper and implement all necessary comments from the reviewers consistently with the content. 

Decision: Reject