Year: 2021

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 data heterogeneity, and hence deviate their limiting points from the stationary solution. To overcome this limitation, we propose an effective decentralized adaptive method with a communicate-thenadapt structure, in which each node conducts the adaptive step after finishing the neighborhood communications. The new method is theoretically guaranteed to converge to the stationary solution in the non-convex scenario. Experimental results on a variety of CV/NLP tasks show that the proposed algorithm has a clear superiority to other existing decentralized adaptive methods.

heading: 1 INTRODUCTION
text: Decentralized SGD (Lopes & Sayed, 2008; Nedic & Ozdaglar, 2009; Chen & Sayed, 2012; Lian et 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 convergence. Inspired by the well-documented success of adaptive methods such as AdaGrad (Duchi et al., 2011a), Adam (Kingma & Ba, 2014) and AMSGrad (Reddi et al., 2019), several decentralized adaptive methods (Nazari et al., 2019; Lin et al., 2021) have been proposed to accelerate decentralized 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.e., global optimal 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. 3) that DAdam (Nazari et al., 2019) and QG-DAdam (Lin et al., 2021) do not converge to the global optimal solution.
This paper studies this situation in detail. We rigorously uncover the reason why DAdam and QGDAdam 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 adapt-then/while-communicate structure: it 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-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 component to guarantee the effectiveness of the communicate-then-adapt structure is the utilization of the
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 converge 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 on a variety of computer vision and natural language processing tasks show that DAG-Adam outperforms various existing state-of-the-art decentralized adaptive baselines under different network and data configurations. Furthermore, the performance of our proposed algorithm is persistently competitive to the centralized counterpart.
Related work on decentralized optimization and deep training. Decentralized optimization was extensively studied in the control and signal processing community. The first decentralized algorithms on general optimization problems include decentralized gradient descent (Nedic & Ozdaglar, 2009), diffusion (Lopes & Sayed, 2008; Chen & Sayed, 2012; Sayed, 2014), and dual averaging (Duchi et al., 2011b). 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 et 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 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 ∼ 2× training time speedup without severe performance degradation. Techniques such as quantization/compression (Alistarh et al., 2017; Bernstein et al., 2018; Koloskova et al., 2019a;b; Tang et al., 2019; Liu et al., 2020), periodic updates (Stich, 2019; Koloskova et al., 2020; Yu et al., 2019), and lazy communication (Chen et al., 2018a; Liu et al., 2019b) were also integrated into decentralized SGD to 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 to run a 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-incurred bias in decentralized momentum SGD. All these methods are not with adaptive strategies to scale gradients.
Related work on adaptive gradient method. Adaptive gradient methods, with AdaGrad (Duchi et al., 2011a) and Adam (Kingma & Ba, 2014) as two representatives, have shown strong performance 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 convergence issue: it may not converge to the desired solution with a fixed mini-batch size (Reddi et al., 2019; Zaheer et al., 2018). Many algorithms have been proposed to resolve this issue. AMSGrad (Reddi et al., 2019) preserves the long-term memory of past gradients to improve convergence, and (Zaheer et al., 2018) suggests the usage of increasing mini-batch sizes in convergence guarantees. (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 et al., 2019a) and AdamW (Loshchilov & Hutter, 2018) can significantly improve Adam performance.
The exploration in decentralized adaptive methods are rather limited. DAdam (Nazari et al., 2019) is the first consensus-based adaptive methods for distributed optimization to our knowledge. (Lin et al., 2021) proposes QG-DAdam, which utilizes quasi-global momentum to locally approximates the globally descent direction. A recent work (Chen et al., 2021a) proposes a 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 unstable convergence or heavy communications. We leave more discussion on their limitations in Sec. 2. Adaptive gradient methods have also been extended to the federated learning setting in which multiple 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 et al., 2019; Reddi et al., 2020).

heading: 2 ADAPT-THEN/WHILE-COMMUNICATE STRUCTURE AND ITS LIMITATION
text: Problem. Suppose n computing nodes cooperate to solve the distributed optimization problem:
min x∈Rd
f(x) = 1
n n∑ i=1 fi(x), where fi(x) := Eξi∼DiF (x; ξi) (1)
In the above problem, fi(x) is local to node i, and random variable ξi denotes the local data that follows distribution Di. We do not assume each distribution Di 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 j to node i, as follows:
wij { > 0 if node j is connected to i, or i = j; = 0 otherwise.
(2)
Ni := {j|wij > 0} is defined as the set of neighbors of node i which also includes node i itself and the weight matrix W := [wij ]ni,j=1 ∈ Rn×n 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: x+i ← ∑ j∈Ni wijxj . (3)
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) isL-smooth, i.e., ‖∇fi(x)−∇fi(y)‖ ≤ L‖x−y‖ for any x, y ∈ Rd. A.2 [GRADIENT NOISE] The random sample ξ(t)i is independent of each other for any k and i. We also assume E[∇F (x; ξi)] = ∇fi(x) and E‖∇F (x; ξi)−∇fi(x)‖2 ≤ σ2. A.3 [WEIGHT MATRIX] The weight matrix W is symmetric and doubly-stochastic, i.e. W1 = 1 and 1TW = 1T , where 1 is an all-ones vector. Further, we assume ‖W − 1n11
T ‖2 ≤ ρ ∈ (0, 1). A.4 [BOUNDED GRADIENT] The loss function F has bounded gradient, i.e., the maximum norm ‖∇F (x; ξi)‖∞ ≤ G for all x and ξi, and i ∈ [n]. Notation. Given a constant n, we let [n] := {1, · · · , n}. Given a vector x ∈ Rd, we let diag(x) = diag{x1, · · · , xd} ∈ Rd×d be a diagonal matrix. Given two vectors x ∈ Rd and y ∈ Rd, we let x y be the element-wise product between x and y.

heading: 2.1 THE ADAPT-WHILE-COMMUNICATE STRUCTURE AND ITS LIMITATION
text: Adapt-While-Communicate Structure. Algorithm 2 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
x (t+1) i = communicate︷ ︸︸ ︷∑ j∈Ni wijx (t) j −
adapt︷ ︸︸ ︷ γ m
(t) i√
v̂ (t) i +
, ∀ i ∈ [n]. (4)
wherem(t)i is the momentum, v̂ (t) i is an estimate of∇F (x (t) i ; ξ (t) i ) ∇F (x (t) i ; ξ (t) i ), and is a small positive constant. Their updates can be referred to Algorithm 2. In recursion (4), it is observed that node i 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 as adapt-while-communicate.
Fixed point condition. Now we examine the fixed point achieved by DAdam and verify whether it satisfies the optimal condition to problem (1). To this end, we let x(t)i → x∞i as t → ∞ for i ∈ [n]. To remove the the influence of gradient noise, we assume each node i can access the fullbatch gradient ∇fi(x). If we define Hi := diag( √ ∇fi(x∞i ) ∇fi(x∞i ) ) to be a diagonal matrix associated with node i, the fixed point condition for DAdam is (see derivation in Appendix B.2):
x∞i = ∑ j∈Ni wijx ∞ j − γ(Hi + I)−1∇fi(x∞i ), ∀ i ∈ [n]. (5)
=⇒ 1 n n∑ i=1 (Hi + I) −1∇fi(x∞) = 0 (if x∞1 = · · · = x∞n = x∞ in the limit) (6)
Fixed point in DAdam is deviated from the desired solution. In the data-heterogeneous scenario where data sample ξi follows different distribution Di, it holds that fi(x) 6= fj(x). If we further assume ∇fi(x) 6= ∇fj(x), it follows that Hi 6= Hj , for any i 6= 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., 1n ∑n i=1∇fi(x∞) = 0. This implies the fixed point of DAdam is not the stationary solution to problem (1). In particular, the following proposition derives the distance between the DAdam fixed point and global optimal solution to problem (1) when the cost function is strongly-convex (Proof is in Appendix B.3).
Proposition 1 Under Assumptions A.1, A.3 and A.4, if each fi(x) is further assumed to be µstrongly-convex, and the full-batch gradient ∇fi(x) is accessed per iteration, then DAdam (Algorithm 2) cannot converge to x?, i.e., the global solution to problem (1). In particular, the distance between DAdam limiting point and x? can be characterized as follows:
lim t→∞ n∑ i=1 ‖x(t)i − x ?‖2 = O ( γ2G2 (1− ρ)2 2 +B2 )
(7)
where B := ‖ 1n ∑n i=1(Hi + I) −1∇fi(x∞i ) − 1n ∑n i=1∇fi(x∞i )‖ 6= 0 is a constant bias term. Furthermore, the B2 term in (7) is necessary and cannot be removed by an improved analysis; there exists strongly convex and smooth functions fi(x) such that limt→∞ ∑n i=1 ‖x (t) i − x?‖2 = Ω(B2).
It is observed in Proposition 1 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 B2 is caused by the adapt-while-communicate structure in DAdam. It is worth noting that a recent work (Chen et al., 2021a) has pointed out that DAdam cannot converge to the stationary solution by constructing a counter-example. However, (Chen et al., 2021a) does not clarify the reason why DAdam fails to converge to the stationary solution, and how far it can be from the desired solution.

heading: 2.2 THE ADAPT-THEN-COMMUNICATE STRUCTURE AND ITS LIMITATION
text: Adapt-Then-Communicate Structure. Algorithm 3 in Appendix B lists the recursions for QGDAdam (Lin et al., 2021). The critical step, which is highlighted in Algorithm 3, is as follows
x (t+1) i = ∑ j∈Ni wij ( x (t) j − γ m (t) j√ v (t) j + ) (8)
It is observed that node i in the above recursion first conducts the adaptive step, and then it communicates with neighbors. We call the structure utilized in QG-DAdam as adapt-then-communicate.
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):
x∞i = ∑ j∈Ni wij ( x∞j − γβ1( √ β2Hj + I) −1∇fj(x∞j ) ) , ∀ i ∈ [n]. (9)
=⇒ 1 n n∑ i=1 ( √ β2Hi + I) −1∇fi(x∞) = 0 (if x∞1 = · · · = x∞n = x∞ in the limit) (10)
where β1, β2 ∈ (0, 1) are momentum parameters listed in 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):
Proposition 2 Under the same conditions as in Proposition 1, the distance between QG-DAdam fixed point and the global solution x? can be characterized as follows:
lim t→∞ n∑ i=1 ‖x(t)i − x ?‖2 = O ( γ2G2 (1− ρ)2 2 +B2 )
(11)
where B := ‖ 1n ∑n i=1( √ 1− β2Hi + I)−1∇fi(x∞i )− 1n ∑n i=1∇fi(x∞i )‖ 6= 0 is a constant bias. Furthermore, the B2 term in (7) is necessary and cannot be removed by an improved analysis; there exists strongly convex and smooth functions fi(x) such that limt→∞ ∑n i=1 ‖x (t) i − x?‖2 = Ω(B2).
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 γ → 0.

heading: 2.3 GT-DADAM: A DECENTRALIZED ADAPTIVE METHOD BASED ON GRADIENT TRACKING
text: It is observed from the fixed-point condition (6) that DAdam cannot converge to the stationary solution due to the discrepancy betweenHi’s. A recent work (Chen et al., 2021a) proposes a gradient tracking based DAdam that enables each local differentHi to converge to H̄ = 1n ∑n i=1Hi in theory,
and therefore, its limiting fixed point satisfies 1n ∑n i=1∇fi(x∞) = 0, the optimality condition to problem (1). GT-DAdam also utilizes the adapt-while-communicate structure. While it can converge to the stationary solution to problem (1) as learning rate γ → 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.1 in Sec. 3.

heading: 3 DECENTRALIZED AUGMENTED GRADIENT ADAM
text: Now that we understand that the adapt-while/then-communicate 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 can overcome the limitation of the adapt-while/then-communicate structure.
Decentralized SGD interprets as standard SGD. Without loss of generality, we assume each node i can access the accurate gradient ∇fi(x) in decentralized SGD recursions. In this scenario, decentralized SGD, according to (Yuan et al., 2016), can be written as
x (t+1) i = ∑ j∈Ni wijx (t) j − γ∇fi(x (t) i ) (12)
= x (t) i − γ ( ∇fi(x(t)i ) + 1
γ (x
(t) i − ∑ j∈Ni
wijx (t) j )︸ ︷︷ ︸
augmented gradient
) , ∀ i ∈ [n]. (13)
In other words, decentralized SGD (12) can be regarded as a standard SGD recursion (13) to solve
min {xi}ni=1 L({xi}ni=1) := n∑ i=1 fi(xi) + 1 2γ ( n∑ i=1 ‖xi‖2 − n∑ i=1 n∑ j=1 wijxixj ) . (14)
We call above as an augmented loss function, which is an approximate penalty problem to the target problem (1). The term ∑n i=1 ‖xi‖2− ∑ i,j wijxixj is convex when the weight matrix W = [wij ] is symmetric and doubly-stochastic, and it equals 0 if x1 = · · · = xn. Apparently, it is a regularization term that promotes consensus among all nodes.
Decentralized Augmented Gradient Adam (DAG-Adam). Inspired by the fact that decentralized SGD can be interpreted as a standard SGD with an augmented gradient (13), we can easily integrate the augmented gradient to the standard Adam method (Kingma & Ba, 2014). Decentralized Augmented Gradient Adam, or DAG-Adam for short is listed in Algorithm 1. It is observed that all communications occur when the stochastic augmented gradient is computed (see the highlighted part in Algorithm 1). After that, each node i will conduct an adaptive step, which is untangled with communication. We call the structure utilized in DAG-Adam as communicate-then-adapt. This adjustment of the algorithm structure is crucial. The stochastic gradient that used to compute m(t)i and
Algorithm 1 DAG-Adam
Initialize x(0)i arbitrarily; let β1, β2,∈ [0, 1); let m (0) i = v (0) i = 0; set γ, ν properly; For t = 0, 1, 2, ..., T − 1, every node i do in parallel
Sample ĝ(t)i = ∇F (x (t) i ; ξ (t) i ) +
ν
γ
( x (t) i − ∑ j∈Ni wijx (t) j ) . stochastic augmented gradient;
m (t) i = β1m (t−1) i + (1− β1) ĝ (t) i ;
v (t) i = β2v (t−1) i + (1− β2) ĝ (t) i ĝ (t) i ;
x (t+1) i = x (t) i − γ
m (t) i√
v (t) i +
. adaptive step;
v (t) i have incorporated the neighbor’s information, which will correct the deviation in fixed point that introduced by different vi (and Hi).
Learning curves (logarithmic scale)
Note that a parameter ν > 0 is added to the adjust the priority to gradient descent, or to promote consensus. Empirically, 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 ν in Appendix D 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 as the augmented gradient and the communicate-then-adapt structure can be extended to AMSGrad or other adaptive gradient methods.
Fixed point condition. The stochastic augmented gradient and communicate-then-adapt structure utilized in DAG-
Adam can remove the influence of the discrepancy in v∞i and hence Hi. Following the settings and arguments in Sec. 2.1, we can derive the fixed point condition for DAG-Adam as follows (see the derivation in Appendix C):
∇fi(x∞i ) + ν
γ (x∞i − ∑ j∈Ni wijx ∞ j ) = 0, ∀ i ∈ [n]. (15)
=⇒ 1 n n∑ i=1 ∇fi(x∞) = 0 (if x∞1 = · · · = x∞n = x∞ in the limit) (16)
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 (Yuan et al., 2016). Relation (16) 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 x? for the strongly-convex scenario.
Proposition 3 Under the same conditions as in Proposition 1, the distance between DAG-Adam fixed point and x? can be characterized as follows:
lim k→∞ n∑ i=1 ‖x(t)i − x ?‖2 = O ( γ2G2 (1− ρ)2ν2 ) (17)
It is observed in (17) that the distance is on the order of O(γ2). Apparently, DAG-Adam will converge to the global optimal solution when γ → 0. Moreover, DAG-Adam has the same communication overhead as in DAdam, and it is more communication-efficient than GT-DAdam. Proposition 3 also implies that DAG-Adam has the same limiting bias as decentralized SGD when ν = 1.
Limiting point justification. We validate the limiting point analysis for DAdam, QG-DAdam, GTDAdam, and DAG-Adam on the full-batch logistic regression problem. Table 5 in Appendix C.3 lists the results we establish in Propositions 1 – 4. When ν = 1 in the DAG-DAdam method, which is a 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
DAdam, GT-DAdam, QG-DAdam, and DAG-Adam are shown in Fig. 1. The MSE metric in the y-axis denotes 1n ∑n i=1 ‖x (t) i − x?‖2. From the figure, it is observed that the DAG-Adam algorithm can converge as fast as other decentralized adaptive algorithms but to a more accurate limiting point. This limiting point is exactly the same as vanilla decentralized SGD, which is consistent with our claim in the limiting point analysis. More experimental setting and results refer to Appendix C.4.
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.
Theorem 1 Suppose the parameters γ, ν, and β2 satisfy the conditions that γ ≤ −2ν2L , ν < min{ /2, κγ}, (κ is any positive constant) and 1 − β2 ≤ 2
16(G+κC)2 . Under Assumptions A.1 - A.4 and the augmented gradient shown is bounded, the decentralized augmented gradient generated by DAG-Adam algorithm satisfies that
1
T T−1∑ t=0 n∑ i=1 ∥∥∥∇fi(x(t)i ) + νγ (x(t)i − ∑ j∈Ni wijx (t) j ) ∥∥∥2 = O(L({x(0)i }ni=0)− L(x∗) γT ) +O(σ2)
(18) where the augmented loss function L(x) is the one defined in (14), L? is the minimum of the augmented loss. Further, it holds for the globally averaged iterate x̄(t) that
1
T T−1∑ t=0 ‖∇f(x̄(t))‖2 ≤ O (L({x(0)i }ni=0)− L? γT ) +O(σ2) +O ( γ2 (1− ρ)2ν2 ) (19)
where x̄(t) = 1/n ∑n i=1 x (t) i and ρ is the second largest eigenvalue of W in magnitude.
Remark 1 The theorem stated two conclusions. The first one is that the augmented gradient in DAG-Adam will converge to a neighborhood around 0 with constant learning rate γ, and the neighborhood, when T →∞, is on the order of O(σ2). The second one is that DAG-Adam will converge to a neighborhood around the stationary solution in terms of the globally averaged iterate x̄(t). The neighborhood, when learning rate γ = O(1/ √ T ) and T →∞, will be on the order of O(σ2). It is thus observed that DAG-Adam will converge to the exact stationary solution with decaying learning rate and increasing mini-batch sizes, which is consistent with the results of Adam using the standard stochastic gradient in (Zaheer et al., 2018). Remark 2 The non-vanishing termO(σ2) 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 corrected by using AMSGrad rather than Adam in DAG-Adam. When there is no stochastic gradient noise, the augmented gradient will converge to zero. In consequence, the v(t)i will converge to zero over all agents as well.

heading: 4 EXPERIMENTS
text: 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 PyTorch’s native Distributed Data Parallel (DDP) module. For the implementation of decentralized methods, we utilize BlueFog. See Appendix F for more details.

heading: 4.1 IMAGE CLASSIFICATION: PERFORMANCE OVER VARIOUS CONFIGURATIONS
text: A series of experiments are carried out with CIFAR-10 (Krizhevsky et al. (2009)) and ImageNet (Deng et al. (2009)) datasets to evaluate the performance of the proposed DAG-Adam on both homogeneous and heterogeneous dataset over different sizes of network. We utilize ResNet-20 on CIFAR-10 and ResNet-50 on ImageNet (He et al., 2016). Training configuration. All methods are trained using 90 epochs with mini-batch of size 32 in each computing node. PAdam uses a 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 divergence1. During the training procedure,
1We examine QG-DAdam based on our own implementation of the algorithm listed in the original paper.
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 as 5× 10−5. We also compared the results of the proposed DAG-Adam with various ν choices. Heterogenerous data configuration. To simulate the heterogenerous data, the disjoint non-i.i.d. training data over agents are generated through Dirichlet distribution Dir(α), 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 α→∞. See Appendix F for more details. Performance comparison. Table 1 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 ν, the proposed method consistently outperforms all other methods under comparison, including the centralized optimization method PAdam, no matter what the data distribution is given. The left and middle figures in Fig. 2 shows how the test loss and test accuracy evolves in a heterogeneous data distribution with α = 10. DAG-Adam (with ν = 1e−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 it eventually caught up when the algorithm converged. The right figure in Fig. 2 plots the consensus error ∑ i ‖xi − x̄‖, which validates that the consensus error in Theorem 1 is proportional to the choice of ν.
Sensitivity on ν constant. As shown in Table 1, the final classification performance depends on the choice of constant ν in DAG-Adam. To better understand how ν affects the DAG-Adam performance, we performed a corresponding ablation study with varying heterogeneity degree α as shown
in Fig. 3. For varying heterogeneity degree α, the constant ν that achieving best performance lies in the range of [1e−2, 5e−1] 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 ν, DAG-Adam persistently achieves comparable performance with the centralized method until the node size reaches n = 64. Even under that case, the drop of performance is quite small.
ImageNet results. We also validate the performance of our proposed method on a relatively largescale dataset ImageNet. We use PAdam to tune the learning rate (4 × 10−4) and wight decay (1 × 10−4) 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 × 8 = 64 GPUs) and train total 100 epochs with a cosine decay scheduler. Our proposed method reaches top-1 accuracy 75.96% which is slightly better than PAdam.

heading: 4.2 LANGUAGE MODELING: PERFORMANCE OVER DIFFERENT TASKS
text: BERT (Devlin et al. (2018)) is a widely used pre-training language representation model for NLP tasks. We fine-tuned pretrained BERT models (Base/Large: 110/330M parameters) on the SQuAD (Rajpurkar et al. (2016)) dataset. All experiments are based on NVIDIA BERT2 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 hyperparameter ν, our proposed method reached best performance in both metrics.

heading: 5 CONCLUSION AND FUTURE WORKS
text: In this paper, we identified the limitation of adapt-while/then-communicate structure utilized in existing adaptive gradient methods: the limiting discrepancy in the squared local gradient term (i.e., v∞i ) can deviate the limiting point from the desired stationary point. To fix this issue, we proposed a novel DAG-Adam algorithm that is built upon the communicate-then-adapt structure instead. DAGAdam 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 baselines. However, it is also observed in these experiments that DAG-Adam is highly-sensitive to the hyper-parameter ν. How to tune ν automatically during the training stage is a crucial topic of the future works.
2https://github.com/NVIDIA/DeepLearningExamples/tree/master/PyTorch/LanguageModeling/BERT

heading: A NOTATIONS AND PRELIMINARIES
text: Notations. We introduce several notations as follows:
• x ,  x1 x2 ... xn  ∈ Rnd×1, m ,  m1 m2 ... mn  ∈ Rnd×1, v ,  v1 v2 ... vn  ∈ Rnd×1.
• ∇f̂(x) ,  ∇F1(x1; ξ1) ∇F2(x2; ξ2)
... ∇Fn(xn; ξn)  ∈ Rnd×1. • W = [wij ] ∈ Rn×n.
• W ,W ⊗ Id ∈ Rnd×nd, where ⊗ means the Kronecker product. • 1n = col{1, 1, . . . , 1} ∈ Rn. • x̄ = ( 1n1n1 T n ⊗ Id)x ∈ Rnd×1.
• Given a vector x ∈ Rd, we let diag(x) = diag{x1, · · · , xd} ∈ Rd×d be a diagonal matrix. • Given a positive definite matrix A, we define the weighted normal ‖x‖2A = xTAx, ‖x‖ as
vector `2 norm and ‖A‖ as matrix `2 norm.
Algorithm reformulation. With the above notation, we rewrite DAG-Adam in Algorithm 1 into the following stacked vector form:
g(t) =∇f̂(x(t)) + ν γ (I −W)x(t) (20)
m(t) =β1m (t−1) + (1− β1)g(t) (21)
v(t) =β2v (t−1) + (1− β2)g(t) g(t) (22)
x(t+1) =x(t) − γ(H(t) + I)−1m(t) (23)
where H(t) is the diagonal matrix defined as H(t) = Diag( √ v(t)).
Smoothness. Since each fi(x) is assumed to be L-smooth in Assumption A.1, it holds that f(x) = 1 n ∑n i=1 fi(x) is also L-smooth. As a result, the following inequality holds for any x,y ∈ Rd:
f(x)− f(y)− L 2 ‖x− y‖2 ≤ 〈∇f(y),x− y〉 (24)
Algorithm 2 DAdam (Nazari et al., 2019)
Initialize x(0)i arbitrarily; let β1, β2, β3 ∈ (0, 1); let m (0) i = v (0) i = v̂ (0) i = 0; set γ properly; For t = 0, 1, 2, ..., T − 1, every node i do Sample g(t)i = ∇F (x (t) i ; ξ (t) i );
m (t) i = β1m (t−1) i + (1− β1) g (t) i ;
v (t) i = β2v (t−1) i + (1− β2) g (t) i g (t) i ; v̂ (t) i = β3v̂ (t−1) i + (1− β3) max{v̂ (t−1) i , v (t) i };
x (t+1) i = ∑ j∈Ni wijx (t) j − γ m (t) i√
v̂ (t) i +
;
Weighted norm inequality. In this paper, the weighted norm ‖x‖2A only considers the scenario in which A is a diagonal matrix. Suppose the diagonal elements in the diagonal matrix A satisfy that 0 < a ≤ [A]i,i ≤ b for all i, one useful inequality is
a‖x‖2A ≤ ‖Ax‖2 ≤ b‖x‖2A (25) The proof is strait-forward:
‖Ax‖2 = xTA2x = (A1/2x)TA(A1/2x) ≤ b(A1/2x)T (A1/2x) = b‖x‖2A (26) We can use the same argument to show a‖x‖TA ≤ ‖Ax‖2 as well. Communication topology. Figure 4 provides a graph example to illustrate the decentralized topology and its communication pattern that is used in all decentralized methods listed in the paper.

heading: B ADAPT-WHILE/THEN-COMMUNICATE STRUCTURE AND ITS LIMITATION

heading: B.1 DADAM AND ADAPT-WHILE-COMMUNICATE STRUCTURE
text: The DAdam algorithm (Nazari et al., 2019) is listed in Algorithm 2.

heading: B.2 FIXED POINT CONDITION FOR DADAM
text: To see the fixed point condition for DAdam, we assume the iterate x(t)i in DAdam converges to some fixed point x∞i as k →∞ for any i ∈ [n]. In order to remove the influence of the gradient noise, we let g(t)i be the full-batch gradient∇fi(x (t) i ) = E[∇F (x (t) i ; ξi)] for any i ∈ [n]. Under this setting, it is easy to verify that m∞i = ∇fi(x∞i ), and v∞i = v̂∞i = ∇fi(x∞i ) ∇fi(x∞i ) (27)
If we define Hi := diag( √ ∇fi(x∞i ) ∇fi(x∞i ) ) to be a positive diagonal matrix, then the highlighted step in DAdam will become (when t→∞)
x∞i = ∑ j∈Ni wijx ∞ j − γ(Hi + I)−1∇fi(x∞i ), ∀ i ∈ [n]. (28)
which is the fixed-point condition listed in (5). If we further let x̄∞ := 1n ∑n i=1 x ∞ i , the following relation can be achieved by (28) and Assumption A.3:
x̄∞ = x̄∞ − γ n n∑ i=1 (Hi + I) −1∇fi(x∞i )
=⇒ 1 n n∑ i=1 (Hi + I) −1∇fi(x∞i ) = 0
=⇒ 1 n n∑ i=1 (Hi + I) −1∇fi(x∞) = 0 (if x∞1 = · · · = x∞n = x∞ in the limit). (29)
The last relation is the one listed in (6).

heading: B.3 PROOF OF PROPOSITION 1
text: Before we prove Proposition 1, we need to introduce several notations:
• x∞ = col{x∞1 , · · · , x∞n } ∈ Rnd • x̄∞ = col{x̄∞, · · · , x̄∞} ∈ Rnd where x̄∞ = 1n ∑n i=1 x ∞ i .
• x? = col{x?, · · · , x?} ∈ Rnd where x? is the optimal solution to problem (1) when the cost function is convex
• ∇f(x∞) = col{∇f1(x∞1 ), · · · ,∇fn(x∞n )} ∈ Rnd • (H + I)−1 = diag{(H1 + I)−1, · · · , (Hn + I)−1}
With these notations, we can rewrite the fixed-point condition (28) into a compact manner:
x∞ =Wx∞ − γ(H + I)−1∇f(x∞) (30) To examine ‖x∞ − x?‖, we will evaluate ‖x∞ − x̄∞‖ and ‖x̄∞ − x?‖ respectively. Upper bound of ‖x̄∞ − x?‖. Left-multiplying 1n1 T to both sides of recursion (30), we achieve
1
n n∑ i=1 (Hi + I) −1∇fi(x∞i ) = 0. (31)
With the above fact, we have
‖x̄∞ − x?‖
= ‖x̄∞ − x? − γ ( 1 n n∑ i=1 (Hi + I) −1∇fi(x∞i )− 1 n n∑ i=1 ∇fi(x?) ) ‖
≤ ‖x̄∞ − x? − γ ( 1 n n∑ i=1 ∇fi(x̄∞)− 1 n n∑ i=1 ∇fi(x?) ) ‖
+ γ‖ 1 n n∑ i=1 (Hi + I) −1∇fi(x∞i )− 1 n n∑ i=1 ∇fi(x∞i )‖
+ γ‖ 1 n n∑ i=1 ∇fi(x∞i )− 1 n n∑ i=1 ∇fi(x̄∞)‖
≤ (1− γµ 2 )‖x̄∞ − x?‖+ γB + γL√ n ‖x∞ − x̄∞‖ (32)
where the last inequality holds because each fi(x) is µ-strongly convex and L-smooth, and the definition of constant B as follows:
B := ‖ 1 n n∑ i=1 (Hi + I) −1∇fi(x∞i )− 1 n n∑ i=1 ∇fi(x∞i )‖. (33)
Inequality (32) leads to
√ n‖x̄∞ − x?‖ ≤ 2
√ nB
µ +
2L
µ ‖x∞ − x̄∞‖. (34)
Upper bound of ‖x∞ − x̄∞‖. Subtracting x̄∞ from both sides of (30), we have
(I −W)(x∞ − x̄∞) = −γ(H + I)−1∇f(x∞). (35) With inequality (43) in (Yuan et al., 2021), we have
‖(I −W)(x∞ − x̄∞)‖ ≥ (1− ρ)‖x∞ − x̄∞‖ (36)
With (35) and (36), and noticing ‖(H + I)−1‖ = maxi{‖(Hi + I)−1‖2} ≤ 1 , we achieve
‖x∞ − x̄∞‖ ≤ γ‖∇f(x ∞)‖
(1− ρ) ≤ γG (1− ρ) (37)
where the last inequality holds because of Assumption A.4. Upper bound of limt→∞ 1n ∑n i=1 ‖x (t) i − x?‖2. With (34) and (37), we have
‖x∞ − x?‖ ≤ ‖x∞ − x̄∞‖+ √ n‖x̄∞ − x?‖
(34)
≤ (1 + 2L µ
)‖x∞ − x̄∞‖+ 2 √ nB
µ (37)
≤ (1 + 2L µ ) γG (1− ρ) +
2 √ nB
µ . (38)
If we ignore the influence of µ and L, we finally achieve
lim t→∞
1
n n∑ i=1 ‖x(t)i − x ?‖2 = 1 n ‖x∞ − x?‖2 = O ( γ2G2 (1− ρ)2 2 +B2 ) . (39)
Lower bound of limt→∞ 1n ∑n i=1 ‖x (t) i − x?‖2. Now we show that the terms depending on B2 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 x(t)i generated by DAdam satisfies
lim t→∞
1
n n∑ i=1 ‖x(t)i − x ?‖2 ≥ B2. (40)
To prove the above conclusion, we consider minimizing problem of the form (1) with
fi(x) = 1
2 (x− yi)2, ∀i ∈ [n] (41)
where x, yi ∈ R. Apparently, the solution to problem (1) is given by x? = 1n ∑n i=1 yi. Next we let x∞i be the limiting point of DAdam (Algorithm 2) in node i. With notations in Sec. B.2, we have
∇fi(x∞i ) = x∞i − yi (42) Hi = |∇fi(x∞i )| = |x∞i − yi| (43)
(H + )−1 = diag{(Hi + )−1} ∈ Rn×n (44)
Under the above setting, the limiting point of DAdam (30) reduces to
x∞ = Wx∞ − γ(H + I)−1∇f(x∞) (45)
in which W ∈ Rn×n is the weight matrix. By left-multiplying 1n1 T to both sides, we have
1
n n∑ i=1 ∇fi(x∞i ) |∇fi(x∞i )|+ = 1 n n∑ i=1 x∞i − yi |x∞i − yi|+ = 0. (46)
On the other hand, it is easy to verify that
1
n n∑ i=1 ∇fi(x̄∞) = 1 n n∑ i=1 (x̄∞ − yi) = x̄∞ − 1 n n∑ i=1 yi = x̄ ∞ − x?. (47)
With (46) and (47), we have
‖x̄∞ − x?‖ (47)= ‖ 1 n n∑ i=1 ∇fi(x̄∞)‖
(46) = ‖ 1
n n∑ i=1 ∇fi(x∞i ) |∇fi(x∞i )|+ − 1 n n∑ i=1 ∇fi(x̄∞)‖
= ‖ 1 n n∑ i=1 ∇fi(x∞i ) |∇fi(x∞i )|+ − 1 n n∑ i=1 ∇fi(x∞i ) + 1 n n∑ i=1 ∇fi(x∞i )− 1 n n∑ i=1 ∇fi(x̄∞)‖
Algorithm 3 QG-DAdam (Lin et al., 2021)
Initialize x(0)i arbitrarily; let β1, β2 ∈ (0, 1); let m (0) i = m̂ (0) i = v (0) i = v̂ (0) i = 0; set γ properly; For k = 0, 1, 2, ..., T − 1, every node i do Sample g(t)i = ∇F (x (tk) i ; ξ (t) i );
m (t) i = β1m̂ (t−1) i + (1− β1)g (t) i ;
v (t) i = β2v̂ (t−1) i + (1− β2)g (t) i g (t) i ;
x (t+1) i = ∑ j∈Ni wij ( x (t) j − γ m (t) j√
v (t) j +
) ;
d (t) i = (x (t+1) i − x (t) i )/‖x (t+1) i − x (t) i ‖2;
m̂ (t) i = β1m̂ (t−1) i + (1− β1)d (t) i ;
v̂ (t) i = β2v̂ (t−1) i + (1− β2)d (t) i d (t) i ;
(42) = ‖ 1
n n∑ i=1 ∇fi(x∞i ) |∇fi(x∞i )|+ − 1 n n∑ i=1 ∇fi(x∞i ) + 1 n n∑ i=1 (x∞i − x̄∞)‖
= ‖ 1 n n∑ i=1 ∇fi(x∞i ) |∇fi(x∞i )|+ − 1 n n∑ i=1 ∇fi(x∞i )‖
(43) = ‖ 1
n n∑ i=1 (Hi + I) −1∇fi(x∞i )− 1 n n∑ i=1 ∇fi(x∞i )‖ = B. (48)
Finally, we have
lim t→∞
1
n n∑ i=1 ‖x(t)i − x ?‖2 = 1 n ‖x∞ − x?‖2
= 1
n ‖x∞ − x̄∞ + x̄∞ − x?‖2
(a) =
1 n ‖x∞ − x̄∞‖2 + 1 n ‖x̄∞ − x?‖2
≥ 1 n ‖x̄∞ − x?‖2 = ‖x̄∞ − x?‖2 (48)= B2, (49)
where equality (a) holds because
〈x∞ − x̄∞, x̄∞ − x?〉 = (x∞)T (I − 1 n 11T ) · 1(x̄∞ − x?) = 0. (50)
Inequality (49) implies that the term B2 cannot be removed from bound (39) with any improved analysis for our constructed problem.

heading: B.4 QG-DADAM AND ADAPT-THEN-COMMUNICATE STRUCTURE
text: The QG-DAdam algorithm (Lin et al., 2021) is listed in Algorithm 3.

heading: B.5 FIXED POINT CONDITION FOR QG-DADAM
text: We let x(t)i → x∞i as t→∞ for any i ∈ [n]. We also assume each node i can access the full-batch gradient ∇fi(x) in order to remove the influence of gradient noise. Under such setting, we can verify in QG-DAdam that
d∞i = 0, m̂ ∞ i = 0, v̂ ∞ i = 0 m∞i = (1− β1)∇fi(x∞i ), v∞i = (1− β2)∇fi(x∞i ) ∇fi(x∞i ) (51)
Substituting m∞i and v ∞ i to the highlighted step in QG-DAdam, we can achieve the fixed-point condition as follows x∞i = ∑ j∈Ni wij ( x∞j − γ(1− β1)( √ 1− β2Hj + I)−1∇fj(x∞j ) ) , ∀i ∈ [n]. (52)
where Hi = diag{ √ ∇fi(x∞i ) ∇fi(x∞i )}. If we further let x̄∞ := 1n ∑n i=1 x ∞ i , the following relation can be achieved by (52) and Assumption A.3:
x̄∞ = x̄∞ − γ(1− β1) n n∑ i=1 ( √ 1− β2Hi + I)−1∇fi(x∞i )
=⇒ 1 n n∑ i=1 ( √ 1− β2Hi + I)−1∇fi(x∞i ) = 0
=⇒ 1 n n∑ i=1 ( √ 1− β2Hi + I)−1∇fi(x∞) = 0 (if x∞1 = · · · = x∞n = x∞ in the limit). (53)
The last relation is the one listed in (10).

heading: B.6 PROOF OF PROPOSITION 2
text: The proof of Proposition 2 is similar to that of Proposition 1. With notations defined in Sec. B.3, we can rewrite (52) into the following compact manner:
x∞ =W ( x∞ − γ(1− β1)( √ 1− β2H + I)−1∇f(x∞) ) (54)
Upper bound of ‖x̄∞ − x?‖. Left-multiplying 1n1 T to both sides of recursion (30), we achieve
1
n n∑ i=1 ( √ 1− β2Hi + I)−1∇fi(x∞i ) = 0. (55)
Using a similar argument to that in (32) and (34), we have √ n‖x̄∞ − x?‖ ≤ 2 √ nB
µ +
2L
µ ‖x∞ − x̄∞‖ (56)
in which the constant bias term B is defined as
B := ‖ 1 n n∑ i=1 ( √ 1− β2Hi + I)−1∇fi(x∞i )− 1 n n∑ i=1 ∇fi(x∞i )‖. (57)
Upper bound of ‖x∞ − x̄∞‖. Subtracting x̄∞ from both sides of (54), we have (I −W)(x∞ − x̄∞) = −γ(1− β1)W( √
1− β2H + I)−1∇f(x∞). (58) Using similar arguments as in (36) and (37), and facts that ‖( √ 1− β2H + I)−1‖ =
maxi{‖( √ 1− β2Hi + I)−1‖2} ≤ 1 and ‖W‖ ≤ 1, we have
‖x∞ − x̄∞‖ ≤ γ(1− β1)‖∇f(x ∞)‖
(1− ρ) ≤ γG (1− ρ) . (59)
Upper bound of limt→∞ 1n ∑n i=1 ‖x (t) i − x?‖2. Using similar arguments to those in (38) and (39), we achieve
lim t→∞
1
n n∑ i=1 ‖x(t)i − x ?‖2 = 1 n ‖x∞ − x?‖2 = O ( γ2G2 (1− ρ)2 2 +B2 ) . (60)
Lower bound of limt→∞ 1n ∑n i=1 ‖x (t) i − x?‖2. With the same constructed problem as in (41), we can easily establish
lim t→∞
1
n n∑ i=1 ‖x(t)i − x ?‖2 ≥ B2 (61)
following the arguments in (42) – (50), where B is defined in (57).

heading: B.7 GT-DADAM
text: Fixed-point condition. If we define H̄ = 1n ∑n i=1Hi, the fixed-point condition of GT-DAdam (i.e., Algorithm 2 in (Chen et al., 2021a)) is as follows:
x∞i = ∑ j∈Ni wijx ∞ j − γ(H̄ + I)−1∇fi(x∞i ), ∀i ∈ [n]. (62)
=⇒ x̄∞ = x̄∞ − γ n n∑ i=1 (H̄ + I)−1∇fi(x∞i )
=⇒ 1 n n∑ i=1 ∇fi(x∞) = 0 (If x∞1 = · · · = x∞n = x∞ in the limit) (63)
It is observed that the fixed-point of GT-DAdam satisfies the optimality condition of problem (1).
Proposition 4 Under the same conditions as in Proposition 1, the distance between GT-DAdam fixed point and the global solution x? can be characterized as follows:
lim t→∞ n∑ i=1 ‖x(t)i − x ?‖2 = O ( γ2G2 (1− ρ)2 2 ) (64)
Proof. With notations defined in Sec. B.3, the fixed-point condition in (62) can be rewritten as
x∞ =Wx∞ − γ(H̄ + I)−1∇f(x∞) (65)
where H̄ = diag{H̄, · · · , H̄} ∈ Rnd×nd. Bound of ‖x̄∞ − x?‖. Left-multiplying 1n1 T to both sides of recursion (65), we achieve
1
n n∑ i=1 ∇fi(x∞) = 0. (66)
With the above fact, we have
‖x̄∞ − x?‖ = ‖x̄∞ − x? − γ ( 1 n n∑ i=1 ∇fi(x∞i )− 1 n n∑ i=1 ∇fi(x?) ) ‖
≤ ‖x̄∞ − x? − γ ( 1 n n∑ i=1 ∇fi(x̄∞)− 1 n n∑ i=1 ∇fi(x?) ) ‖
+ γ‖ 1 n n∑ i=1 ∇fi(x∞i )− 1 n n∑ i=1 ∇fi(x̄∞)‖
≤ (1− γµ 2 )‖x̄∞ − x?‖+ γL√ n ‖x∞ − x̄∞‖ (67)
where the last inequality holds since each fi(x) is µ-strongly convex and L-smooth. We thus have
√ n‖x̄∞ − x?‖ ≤ 2L
µ ‖x∞ − x̄∞‖ (68)
Bound of ‖x∞ − x̄∞‖. Subtracting x̄∞ from both sides of (65), we have
(I −W)(x∞ − x̄∞) = −γ(H̄ + I)−1∇f(x∞). (69) With inequality (43) in (Yuan et al., 2021), we have
‖(I −W)(x∞ − x̄∞)‖ ≥ (1− ρ)‖x∞ − x̄∞‖ (70)
With (69) and (70), and noting that ‖(H̄ + I)−1‖2 ≤ 1/ , we achieve
‖x∞ − x̄∞‖ ≤ γ‖∇f(x ∞)‖
(1− ρ) (71)
Proof of Proposition 4. With (68) and (71), we have
‖x∞ − x?‖ ≤ ‖x∞ − x̄∞‖+ √ n‖x̄∞ − x?‖
≤ (1 + 2L µ )‖x∞ − x̄∞‖
≤ (1 + 2L µ ) γ (1− ρ) ‖∇f(x∞)‖. (72)
The above inequality implies that
lim t→∞
1
n n∑ i=1 ‖x(t)i − x ?‖2 = O ( γ2G2 (1− ρ)2 2 ) . (73)
Remark 3 Different from Propositions 1 and 2, it is observed from Proposition 4 that the distance between the GT-DAdam fixed point and the optimal solution will diminish to zero as learning rate γ → 0. However, GT-DAdam will incur two rounds of neighborhood communication per iteration, which is much more expensive than DAdam and QG-DAdam.

heading: C FIXED-POINT CONDITION FOR DAG-ADAM

heading: C.1 FIXED-POINT CONDITION
text: When t→∞, we let x(t)i → x∞i for any i ∈ [n] in DAG-Adam. We further assume each agent can access the real gradient ∇fi(x) instead of the stochastic gradient ∇F (x; ξi). Under this setting, we can verify that
ĝ∞i = ∇fi(x∞i ) + ν
γ (x∞i − ∑ j∈Ni wijx ∞ j ) (74)
and m∞i = ĝ ∞ i , v ∞ i = ĝ ∞ i ĝ∞i . By letting Ĥi = diag{ √ v∞i }, it can be derived from the adptive step in DAG-Adam that
x∞i = x ∞ i − γ(Ĥi + I)−1ĝ∞i , ∀i ∈ [n] (75)
⇐⇒ ∇fi(x∞i ) + ν
γ (x∞i − ∑ j∈Ni wijx ∞ j ) = 0, ∀i ∈ [n] (76)
=⇒ 1 n n∑ i=1 ∇fi(x∞i ) = 0 (77)
⇐⇒ 1 n n∑ i=1 ∇fi(x∞) = 0 (If x∞i = x∞ in the limit) (78)
In other words, DAG-Adam can converge to the stationary solution if x∞1 = · · · = x∞n = x∞ in the limit. Compared to DAdam and QG-DAdam in which the discrepancy between Hi’s has made the limiting fixed point deviate from the desired solution, the communicate-then-adapt structure in DAG-Adam make it immune to the difference between Hi.

heading: C.2 PROOF OF PROPOSITION 3.
text: With notations defined in Sec. B.3, the fixed-point condition in (76) can be rewritten as
∇f(x∞) + ν γ (I −W)x∞ = 0. (79)
Bound of ‖x̄∞ − x?‖. Left-multiplying 1n1 T to both sides of recursion (79), we achieve
1
n n∑ i=1 ∇fi(x∞) = 0. (80)
Using similar arguments to (67), we achieve √ n‖x̄∞ − x?‖ ≤ 2L
µ ‖x∞ − x̄∞‖ (81)
Bound of ‖x∞ − x̄∞‖. Subtracting x̄∞ from both sides of (79), we have
(I −W)(x∞ − x̄∞) = −γ ν ∇f(x∞). (82)
With inequality (43) in (Yuan et al., 2021), we have
‖(I −W)(x∞ − x̄∞)‖ ≥ (1− ρ)‖x∞ − x̄∞‖ (83) With (82) and (83), we achieve
‖x∞ − x̄∞‖ ≤ γ‖∇f(x ∞)‖
(1− ρ)ν (84)
Proof of Proposition 3. With (81) and (84), we have
‖x∞ − x?‖ ≤ ‖x∞ − x̄∞‖+ √ n‖x̄∞ − x?‖
≤ (1 + 2L µ )‖x∞ − x̄∞‖
≤ (1 + 2L µ ) γ (1− ρ)ν ‖∇f(x∞)‖. (85)
The above inequality implies that
lim t→∞
1
n n∑ i=1 ‖x(t)i − x ?‖2 = O ( γ2G2 (1− ρ)2ν2 ) . (86)

heading: C.3 COMPARISON IN LIMITING POINT DISTANCES TO GLOBAL SOLUTION
text: Table 5 lists the results we establish in Propositions 1 – 4. When ν = 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:
DAG-Adam < GT-DAdam < QG-DAdam ≈ DAdam (87) This conclusion matches with the numerical experiment in Fig. 1.

heading: C.4 EXPERIMENT SETTING FOR LOGISTIC REGRESSION (I.E., FIG 1)
text: In this experiment, we consider the binary logistic regression problem:
min x∈Rd
1
n n∑ i=1 fi(x) + λ 2 ‖x‖2 where fi(x) = 1 K K∑ k=1 ln ( 1 + exp(−γi,khTi,kx) ) (88)
where hi,k ∈ Rd is the k-th feature vector at agent i and γi,k ∈ {+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 so that is satifies Assumption A.3. Also, we choose d = 25 as the dimension of feature vector and generate K = 50 data for each agent locally. The corresponding γ is generated through a pre-set random xo vector. We first compute the linear score hTi,kx
o, then determine the γ by the probability based on the sigmoid value. For all algorithms, we choose the constant learning rate γ = 0.01, β1 = 0.9, β2 = 0.99. One exception is that we choose β1 = 0.1 for QG-DAdam algorithm to achieve better convergence performance.
Besides the learning curve we have shown in Fig. 1, we also plots the v(t)i of various algorithms at the last iteration in Fig. 5. To characterize the difference between different agents, we use the box plot to show the difference of v(t)i of each entry among all agents. From the figure, it is clear that the v (t) i in DAG-Adam algorithm is almost zero when the algorithm converged, which is much narrower and lower than others methods.
Fig. 6 provides complementary experimental results to Fig. 1. We added a new algorithm named DAdam-ReParam which reparameterizes DAdam to obtain a communicate-then-adapt structure. In addition, the convergence with both constant and decaying learning rates are depicted in the left and right plot in Fig. 6, respectively. The It is observed that DAdam-ReParam converges closely to DAdam, and both approaches converge to a less accurate solution than DAG-Adam.
D MORE DISCUSSION ON THE HYPER-PARAMETER ν
This section discusses the role of hyper-parameter ν in DAG-Adam, and how it influences the convergence performance. To this end, we first discuss whether ν is needed in the vanilla decentralized SGD (or DSGD for short) algorithm and DAdam. Next, we will study the influence of ν in the more complicated DAG-Adam algorithm.
D.1 INFLUENCE OF ν ON DSGD
Without loss of generality, we consider the DSGD method with a full-batch gradient. In this setting, the augmented gradient of DSGD (13) is given by
x (t+1) i = x (t) i − γ ( ∇fi(x(t)i ) + 1
γ (x
(t) i − ∑ j∈Ni
wijx (t) j )︸ ︷︷ ︸
augmented gradient
) , ∀ i ∈ [n]. (89)
With notations defined in Appendix A and the introduction of the hyper-parameter ν as in DAGAdam, we can rewrite the above recursion into a more compact form
x(t+1) = x(t) − γ ( ∇f(x(t)) + ν
γ (I −W)x(t) ) = ( (1− ν)I + νW )
︸ ︷︷ ︸ :=W̃ x(t) − γ∇f(x(t)) (90)
The above recursion implies that the hyper-parameter ν will replace the original weight matrixW with W̃ , whose eigenvalues are derived as
eigk(W̃) = (1− ν) · 1 + ν · eigk(W) ⇐⇒ 1− eigk(W̃) = ν(1− eigk(W)) (91) where eigk(W) stands for the k-th eigenvalue of matrixW . Equation (91) implies all eigenvalues of W̃ are more closer to value 1 for any ν ∈ [0, 1). Since a larger spectral gap, i.e. 1− λ2(W̃), 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.
We validate the above discussion with deep learning experiments over CIFAR-10 dataset. Fig. 7 illustrates the influence of ν on vanilla DSGD. It is observed that ν = 1 enables DSGD to converge fastest and achieve the best validation accuracy, which is consistent with the above conclusions.
D.2 INFLUENCE OF ν ON DADAM
Since DAdam is an immediate variant of DSGD, we expect the influence of ν on DAdam will be similar to that on DSGD. To validate it, we impose a hyper-parameter ν to DAdam recursion:
g(t) =∇f(x(t)) (92)
m(t) =β1m (t−1) + (1− β1)g(t) (93)
v(t) =β2v (t−1) + (1− β2)(g(t) g(t)) (94)
x(t+1) =((1− ν)I + νW )x(t) − γ(H(t) + I)−1m(t) (95) Fig. 8 illustrates the influence of ν on DAdam. Similar to DSGD, it is observed that DAdam with ν = 1 (i.e., the vanilla DAdam with no introduction of ν) has the best convergence performance.
D.3 INFLUENCE OF ν ON DAG-ADAM
Without loss of generality, we consider DAG-Adam with dimension d = 1. In this scenario, DAGAdam can be rewritten as
g(t) = ∇f(x(t)) + ν γ (I −W )x(t) (96)
m(t) = β1m (t−1) + (1− β1)g(t) (97)
v(t) = β2v (t−1) + (1− β2)(g(t) g(t)) (98)
x(t+1) = x(t) − γ(H(t) + I)−1m(t) (99)
where W ∈ Rn×n is the weight matrix and H(t) = diag{ √ v(t)} ∈ Rn×n is a diagonal matrix. Subtracting (99) by β1 times (99) with one iteration shift, we have
x(t+1) − β1x(t) = x(t) − β1x(t−1) − γ(H(t) + I)−1m(t) + β1γ(H(t−1) + I)−1m(t−1) (100) Rearranging the terms in the above recursion, we obtain
x(t+1) =x(t) − (1− β1)γ(H(t) + )−1g(t) + β1(x(t) − x(t−1))
+ β1
( γ(H(t−1) + )−1 − γ(H(t) + )−1 ) 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(t) = αI , which amounts to the case where all nodes maintain constant v(t)i across i and t 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 v(t)i converges to the same value v for any i ∈ [n].
Substituting H(t) = αI into (101), we have
x(t+1) = x(t) − γ(1− β1) α+ g(t) + β1(x (t) − x(t−1))
= [ (
1− 1− β1 ν(α+ )
) I +
1− β1 ν(α+ )
W︸ ︷︷ ︸ :=W̃DAG
] x(t)− γ(1−β1)
α+ ∇f(x(t)) +β1(x(t)−x(t−1))
(102)
From the expression of W̃DAG, it is observed that the optimal value for ν to minimize the mixing time of the weight matrix is α+ 1−β1 , which is not 1 as in the vanilla DSGD algorithm. In addition, it is worth noting that W̃DAG cannot outperform W in terms of mixing time for any choice of ν.
This trivial example illustrates the necessity to have the hyper-parameter ν in DAG-Adam. The introduction of ν is to compensate the negative influence of the communicate-then-adapt structure in DAG-Adam which incorporates both the gradient and the consensus constraint into the adaptive momentum buffer. The weight matrix W̃DAG can be quite inefficient to aggregate information if no ν exists to speed up partial averaging.
Generalized scenario. Unlike the above trivial scenario, it is very challenging to determine a proper value for ν in the general scenarios. To see it, we ignore the last term in (101) to achieve
x(t+1) ≈ ( I − ν(1− β1)(H(t) + I)−1(I −W ) )︸ ︷︷ ︸ :=W̃DAG x(t) − (1− β1)γ(H(t) + I)−1∇f(x(t))
+ β1(x (t) − x(t−1)) (103)
which is a reasonable approximation to (101) since β2 is typically set as 0.999 and v(t) (and hence H(t)) will not change dramatically. The first term in (103) mixes x(t)i with weight matrix
W̃DAG = (I − ν(1− β1)(H(t) + I)−1)I + ν(1− β1)(H(t) + I)−1W (104)
If we let Λ := ν(1− β1)(H(t) + )−1, it holds that
Λ−1/2W̃DAGΛ 1/2 = I − Λ + Λ1/2WΛ1/2 (105)
The left-hand side of (105) is the similarity transformation of W̃DAG. Hence, the eigenvalues of W̃DAG equal to ones of the right-hand side of (105). Unfortunately, it is difficult to determine the eigenvalues of Λ1/2WΛ1/2, not to mention the optimal value for ν. However, it is obvious that ν = 1 is not necessarily optimal for DAG-Adam. This motivates us to tune ν in experiments to boost the convergence performance of DAG-Adam. In fact, the results in Table 1 (with CIFAR-10 dataset), Table 3 (with ImageNet dataset), and Table 4 (with SQuAD dataset) corroborate that ν = 1 is not the optimal choice for DAG-Adam. How to find the optimal ν automatically is the main direction of our future work.

heading: E CONVERGENCE ANALYSIS

heading: E.1 CONVERGENCE PROOF OF DAG-ADAM
text: As we motivated in the Section 3, we consider the augmented loss function
L(x) = f(x) + ν 2γ ‖x‖2I−W , where f(x) := K∑ k=1 fk(xk) (106)
It is easy to verify that
∇xL(x) =  ∇x1f1(x1) ∇x2f2(x2)
... ∇xKfK(xK) + νγ (I −W)x = ∇f(x) + νγ (I −W)x (107) 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 convergence analysis idea. First, we use the similar proof technique as Zaheer et al. (2018) did for the standard Adam to show the convergence of the decentralized augmented gradient. Next, based on that, we establish the consensus lemma to show that the models between all agents are close. Last,
combining two, we finally arrive the convergence of centralized iterate, ‖∇f(x̄(t))‖ as the common decentralized algorithm theorem stated.
It is common in the proof of adaptive gradient methods, for example Zaheer et al. (2018); Chen et al. (2021a; 2018b); Reddi et al. (2019; 2020), to assume the gradient∇fi(x(t)i ) and/or stochastic gradient ∇Fi(x(t)i ; ξi) have bounded `2 or `∞ norms at all iterations t, i.e., ‖∇fi(x (t) i ))‖ ≤ G and ‖∇Fi(x(t)i ; ξi)‖ ≤ G. Hence, it is nature to see we need the similar bounded gradient assumption on the augmented gradient. However, notice our augmented gradient has a (I −W)x term. So we need to further assume that ‖x(t)‖ ≤ C. This is a 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 g(t) converges to a very small value without any requirement on the boundary on the iterate, as shown in Fig. 5. In this case, we can show that
‖g(t)‖∞ ≤ max i ‖∇f̂i(x(t)i )‖+ ‖
ν γ (I −W)x(t)‖ ≤ G+ ν γ ‖x(t)‖ ≤ G+ κC︸ ︷︷ ︸
,G′
(108)
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., β1 = 0, which is typically referred as RMSprop.
Lemma 1 (Convergence lemma of augmented gradient) Suppose the parameters γ, ν and β2 satisfy the conditions that γ ≤ −2ν2L , ν < min{ /2, κγ}, (κ is any positive constant) and 1 − β2 ≤ 2
16(G+κC)2 . Under the Assumption A.1 - A.4 and bounded augmented gradient, the augmented gradient generated using DAG-Adam has the following bound
1
T T−1∑ t=0 E ‖∇f(x(t)) + ν γ (I −W)x(t)‖2 ≤ O (L(x(0))− L∗ γT ) +O(σ2) (109)
where L∗ is the minimum value of the augmented loss function (106).
Proof. To shorten the notation, we denote the stochastic augmented gradient as
∇xL̂(x) , ∇f̂(x(t)) + ν
γ (I −W)x(t) (110)
Utilizing the L-smooth property and noting that the augmented loss function L has a new Lipschitz constant L′ = L+ νγ , we have
L(x(t+1)) ≤L(x(t)) + 〈∇L(x(t)),x(t+1) − x(t)〉+ L ′
2 ‖x(t+1) − x(t)‖2 ≤L(x(t))− γ 〈 ∇xL(x), (H(t) + )−1 ( ∇f̂(x(t)) + ν
γ (I −W)x(t) )〉 + γ2L′
2 ‖(H(t) + )−1(∇f̂(x(t)) + ν γ (I −W)x(t))‖2
=L(x(t))− γ 〈 ∇xL(x), ( √ β2H (t−1) + )−1∇xL̂(x) 〉
+ γ 〈 ∇xL(x), ( ( √ β2H (t−1) + )−1 − (H(t) + )−1 ) ∇xL̂(x) 〉 + γ2L′
2 ‖(H(t) + )−1∇xL̂(x)‖2 (111)
where the last equality we add and subtract the inner product with ( √ β2H
(t−1) + )−1L̂(x). The main reason to do this is observing that H(t) is correlated with the stochastic gradient∇L̂(x).
Taking the conditional expectation E t of L(x(t+1)), more precisely, taking the expectation given all previous recursion information {x(j),v(j)}tj=1, we obtain
E tL(x(t+1)) ≤L(x(t))− γ‖∇xL(x)‖2(√β2H(t−1)+ )−1 + γE t 〈 ∇xL(x), ( ( √ β2H (t−1) + )−1 − (H(t) + )−1 ) ∇xL̂(x) 〉
+ γ2L′
2 E t‖(H(t) + )−1∇xL̂(x)‖2 (112)
Here we can remove the gradient noise by conditional expectation since the weighted diagonal matrix √ β2H
(t−1) is deterministic given the all information before iteration t and the zero gradientnoise assumption A.2.
To bound the term E t‖(H(t) + )−1∇xL̂(x)‖2, we notice that any diagonal element of weighting matrix satisfies that (
G+ κC + )−1 ≤ [(H(t) + )−1]i,i ≤ 1/ , ∀i (113)
Apply the inequality (25), we establish that
E t‖(H(t) + )−1∇xL̂(x)‖2 ≤ 1 E t‖∇xL̂(x)‖2(H(t)+ )−1
≤1 E t‖∇xL̂(x)‖2(√β2H(t−1)+ )−1 (114)
where the second inequality is because that √ β2H (t−1) ≤ H(t). Next, we bound the cross terms:
E t 〈 ∇xL(x), ( ( √ β2H (t−1) + )−1 − (H(t) + )−1 ) ∇xL̂(x) 〉 = 〈 ∇xL(x),E t ( ( √ β2H (t−1) + )−1 − (H(t) + )−1 ) ∇xL̂(x)
〉 ≤‖∇xL(x)‖∞‖E t ( ( √ β2H (t−1) + )−1 − (H(t) + )−1 ) ∇xL̂(x)‖1 (115)
where the last inequality is Holder’s inequality. Using the same methods as in (Zaheer et al., 2018, Appendix A), we can show that
‖E t ( ( √ β2H (t−1) + )−1 − (H(t) + )−1 ) ∇xL̂(x)‖1 ≤ √ 1− β2
E t‖∇xL̂(x)‖2(√β2H(t−1)+ )−1 (116)
Plugging back, we establish E t 〈 ∇xL(x), ( ( √ β2H (t−1) + )−1 − (H(t) + )−1 ) ∇xL̂(x) 〉 ≤ G ′√1− β2
E t‖∇xL̂(x)‖2(√β2H(t−1)+ )−1 (117)
Substituting (114) and (117) into (112), we obtain
E tL(x(t+1)) ≤L(x(t))− γ‖∇xL(x)‖2(√β2H(t−1)+ )−1
+
( γ √ 1− β2G′
+ γ2L′
2
) E t‖∇xL̂(x)‖2(√β2H(t−1)+ )−1 (118)
Next, we bound the weighted norm of stochastic noisy gradient:
E t‖∇xL̂(x)‖2(√β2H(t−1)+ )−1 =‖∇xL(x)‖ 2 ( √ β2H(t−1)+ )−1 + E t‖∇f(x(t))−∇f̂(x(t))‖2(√β2H(t−1)+ )−1
≤‖∇xL(x)‖2(√β2H(t−1)+ )−1 + 1 E t‖∇f(x(t))−∇f̂(x(t))‖2
=‖∇xL(x)‖2(√β2H(t−1)+ )−1 + 1 n∑ i=1 E t‖∇fi(x(t)i )−∇f̂i(x (t) i )‖ 2
≤‖∇xL(x)‖2(√β2H(t−1)+ )−1 + 1 nσ2 (119)
where the first equality is because of independent and zero-mean gradient noise assumption and the first inequality exploited the equation 25. Plugging back and rearranging the terms, we get
γ ( 1− √ 1− β2G′ − γL ′
2
) E ‖∇L(x(t))‖2(√β2H(t−1)+ )−1 (120)
≤ EL(x(t))− EL(x(t+1)) + ( γ √ 1− β2G′
2 + γ2L′
2 2
) nσ2 (121)
To make the coefficient in the left-hand side of inequality positive, we require that
γL′
2 ≤ 1 4 =⇒ γ ≤ − 2ν
2L√ 1− β2G′
≤ 1
4 =⇒ 1− β2 ≤
2
16(G+ κC)2 (122)
Hence, we conclude that by taking the telescoping sum:
1
T T−1∑ t=0 E ‖∇f(x(t)) + ν γ (I −W)x(t)‖2
≤ 2( √ β2G ′ + ) ( L(x(0))− L∗
γT +
(√ 1− β2G′
2 + γL′
2 2
) nσ2 ) (123)
where we use the fact that L∗ ≤ L(x) for any x. Above lemma shows that that local augmented gradient will converge to the stationary point within the constant factor of O(σ2) for constant learning rate γ, which is the same as stated in Theorem 1 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 Lemma 1, it holds that
1
T T−1∑ t=0 E ‖x(t) − x̄(t)‖2 = O (
γ2
(1− ρ)2ν2
) (124)
where the ρ is the second largest eigenvalue of combination matrixW in magnitude, which is strictly less than 1.
Proof: SinceW is a symmetric doubly stochastic matrix, there is an eigenvalue decomposition form W = QΛQT , where Q is some orthogonal matrix. The diagonal matrix Λ has the value within the range (0, 1] and contains one and only one entry that is 1 due to Assumption A.3. Therefore, we can establish that
‖(I −W)x‖2 = ‖(I −W)(x− x̄)‖2 =‖(Q(I − Λ)QT ⊗ I)(x− x̄)‖2 ≥ (1− ρ)2‖x− x̄‖2 (125)
where the first equality holds because (I −W )1 = 0. Now, we are read to establish the bound for the consensus error from the augmented gradient:
1
T T−1∑ t=0 ‖x(t) − x̄(t)‖2 ≤ γ 2 (1− ρ)2ν2T T−1∑ t=0 ∥∥∥ν γ (I −W)x(t) ∥∥∥2
≤ 2γ 2
(1− ρ)2ν2T T−1∑ t=0 ∥∥∥∇f(x̄) + ν γ (I −W)x(t) ∥∥∥2 + 2γ2 (1− ρ)2ν2T T−1∑ t=0 ∥∥∥∇f(x̄)∥∥∥2 (126)
where the last inequality utilizes the Jensen’s inequality ‖a‖2 = ‖a+b+(−b)‖2 ≤ 2‖a+b‖2+2‖b‖2 and by setting a = νγ (I − W)x
(t) and b = ∇f(x(t)). Using the conclusion from Lemma 1 and bounded gradient assumption, we can immediately establish that
1
T T−1∑ t=0 ‖x(t) − x̄(t)‖2
≤ 4γ 2( √ β2G ′ + )
(1− ρ)2ν2T
( L(x(0))− L∗
γT +
(√ 1− β2G′
2 + γL′
2 2
) nσ2 + nG2 ) (127)
which gives the desired bound that the consensus error has the order of O ( γ2
(1−ρ2)ν2
) .
This bounds for the consensus error has several easy interpretable conclusions: To have the smaller consensus error, we can either 1) use a better connectivity of the graph (i.e., ρ is closer to 0), or 2) set a smaller learning rate γ, or 3) choose a larger ν. More accurately, the consensus error is determined by the ratio between γ and ν, which is straight-forward to understand since the communication term (I −W)x is scaled by ν/γ. With above two lemma, we are ready to present the convergence theorem.
Proof of theorem 1. The first half of statement has already been shown in the lemma 1. We just to show the convergence for the centralized iterate. To connect the gradient over the centralized iterate x̄ with the stacked gradient over the stacked iterate x̄, we have
‖∇f(x̄(t))‖2 (a)= ∥∥∥∥∥∥ 1n n∑ i=1 ∇fi(x̄(t)) + 1 n n∑ i=1 ν γ (x (t) i − ∑ j∈Ni wijx (t) j ) ∥∥∥∥∥∥ 2
(b) ≤ 1 n n∑ i=1 ∥∥∥∥∥∥∇fi(x̄(t)) + νγ (x(t)i − ∑ j∈Ni wijx (t) j ) ∥∥∥∥∥∥ 2
= 1
n ∥∥∥∥∇f(x̄(t)) + νγ (I −W)x(t) ∥∥∥∥2
(c) ≤ 2 n ∥∥∥∥∇f(x(t)) + νγ (I −W)x(t) ∥∥∥∥2 + 2n ∥∥∥∇f(x(t))−∇f(x(t))∥∥∥2
(d) ≤ 2 n ∥∥∥∥∇f(x(t)) + νγ (I −W)x(t) ∥∥∥∥2 + 2L2n ∥∥∥x(t) − x(t)∥∥∥2 (128)
where step (a) follows the fact that W = [wij ] is a doubly stochastic matrix and step (b) and (c) are due to Jensen’s inequality and step(d) utilized the Lipschitz property.
Therefor, combining with the conclusions in lemma 1 and lemma 2, we have
1
T T∑ t=1 ‖∇f(x̄(t))‖2
≤ 2 nT T∑ t=1 ∥∥∥∥∇f(x(t)) + νγ (I −W)x(t) ∥∥∥∥2 + 2L2nT T∑ t=1 ∥∥∥x(t) − x(t)∥∥∥2 ≤4( √ β2G ′ + ) ( L(x(0))− L∗
γnT +
(√ 1− β2G′
2 + γL′
2 2
) σ2 )
+ 8L2γ2(
√ β2G ′ + )
(1− ρ)2ν2
( L(x(0))− L∗
γnT +
(√ 1− β2G′
2 + γL′
2 2
) σ2 +G2 ) =4( √ β2G ′ + ) ( 1 + 2L2γ2
(1− ρ)2ν2
)( L(x(0))− L∗
γnT +
(√ 1− β2G′
2 + γL′
2 2
) σ2 )
+ 8L2γ2(
√ β2G ′ + )
(1− ρ)2ν2 G2
=O (L(x(0))− L∗
γT
) +O(σ2) +O ( γ2 (1− ρ2)ν2 ) (129)
which gives us the desired result.

heading: E.2 CONVERGENCE PROOF SKETCH FOR THE VARIATION OF DAG-ADAM ALGORITHM
text: Similar as adapt-while-communicate versus adapt-then-communicate format, our proposed DAGAdam algorithm also can have another style:
g(t) =W∇f̂(x(t)) + ν γ (I −W)x(t) (130)
m(t) =β1m (t−1) + (1− β1)g(t) (131)
v(t) =β2v (t−1) + (1− β2)g(t) g(t) (132)
x(t+1) =x(t) − γ(H(t) + )−1m(t) (133)
Note there are twoW 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
g(t) = ν γ x(t) − ν γ W ( x(t) − γ ν ∇f̂(x(t)) ) (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, we need to find the gradient (134) as a standard gradient of another augmented loss function. As long as as we find that loss function, the rest of proof will be similar as we did in Theorem 1. Fortunately, it has been stated in Yuan et al. (2021) paper for the momentum algorithms. Here, we give a modification for the Adam algorithm.
First, we 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 can use W̃ = (I + W )/2 instead. Suppose W has eigenvalue decomposition form W = QTΛQ, where Q is an orthogonal matrix. Then, we define Wα = QTΛαQ, which is also positive definite matrix for any α > 0. So we have W = W 1 2W 1 2 . Now we introduce the algorithm into a transformed domain by multiplyingW− 12 on the both sides:
W− 12g(t) =W 12∇f̂(x(t)) + ν γ (I −W)W− 12x(t) (135)
W− 12m(t) =W− 12 β1m(t−1) + (1− β1)W− 1 2q(t) (136)
v(t+1) =β2v (t) + (1− β2)g(t) g(t) (137)
W− 12x(t+1) =W− 12x(t) − γW− 12 (H(t) + )−1W 12W− 12m(t) (138)
We further introduce
s(t) ,W− 12x(t),q(t) ,W− 12g(t),p(t) ,W− 12m(t+1), U(t) ,W− 12 diag(v(t))W 12 (139)
The algorithm (130)-(133)is equivalently to
q(t) =W 12∇(·)f̂(W 1 2 s(t)) +
ν γ (I −W)s(t) (140)
p(t) =β1p (t−1) + (1− β1)q(t) (141)
U(t) =β2U (t−1) + (1− β2)W− 1 2 diag [ (W 12q(t)) ]2 W 12 (142)
s(t+1) =s(t) − γ(U(t) + )−1p(t) (143)
where the notation ∇(·)f(·) means taking the gradient with respect to the whole argument of f and note that W− 12 (H(t) + )−1W 12 = ( W 12H(t)W− 12 + )−1 . Remember we can always retrieve
x(t) by x(t) =W 12 s(t). Now, we are prepared for introduce this new augmented loss function
LW (s) =f(W 1 2 s) +
ν
2γ ‖s‖2I−W (144)
It is not hard to verify that
∇sLW (s) =W 1 2∇(·)f(W 1 2 s(t)) +
ν γ (I −W)s(t) (145)
This means that (140) - (143) can be viewed as Adam algorithm applied on this augmented loss function LW (s). There is one difference that U(t) is no longer diagonal matrix. However, recall that we mainly use it in weighted norm, and the useful inequality (25) can be extended for arbitrary positive matrix
a‖x‖TA ≤ ‖Ax‖2 ≤ b‖x‖TA (146)
where a and b are the smallest and largest eigenvalue of matrixA. To see that, supposeA = QTΛQ, we have
‖Ax‖2 = ‖QTΛQx‖2 = ‖ΛQx‖2 ≤ b‖Λ1/2Qx‖2 = b‖x‖2A (147)
Therefore, we can establish the similar conclusion as Theorem 1.

heading: F HETEROGENEOUS DATA DISTRIBUTION GENERATION
text: This subsection provides the detailed heterogeneous data generation for CIFAR-10 training dataset. To simulate the heterogeneous data, the disjoint non-i.i.d. training data over agents are generated through the Dirichlet distribution. For each data class, a categorical vector q = (q1, · · · , qn), where∑ i qi = 1, qi ≥ 0, is used to illustrate the training data distribution in a network of size n. It is drawn from a symmetric Dirichlet distribution Dir(α), 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 α → ∞. After the sampling procedure, the data is reallocated to ensure the same amount of training data in each network node.
Fig. 9 visualizes the heterogeneous data distribution for the CIFAR-10 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, as α → 0, the data for each class tends to be allocated in a single node. When α→∞, all the data is distributed evenly. Fig. 10 illustrates the training loss and validation accuracy curves of different algorithms when α = 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.

heading: G MORE EXPERIMENTAL SETTING AND BERT EXPERIMENTAL RESULTS
text: More Implementation details. We also follow DDP’s design to enable computation and communication overlap. Each server contains 8 V100 GPUs in our cluster and is treated as 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 et al. (2019)) are utilized as default.
Training Loss. Fig. 11 shows the iteration-wise training loss curves of aforementioned algorithms separately.
The effect of using dynamic ν. Besides with fine-tuning a proper ν constant for DAG-Adam, we tried to use a dynamic ν scheduler to validate its performance. Compared to the common learning rate scheduler, we use dynamic ν schedulers that provide a relatively small ν value at first and grow to 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 ν for a certain iterations then use dynamic ν schedulers afterwards. We provide some preliminary results in Table 6. Unfortunately, it did not provide better performance compared with the result of using constant ν. We leave it as future works to design a better strategy to select ν adaptively without introducing more hyper-parameters.

Review summaries:
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).

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.