Year: 2018

Abstract:
Online and stochastic optimization methods such as SGD, ADAGRAD and ADAM are key algorithms in solving large-scale machine learning problems including deep learning. A number of schemes that are based on communications of nodes with a central server have been recently proposed in the literature to parallelize them. A bottleneck of such centralized algorithms lies on the high communication cost incurred by the central node. In this paper, we present a new consensus-based distributed adaptive moment estimation method (DADAM) for online optimization over a decentralized network that enables data parallelization, as well as decentralized computation. Such a framework not only can be extremely useful for learning agents with access to only local data in a communication constrained environment, but as shown in this work also outperform centralized adaptive algorithms such as ADAM for certain realistic classes of loss functions. We analyze the convergence properties of the proposed algorithm and provide a dynamic regret bound on the convergence rate of adaptive moment estimation methods in both stochastic and deterministic settings. Empirical results demonstrate that DADAM works well in practice and compares favorably to competing online optimization methods.

1 INTRODUCTION
Online optimization is a fundamental procedure for solving a wide range of machine learning problems Shalev-Shwartz et al. (2012); Hazan et al. (2016). It can be formulated as a repeated game between a learner (algorithm) and an adversary. The learner receives a streaming data sequence, sequentially selects actions, and the adversary reveals the convex or nonconvex losses to the learner. A standard performance metric for an online algorithm is regret, which measures the performance of the algorithm versus a static benchmark Zinkevich (2003); Hazan et al. (2016). For example, the benchmark could be an optimal point of the online average of the loss (local cost) function, had the learner known all the losses in advance. In a broad sense, if the benchmark is a fixed sequence, the regret is called static. Recent work on online optimization has investigated the notion of dynamic regret Zinkevich (2003); Hall & Willett (2015); Besbes et al. (2015). Dynamic regret can take the form of the cumulative difference between the instantaneous loss and the minimum loss. For convex functions, previous studies have shown that the dynamic regret of online gradient-based methods can be upper bounded by O( √ T DT ), where DT is a measure of regularity of the comparator sequence or the function sequence Zinkevich (2003); Hall & Willett (2015). This bound can be improved to O(DT ) Mokhtari et al. (2016); Zhang et al. (2017) when all the cost functions are strongly convex and smooth.
Decentralized nonlinear programming has received a great deal of interest in diverse scientific and engineering fields Tsitsiklis et al. (1986); Li et al. (2002); Rabbat & Nowak (2004); Lesser et al. (2012). The key problem involves optimizing a cost function f (x) = 1n ∑ n i=1 fi(x), where x ∈ Rp and each fi is only known to the individual agent i in a connected network of n agents. The agents collaborate by successively sharing information with other agents located in their neighborhood with the goal of jointly converging to the network-wide optimal argument Nedic & Ozdaglar (2009). Compared to optimization procedures involving a fusion center that collects data and performs the computation, decentralized nonlinear programming enjoys the advantage of scalability to network sizes, robustness to dynamic topologies, and privacy preservation in data-sensitive applications Yuan et al. (2016); Shi et al. (2015); Jiang et al. (2017); Lian et al. (2017).
Appropriately choosing the learning rate that scale coordinates of the gradient and the way of updating them are crucial issues driving the performance of first Duchi et al. (2011); Kingma & Ba (2014) and second order optimization procedures Peyghami & Tarzanagh (2015). Indeed, the understanding that adaptation of the learning rate is advantageous, particularly on a per parameter basis dynamically, led to the development of a family of widely-used adaptive gradient methods including ADAGRAD Duchi et al. (2011), RMSPROP Tieleman & Hinton, and ADAM Kingma & Ba (2014). The ADAM optimizer computes adaptive learning rates for different parameters from estimates of first and second moments of the gradients and performs a local optimization. Numerical results show that ADAM can achieve significantly better performance compared to ADAGRAD, RMSPROP and other gradient descent procedures when the gradients are sparse, or in general small in magnitude. However, its performance has been observed to deteriorate in settings where the loss functions are nonconvex and gradients are dense. Further, there is currently a gap in the theoretical understanding of these methods, especially in the nonconvex and stochastic setting Ward et al. (2018); Zeng & Yin (2018).
1.1 CONTENTS AND CONTRIBUTIONS
In this paper, we develop and analyze a new consensus-based distributed adaptive moment estimation (DADAM) method that incorporates decentralized optimization and uses a variant of the adaptive moment estimation methods Duchi et al. (2011); Kingma & Ba (2014); Tieleman & Hinton; McMahan & Streeter (2010). Existing distributed stochastic and adaptive gradient methods for deep learning are mostly designed for central network topology Dean et al. (2012); Li et al.. The main bottleneck of such a topology lies on the communication overload on the central node, since all nodes need to concurrently communicate with it. Hence, performance can be significantly degraded when network bandwidth is limited. These considerations motivate us to study an adaptive algorithm for network topologies, where all nodes can only communicate with their neighbors and none of the nodes is designated as “central”. Therefore, the proposed method is suitable for large scale machine learning problems, since it enables both data parallelization and decentralized computation.
Next, we briefly summarize the main technical contributions of the work.
- Our first main result (Theorem 4) provides guarantees of DADAM for constrained convex minimization problems defined over a closed convex set X . We provide the convergence bound in terms of dynamic regret and show that when the data features are sparse and have bounded gradients, our algorithm’s regret bound can be considerably better than the ones provided by standard mirror descent and gradient descent methods Nedic & Ozdaglar (2009); Hall & Willett (2015); Besbes et al. (2015). It is worth mentioning that the regret bounds provided for adaptive gradient methods Duchi et al. (2011) are static and our results generalize them to dynamic settings.
- In Theorem 5, we give a new local regret analysis for distributed gradient-based algorithms for nonconvex minimization problems computed over a network of agents. Specifically, we prove that under certain regularity conditions, DADAM can achieve a local regret bound of order Õ( 1T ) for nonconvex distributed optimization. To the best of our knowledge, rigorous extensions of existing adaptive gradient methods to the distributed nonconvex setting considered in this work do not seem to be available.
- In this paper, we also present regret analysis for distributed stochastic optimization problems computed over a network of agents. Theorems 8 and 10 provide regret bounds of DADAM for minimization problem equation 3 with stochastic gradients and indicate that the result of Theorems 4 and 5 holds true in expectation. Further, in Corollary 11 we show that DADAM can achieve a local regret bound of order O( ξ 2 √
nT + 1T ) for noncon-
vex distributed stochastic optimization where ξ is an upper bound on the variance of the stochastic gradient. Hence, DADAM outperforms centralized adaptive algorithms such as ADAM for certain realistic classes of loss functions when T is sufficiently large.
The remainder of the paper is organized as follows. Section 2 gives a detailed description of DADAM, while Section 3 establishes its theoretical results. Section 4 explains a network correction technique for our proposed algorithm. Section 5 illustrates the proposed framework on a number of synthetic and real data sets. Finally, Section 6 concludes the paper.
The detailed proofs of the main results established are delegated to the Appendix.
1.2 MATHEMATICAL PRELIMINARIES AND NOTATIONS.
Throughout the paper, Rp denotes the real coordinate space of p dimensions. For any pair of vectors x,y ∈ Rp, 〈x,y〉 indicates the standard Euclidean inner product. We denote the `1 norm by ‖X‖1 = ∑i j |xi j|, the infinity norm by ‖X‖∞ = maxi j |xi j|, and the Euclidean norm by ‖X‖= √ ∑i j |xi j|2. The
above norms reduce to the vector norms if X is a vector. The diameter of the set X is given by
γ∞ = sup x,y∈X ‖x− y‖∞. (1)
Let S p+ be the set of all positive definite p× p matrices. ΠX ,A [x] denotes the Euclidean projection of a vector x onto X for A ∈S p+ :
ΠX ,A [ x ] = argmin
y∈X ‖A
1 2 (x− y)‖.
The subscript t is often used to denote the time step while yi,t,d stands for the d-th element of yi,t . Further, yi,1:t,d ∈ Rt is given by
yi,1:t,d = [yi,1,d ,yi,2,d , . . . ,yi,t,d ]>.
We let gi,t to denote the gradient of f at xi,t . The i-th largest singular value of matrix X is denoted by σi(X). We denote the element in the i-th row and j-th column of matrix X by [X ]i j. In several theorems, we consider a connected undirected graph G = (V ,E ) with nodes V = {1,2, . . . ,n} and edges E . The matrix W ∈ Rn×n is often used to denote a symmetric mixing matrix Shi et al. (2015) of graph G . Indeed, for any agent i, we assign a positive weight [W ]i j for the information received from agent j 6= i so that [W ]i j > 0 if and only if (i, j) ∈ E and
n
∑ i=1
[W ]i j = n
∑ j=1 [W ]i j = 1. (2)
The role of W is the similar as that in decentralized gradient descent methods Yuan et al. (2016) and average consensus Xiao et al. (2007). It has a few common choices, which can significantly affect performance (see, Shi et al. (2015)). Throughout this paper, we consider Metropolis constant edge weight matrix Xiao & Boyd (2004); Xiao et al. (2007) defined as follows
[Ŵ ]i j =  1 max{deg(i),deg( j)}+ε , if (i, j) ∈ E , 0, if (i, j) /∈ E and i 6= j,
1− ∑ k∈V [Ŵ ]ik, if i = j,
for some small positive ε > 0. When Ŵ is chosen according this scheme, W = I+Ŵ2 is found to be very efficient. Note, the above doubly stochastic matrix implies uniqueness of σ1(W ) = 1 and warrants that other singular value of W are strictly less than one in magnitude.
The Hadamard (entrywise) and Kronecker product are denoted by and ⊗, respectively. Finally, the expectation operator is denoted by E.
2 PROBLEM FORMULATION AND ALGORITHM
In this section, we propose a new optimization method for online optimization that employs data parallelization and decentralized computation over a network of agents. In our new structure, given a connected undirected graph G = (V ,E ), we let each node i ∈ V at time t ∈ {1, . . . ,T} hold its own measurement and training data mi, and set fi,t(x) = 1mi ∑ mi j=1 f j i,t(x). We also let each agent i hold a local copy of the global variable x at time t ∈ {1, . . . ,T}, which is denoted by xi,t ∈ Rp. With this setup, we present a distributed adaptive gradient method for solving the minimization problem
minimize x∈X F(x) = 1 n
T
∑ t=1
n
∑ i=1 fi,t(x), (3)
where fi,t : X → R is a continuously differentiable mapping on the convex set X . It is known that it is impossible to achieve a sub-linear dynamic regret bound Zhang et al. (2017), because of the arbitrary fluctuations in problem equation 3. We want to characterize the hardness of the problem via a complexly measure that captures the pattern of the minimizer sequence {x∗t }Tt=1, where x∗t = argminx∈X ft(x). Subsequently, we would like to provide a regret bound in terms of
DT,d = T−1
∑ t=1 |x∗t+1,d− x∗t,d | for d ∈ {1, ..., p}, (4)
which represents the variations in {x∗t }Tt=1. DADAM uses a new distributed adaptive gradient method in which a group of n agents seeking to solve a sequential version of problem equation 3. Here, we assume that each component function fi,t : X → R becomes only available to agent i ∈ V , after having made its decision at time t ∈ {1, . . . ,T}. In the t-th, the i-th agent chooses a point xi,t corresponding to what it considers the network as a whole should have selected. After committing to this choice, the agent has access to a cost function fi,t : X → R and the network cost is then given by ft(x) = 1n ∑ n i=1 fi,t(x). Note that this function is not known to any of the agents and is not available at any single location.
The procedure of our proposed method is outlined in Algorithm 1.
Algorithm 1: A distributed adaptive moment estimation method (DADAM) input : x1 ∈X , a positive sequence {αt}Tt=1, exponential decay rates for the moment
estimate β1,β2,β3 ∈ [0,1), and a mixing matrix W satisfying equation 2; 1 for all i ∈ V , initialize moment vectors mi,0 = υi,0 = υ̂i,0 = 0 and xi,1 = x1; 2 for i ∈ V do 3 for t← 1 to T do 4 gi,t = ∇ fi,t(xi,t); 5 mi,t = β1mi,t−1 +(1−β1)gi,t ; 6 υi,t = β2υi,t−1 +(1−β2)gi,t gi,t ; 7 υ̂i,t = β3υi,t +(1−β3)max(υ̂i,t−1,υi,t); 8 xi,t+ 12
= ∑nj=1[W ]i jx j,t ; 9 xi,t+1 = ΠX ,√diag(υ̂i,t ) [ xi,t+ 12 −αt mi,t√ υ̂i,t ] ;
output: resulting parameter x̄ = 1n ∑ n i=1 xi,T+1
It is worth mentioning that DADAM computes adaptive learning rates from estimates of both first and second moments of the gradients similar to Duchi et al. (2011); Tieleman & Hinton; Kingma & Ba (2014); Reddi et al. (2018). However, DADAM uses a larger learning rate in comparison to AMSGrad Reddi et al. (2018) and yet incorporates the intuition of slowly decaying the effect of previous gradients on the learning rate. The key difference of DADAM with ADAM and AMSGrad is that it maintains the maximum of all second moment estimates of the gradient vectors until time step t and uses
υ̂i,t = β3υi,t +(1−β3)max(υ̂i,t−1,υi,t), for normalizing the running average of the gradient instead of υi,t in ADAM and max(υ̂i,t−1,υi,t) in AMSGrad. The learning rate υ̂i,t is an important component of the DADAM framework, since it enables us to develop a convergent adaptive method similar to AMSGrad while maintaining the efficiency of ADAM.
Next, we provide the notion of regret which measures the performance of DADAM against a sequence of local minimizers.
In the framework of online convex optimization, the performance of algorithms is assessed by regret that measures how competitive the algorithm is with respect to the best fixed solution Mateos-Núnez & Cortés (2014); Hazan et al. (2016). However, the notion of regret fails to illustrate the performance of online algorithms in a dynamic setting. To overcome this issue, we consider a more stringent
metric–dynamic regret Hall & Willett (2015); Besbes et al. (2015); Zinkevich (2003), in which the cumulative loss of the learner is compared against the minimizer sequence {x∗t }Tt=1, i.e.,
RegCT := 1 n
n
∑ i=1
T
∑ t=1
fi,t(xi,t)− T
∑ t=1 ft(x∗t ),
where x∗t = argminx∈X ft(x).
On the other hand, in the framework of nonconvex optimization, it is usual to state convergence guarantees of an algorithm towards an ε-approximate stationary point–that is, there exist some iterates xi,t for which ‖∇ ft(xi,t)‖ ≤ ε . Inspired by Hazan et al. (2017), we next provide the definition of projected gradient and introduce local regret, a new notion of regret which quantifies the moving average of gradients over network.
Definition 1. (Local Regret). Assume fi : X →R is a differentiable function on a closed convex set X ⊆Rp. Given a step-size α > 0, we define GX (x, fi,α) : X →Rp the projected gradient of fi at x, by
GX (x, fi,α) = √
υ̂i α (x− x+i ), ∀i ∈ V , (5)
where
x+i = argmin y∈X {〈y, mi√ υ̂i 〉+ 1 2α ‖y−
n
∑ j=1 [W ]i jx j‖2}. (6)
Then, the local regret of an online algorithm is given by
RegNT := 1 n
n
∑ i=1 min t∈{1,...,T} ‖GX (xi,t , f̄i,t ,αt)‖2,
where f̄i,t(xi,t) = 1t ∑ t s=1 fi,s(xi,t) is an aggregate loss.
We analyze the convergence of DADAM as applied to minimization problem equation 3 using regrets RegCT and Reg N T . It is worth to mention that DADAM is initialized at xi,t = 0 to keep the presentation of the convergence analysis clear. In general, any initialization can be selected for implementation purposes.
3 CONVERGENCE ANALYSIS
In this section, our aim is to establish convergence properties of DADAM under the following assumptions:
Assumption 2. For all i ∈ V and t ∈ {1, . . . ,T}, the function fi,t(x) is continuously differentiable over X , and has Lipschitz continuous gradient on this set, i.e. there exists a constant ρ ≥ 0 so that
‖∇ fi,t(x)−∇ fi,t(y)‖ ≤ ρ‖x− y‖, ∀x,y ∈X .
Further, fi,t(·) is Lipschitz continuous on X with a uniform constant L≥ 0, i.e.,
| fi,t(x)− fi,t(y)| ≤ L‖x− y‖, ∀x,y ∈X . (7)
There are many cost functions fi,t that satisfy this type of Lipschitz condition. For example, it holds for any convex function on a compact set X , or for any polyhedral function on an arbitrary domain Duchi et al. (2011).
Assumption 3. For all i ∈ V and t ∈ {1, . . . ,T}, the stochastic gradient, as notation we use bold letters g =∇ fi,t(xi,t), satisfies
E [ ∇ fi,t(xi,t) ∣∣Ft−1]= ∇ fi,t(xi,t), E[‖∇ fi,t(xi,t)‖2 ∣∣Ft−1]≤ ξ 2, where Ft is the ξ -field containing all information prior to the outset of round t +1.
3.1 CONVEX CASE
Next, we focus on the case where for all i ∈ V and t ∈ {1, . . . ,T}, the agent i at time t has access to the exact gradient gi,t = ∇ fi,t(xi,t). The following results apply to convex problems, as well as their stochastic variants in a dynamic environment.
Theorem 4. Suppose that the parameters β1,β2 ∈ [0,1) satisfy η = β1√β2 < 1. Let β1,t = β1λ t−1,λ ∈ (0,1) and ‖∇ fi,t(x)‖∞ ≤ G∞ for all t ∈ {1, . . . ,T}. Then, using a step-size αt = α√t for the sequence xi,t generated by Algorithm 1, we have
RegCT ≤ (1−β1)α
√ 1+ logT
2 √ n √ (1−β2)
p
∑ d=1 ‖g1:T,d‖+
p
∑ d=1 G∞γ∞ (1−β1)(1−λ )
+ p
∑ d=1 γ∞(γ∞ +DT,d)√ n(1−β1)α
√ T υ̂T,d +
4α √
1+ logT ∑pd=1 ‖g1:T,d‖ (1−σ2(W )) √ (1−β1) √ (1−η) √ (1−β2) .
Next, we analyze the stochastic convex setting and extend the result of Theorem 4 to the noisy case where agents have access to stochastic gradients of the objective function equation 3.
Theorem 5. Suppose that Assumption 3 holds. Further, the parameters β1,β2 ∈ [0,1) satisfy η = β1√
β2 < 1. Let β1,t = β1λ t−1,λ ∈ (0,1). Then, using a step-size αt = α√t for the sequence xi,t
generated by Algorithm 1, we have
E [ RegCT ] ≤ (1−β1)α √ 1+ logT
2 √ n √ (1−β2)
p
∑ d=1
E [ ‖g1:T,d‖ ] + p
∑ d=1 ξ γ∞ (1−β1)(1−λ )
+ p
∑ d=1 γ∞(γ∞ +DT,d)√ n(1−β1)α
√ TE [√ υ̂T,d ] +
4α √ 1+ logT ∑pd=1E [ ‖g1:T,d‖ ] (1−σ2(W )) √ (1−β1) √ (1−η) √ (1−β2) .
Remark 6. Theorems 4 and 5 show that the regret bound of DADAM can be considerably better than the ones provided by standard mirror descent and gradient descent methods for both centralized and decentralized settings Zinkevich (2003); Hall & Willett (2015); Besbes et al. (2015); Shahrampour & Jadbabaie (2018) because
p
∑ d=1 ‖g1:T,d‖=
p
∑ d=1
√ g21,d +g 2 2,d + · · ·+g2T,d ≤ p
∑ d=1
√ G2∞ +G2∞ + · · ·+G2∞
= p
∑ d=1
√ T G∞ = pG∞ √ T ,
p
∑ d=1
√ T υ̂T,d ≤ p
∑ d=1
√ T G∞ ≤ pG∞ √ T .
It is easy to show that the regret of DADAM is upper bounded by O(G∞DT √
T 1−σ2(W ) ) where DT =
maxd∈{1,...,p}DT,d . Indeed, the term ∑Tt=1 |gi,t,d |/ √
t in the proof of Lemma 14 can be bounded by O(G∞ √ T ) instead of O(G∞ √ T logT ). Hence, the regret of DADAM is upper bounded by minimum of O(G∞DT √
T 1−σ2(W ) ) and the bound presented in Theorems 4 and 5, and thus the worst case dependence
on T is √ T rather than √ T logT .
Remark 7. We note that in the static setting, i.e. DT = 0, the regret of DADAM is upper bounded by
O( G∞ √
T 1−σ2(W ) ),
where 1−σ2(W ) is the spectral gap of the network.
3.2 NONCONVEX CASE
In this section, we provide convergence guarantees for DADAM for the nonconvex minimization problem equation 3 defined over a closed convex set X . To do so, we use the projection map ΠX instead of Π
X , √ diag(v̂i,t ) for updating parameters xi,t for t ∈ {1, . . . ,T}, i ∈ V (see, Algorithm 1 for
details).
Next, we derive an upper and lower bound for the second moment of gradient, υi,t . Assume that there exists a positive number ῡ such that
max d∈{1,...,p} gi,t,d ≤ ῡ . (8)
Now, using the update rule of υi,t , we have υi,t =(1−β2)∑tl=1 β t−l 2 g 2 i,l . This together with equation 8 imply that
√ υi,t ≤ max
d∈{1,...,p}
√ υi,t,d = max
d∈{1,...,p}
√ (1−β2) t
∑ l=1 β t−l2 g 2 i,l,d
≤ ῡ √ (1−β2) t
∑ l=1 β t−l2 ≤ ῡ . (9)
On the other hand, since υi,t,d is non-decreasing and gi,t,d is required to be element-wise non-zero, we have υi,t,d ≥ υ2 > 0, (10) for some constant υ .
Now, using the update rule of υ̂i,t along with equation 10 and equation 9, we have
υ2 ≤ β3υ2 +(1−β3)υ2
≤ υ̂i,t = β3υi,t +(1−β3)max(υ̂i,t−1,υi,t) ≤ β3ῡ2 +(1−β3)ῡ2 ≤ ῡ2. (11)
Theorem 8. Suppose that Assumption 2 holds. Further, the parameters β1,β2 ∈ [0,1) satisfy η = β1√
β2 < 1. Choose the positive sequence {αt}Tt=1 such that 0 < αt ≤
(2−β1)υ2 ρῡ with αt < (2−β1)υ2 ρῡ for
at least one t. Then, for the sequence xi,t generated by Algorithm 1, we have
RegNT ≤ 1 ϑt [(2+ logT )2L max t∈{2,...,T}
2 √ n (1−η) √ (1−β2) t−1 ∑ s=0 αsσ t−s−12 (W )
+ T
∑ t=1 αtβ1,t ῡ 2(1−β1,t)(1−η)2(1−β2) ], (12)
where ϑt = ∑Tt=1[ (2−β1)αt 2ῡ − ρα2t 2υ2 ].
The following corollary shows that DADAM using a certain step-size leads to a near optimal regret bound for nonconvex functions. Corollary 9. Under the same conditions of Theorem 8, using the step-sizes αt = (2−β1)υ 2
2ρῡ and β1,t = β1λ t−1,λ ∈ (0,1) for all t ∈ {1, . . . ,T}, we have
RegNT ≤ ( 2ῡ2 (2−β1)(1−β1)(1−η)2(1−β2)(1−λ ) ) 1 T
+ ( 16√nῡL (2−β1)(1−η) √ (1−β2)(1−σ2(W )) ) (2+ logT ) T . (13)
To complete the analysis of our algorithm in the nonconvex setting, we provide the regret bound for DADAM, when stochastic gradients are accessible to the learner.
Theorem 10. Suppose that Assumption 2 holds. Further, the parameters β1,β2 ∈ [0,1) satisfy η = β1√
β2 < 1. Choose the positive sequence {αt}Tt=1 such that 0 < αt ≤
(2−β1)υ2 ρῡ with αt < (2−β1)υ2 ρῡ
for at least one t. Then, for the sequence xi,t generated by Algorithm 1, we have
E [ RegNT ] ≤ 1
ϑt [(2+ logT )2L max t∈{2,...,T}
2 √ n (1−η) √ (1−β2) t−1 ∑ s=0 αsσ t−s−12 (W )
+ T
∑ t=1 αtβ1,t ῡ 2(1−β1,t)(1−η)2(1−β2) + ῡξ 2 υ2(1−β1) T ∑ t=1 αt ], (14)
where ϑt = ∑Tt=1[ (2−β1)αt 2ῡ − ρα2t 2υ2 ].
3.2.1 WHEN DOES DADAM OUTPERFORM ADAM?
We next theoretically justify the potential advantage of the proposed decentralized algorithm DADAM over centralized adaptive moment estimation methods such as ADAM . More specifically, the following corollary shows that when T is sufficiently large, the 1T term will be dominated by the 1√ nT term which leads to a 1√ nT convergence rate.
Corollary 11. Suppose that Assumptions 2 and 3 hold. Moreover, the parameters β1,β2 ∈ [0,1) satisfy η = β1√
β2 < 1 and β1,t = β1λ t−1,λ ∈ (0,1). Choose the step-size sequence as αt = α√nT with
α = (2−β1)υ 2
ρῡ . Then, for the sequence xi,t generated by Algorithm 1, we have E [ RegNT ] T ≤ ( 8ῡα υ2(1−β1) ) ξ 2√ nT +2 ( f1(x1)− f1(x∗1) ) 1 T , (15)
if the total number of time steps T satisfies
T ≥ (I1 + I2), (16a)
T ≥max{ 4ρ 2ῡ2
nυ4(2−β1)2 , 4ῡ2n (2−β1)2 }, (16b)
where
I1 = υ2
2(1−η)2(1−β2)(1−λ )ξ 2 , I2 =
16nL2υ4(1−β1)2
(1−η)2(1−β2)(1−σ2(W ))2ῡ2ξ 4 .
Let ε-approximation solution of equation 3 be defined by E[Reg N T ]
T ≤ ε . Corollary 11 indicates that the total computational complexity of DADAM to achieve an ε-approximation solution is bounded by O( 1ε2 ). The key setup which leads to this regret bound is that we do not use the boundedness assumption for domain or gradient. These assumptions can simplify the proof but lose some of the sophisticated structures in the problem.
4 AN EXTENSION OF DADAM WITH A CORRECTED UPDATE RULE
Compared to classical centralized algorithms, decentralized algorithms encounter more restrictive assumptions and typically worse convergence rates. In order to improve the convergence rate, Shi et al. (2015) introduced a corrected decentralized gradient method called EXTRA, which has a linear rate of convergence if the objective function is strongly convex. Similar to EXTRA, we provide next a corrected update rule for i ∈ V , given by
xC-DADAMi,t+1 = xi,t+1 + t−1
∑ s=0
n
∑ j=1 [W −Ŵ ]i jx j,s︸ ︷︷ ︸ correction , t = 0,1, . . . . (17)
where xi,t+1 is generated by Algorithm 1.
Our numerical results on some test problems show the efficiency and effectiveness of the corrected DADAM (C-DADAM) in practice. Note that a C-DADAM update is a DADAM update with a cumulative correction term. The summation in equation 17 is necessary, since each individual term ∑nj=1[W −Ŵ ]i jx j,s is asymptotically vanishing and the terms must work cumulatively.
5 NUMERICAL RESULTS
In this section, we present numerical results for Algorithm 1 (DADAM), on both synthetic and real data sets. The employed data sets and the code will be made available on github upon acceptance of this manuscript. We first present numerical results on a sparse binary classification problem, comparing the performance of DADAM to that of standard decentralized gradient descent (DGD) Nedic & Ozdaglar (2009); Yuan et al. (2016) and its corrected version EXTRA Shi et al. (2015). In Section 5.2, we demonstrate the efficacy of DADAM in comparison with a decentralized ADAM (Algorithm 1 with β3 = 1) and the recently proposed distributed federated averaging SGD (FedAvg) algorithm on benchmark datasets such as MNIST and CIFAR-10. All algorithms have been implemented in a Mac machine equipped with a 1.8 GHz Intel Core i5 processor and 8 GB 1600 MHz DDR3 of memory.
5.1 BINARY CLASSIFICATION BASED ON SYNTHETIC DATA IN THE STATIC ENVIRONMENT
Consider the following online distributed learning setting: at each time t, mi randomly generated data points are given to every agent i in the form of (yt,i, j,xt,i, j), where yt,i, j ∈ {±1} is a binary label and xt,i, j ∈ Rp is a feature vector for j = 1, . . . ,mi. Our goal is to train a classifier θ ∈ Rp such that for an arbitrary new feature vector x̂ it assigns ŷ = sign(〈θ , x̂〉). We design decentralized convex logistic and nonconvex sigmoid loss functions with `2 regularization as follows:
f 1i,t(θ) = 1 mi
mi ∑ j=1
( 1+ exp(10〈xt,i, j,θ〉yt,i, j) )−1 +ν‖θ‖22,
f 2i,t(θ) = 1 mi
mi ∑ j=1 log(1+ exp(−〈xt,i, j,θ〉yt,i, j))+ν‖θ‖22, (18)
where ν = 1/mi and mi is the size of the training data on node i.
For X , we consider the `1 ball X`1 = {θ ∈ Rp : ‖θ‖1 ≤ r}, when a sparse classifier is preferred. We show results for the decentralized problem solved by DADAM, C-DADAM, DGD and EXTRA over a medium-scale network. We have implemented EXTRA and DGD with their default settings. The connected network is randomly generated with n = 50 agents and connectivity ratio r = 0.2. Each agent holds 10 samples, i.e., mi = 10,∀i ∈ V . The agents shall collaboratively obtain p coefficients via loss functions equation 18. All samples are randomly generated, and the reference classifier θ ∗ is pre-computed using a centralized method. As it is easy to implement in practice, we use the Metropolis constant edge weight matrix W Shi et al. (2015) in our experimental evaluation 1. We have tested the DADAM and C-DADAM with β1 = β2 = β3 = 0.9. The numerical results are illustrated in Figure 1. It can be seen that DADAM and C-DADAM outperform DGD and EXTRA, showing almost linear convergence in the convex setting to the reference logistic classifier x∗.
5.2 CIFAR AND MNIST EXPERIMENTS
Next, we present the experimental results using the CIFAR-10 image recognition dataset and the MNIST digit recognition task. The model architecture for training CNN to classify CIFAR10 dataset was taken from the TensorFlow tutorial 2. Also, the model for training a simple multilayer percepton (MLP) on the MNIST dataset was taken from https://github.com/keras-team/keras/blob/master.
1 http://www.math.ucla.edu/ wotaoyin/software.html 2 http://www.tensorflow.org/tutorials
lem using convex and nonconvex (with α/
√
t) loss functions. Constant α = σn/ρ is the theoretical critical step-size given for DGD Yuan et al. (2016). (a) classification with p = 10 and ν = 0. (b) classification with p = 20 and ν = 0. (c) classification with p = 20 and ν = 1/mi.
We compare the accuracy of DADAM with that of the decentralized ADAM (Algorithm 1 with β3 = 1 ) and the Federated Averaging (FedAvg) algorithm McMahan et al. (2016) which also performs data parallelization without decentralized computation. The connected network is generated with n = 5 agents and connectivity ratio r = 0.8. The parameters for DADAM and ADAM are selected in a way similar to the previous experiments. In our implementation, we use same number of agents and choose E = C = 1 as the parameters in the FedAvg algorithm since it is close to a connected topology scenario as considered in the DADAM and ADAM. It can be easily seen from Figure 2 that DADAM and the decentralized ADAM (β3 = 1) outperform FedAvg. Further, DADAM can achieve high accuracy in comparison with the decentralized ADAM and FedAvg.
6 CONCLUSION
A decentralized adaptive moment estimation method DADAM was proposed for the distributed learning of deep networks based on adaptive moment of first and second moment of estimations. Convergence properties of the proposed algorithm were established for convex (and dynamic) and nonconvex functions in both stochastic and deterministic settings. Numerical results on some datasets show the efficiency and effectiveness of the new proposed method in practice.
REFERENCES Hedy Attouch, Jérôme Bolte, and Benar Fux Svaiter. Convergence of descent methods for semi-
algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized gauss–seidel methods. Mathematical Programming, 137(1-2):91–129, 2013.
Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167–175, 2003.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Operations Research, 63(5):1227–1244, 2015.
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Andrew Senior, Paul Tucker, Ke Yang, Quoc V Le, et al. Large scale distributed deep networks. In Advances in neural information processing systems, pp. 1223–1231, 2012.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(Jul):2121–2159, 2011.
Eric C Hall and Rebecca M Willett. Online convex optimization in dynamic environments. IEEE Journal of Selected Topics in Signal Processing, 9(4):647–662, 2015.
Elad Hazan, Karan Singh, and Cyril Zhang. Efficient regret minimization in non-convex games. arXiv preprint arXiv:1708.00075, 2017.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends R© in Optimization, 2(3-4):157–325, 2016.
Roger A Horn, Roger A Horn, and Charles R Johnson. Matrix analysis. Cambridge university press, 1990.
Zhanhong Jiang, Aditya Balu, Chinmay Hegde, and Soumik Sarkar. Collaborative deep learning in fixed topology networks. In Advances in Neural Information Processing Systems, pp. 5904–5914, 2017.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Victor Lesser, Charles L Ortiz Jr, and Milind Tambe. Distributed sensor networks: A multiagent perspective, volume 9. Springer Science & Business Media, 2012.
Dan Li, Kerry D Wong, Yu Hen Hu, and Akbar M Sayeed. Detection, classification, and tracking of targets. IEEE signal processing magazine, 19(2):17–29, 2002.
Mu Li, David G Andersen, and Jun Woo Park. Scaling distributed machine learning with the parameter server.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems, pp. 5330–5340, 2017.
David Mateos-Núnez and Jorge Cortés. Distributed online convex optimization over jointly connected digraphs. IEEE Transactions on Network Science and Engineering, 1(1):23–37, 2014.
H Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. arXiv preprint arXiv:1002.4908, 2010.
H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, et al. Communication-efficient learning of deep networks from decentralized data. arXiv preprint arXiv:1602.05629, 2016.
Aryan Mokhtari, Shahin Shahrampour, Ali Jadbabaie, and Alejandro Ribeiro. Online optimization in dynamic environments: Improved regret rates for strongly convex problems. In Decision and Control (CDC), 2016 IEEE 55th Conference on, pp. 7195–7201. IEEE, 2016.
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48–61, 2009.
M Reza Peyghami and D Ataee Tarzanagh. A relaxed nonmonotone adaptive trust region method for solving unconstrained optimization problems. Computational Optimization and Applications, 61(2):321–341, 2015.
Michael Rabbat and Robert Nowak. Distributed optimization in sensor networks. In Proceedings of the 3rd international symposium on Information processing in sensor networks, pp. 20–27. ACM, 2004.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018.
Shahin Shahrampour and Ali Jadbabaie. An online optimization approach for multi-agent tracking of dynamic parameters in the presence of adversarial noise. In American Control Conference (ACC), 2017, pp. 3306–3311. IEEE, 2017.
Shahin Shahrampour and Ali Jadbabaie. Distributed online optimization in dynamic environments using mirror descent. IEEE Transactions on Automatic Control, 63(3):714–725, 2018.
Shai Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and Trends R© in Machine Learning, 4(2):107–194, 2012.
Wei Shi, Qing Ling, Gang Wu, and Wotao Yin. Extra: An exact first-order algorithm for decentralized consensus optimization. SIAM Journal on Optimization, 25(2):944–966, 2015.
T Tieleman and G Hinton. Divide the gradient by a running average of its recent magnitude. coursera: Neural networks for machine learning. Technical report, Technical Report. Available online: https://zh. coursera. org/learn/neuralnetworks/lecture/YQHki/rmsprop-divide-the-gradientby-a-running-average-of-its-recent-magnitude (accessed on 21 April 2017).
John Tsitsiklis, Dimitri Bertsekas, and Michael Athans. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE transactions on automatic control, 31(9): 803–812, 1986.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization. arXiv preprint arXiv:1806.01811, 2018.
Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1):65–78, 2004.
Lin Xiao, Stephen Boyd, and Seung-Jean Kim. Distributed average consensus with least-meansquare deviation. Journal of Parallel and Distributed Computing, 67(1):33–46, 2007.
Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3):1835–1854, 2016.
Jinshan Zeng and Wotao Yin. On nonconvex decentralized gradient descent. IEEE Transactions on Signal Processing, 66(11):2834–2848, 2018.
Lijun Zhang, Tianbao Yang, Jinfeng Yi, Jing Rong, and Zhi-Hua Zhou. Improved dynamic regret for non-degenerate functions. In Advances in Neural Information Processing Systems, pp. 732–741, 2017.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. 2003.
Next, we establish a series of lemmas used in the proof of main theorems.
6.1 PROPERTIES OF DADAM
Lemma 12. Beck & Teboulle (2003) Let X be a nonempty closed convex set in Rp. Then, for any d ∈X , we have
〈x∗−d,a〉 ≤ 1 2 ‖d− c‖2− 1 2 ‖d− x∗‖2− 1 2 ‖x∗− c‖2,
where x∗ = argmin
x∈X {〈a,x〉+ 1 2 ‖x− c‖2}.
Lemma 13. McMahan & Streeter (2010) For any A ∈S p+ and convex feasible set C⊂Rp, suppose a1 = ΠC,A[b1],a2 = ΠC,A[b2], we have
‖A 1 2 (a1−a2)‖ ≤ ‖A 1 2 (b1−b2)‖.
Lemma 14. For all i ∈ V if β1,β2 ∈ [0,1) satisfy η = β1√β2 < 1, then we have
T
∑ t=1
p
∑ d=1 αtm2i,t,d υ̂i,t,d
≤ α √
1+ logT (1−β1)(1−η) √ (1−β2) p ∑ d=1 ‖gi,1:T,d‖,
where αt = α√t for all t ∈ {1, . . . ,T}.
Proof. Using the update rules in Algorithm 1, we have
T
∑ t=1 αm2i,t,d√ tυ̂i,t,d = T−1 ∑ t=1 αm2i,t,d√ tυ̂i,t,d + αT m2i,T,d√ (1−β3)max{υ̂i,T−1,d ,υi,T,d}+β3υi,T,d
≤ T−1
∑ t=1 αm2i,t,d√ tυ̂i,t,d + αT m2i,T,d√
(1−β3)υi,T,d +β3υi,T,d (i) = T−1
∑ t=1 αm2i,t,d√ tυ̂i,t,d + α(∑Tl=1(1−β1)β T−l1 gi,l,d)2√
T ∑Tl=1(1−β2)β T−l2 g2i,l,d (ii) ≤ T−1
∑ t=1 αm2i,t,d√ tυ̂i,t,d + α√ T (1−β2) (∑Tl=1 β T−l 1 )(∑ T l=1 β T−l 1 g 2 i,l,d)√
∑Tl=1 β T−l 2 g 2 i,l,d
(iii) ≤
T−1 ∑ t=1 αm2i,t,d√ tυ̂i,t,d + α (1−β1) √ T (1−β2) T ∑ l=1 β T−l1 g 2 i,l,d√
β T−l2 g 2 i,l,d
≤ T−1
∑ t=1 αm2i,t,d√ tυ̂i,t,d + α (1−β1) √ T (1−β2) T ∑ l=1 ηT−l |gi,l,d |,
where (i) follows from the fact that the update rules of mT and υT can be written as mT = (1− β1)∑Tl=1 β T−l 1 gl and υT = (1− β2)∑ T l=1 β T−l 2 g 2 l , respectively. (ii) follows from Cauchy-Schwarz inequality and the fact that 0≤ β1 < 1. Inequality (iii) follows since ∑Tl=1 β T−l1 ≤ 1 1−β1 . Hence, we have
T
∑ t=1 αm2i,t,d (1−β1) √ tυ̂i,t,d ≤ T ∑ t=1 α (1−β1) √ t(1−β2) t ∑ l=1 η t−l |gi,l,d |
= α (1−β1) √ (1−β2) T ∑ t=1 1√ t t ∑ l=1 η t−l |gi,l,d |
= α (1−β1) √ (1−β2) T ∑ t=1 |gi,t,d | T ∑ l=t η l−t√ l
≤ α (1−β1) √ (1−β2) T ∑ t=1 |gi,t,d | T ∑ l=t η l−t√ t
(i) ≤ α (1−β1) √ (1−β2) T ∑ t=1 |gi,t,d | 1 (1−η) √ t
(ii) ≤ α (1−β1)(1−η) √ (1−β2) ‖gi,1:T,d‖
√ T
∑ t=1 1 t
(iii) ≤ α
√ 1+ logT (1−β1)(1−η) √ (1−β2) ‖gi,1:T,d‖,
where inequality (i) follows since ∑Tl=t η l−t ≤ 1(1−η) . Inequality (ii) follows from Cauchy-Schwarz inequality. The inequality (iii) follows since
T
∑ t=1 1 t ≤ 1+ ∫ T t=1 1 t dt = 1+ log t|T1 = 1+ logT. (19)
Next, we provide an upper bound on the deviation of the local estimates at each iteration from their consensual value. A similar result has been proven in Shahrampour & Jadbabaie (2017) for online decentralized mirror descent; however, the following lemma extends that of Shahrampour & Jadbabaie (2017) to the online adaptive setting and takes into account the sparsity of gradient vector.
Lemma 15. ( Network Error with Sparse Data) If β1,β2 ∈ [0,1) satisfy η = β1√β2 < 1, then the sequence xi,t generated by Algorithm 1 satisfies
T
∑ t=1
n
∑ i=1 1 αt ‖V̂ 1 4 i,t (x̄t − xi,t)‖ 2 ≤
n √ nα √
1+ logT ∑pd=1 ‖g1:T,d‖ (1−σ2(W ))2(1−β1)(1−η) √ (1−β2) ,
where V̂i,t = diag(υ̂i,t) and x̄t = 1n ∑ n i=1 xi,t .
Proof. Let ei,t := xi,t+1−∑nj=1[W ]i jx j,t , where W satisfies equation 2. Using the update rule of xi,t+1 in Algorithm 1, we have
T
∑ t=1 1 αt ‖V̂ 1 4 i,t ei,t‖ 2 =
T
∑ t=1 1 αt ‖V̂ 1 4 i,t (xi,t+1− n ∑ j=1 [W ]i jx j,t)‖2
= T
∑ t=1 1 αt ‖V̂ 1 4 i,t (ΠX , √ V̂i,t [ n ∑ j=1 [W ]i jx j,t − αtmi,t√ υ̂i,t ] − n ∑ j=1 [W ]i jx j,t)‖2
≤ T
∑ t=1 1 αt ‖V̂ 1 4 i,t ( n ∑ j=1 [W ]i jx j,t −αtV̂ −1 2 i,t mi,t − n ∑ j=1 [W ]i jx j,t)‖2
= T
∑ t=1
p
∑ d=1 αtm2i,t,d√ υ̂i,t,d , (20)
where the first inequality follows from Lemma 13.
Further, from the definition of ei,t , we have
xi,t+1 = n
∑ j=1 [W ]i jx j,t + ei,t . (21)
Now, from equation 2 and equation 21, we have
x̄t+1 = 1 n
n
∑ i=1 xi,t+1 = 1 n
n
∑ i=1
n
∑ j=1 [W ]i jx j,t + 1 n
n
∑ i=1 ei,t
= 1 n
n
∑ j=1
( n
∑ i=1 [W ]i j)x j,t + 1 n
n
∑ i=1 ei,t
= x̄t + ēt ,
where ēt = 1n ∑ n i=1 ei,t . Hence,
x̄t+1 = t
∑ s=0 ēs. (22)
It follows from equation 21 that
xi,t+1 = t
∑ s=0
n
∑ j=1 [W t−s]i jei,s. (23)
Now, using equation 23 and equation 22, we have
xi,t+1− x̄t+1 = t
∑ s=0
n
∑ j=1 ([W t−s]i j− 1 n )ei,s. (24)
Now, taking the Euclidean norm of equation 24 and summing over t ∈ {1, . . . ,T}, one has: T
∑ t=1 1 αt ‖V̂ 1 4 i,t (xi,t+1− x̄t+1)‖ 2 (i) ≤
T
∑ t=1
t t
∑ s=0
( n
∑ j=1 |[W t−s]i j− 1 n |)2 ‖V̂
1 4
i,sei,s‖2
αs
(ii) ≤
T
∑ s=0
‖V̂ 1 4
i,sei,s‖2
αs
T
∑ t=1 ntσ2t−2s2 (W )
(iii) ≤ n (1−σ2(W ))2 T ∑ t=0
‖V̂ 1 4
i,t ei,t‖2
αt (iv) ≤ n
(1−σ2(W ))2 p ∑ d=1 T ∑ t=1 αtm2i,t,d√ υ̂i,t,d
(v) ≤
nα √
1+ logT ∑pd=1 ‖gi,1:T,d‖ (1−σ2(W ))2(1−β1)(1−η) √ (1−β2) , (25)
where step (i) follows from ‖∑ni=1 ai‖2 ≤ n∑ni=1 ‖ai‖2, step (ii) follows from the following property of mixing matrix W Horn et al. (1990),
n
∑ j=1 ∣∣∣∣[W t]i j− 1n ∣∣∣∣≤√nσ t2(W ), (26)
step (iii) follows from ∑Tt=1 tσ t2(W ) < 1
(1−σ2(W ))2 , step (iv) follows from equation 20 and step (v)
follows from Lemma 14.
Now, summing the equation 25 over i ∈ V and using n
∑ i=1 ‖gi,1:T,d‖ ≤
√ n( n
∑ i=1 ‖gi,1:T,d‖2)
1 2 = √ n‖g1:T,d‖, (27)
we complete the proof.
Lemma 16. For the sequence xi,t generated by Algorithm 1, we have
1 n
n
∑ i=1
T
∑ t=1 (
√ υ̂i,t
αt ‖x∗t −
n
∑ j=1
[W ]i jx j,t‖2− √
υ̂i,t αt ‖x∗t − xi,t+1‖2)
≤ 2γ 2 ∞√ n p
∑ d=1 √ υ̂T,d αT + 2γ∞√ n p ∑ d=1 √ υ̂T,d αT T−1 ∑ t=1 |x∗t+1,d− x∗t,d |. (28)
Proof. From the left side of equation 28, we have√ υ̂i,t
αt ‖x∗t −
n
∑ j=1
[W ]i jx j,t‖2− √
υ̂i,t αt ‖x∗t − xi,t+1‖2
=
√ υ̂i,t
αt ‖x∗t −
n
∑ j=1
[W ]i jx j,t‖2− √
υ̂i,t+1 αt+1 ‖x∗t+1− n ∑ j=1 [W ]i jx j,t+1‖2
+
√ υ̂i,t+1
αt+1 ‖x∗t+1−
n
∑ j=1
[W ]i jx j,t+1‖2− √
υ̂i,t+1 αt+1 ‖x∗t − n ∑ j=1 [W ]i jx j,t+1‖2 (29)
+
√ υ̂i,t+1
αt+1 ‖x∗t − xi,t+1‖2−
√ υ̂i,t
αt ‖x∗t − xi,t+1‖2. (30)
By construction of equation 29, we have√ υ̂i,t+1‖x∗t+1− n
∑ j=1
[W ]i jx j,t+1‖2− √ υ̂i,t+1‖x∗t − n
∑ j=1 [W ]i jx j,t+1‖2
= p
∑ d=1
√ υ̂i,t+1,d〈x∗t+1,d− x∗t,d ,x∗t+1,d + x∗t,d−2 n
∑ j=1 [W ]i jx j,t+1,d〉
≤ 2γ∞ p
∑ d=1
√ υ̂i,t+1,d |x∗t+1,d− x∗t,d |, (31)
where the last inequality holds due to equation 1.
Summing equation 30 over t ∈ {1, . . . ,T}, the first term telescopes, while the second is handled with equation 31. Hence,
T
∑ t=1 (
√ υ̂i,t
αt ‖x∗t −
n
∑ j=1
[W ]i jx j,t‖2− √
υ̂i,t αt ‖x∗t − xi,t+1‖2)
≤ p
∑ d=1
γ2∞ √
υ̂i,1,d α1 + T−1 ∑ t=1 p ∑ d=1
2γ∞ √
υ̂i,t+1,d αt+1 |x∗t+1,d− x∗t,d |+ γ2∞ T−1 ∑ t=1 p ∑ d=1 ( √ υ̂i,t+1,d αt+1 − √ υ̂i,t,d αt )
≤ p
∑ d=1
2γ2∞ √
υ̂i,T,d αT + T−1 ∑ t=1 p ∑ d=1
2γ∞ √
υ̂i,t+1,d αt+1 |x∗t+1,d− x∗t,d |, (32)
where the last inequality follows since from definition of υ̂i,t , we have√ υ̂i,t+1,d αt+1 ≥ √ υ̂i,t,d αt . (33)
Now, summing equation 32 over i ∈ V and using the inequality ∑ni=1 √ υ̂i,t ≤ √ n √
υ̂t , the claim in equation 28 follows.
Lemma 17. Suppose that the parameters β1,β2 ∈ [0,1) satisfy η = β1√β2 < 1. Let β1,t = β1λ t−1,λ ∈ (0,1) and ‖∇ fi,t(x)‖∞ ≤ G∞ for all t ∈ {1, . . . ,T}. Then, using a step-size αt = α√t for the sequence xi,t generated by Algorithm 1, we have
1 n
n
∑ i=1
T
∑ t=1
( fi,t(xi,t)− fi,t(x∗t ) ) ≤ (1−β1)α √ 1+ logT
2 √ (1−β2)
p
∑ d=1 ‖g1:T,d‖+
p
∑ d=1 G∞γ∞ (1−β1)(1−λ )
+ 2α √
1+ logT ∑pd=1 ‖g1:T,d‖ (1−σ2(W )) √ (1−β1) √ (1−η) √ (1−β2)
+ γ2∞√
n
p
∑ d=1
√ T υ̂T,d
(1−β1)α + γ∞√ n
p
∑ d=1
√ T υ̂T,d
(1−β1)α
T−1 ∑ t=1 |x∗t+1,d− x∗t,d |.
Proof. From convexity of fi,t(·), we have
1 n
n
∑ i=1
T
∑ t=1 fi,t(xi,t)− fi,t(x∗t )≤ 1 n
n
∑ i=1
T
∑ t=1 〈∇ fi,t(xi,t),xi,t − x∗t 〉
= 1 n
n
∑ i=1
T
∑ t=1 〈∇ fi,t(xi,t),xi,t+1− x∗t 〉︸ ︷︷ ︸
I1
+ 1 n
n
∑ i=1
T
∑ t=1 〈∇ fi,t(xi,t),xi,t −
n
∑ j=1 [W ]i jx j,t〉︸ ︷︷ ︸ I2
+ 1 n
n
∑ i=1
T
∑ t=1 〈∇ fi,t(xi,t),
n
∑ j=1 [W ]i jx j,t − xi,t+1〉︸ ︷︷ ︸ I3 . (34)
Individual terms in equation 34 can be bounded in the following way. From the Young’s inequality for products3, we have
I3 = 1 n
n
∑ i=1
T
∑ t=1 〈∇ fi,t(xi,t),
n
∑ j=1 [W ]i jx j,t − xi,t+1〉
≤ 1 n
n
∑ i=1
T
∑ t=1
√ υ̂i,t
2αt(1−β1) ‖
n
∑ j=1 [W ]i jx j,t − xi,t+1‖2 + 1 n
n
∑ i=1
T
∑ t=1 (1−β1)αt 2 √ υ̂i,t ‖∇ fi,t(xi,t)‖2. (35)
Note also that:
T
∑ t=1 αtg2i,t,d√ υ̂i,t,d = T−1 ∑ t=1 αtg2i,t,d√ υ̂i,t,d + αT g2i,T,d√ υ̂i,T,d
= T−1
∑ t=1 αtg2i,t,d√ υ̂i,t,d + αg2i,T,d√ T (1−β2) √ ∑Tl=1 β T−l 2 g 2 i,l,d
≤ T−1
∑ t=1 αtg2i,t,d√ υ̂i,t,d + α|gi,T,d |√ T (1−β2) .
3An elementary case of Young’s inequality is ab≤ a22 + b2 2 .
Using Cauchy-Schwarz inequality, equation 19 and equation 27, we have n
∑ i=1
T
∑ t=1 αtg2i,t,d√ υ̂i,t,d ≤ α√ (1−β2) n ∑ i=1 T ∑ t=1 |gi,t,d |√ t
≤ α√ (1−β2) n ∑ i=1 ‖gi,1:T,d‖
√ T
∑ t=1 1 t
≤ α √ 1+ logT√ (1−β2) n ∑ i=1 ‖gi,1:T,d‖ ≤ √ nα √
1+ logT√ (1−β2) ‖g1:T,d‖. (36)
Using equation 35 and equation 36, we have
I3≤ 1 n
n
∑ i=1
T
∑ t=1
√ υ̂i,t
2αt(1−β1) ‖
n
∑ j=1
[W ]i jx j,t − zi,t+1‖2 + (1−β1)
√ nα √ 1+ logT 2 √ (1−β2) ‖g1:T,d‖. (37)
In addition, we have
I2 = 1 n
n
∑ i=1
T
∑ t=1 〈gi,t ,xi,t −
n
∑ j=1 [W ]i jx j,t〉
= 1 n
n
∑ i=1
T
∑ t=1 〈gi,t ,xi,t − x̄t + x̄t −
n
∑ j=1 [W ]i jx j,t〉
= 1 n
n
∑ i=1
T
∑ t=1 〈gi,t ,xi,t − x̄t〉+ 1 n
n
∑ i=1
T
∑ t=1
n
∑ j=1 [W ]i j〈gi,t , x̄t − x j,t〉
= 1 n
n
∑ i=1
T
∑ t=1 〈 √ αtV̂ −1 4 i,t gi,t , V̂
1 4
i,t√ αt (xi,t − x̄t)〉
+ 1 n
n
∑ i=1
T
∑ t=1
n
∑ j=1
[W ]i j〈 √ αtV̂ −1 4 i,t gi,t , V̂
1 4
i,t√ αt (x̄t − x j,t)〉
≤ 1 n
n
∑ i=1
√ T
∑ t=1
αtV̂ −1 2 i,t g 2 i,t √√√√ T∑ t=1 V̂ 1 2 i,t αt (xi,t − x̄t)2
+ 1 n
n
∑ i=1
n
∑ j=1 [W ]i j
√ T
∑ t=1
αtV̂ −1 2 i,t g 2 i,t √√√√ T∑ t=1 V̂ 1 2 i,t αt (x j,t − x̄t)2 (38)
where equation 38 follows from Cauchy-Schwarz inequality.
Now, using equation 38 we obtain
I2 ≤ 1 n
√ n
∑ i=1
T
∑ t=1
p
∑ d=1
αt υ̂ −1 2 i,t,dg 2 i,t,d √√√√ n∑ i=1 T ∑ t=1 p ∑ d=1 υ̂ 1 2 i,t,d αt (xi,t,d− x̄t,d)2
+ 1 n
n
∑ j=1 [W ]i j
√ n
∑ i=1
T
∑ t=1
p
∑ d=1
αt υ̂ −1 2 i,t,dg 2 i,t,d √√√√ n∑ i=1 T ∑ t=1 p ∑ d=1 υ̂ 1 2 i,t,d αt (x j,t,d− x̄t,d)2 (39)
≤ 2α √
1+ logT ∑pd=1 ‖g1:T,d‖ (1−σ2(W )) √ (1−β1) √ (1−η) √ (1−β2) , (40)
where equation 39 utilize Cauchy-Schwarz inequality and equation 40 follows from equation 2, Lemma 15 and equation 36.
To bound I1, using the update rule of m̂i,t in Algorithm 1, we have
〈αt mi,t√
υ̂i,t ,xi,t+1− x∗t 〉= 〈αt( β1,t√ υ̂i,t mi,t−1 + (1−β1,t)√ υ̂i,t ∇ fi,t(xi,t)),xi,t+1− x∗t 〉
= 〈 αtβ1,t√
υ̂i,t mi,t−1,xi,t+1− x∗t 〉+ 〈 αt(1−β1,t)√ υ̂i,t ∇ fi,t(xi,t),xi,t+1− x∗t 〉.
Now, by rearranging the above equality, we obtain: p
∑ d=1 〈 (1−β1,t)√ υ̂i,t,d ∇ fi,t,d(xi,t,d),xi,t+1,d− x∗t,d〉 = p
∑ d=1 〈 mi,t,d√ υ̂i,t,d ,xi,t+1,d− x∗t,d〉+ p ∑ d=1 β1,t√ υ̂i,t,d 〈mi,t−1,d ,x∗t,d− xi,t+1,d〉
≤ 〈 mi,t√
υ̂i,t ,xi,t+1− x∗t 〉+ ||x∗t − xi,t+1||∞
p
∑ d=1 β1,tmi,t−1,d√ υ̂i,t,d
≤ 1 2αt ||x∗t −
n
∑ j=1
[W ]i jx j,t ||2− 1
2αt ||x∗t − xi,t+1||2− 1 2αt ||xi,t+1−
n
∑ j=1 [W ]i jx j,t ||2︸ ︷︷ ︸ (II1)
+ ||x∗t − xi,t+1||∞G∞ p
∑ d=1 β1,t√ υ̂i,t,d︸ ︷︷ ︸
(II2)
, (41)
where (II1) follows from Lemma 12. The term (II2) is obtained by induction as follows: using the assumption, ‖gi,t‖∞ ≤ G∞; now, using the update rule of mi,t in Algorithm 1, we have
‖mi,t‖∞ ≤ (β1 +(1−β1))max(‖gi,t‖∞,‖mi,t−1‖∞) = max(‖gi,t‖∞,‖mi,t−1‖∞)≤ G∞, (42) where ‖mi,t−1‖∞ ≤ G∞ by induction hypothesis.
Note that from our assumption, we have β1,t = β1λ t−1,λ ∈ (0,1) and β1,t ≤ β1. Substituting this into equation 41, we get
I1 = 〈∇ fi,t(xi,t),xi,t+1− x∗t 〉 ≤ √
υ̂i,t (1−β1,t) [ 1 2αt ||x∗t −
n
∑ j=1
[W ]i jx j,t ||2− 1
2αt ||x∗t − xi,t+1||2
− 1 2αt ||xi,t+1−
n
∑ j=1
[W ]i jx j,t ||2]+ ||x∗t − xi,t+1||∞G∞ p
∑ d=1 β1,t (1−β1,t)
≤ √
υ̂i,t (1−β1) [ 1 2αt ‖x∗t −
n
∑ j=1
[W ]i jx j,t‖2− 1
2αt ‖x∗t − xi,t+1‖2]
− √
υ̂i,t (1−β1)2αt ||xi,t+1− n ∑ j=1 [W ]i jx j,t ||2 + γ∞G∞ p ∑ d=1 β1,t (1−β1,t) , (43)
where the last line comes from equation 1.
Plugging equation 37, equation 40, and equation 43 into equation 34, we obtain
1 n
n
∑ i=1
T
∑ t=1
( fi,t(xi,t)− fi,t(x∗t ) ) ≤ (1−β1)α √ 1+ logT
2 √ n √ (1−β2)
p
∑ d=1 ‖g1:T,d‖+ γ∞G∞
T
∑ t=1
p
∑ d=1 β1,t (1−β1,t)
+ 2α √
1+ logT ∑pd=1 ‖g1:T,d‖ (1−σ2(W )) √ (1−β1) √ (1−η) √ (1−β2)
+ 1 n
n
∑ i=1
T
∑ t=1
√ υ̂i,t
2(1−β1) [ 1 αt ||x∗t −
n
∑ j=1 [W ]i jx j,t ||2− 1 αt ||x∗t − xi,t+1||2].
Now, since β1,t = β1λ t−1,λ ∈ (0,1) and β1,t ≤ β1, we have T
∑ t=1 β1,t (1−β1,t) ≤ T ∑ t=1 λ t−1 (1−β1) ≤ 1 (1−β1)(1−λ ) . (44)
Finally, using Lemma 16 and equation 44, we obtain the desired result.
6.1.1 PROOF OF THEOREM 4
Proof. From convexity of fi,t(·) it follows that ft(xi,t)− ft(x∗t ) = ft(xi,t)− ft(x̄t)+ ft(x̄t)− ft(x∗t )
≤ 〈gi,t ,xi,t − x̄t〉+ ft(x̄t)− ft(x∗t )
= 1 n
n
∑ i=1 fi,t(x̄t)− 1 n
n
∑ i=1 fi,t(x∗t )+ 〈gi,t ,xi,t − x̄t〉,
and
ft(xi,t)− ft(x∗t )≤ 1 n
n
∑ i=1 fi,t(xi,t)− 1 n
n
∑ i=1 fi,t(x∗t )+ 〈gi,t ,xi,t − x̄t〉+ 1 n
n
∑ i=1 〈gi,t ,xi,t − x̄t〉. (45)
Summing over t ∈ {1, . . . ,T} and i ∈ V , and applying Lemma 17 and equation 40 gives the desired result.
6.1.2 PROOF OF THEOREM 5
Proof. We just need to rework the proof of Lemma 17 and Theorem 4 using stochastic gradients by tracking the changes. Indeed, using stochastic gradient at the beginning of Lemma 17, we have
T
∑ t=1
( fi,t(xi,t)− fi,t(x∗t ) ) ≤ T
∑ t=1 〈∇ fi,t(xi,t),xi,t − x∗t 〉
= T
∑ t=1 〈∇ fi,t(xi,t),xi,t − x∗t 〉+
T
∑ t=1 〈∇ fi,t(xi,t)−∇ fi,t(xi,t),xi,t − x∗t 〉
= T
∑ t=1 〈∇ fi,t(xi,t),xi,t+1− x∗t 〉+
T
∑ t=1 〈∇ fi,t(xi,t),xi,t −
n
∑ j=1 [W ]i jx j,t〉
+ T
∑ t=1 〈∇ fi,t(xi,t),
n
∑ j=1
[W ]i jx j,t − xi,t+1〉+ T
∑ t=1 〈∇ fi,t(xi,t)−∇ fi,t(xi,t),xi,t − x∗t 〉.
Further, if we replace any bound involving G∞ which is an upper bound on the exact gradient with the norm of stochastic gradient, we obtain
1 n
n
∑ i=1
T
∑ t=1
( fi,t(xi,t)− fi,t(x∗t ) ) ≤ (1−β1)α √ 1+ logT
2 √ n √ (1−β2)
p
∑ d=1 ‖g1:T,d‖+ γ∞‖mi,t−1‖∞
T
∑ t=1
p
∑ d=1 β1,t (1−β1,t)
+ 2α √
1+ logT ∑pd=1 ‖g1:T,d‖ (1−σ2(W )) √ (1−β1) √ (1−η) √ (1−β2)
+ 1 n
n
∑ i=1
T
∑ t=1
√ υ̂i,t
2(1−β1) [ 1 αt ||x∗t −
n
∑ j=1 [W ]i jx j,t ||2− 1 αt ||x∗t − xi,t+1||2]
+ 1 n
n
∑ i=1 〈∇ fi,t(xi,t)−∇ fi,t(xi,t),xi,t − x∗t 〉. (46)
Note that using Assumption 3, we have
E [〈∇ fi,t(xi,t)−∇ fi,t(xi,t),xi,t − x∗t 〉] = 0, and
E [‖∇ fi,t(xi,t)‖]≤ ( E [ ‖∇ fi,t(xi,t)‖2 ]) 12 ≤ ξ .
Hence taking expectation from equation 46, using the above inequality and equation 42, we have
1 n
n
∑ i=1
T
∑ t=1
( E [ fi,t(xi,t)]− fi,t(x∗t ) ) ≤ (1−β1)α √ 1+ logT
2 √ n √ (1−β2)
p
∑ d=1
E [ ‖g1:T,d‖ ] + γ∞ξ T
∑ t=1
p
∑ d=1 β1,t (1−β1,t)
+ 2α √ 1+ logT ∑pd=1E [ ‖g1:T,d‖ ] (1−σ2(W )) √ (1−β1) √ (1−η) √ (1−β2)
+ 1 n
n
∑ i=1 1 2(1−β1) E
[√ υ̂i,t
αt ‖x∗t −
n
∑ j=1
[W ]i jx j,t‖2− √
υ̂i,t αt ‖x∗t − xi,t+1‖2
] .
According to the result in Lemma 16 and equation 44, we have
1 n
n
∑ i=1
T
∑ t=1
( E [ fi,t(xi,t)]− fi,t(x∗t ) ) ≤ (1−β1)α √ 1+ logT
2 √ n √ (1−β2)
p
∑ d=1
E [ ‖g1:T,d‖ ] + p
∑ d=1 ξ γ∞ (1−β1)(1−λ )
+ 2α √ 1+ logT ∑pd=1E [ ‖g1:T,d‖ ] (1−σ2(W )) √ (1−β1) √ (1−η) √ (1−β2)
+ γ2∞√
n
p
∑ d=1
√ TE [√ υ̂T,d ]
(1−β1)α + γ∞√ n
p
∑ d=1
√ TE [√ υ̂T,d ]
(1−β1)α
T−1 ∑ t=1 |x∗t+1,d− x∗t,d |.
Finally, using equation 45 we complete the proof.
Next, we establish a series of lemmas used in the proof of Theorems 8 and 10. Lemma 18. Attouch et al. (2013) Let GX be the projected gradient defied in equation 5. Then, GX (ϖ , fi,α) = 0 if and only if ϖ is a critical point of equation 3.
Next, we show that the projection map GX in Definition 1 is Lipschitz continuous. Lemma 19. Suppose the second moment υ̂ satisfies equation 11. Let x+1,i and x + 2,i be given in
Definition 1 with mi√ υ̂i replaced by m 1 i√ υ̂1i and m 2 i√ υ̂2i , respectively. Then,
‖G1X (xi, f̄i,α)−G2X (xi, f̄i,α)‖ ≤ ῡ υ ‖m1i −m2i ‖, ∀i ∈ V ,
where G1X and G 2 X are the projection maps corresponding to x + 1,i and x + 2,i, respectively.
Proof. Consider the optimality condition of equation 6, for any u ∈X . For each i ∈ V , observe that
〈 m 1 i√ υ̂1i + 1 α (x+1,i− n ∑ j=1 [W ]i jx j),u− x+1,i〉 ≥ 0, (47) 〈 m 2 i√ υ̂2i + 1 α (x+2,i− n ∑ j=1 [W ]i jx j),u− x+2,i〉 ≥ 0. (48)
Taking u = x+2,i in equation 47, we have
〈m1i ,x+2,i− x + 1,i〉 ≥
√ υ̂1i
α 〈
n
∑ j=1 [W ]i jx j− x+1,i,x + 2,i− x + 1,i〉. (49)
Likewise, setting u = x+1,i in equation 48, we get
〈m2i ,x+1,i− x + 2,i〉 ≥
√ υ̂2i
α 〈
n
∑ j=1 [W ]i jx j− x+2,i,x + 1,i− x + 2,i〉. (50)
Now, using equation 49, equation 50 and equation 11, we obtain
‖m1i −m2i ‖ ≥ υ α ‖x+2,i− x + 1,i‖. (51)
Without loss of generality, assumes that √ υ̂1i ≤ √ υ̂2i . Then, using equation 5, we have
‖G1X (xi, f̄i,α)−G2X (xi, f̄i,α)‖= ‖
√ υ̂1i
α (x− x+1,i)−
√ υ̂2i
α (x− x+2,i)‖
≤ ‖
√ υ̂1i
α (x− x+1,i)−
√ υ̂1i
α (x− x+2,i)‖
(i) ≤ ῡ
α ‖x+2,i− x + 1,i‖
(ii) ≤ ῡ
υ ‖m1i −m2i ‖,
where (i) follows from equation 11 and (ii) follows from equation 51.
Lemma 20. Let β1,β2 ∈ [0,1) satisfy η = β1√β2 < 1. Then, for the sequence xi,t generated by Algorithm 1, we have
1 n
n
∑ i=1 ‖xi,t − x∗t ‖ ≤
2 √ n (1−η) √ (1−β2) t−1 ∑ s=0 αsσ t−s−12 (W ) := Bt .
Proof. In the proof of Lemma 15 we showed that
xi,t+1− x̄t+1 = t
∑ s=0
n
∑ j=1 ([W t−s]i j− 1 n )ei,s.
Now, using the above equality, we have
‖xi,t+1− x̄t+1‖= t
∑ s=0
n
∑ j=1 |[W t−s]i j− 1 n |‖ei,s‖. (52)
Also, using Lemma 14, we get
mi,t√ υ̂i,t ≤ 1 (1−η) √ (1−β2) . (53)
The above inequality together with the update rule of xi,t+1, imply that
‖ei,t‖= ‖xi,t+1− n
∑ j=1
[W ]i jx j,t‖= ‖ΠX [ n
∑ j=1
[W ]i jx j,t −αt mi,t√
υ̂i,t ]−
n
∑ j=1 [W ]i jx j,t‖
≤ ‖ n
∑ j=1
[W ]i jx j,t −αt mi,t√
υ̂i,t −
n
∑ j=1 [W ]i jx j,t‖
= αt‖ mi,t√
υ̂i,t ‖
≤ αt (1−η) √ (1−β2) , (54)
where the first inequality follows from the nonexpansiveness property of the Euclidean projection4.
Substituting equation 26 and equation 54 into equation 52, we get
‖xi,t − x̄t‖ ≤ √ n (1−η) √ (1−β2) t−1 ∑ s=0 αsσ t−s−12 (W ).
Summing the above inequality over i ∈ V , we conclude that n
∑ i=1 ‖xi,t − x∗t ‖ ≤
n
∑ i=1 ‖xi,t − x̄t‖+
n
∑ i=1 ‖x̄t − x∗t ‖ ≤
2n √ n (1−η) √ (1−β2) t−1 ∑ s=0 αsσ t−s−12 (W ).
4‖ΠX [x1]−ΠX [x2]‖ ≤ ‖x1− x2‖, ∀x1,x2 ∈ Rp.
Lemma 21. For the sequence xi,t generated by Algorithm 1, we have
〈∇ f̄i,t ,GX (xi,t , f̄i,t ,αt)〉 ≥ (2−β1,t)
2(1−β1,t) ‖GX (xi,t , f̄i,t ,αt)‖2− β1,t υ̂i,t 2(1−β1,t)(1−η)2(1−β2) .
Proof. A quick look at optimality condition of equation 6 verifies that
〈 mi,t√
υ̂i,t + 1 αt (xi,t+1− n ∑ j=1 [W ]i jx j,t),z− xi,t+1〉 ≥ 0, ∀z ∈X .
Substituting z = xi,t into the above inequality, we get
〈 mi,t√
υ̂i,t ,xi,t − xi,t+1〉 ≥ 1 αt 〈xi,t+1−
n
∑ j=1 [W ]i jx j,t ,xi,t+1− xi,t〉.
Now using equation 2, we have√ υ̂i,t
αt ‖xi,t − xi,t+1‖2 ≤ 〈mi,t ,xi,t − xi,t+1〉= 〈β1,tmi,t−1 +(1−β1,t)∇ f̄i,t ,xi,t − xi,t+1〉 = β1,t √
υ̂i,t−1 αt
〈 αtmi,t−1√
υ̂i,t−1 ,xi,t − xi,t+1〉+(1−β1,t)〈∇ f̄i,t ,xi,t − xi,t+1〉
≤ β1,t √
υ̂i,t 2αt ( α2t (1−η)2(1−β2) +‖xi,t − xi,t+1‖2)+(1−β1,t)〈∇ f̄i,t ,xi,t − xi,t+1〉,
where the first equality follows from the update rule of mi,t . The last inequality is valid since CauchySchwarz inequality and inequality √ υ̂i,t−1β1,t ≤ √ υ̂i,tβ1. The claim then follows after using Definition 1.
6.1.3 PROOF OF THEOREM 8
Proof. Let f̄i,t(xi,t) = 1t ∑ t s=1 fi,s(xi,t). Using Assumption 2, Taylor’s expansion and Definition 1, we have
f̄i,t(xi,t+1)≤ f̄i,t(xi,t)+ 〈∇ f̄i,t(xi,t),xi,t+1− xi,t〉+ ρ 2 ‖xi,t+1− xi,t‖2
≤ f̄i,t(xi,t)− αt√ υ̂i,t 〈∇ f̄i,t(xi,t),GX (xi,t , f̄i,t ,αt)〉+ ρα2t 2υ̂i,t ‖GX (xi,t , f̄i,t ,αt)‖2.
The above inequality together with Lemma 21, equation 11 and β1,t ≤ β1, imply that
f̄i,t(xi,t+1)≤ f̄i,t(xi,t)− αt(2−β1)
2ῡ ‖GX (xi,t , f̄i,t ,αt)‖2
+ αtβ1,t ῡ
2(1−β1,t)(1−η)2(1−β2) + ρα2t 2υ2 ‖GX (xi,t , f̄i,t ,αt)‖2. (55)
Let ∆i,t = f̄i,t(xi,t)− f̄i,t(x∗t ) denotes the instantaneous loss at round t. We have
∆i,t+1 = t t +1 ( f̄i,t(xi,t+1)− f̄i,t(x∗t+1))︸ ︷︷ ︸
(I)
+ 1
t +1 ( fi,t+1(xi,t+1)− fi,t+1(x∗t+1)). (56)
Note that (I) can be bounded as follows:
f̄i,t(xi,t+1)− f̄i,t(x∗t+1)≤ f̄i,t(xi,t+1)− f̄i,t(x∗t )≤ ∆i,t − [ (2−β1)αt 2ῡ − ρα 2 t 2υ2 ]‖GX (xi,t , f̄i,t ,αt)‖2
+ αtβ1,t ῡ
2(1−β1,t)(1−η)2(1−β2) , (57)
where the first inequality is due to the optimality of x∗t and the second inequality follows from equation 55.
Now, combining equation 57 and equation 56 gives
∆i,t+1 ≤ t
t +1 (∆i,t − [ (2−β1)αt 2ῡ − ρα 2 t 2υ2 ]‖GX (xi,t , f̄i,t ,αt)‖2
+ αtβ1,t ῡ
2(1−β1,t)(1−η)2(1−β2) )+ 1 t +1 ( fi,t+1(xi,t+1)− fi,t+1(x∗t+1)).
By rearranging the above inequality, we have t
t +1 [ (2−β1)αt 2ῡ − ρα 2 t 2υ2 ]‖GX (xi,t , f̄i,t ,αt)‖2 ≤ t t +1 (∆i,t + αtβ1,t ῡ 2(1−β1,t)(1−η)2(1−β2) )
+ 1
t +1 ( fi,t+1(xi,t+1)− fi,t+1(x∗t+1))−∆i,t+1. (58)
Using the definition of ∆i,t+1, we get 1t+1 ( fi,t+1(xi,t+1)− fi,t+1(x ∗ t+1))−∆i,t+1 =−( t t+1 )( f̄i,t(xi,t+1)− f̄i,t(x∗t+1)). Hence, using equation 58 and simplifying terms, we obtain
[ (2−β1)αt 2ῡ − ρα 2 t 2υ2 ]‖GX (xi,t , f̄i,t ,αt)‖2
≤ ∆i,t − ( f̄i,t(xi,t+1)− f̄i,t(x∗t+1))+ αtβ1,t ῡ
2(1−β1,t)(1−η)2(1−β2) . (59)
Note that: 1 n n ∑ i=1 T ∑ t=1 ( ∆i,t − ( f̄i,t(xi,t+1)− f̄i,t(x∗t+1)) ) =
1 n
n
∑ i=1
T
∑ t=1
( ( f̄i,t(xi,t)− f̄i,t(xi,t+1))− ( f̄i,t(x∗t )− f̄i,t(x∗t+1)) ) =
1 n
n
∑ i=1 [− f̄i,T (xi,T+1)+ f̄i,1(xi,1)− f̄i,1(x∗1)+ f̄i,T (x∗T+1)]
+ 1 n
n
∑ i=1
T
∑ t=2
t−1 ( fi,t(xi,t)− f̄i,t−1(xi,t)− ( fi,t(x∗t )− f̄i,t−1(x∗t )) )
(60)
≤ 1 n
n
∑ i=1
L ( ‖xi,T+1− x∗T+1‖+‖xi,1− x∗1‖+ T
∑ t=2
2t−1‖xi,t − x∗t ‖ )
(61)
≤ 2L max t∈{2,...,T}
Bt(1+ T
∑ t=2 t−1)≤ 2L max t∈{2,...,T} Bt(2+ logT ), (62)
where the first equality uses
f̄i,t(xi,t)− f̄i,t−1(xi,t) = t−1( fi,t(xi,t)− f̄i,t−1(xi,t)). The first inequality follows from Assumption 2. The second inequality follows from Lemma 20 and equation 19.
Summing equation 59 over i ∈ V , t ∈ {1, . . . ,T} and using equation 62, we have 1 n n ∑ i=1 min t∈{1,...,T} ‖GX (xi,t , f̄i,t ,αt)‖2 T ∑ t=1 [ (2−β1)αt 2ῡ − ρα 2 t 2υ2 ]
≤ 1 n
n
∑ i=1
T
∑ t=1
[ (2−β1)αt 2ῡ − ρα 2 t 2υ2 ]‖GX (xi,t , f̄i,t ,αt)‖2
≤ (2+ logT )2L max t∈{2,...,T}
2 √ n (1−η) √ (1−β2) t−1 ∑ s=0 αsσ t−s−12 (W )
+ T
∑ t=1 αtβ1,t ῡ 2(1−β1,t)(1−η)2(1−β2) . (63)
Note that ∑Tt=1[ (2−β1)αt 2ῡ − ρα2t 2υ2 ] > 0. Therefore, dividing both sides of the equation 63 by ∑Tt=1[ (2−β1)αt 2ῡ − ρα2t 2υ2 ], we obtain equation 14.
6.1.4 PROOF OF COROLLARY 9
Proof. With the constant step-sizes αt = (2−β1)υ 2 2ρῡ for all t ∈ {1, . . . ,T}, we have
ϑt = T
∑ t=1
[ (2−β1)αt 2ῡ − ρα 2 t 2υ2 ] = T (2−β1)2υ2 8ρῡ2 .
Therefore, using the above equality and equation 12 together with αt = (2−β1)υ 2
2ρῡ for all t ∈ {1, . . . ,T}, we obtain
1 ϑt
T
∑ t=1 αtβ1,t ῡ 2(1−β1,t)(1−η)2(1−β2) = 4ῡ T (2−β1)
T
∑ t=1 β1,t ῡ 2(1−β1,t)(1−η)2(1−β2)
≤ 4ῡ T (2−β1)
T
∑ t=1 λ t−1ῡ 2(1−β1)(1−η)2(1−β2)
≤ 2ῡ 2
T (2−β1)(1−β1)(1−η)2(1−β2)(1−λ ) , (64)
and
1 ϑt (2+ logT )2L max t∈{2,...,T}
2 √ n (1−η) √ (1−β2) t−1 ∑ s=0 αsσ t−s−12 (W )
≤ 16ῡ(2+ logT )L √ n T (2−β1)(1−η) √ (1−β2) max t∈{2,...,T} t−1 ∑ s=0 σ t−s−12 (W ) ≤ 16ῡ(2+ logT )L √ n
T (2−β1)(1−η) √ (1−β2)(1−σ2(W )) . (65)
Combine the results in equation 64 and equation 65, we have equation 13.
6.1.5 PROOF OF THEOREM 10
Proof. Let δi,t =∇ f̄i,t(xi,t)−∇ f̄i,t(xi,t), ∀t ≥ 1,
where ∇ f̄i,t(xi,t) = 1t ∑ t s=1∇ fi,s(xi,t) denotes the minibatch stochastic gradient on node i.
Since fi,t is ρ-smooth, it follows that f̄i,t is also ρ-smooth. Hence for every i∈ V and t ∈ {1, . . . ,T}, we have
f̄i,t(xi,t+1)≤ f̄i,t(xi,t)+ 〈∇ f̄i,t(xi,t),xi,t+1− xi,t〉+ ρ 2 ‖xi,t+1− xi,t‖2
≤ f̄i,t(xi,t)− αt√ υ̂i,t 〈∇ f̄i,t(xi,t),GX (xi,t , f̄i,t ,αt)〉+ ρα2t 2υ̂i,t ‖GX (xi,t , f̄i,t ,αt)‖2 = f̄i,t(xi,t)− αt√ υ̂i,t 〈∇ f̄i,t(xi,t),GX (xi,t , f̄i,t ,αt)〉+ ρα2t 2υ̂i,t ‖GX (xi,t , f̄i,t ,αt)‖2 + αt√ υ̂i,t 〈δi,t ,GX (xi,t , f̄i,t ,αt)〉,
where GX (xi,t , f̄i,t ,αt) denotes the projected stochastic gradient on node i.
The above inequality together with Lemma 21, equation 11 and β1,t ≤ β1, imply that
f̄i,t(xi,t+1)≤ f̄i,t(xi,t)− αt(2−β1)
2ῡ ‖GX (xi,t , f̄i,t ,αt)‖2 + αtβ1,t ῡ 2(1−β1,t)(1−η)2(1−β2)
+ ρα2t 2υ2 ‖GX (xi,t , f̄i,t ,αt)‖2 + αt√ υ̂i,t 〈δi,t ,GX (xi,t , f̄i,t ,αt)〉 + αt√ υ̂i,t 〈δi,t ,GX (xi,t , f̄i,t ,αt)−GX (xi,t , f̄i,t ,αt)〉
≤ f̄i,t(xi,t)− αt(2−β1)
2ῡ ‖GX (xi,t , f̄i,t ,αt)‖2 + αtβ1,t ῡ 2(1−β1,t)(1−η)2(1−β2)
+ ρα2t 2υ2 ‖GX (xi,t , f̄i,t ,αt)‖2 + αt√ υ̂i,t 〈δi,t ,GX (xi,t , f̄i,t ,αt)〉 + αt√ υ̂i,t ‖δi,t‖‖GX (xi,t , f̄i,t ,αt)−GX (xi,t , f̄i,t ,αt)‖
≤ f̄i,t(xi,t)− αt(2−β1)
2ῡ ‖GX (xi,t , f̄i,t ,αt)‖2 + αtβ1,t ῡ 2(1−β1,t)(1−η)2(1−β2)
+ ρα2t 2υ2 ‖GX (xi,t , f̄i,t ,αt)‖2 + αt√ υ̂i,t 〈δi,t ,GX (xi,t , f̄i,t ,αt)〉 + αt√ υ̂i,t ‖δi,t‖ ῡ υ t ∑ r=1 (1−β1,r)β t−r1 ‖δi,r‖, (66)
where the second inequality follows from the Cauchy-Schwartz inequality. The last inequality follows from the fact that β1,t = β1λ t−1,λ ∈ (0,1) and Lemma 19 if we set G1X (xi, f̄i,α) = GX (xi,t , f̄i,t ,αt), and G2X (xi, f̄i,α) = GX (xi,t , f̄i,t ,αt).
Let ∆i,t = f̄i,t(xi,t)− f̄i,t(x∗t ) denotes the instantaneous stochastic loss at time t. We have
∆i,t+1 = t t +1 ( f̄i,t(xi,t+1)− f̄i,t(x∗t+1))︸ ︷︷ ︸
(I)
+ 1
t +1 ( fi,t+1(xi,t+1)− fi,t+1(x∗t+1)). (67)
Observe that (I) can be bounded as follows:
f̄i,t(xi,t+1)− f̄i,t(x∗t+1)≤ f̄i,t(xi,t+1)− f̄i,t(x∗t )≤ ∆i,t − [ (2−β1)αt 2ῡ − ρα 2 t 2υ2 ]‖GX (xi,t , f̄i,t ,αt)‖2
+ αtβ1,t ῡ
2(1−β1,t)(1−η)2(1−β2) + αt√ υ̂i,t 〈δi,t ,GX (xi,t , f̄i,t ,αt)〉+ ῡαt υ2 t ∑ r=1 β t−r1 ‖δi,r‖‖δi,t‖, (68)
where the first inequality is due to x∗t+1 ∈X and the optimality of x∗t and the second inequality is due to equation 66 and the fact that 0≤ β1,r < 1. Thus, using equation 67 and equation 68, we get
∆i,t+1 ≤ t
t +1
( ∆i,t − [
(2−β1)αt 2ῡ − ρα 2 t 2υ2 ]‖GX (xi,t , f̄i,t ,αt)‖2 + αtβ1,t ῡ 2(1−β1,t)(1−η)2(1−β2)
+ αt√ υ̂i,t 〈δi,t ,GX (xi,t , f̄i,t ,αt)〉+ ῡαt υ2 t ∑ r=1
β t−r1 ‖δi,r‖‖δi,t‖ ) + 1 t +1 ( fi,t+1(xi,t+1)− fi,t+1(x∗t+1)).
By rearranging the above inequality, we have
t t +1 [ (2−β1)αt 2ῡ − ρα 2 t 2υ2 ]‖GX (xi,t , f̄i,t ,αt)‖2 ≤ t t +1
( ∆i,t +
αtβ1,t ῡ 2(1−β1,t)(1−η)2(1−β2)
+ αt√ υ̂i,t 〈δi,t ,GX (xi,t , f̄i,t ,αt)〉+ ῡαt υ2 t ∑ r=1
β t−r1 ‖δi,r‖‖δi,t‖ )
+ 1
t +1 ( fi,t+1(xi,t+1)− fi,t+1(x∗t+1))−∆i,t+1. (69)
Now, using definition of ∆i,t+1, 1t+1 ( fi,t+1(xi,t+1)− fi,t+1(x ∗ t+1))− ∆i,t+1 = −( t t+1 )( f̄i,t(xi,t+1)− f̄i,t(x∗t+1)), together with equation 69, we obtain
[ (2−β1)αt 2ῡ − ρα 2 t 2υ2 ]‖GX (xi,t , f̄i,t ,αt)‖2 ≤ ∆i,t − ( f̄i,t(xi,t+1)− f̄i,t(x∗t+1))
+ αtβ1,t ῡ
2(1−β1,t)(1−η)2(1−β2) + αt√ υ̂i,t 〈δi,t ,GX (xi,t , f̄i,t ,αt)〉+ ῡαt υ2 t ∑ r=1 β t−r1 ‖δi,r‖‖δi,t‖. (70)
Note that from Assumption 3, we have E [ 〈δi,t ,GX (xi,t , f̄i,t ,αt)〉 ] = 0 and
E [ ‖∇ fi,t(xi,t)−∇ fi,t(xi,t)‖2 ] = E [ ‖∇ fi,t(xi,t)‖2 ] −‖E [∇ fi,t(xi,t)]‖2 ≤ E [ ‖∇ fi,t(xi,t)‖2 ] ≤ ξ 2,
which implies that E [ ‖δi,t‖2 ] = E [ ‖∇ f̄i,t(xi,t)−∇ f̄i,t(xi,t)‖2 ] = E [ ‖1
t
t
∑ s=1
(∇ fi,s(xi,t)−∇ fi,s(xi,t))‖2 ]
≤ 1 t
t
∑ s=1
E [ ‖∇ fi,s(xi,t)−∇ fi,s(xi,t)‖2 ] ≤ ξ 2.
The above inequality together with Cauchy-Schwarz for expextations, imply that E [‖δi,t‖‖δi,r‖]≤ √ E [‖δi,r‖2] √ E [‖δi,t‖2]≤ ξ 2. (71)
Now, using equation 71 and equation 62, summing equation 70 over i ∈ V and t ∈ {1, . . . ,T}, and taking expectation, we obtain
1 n
n
∑ i=1 min t∈{1,...,T}
E [ ‖GX (xi,t , f̄i,t ,αt)‖2 ] T ∑ t=1 [ (2−β1)αt 2ῡ − ρα 2 t 2υ2 ]
≤ T
∑ t=1
[ (2−β1)αt 2ῡ − ρα 2 t 2υ2 ] 1 n n ∑ i=1
E [ ‖GX (xi,t , f̄i,t ,αt)‖2 ] ≤ (2+ logT )2L max
t∈{2,...,T}
2 √ n (1−η) √ (1−β2) t−1 ∑ s=0 αsσ t−s−12 (W )
+ T
∑ t=1 αtβ1,t ῡ 2(1−β1,t)(1−η)2(1−β2) + ῡξ 2 υ2 T ∑ t=1 αt t ∑ r=1 β t−r1 . (72)
Note that ∑Tt=1[ (2−3β1)αt 2ῡ − ρα2t 2υ2 ]> 0, and
T
∑ t=1
αt t
∑ r=1
β t−r1 = T
∑ t=1
αt T
∑ r=t
β r−t1 ≤ T
∑ t=1 αt (1−β1) . (73)
Therefore, dividing both sides of the equation 75 by ∑Tt=1[ (2−3β1)αt 2ῡ − ρα2t 2υ2 ], using equation 73, we complete the proof.
6.1.6 PROOF OF COROLLARY 11
Proof. Let ϑt = ∑Tt=1[ (2−β1)αt 2ῡ − ρα2t 2υ2 ]. We claim that if
T ≥max{ 4ρ 2ῡ2
nυ4(2−β1)2 , 4ῡ2n (2−β1)2 }, (74)
then ϑt ≥ 1/2. One can easily seen that T must satisfy (2−β1)αt2ῡ − ρα2t 2υ2 ≥ 1 2T which results in
−T ρα2t ῡ +T υ2(2−β1)αt − ῡυ2 ≥ 0.
By rearranging the above inequality, we obtain
1≥ ραt ῡ υ2(2−β1) + ῡ T (2−β1)αt := A1 +A2.
Now, if A1,A2 ≤ 12 , then αt ≤ υ2(2−β1) 2ρῡ , and αt ≥ 2ῡ T (2−β1) , respectively. These bounds together with our assumption on αt give equation 74.
Now, let equation 74 holds. Using equation 70, and since ϑt ≥ 1/2, we have 1
T n
n
∑ i=1 min t∈{1,...,T}
E [ ‖GX (xi,t , f̄i,t ,αt)‖2 ] ≤ 2
T n
n
∑ i=1 min t∈{1,...,T}
E [ ‖GX (xi,t , f̄i,t ,αt)‖2 ] T ∑ t=1 [ (2−β1)αt 2ῡ − ρα 2 t 2υ2 ]
≤ 2 T
T
∑ t=1
[ (2−β1)αt 2ῡ − ρα 2 t 2υ2 ] 1 n n ∑ i=1
E [ ‖GX (xi,t , f̄i,t ,αt)‖2 ] ≤ 2
T n
n
∑ i=1
( fi,1(xi,1)− fi,1(x∗1) ) +L ( ‖xi,T+1− x∗T+1‖+ T
∑ t=2
2t−1‖xi,t − x∗t ‖ )
+ 2 T
T
∑ t=1 αtβ1,t ῡ 2(1−β1,t)(1−η)2(1−β2) + 2ῡξ 2 υ2(1−β1)T T ∑ t=1 αt , (75)
where the last inequality follows from equation 60, equation 61 and equation 71.
We proceed to bound RHS of equation 75. By substituting αt = α√nT and β1,t = β1λ t−1,λ ∈ (0,1) into the last two terms of equation 75, we have
2ῡξ 2
υ2(1−β1)T
T
∑ t=1
αt = 2αῡξ 2
υ2(1−β1) √ nT , (76)
and 1 T T ∑ t=1 αtβ1,t ῡ (1−β1,t)(1−η)2(1−β2) = αῡ T √ nT (1−η)2(1−β2) T ∑ t=1 β1,t (1−β1,t)
= αῡ
T √ nT (1−η)2(1−β2)(1−β1)(1−λ ) . (77)
Further, using equation 75 and Lemma 20, we get
L T n
n
∑ i=1 ‖xi,T+1− x∗T+1‖ ≤
2 √
nαL T (1−η) √ (1−β2) √ nT T ∑ s=0 σT−s2 (W )
≤ 2 √
nαL T (1−η) √ (1−β2) √ nT (1−σ2(W )) . (78)
Similarly, using equation 75 and Lemma 20, we have
L T n
n
∑ i=1
T
∑ t=2
t−1‖xi,t − x∗t ‖ ≤ 2 √
nαL√ nT (1−η) √ (1−β2)T T ∑ t=2 t−1 t−1 ∑ s=0 σ t−s−12 (W )
≤ 2 √
nαL√ nT (1−η) √ (1−β2)T
√ T
∑ t=2 t−2
√ T
∑ t=2
( t−1
∑ s=0 σ t−s−12 (W ))2
≤ 2 √
nαL√ nT (1−η) √ (1−β2)T (1−σ2(W )) , (79)
where the second inequality is due to Cauchy-Schwarz inequality and the last inequality follows because ∑Tt=2 1 t2 ≤ 1.
Using equation 16a, equation 77, equation 78 and equation 79 are bounded by equation 76. This completes the proof.
6.2 SENSITIVITY OF DADAM TO ITS PARAMETERS
Next, we examine the sensitivity of DADAM on the parameters related to the network connection and update of the moment estimate. As it is clear from Figure 3 the convergence of training accuracy value happens faster for sparser networks (higher σ2(W )). This is similar to the trend observed for FedAvg algorithm while reducing parameter C which makes the agent interaction matrix sparser. This is also expected as discussed in Theorems 4 and 5. Note that with the availability of a central parameter server (as in FedAvg algorithm), sparser topology may be useful for a faster convergence, however, topology density of graph is important for a distributed learning scheme with decentralized computation on a network.
We also empirically evaluate the effect of the β3 in Algorithm 1. We consider a range of hyperparameter choices, i.e. β3 ∈ {0,0.9,0.99}. From Figure 4 it can be easily seen that DADAM per-
forms equal or better than AMSGrad (β3 = 0), regardless of the hyper-parameter setting for β1 and β2.

Review summaries:
This paper presents a consensus-based decentralized version of the Adam algorithm for online optimization. The authors consider an empirical risk minimization objective, which they split into different components, and propose running a separate online optimization algorithm for each component, with a consensus synchronization step that involves taking a linear combination of the parameters from each component before applying each component's individual parameter update. The final output is a simple average of the parameters from each component.