Communicate Then Adapt: An Effective Decentralized Adaptive Method for Deep Training
Authors: Bicheng Ying
Kun Yuan
Yiming Chen
Hanbin Hu
Yingya Zhang
Pan Pan
Wotao Yin
Venue: ICLR 2022 Submitted (2022)

Abstract: Decentralized adaptive gradient methods, in which each node averages only with its neighbors, are critical to save communication and wall-clock training time in deep learning tasks. While different in concrete recursions, existing decentralized adaptive methods share the same algorithm structure: each node scales its gradient with information of the past squared gradients (which is referred to as the adaptive step) before or while it communicates with neighbors. In this paper, we identify the limitation of such adapt-then/while-communicate structure: it will make the developed algorithms highly sensitive to heterogeneous data distributions, and hence deviate their limiting points from the stationary solution. To overcome this limitation, we propose an effective decentralized adaptive method with a communicate-then-adapt structure, in which each node conducts the adaptive step after finishing the neighborhood communications. The new method is theoretically guaranteed to approach to the stationary solution in the non-convex scenario. Experimental results on a variety of CV/NLP  tasks show that our method has a clear superiority to other existing decentralized adaptive methods.

Under review as a conference paper at ICLR 2022
COMMUNICATE THEN ADAPT: AN EFFECTIVE DECEN- TRALIZED ADAPTIVE METHOD FOR DEEP TRAINING
Anonymous authors Paper under double-blind review
ABSTRACT
Decentralized adaptive gradient methods, in which each node averages only with its neighbors, are critical to save communication and wall-clock training time in deep learning tasks. While different in concrete recursions, existing decentralized adaptive methods share the same algorithm structure: each node scales its gradient with information of the past squared gradients (which is referred to as the adaptive step) before or while it communicates with neighbors. In this paper, we identify structure: it will make the
the limitation of such helep--tenn/hhie--commmr developed algorithms highly sensitive to data heterogeneity, and hence deviate their limiting points from the stationary solution. To overcome this limitation, we propose an effective decentralized adaptive method with communicate- -thnn adapt structure, in which each node conducts the adaptive step after finishing the neighborhood communications. The new method is theoretically guaranteed converge to the stationary solution in the non-convex scenario. Experimental re- sults variety of CV/NLP tasks show that the proposed algorithm has a clear superiority to other existing decentralized adaptive methods.
INTRODUCTION
Decentralized SGD (Lopes & Sayed 2008 Nedic Ozdaglar 2009 Chen & Sayed 2012 Lian
eet al. 2017 Assran et al. 2019) is an emerging training approach for deep learning known for its much less communication overhead. In contrast to parallel SGD in which a global averaging across all computing nodes is required per iteration, decentralized SGD does not involve any global operations. Building upon partial averaging. in which each node only needs to compute the locally averaged model within its neighborhood, decentralized SGD can save remarkable communications and training time in large-scale distributed deep learning tasks compared to parallel SGD.
Although simple to use, the vanilla decentralized SGD sometimes suffers from the slow conver- gence. Inspired by the well-documented success of adaptive methods such as AdaGrad (Duchi) let al. (011aa), la). Adam (Kingma & Ba 2014) and AMSGrad (Reddi et al. 2201)), several decentralized adaptive methods (Nazari et al. 2019 Lin et al., (02T) have been proposed to accelerate decentral- ized SGD training. While these algorithms have achieved remarkable success in several practical applications, they have also been observed to not converge to the desired solution (i.c., global opti- mal solution in the convex scenario or stationary solution in the non-convex scenario) in some other settings. For example, it has been observed in the convex setting (see Sec. B) that DAdam (Nazari al. 2019 and QG-DAdam (Lin et al.) 202T) do not converge to the global optimal solution.
This paper studies this situation in detail. We rigorously uncover the reason why DAdam and QG- DAdam fail to achieve the desired solution, and propose a novel decentralized adaptive method to resolve the convergence issue. In particular, we make the following key contributions:
We find the algorithms DAdam and QG-DAdam, while different in concrete recursions, share a similar structure: each node scales its gradient with the past squared gradients (which is referred to as the adaptive step) before or while it communicates with neighbors. We identify the limitation of such
wwm.mminiileeoommnitttet structure: will make the developed algorithms highly sensitive to data heterogeneity. and hence deviate their limiting points from the desired solution.
To overcome these limitations, we propose a novel communicate thee-hhheeeee then-adapt algorithm structure, in which each node will conduct the adaptive step after all neighborhood communications. It is not just trivially switching the order of communication step and adaptive step. The key compo- nent to guarantee the effectiveness of the communicate-then-ann structure is the utilization of the

---

Under review as a conference paper at ICLR 2022
decentralized augmented gradient (DAG) rather than the standard stochastic gradient in algorithm development. The newly proposed algorithm, which is coined as DAG-Adam, can provably con- verge to the desired solution. While this paper mainly focuses on the vanilla Adam algorithm, the core idea behind DAG-Adam can be easilty extended to AMSGrad or other adaptive methods.
Experimental results variety of computer vision and natural language processing tasks show that DAG-Adam outperforms various existing state-of-the-art decentralized adaptive baselines un- der different network and data configurations. Furthermore, the performance of our proposed algorithm is persistently competitive to the centralized counterpart.
Related work decentralized optimization and deep training. Decentralized optimization was extensively studied in the control and signal processing community. The first decentralized algo- rithms on general optimization problems include decentralized gradient descent (Nedic & Ozdaglar 2009), diffusion (Lopes & Sayed, 2008 Chen & Sayed, 2012 [Sayed| 2014), and dual averaging (Duchi al., 20] After that, various primal-dual algorithms come out to further speed up the convergence, and they are based on alternating direction method of multipliers (Adam) (Shi et al.)
2014), explicit bias-correction (Shi al., 2015 Yuan et al. 2019;
Li et al. 2019), gradient tracking
(Xu et al. 2015; Di Lorenzo & Scutari 2016 Nedic et al.
2017
Qu & Li 2018 Lu et al. 2019)
and dual acceleration (Scaman et al. 2017 Uribe
Uribe et al. 2020).
In deep learning tasks, decentralize SGD, which was established in (Lian et al. 2017) to achieve the same linear speedup as parallel SGD in convergence rate, has attracted a lot of attentions. Many efforts have been made to extend the algorithm to directed topologies (Assran et al., 2019), time-varying topologies (Koloskova et al. 2020). asynchronous settings (Lian et al. 2018), and
data-heterogeneous scenarios (Tang et al. 2018 Xin et al. 2020) Lin et al. 2021 Yuan et al.
2021 With careful consensus control (Kong et al. | 2021) or periodic global averaging (Chen et al,
2021b), decentralize SGD can achieve 1.3 ~ 2x training time speedup without severe performance
(Alistarh et al.] 2017: Bernstein et al. 2018 Koloskova al. 2019a by TTang et al. 2019) Liu et al., 2020), periodic updates (Stich [2019] Koloskova et al.]] [2020] Yu et al. (201)). and lazy communication (Chen et al.] [0188] [iu et al,,
degradation. Techniques such as quantization/comprsstt
2019b) were also integrated into decentralized SGD further reduce communication overheads.
There are also a few studies on accelerated variants of decentralized SGD, and most of them are on (static) momentum acceleration. (Assran et al. 2019 Gao & Huang 2020) propose run local momentum SGD step first before the partial averaging is conducted. Another work (Yu et al. 2019) imposes an additional partial averaging over momentum to increase stability. Recent works (Lin et al. 2021 Yuan et al. 2021) developed strategies that can remove the momentum-incume decentralized momentum SGD. All these methods are not with adaptive strategies to scale gradients.
bias in
Related work on adaptive gradient method. Adaptive gradient methods, with AdaGrad (Duchi jtt al.] 201Ta) and Adam (Kingma & Bal (2144) as two representatives, have shown strong perfor- mance in training deep neural networks. With adaptive adjustment in the gradient direction and automatic tune in the learning rate, adaptive gradient methods can boost the performance of SGD training significantly. In spite of its remarkable empirical success, Adam suffers from a conver- gence issue: it may not converge to the desired solution with a fixed mini- manc-batch size (Reddi et al.) Zaheer et al., 2018). Many algorithms have been proposed to resolve this issue. AMSGrad Reeddi et al.] 2019) preserves the long-term memory of past gradients to improve convergence, and Zaheer al. 20188) suggests the usage of increasing mini-batch sizes in convergence guarantees.
2019
Chen et al. 2018b) has studied the convergence of a family of Adam-type algorithms. (Zhou et al., 2018) provides a better convergence rate for AMSGrad. From the empirical side, RAdam (Liu al. 2019a) and AdamW (Loshchilov & Hutter 2018) can significantly improve Adam performance.
The exploration in decentralized adaptive methods are rather limited. DAdam (aazari et al. 2019)
is the first consensus-base based adaptive methods for distributed optimization to our knowledge. (Lin al., (021) proposes QG-DAdam, which utilizes quasi-global momentum to locally approximates the globally descent direction. A recent work (Chen et al.] (021a) proposes unified framework that incorporates various adaptive methods into decentralized setting. While these methods have shown strong empirical performance in several practical applications, they either suffer from unsta- ble convergence or heavy communications. We leave more discussion on their limitations in Sec. Adaptive gradient methods have also been extended to the federated learning setting in which mul- tiple clients cooperate to learn a model under the supervision of a central server (McMahan et al. 2017). Useful references in this direction can be found in (Xie al. 2019 Reddi et al. 2020).
2

---

Under review as a conference paper at ICLR 2022
2
STRUCTURE AND ITS LIMITATION Problem. Suppose computing nodes cooperate to solve the distributed optimization problem:
! Σ = 72 1=1
n
min ((x 2ER4
(x),,
where [1(x) == DE Et)
In the above problem, ft(x)) local to node i, and random variable & denotes the local data that follows distribution Dj. We do not assume each distribution D; is the same across all nodes.
Network topology and weights. We assume all computing nodes are connected by a network topology. We define Wij, the weight to scale information flowing from node to node as follows:
node j is connected to i, or = > 0
Waj
otherwise.
= (ilung > 0} is defined as the set of neighbors of node i which also includes node i itself and the weight matrix W = [w]r]],j=1 RRax are denoted as a matrix that stacks the weights of all nodes. This matrix W characterizes the sparsity and connectivity of the underlying topology.
Partial averaging. Decentralized methods are based on partial averaging within neighborhood defined by the network topology. With weights {wij} and the set of neighbors Ni. the partial averaging operation of node i can be expressed as
Partial averaging: 1. Σ
Wiyay-
(3)
JEN.
Partial averaging requires much less communication than global averaging on sparse topologies.
Assumptions. We will make the following standard assumptions throughout the paper:
A.1 [SMOOTHNESS] Each fi (x) is L-smooth, i.e., [fi==) - -||-~v|l for any v, E Rdd.
A.2 [GRADIENT NOISE] The random sample <!¹) independent of each other for any h and i. We also assume (z; { = fi(r) and V Ev) [z)) - o².
A.3 [WEIGHT MATRIX] The weight matrix W symmetric and doubly-stochastic, i.e. W1 1 and 1TW = 17, where 1 is an all-ones vector. Further, we assume ||W - 111 12 S p E (0,
A.4 [BOUNDED GRADIENT] The loss function F' has bounded gradient, i.c., the maximum norm I G for all x and E,, and E [r]].
Notation. Given a constant n, we let [n] := (l.......)) Given a vector Rd we let diag(z) diag(=1, ] E Rdxd be diagonal matrix. Given two vectors x E Ie and y E Rd we let y be the element-wise product between z and y.
2.1
THE ADAPT-WHILE WEETTWIIIII-CCMCCCCCCCCCCCCCCCCC COMMUNICATE STRUCTURE AND ITS LIMITATION
Shapt--Wile-Commmmn Structure. Algorithm in Appendix B lists recursions for DAdam
Nazari et al. 2019). The critical step in DAdam, which is highlighted in Algorithm 2 is as follows
adapt
communicate
(C) mm
(t+1)
ViE [n].
(4)
JEN.
+
(1)) is an estimate of V F c. VF( (())), and e is a small where m² is the momentum, 02
positive constant. Their updates can be referred to Algorithm 2 In recursion (4) observed that node in DAdam conducts the adaptive step (i.e., scales the gradient by the square root of exponential moving averages of past squared gradients) while it communicates with neighbors. We call such structure utilized in DAdam adapt-while-ae comliiicomm
Fixed point condition. Now we examine the fixed point achieved by DAdam and verify whether - oo for i E [ra]. To remove the the influence of gradient noise, we assume each node i can access the full- batch gradient V fxr).. we define H, == diag( ( ff(z))))) C f((;;)) to be diagonal matrix associated with node i, the fixed point condition for DAdam is (see derivation in Appendix B.2
it satisfies the optimal condition to problem ( To this end, we let x; (() x;
3

---

Under review as a conference paper at ICLR 2022
Σ
Wizzy 7H1, + Vie [n].
(5)
jEN,
+el - 0 (if
x0 in the limit)
Fixed point in DAdam is deviated from the desired solution. In the dettr-eeteoossneouu scenario where data sample & follows different distribution D., it holds that fa(z) (z). If we further assume (x())) * V (x)) ) it follows that H; * H,. for any i # j. With this fact, we conclude that DAdam fixed point satisfying condition (6) does not necessarily satisfy the optimality condition for problem (1 i.e., A > (z(x²*) = 0. This implies the fixed point of DAdam is not the stationary solution problem ① In particular, the following proposition derives the distance between the DAdam fixed point and global optimal solution to problem IT when the cost function
strongly-conver (Proof is in Appendix B.3
Proposition 1 Under Assumptions A.I, A.3 and A.4, if each f((x) is further assumed to be μJ- strongly-convex and the full-batch gradient f((x) is accessed per iteration, then DAdam (Al- gorithm 2 cannot converge to x², i.e. the global solution to problem 0 In particular, the distance between DAdam limiting point and x² can be characterized follows:
10 - x 11= (
G²
lim
-B²)
p)
where = 14 (H, - -
- (( Ill * a constant bias term. Furthermore, the B term in (7) is necessary and cannot be removed by an improved analysis; there exists strongly convex and smooth functions f:(x) such that lim Σi || 21 -BBB).
observed in Proposition [ that the distance between the DAdam fixed point and the optimal solution cannot diminish to zero as learning rate + 0. Such non-vanishing limiting bias B caused by the adapt-while-communice work (Chen et al.] 2021a) has pointed out that DAdam cannot converge to the stationary solution by constructing a counter-cxample. However, (Chen et al. 2021a] does not clarify the reason why DAdam fails to converge the stationary solution, and how far it can be from the desired solution.
structure in DAdam.
worth noting that recent
2.2 THE ADAPT-THEX--COMMUUNCAE STRUCTURE AND ITS LIMITATION
Adapt- Adapt-Then-Communt Tomm-CCmm Structure. Algorithm in Appendix B lists the recursions for QG- DAdam (Lin et al. 2021). The critical step, which is highlighted in Algorithm 3 is as follows
(t)
(++1) Σ Wij
m
JEN:
It is observed that node i in the above recursion first conducts the adaptive step, and then it commu- nicates with neighbors. We call the structure utilized in QG-DAdam as tilupt-then-commniice
Fixed point condition and limitation. Following the settings and arguments in Sec. 2.1 we can derive the fixed point condition for QG-DAdam as follows (see the derivation in Appendix B.5
20
Σ JEN;
Wiy 2350 7 +2
Vie [n].
(9)
1
Σ
+
(if x:100
2 20 in the limit)
(10)
where 31, B2 E (0, are momentum parameters listed Algorithm 3 Similar to DAdam, the above condition implies that the fixed point of QG-DAdam is also deviated from the stationary solution. In particular, the distance between QG-DAdam fixed point and the global solution x" can be characterized for the strongly-convex scenario as follows (proof is in Appendix B.6):
4

---

Under review as a conference paper at ICLR 2022
Proposition 2 Under the same conditions in Proposition 7 the distance between QG-DAdam fixed point and the global solution x² can be characterized as follows:
G²2
lim
|
- x 11= 0
B²)
(11)
p)
where B :== - Furthermore, the B² term in 7 is necessary and cannot be removed by an improved analysis; there
B,H,+0l VV - vf(xz))) # 0 is constant bias.
exists strongly convex and smooth functions f((x)) such that lim Σ ||x])) -xx 1| (2(
Similar to DAdam, it is observed that the distance between the QG-DAdam fixed point and the optimal solution cannot diminish to zero as learning rate 7 - O.
2.3 GT-DADAM: A DECENTRALIZEE ADAPTIVE METHOD BASED ON GRADIENT TRACKING
is observed from the fixed-point condition c that DAdam cannot converge to the stationary solution due to the discrepancy between H, 's recent work (Chen et al. 2021a proposes gradient tracking based DAdam that enables each local different H, to converge to H Ei=1 H; in theory, and therefore, its limiting fixed point satisfies - V{((=*) O. the optimality condition to problem ( GT-DAdam also utilizes the addap-whill-commmuiiate structure. While it can converge to the stationary solution to problem (I) as learning rate y 0, it incurs twice amount of the communication overhead as DAdam. The distance between GT-DAdam fixed point and the global solution x* can be characterized in Proposition 4 in Appendix B.7 for the strongly-convex scenario. In the convex scenario, the distance between GT-DAdam fixed point and the global solution can be worse than that of the proposed DAG-Adam, see Table 5 in Appendix
C.3 and Fig in Sec.
DECENTRALIZED AUGMENTED GRADIENT ADAM
Now that we understand that the adapt- Shaap--wiieethhnn-oo communicattt structure in decentralized adaptive methods either deviates the limiting point from the desired solution (e.g.. DAdam and QG-DAdam), or incurs more expensive communication overhead (GT-DAdam), this section will propose a new algorithm that overcome the limitation of the adapt- www.w//hen-coomeeteeee
structure.
Decentralized SGD interprets as standard SGD. Without loss of generality, we assume each node i access the accurate gradient (/1(x) in decentralized SGD recursions. In this scenario, decen- tralized SGD, according to (Yuan et al. 2016), can be written as
(++1))
2
(0)
(12)
JEN
(8) n 7 (2) + (x
Σ wiyzs()))
Vi [m].
(13)
JEN:
augmented gradient
In other words, decentralized SGD 12 can be regarded standard SGD recursion
13 to solve
min (a.)2
Σ filas) +
1 27
Σ
n
|
ΣΣ ==1==
n
(14)
We call above augmented loss function, which is approximate penalty problem to the target problem (1). The term Σn |2 Σn, Wiyay is convex when the weight matrix W = == [way]] is symmetric and term that promotes consensus among all nodes.
and it equals 0 bff = Zn. Apparently, it a regularization
Decentralized Augmented Gradient Adam (DAG-Adam). Inspired by the fact that decentralized SGD can be interpreted as standard SGD with augmented gradient (13)
easily inte-
grate the augmented gradient to the standard Adam method (Kingma & Ba, 2014). Decentralized It is observed that all communications occur when the stochastic augmented gradient is computed (see the highlighted part Algorithm[I] []. After that, each node i will conduct an adaptive step, which is untangled with communication. We call the structure utilized in DAG-Adam as communicat--hhen tateiiaaat--ee-appp.... This ad-
Augmented Gradient Adam, DAG-Adam for short is listed in Algorithm
justment of the algorithm structure is crucial. The stochastic gradient that used to compute m. and
5

---

Under review as a conference paper at ICLR 2022
Algorithm DAG-Adam
Initialize 2 arbitrarily; let 11, 52, E [0. 1); let m (0)
v.00) O; set y, properly;
For / = 1, 2,.,.... ....7 every node i do in parallel
Sample 9, < (x
V
)
stochastic augmented gradient;
JEN
m
(t) Bimg (1-1)
+ (1 91)
vi (t) B20g (1-1) + (1 B2) 9. о 0
(++1) = 2z 1
> adaptive step;
have incorporated the neighbor's information, which will correct the deviation in fixed point that introduced by different i/ (and H₃).
Learning curves (logarithmic scale)
Note that a parameter > 0 is added to the adjust the pri- ority to gradient descent, to promote consensus. Empiri- cally, we can set 1 for the convex scenario. But for the non-convex deep learning problems, the choice of will heavily influence both convergence rate and performance. We extensively discuss the influence of v/ in Appendix [ and empirically examine it in the later experiment section. While this paper we only focus on the extension of the vanilla Adam method, the core ideas such the augmented gradient and the communicate-then-adeee extended to AMSGrad or other adaptive gradient methods.
DSGD
10"
QG-DAdam
GT-DAdam
DAdam
DAG Adam
1110
10-2
0
100
200
300
400
500
600
700
structure can be
Iterations
Figure 1: Convergence comparison be- tween various algorithms for full-batch logistic regression problem.
Fixed point condition. The stochastic augmented gradi- ent and communicate- then---ppt structure utilized in DAG- Adam can remove the influence of the discrepancy in of and hence H;. Following the settings and arguments in Sec. 2.T we can derive the fixed point condition for DAG-Adam as follows (see the derivation in Appendix
C
Σ JEN.
wijzf() 0, Vi [n].
(15)
7
(z =0
(if x
x x0 in the limit)
(16)
n
Note that the fixed-point condition (15) for DAG-Adam, when = 1. is exactly the same as that
for vanilla decentralized SGD with full-bath gradient Yuuan et al., 2016). Relation (T6) implies
that DAG-Adam will converge to the stationary solution to problem (1). The following proposition
characterizes the distance between the DAG-Adam fixed point and the global optimal solution for the strongly-conver scenario.
Proposition 3 Under the same conditions as in Proposition ! the distance between DAG-Adam fixed point and x* can be characterized as follows:
G²G²
lim 10-+00
1
-+= (1 pp
x+1
(17)
It is observed in 17) that the distance is on the order of 0(72). Apparently, DAG-Adam will con- verge the global optimal solution when 7 - Moreover, DAG-Adam has the same communica- tion overhead as in DAdam, and is more communication--fficii also implies that AAG-Adam has the same limiting bias as decentralized SGD when //
than GT-DAdam. Proposition
Limiting point justification. We validate the limiting point analysis for DAdam, QG-DAdam, GT- DAdam, and DAG-Adam on the full-batch logistic regression problem. Table 5 in Appendix C3 lists the results we establish in Propositions D- When v/ = 1 in the DAG-DAdam method, which valid choice in convex settings in numerical experiments, the fixed point of DAG-DAdam is closet to the global solution x² when the cost function is strongly-convex. The learning curves of

---

Under review as a conference paper at ICLR 2022
DAdam, GT-DAdam, QG-DAdam, and DAG-Adam shown in Fig. The MSE metric in the n. Ex= ||x; ( x 2²1 From the figure, it is observed that the DAG-Adam algorithm can converge as fast as other decentralized adaptive algorithms but to more accurate limiting point. This limiting point is exactly the same as vanilla decentralized SGD, which consistent with our claim in the limiting point analysis. More experimental setting and results refer Appendix C.4
y-axis denotes 1
Convergence Analysis. We provide the convergence analysis for our proposed DAG-Adam for non-convex functions. The full proof can be found in Appendix E
and B2 satisfy the conditions that Y S min wy), (r is any positive constant) and B2 S To(GiRcys. Under Assumptions A.I A.4 and the augmented gradient shown is bounded, the decentralized augmented gradient generated by DAG-Adam algorithm satisfies that
Theorem Suppose the parameters
2-
21
/01 = =0( ((112)
- 12 ((x'))
ΣΣ t=0
( (a!
E uayz (0)
+ 0
T
TT
JEN:
(18)
where the augmented loss function f(xx is the one defined in (14. l is the minimum of the aug- mented loss. Further, holds for the globally averaged iterate z(() that
1i (
0 [(fx,
(0)
-" - +0 + 0 (1-p)
Σ IVf(=(0)11
(19)
T 1=0
-T
where z(()) = I/n 2; and is the second largest eigenvalue of W in magnitude.
Remark The theorem stated two conclusions. The first one is that the augmented gradient in DAG-Adam will converge neighborhood around 0 with constant learning rate ", and the neigh- borhood, when T + oo, is on the order of (o²)). The second one is that DAG-Adam will converge to a neighborhood around the stationary solution in terms of the globally averaged iterate a(t), The neighborhood. when learning rate 7 = O /T) and - oc. will be on the order of O(o²). ). is thus observed that DAG-Adam will converge the exact stationary solution with decaying learning rate and increasing mini-bate batch sizes, which is consistent with the results of Adam using the standard stochastic gradient in (Zaheer et al. 2018
Remark The non- non-vanishing term O(o²) in 18) and 19 is caused by the vanilla Adam algorithm structure, not the decentralized communication and update in DAG-Adam. Such term can be cor- rected by using AMSGrad rather than Adam in DAG-Adam. When there is no stochastic gradient (1) noise, the augmented gradient will converge to zero. In consequence, the v, will converge to zero over all agents as well.
4 EXPERIMENTS
In this section, we systematically compare the proposed method, DAG-Adam, with all previous mentioned state-of-the-art decentralized adaptive methods on typical CV and NLP tasks.
Implementation Details. We implement all the aforementioned algorithms with PyTorch 1.8.0 (Paszke et al. (2019) using NCCL 2.9.6 (CUDA 10.2) as the communication backend. For PAdam, we used PoTor'h's 's native Distributed Data Parallel (DDP) module. For the implementation of de- centralized methods, we utilize BlueFog. See Appendix F for more details.
4.1 IMAGE CLASSIFICATION: PERFORMANCE OVER VARIOUS CONFIGURATION
A series of experiments are carried out with CIFAR-10 (Krizhevsky et al. (009) and ImageNet (Deng et al. (2009)) datasets to evaluate the performance of the proposed AAG-Adam on both ho- mogeneous and heterogeneous dataset over different sizes of network. We utilize ResNet-20 on CIFAR-10 and ResNet-50 ImageNet (He et al. 2016).
Training configuration. All methods are trained using 90 epochs with mini-batch of size 32 each computing node. PAdam uses learning rate of 0.0125, while the ones for decentralized algorithms are scaled by the network size. In addition, QG-Adam (Lin et al. (2021) uses a learning rate 10 times smaller than other decentralized methods to avoid divergence" During the training procedure,
We examine QG-DAdam based own implementation of the algorithm listed in the original paper.

---

Under review as a conference paper at ICLR 2022
Table Classification accuracy comparison of different methods for CIFARIO dataset.
4 NODES
8 NODES
METHODS
IID
0.1
a = 1
a 10
IID
PADAM
90.28 #0.07
51.65
#0.88
84.33
40.
90.82
#0.23
91.19
#0.09
DADAM
87.23 14.14
53.71
83.67
10.14
86.34
#0.51
87.04
#0.12
QG-DADAM
34.24 83.43 20.22
57.89
10.34
71.97
+0.49
77.82
#0.13
GT-DADAM
20.17
56.48
64.63.2.22
86.71
20.31
86.47
#0.12
DAG-ADAM (v 1
84.62 #0.49
46.77 11.09
75.76 20.34
81.88
#0.79
82.38
#0.55
DAG-ADAM (v 2
07.50=0.33
51.63
82.24
87.82
#0.35
88.55 #0.33
DAG-ADAM (0= 10
91.39 #0.09
55.27 #0.31
86.64 20.03
91.00 #0.18
91.23 #0.09
the learning rate is warmed up in the first 5 epochs and is then decayed by a factor of 10 at 30, 60 and 80 epochs. The weight decay is chosen 5 x 10-5, We also compared the results of the proposed DAG-Adam with various V choices.
Heterogenerous data configuration. To simulate the heterogenerous data, the disjoint non-i.id training data over agents are generated through Dirichlet distribution Dir(a), where stands for the degree of the data heterogeneity (Lin et al. 2021, Yurochkin et al. 2019). The training data for a particular class tends to concentrate in a single node as - 0. i.e. becoming more heterogenous
while the homogeneous data is formed as + oo. See Appendix F for more details.
Performance comparison. Table [ compares the proposed DAG-Adam with other methods over networks with both homogeneous data distribution and heterogeneous ones. Two different network sizes (4 and 8) are tested using ring topology. With a proper choice of v. the proposed method consistently outperforms all other methods under comparison, including the centralized optimization method PAdam, matter what the data distribution is given. The left and middle figures in Fig. shows how the test loss and test accuracy evolves in a heterogeneous data distribution with a 10. DAG-Adam (with v le-1) converges faster than any other decentralized algorithms. As typical decentralized algorithm behaves, it was relatively slower compared with centralized PAdam algorithm in the beginning. but eventually caught up when the algorithm converged. The right figure in Fig. 2 plots the consensus error E | T||, which validates that the consensus error in Theorem is proportional to the choice of V.
0.8
10*
Concenous Emar
0.6
DAcam
10
QG DAdam
Yo
0.4
DAG-Adam (2e33)
DAcam
20a
DAC Adam (e-2)
0.2
DAC-Adam (2-1)
1077_
40 Epochs
40
20
Epochs
Epochs
Figure 2: The evolution comparison of loss, accuracy and consensus error for CIFAR-10 10 dataset on a heterogeneous (a 10) network of size 8.
90
0.8
IID
990 98%
a 1910 68-00 96-6 90%
1e=01
2%% 5757777777 % 74% 54 17 9/03 95 0.74
0.7
70
0.6
3e.01
10:01
48%
2%%
50
0.4
2152116266
0.3
03
33% 26.6 25% 754
0.2
1w-03
22% 25% 2000 301633000000 25%4
-30
10.3
10
10
10
10
102
Figure 3: An ablation study of the hyperparameter v in DAG-Adam for CIFAR-10 dataset on het- erogeneous networks of size 8. The heatmap on the right shares the same selection of and a with the left figure. We reported the detailed accuracy value in it.
Sensitivity constant. As shown in Table I the final classification performance depends the choice of constant // in AdG-A To better understand how y affects the DAG-Adam perfor- mance, performed corresponding ablation study with varying heterogeneity degree a as shown
8

---

Under review as a conference paper at ICLR 2022
in Fig. 3 For varying heterogeneity degree a, the constant v that achieving best performance lies in the range [le
5e for CIFAR- 10 typically.
Performance over different network scales. We further examine the performance of the proposed algorithm over different network sizes to see how good it can scale up in large decentralized network case. As shown in Table 2 under the exponential graph (Assran et al. 2019) and fine-tuning of v, DAG-Adam persistently achieves comparable performance with the centralized method until the node size reaches 64. Even under that case, the drop of performance is quite small.
Table 2: Comparison of different nodes and methods on CIFAR- 10 classification over homogencous data.
NODES
4
8
16
32
64
PADAM
91.28 +0.07
91.19
+0.09
90.67
#0.09
90. 15 11
90.11
=0.13
DAG-ADAM (v 1e-
84.62
#0.57
82.38
#0.55
84.35
#0.51
83.73
#0.49
83.90 +0.61
DAG-ADAM 1e-2)
87.50
+0.29
86.55
+0.33
#0.42
#0.42
87.83 #0.31
87.62
#0.37
DAG-ADAM (V 1)-1) 91.39 20.11
91.23 20.09
91.36 #0.12
90.16 20.07
89.98 +0.22
ImageNet results. We also validate the performance of our proposed method on relatively large- scale dataset ImageNet. We use PAdam to tune the learning rate (4 10-4) and wight decay x 10-1) hyper-parameters to reach a strong baseline. Then, the same hyper-parameters are applied for decentralized counterparts. In the experiment, the algorithms run on 8 nodes (i.e. 8 x = 64 GPUs) and train total 100 epochs with cosine decay scheduler. Our proposed method reaches top-1 accuracy 75.9 55.6% which is slightly better than PAdam.
Table 3: Comparison of different methods and models ImageNet classification.
METHOD PADAM DADAM
QG
GT
DAG/le-1 DAG/Ie-2 DAG/Ie-3
DAG/Ie-4
ACCURACY 75.62
70.53
73.89
74.736
66.506
73.750
75.445
75.96
4.2
LANGUAGE MODELING: PERFORMANCE OVER DIFFERENT TASKS
BERT (Devlin al. 2018) is widely used pre-training language representation model for NLP tasks. We fine-tuned pretrained BERT models (Base/Larre: 1 110/330 parameters) on the SQuAD Rajpurkar al. (2166) dataset. All experiments are based NVIDIA BERT implementation with mixed precision support. We examine the task over both static exponential graph and dynamic exponential graph setting (Assran et al., 2019). As shown in Table 4 with proper tuned hyper- parameter our proposed method reached best performance in both metrics.
Table 4: Comparison of different methods BERT fine-tuning (SQuAD) Exact Match and Fi-score.
MODEL
BERT-BASE
BERT-LARGE
TOPOLOGY
STATIC
DYNAMIC
STATIC
DYNAMIC
EM
F1
EM
F1
EM
F1
EM
FI
EM
PADAM
81.50
88.85
83.54
90.69
DADAM
80.61
87.57
80.31
87.42
83.25
89.98
83.16
89.77
QG-DADAM
79.4
86.98
80.17
87.33
83.05
89.84
83.89
90.64
GT-DADAM
80.66
87.85
80.67
87.81
83.81
90.51
83.95
90.61
DAG-ADAM (v 1c-1)
48.89
60.85
43.77
56.22
59.24
71.40
55.18
67.89
DAG-ADAM (v 1c-
71.98
81.62
70.30
80.15
78.20
86.68
76.85
85.59
DAG-ADAM (v= 1e-3
80.66
87.99
80.14
87.54
83.93
90.48
83.31
90.26
DAG-ADAM (v le-4)
81.79
88.93
81.89
88.96
83.82
90.71
84.28
91.08
5 CONCLUSION AND FUTURE WORKS
In this paper, we identified the limitation of existing adaptive gradient methods: the limiting discrepancy in the squared local gradient term (i.e., vf") can deviate the limiting point from the desired stationary point. To fix this issue, we proposed novel DAG-Adam algorithm that built upon the communicate-then-ddagy structure instead. DAG- Adam can provably converge to the desired solution even with heterogeneous data. Experimental results on a variety of deep learning tasks show that DAG-Adam persistently outperforms existing decentralized adaptive basclines. However, it is also observed in these experiments that DAG-Adam highly- to the hyper-parameter v. How to tune v automatically during the training stage crucial topic of the future works.
structure utilized in

---

Under review as a conference paper at ICLR 2022
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovie. Qsgd: Communication--liciiinnt sgd via gradient quantization and encoding. 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 (ICML), pp. 344- 353, 2019.
Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar. signsgd with majority vote is communication efficient and fault tolerant. arXiv preprint: 1trpriin::110005299,, 2018.
Jianshu Chen and Ali H Sayed. Diffusion adaptation strategies for distributed optimization and learning over networks. IEEE Transactions on Signal Processing, 60(8))4289 4305, 2012.
Tianyi Chen, Georgios Giannakis, Tao Sun, and Wotao Yin. LAG: Lazily aggregated gradient for communication-effict distributed learning. In Advances Neural Information Processing Sys- tems, pp. 5050-5060, 20.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of adam-typp -ttm-ttppe algorithms for non-convex optimization. In International Conference on Learning Representa- lions, 2018b.
Xiangyi Chen, Belhal Karimi, Weijie Zhao, and Ping Li. On the convergence of decentralized adaptive gradient methods. arXiv preprint arXiv:2109.03114 2021a
Yiming Chen, Kun Yuan, Yingya Zhang, Pan Pan, Yinghui Xu, and Wotao Yin. Accelerating gossip sgd with periodic global averaging. In Proceedings of the 38th International Conference on Machine Learning (ICML), 2021b.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: large-scale hierarchical image database. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 248-255. leee, 2009.
Jacob Devlin, Ming-Wor Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv 1reprina:1810.048005, 2018.
P. Di Lorenzo and G. Scutari. Next: In-network nonconvex optimization. IEEE Transactions Signal and Information Processing over Networks, 2(2):120-136, 2016.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 201 la.
John C Duchi, Alekh Agarwal, and Martin J Wainwright. Dual averaging for distributed optimiza- tion: Convergence analysis and network scaling. IEEE Transactions on Automatic control, 57(3): 592-606, lb.
Hongchang Gao and Heng Huang. Periodic stochastic gradient descent with momentum for decen- tralized training. arXiv preprint:2008. 10435, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In IEEE Conference on Computer Vision and Puttern Recognition (CVPR), pp. 770-778, 2016.
Diederik P Kingma and Jimmy Ba. Adam:
method for stochastic optimization. arXiv
preprint: 1412.690, 2014.
Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. In International Conference on Learning Represen- tations, 2019a.
Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning, pp. 3478-3487, 2019h.
10

---

Under review as a conference paper at ICLR 2022
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 International Confer- on Machine Learning (ICML), pp. 1-12, 2020.
Lingjing Kong, Tao Lin, Anastasia Koloskova, Martin Jaggi, and Sebastian U Stich. Consensus control for decentralized deep learning. arXiv 11pprint:2122.048266 2021.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
7. Li, W. Shi, and M. Yan. A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates. IEEE Transactions Signal Processing, July 2019. early acces. Also available on arXiv: 174.017704.0807.
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, pp. 5330-5340, 2017.
Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. In International Conference on Machine Learning, pp. 3043-3052, 2018.
Tao Lin, Sai Praneeth Karimireddy, Sebastian Stich, and Martin Jaggi. Quasi-global momen- tum: Accelerating decentralized deep learning heterogeneous data. In Proceedings of the 38th International Conference on Machine Learning (ICML), 2021.
Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. In International Conference Learning Representations, 2019a.
Xiaorui Liu, Yao Li, Rongrong Wang, Jiliang Tang, and Ming Yan. Linear convergent decentralized optimization with compression. arXiv preprint arXiv:2007.0022 2020.
Yaohua Liu, Wei Xu, Gang Wu, Zhi Tian, and Qing Ling. Communication admm for decentralized consensus optimization. IEEE Transactions on Signal Processing, 67(1)225565- 2579, 2019b.
Cassio G Lopes and Ali H Sayed. Diffusion least-mean squares over adaptive networks: Formulation and performance analysis. IEEE Transactions on Signal Processing, 56(7):3122-3 2008.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Confer- ence on Learning Representations, 2018.
Songtao Lu, Xinwei Zhang, Haoran Sun, and Mingyi Hong. Gnsd: A gradient-tracking based non- convex stochastic algorithm for decentralized optimization. In 2019 IEEE Data Science Workshop (DSW), pp. 315-321. IEEE, 2019.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication--ffiiienn learning deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp.
PMLR, 2017.
Parvin Nazari, Davoud Ataee Tarzanagh, and George Michailidis. Dadam: A consensus-based distributed adaptive gradient method for online optimization. arXiv preprint arXiv: 190109990,,,, 2019.
A. Nedic, A. Olshevsky, and W. Shi. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27(4):2597-2333 2017.
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimiza- tion. IEEE Transactions on Automatic Control, 54(1):48-6) 61, 2009.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, al. Pytorch: An imperative style, pegghherffrmacce deep learning library. In Advances in Neural Information Processing Systems (NeurIPS). pp.
2019.
11

---

Under review as a conference paper at ICLR 2022
G. Qu and N. Li. Harnessing smoothness to accelerate distributed optimization. IEEE Transactions on Control of Network Systems, 5(3):1245-122 1260, 2018.
Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. Squad: 100,000+ questions for machine comprehension of text. arXiv preprint wwx.vv1606.05200 2016.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprint:1904.090 2019.
Sashank J Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In International Conference on Learning Representations, 2020.
Ali H Sayed. Adaptation, learning, and optimization over networks. Foundations and Trends in Machine Learning. -,- 2014.
Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In International Conference on Machine Learning, pp. 3027-3036, 2017.
W. Shi, Q. Ling, G. Wu, and W. Yin. EXTRA: An exact first-order algorithm for decentralized consensus optimization, SIAM Journal on Optimization, 25(2):944-966 2015.
Wei Shi, Qing Ling, Kun Yuan, Gang Wu, and Wotao Yin. On the linear convergence of the admm in decentralized consensus optimization. IEEE Transactions on Signal Processing, 62(7): 1761, 2014.
Sebastian Urban Stich. Local sgd converges fast and communicates little. In International Confer- ence on Learning Representations (ICLR), 2019.
Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. d: 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 error-commensated compression. International Conference Machine Learning, pp. 6155-6165 PMLR, 2019.
César A Uribe, Soomin Lee, Alexander Gasnikov, and Angelia Nedić. A dual approach for optimal algorithms in distributed optimization over networks. Optimization Methods and Software, pp. 1-40, 2020.
Cong Xie, Oluwasanmi Koyejo, Indranil Gupta, and Haibin Lin. Local adaalter: Communication-effiiient stochastic gradient descent with adaptive learning rates. arXiv preprint arXiv:1911.09030. 2019.
Ran Xin, Usman A Khan, and Soummya Kar. An improved convergence analysis for decentralized online stochastic non-convex optimization. arXiv preprint: 04195, 2020.
J. Xu, S. Zhu, Y. C. Soh, and L. Xie. Augmented distributed gradient methods for multi-agent op- timization under uncoordinated constant stepsizes. In IEEE Conference on Decision and Control (CDC), pp. 2055-2060, Osaka, Japan, 2015.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis communication efficient mo- mentum sgd for distributed non-convex optimization. In International Conference Machine Learning, pp. 7184-7193. PMLR, 2019.
K. Yuan, B. Ying. X. Zhao, and A. H. Sayed. Exact difusion for distributed optimization and learning - Part Algorithm development. IEEE Transactions on Signal Processing, 67(3):708 723, 2019.
Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3):1835-1844 2016.
12

---

Under review as a conference paper at ICLR 2022
Kun Yuan, Yiming Chen, Xinmeng Huang. Yingya Zhang, Pan Pan, Yinghui Xu, and Wotao Yin. DecentLaM: Decentralized momentum SGD for large-batch deep training. arXiv preprint arXiv:2104.1190 11981, 2021.
Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Nghia Hoang, and Yasaman Khazaeni. Bayesian nonparametric federated learning of neural networks. In Interna- tional Conference on Machine Learning, pp. 7252-7261. PMLR, 2019.
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, Neural Information Prucessing Systems, volume 31. Curran Associates, Inc., 2018. URL https:
N. Cesa-Bianchi, and R. Garnett (eds.). Advances / neurips cc/ pdÉ
/agp://2000/ELLLe000333351.//2/3 7437a1 3333
Dongruo Zhou, Jinghui Chen, Yuan Cao, Yiqi Tang, Ziyan Yang, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint arX1v:1808.05661,2011
13

---

Under review as a conference paper at ICLR 2022
A
NOTATIONS AND PRELIMINARIES
Notations. We introduce several notations as follows:
a1 22
mm
V1
m2
V2
X A
E Radx1
m
E
Rnnxx
E Rudx1
n
mn
nn
V Fi (11
V V22 E2)
Vf(x)) A
Rudx1
F (mnn Em)
W [wyy] Ruxn
W W @ r7 E Rrdxnd where means the Kronecker product.
In (1, ...., ()
x = 1,,,,, & La)x R
Given vector Rd, we let diag(x:) diag(ai, ,.a Rddd be diagonal matrix.
Given a positive definite matrix A, we define the weighted normal ||x|| = xx Ax, ||>||| as vector & norm and ||||] matrix & norm.
Algorithm reformulation. With the above notation, rewrite DAG-Adam in Algorithm following stacked vector form:
into the
(1) () + (1 - W)x(1)
(20)
m (1) =Bmm (1-1) (()
(21)
(() =B2((t-1)
(2)g(t) (t)
(22)
((+1) =x(() - (H + eT) -mmm (9)
(23)
where ((!) is the diagonal matrix defined as H Diag( Vv())..
Smoothness. Since each (z) is assumed to be L-smooth in Assumption A.1, holds that f(z)
" f(()) is also L-smooth. As a result, the following inequality holds for any x, y E Rd:
L x y11 < (Vf(y), x 8)
f(x) f(y)
(24)
(1+1) x
Σ
wiyz
jeNi
Figure 4: An illustration decentralized topology and its communication pattern
14

---

Under review as a conference paper at ICLR 2022
Algorithm 2 DAdam (Nazari et al. 2019)
Initialize 2 arbitrarily; let 11, B2, B3 (0, 1); let m())
v/!))
-6(0)
0: set 7 properly:
For / = 0, 2, ...., T 1, every node i do
Sample 9i (0) F (1) (
m (0) 8imi ((-1) (1- 31) (0)
(t) U (t) $20, (t-1) + (1 B2) 9i C 9i
(8)
of Bzt," + +(1
(1- - B3) max (o
0
3:
((+1) EjEN, Wiyaz (1)
m
2i
Weighted norm inequality. In this paper, the weighted norm ||=||²a only considers the scenario in which diagonal matrix. Suppose the diagonal elements the diagonal matrix A satisfy that 0 < < [A]i b for all i, one useful inequality is
al|=||a = || | S b||=|12
(25)
The proof is strait-forward:
||x|| 2 x²' A2r (A A(A S (1
b||=11/
(26)
We can use the same argument to show a||=>|| < Ax as well.
Communication topology. Figure 4 provides graph example to illustrate the decentralized topol- ogy and its communication pattern that is used in all decentralized methods listed in the paper.
B
ADAVE-WWLLI/HEEN-COMNNUNNNEEEE STRUCTURE AND ITS LIMITATION
B.1 DADAM AND ADAPT-WHIIF-CCMMMONNNN STRUCTURE
The DAdam algorithm Nazari et al. 2019) is listed in Algorithm 2
B.2 FIXED POINT CONDITION FOR DADAM
To see the fixed point condition for DAdam, we assume the iterate x in DAdam converges to some fixed point x; as k - so for any i [ni]. In order to remove the influence of the gradient noise,
let g: be the full-batch gradient V f(())) easy to verify that
(1) = F (9) E.) for any i E [n]. Under this setting,
m
()((;))) and v, :e ()((z;)) v((x;')
(27)
we define H, == diag( / (I()) O vf((x))) lighted step in DAdam will become (when x))
) to be a positive diagonal matrix, then the high-
a 711 + el) - 'V(({)) Vi [n].
(28)
JEN,
which is the fixed-point condition listed in 5). If we further let x = 1 Em of the following relation can be achieved by (28) and Assumption A.3:
F
500
H, -1+
1=1
H + el) (V((2(²)) =0
π
(1I + (Il++el)VV/((>>) =0 0 (if o
x ~ in the limit). (29)
n
The last relation is the one listed in 6
15

---

Under review as a conference paper at ICLR 2022
B.3 PROOF OF PROPOSITION 1
Before we prove Proposition
1 we need to introduce several notations:
x x co
In E Rnd
x col(x
x } E Rnd where x = -
x = colf fx" .... x²| Rnd where x² is the optimal solution to problem
when the
cost function is convex
Vf(x**) = (Z) ... V(n(z))) ERd (H (H+ diag (H1 + cf)- .... (H, +
With these notations, we can rewrite the fixed-point condition (2 into compact manner:
x Vx 7 + -
Vf(x
(30)
To examine ||x - x*1,, we will evaluate ||x* - x x and || x²| respectively.
Upper bound of | 1² Left-multiplynng 1 to both sides of recursion 30). achieve
H. + ((f = O.
(31)
With the above fact, we have
2000 x11l
00 x²
1
Hi +el) (V[('T)' Σ v)(("))
i=1
1 Σ
<
_0000
x²
1=1
+71
H, + +el) - [1
1
7||
(
(1
7/4 2
||ا
x²
B +
7h || x
(32)
vn
where the last inequality holds because each fi(z) j-strongly convex and L-smooth, and the definition of constant B as follows:
B =
H, ++1+ 1
(x:
(33)
Inequality
32 leads to
v Vnla x+11 S 2
2L
+ - 1|1 x x
(34)
Upper bound of ||x00
x²1 Subtracting x from both sides of 30 we have
[) x²0 (H - -Vf(x
(35)
With inequality (43) in Yuan et al.
2021 we have
[I(I (x
x00 || 2 (1 p)1|x* - x
(36)
With 35 and
36 and noticing
[|(++e))-+
= mnax
111) < L. we achieve
> Vf(x'*]
7G
|x - x
<
< (1- p)e
(37)
(1 p)e
16

---

Under review as a conference paper at ICLR 2022
where the last inequality holds because of Assumption A.4.
Upper bound of oi n Ei=1
x²
112. With (34) and
37
we have
1x20
x"1
S
1x
x
x0
+
v x''l
2L
1 2
||x>00
-
/
1
2L
GG
2/nB
(38)
(1
p)e
1
If we ignore the influence of y and L, finally achieve
1 - xx x²1
G² =0 p)) (1(1=00(00))) B2)
lim
1
x²12
(39)
Lower bound of lim Ei=1 || (c) x² 112. Now we show that the terms depending B in the upper bound (39) are necessary and cannot be removed by an improved analysis. In fact, there exists strongly convex and smooth functions such that (" generated by DAdam satisfies
lim 12
2 B².
(40)
To prove the above conclusion, we consider minimizing problem of the form
I with
f((z) = 7 -/(0 v1)²
Vi E [n]]
(41)
where E R. Apparently, the solution to problem I is given by =
Σ/=
Next we let we have
i=
z be the limiting point of DAdam (Algorithm
[2] in node With notations Sec. B.2
(((1²)) x; V/
(42)
H = [x 12,"" - 3/1 H + - (Ha (H++ E R***
(43)
(44)
Under the above setting, the limiting point of DAdam
(30 reduces to
x
Wx 00 7H + + (V(x))
(45)
in which W e guxn is the weight matrix. By left-muliplying 41T to both sides, have
1 Vi(())))
1 Σ n
Vi 0.
(46)
n
vi(aT))+
+e
r
+
On the other hand, it is easy verify that
91
=
x
= x
(47)
1=
With (46) and
47
we have
[((()))
46
1
Vi((1;))) +c ((
[)((x
(f((z
+ (f(())))) + Σ (
Σ (z
n
n
17

---

Under review as a conference paper at ICLR 2022
Algorithm 3 QG-DAdam (Lin et al. 2021
Initialize _ arbitrarily; let 31, .2 E (0. 1); let m0)
mn!
v2()) -0.0)
0: set y properly:
For k 0, 1, ...., T - 1, every node do
Sample 9i (0) Fxx
(1K) =
m (0) fi [(-1) (1- Bi)gi (0)
vit) B20; 020(1-11 + +11 -1- 32)g (t) (t),
9i
(++1)
ΣJEN, wiy (1) (0)
? m (9)
d0) (x(tt1)
_ (11) |1 (1+1)
2f 112:
m (6) Bim (1-1) (1 81) )
600) B20/(-11 1) + (1 - B2 ( d.
Vi((z))) + Vf(zz +
x
x )|
11
Vf((2.0)
Σ (((
V(((;)))
43
(H, +e) ()())))
Σ
B.
(48)
Finally, we have
lim (-000
1
(1)
112
00 x*1
71
+ x - =1112
xx 00
x 1|2
x+1
IV
1
||
B²
(49)
where equality (a) holds because
xt) (x T
117)
11
x²) =
(50)
Inequality (49 implies that the term B² cannot be removed from bound analysis for our constructed problem.
39 with any improved
B.4
QG-DADAM AND ADAPT-THEN-COMMMUUN
STRUCTURE
The QG-DAdam algorithm (Lin al. 2021) is listed in Algorithm
B.5 FIXED POINT CONDITION FOR QG-DADAM
We let (1( + 20 as + oo for any e [n]. We also assume each node can access the full-batch gradient (x. in order to remove the influence of gradient noise. Under such setting, we can verify in QG-DAdam that
det = 0, m. = O,
-0
m 00 (1 B1 (z
vf = 32
V/((29))
(51)
18

---

Under review as a conference paper at ICLR 2022
Substituting mi and o. the highlighted step in QG-DAdam, can achieve the fixed-point
condition as follows 1
(1 - -
Vi E [n].
(52)
JEN;
where H, diag( V (x ④ (+( ). we further let 7000 1 Ei=l o7 the following
relation can be achieved by (52
and Assumption A.3:
2(1 31)
Σ
2(V1- 3,H, + el) -
2m1
n
B211, el) ([(())) =0
71
Σ 82H1+ + = xf
x x in the limit), (53)
The last relation is the one listed in 10
B.6 PROOF OF PROPOSITION 2
The proof of Proposition is similar to that of Proposition can rewrite (52) into the following compact manner:
With notations defined in Sec. B.3 we
W(x 711 (1) +
(54)
Upper bound of | - x'1|
---=x Left-multiplying 1 to both sides of recursion 30 we achieve
11V1, + +el)
(V/ V(((z))) = 0.
(55)
2=1
Using a similar argument to that in
32 and
34
we have
2/rB
2T.
Vnlj
x
x00
(56)
in which the constant bias term B is defined
1
B (VI +2)
(57)
n
Upper bound of ||x00 x01 Subtracting x from both sides of (54). we have
(1 -1- (x - ) = -- - 3:)
+ el)
-V((x Vf(x
(58)
Using similar arguments in 36 and 37 and facts that
3,H +c)
max; (lxx]ll[[TTBBB 3,H, + - 1112} - and || S 1, we have
7(1 - B1 V[
7
x - x <
(59)
p)c
p)c
Upper bound of lim Σn || - x² x=1 Using similar arguments to those in we achieve
38) and
39
lim
|0:
1|xx00 x -
x011== n
1
0 (11
720² pp (1-
BB2)
(60)
Lower bound of lim can easily establish
||
x+12
11
With the same constructed problem as
41
lim
211 12
(61)
n
following the arguments in
50 where B is defined in
19

---

Under review as a conference paper at ICLR 2022
B.7 GT-DADAM
Fixed-point condition. we define H 1/2 E H, the fixed-point condition of GT-DAdam (i.e..
Algorithm 2 in (Chen et al. 2021ab) is as follows:
24
Wiyaj
7H + cl) cI) vVf-())
Vi [n].
(62)
JEN.
x000
r
(H + El) -Vf()=,
1=1
V)(x))= (If xf
nn = 20 in the limit)
(63)
n
It is observed that the fixed-point of GT-DAdam satisfies the optimality condition of problem
Proposition 4 Under the same conditions in Proposition 7 the distance between GT-DAdam fixed point and the global solution xt can be characterized as follows:
G2
lim 100
|
1= = 0 (1 p)
(64)
Proof. With notations defined in Sec.
B.3 the fixed-point condition in (62) can be rewritten as
x
Wx 7( + - V) (V(xxx(((x>>)
(65)
where H = diag H, ... H) E Radxud
Bound of ||000 I|. Left-multiplinng 4 both sides of recursion 65 achieve
\ = 0.
(66)
With the above fact, we have
n Σ Vf(("))]
10000
x² = |
7
n i=1
i=1
1
< |
?
fi(1
ff((=)))|
n
n
1
+ 7
V
ff(x;²0
v((%)))
< (1 (1- 2 x11|
+
|
x
(67)
where the last inequality holds since each fi(x) j-strroglyy convex and L-smooth. We thus have
2T. ||x
Vn|| - =11| S
-
x
(68)
/
Bound of ||x0
x²0 Subtracting x from both sides of (65 have
(I (x
- el) - Vf((x
(69)
With inequality (43) in Yuan et al.
2021 we have
[I(T () x00) ||| (1 p) x
(70)
With 69 and 70 and noting that ||( + +cI) cI)-~111 - 1/c, we achieve
| - x00 || < > Vf(xx)) ]|
(71)
p)E
20

---

Under review as a conference paper at ICLR 2022
Proof of Proposition
4
With (68) and 71
we have
xx
x
Σ x
x
x
x"1l
2L
S +
||x x
2L
-
(1
+
Vf(x>)]1
(72)
(1
p)c
The above inequality implies that
72G22
(1)
x x=12 0
1
(73)
61000
17
( [1-p)
Different from Propositions 7 and 2 it is observed from Proposition 4 that the distance between the GT-DAdam fixed point and the optimal solation will diminish to zero as learning rate - O. However, GT-DAdam will incur two rounds of neighborhood communication per iteration, which is much more expensive than DAdam and QG- GGDDAdam
Remark 3
C FIXED-POINT CONDITION FOR DAG-ADAM
C.I FIXED-POINT CONDITION
(1) + 2; for any E [n] in DAG-Adam. We further assume each agent can When + we let 2;
access the real gradient V (z) instead of the stochastic gradient VF(r;t)). Under this setting, we verify that
g vf((z;)) + (z
Σ w)) JEN,
(74)
and m 20 step in DAG-Adam that
2 = 08 @ g By letting H, = diag( / /U }. it can be derived from the adptive
x.- -. (H, + 9, Vi [n]
(75)
xx( ) + (x: - Σ
w1 = O. E
(76)
JEN
[i(xz;)) =
(77)
n
Vf((z))= =0 (If xF = = in the limit)
(78)
other words, DAG-Adam can converge to the stationary solution xf x in the limit. Compared to DAdam and QG-DAdam in which the discrepancy between H,'s has made the limiting fixed point deviate from the desired solution, the communicate-thenaddeee structure in DAG-Adam make immune to the difference between Hy.
C.2 PROOF OF PROPOSITION
With notations defined in Sec. B.3 the fixed-point condition in (76) can be rewritten as
vf(x " W)x =0
(79)
Bound of || - ==1]. Left-multiplying 1 to both sides of recursion 79 achieve
Vf( = 0.
(80)
7 1=1
21

---

Under review as a conference paper at ICLR 2022
Table 5: Comparison between different decentralized adaptive methods in the limiting point distance the global solution x" when cost function in problem ① strongly convex. The learning rate y is set as constant, and the full-batch gradient fx()) can be assessed per-iteration.
Algorithm
Distance global solution
DAdam Nazari et al.
2019
B
[-p)
QG-DAdam (Lin al.
2021)
(1- (1-P)=E2 B²
1202
-202
GT-DAdam Chen et
2021a)
(1-p)=
JP02
DAG-Adam (ours; v
(1 (1-p)z
Using similar arguments to 67 we achieve
2L
x 2=1l S
1|x x
(81)
/
Bound of ||x00
x | Subtraccin x from both sides of 79) we have
(1-W) xx)= -
(82)
With inequality (43) in Yuan al. 2021), we have
(I () - x || 2 (1- 110p))ll>* x
(83)
With 82 and 83
we achieve
||x
(84)
(1 p)v
Proof of Proposition
3 With 8 and
84
we have
|
|
/n 20 - x+1
2L
S (1 +
||xx - x
(1 + 2L
7
|f(x'')
(85)
(1 - p)v
The above inequality implies that
lim t-000
1
10
(2)
x+1| 0
7²G²
(86)
2)
C.3 COMPARISON IN LIMITING POINT DISTANCES TO GLOBAL SOLUTION
When v 1 in the DAG-DAdam method, which is a valid choice for convex settings in empirical studies, the comparison between different decentralized adaptive methods in the limiting point distance to the global solution x² can be listed as follows:
Tlste the results we establish in Propositions
DAG-Adam < GT-DAdam < QG-DAdam s DAdam
(87)
This conclusion matches with the numerical experiment in Fig.
C.4 EXPERIMENT SETTING FOR LOGISTIC REGRESSION (I.E., FIG
In this experiment, we consider the binary logistic regression problem:
min Σ f((x) + ZER n 1=1 2 |1/1 where f((x) = K
X
Σ In (1 + cxp(-nAAh).e)))
K
(88)
k=
22

---

Under review as a conference paper at ICLR 2022
where h4 E Rd is the k-th feature vector agent and Yi (+1,-1) is the corresponding label. In the experiment, we set = 0.25, n 16, and all computing nodes are organized into the (undirected) ring topology. The weighted matrix is simply generated through the average rule that satifies Assumption A.3. Also, we choose d = 25 as the dimension feature vector and generate K= 50 data for each agent locally. The corresponding y generated through pre-set random xe vector. We first compute the linear score =x,x", then determine the 7 by the probability based on the sigmoid value. For all algorithms, we choose the constant learning rate = 0.01, B = 0.9, 82 0.99. One exception is that choose 31 0.1 for QG-DAdam algorithm achieve better convergence performance.
(1) of various algorithms Besides the learning curve have shown in Fig. we also plots the Uj the last iteration in Fig. 5 To characterize the difterence between different agents, we use the box (t) of each entry among all agents. From the figure, it is clear that the plot to show the difference of of
o in DAG-Adam algorithm is almost zero when the algorithm converged, which is much narrower and lower than others methods.
The box plot of gradient square term in each entry.
0.06
entry
0.05
1
grad_sp square
0.04
2
3
0.03
4
5
7
0.01
8
DAG Adam
DAdam
GT-DAdam
QG DAdam
methad
Figure 5:
The boxplot of the first 9 entries of gradient square term ( the end of iteration of various
algorithms. The box represents the mean, quartile, and the min-max value of that entries cross agents.
Fig. provides complementary experimental results to Fig. [ We added new algorithm named which reparameterizes DAdam to obtain a communicate-then-adeee addition, the convergence with both constant and decaying learning rates are depicted in the left and right plot in Fig. G respectively. The observed that DAdam-Retl ReParam converges closely to DAdam, and both approaches converge to less accurate solution than DAG-Adam.
structure. In
Learning curves (logarithmic scale)
Learning curves (logarithmic scale)
DSGD
QG-DAdam
GT- ET-DAdam
10c
DAdam
Excess Risk
Excess Risk
AdG-A
10
DAdam-RePall
10
DSGD
QG-DAdam
10-2
10
GT-JAdam
DAdam
10
10-7
DAG-Adam
ReParam
100
200
300
400
500
600
100
200
300
400
500
600
Rerations
Iterations
Figure 6: Convergence comparison between various algorithms for full-batch logistic regression problem. The y-axis indicates the excess risk. ie.. 1 Σn [[[(=())) - -"). Left plot: convergence with constant learning rate. Right plot: convergence with stair-wise decaying learning rate.
23

---

Under review as a conference paper at ICLR 2022
D MORE DISCUSSION ON THE HYPER-PARAMER //
This section discusses the role of hyper-paan eeper--araeeter v in DAG-Adam, and how it influences the con- vergence performance. To this end, first discuss whether v is needed in the vanilla decentralized SGD (or DSGD for short) algorithm and DAdam. Next, we will study the influence of y in the more complicated DAG-Adam algorithm.
D.1 INFLUENCE
DSGD
Without loss of generality, we consider the DSGD method with a full-batch gradient. In this setting, augmented gradient of DSGD is given by
(t+1) 7 [+ + 2
Vi E [m]]
(89)
JENS
augmented gradient
With notations defined in Appendix A and the introduction of the hyper-parameter in DAG- Adam, we can rewrite the above recursion into a more compact form
x(+11)
x (t) (F(x(())+ (I-W)x(!))
-1--
DJT D +w) x(1) -VP(((9))
(90)
The above recursion implies that the hyper-parameter v will replace the original weight matrix W with W, whose eigenvalues are derived
cig. (W) = (1 - 2) 1 + cig, (W)
ciga (W) = 1/1 cig.(W)
(91)
implies all eigenvalues of W are more closer to value for any и E [0, 1). Since larger spectral gap, i.e. 1 (WV), will reduce the mixing time of gossip average and hence speed up the DSGD convergence, the optimal choice for DSGD is 1; other values will not improve the convergence of the vanilla DSGD.
where cig. (W) stands for the k-th eigenvalue of matrix W. Equation
We validate the above discussion with deep learning experiments over CIFAR-10 10 dataset. Fig. illustrates the influence of on vanilla DSGD. It is observed that y 1 enables DSGD to converge fastest and achieve the best validation accuracy, which is consistent with the above conclusions.
v=1.De+00
0.9
v=1.0e 01
v=1.0e.0
Validation Accuraci (
>=1.De:03
0.7
109
0.5
v=1.0e+00
0.3
v-1.0e-01
v=1.0e-02
0.2
v=1.0c 1.0e-03
40
60
80
20
40
60
80
Epechs
Figure 7: Loss and accuracy evolution for CIFAR- 10 dataset using DSGD(v) under a homogeneous network of size 8. Left plot: training loss. Right plot: validation accuracy.
D.2 INFLUENCE OF ON DADAM
Since DAdam is an immediate variant of DSGD, we expect the influence of v on DAdam will be similar to that DSGD. To validate it, impose hyper-parameter to DAdam recursion:
(1)
(22)
24

---

Under review as a conference paper at ICLR 2022
( =m (t-1) +1 (1- (1)g(
(93)
(0) =32(((11) +1 - (1-1
(g gg)
(94)
x (++1) =(11 1/1 + + 7 + =
(95)
Fig. illustrates the influence / on DAdam. Similar to DSGD, is observed that DAdam with (i.c., the vanilla DAdam with introduction of i/) has the best convergence performance.
0.9
x 10
0.3
Validation Accuracy
0.7
10a
0.6
10
v= 10000+00
v=1.0e+00
v= y=1.0e.01
v=1,0e:01 01
x0-1
v=1. 02-000
v=1.0e-02
03
v= 1.00e-03
20
40
60
80
20
40
60
80
Epochs
Epochs
Figure 8: Loss and accuracy evolution for CIFAR- 10 dataset using DAdam(v) under a homogeneous network of size 8. Left plot: training loss. Right plot: validation accuracy.
D.3 INFLUENCE OF V ON DAG-ADAM
Without loss of generality, consider DAG-Adam with dimension d 1. In this scenario, DAG- Adam can be rewritten as
(0) vf(((()) + (T W)x
(96)
?
m (t) (t-m(-1) + (1 31 31)g(t)
(97)
(1) 12 + (1 (2) og(
(98)
x (++1) = (1) ((H (1) + =I) m (1)
(99)
where W E Raxa the weight matrix and H = diagf diag(vv(() E Raxa is a diagonal matrix.
Subtracting 99 by $n times 99 with one iteration shift, we have
(!)) -
((x(1-1) (H + mm + + (
(m
(100)
Rearranging the terms in the above recursion, we obtain
((++1) =x(1) (1 - (1) -e)_ + B1 (x - (11-1))
+ 31 (((H- + (H + + m (t-1)
(101)
In the following, we will first study a simple example that can shed lights on the influence of on DAG-Adam, and next we will discuss the more generalized scenario.
An illustrating example. We consider a trivial scenario in which H = aT, which amounts to the case where all nodes maintain constant ei across i and in the local buffer. As we have shown in the convex experiment in Fig. 5) this trivial scenario becomes valid in the asymptotic stage of
DAG-Adam in which 0 converges to the same value v for any E [n]]
(t)
Substituting H()) = aT into (101). we have
x ((+1) (() 7(1 - (1)
(0) + +,((x(0) - x((-1))
a+t
= =[(1- 1 31
I+ 1- B1
7(1 (1- a
W]x(1)
Vf(x(9) + (x((()) - x((-1))
v(a +c) v(a+e)
(102)
25

---

Under review as a conference paper at ICLR 2022
From the expression of WDAG, it is observed that the optimal value for to minimize the mixing time of the weight matrix atte I-Di' which is not as in the vanilla DSGD algorithm. In addition,
worth noting that WAG cannot outperform W in terms of mixing time for any choice of v.
This trivial example illustrates the necessity to have the hyper-parameter in DAG-Adam. The introduction v to compensate the negative influence of the communicate-then-adeeee structure DAG-Adam which incorporates both the gradient and the consensus constraint into the adaptive momentum buffer. The weight matrix DAG can quite inefficient to aggregate information no exists speed up partial averaging.
Generalized scenario. Unlike the above trivial scenario, is very challenging to determine a proper value for in the general scenarios. To see it, we ignore the last term in (TOT) to achieve
(++1) u(1 (H + W)) (1) (1 (H + VV((x())
:m WDG
+ (x
(1-1)
(103)
which is reasonable approximation to 101 since Ba typically 0.999 and v()) (and hence H()) will not change dramatically. The first term in (103 mixes (1))) with weight matrix
WDAG = (1 v(1 - (H) + + ( (H) ( +
(104)
If we we A = r(1 (H) (1) + + it holds that
-1- /
1/2
(105)
The left-hand side of 1105 is the similarity transformation of WDAG. Hence, the eigenvalues of WDAG equal ones of the right-hand side of (05)). Unfortunately, it is difficult to determine the eigenvalues of A 1/122 not to mention the optimal value for v. However, it is obvious that 1 is not necessarily optimal for DAG-Adam. This motivates us tune in experiments to boost the convergence performance of DAG-Adam. In fact, the results in Table I (with CIFAR-10 dataset), Table (with ImageNet dataset), and Table SQuAD dataset) corroborate that not the optimal choice for DAG-Adam. How to find the optimal automatically is the main direction of our future work.
E CONVERGENCE ANALYSIS
E. CONVERGENCE PROOF OF DAG-ADAM
As we motivated in the Section 3 we consider the augmented loss function
K
=(x)=f(x) =
+ V 27
|x||>w>>
where f(x) = Σ [x((*))
(106)
k=
It is easy to verify that
Vx, (x1
(2(2))
vxL(x)=
[ - w)x vf(x) ([-WW)x
(107)
Vxx (xx)
which is exactly the same format as our decentralized augmented gradient in equation 20
Proof idea. Therefore, we can view our DAG-Adam over multiple agents as the standard Adam for virtual single agent with a long stacked vector. This observation leads to the following conver- gence analysis idea. First, standard Adam to show the convergence the decentralized augmented gradient. Next, based on that, establish the consensus lemma show that the models between all agents close. Last,
the similar proof technique Zaheer al. (2018) did for the
26

---

Under review as a conference paper at ICLR 2022
combining two, finally arrive the convergence of centralized iterate, [ the common decentralized algorithm theorem stated.
It is common in the proof of adaptive gradient methods, for example Zaheer al. 2018): Chen
et al. 2021a; 2018b;; Reddi et al. (019 2020), to assume the gradient V [a ( and/or stochastic
gradient V (a. :E:) have bounded & or lo norms at all iterations t, i.e., || (z; S G and [x (2
:.)il - G. Hence, it is nature to see we need the similar bounded gradient assumption on the augmented gradient. However, notice our augmented gradient has (7 W)x term. So need to further assume that ||x(||| I C. This is relatively strong assumption, but it can be strictly achieved by simply taking a projection step. Also, in the practice, we always observe that the terms gt() converges to a very small value without any requirement on the boundary on the iterate, as shown in Fig. In this case, we can show that
lgg ooo S max V (= + (1 || G |>
V ||
G KC
(108)
G
Same as the paper Zaheer et al. 2018)) did, we show the case that there is no-momentum for the sake of simplicity, i.e., 31 0, which is typically referred RMSprop.
Lemma (Convergence lemma of augmented gradient) Suppose the parameters "I and Bo satisfy the conditions that 7 S z-2u v < min min(t/2, k7), (K is any positive constant) and
e² 1 B2 S 16(G+&Cyz- Under the Assumption A.I A.4 and bounded augmented gradient, the augmented gradient generated using DAG-Adam has the following bound
1
+ - -1x
1)x S =0( -0(1)(1)))) +
(109)
T
TT
where C is the minimum value of the augmented loss function (706).
Proof. To shorten the notation, we denote the stochastic augmented gradient as vxā(x) e vf(x!)) + - -
W)x (1)
(110)
Utilizing the L-smooth property and noting that the augmented loss function L has a new Lipschitz constant L' L + y. we have
1(x(1-1)) xC(x(0) + (VL(x(t)) x((()) x(0) +
2 ||x(++1)- - (x
)L(x(0) - (>(Vx((x), +c) (Vf(x(() + - - wix()))
22 (1 (1) + e) (v) + (1 (1- - W)x 11?
+ 2
= -( - > (Vx((x), (V
-V [(x))
+ 7 VxL(x), (( 3
(H()) c) Vx
v) Vx((xx)
+ L
2 (I
v
(111)
where the last equality we add and subtract the inner product with (vi,H( -) The main reason to do this is observing that (1) is correlated with the stochastic gradient V(().
Taking the conditional expectation E, of (+x(++))) more precisely, taking the expectation given all previous recursion information (x(1), vo) 3 we obtain
E (x((x(+11) <C(x(9) >1 =xI]x((())] (1)))) + +7B, (x)())
+e) (H +c) (==(+))))V+((x
+c)
27

---

Under review as a conference paper at ICLR 2022
2 2 E. (H +
(112)
Here we can remove the gradient noise by conditional expectation since the weighted diagonal matrix v (1-1) deterministic given the all information before iteration and the zero gradient- noise assumption A.2.
To bound the term I (H) + xxxxx( we notice that any diagonal element of weighting matrix satisfies that
+ (c+NC+s)
(c
(H + +c) S 1/e, Vi
(113)
Apply the inequality
25
establish that
E -
E. VxIlVx[(xi) (1)+
V (V22H
(114)
where the second inequality is because that v
32 H < ( Next, we bound the cross terms:
vx((x), ((V ( + - (H (1) + V2((x)
E
Vx((x), R. B2H c) (H 1 V vx((x)
< [xxx(( || 32 (t-1)
+ - (H + + + V
(115)
where the last inequality is Holder's inequality. Using the same methods in Zaheer al. 2018 Appendix A), we can show that
-I- B2 E. V (xx)] +0)
|E ((VBBB B +e) -(H( +c) Vxxxxx s
(116)
Plugging back, we establish
E, Vx Vxx(x), ((V (1 + +c) (H + +c) 1) V=(x)))((((
G' VVV
E,
(117)
Substituting 114 and 117 into 112 we obtain
E,C(x(+11)
<((x(!) - 711 V [(x) (
VV VVI- 32G + 2e
22L')
E E
(118)
Next, we bound the weighted norm of stochastic noisy gradient:
E, E.IVv Wi
( ( - = Vx
HHH + E, E. (f(((()
vi(e
1400
< VxL(x)) BHE 144c) + ( v)(x
VxC(x)
+
[.Il vf((x()))
< Vx((()) V D44)
no?
(119)
where the first equality is because of independent and zero-mean gradient noise assumption and the Plugging back and rearranging the terms, we get
first inequality exploited the equation] 25
I1
82G'
LL'
(120)
2c
/3. (1
28

---

Under review as a conference paper at ICLR 2022
(1V1-
B2
>²''
< - -E +
-
62
+
26
no
(121)
To make the coefficient in the left-hand side of inequality positive, require that
7
E 2v
= 7
26
4
2I.
VI G²
1
2
- B2 5 16(G + kC)²
(122)
Hence, we conclude that by taking the telescoping sum:
T-1
E [(] + (T-W)x((0)
- -
(vI- (VI-BaC"
32G
7L'
2 +c)
no?
(123)
7/
62
26
where we use the fact that S [(x) for any x.
Above lemma shows that that local augmented gradient will converge the stationary point within constant factor (o²) for constant learning rate 7, which the same as stated in Theorem of Zaheer et al. 2018). Next, we evaluate that how close the model between each agent.
Lemma 2 (Convergence of consensus value) Under the same condition as Lemmal 7 it holds that
1 T-1
E - x10p= (00)00000000000---00 72
(124)
T
p))
1=
where the p is the second largest eigenvalue of combination matrix W in magnitude, which is strictly less than 1.
Proof: Since W is symmetric doubly stochastic matrix, there is an eigenvalue decomposition form W QAQ", where is some orthogonal matrix. The diagonal matrix A has the value within the range (0, 1] and contains one and only one entry that I due to Assumption A.3. Therefore, we can establish that
[I - W)xl| = - - =1 -A)Q" & f)(x x)1 2 (1 - p) X
-
(125)
where the first equality holds because (/ - W)1 = 0. Now, are read to establish the bound for the consensus error from the augmented gradient:
72
(x(0
x00
[ - -1--
T
(1
UTT
2-2
Vf(x) + - - -V]--x/00
T-1
< [1 2
Vf
(1 - p2
(126)
where the last inequality utilizes the Jensen's inequality = [|++b+<b)]] < 2||a+b|1++21bbb and by setting a ' W)x(") and b vf(x(t).. Using the conclusion from Lemma and bounded gradient assumption, we can immediately establish that
||a
(1) 1
1 +c) (1 - PU?T
(((x00) - L. +
-
(VT-5aG
3₂G
)L')
+
no² +
nG²
(127)
IT
2ca
(2
which gives the desired bound that the consensus error has the order of 0
[I-
29

---

Under review as a conference paper at ICLR 2022
This bounds for the consensus error has several easy interpretable conclusions: To have the smaller consensus error,
either 1) use better connectivity of the graph (i.e., p closer to 0), 2) set a smaller learning rate 7,, or 3) choose a larger v. More accurately, the consensus error is determined by the ratio between 7 and v, which is forwgd to understand since the communication term (I- W)x is scaled by v/y-
With above two lemma, we ready present the convergence theorem.
Proof of theorem [ The first half of statement has already been shown in the lemma T We just to show the convergence for the centralized iterate. To connect the gradient over the centralized iterate I with the stacked gradient over the stacked iterate x, we have
(
JEN
(((((())) + V (1)
(1
Σ
usjae! (0))
JEN.
(f(x(1)) + (1- 1---Wy (W)x
17
7
2
vi(x(()) + -1- - w)x 7
+ VP(x(0) - -V
71
2
(1) + " -1 w)x
(1))
2L + (1) - -x(0 1
(128)
7
n
where step (a) follows the fact that W |wgg] is doubly stochastic matrix and step (b) and (c) are due to Jensen's 's inequality and step(d) utilized the Lipschitz property.
Therefor, combining with the conclusions in lemma and lemma
2
we have
(1
T nT
21 T
vf(x(()) + ?
-(T-W)x(())
Σ
((1) x0012
+
nT
t=1
<4( 4(V333'+ +c) (E(x(0)) - -c-
(VT-T=0''
+ 7TA
0²)
+
262
+c) (
L'
VI - B₂G
YL'
0²
G2
(1- -PP)22
IIT
2
22
11 (1- p} )
21,22
(L(x(T)
L
+VT
F26
7L'
B.' + +c)
+
0²
62
2e
31.22(1B31) +6)
+ (1 pp2
G2
-0( ((xx(0) + 0 0
72
(129)
7T
(1-p2)
(1-
which gives us the desired result.
30

---

Under review as a conference paper at ICLR 2022
E.2 CONVERGENCE PROOF SKETCH FOR THE VARIATION OF DAG-ADAM ALGORITHM
Similar as Adam algorithm also can have another style:
versus adap-thhen-communicate format, our proposed DAG-
g( -WVf(x(()) +
V/ (1 W)x
(130)
7
m (1) =1 + (1)g(()
(131)
(()) =B2v(1-1) + (1 (2)g( @g x ((+1) =x(0) - -H (4) +e) "m (1)
(132)
(133)
Note there are two W in the augmented gradient step, but we only need one round of communication in practice. To see that, we can re-write into this form
(1) g
V 10 " -w(x'0--2 2 ZF((x(0))
(134)
That is, instead of communicating the parameters directly, we communicate the parameters with one SGD step forward.
To establish the convergence analysis of this algorithm, need to find the gradient 134) standard gradient of another augmented loss function. As long as as we find that loss function, the rest of proof will be similar we did in Theorem I Fortunately, it has been stated in Yuan et al. 2021 paper for the momentum algorithms. Here, we give modification for the Adam algorithm.
First, need to further assume that W is a positive definite matrix. It is easy to achieve that since if the original W is not, we use W (I + W)/2 instead. Suppose W has eigenvalue decomposition form W = QT'QQ, where Q is an orthogonal matrix. Then, we define Wa = Q" A"Q, which is also positive definite matrix for any > O. So we have W = W W Now we introduce the algorithm into a transformed domain by multiplying W on the both sides:
W (2) =Wa (0( + - (I W x0)
(135)
W 3 m (0) =w m (1-1) + (1 - ()
(136)
((+1) =f2v(()
32) (9) : g'
(137)
W 1 (++1) - 7 1 (H + e) W
(138)
We further introduce
$ (1)
w (t)
(1) w ig (t) ( - w- m U( & w ddiag(v(())
(139)
The algorithm 130
133 is equivalently to
qdt = f(W + "I W)s
(140)
7
( =8p (t-1) + -1:)g(t (t)
(141)
UO = (()() + (1 (1- b (1)
(142)
((+1) (t( -(( (p
(143)
where the notation (-)(()) means taking the gradient with respect to the whole argument of f and note that W (H) + +) - la = (W:HOW 1 + +c) Remember we can always retrieve
(t) by (t) (1)(t) Now, we are prepared for introduce this new augmented loss function
(w ((W2s)
(144)
27
It is not hard to verify that
(s = W ((W
(T-W)s
(145)
31

---

Under review as a conference paper at ICLR 2022
This means that (14 function Cw(s), There is one difference that U is no longer diagonal matrix. However, recall that we mainly use weighted norm, and the useful inequality (25) can be extended for arbitrary positive matrix
(43) can be viewed Adam algorithm applied this augmented loss
a|هI|| S | |
b||=||1
(146)
where a and are the smallest and largest eigenvalue of matrix A. To see that, suppose A = Q" AQ. have
||Ar||2 = - AQ=1 |AQ=|| & 3
(147)
Therefore, we can establish the similar conclusion as Theorem
I
F HETEROGENEOUS DATA DISTRIBUTION GENERATION
This subsection provides the detailed heterogeneous data generation for CIFAR-10 10 training dataset. To simulate the heterogencous data, the disjoint non-i..d. training data over agents generated through the Dirichlet distribution. For each data class, a categorical Vector
(q1, ... 9n.. where Σ. 1, 9: 2 0, is used to illustrate the training data distribution in network of size n. It is drawn from a symmetric Dirichlet distribution Dir(a)) where a stands for the degree of the data heterogeneity (Lin al.) 2021 Yurochkin et 2019). The training data for a particular class tends to concentrate in single node as a + 0, i.e. becoming more heterogenous while the homogeneous data is formed as a > oo. After the sampling procedure, the data reallocated ensure the same amount of training data in each network node.
Fig. 9 visualizes the heterogeneous data distribution for the CIFAR-IO experiments shown in Table 1 for both network size (4 and 8). The radius of each circle stands for the proportion of the samples for the corresponding data class in the node. Clearly, a 0, the data for each class tends to be allocated in a single node. When - all the data is distributed evenly.
Fig. T0 illlstraates the training loss and validation accuracy curves of different algorithms when a 10. It is observed in the left plot that PAdam and DAG-Adam converges with much lower training losses and higher validation accuracy than the others due to their insensitivity to data heterogeneity.
G MORE EXPERIMENTAL SETTING AND BERT EXPERIMENTAL RESULTS
More Implementation details. We also follow DDP's design to enable computation and commu- nication overlap. Each server contains 8 V100 GPUs in cluster and is treated one node. The inter-node network fabrics are 25 Gbps TCP as default, which is a common distributed training platform setting. The exponential topologies (Assran al. (219 are utilized default.
Training Loss Fig. shows the iteration wise training loss curves of aforementioned algorithms separately.
The effect of using dynamic v. Besides with fine-tuning a proper v constant for DAG-Adam, we tried use dynamic scheduler validate its performance. Compared to the common learning rate scheduler, we use dynamic и schedulers that provide a relatively small v value at first and grow 1 at the end of training. Both linear schedulers and cosine schedulers were examined. Similar as learning rate scheduler, we also use a warm-up strategy, i.e., to fix a static v for a certain iterations then use dynamic schedulers afterwards. We provide some preliminary results in Table Unfortunately. it did not provide better performance compared with the result of using constant V. We leave as future works to design a better strategy select v adaptively without introducing more sypper-prrametet
32

---

Under review as a conference paper at ICLR 2022
Network size
10
Network size a 10
Truck
Truck
Ship
Ship
Horse-
Horse-
Frog
Frog-
Data Class
Data Class
Dog
Dog
Deer
Deer
Cat
Bird
Bird-
Automobile
Automobile
Airplane
Airplane
5
7
Node
Node
Network size 4,
Network size 8, a
Truck
Truck
Ship-
Ship
Horse
Horse
Frog
Frog
Data Class
Data Class
Dog
Dog-
Deer
Deer
Cat
Cat
Bird
Bird
Automobile-
Automobile
Airplane
Airplane
2
5
6
7
Node
Node
Network size 4, 0.1
Network size 8, a 0.1
Truck
Truck
Ship
Ship
Horse
Frog
Frog
Data Class
Data Class
Dog
Dog-
Deer
Deer-
Cat
Bird
Bird
Automabile
Automobile
Airplane
Airplane
Node
Node
Figure 9: Heterogeneous data distribution visualization for CIFAR-10 dataset.
33

---

Under review as a conference paper at ICLR 2022
0.9
DAdam
0.8
10a
QG-Dan QG-DAdam
GT DAdam
Train Loss
DAG Adam
0.6
Validation
0.5
PAdam
DAdam
QG-DAdam
0.3
GT-DAdam
0.2
DAG Adam
Epochs
Epochs
Figure 10: Training loss and validation accuracy evolution for CIFAR-IB 10 dataset under heteroge- neous network of size 8 with a 10. Left plot: training loss. Right plot: validation accuracy.
BERT Base (Static Topology)
BERT Base (Dynamic Topology)
PAdam
PAdam
DAdam
DAdam
5
QG-DAdam
QG-DAdam
GT-DAdam
GT-DAdam
Train Loss
DAG-Adamtle-P
Train Loss
DAG-Adam(le-4)
2
1
0
200
400
600
800
1000
1200
1400
0
200
400
600
800
1000
1200 1400
Iterations
Iterations
BERT Large (Static Topology)
BERT Large (Dynamic Topology)
DAdam
DAdam
5
QG-DAdam
QG-DAdam
GT DAdam
GT ST-DAdam
Train Loss
4
DAG-Adami 1-44
Train Loss
DAG-Adam(1e 1e-4)
1
1400
1400
Iterations
Iterations
Figure 11: Convergence results on the BERT fine-tuning (SQuAD) task with different models and topologies.
Table 6: The effect of using dynamic (BERT base with static topology).
SCHEDULER WARM-UP RATIO
EXACT MATCH
LINEAR
0
46.68
58.64
COSINE
0
65.28
75.99
LINEAR
0.2
76.26
84.69
COSINE
0.2
77.97
85.85
LINEAR
0.35
80.26
86.69
COSINE
0.35
80.97
87.85
34


Reviews:
[{"review_id": "fxoLQHWUhzd", "reviewer": "Reviewer_1RX3", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strengths:\nI found this paper very interesting, and have been long awaiting progress on the topic of adaptive decentralized optimization for deep learning. Traditional gossip-based methods performing consensus on the parameters cannot be naively applied to adaptive gradient methods, such as Adam, because of the non-linearity in the gradient update (e.g., dividing by the square-root of the second moment buffer), which breaks traditional proofs and significantly degrades performance in practice compared to centralized learning (e.g., see [a]). This paper is very important and contributes to an emerging literature. In particular, to realize the benefits of decentralized (gossip-based) optimization for deep learning, one must develop strategies suited for adaptive gradient methods, especially since many popular deep learning tasks seem to only work with adaptive methods, such as language models and the new swath of image-based methods relying on Vision Transformer architectures.\n\nThis paper also shows a very good familiarity with related work. Despite my current rating, I strongly support this paper, and thus will focus on the main issues I observed below so that the authors can address them, and hopefully find their paper accepted at the end of this process.\n\nWeaknesses:\n- Proposition 1 is somewhat meaningless… what is relevant here is a lower bound on the squared norm of the sub-optimality of the iterate $x^t_i$ as $t$ goes to infinity. Similarly for Proposition 2.\n- Can you clarify the following: Theorem 1 assumes that not just the gradient is bounded, but that the gradient with an additional consensus penalty is bounded?\n- In Theorem 1, the language indicates that $x^\\star$ is the optimal solution, but note that in the non-convex setting there does not necessarily exist a unique global optimizer.\n- Would be interested in seeing the statistical significance of results (across a few seeds) in Table 1 on CIFAR10.\n- Why does heterogeneity of data distributions have such a large impact on the final validation performance in Table 1? I would expect the heterogeneity to affect the convergence rate, but not the final validation performance.\n- What architecture is used for the Image Classification experiments?\n- I don’t find enough evidence to support the fact that adapt-the-combine is the issue preventing convergence. It is quite bizarre to me that there should be a difference in adapt-then-combine compared to combine-then-adapt, since the two are often trivial re-parameterizations for gossip-based methods. For example, consider your case of the adapt-then-combine structure (section 2.2) equation 8. Let z^{t+1}_j = x^{t}_j - \\gamma \\frac{m^t_j}{\\sqrt{v^t_j} + \\epsilon} and let x^{t+1}_i = \\sum_{j \\in N_i} w_{ij} z^{t+1}_j, then the $z$ variable has the same fixed point iteration as equation (16) in your combine-then-adapt setting. To me it seems that the reason your proposed method seems to resolve the obvious issue of adaptive methods with linear consensus updates is that the consensus update is incorporated into the adaptive momentum buffer (i.e., tracking not just moving average of gradients, but also the consensus constraint), as opposed to swapping the order of adapt-then-combine vs combine-then-adapt. On this note, I would urge you to also take a look at the SlowMo work of [b] which incorporates a slow-moving consensus step into the momentum update of decentralized gossip-based methods.\n- There might be a problem with Figure 1 since none of the methods convergence to the optimal solution in this strongly-convex case. For logistic regression in particular there isn’t an analytic solution for $x^\\star$ so I’m curious how you’re computing it? Moreover, depending on the conditioning, there could be several solutions in the argmax set. I would be interested in seeing the logistic loss plotted instead, and would be particularly interested in seeing the MSE of the variable z (which I mentioned in the bullet above) plotted for the adapt-the-combine methods.\n- With respect to the fixed-point iteration on page 4: the condition $f_i(x) \\neq f_j(x)$ does not necessarily guarantee $H_i \\neq H_j$ unless you make additional assumptions about how f_i and f_j differ. E.g., consider an extreme case where the distribution differences between $D_i$ and $D_j $amount to a constant shift in the expected loss.\n\n[a] Assran et al., Advances in asynchronous parallel and distributed optimization, Proceedings of the IEEE, 2020.\n\n[b] Wang et al., SlowMo: Improving communication-efficient distributed SGD with slow momentum, ICLR, 2019.", "summary_of_the_paper": "This paper proposes a decentralized adaptive method for distributed deep learning, termed DAG-Adam. Convergence results are provided for smooth non-convex objectives under a bounded gradient assumption. Numerical experiments are conducted on Image Classification (CIFAR10, ImageNet-1k) and Language Modelling (fine-tuning pre-trained BERT models on SQuAD).", "summary_of_the_review": "In short, I find the paper very well motivated, the problem is very important, authors show a familiarity with related work, and the method is sufficiently novel.\n\nHowever, I do not find the claims in the paper to be well supported. Specifically, I don’t find enough evidence to support the fact that adapt-then-combine is the issue preventing convergence of previous methods, and that the proposed method resolves this issue by using a combine-then-adapt strategy, especially since:\n- with a simple re-parameterization, the proposed method can actually be written as an adapt-then-combine strategy\n- propositions 1 and 2 showing issues with adapt-then-combine strategies provide upper bounds, but these are completely uninformative since the relevant quantities should provide a lower bound on the sub-optimality of the iterates with these strategies\nIt seems to me that the proposed method actually works because of the fact that consensus steps are incorporated into the first/second-order momentum buffers, not because the order of adapt/combine is flipped.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "RS1QF62ZjMk", "reviewer": "Reviewer_XYfg", "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": "Pros:\n1. The motivation is clear. It shows why existing methods do not converge to the stationary point. \n\n2. The extensive experiments can support the superiority of this new method. \n\nCons:\n\n1. The novelty is not significant. It is an extension of (Yuan et al., 2016) to the adaptive gradient. \n\n2. This method can only converge to the neighborhood of the stationary point. However, existing methods can converge to the stationary point.\n\n3. $\\beta_2$ is lower bounded. It is not very reasonable. $\\epsilon$ should be very small. Then, this lower bound is very large. \nIt conflicts with the common practice that $\\beta_2=0.1$ or $\\beta_2=0.01$. Thus, this convergence rate is problematic. \n\n4. How is $\\beta_1$? Is there any constraint for $\\beta_1$?\n\n5. Which value is used for $\\beta_2$ in the experiment?\n\n5. Which value is used for $\\epsilon$ in the experiment? Typically, $\\epsilon$ should be very small, e.g., $1e-7$. According to Theorem 1, $v$ should be smaller than $\\epsilon$. But it looks $v$ is large in the experiment. Thus, I don't think the hyperparameters in Theorem 1 are reasonable. \n ", "summary_of_the_paper": "This paper developed a new decentralized adaptive gradient descent method to address the data heterogeneity problem. The motivation is clear and the experimental results show improvement over existing methods. However, the theoretical analysis is not  solid. ", "summary_of_the_review": "The problem studied is interesting. But the method is not novel and the theoretical analysis is not solid. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "2wBHIQ7np2s", "reviewer": "Reviewer_i1gD", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "In this paper authors propose to change the order of adaptation and communication in contrast with D-Adam. More precisely, First, in Section $2$, authors consider heterogeneous data as an input of D-Adam algorithm. They show that algorithm can diverge, moreover, under some additional assumptions it is proven to diverge. Another version of distributed Adam QG-DAdam uses another strategy - adapt-then-communicate. This algorithm also cannot converge to the optimum with heterogeneous input. Finally, they discussed the loss of efficiency of recent GT-DAdam in the same setup.\nThese arguments motivates authors to design the algorithm with communicate-then-adapt. This algorithm is based on the augmented gradient update that allows to interpret it as standard SGD algorithm with the same proof techniques. \n\nIn Theorem $1$, authors present the theoretical result for their algorithm that converges: with the constant learning rate the augmented gradient converges to 0; with $\\gamma = 1/\\sqrt{T}$ the global average of iterates converges to the stationary point.\n\nFinally, in the experiments authors compare their algorithm with different modifications of DAdam (that diverge) and Distributed SGD and shows that in practice their algorithm also makes sence. \n", "summary_of_the_paper": "In this paper, authors propose the novel modification of Distributed Adam Algorithm that allows heterogeneous data.", "summary_of_the_review": "I want to thank authors for their work. The heterogeneous input is very important and I think that the adaptation of Adaptive Distributed Adam to it is an important step. \nThe only thing I am curios is the following: how do authors propose to calculate the global average and how long will it take in the end of the algorithm to calculate it? \nFurthermore, I think that this result can be extended to the case when instead of weighted update with neighbors we select every neighbor with some probability and communicate only among them. This can save a lot of communication cost and make an algorithm even faster.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "1yqpuiuAcZM", "reviewer": "Reviewer_RKoY", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "On one hand, I think the idea of DAG-Adam looks interesting, as it requires no additional computation -- just a reordering on the adapting and communication, the algorithm is guaranteed to converge to the exact solution on strongly convex problems. However, in terms of the correctness and insights, I have three main concerns:\n\n- Both proposition 1 and 2 are shown in terms of the $O(\\cdot)$, which does not really substantiate the claim \"DAdam cannot converge to $x^*$\" since 1) $a=O(\\cdot)$ means $a\\leq C\\cdot$ for some constant $C$, but $a$ can be arbitrarily small; 2) With no lower bound, it's hard to argue a $O(\\cdot)$ is tight, so it's possible that the extra term $G^2/\\epsilon^2$ is incurred by a loose analysis. I think the only way to substantiate the claim is to derive a lower bound.\n\n- The idea of DAG-Adam, different from the DSGD which directly follows from the update rule, requires an additional hyperparameter $\\nu$. This essentially seems to reduce the mixing time of the original communication matrix $W$ -- which is straightforward to verify by Equation (13). This may be unfair in the comparison to other algorithms -- it is possible that DAdam can perform equally good if the mixing matrix there is also tuned by $\\nu$. So I think more illustration is need there, especially in the experiments.\n\n- The paper provides empirical studies on multiple tasks, including image classification and BERT finetuning. However, it's not clear to me how these results interact with the main theorem. As these are non-convex, and there is no $x^*$ anymore, it's unclear whether these improvement comes from the strategy of \"Communicate Then Adapt\", or just the fact that gradient tracker is used/mixing matrix is tuned. On a side note, I recommend the authors to include std for each table, as the results are pretty close.", "summary_of_the_paper": "This paper proposes a new variant to decentralized Adam with a strategy called Communicate Then Adapt. The paper provides analysis and toy example to illustrate why a traditional Adam would fail to converge to the exact solution, and provide experiments on CV/NLP tasks to substantiate the theory.", "summary_of_the_review": "Please refer to the main review. I'd be happy to increase my score if these concerns are properly addressed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a ''communicate-then-adapt'' framework for decentralized optimization, with both theoretical and empirical analysis. The reviewers' main concern is the comparison in theory with prior methods like the GT-DAdam. The convergence to a stationary point of GT-DAdam seems to be faster than the proposed method in the important non-convex optimization. The reviewers are not convinced by the strong claim that ''communicate-then-adapt'' is better than ''adapt-then-communicate'' as such ''adapt-then-communicate'' method can also achieve same or better rates, possibly with less hyper-parameter tuning. I would suggest the authors to make more proper comparison with related methods.
Decision: Reject