Asynchronous Training Schemes in Distributed Learning with Time Delay
Authors: Haoxiang Wang
Zhanhong Jiang
Chao Liu
Soumik Sarkar
Dongxiang Jiang
Young M Lee
Venue: Accepted by TMLR ()

Abstract: In the context of distributed deep learning, the issue of stale weights or gradients could result in poor algorithmic performance. This issue is usually tackled by delay tolerant algorithms with some mild assumptions on the objective functions and step sizes. In this paper, we propose a different approach to develop a new algorithm, called \textbf{P}redicting \textbf{C}lipping \textbf{A}synchronous \textbf{S}tochastic \textbf{G}radient \textbf{D}escent (aka, PC-ASGD). Specifically, PC-ASGD has two steps - the \textit{predicting step} leverages the gradient prediction using Taylor expansion to reduce the staleness of the outdated weights while the \textit{clipping step} selectively drops the outdated weights to alleviate their negative effects. A tradeoff parameter is introduced to balance the effects between these two steps. Theoretically, we present the convergence rate considering the effects of delay of the proposed algorithm with constant step size when the smooth objective functions are weakly strongly-convex, general convex, and nonconvex. One practical variant of PC-ASGD is also proposed by adopting a condition to help with the determination of the tradeoff parameter. For empirical validation, we demonstrate the performance of the algorithm with four deep neural network architectures on three benchmark datasets.

Published in Transactions on Machine Learning Research (MM/YYY)
Asynchronous Training Schemes in Distributed Learning with Time Delay
Haoxiang Wang
whaa22@mail..siigguua...c
Deportment of Automation Tsinghua University
Zhanhong Jiang
zhjiang@iustatee Wiustate. edu
Translational AI Center lowa State University
Chao Liu
cliu5 cliu5@tsinghua. edu.cn
Department of Energy and Power Engineering Tsinghua University
Soumik Sarkar
soumiks Siastate.ceoecoo edu
Deportment of Mechanical Engineering
lowa State Universily
Dongxiang Jiang
Atsigghh@tssiguuua.com edd..cr
Department of Energy and Power Engineering Tsinghua University
Young M. Lee Johnson Controls
young. wew.g.m..ee@jjsccom
Reviewed on OpenReview: https: // openreview. net/ forum? id= a0CJmu07Z6
Abstract
In the context of distributed deep learning, the issue of stale weights gradients could result in poor algorithmic performance. This issue is usually tackled by delay tolerant algo- rithms with some mild assumptions on the objective functions and step sizes. In this paper, we propose a different approach to develop a new algorithm, called Predicting Clipping Asynchronous Stochastic Gradient Descent (aka, PC-ASGD). Specifically, PC-ASGD has two steps the predicting step leverages the gradient prediction using Taylor expansion to reduce the staleness of the outdated weights while the clipping step selectively drops the outdated weights to alleviate their negative effects. A tradcoff parameter is introduced to balance the effects between these two steps. Theoretically, present the convergence rate considering the effects of delay of the proposed algorithm with constant step size when the smooth objective functions are weakly strongly-conee general convex, and nonconvex. One practical variant PC-ASGD is also proposed by adopting a condition to help with the determination the tradeoff parameter. For empirical validation, we demonstrate the per- formance of the algorithm with four deep neural network architectures on three benchmark datasets.
1 Introduction
The availability of large datascts and powerful computing led to the emergence of deep learning that is revolutionizing many application sectors from the internet industry and healthcare to transportation and energy Gijzen (201)): Wiedemann el all (2019) Gao all (2022); Lin & Lui (2023) As the applications

---

Published in Transactions on Machine Learning Research (MM/YYY)
scaling up, the learning process of large deep learning models is looking to leverage emerging resources such as edge computing and distributed data centers privacy preserving. In this regard, distributed deep learning algorithms are being explored by the community that leverage synchronous and asynchronous computations with multiple computing agents that exchange information over communication networks Lian ct all (207Z); Cao all (2023); Qian el al. (2022). We consider an example selting involving an industrial ToT framework where the data geographically distributed as well as the computing resources. While the computing resources within a local cluster can operate in (loosely) synchronous manner, multiple (geographically distributed) clusters may need to operate in asynchronous manner. Furthermore, communications among the computing resources may not be reliable and prone to delay and loss of information.
The master-slave and peer-to-peer are two categories of distributed learning architectures. On one hand, Federated Averaging and its variants are considered to be the state-of-the-art for training deep learning
models with data distributed among the edge computing resources such as smart phones and idle computers
Hard et (20);; Saftler all (20H). PySyft Ryttel et all (2018) and its robust version Deng et al. (2020).
the scalable distributed DNN training algorithms Strom (20T) and more recent. distributed SVRG Cen el all
(21IT) and clustered FL Sattler at (АЛЛА] are examples of the master-slave architecture.
On the other
hand, examples of the pecr-to-peer architecture include the gossip algorithms Blot cf all (20T6): Even ct al
(2022)
Li Liet.am all (2122T): [T ct all (2122), and the collaborative learning frameworks giang et a..
21 ml (11
However, as mentioned earlier, communication delay remains a critical challenge for achieving convergence in an asynchronous learning setting Ch (2Iл)); Isianos et al (2012) and affects the performances of the frameworks above. Furthermore, the amount of delay could be varying widely due to artifacts of wireless communication and different devices. To eliminate the negative impact of varying delays the convergence characteristies of distributed learning algorithms, this work proposes a novel algorithm, called Predicting Clipping Asynchronous Stochastic Gradient Descent (aka, PC-ASGD). The goal is to solve the distributed learning problems involving multiple computing or edge devices such as GPUs and CPUs with varying communication delays among them. Different from traditional distributed learning scenarios where synchronous and asynchronous algorithms are considered separately, we take both into account together in networked sctting.
Table 1: Comparisons between asynchronous algorithms
Methods
f
V
Delay Ass.
Con.Rater
D.C.
G.C.
A.S.
ASGD Dean all (2133)
Non-convex
Lip.
Bou.
O
X
x
X
Str-con
Tap.
Bou.
x
/
X
DC-ASGD Zheng
411
Non-convex
Tip.
Bon.
O
/
D-ASGD Lian el (1
Non-convex
&
Bou.
O
/
x
DC-s3dg Rigazz
Non-convex
Lip.
Unbou.
N/A
/
/
x
ACP Aistrati & (6imma
Str-con
Lip.
Bou.
OG
TV
T
/
x
x
Praque Luo ef
[X1
Non-convex
Lip.
Bou.
N/A
/
x
DSGD-AAU Xiong et al
Non-convex
Lip.
Bou.
O
x
DGD-ATC Win (211K)
Str-con
Lip.
Unbou.
Olp")
/
x
AD-APD Abollazh Al
(212%)
Convex
Lip.
Bou.
O
8
Weakly Str-con
Lip.
Bou.
O(p
+
PC-ASCD (This paper)
Convex
Lip.
Bou.
O
1 P
Non-convex
Lip.
Bou.
O
Rate: convergence rate, Str-con: strongly convex. Lip.& Bou.: Lipschitz continuous and bounded. Delay Ass.: Delay Assumption.
Unbou.: Unbounded. T: Total iterations. D.C.: decentralized computation. G.C.: Gradlent Compensation. A.S.: Alternant Step, P (0, 1) is positive constant. Note that the convergence rate PC-ASGD is obtained by using the constant step size. E (0, I).
Related work. In the early works on distributed learning with master-slave architecture, Asynchronous Stochastic Gradient Descent (ASGD) algorithm has been proposed Deaa all (2MB), where cach local worker continues its training process right after its gradient is added to the global model. The algorithm could tolerate the delay in communication. Later works Agarwal & Duch (201)); Feyzmahdavian et all (2016) Recht al (20IT); Zhuang et al. (202I) extend ASGD to more realistic scenarios and implement the algorithms with a central server and other parallel workers. Typically, since asynchronous algorithms suffer from stale gradients, researchers have proposed algorithms such DC-ASGD Zheng el. all (2017), adopting
2

---

Published in Transactions on Machine Learning Research (MM/YYYY)
the concept of delay compensation to reduce the impact of staleness and improve the performance of ASGD. For the distributed learning with peer-to-peer architecture, Lian el (2017) proposes an algorithm termed AD-PSGD (decentralized ASGD algorithm, aka D-ASGD) that deals with the problem of the stale parameter exchange, as well as presents theoretical analysis for the algorithm performance under bounded delay. Liang BLal (2021) also proposes similar algorithm with slightly different assumptions. However, these algorithms do not provide empirical or theoretical analysis regarding the impact of delay in detail. Additional works such
as using central agent for control Nair & Gupta (2017), requiring prolonged communication Issanos Rabe
bat (2016), utilizing stochastic primal-dual method Lan et all (2020), and adopting importance sampling Du Et alll (2020), have also been done to address the communication delay in the decentralized setting. More (201)) proposes the DC-s3gd algorithm to enable large-scale decentralized neural network training with the consideration of delay. Zakharod (2122),, Venigalla el al. (2020), Chen el all (20T)) and
recently, Rigazzi
Abbasino Clas (201 also develop algorithms of asynchronous decentralized training for neural networks, while thcoretical guarantce is still missing. Asynchronous version of stochastic gradient push (AGP) Assran & Rabbal (2020) is developed to address the asynchronous training in mulli-agent framework. The authors claim that AGP is more robust to failing stalling agents, than the synchronous first-order methods. While the proposed algorithm is only applicable to the strongly convex objectives. To further advance this area, the most recent schemes such as Praque Luo-et all (2n2r) adopting a partial all-reduce communcattin primitive, DSGD-AAU Xiong et. all (202)) utilizing an adaptive asynchronous updates, DGD-ATC Wi el all (2023) extending the Adapt-then selap-then-Commine technique from synchronous algorithms, and AD-APD Abolazh et al (2023) leveraging accelerated primal-dual algorithm, are developed, but most of them are limited to ouly (strongly) convex cases, Another line of work based on Federated Learning Dmm et all (202%); Gamboad Montero all (2023); Miao et. all (2023); Xn et all (2028); Zhang et all (2028) has also recently received considerable attention, while all proposed approaches essentially rely a center server, which may threat
the privacy of local workers. Different from the aforementioned works, in this study, we specifically present analysis of the impact of the communication delay on convergence error bounds.
Contributions. The contributions of this work are specifically as follows:
Algorithm Design. novel algorithm, called PC-ASGD for distributed learning is proposed to tackle the convergence issues due to the varying communication delays. Built upon ASGD, the PC-ASGD algorithm consists of two steps. While the predicting step leverages the gradient prediction using Taylor expansion to reduce the staleness of the outdated weights, the clipping step selectively drops the outdated weights to alleviate their negative effects. To balance the effects, a tradeoff parameter is introduced to combine these two steps.
Converyence guarantee. We show that with proper constant step size, PC-ASGD can converge to the neighborhood of the optimal solution at a lincar rate for weakly strongly-convex functions while at sublinear rate for both generally convex and nonconvex functions (specific comparisons with other related existing approaches are listed in Table M). We also model the delay and take it into consideration in the convergence analysis.
Verificution studies. PC-ASGD is deployed on distributed GPUs with three datasets CIFAR-10, CIFAR-100, and TinyImageNet by using Net DenseNet, ResNet20, and EfficientNNt chitectures. Our proposed algorithm outperforms the existing delay tolerant algorithms as well as the variants of the proposed algorithm using only the predicting step or the clipping step.
2 Formulation and Preliminaries
Consider N agents in networked system such that their interactions are driven by a graph G, where G = (V,E), where V = (1, (1, N) indicates the node or agent set, & C V x V is the edge set. Throughout the paper, we assume that the graph is undirected and connected. The connection between any two agents and j can be determined by their physical connections, Icading to the communication between them. Traditionally, if agent j is in the neighborhood of agent i, they can communicate with each other. Thus, we define the neighborhood for any agent i as Nb(i) == (i E V)( E & or = i). Rather than considering
3

---

Published in Transactions on Machine Learning Research (MM/YYYY)
synchronization and asynchronization separately, this paper considers both scenarios together by defining the following terminologies.
Definition 1. At time step agent j is called reliable neighbor of the agent i if agent i has the stote information of agent) j up to 1.
Definition 2. At time step t, an agent j is called an unreliable neighbor of the agent if agent i has the stale information of agent only up to T, where T is the so-called delay and 1 < xc.
Remark: Definitions D and @ allow us to perceive the delay problem the decentralized learning with a new perspective that depends on the amount of delay. One agent can selectively make use of the outdated information from unreliable neighbors or completely drop such information. The first scenario related most previous works on asynchronous delay tolerant approaches it involves gradient prediction technique to reduce the negative effects of stale parameters. The second scenario corresponds to most synchronous schemes since the agent only collects information from the reliable neighbors. In this paper, mainly focus on the fixed delay with a connected graph to better characterize the influence of delay. Real cases with complex lopology and Lime-varying delay modeling are essential but future extensions of the work.
Thus, inside the neighborhood of an agent, there are reliable and unreliable neighbors respectively. This work aims at studying how to effectively tackle issues such as negative impacts that delays may bring on the performance. We define set for reliable neighbors of agent as: R == (j E Nb(i) Pr(x' 10) = 1}, implying that agent has the state information x up to the time t - 1, i.e. x2-1- We can directly have the set for unreliable neighbors such that R = -Nb R m
Then we can consider the decentralized empirical risk minimization problems, which can be expressed as the summation of all local losses incurred by each agent:
N min F(x) = Σ Σ (z)
(1)
1=1 sED.
the local copy of x E R2, D, is a local data set uniquely known by agent i, f : IRd + R the incurred local loss of agent given a sample s. Based on the above formulation, we then assume everywhere that our objective function is bounded from below and denote the minimum by F":= F(x*) where x" argmin F(x). Hence F* > -c. Moreover, all vector norms refer to the Fuclidean norm while matrix norms refer to the Frobenius norm. Some necessary definitions and assumptions are given below for characterizing the main results.
where x = [=";=";...;;"", x²
Each objective function fi is assumed to satisfy the following conditions: a) fo is 7/- smooth; b) Js is proper (not everyahere insinile) and coercive.
Assumption 1.
Assumption 2. A mixing matrir W. E RNNN satisfies a) 1 = 11,W1 = =1T 6) Nullf1 - W = Span(1}; c) > W > -I.
Assumption 3. The stochastic gradient of F at any x is denoted by g(x), such that a) g(x) is the unbiased estimate of gradient Fx()); b) The variance is uniformly bounded by o², Le.,E]ll((() - FF(x) o²; c)
The second moment of g(x) is bounded,, i.e., [[[lg(x)][]] G
Given Assumption M. one immodiate consoquence that F is Ym == max(%). /2.x///.......... .2...... 7N smoohh at all x E RdN, The main outcome of Assumption 2 is that the mixing matrix W doubly stochastic matrix and that we have e (W)- 1 e2 (W) 2 .. 2 ex (W) -1, where e, (W) denotes the z-th largest eigenvalue of W Zeng & Yin 2 In Assumption B. the first two are quite generic. While the third part is much weaker than the bounded gradient that is not necessarily applicable to quadratic-like objectives.
Remark:
Note that the delay varies in the asynchronous learning scheme, and there two types of asynchronization, (i) fixed value of delays Zheng et (20Tо); Rigazz] (21)g) and (ii) time-varying delays Dean alll (201)); Man (21T22) along the learning process. We follow the first setting this work to implement the experiments.
4

---

Published in Transactions on Machine Learning Research (MM/YYY)
3 PC-ASGD
3.1
Algorithm Design
We present the specific update law for our proposed method, PC-ASGD. In Algorithm II for the predicting step (line 6), any agent k that is unreliable has a delay when communicating its weights with agent To compensate for the delay, we adopt the Taylor expansion approximate the gradient for each time step. The predicted gradient (or delay compensated gradient) is denoted by gh (xk_,), which is expressed as follows
9h (x) = E ge (x + )gx(a;_.) o 92 (x())))) 2 (d/-r4r - xi_r),
(2)
where À is positive constant in (0, 1] and the term >ge(=*=>) (00g((()-)))) is an estimate of the Hessian matrix, (ox( Throughout the rest of analysis, we define gk de.t (xf == (x(x)-r) + Agu (*f(x))) +) O gu (x)-->) o (si-rtr - ={_r). We briefly provide explanation for the ease of understanding, while referring interested readers to Appendix A2.2 for the details of the derivation of Eq. 0. For agent k, at the current time step t, since it did not get updated over the past T time steps, it is known that x == =t_.. By abuse of notation, we use of (x/->) instead of o (xf)) for the predicted gradient, as the former reasonably justifies Eq. D. While we still keep the parameter of at in the predicting step since it will be convenient for us to derive the compact step in the following. However, one can also replace æ with oř- if necessary. Additionally, the communication scheme for the predicting step among agents remains similar as in Jiang et. all (2017) but our method needs extra communication overhead in the predicting step for the gradient information of (x(=->)) This burden can be further reduced by gradient quantization Alistarh of all (2017) but beyond the scope of our work.
Also, the term (+)--t-- - x(-r) is from agent i due to the inaccessible outdated information of agent k which intuitively illustrates that the compensation is driven by the agent i when agent h is in its neighborhood and deemed an unreliable one. We remark that the replacement by using agent i is reasonably feasible due to the following three reasons. First, the individual model difference decays along with time for all agents in the network. Particularly, as agent is in the neighborhood of agent i, the decaying trend between (xf-rtr- - x{_r) and (a/-+tr- at should be similar. Second, such a replacement assumption to bound the difference, e.g-,
Remark:
may cause an extra error term in the error bound if imposing [[ =(-+)= - (ağ =f-,)]l S c, where 2 0, but the overall convergence rate remains the same as the step size plays a role to determine it Finally, the empirical results show the feasibility of such a replacement. If the replacement caused the divergence of the gradient norm, the training loss and testing accuracy would be poor. In our practice, we carcfully examine thoir difference to make sure the replacement proceeds well. However, due to the replacement, the predicted gradient is approximate.
On the contrary, at the time instant t, when the clipping step is taken, intuitively, we have to clip the agents that possess outdated information, resulting in the change of the mixing matrix W. Essentially, we can manipulate the corresponding weight values Way, R in W. such that at the clipping step, Way = 0. E R For the convenience of analysis, we introduce W to represent the mixing matrix at this step. This seems a bit unnecessary in terms of formulation as the first part in the predicting step can be used for the clipping step, while for analysis it would help clarify, particularly when we show the convex combination in line 8. Additionally, though the first part in the predicting step is essentially the same as the clipping step, the scparation between them in Algorithm I would make the presentation clear about that these two steps take place in single update.
Different from the DC-ASGD, which significantly relies on central server to receive information from each agent, our work removes the dependence on the central server, and instcad constructs a graph for all of agents. The clipping step (line 7) essentially rejects information from all the unreliable neighbors in the neighborhood of one agent. Subsequently, the equality in line 8 balances the tradeoff between the predicting and clipping steps. In practice, the determination of 6g results in some practical variants. In the empirical study presented in Section 5, one can see that 6, is either 0 or by leveraging one condition, which implies that in each epoch, only one step is adopted, yielding two other variants shown in the experiments, C-ASGD
5

---

Published in Transactions on Machine Learning Research (MM/YYY)
Algorithm 1: PC-ASGD
Input:
number of agents N, learning rate > 0, agent interaction matrices W, W number of epochs T, the tradeoff paramcter 2 0 I 1, E 10. 1}
Output: the models' parameters in agents z/,1 1,2, 1: Initialize all the agents' parameters zy 1,,.....
Do broadcast identify the clusters of reliable agents and the delay T
1=0
while epoch < 7 do for each agent do
6: Predicting Step: zit1,pre = EjER Wiyel - ng((1;) + ENER wit - -ng (2,_
7: Clipping Step: "Ht1cl EEJENOO) (.sja (z/((())
'/41 = 0
0,) 0,)0
end for
10: t=
11: end while
P-ASGD. However, for the sake of generalization, we provide the analysis for the combined steps (line 8). In practice, we try practical strategy for adaptive 0 choices and we also show the effectiveness empirically.
Since the term ΣeER (x/=>) applics to unreliable neighbors only, for the convenience of analysis, we expand it the whole graph. means that we establish an expanded graph to cover all of agents by setting some elements in the mixing matrix W E NNN oqual to O, but keeping the same connections as W. Namely, we have w 0, R and w = wa, k R By setting the current time as t T, the compact form in line 8 can be rewritten as:
Xi+r+1 W4+ ng((x(+T) + Oetr Σ Ew'
W'gdar dor (x:))
Wi+ is denoted by 0,,, W + (1 W, where W= W & Iaxa, W = W & Laxd, and W = W' & laxd- We have deferred the derivation of Eq. & the Appendix.
4 Convergence Analysis
This section presents convergence results for the PC-ASGD. We show the consensus estimate and the optimal- ity for both weakly strongly-convex (Polyal--ojjaiewiicz Condition Karimi et all (2016)) generally convex, and nonconvex smooth objectives. The consensus among agents (aka, disagrocment estimate) can be thought of as the norms ||æ; - æ/ the differences between the iterates of and x/- Alternatively, the consensus can be measured with respect to reference sequence, i.e., Yt N EN z/. In particular, we discuss ||=] yell for any time f as the metrics with respect to the delay т.
Lemma 1. (Consensus) Let Assumptions 2 and 3 hold. Assume that the delay compensated gradients are uniformly bounded, i.e., there exists a scalar > 0, such that
de. (xx)ll S B, Vt 2 and 0 S
Then for all illie V and 2 0, Bn 0, we have
G + (T L)BBm
Elllat vell <
(4)
1 82
where Om mar(0s+1) 1+r-1 82 max 0.e2 + (1 - ) < 1, where e2 == =e2(W) < and ?2 ==
ex(W) < 1.
The detailed proof shown in the Appendix. Lemma states the consensus bound among agents, which is proportional to the step size n and inversely proportional the gap between the largest and the second- largest. magnitude eigenvalues of the equivalent graph W.

---

Published in Transactions on Machine Learning Research (MM/YYYY)
One implication that can be made from Lemma 1 is when T = 1, the consensus bound becomes the nGC This bound is the same obtained already by most decentralized smallest, which can be obtained as I-82
Remark:
learning (or optimization) algorithms. This accordingly implies that the delay compensated gradient or prodicted gradient does not necossarily require many time steps. Otherwise, more compounding error could be included. Alternatively, On = can also result. in such a bound, suggesting that. the clipping step dominates the update. On the other hand, once T >> and 6.. * 0, the consensus bound becomes worse, which will be validated by the empirical results. Additionally, if the network is sparse, which suggests e2 + and éअ 1, the consensus among agents may not be achieved well and correspondingly the optimality would be negatively affected, which has been justified in existing works Jiang et al. (20T7).
Most previous works have typically explored the convergence rate on the strongly convex objectives. However, the assumption of strong convexity can be quite strong in most models such that the results obtained may be theoretically instructive and useful. Hence, we introduce a condition that is able to relax the strong convexity, but still maintain the similar theoretical property, i.c., Polyak--ojasiewicz (PL) condition Karimi et (2016). The condition is expressed follows: A differentiable function F satisfies the PL condition such that there exists a constant P > 0
1 |VF(x)]| 2 (F((x) - F)).
(5)
2
When F(x) strongly convex, it also implies the PL condition. However, this is not vice versa. We now state the first main result.
Theorem 1. Let Assumptions 1,2 and hold. Assume that the delay compensated gradients are uniformly bounded, i.e., there exists a scalar B > 0 such that
llgdorr xs))lssB B, 2 and 0 1
(6)
and that VF(x)) is 5m smooth for all 2 O. and the objective satisfies the PL condition, they satisfy
Then for the iterates generated by PC-ASGD, when 0 < r S 2μt
Q
Q
B[F(x,) - F+ s (1- 2 1 (F(x)) F
F*]
+
(7)
2
2pM
where
3 r-1
Q Gpn1-1 +
Σ
C, + 22
2
(8)
T-1
+ GijTa + Gfm + +eD + + X)G2) r=1
Σ
Cr + 1/2 + +n
and C1 = ()-Brr))Bmm C. ()+(r-1)BB C2 20+(r-1)BBm eD > 0 and > O are upper bounds for the 1-
bg approcimation errors of the Hessian matrix that can be obtained as we describe in the Appende
82
Remark: One implication from Theorem M is that PC-ASGD enables the itcrates (x,} to converge to the Q neighborhood of x", which is 2mprr matching the results by Diang et all (2um7); (Botonn all (201)): Patrascn Necoara (2017). In addition, Theorem M shows that the error bound is significantly attributed to network errors caused by the disagreement among agents with respect to the delay and the variance of stochastic gradients. Another implication can be made from Theorem to the delay and the step size such that when the delay is large it may reduce the coefficient, 1 2,uyT, to speed up the convergence. However, correspondingly the upper bound of the step size is also reduced. Hence, there is Tradeoff between the step size and the delay in PC-ASGD. Theorem M also suggests that when the objective function only satisfies the PL condition and is smooth, the convergence to the neighborhood of x" in a lincar rate can still be achieved. The PL condition may not necessarily imply convexity and honce the conclusion can even apply to some nonconvex functions. To further analyze the error bound, we define
that the convergence rate is closely related
2The proof for this theorem is fairly non-trivial and technical. We refer readers the Appendix for more details. To simplify the proof, this main result will he divided into several lemmas.
7

---

Published in Transactions on Machine Learning Research (MM/YYYY)
7= 0 PC-ASGD PC-ASGG enjoys convergence rate of O(p' + + vi) to the neighborhood of which becomes G(2(1- - 2 + To G).
Studying the convergence behavior of PC-ASGD for generally convex functions is critically vital as many objectives in machine learning fall into this category of interest. However, the proof techniques for showing the convergence are different from those shown for the above weakly strongly convex objectives. In the sequel, well-known result regarding convexity is first introduced and then the theoretical claim is presented, while its associated proof is deferred to the Appendix.
Lemma 2. If F: Rd + R is convez and differentiable, then for all æ, E RR, the following holds:
F(x) + I y)
(9)
Theorem 2. Let Assumptions 1, 2 and 9 hold. Assume that the delay compensated gradients uniformly bounded, i.e., there erists scalar B > O such that for all T 21
lg (xx) S B, V2 0 and 0 05rST-L
(10)
and there exists C > O,
E||x; x11] S SC,
(11)
where x* E argminn(x)). Then for the ileralions generaled by PC-ASGD, there erists 0 < 1 < that
such
207m
x1 -x-x 12
A
ExF(XT) - =F
+
(12)
Tn
where A = 107 C2 65 05 2m 22 24Gh
G+(r-1)B80m
o :
1-62
E Ellg(x)) FF XT -'=1x,
Remark: As Theorem 2 suggests, when F is generally convex; asymptotically, PC-ASGD yields the con- vergence of the iterates {xx) to the neighborhood of x", which is 4 Analogously, Theorem Ø shows that the error bound is highly correlated with the consensus estimates among agents and the stochastic gradient variances as well as the time delay. To further analyze the error bound, we still define the = O }
PC-ASGD exhibits a convergence rate of O 1 + +TiE) to the neighborhood of x", which is 2C - 1)6,, B. .T
This implies that if there is no time delay, PC-ASGD converges to the optimal solution exactly. Also, the convergence rate matches the state-of-the-art in both centralized Garrigos & Gower (2023); Khaled et all (2123) and distributed Nedid (2121); Sun ell (2122); Choi & Kim (2112) settings. In Theorem 2 we also impose a constraint for the distance between x; and x". Immediately, we know that the error bound in Eq. 12 can become C² A which is relatively looser. On the other hand, without such a constraint, we can Tw +
probably just use ||x; |= < | - =x'|| to replace C, which enables a slightly tighter bound. This also illustrates that Eq. [T] is not strong constraint.
We next investigate the convergence for the non-convex objectives. For PC-ASGD, we show that it converges to a first-order stationary point at a sublinear rate. It should be noted that such a result may not absolutely guarantce a fcasible minimizer due to the lack of some necessary sccond-order information. However, for most nonconvex optimization problems, this is generic, though some existing works have discussed the second-order stationary points Carmon et all (2ME), which is out of our investigation scope.
Theorem 3. Let Assumptions 1, 2 and 9 hold. Assume that the delay compensated gradients are uniformly bounded, i.e., there erists a scalar B > O such that for all T 2
dlg (xx))l S B, VE 0 and 05r
(13)
and there exists M > O,
Ellg (x)))( < M.
(14)
Then for the iterations generated by PC-ASGD, there exists < 1) < 1
such that
T T
2(F(x)) F*)
R
(15)
Tn
1
8

---

Published in Transactions on Machine Learning Research (MM/YYYY)
where, R 2G = + no² 2 + +110 B 7m ( + C G+(7-1)BB, 1-62
Remark: Theorem & states that with properly chosen constant step size, PC-ASGD is able to converge the iterates {xr} to the noisy neighborhood of a stationary point x" in rate of 0 v whose radius is a² + we can know that the determined by & +oTB if we define n 1 ( Additionally, based on 2
error bound is mainly caused by the variance of stochastic gradients and the time delay. As the length of the delay can have an impact on the predicting steps used in the delay compensated gradient, a short term prediction may help alleviate the negative effect causod by the stale agents. Otherwise, the compounding error in the delay compensated gradient could deteriorate the performance of the algorithm.
5 Experiments
5.1 Practical Variant
So far, we have analyzed theoretically in detail how the proposed PC-ASGD converges with some mild assumptions. In practical implementation, we need to choose a suitable 0, to enable the training fast with clipping steps and allow the unreliable neighbors to be involved in training with predicting steps. In this context, we develop a heuristic practical variant with a criterion for determining the tradeoff parameter value. Intuitively, if the delay messages from the unreliable neighbors do not influence the training negatively, they should be included in the prediction. This can be determined by the comparison with the algorithm without. making use of these messages. The criterion is shown follows:
(0 (x)))
(0) +1 (x:))
={ sit1pre
10 211
(16)
21+1,els
O.W0
where we choose the cosine distance to compare the distances for predicting and clipping steps. The prediction step is selected if it has the larger cosine distance, which implies that the updale due to the predicting step yields the larger loss descent. Otherwise, the clipping step should be chosen by only trusting reliable neighbors. Our practical variant with this criterion still converges since we just set O, as 0 or for each iteration and the previous analysis in our paper still holds. To facilitate the understanding of predicting and clipping steps, in the following experiments, we also have two other variants P-ASGD and C-ASGD. While the former corresponds to an "optimistic" scenario to only rely on the predicting step, the latter presents a "pessimistic" scenario by dropping all outdated agents. Both variants follow the same convergence rates induced by PC-ASGD. The specific algorithm is shown as Algorithm !
5.2 Distributed Network and Learning Setting
Models and Data sets. D-ASGD adopted as the baseline algorithm. Two deep learning structures, NreResNet110 He all (21T6)) DenseNet [Huan et all (21177), ResNet20 [Heett (2016a) and Efficient Net Tan K Ld (201)) (noted model 1, model 2, model 9 and model 4), are employed. The detailed training settings are illustrated in Appendix Q CIFAR-10, CIFAR-100 and TinyImageNet are used in the experiments following the settings in Krizhevsky (2)22. The training data is randomly assigned to each agent, and the parameters of the deep learning structure are maintained within each agent and communicated with the predefined delays. The testing set is utilized for each agent to verify the performance, where our metric is the average accuracy among the agents. 6 runs are carried out for each case and the mean and variance are obtained and listed in Table
Delay setting. The delay is set agents outside of the reliable cluster are the ones that were obtained 7 itcrations before. is both fixed at 20 to test the performances of different algorithms including our different variants (P-ASGD, C-ASGD, and PC-ASGD) and baseline algorithms in Section 5 and S.E We also try to exploit its impact in Section b.l
discussed before, which means the parameters received from the
Distributed network sctting. A distributed network (noted as distributed network 1) with 8 agents (nodes) in a fully connected graph is first applied with model 1-4, and 2 clusters of reliable agents are defined within the graph consisting of 3 agents and 5 agents, respectively. Then two distributed networks (with
9

---

Published in Transactions on Machine Learning Research (MM/YYY)
Algorithm 2: PC-ASGD-PV
Input: number of agents N, learning rate > 0, agent interaction matrices W, W, number of epochs T
Output: the models' parameters in agents z7,1 = 1.2...... N
1: Initialize all the agents' parameters vi, i 1,2....,
2: Do broadcast to identify the clusters of reliable agents and the delay T
t ==
while epoch < T do for each agent do Predicting Step: sit1pre = LjER Wiyzt ()/((=)))) + EMERE win (al
-1gh ( (st_+)
7:
Clipping Step: #1+1,oli = -EjRR JER Wiget - (1))
pre =x/+1, 11+t1ppe Fii Anti F2+1,chi x.
9: if (1))
(x))) A
then
p
10:
1 11t1,pre
11:
else
12:
-/-1 r 1.id
13:
end if
14:
end for
15:
t=t+1
16: end while
5-agent and 20-agent, respectively) are used for scalability analysis, noted distributed network 2 and distributed network 8, individually. For distributed network 2, we construct clusters of reliable agents with and 2 agents. In distributed network 3, four clusters are formed and 3 clusters consist. of 6 agents while each the rest has 2 agents.
5.3 Performance Evaluation
The testing accuracies on the CIFAR-10 and CIFAR-100 data sets with model and model in distributed network I are shown in Fig. It shows that the proposed PC-ASGD outperforms the other single variants and it presents accuracy increment greater than 2.3% (nearly 4% for DenseNet with CIFAR-10) compared to the baseline algorithm. For other variants P-ASGD C-ASGD, the testing accuracies are also higher than that of the baseline algorithm. Moreover, PC-ASGD shows faster convergence than P-ASGD as the updating rule overcomes the staleness, and achieves better accuracy than the C-ASGD as it includes the messages from the unreliable neighbors. This consistent with the analysis in this work. We also show the detailed results of both distributed nelwork and distribuled nelwork in Table
We then compare our proposed algorithu with other delay-tolerant algorithms in distributed network with model 1-4, including the baseline algorithm D-ASGD, DC-s3gd Rigazzi (2IIH)) D-ASGD with IS Du Et all (2020),, and Adaptive Braking /Vengalla el. all (202T). The distributed network 1 is applied for the comparisons. From Table 3 the proposed PC-ASGD obtains the best results in all the cases. It should be noted that some of above-listed algorithms are not designed specifically for this kind of peer-to-peer application (e.g., Adaptive Braking) or may not consider the modeling of severe delays in their works (e.g., D-ASGD with and DC-s3gd). In this context, they may not perform well in the test cases. The results also demonstrate our proposed framework can be employed by differential types of models, such as simple ResNet20 and complex EfficientNet. We also conduct numerical studies Tiny and time-series dataset in Appendix D the results also verify the effectiveness of our method. Before concluding this section, we remark on the difference between PC-ASGD and DC-s3gd as the latter also leverages the predicting step for the gradient estimates. In our PC-ASGD approach, we dilferentiate between reliable and unreliable agents, allowing reliable agents to proceed with their updates. For unreliable agents, our method incorporates both predicting and clipping steps, establishing choice criteria enhance overall performance. s3gd exclusively employs prediction (delay compensation) for all agents. Regarding the delay compensation aspect, for agent requiring update, our approach employs delay compensation with the delayed gradient.
contrast, DC-
10

---

Published in Transactions on Machine Learning Research (MM/ (YYY)
14.5-
66.4
04.1-
1427
CAAGDD
Reuder
175
spoda
(a) DenseNet CIFAR-10
(b) DenseNet CIFAR-100
40
spodla
<poda
(c) PreResNett10 CIFAR-10
(d) Nee11sNet110 CIFAR-100
Figure 1: Testing accuracy on CIFAR-10 and CIFAR-100 with distributed network 1.
Table 2: Performance evaluation of PC-ASGD on CIFAR-10 and CIFAR-100
agents
PC-ASGD
P-ASGD
C-ASGD
Baseline
Model & dataset
acc. (%)
o.p. (%)
acc. (%) o.p. (%) a%c. o.p. (%)
acc. (%)
Prel10, CIFAR-10
87.3
1.1
4.1
84.9 = 0.9 0.9 8.0
2.0
+ 1.0 84.0 + 0.3
Prel10, CIFAR-100
67.4 1.4 3.1 64.8 + 1.3 1.5 66.4
1.9
+
1.6 64.5 + 1.5
Des, CIFAR-10
86.9 1 0.9
3.8
84.4 + 0.6
1.0 1.5 85.9
0.9
2.7
1.7
83.3
E 0.9
Des, CIFAR-100
68.6 = 0.6
2.3 1.7
66.8 + 1.5 1.6 + 1.6
66.8 + 1.6
1.8 + 1.6 66.1 + 1.9
20 agents P-ASGD
PC-ASGD
C-ASGD
Baseline
Model & dataset
acc, (%)
o.p. (%)
acc. (%) o.p. (%) acc.
o.p. (%)
acc. (%)
Prel10, CIFAR-10
84.7 = 0.9
4.0 83.3 = 0.9 2.7
8.
1.9
80.4
Pre110, CIFAR-100
62.4
0.8
61.7 2.0
2.0
61.5
2.
59.3 1.7
Des, CIFAR-10
82.9 = 0.9 0.9 0.7
1.4
8.6
1.8
80.1 0.9
Des, CIFAR-100
64.5 0.7 1.7 62.5 1.3 2.9
62.0
1.5
1.3
1.4
60.4 1.7
aac.uaccur,yy, oop--outperoommed comparing to baseline.
of agent k in the unreliable cluster, denoted of utilizing the term (x) (=;-x1/ x/-7). (x)-x(_,). Conversely, DC-s3gd utilizes (af - z²_r) without any thcoretical guarantee. We hypothetically claim that though it is feasible for us to leverage the same predicting step employed in DC-s3gd, while in practice, (#f - -xp_) may cause larger error bound when models between agents and & are significantly different. We can also compare the algorithm employing only P-stop (P-ASGD), as presented in Table 0 (with 5 agents) with DC-s3gd in Table G. The results also reveal that certain scenarios (Prel10/Des, CIFAR100), the performance of P-step is better than that of DC-s3gd, which supports our approximation of gle well.
11

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Table 3: Performance comparison for different algorithms
Prel 10 CIFAR-10
Des CIFAR-10
20
Pre110
Des CIFAR-100 68.6 = 0.6
Efficient
Model & dataset
CIFAR-10
CIFAR-100
CIFAR-100 78.5 = 1.3
PC-ASGD (Ours)
87.3 = 1.1
86.9 = 0.6
84.9 + 0.6
67.4 + 1.4
D-ASGD
84.0 + 0.3
82.5 0.1
83.3 0.9
64.5 1.5
66.1 1.9
74.7 0.4
Lian all (2017)
DC-s3gd
86.3 0.8
85.7 0.8
83.1
63.5
66.2
76.0 + 1.1
Rigazzi 2
D-ASGD with IS
85.0 0.3
84.6 0.4
83.1 0.5
64.6 1.2
66.2 :: 0.8
75.5 + 1.4
Di et all
(2)20)
Adaptive Braking
86.8 + 0.9
85.3 1.0
84.3 + 0.4
66.5 + 1.2
6..3
77.3 + 0.8
Venigalaa et al.
2122
5.4 Impacts of Different Delay Settings
To further show our algorithm's effectiveness, also implement experiments with different delays. As discussed above, more severe delay could cause significant drop in the accuracy. More numerical studies with different steps of delay are presented here. The delays are set as 5, 20, 60 with our PreResNet1 10 (model 1) of agents (synchronous network without delay is also tested). We use CIFAR-10 the studies and the topology is distributed nelwork The results are shown Fig.
90
87.3
87.6
86.8
$7.3
86.3
$5.4
84.0
84.2
82.3
$0
75
Spockenssto PCASCD
DCidel
65
Sychrrnnuu
Figure 2: Performance evaluation for different steps of delay.
We can find out as the delay increases, the accuracy decreases. For the synchronous setting, the testing accuracy is close to that in the centralized scenario YYngg (2019) but with higher batch size. When the delay is 60, the accuracy for the D-ASGD reduces significantly, and this validates that the large delay significantly influences the performance and causes difficulties in the training process. However, the delays are practical in real implementations such as industrial IoT platforms. Our proposed PC-ASGD outperforms other algorithms all cases with different delays. Morcover, the accuracy drop is relatively smaller cases with larger delays, which suggests that PC-ASGD more robust to different communication delays.
5.5 Impacts of Network Size
For evaluating the performance in different structure sizes of distributed networks, distributed network 2 and distribuled network follow the same setting as in the distribuled network (delay т = 20, model 1, CIFAR-10). The results are shown Fig. 3 According to both Table and Fig. E, as the number of agents increases, the accuracy decreases. It shows that the large size of the network has negative impact on the training. Our proposed PC-ASGD outperforms all other approaches, which further validates the efficacy and scalability of the proposed algorithm.
12

---

Published in Transactions on Machine Learning Research (M//YYY)
35
90
68,0
65.2
$6.2
$6.7
87.1
K5,0
84.99
50.0
86.3
36.8
84.0
84.7
83.3
82,5
$3.1
62.9
80.4
50
P-ASCO
C-ASGD
DC5dgl
agents
agents
agents
Figure 3: Performance evaluation for different numbers of agents.
5.6 Numerical Studies on 0 Assignments
We also conduct empirical studies about the different choices for 0. As we mentioned above, a practical variant is applied for 8, where we intend to form a strategy to determine if the received information (parameters of the deep learning modols) is outdated or not. Here, different assignment rules for are tested and compared. Model 1 is applied, by using CIFAR-10 and the 8 agents system with 3 and 5 agents (distributed network 1).
First, 0 is fixed as 0.3, 0.5, 0.7 (denoted as fl, f2, f3), respectively. Then we determine the @ as 0, 1 randomly with fixed probability in each round with 0.3, 0.5, 0.7 (denoted as pl, p2, p3). We also try the fully uniformly random assigned 0 in each round (denoted as rf). The results are listed in Table E The PC-ASGD-PV
Table 4: Mcan Performance for Different assignment for Pre110, CIFAR-10
Method Parameters
ʃ1/p1
f2/p2
ƒ3/p3
0 Fixed
86.3
85.0
84.5
0 Bool randomly
85.6
85.0
84.1
0 randomly (rl)
85.2
PC-ASGD-PV
87.3
ABASGD(Bassliigg
84.0
obtains the best performance which implics that the trade-off between the predicting step and the clipping step in Algorithm Ø is proper and plays important role in the convergence process. With the fixed 0 (first row '0 fixed'), the experimental results show that the optimal ratio between the predicting step and clipping step is 0.3 in this case. And this suggests that more clipping steps are better. For the pl, p2, p3 cases (second row 9 Bool randomly, ie. either 0 or 1), the experimental results show that the optimal probability between the predicting step and clipping step is 0.3. This is consistent with the fixed case. Compared with the fix 0 setting, picking for the 0 in a predefined probability performs worse. The randomness still helps the convergence process but is not good as the fix 0 setting. For the random 6, the randomness helps the convergence process. However, there exists an optimal 0 for every case and the randomness is not able get the best performance. The baseline D-ASGD gets the worst performance, which shows the predicting and clipping steps are helpful for the scenarios with delays in the distributed network. This also provides us with the necessity of the additional time cost for the predicting and clipping steps. Note also that optimizing the selection of beneficial and we can set as binary or non-binary (continuous). The binary setting with the strategy in Algorithm D is straightforward and performs well in this work.
To further explore the connection between the 0 selection and the binary strategy in our algorithm, the occurrence of choosing the predicting step or clipping step in PC-ASGD-PV is collected and shown in Fig. H. The frequencics for the clipping and predicting step choices tend to stabilize with the epochs when the values are around 0.625 and 0.375 respectively. This is consistent with the fixed 0 experiments (where the optimal ratio between the predicting step and clipping step is 0.3, compared to 0.5 and 0.7.) The final choice frequency appears to be empirically determined by the proportion of unrcliable clusters. It indicates that the proportion of delayed information included by these unreliable clusters will determine the likelihood of rejecting the P-step. Additionally, we also observe 0 will increase the time delay diminishes to be smaller
13

---

Published in Transactions on Machine Learning Research (MM/YYYY)
empirically. However, cannot construct proportional relationship since adopt some approximations when dealing with P-step and more theoretical and empirical analysis can be an interesting future direction.
04-
Figure 4: Predicting and clipping steps choices changing with epochs.
5.7 Time Cost Comparison
The time cost for the presented algorithm is compared with the baseline algorithm (D-ASGD), P-ASGD, and C-ASGD. The average time costs for model with CIFAR-10 in distributed network are collected and shown in Fig. E. The hardware we adopt is shown in Appendix Q
1.8
LBt
0.6
05
PC-AGGD PANG
CASGD
D-AGG
Figure 5: Average time costs for different methods (per epoch).
We observe that the extra time costs the predicting and clipping steps and additional criterion are not large, although there are still 17% more costs compared D-ASGD, Therefore, we need consider the trade- off before implementing the proposed algorithm. However, with the improvement of the local computing resources and the architecture design, the extra time cost might be acceptable with the gains in performance. Moreover, the extra time cost. is not changed with the delay, while the boosting in the performance is more significant in large delays (as shown in Fig. Ø). It means that our algorithm could be more applicable in the distributed network with various delays, and this is realistic in industrial IoT systems where the computing resources vary remarkably among the agents and the data in each agent also differs significantly.
5.8 Validation for Theoretical Analysis
Finally, present two examples to verify our constructed theoretical analysis. We establish network involving three agents. We also set two reliable clusters with 1 and 2 agents, respectively. We leverage three nonconvex functions, i.e., Rastrigin, Rosenbrock Liang el al. (2006) and three three-hump camel function Horst et all (елот) to test the performance of our proposed framework. Though these functions are simple nonconvex problems, they have been used widely to test the performance of many numerical optimizers Misnal (2mm)). We randomly sample batches during local training in each agent. We fixed step size according to Theorem 2 0.008. The number of iterations is set to 500 for each
14

---

Published in Transactions on Machine Learning Research (MM/YYY)
-4
-15
(a) Convergence trajectories for Rosen- (b) Convergence trajectories for Rastrigin (c) Convergence trajectories for three- function
brock function
hump camel function
aday +2
Zound ealg-20
20rnthsday dday = 325
45-
bound Bakaym223
oday 350
Bound mddey135
143
35.
daay
30-
125
16
200
Fonilen
(d) Average gradients bound verification (e) Average gradients bound verification (I) Average gradients bound verification in Rosenbruck function
Rastrigin function
three three-hump camel function
Figure 6: The results of simple functions.
view the convergence of our proposed PC-ASGD algorithms. For the bound verification, we take different values of the delay to observe the performances of our theoretical framework. We first. find that when the delay is large, the squared norm of the gradient is large, which is consistent with our theoretical analysis. In all three cases, the quantitative results verify the correctness of our proposed theoretical framework in Fig. d b and [(T] the Rosenbrock function case, our established theory could describe the tendency of the average gradients square norm and the results are nearly tight asymptotically. But in Rastrigin function and three three-hump camel function cases, we observe that the differences between different delays are not large such that the bound is not tight. However, when calculating bounds, we find that the bounds for different delays differ mildly, which is consistent with all the empirical results. It also shows the effectiveness of our proposed theoretical analysis.
From Fig. a b and c
6 Limitations
In practical applications, our proposed algorithm still faces challenges. In comparison with the classical D-ASGD, our methods do not excel in communication efficiency. Notably, our methods introduce additional computational overhead, as illustrated in Fig. E (approximately 0.17 times). This is attributed to increased communicatio overhead (doubled for transmitting gradients to compute g and heightened memory over- head, necessitating agents to store 2f_r....,
These challenges become storage capacity are limited. For the real-world implementation of our algorithm, it is necessary to ensure the availability of adequate resources. It's also a promising direction to alleviate these burdens by algorithmic improvements, such as quantization and compression.
pronounced when computational resources, communication bandwidth, and
In addition the conventional practice of tuming the learning rate, fino-tuning the parameter À o is also essential for optimal results (as detailed in Appendix Q) opting determine the P/C choice 6, it also requires tuning in accordance with the discussions in Sec. 5.R.
15

---

Published in Transactions on Machine Learning Research
7
Conclusion
This paper presents a novel learning algorithm for distributed deep learning with heterogencous delay charac- teristics in ggeent-ommuriatiion-eewwww ing step, a clipping step, and the corresponding update law for reducing the staleness and negative effects caused by the outdated weights. We present theoretical analysis for the convergence rate of the proposed algorithm with constant step size when the objective functions are weakly strongly-conver and nonconvex. The numerical studies show the effectiveness of our proposed algorithms in different distributed systems with delays, by comparing it to multiple baselines. In future work, the cases for distributed networks with diverse delays and dynamic topology will be further studied and tested.
systems. We propose PC-ASGD algorithm consisting of a predict-
References
Soheil Abbasloo and H. Jonathan Chao. SharpEdge: An Asynchronous and Core-Agnostic Solution to Guarantee Gounded-Delays. arXiv e-prints, art. arXiv:2001.00112, Dec 2019.
Nazanin Abolfazli, Afrooz Jalikzadeh, and Erfan Yazdandoost Hamedani. An accelerated asynchronous distributed method for convex constrained optimization problems. In 2023 57th Annual Conference Information Sciences and Systems (CISS), pp. 1 6. IEEE, 2023.
Alekh Agarwal and John C Duchi. Distributed delayed stochastic optimization. arXie: Optimization and Control, 2011.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Commuicaation-eficeenn sgd via gradient quantization and encoding. Advances newral information processing systems, 30, 2017.
Mahmoud S Assran and Michael G Rabbat. Asynchronous gradient push. IEEE Transactions on Automatic Control, 66(1):168-18) 2020.
S. Becker and Yann Lecun. Improving the convergence of prok-propn learning with second-order methods. In D. Touretzky, G. Hinton, and T. Sejnowski (eds.), Proceedings of the 1988 Connectionist Models Summer School, San Mateo, pp. 29 37. Morgan Kaufmann, 1989.
Michael Blot, David Picard, Matthieu Cord, and Nicolas Thome. Gossip training for deep learning. arXiv: Computer Vision and Pattern Recognition, 2016.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223 311, 2018
Xuanyu Cao, Tamer Başar, Suhas Diggavi, Yonina Eldar, Khaled B Letaief, H Vincent Poor, and Junshan Zhang. Commmicatiinn-fficinn distributed lcarning: An overview. IEEE journal on selected areas in communications, 2023.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Accelcrated methods for nonconvex opti- mization. SIAM Journal on Optimization, 28(2): 2018
Shicong Cen, Huishuai Zhang, Yuejic Chi, Wei Chen, and Tic- Yan Liu. Convergence of distributed stochastic variance reduced methods without sampling extra data. IEEE Transactions on Signal Processing, 68:3976- 3989, 2020.
Jianmin Chen, Xinghao Pan, Rajat Monga, Samy Bengio, and Rafal Jozefowicz. Revisiting distributed synchronous sgd. arXiv preprint arXiv:1604.00900 2016.
Yang Chen, Xiaoyan Sun, and Yaochu Jin. Commuication--ffiieenn federated deep learning with layerwise asynchronous model update and temporally weighted aggregation. IEEE transactions neural networks and learning systems, 31 (111):4229 4238, 2019.
Woocheol Choi and Jimycong Kim. On the convergence analysis of the decentralized projected gradient descent. Xic preprint Xxi:2303308844 2023.
16

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Jeffrey Dean, Greg S Corrado, Rajat Monga, Kai Chen, and Andrew Y Ng. Large scale distributed deep networks. Advances in neural information processing systems, 2013.
Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Distributionally robust federated aver- aging. Advances in Neural Information Processing Systems, 33, 2020.
Yubo Du, Keyou You, and Yilin Mo. Asynchronous stochastic gradient descent over decentralized datasets. In 2020 IEEE 16th International Conference on Control & Aulomalion (ICCA), pp. 216 221. IEEE, 2020.
Chen Dun, Mirian Hipolito, Chris Jermaine, Dimitrios Dimitriadis, and Anastasios Kyrillidis. Efficient and light foderated learning via asynchronous distributed dropout. In International Conference Artificial Intelligence and Statistics, pp. 6630-6660. PMLR, 2023.
Mathieu Even, Hadrien Hendrikx, and Laurent Massoulié. Asynchrony and acceleration in gossip algorithmss
arXiv preprint orXic:2011.02371 2020.
Hamid Reza Feyzmahdavian, Arda Aytekin, and Mikael Johansson. An asynchronous mini-batch algorithm for regularized stochastic optimization. conference on decision and control, 61(12)1884-1338, 2015.
Jerome Friedman, Trevor Hastie, and Robert Tibshirani. The elements of statistical learning, volume Springer series in statistics New York, 2001.
Juan Jose Gamboa-Montero, Fernando Alonso Martin, Sara Villarrry,, Joao Sequeira, and Miguel A Salichs. Asynchronous federated lcarning system for human-robot touch interaction. Expert Systems with Applications, 211:118510, 2023.
Ning Gao, Le Liang, Donghong Cai, Xiao Li, and Shi Jin. Coverage control for nav swarm communication networks: A distributed learning approach. IEEE Internet of Things Journal, (220):19854-19667 2022.
Guillaume Garrigos and Robert M Gower. Handbook of convergence theorems for (stochastic) gradient methods. arXiv prepriat ar xiv:22301111 11235, 2023.
Hubert Gijzen. Big data for a sustainable future. Nature, 502(7469):38-333 2013.
Andrew Hard, Chloe Kiddon, Daniel Ramage, Francoise Beaufays, Hubert Eichner, Kanishka Rao, Rajiv Mathews, and Sean Augenstein. Federated learning for mobile keyboard prediction. arXin: Computation and Language, 2018.
Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual Icarning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. Tn Computer Vision ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11-14 14, 2016, Proceedings, Part IV 14, pp. 630-645. Springer, 2016b.
Reiner Horst, Panos M Pardalos, and Nguyen Van Thoai. Introduction global optimization. Springer Science & Business Media, 2000.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolu- tional networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 4700-4708, 2017.
Zhanhong Jiang, Aditya Balu, Chinmay Hegde, and Soumik Sarkar. Collaborative deep learning in fixed topology networks. In Advances in Newral Information Processing Systems, pp. 5904 5914, 2017.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Lincar convergence of gradient and proximal-gradient methods under the lojaak-lojssiewicz condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 795-811 811. Springer, 2016.
17

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Ahmed Khaled, Othmane Sebbouh, Nicolas Loizon, Robert M Gower, and Peter Richtárik. Unified analysis of stochastic gradient methods for composite convex and smooth optimization. Journal of Oplimization Theory and Applications, 199(2):499 540, 2023.
Alex Krizhevsky. Learning multiple layers of features from tiny images. University of Toronto, 05 2012.
Guanghui Lan, Soomin Lee, and Yi Zhou, Communccttion efficieen algorithms for decentralized and stochas- tic optimization. Mathematical Programming, 180(1):237 284, 2020.
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231N, 7(7):3, 2015.
Jinhao Lei, Chao Liu, and Dongxiang Jiang. Fault diagnosis of wind turbine based on long short-term memory networks. Renewable eneryy, 133:4224332 2019.
Zhongguo Li, Bo Liu, and Zhengtao ao Ding. Consensus-based cooperative algorithms for training over dis- tributed data sets using stochastic gradients. IEFE Transactions on Newral Networks and Learnöng Sys- tems, 2021.
Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. arXiv: Optimization and Control, 2017.
Jing J Liang, A Kai Qin, Ponmuthurai N Suganthan, and S Baskar. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions. IEEE transactions on evolutionary computation, 10(3):281-22) 225, 2006.
Xinyue Liang, Alireza M Javid, Mikael Skoglund, and Saikat Chatterjee. Asynchrounous decentralized learning of neural network. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3947-3951. TEEE, 2020.
Bo Liu, Zhengtao Ding, and Chen Lv. Distributed training for multi- neural networks by consensus. IEFE transactions on neural networks and learning systems, (16))1771-11778 2019.
Chao Läu, Dongxiang Jiang, and Wenguang Yang. Global geometric similarity scheme for feature selection in fault diagnosis. Expert Systems with Applications, 41(8):3585 3595, 2014.
Xiaolan Liu and Yuanwei Liu. Distributed learning for metaverse over wireless networks. IEEE Communi- cations Magazine, 2023.
Qinyi Luo, Jiaao He, Youwei Zhuo, and Xuehai Qian. Prague: High-ppeformance heterogeneity-awarr asyn- chronous decentralized training. In Proceedings of the Twenty- Fifth International Conference on Architec- turul Support for Programming Languages and Operuling Systems, pp. 401 401-416, -16,4 2020.
Yinbin Miao, Ziteng Liu, Xinghua Li, Meng Li, Hongwei Li, Kim-Kwang Raymond Choo, and Robert H Deng. Robust asynchronous federated learning with time-weighted and stale model aggregation. IEFE Transactions on Dependable and Secure Computing, 2023.
Sudhanshu K Mishra. Some new test functions for global optimization and performance of repulsive particle swarm mothod. Available at SSRN 926132, 2006.
Ravi Nair and S Gupta. Wildfire: approximate synchronization of parameters in distributed deep learning. Ibm Journal of Research and Development, 61(:):7, 2017.
Angelia Nedic. Distributed gradient methods for convex machine learning problems in networks: Distributed optimization. IEEE Signal Processing Magazine, 37(3)992 101, 2020.
Andrei Patrascu and lon Necoara. Nonasymptotic convergence of stochastic proximal point methods for constrained convex optimization. The Journal of Machine Learning Research, 18()):7004-7245, 2017.
Liangxin Qian, Ping Yang, Ming Xiao, Octavia A Dobre, Marco Di Renzo, Jun Li, Zhn Han, Qin Yi, and Jiarong Zhao. Distributed learning for wireless communications: Methods, applications and challenges. IEFE Journal of Selected Topics in Signal Processing, 16(3):326 342, 2022.
18

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild!: A lock-free approach to par-
allelizing stochastic gradient descent. Advances in neural information processing systems, 24:693-700 2011.
Alessandro Rigazzi. De-s3gd: compensamee stale-synchronous sgd for large-scale decentralized neural network training. arXie: Learning, 2019.
Theo Ryffel, Andrew Trask, Morten Dahl, Bobby Wagner, Jason Mancuso, Damiel Rueckert, and Jonathan Passeratpalmbach. A generic framework for privacy proserving deep learning. arXiv: Learning, 2018.
Felix Sattler, Simon Wiedemann, Klaus-Robert Müller, and Wojeiech Samek. Robust and communication- efficient federated learning from non-iid data. IEEE transactions on neural networks and learning systems, 31(9):3400-33) 3413, 2019.
Felix Sattler, Klaus-Robert Müller, and Wojciech Samek. Clustered federated learning: Model-agnostic distributed multitask optimization under privacy constraints. IEEE Transactions on Neural Networks and Learning Systems, 32(8):3710-3722 2021. doi: 1.1109/TNNIS..0001
Nikko Strom. Scalable distributed dnn training using commodity gpu cloud computing. Tn Sirteenth Annual Conference of the International Speech Communication Association, 2015.
Tao Sun, Dongsheng Li, and Bao Wang. On the decentralized stochastic gradient descent with markov chain sampling. IEEE Transactions on Signal Processing, 2023.
S Sundhar Ram, Angelia Nedić, and Venugopal V Veeravalli. Distributed stochastic subgradient projection algorithms for convex optimization. Journal of optimization theory and applications, 147:516-545, 2010.
Mingxing Tan and Quoc Le. Efficientnet: Rethinking model scaling for convolutional neural networks. In International conference on machine learning, pp. 6105-6114. PMLR, 2019.
Konstantinos Tsianos, Scan Lawlor, and Michael G Rabbat.
compppacaiiioooommtttttttoooonnn tradcoffs in consensus-based distributed optimization. In Advances in newral information processing systemss, pp. 1943 1951, 2012.
Konstantinos I Tsianos and Michael G Rabbat. Efficient distributed online prediction and stochastic optimiza- tion with approximate distributed averaging. IEEE Transactions on Signal and Information Processing over Networks, 2(4):489-506, 2016.
Jun Tu, Jia Zhou, and Donglin Ren. An asynchronous distributed training algorithm based gossip communication and stochastic gradient descent. Computer Communications,, 195:416 423, 2022.
Abhinav Venigalla, Atli Kosson, Vitaliy Chiley, and Urs Köster. Adaptive braking for mitigating gradient delay. arXie preprint arXiw:2007.01399 2020.
Simon Wiedemann, Klaus-Robert Müller, and Wojciech Samek. Compact and computationally efficient representation of deep neural networks. IEEE transactions on neural networks and learning systems, 31
(3):772-788) 785, 2019.
Xuyang Wu, Changxin Liu, Sindri Magnusson, and Mikael Johansson. Delay-agnostic asynchronous dis- tributed optimization. arXiv preprint arXin:2303. 18034, 2023.
Guojun Xiong, Gang Yan, Shiqiang Wang, and Jian Li. Straggler-resilinn decentralized learning via adaptive asynchronous updates. arXiv preprint XxXi::2306.06553 2023.
Yang Xu, Zhenguo Ma, Hongli Xu, Suo Chen, Jianchun Liu, and Yinxing Xue. Fedlc: Accelerating asyn- chronous federated learning in edge computing. IEEE Transactions on Mobile Computing, 2023.
Wei Yang. pytorch-classffeation. https: http::///ttthh.cccoaarrrarrrrrrr cossed: 2019-01-24.
2019. Ac-
Maxim Zakharov. Asynchronous Consensus Algorithm. Xiv e-prints, art arXiv:2001.07777 007704, Jan 2020.
19

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Jinshan Zeng and Wotao Yin. On nonconvex decentralized gradient descent. IEEE Transactions on signal processing, 66((1))2233-22 2848, 2018.
Tuo Zhang, Lei Gao, Sunwoo Lee, Mi Zhang, and Salman Avestimehr. Timelyfi: Heterogeneity-awvare asyn- chronous federated learning with adaptive partial training. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 1063-5072, 2023.
Shuxin Zheng, Qi Meng. Taifeng Wang, Wei Chen, Nenghai Yu, Zhi-Ming Ma, and Tie- Yan Liu. Asyn- chronous stochastic gradient descent with delay compensation. In International Conference on Machine Learning, pp. 4120 4129. PMLR, 2017.
Huiping Zhuang, Yi Wang, Qinglai Liu, and Zhiping Lin. Fully decoupled neural network learning using delayed gradients. IEEE Transactions on Neural Networks and Learning Systems, 2021.
20

---

Published in Transactions on Machine Learning Research (MM/YYV (YYY)
A Additional Analysis
Before presenting the main results, introduce some necessary background the delay compensated gradients.
A.1 Connection Between PC Steps
As discussed above, PC-ASGD relies upon the two steps to determine the updates for each agent at every time step, as displayed in Fig. M We first turn to the clipping step (line 7 Algorithm MI) where all stale
Predicting Step
Clipping Step
Figure 7: Chapiiiinn---iiinngggggg Steps: in the predicting step, blue lines indicate no delay transmission; green lines represent delayed transmission that requires gradient prediction to reduce the stale effect; the clipping step, the agent selectively drops the delayed information while only receiving information without delay.
information is dropped, which is equivalent to 'clipping' the original graph to become a smaller scale graph. Therefore, between the predicting step and the clipping step, we observe two static graphs switching alternatively. This also suggests that element values of the mixing matrix W in the clipping step different from those in the predicting step. In the predicting step (line 6 of Algorithm M). the agent still requires all the information from its neighbors while asking for gradient prediction from the unreliable neighbors. However, the update is determined by the combination of these two steps in Algorithm M. which relics on the A value to balance the IradeofT. For simplicity, we set the initialization of each agent 0.
We now turn the practical variant of PC-ASGD in Algorithm D in the Appendix. The condition (line 9) adopted for PC-ASGD is based the approximate cosine value of the angle between (<(x)) and Apre (or Aeti)). When the angle between s<())) and Apre. (or Adtip) is smaller, leading to larger cosine value, the corresponding step should be chosen as it enables larger descent amount along with the direction of (x))) Hence, with a sequence of graphs and the properly set condition, these two alternating steps are connected to each other, allowing for convergence.
A.2 Delay compensated gradient
We detail how to arrive at Eq. Specifically, given the outdated weights of agent xt due to the delay equal to t, by induction, can obtain for agent k
2 1+1 = (
(17)
-
Σ
[g((1 + (g oz (1) (2/
-2
r=0
19g f -+) = = -mgu(tt n9k (2t (1t
24- =r -.t---1
Σ
Ia (xt
Aga ( 2 ga (xt ( 2(-r)]
(18)
k Rd 11
Σ
Ia (2tt Agu(st= ox (of - x(-r)]
(19)
21

---

Published in Transactions on Machine Learning Research (MM/YYY)
As mentioned in the main contents, the term (#)-74r z/_+) is from agent due to the outdated information of agent k; which intuitively illustrates that the compensation is driven by the agent i when agent k is in its neighborhood and deemed an unreliable one.
A.3 Compact Form of PC Steps
We next briefly discuss how to arrive at the compact form of the predicting and clipping steps for the analysis. For the convenience of analysis, we set the current time step as I + such that line 6 in Algorithm shifts T time steps ahead. Let us start with the predicting step and discuss its associated term ΣjER Wyyal+ + EVER= Wy-rftr where for the time being, it essentially holds that <t+r =- xt. Note that R. includes the agents i itself. Although unreliable neighbors are outdated, in the context, the update for agent i still requires such outdated information, which suggests that the whole graph applies. Additionally, the consensus is performed parallel with the local computation, so this term boils down to a similar term in the existing consensus- based optimization algorithms in the literature. Thus, one can convert the current consensus term for weights Ep Wip E V. To show the evolution of predicting gradient over the past steps ranging from 0 to 1, we Ik de,r (at) to represent.
Hence, the update law for the predicting step can be rewritten as:
11+++1 = E Euppet++ ((gn(1)+>)
Σ KER=
wik Σ
9k
de.r (xt))
(20)
One may argue that for those ouldated agent & E R2, they have no information ahead of time 4, which is T time steps back from the current time. As the graph is undirected and connected, the time scale will not change the connections among agents. Also, for agent i, it receives always information from other agents, either the current or the outdated to update ils weights. Thus, we have,
{ x/ 2t k=k,k R
p=jjER
L -
(21)
Since the term ΣKER Wik Σ,= 9k we expand it to the whole graph. It means that we establish an expanded graph to cover all of agents by setting some elements in the mixing matrix W' e NNN equal to 0, but keeping the same connections as in W. Then Eq. 2D can be modified as
de. (x+²) applics to unreliable neighbors only, for the convenience of analysis,
Σ wipal++ n(ax(1(+>) + Σ w/y
Σ
9k
der (2))
(22)
where
w/y {{ Wik
if 4 k if E R
(23)
Thus, we know via the above setting that W is at least row stochastic matrix. We rewrite the update law into compact form such that
X Wx. 7g((x(+)) + Σ gdeee.r)x))))
(24)
r=0
where W W ② Laxd and W W' ② Laxd- Similarly, we rewrite the clipping steps in vector form follows:
X = Wx ng(x++))
(25)
where W- W. & Taxa= We now ready to give the generalized step
X++++1 = Wo4rXe4r (((((++7) + 0,+7
Σ W' (x)))
(26)
r=0
22

---

Published in Transactions on Machine Learning Research (MM/YYYY)
where WA+ is denoted as 0u+r W (1 - W throughout the rest of the analysis. Though the original graphs corresponding to the predicting and clipping steps are static, the equivalent graph WA+ has become time-varying due to the time-varying / value.
A.4 Approximate Hessian Matrix
Based on the update law, we know that the key part of PC-ASGD is the delay compensated gradients using Taylor expansion and Hessian approximation. Therefore, the Taylor expansion of the stochastic gradient g(X++7) at X2 can be written as follows:
g(x++7 = g(x)) + Vg(())(Xx+7> - x.) + +(( - x1)3
(27)
where Vg denotes the matrix with the element V = oF for all i.j EV. dr
In most asynchronous SGD works, they used the zero-order item in Taylor expansion as its approximation to gxx++r) by ignoring the higher order term. Following from Zheng al. (2117) we have
g(x++>) g(x)) + Vgg(x) Xt),
(28)
Directly adopting the above equation would be difficult in practice since Vg(x.) is generically computationally intractable when the model is very large, such as deep neural networks. To make the delay compensated gradients in PC-ASGD technically feasible, apply approximation techniques for the Hessian matrix. We first use (xx;) to denote the outer product matrix of the gradient at x,, i.e.
à F(x:))"
O(x:) - ( F(x))) Ox:
(29)
0x
When the objective functions take the form of the cross-entropy loss or negative log-likelihood, the outer product of the gradient is an asymptotically unbiased estimation of the Hessian, according to the two equivalent methods to calculate the Fisher information matrix EFiedman et all (2001)). That is,
E = [x]] Hxx)lll + 0, +
(30)
where (x:) is the Hessian matrix of at point X
The above equivalence relies on assumptions that the underlying distribution equals the model distribution with parameter x" and that the training model x, asymptotically converges to the (globally or locally) optimal model x". According to the universal approximation theorem for DNN and some recent results on the optimality of the local optimal, such assumptions are technically reasonable. As the above equivalence was only developed by the negative log- likeelhoood form, that may not be applicable when we use PC-ASGD for the mean square error form, such as some time-series predictions with LSTM networks. Therefore, we introduce one assumption on the top of such an equivalence as follows,
BillO(x,) - H(x)lll s e =
(31)
which primarily eliminates the computational complexity when directly calculating H(x;). Another concern would be the large variance probably caused by O(x:), though an unbiased estimation of Hx,)). Similar to Zheng et al. 72 we introduce a new approximator AO(x,) - A( 1 F'xx)) Tx, F(x.))" The authors
in Zheng et al.
( have proved that (x(x,) is able to lead to smaller variance during training. Thus we
refer interested readers to Zheng et al. (2017) for more details.
To reduce the storage of the approximator X0(x)), one widely-used diagonalization trick is adopted Becked M Lecom (188S]) Hence, the update law for PC-ASGD, we can see in the delay compensated gradient involving )x(x;) >g(x;). By denoting the diagonalized approximator as Diag(X0(x,)), the following relationship obtained:
Diag(A0(x.)) Ag(x;) Ag(x;)
(32)
23

---

Published in Transactions on Machine Learning Research (MM/YYYY)
However, for analysis, when we apply diagonalization to Hxx,, it could cause diagonalization error such that we assume that the error is upper bounded by a constant >> 0, i.e.,
(x))((((x)))- (xx) ED
(33)
B
Additional Proof
For completeness, when presenting proof, re-present statements for all lemmas and theorems.
Lemma 3: The ilerates generated by PC-ASGD satisfy AI 2 O, and T 2 2:
1+7-1
47- 111-1
(+ 1 f+
X
II
1
- 5=0 p=st1
Σ II
Wertss-g(x.)) - Σ II
Os+ WATT
Σ
W' g(x+1))
0=0
w=st1
r=
(34)
Proof. Basod on the vector form of the update law, we obtain
T-2 Σ W Wgggee (x:))
X 1 7(g(((+7-1) 0
(35)
With the above equation, it can be observed that X is a function with respect to X which contains all of agents. This suggests that by X2, there were no delay compensated gradients, while after X the unreliable neighbors need the delay compensated gradients due delay. Hence, applying the above equation from T yields the desired result.
Bounded (stochastic) gradient assumption: As B[]g(())] < G² and Elg(x)) VF(x), one get that [|V] = [[[[(()]]| < [[]g(())|I] (xIll VB[Ig())II)=
Lemma 1: Let Assumptions 2 and 3 hold. Assume that the delay compensated gradients are uniformly bounded, i.c., there exists a scalar B > 0, such that
de.r (x,) S, V2 and 0 OSrST- 1,
(36)
Then for all e V and 12 0, Bn > have
G + (T 1)B0
E||K
Ill <
(37)
1 82
where 6m = max(0++1).tr 1++--1, 82 = max(fse2 + (1 -0--0,, 0.)ē2 1++-1 1, where e2 = e2(W) < and 82 := ez(W) 1.
Proof. Since
1
| y1+t|l S ||x++ Mttr = ||
1 x1
N
(38)
=||x4t7 N
1
11T T x
= =1[[1
11 Ix
N
24

---

Published in Transactions on Machine Learning Research (MM/YYYY
where 1 is the column vector with entries all being 1. According to Assumption we have 117 N 117. Hence, by induction, setting Xe = O, and Lemma 3, the following relationship can be obtained
|x - 34+- 11
147-1 1 147-1
H-- 44r-1
-nl
Σ
W4
11
)gx + Σ
III
10+t1 11
11
Σ
W
g dew (xx)
N
N
==0 v=s+1
e=tt1
r=U
H--11
(+r-1
14-11
2
-1 Σ
W WAT+S-
11 [|l](())]] + Σ
II
W W4r++s-0
1
11
111 x+1 Σ
W' gi
de (x+)ll
N
N
H
#
SnG
Σ
84--1-
2
+
02
84--1-88,
10-11-00+1( 0.+1(T B)BB
==0
==
ST 1
82 02
-1
1/(
1)B0,n
02
m
82
G+0 (T 1)88m
51
1- 82
(39) The second incquality follows from the Trianglc incquality and Gauthy-Schwarte incquality and the third inequality follows from Assumption @ and that the matrix N 11 is the projection of W onto the eigenspace associated with the eigenvalue equal to The last inequality follows from the property of geometric sequence. The proof is completed by replacing t + r with on the left hand side.
To prove the main results, we present several auxiliary lemmas first. We define
(x,))) Σ g(x+++)) H(x:) -x, xx)
(40)
T-1 VF (x,) = Σ VF( E[H B[H())) xx)]
which are the incrementally delay compensated gradient and its expectation, respectively. It can be ob- served that (xx) is the unbiased estimator of (x)) It should be noted that H(x,) = Vg(x;). Let Vitr = W4+xX++7- We next present. a lemma to upper bound [[V((verr) - vxih"((x))ll where VxFl)(())) = (x((t+)) + ([.((x)(Vet+r - x,)].
Lemma Let Assumptions 1,2 and hold. Assume that VF(x,) smooh.. For 2 0, the iterates generated by PC-ASGD satisfy the following relationship, when
Em 1 2
2G + (r 1) 1)
- - (x))l <
(41)
1- 82
when r= 0, we have
(1 + (T 1)
[VV( VF(xx)I S 2mm
(42)
82
Proof. By the smoothness condition for VF(x), we have
Em
Em
[VF(v (x)))()))) S
||ver -xll <
X x
(43)
2
2
Let Autr Xetr X Thus, based Lemma. 1, have
1+
14- t1--1
r-2
X
II
W
Σ
II v=++1
W ((4)))-g(xx)-0)
Σ
W w=
II
Σ ==0
1 W' de. (xx+1-r)
(44)
25

---

Published in Transactions on Machine Learning Research (MM/YYY)
Hence, we obtain
1+p-1
b+p-1 tip=l
b4r-1 t4r=1
|| | = IK
II v=t
W
Σ
II W
Σ
WHstr- II
Σ
2 W W'g (x=+11=)))
a=t
v=s+1
s=t b=s+1
==0
(45)
Due to Xo = 0 and no delay compensated gradients before time slep I, we can oblain
A Mtrl 2
# M
6+r-1
r-2 Σ
=I1
7 Σ
W. gxx,) - 17 Σ
W W4s44r
011 W Wggdeii
(x +
EII
W g(x,)]1
==0
H+-1 H+--1
b---1 6+r-1
(1)
Σ
gex+ +
W Wetatr-v
0,+1 W'g do (xo+((x+1-+)11 +
g
Σ
W W
D=st1
==0 v=s
4+--1
14--1
(4r-1
Σ
W v(x))=
Σ
W Witetrew
0 W' g Σ
do,
(x++1- +
Σ
g(+)-
v=++1
8=1
8=8+1
==0
s=0
H+r 14--1
H4- 1 t-r-1
r-2 Σ
(
Σ
[Westr-olll
0s+ W' (x
w=++1
0=s+1
2=0
Σ II [ (lx,)())
v=
2G
1 - 82 + 1-
B(r m)
2G + 0ml
(r 1)B }
82
(46)
The first inoquality follows from the Triangle inoquality. The second inequality follows from the Jensen inequality. The third incquality follows from the Cauthy-Schwartz incquality and the submultiplicative matrix applied to stochastic matrices. The fourth inequality follows from the Assumption and bounded gradient. We have observed that this holds when r 1. While 0 enables -VF(v++)-=hhr (xx)ll to degenerate to [[V)(v,) - VF(x))] based on the definition of F (x.). Using the smoothness condition of F(x), we can immediately oblain
G+ (T (m0)B0mm
[VF(V.) - VF(x))] S Ymm!
(47)
1 - 82
The proof is completed.
Lemma 5: Let Assumptions 1, and hold. Assume that the delay compensated gradients are uniformly bounded, i.c., there exists a scalar such that
(x+))l degderr(x))) S B, Vt and 0 0
dgder
(48)
Then for the iterates generated by PC-ASGD, B7 0, they satisfy
7-1 Σ W' der (x:)ll
[x)]
r=0
(49)
2G + (r (r-1) 10
(7m tep + (1 -))
+ TO
1 1-82 -2
26

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Proof. Based on the definition of Eg"(x,), we have
|E[g* [x)) Σ W'g dor (xx) = g 8(x++r)
Σ (x - xx)] - Σ W Wggarr (xx)]
==0
1=0
==0
=|E[g (x)) W'g W'g / (x1)
E
(x,)
W' g g (xx) + Blg" (x1)) )] W' de,
(xx)
< <|Eggh== W do (x4) + | (xx)
W g (gdor==((x))) +...
(xx)] W'
W'g Wigd
(50)
The last inequality follows from the Triangle inequality. Now let us discuss |EG (xx) - W ggt.t..rr (x))) The
following analysis is for cases where 2 1. We give brief analysis for the case in which r = 0 subsequently.
(x; W'g (xx))
[x(((x+++) + H (xx,)xx+++ (x,
*g(xx) o g(x,) (x,+1
[VF((+++)
[(ll((x())__""((("xxxxxxxx/x" x.)I
V F (x(++) - W'g(x)]l + (x; AW ogx) x,)l
V (x(++)) - W'g(x)]l + (x;) AW g(x, (g(x)) 0gxx))(((xx))) - g(x.) e g((x))
Diag H (x:) +
- x
Fx((++)) - W (x,)] + |xx+r - xx xxIlI(AW''(( g(x) 0g(x)) - g(x) (x()))) + (g(x:) o g(x))
Diag( H (xx)) + (Diag( (x())) (x)))lI
F W [x+]] ||t+rr X (xxx))(())))))))
O gxx)) g(x)) g(x))l |l((x)) g(x))
(x))) Diag H (x,)) lx))
The third inequality follows from Cauthy-Schward inequality while the last one follows from the Triangle incquality. It should be noted that when we combine (xxx)(x+++> xx) and AW'g(x)) @ g(x;) @ (x++r x.), we follow the update law. Since in a rigorously mathematical sense, g(x,) @ g(x)) should be g(x))g(x,)" However, for reducing the computational complexity when implementing the algorithm, as discussed above, we have made the approximation and diagonalization trick. Hence, assume that H H(x)) -W' -W''g(x)) Og(:)) can hold for simplicity and convenience.
Then we discuss E||l E[[ F((++)) - (x:))-
E
V F X
W'g(x))II < ((]])( g(x))
E
F X
VF(x)) + Vx) - g(x:)]l
E
V
F
X
VF(x)) E| g(xx)ll
5m
|
x, + (I 1(x)
(51)
2G + (r 1)
1m
/ [/ - g(x))1l2
1 1 82
2G + (r - 1)B0m.
5mm
a
1-82 82
Hence, we have
2G + (r - -1)00m
2G + (r - B0)
|[E[g((x,)] Σ
W'gder dew (x:)l Smm
[(1 - X) +ep + +t
+ 0
1-6g 82
1 1 62
0=
(52)
2G + (r
=(mm ED
+c+ t
+ 2)
+ o
1 1 82
The above relationship is obtained for cases where r 2 1. There still is r = 0 left. For r = 0,
VV(xx)) W W'g(x:)1 So
(53)
27

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Thus, combining each upper bound for [[[("h((x,) W "xgg"(((x)))))
obtain
2G - (r 1r--) - +0,
|E|g - Σ dey "x))l - Σ Im +c
(54)
1- 82
which completes the proof.
Lemma 6: Let Assumptions 1, and hold. Assume that the delay compensated gradients are uniformly bounded, i.e., there exists a scalar B such that
Ig (xx) S B, V22 and OSrST-1,
(55)
Then for the iterates generaled by PC-ASGD, By > 0, they satisfy
G + (r 1)B0m
F(x+++) F(ve++) -22
(56)
82
Proof. Due to the convexity, we have
F(x+++) 2 + V V(+T)
2 F(v++T) -
XL+T||
2 F(V++7) - Gillv++ X(+7ll
2 F(Vi+r) - Glllve++ 3etr 1u4r1=1 B1t, X1+T||
(57)
2 F(V++7) - -G([Iv++ - -11+ + || 1 x(+r|l)
Z F(v++7)- 2G G+ (T (m)
1 82
The second inequality follows from the Cauthy-Schwarz Schwarz inequality. The proof is completed.
Theorem Let Assumptions 1,2 and hold. Assume that the delay compensated gradients are uniformly bounded, i.c., there exists a scalar such that
deg (x,)) B, Vt 0 and 0 Osrss 1T-1,,
(58)
and that Fx(x,) is Em smooth for all f 2 0. Then for the iterates generated by PC-ASGD, when 0 < S and the objective satisfies the PL condition, they satisfy
2μr
Q
B[F(x;) - FF1 < 2pmTT' ( (F(x)) F
+
(59)
24M7
2
T G
Q 1=2(1 - 2 Gnj +
Σ
C, 21
2
rm1
(60)
+ Giyra + m20(% +c 2)6²)
C n² + Gr
and,
C G + (T - 1) m
1 82
C, 2G + (r B0 m
(61)
- 82
C₂ 2G + (T 1)B0m
82
eD 0 and 0 are upper bounds for the approximation errors of the Hessian matrix.
28

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Proof. According to the smoothness condition of F(x). We have
B[F(x++++)) - F(x")] = B[F(v(++) -(x)))))))x())))) ([ (X4+++1 (Xtrr11-Vt+7)) V1++))]+
I'm B x - Ve+-
2
(62)
Based on the update law, we can obtain
E(F(x+++1)) -
< <B(F(V+++) F*] -B
(VFFFVVv
Σ W W de (x,)))
1m E[llg(x(++)
Σ
W Vggeer (x:)]11
+ 2
(63)
SB(F PM) (VV(VV - -V
+ +n VV((+++)
VF B
-
+ [VV(+,+),
Σ W'g der (xx)))(xx))) +
EE g((()(())))))) +
W g de (xx))
2
We next investigate each term on the right hand side. Based on Lemma 6, we can obtain
G + (T - 1)
F(x++)) 2 F(ve+T) 2Gm
(64)
- 82
such that
G + (T - B0m F(x++T) F F(ver) F -2G
(65)
1- 82
For the term (VF g(x+++))) we can quickly get that is bounded above by n/6 due the Cchthy-Schwarz inequality. Then for term (VV one can get the following relation- ship due to the PL condition.
|| (FV))() F*)
(66)
Combining F(Y++7)- F*, we have
(F( F*)
G (T 1)B0...
(67)
< (1 (FT F*) 2Gm
82
Based on Lemma 4, we have known that
[VF(v - V.rli (x:) <
Em 1/21
2
2G + (r 1) B8
(68)
2
1 82
for 2 1, while for r= 0, it can be obtained that
G (T B)
[VF(v)) VF(x))] < 2m
(69)
1 1-82 82
Since
(VF((+))
VF(V -F"x))
-F((++))=="x))
F=0
(70)
< EE ((++++)
Σ -x
29

---

Published in Transactions on Machine Learning Research (MM/YYYY)
The first incquality follows from Cauthy-Schwand inequality and the second one follows from Triangle in- equality. Hence, we can have
Sm. 2G + B(r - 1)0ml + 2n G + (T - 1)B0m.
(VF(( -
2(1 62)
1 82
(71)
According to Lemnma 4, the following relationship can be obtained,
r²C (m (m + +c+ A)Ga)
E(VVFVY+))) Σ W (x,)))
Σ
2G + (r (r- 10m + Gnrr
1-62
(72)
The last term N (VF (V(()))) (V(++))))), which can be rewritten such that
(V (V((v++))
Σ VF((v++)))
1=0
(73)
(atpae)))_((((......)>>>-)) +
-
< (F (V [VF(v++)) VF(x+7-1)II
Using the smoothness condition, we then can bound the term by deriving the following relationship with Lemma 1 and Lemma 3,
((VE( Σ VV(Vv++)) m/ Gr 2G (T 1)
(74)
82
We combine the upper bounds of each term on the right hand side to produce the following relationship.
G + (r 18m
E [[F(xx+T+1)= - (F(())))))((() < (1 -
- F²) + 2(1 21prr Gn
1 82
+ 17² Sm G
Σ
T-1
I2G (r ( 1) +:2/
B)
GiJTO + 1/G²
2(1 52)
1 1-62 82
r=1
+ G
2G + (T 10
(Im + +c+ (1-) Σ
2G + (r - Bl
m + 17 rm Gr
1 82
1 - 82
(75)
We now know that
B[F(x++1) F (1
F -F
(76)
subtracting the constant
from both sides, one obtains
2urq
Q
Q
B[F((++1) - F*]-
< (1 21 [F( FF) ) Q 2μt
2μT
(77)
(1 2njrr) FM)
2μTT
Observe that the above incquality is a contraction incquality since 0 < 2nprr S due to <ns 2ur result thus follows by applying the inequality repeatedly through iteration t t N.
The
Another scenario that could be of interest the strongly convex objective. As Theorem 0 has shown with a properly set constant step size, PC-ASGD is able converge to the neighborhood of the optimal solution
30

---

+ " Published in Transactions on Machine Learning Research (MM/YYY)
with linear rate. This also applies to the strongly convex objective in which the strong convexity implics the PL condition, while the constants are subject to changes. We now proceed to give the proof for the generally convex case.
Theorem Let Assumptions 1, 2 and 3 hold. Assume that the delay compensated gradients are uniformly bounded, i.e., there exists a scalar such that for all T
lg (x,)) B, At 2 0 and 0 S r TT
(78)
and there exists C>0 O,
E||x x x11 S CC
(79)
where x" E axgminn(xx). Then for the iterations generated by PC-ASGD, there exists 0 < < 20% that
such
X1 x 1|
A
B[F(XT) - F*)
(80)
Tn
where A = El|g(x*) Vx Et=xx Xt.
G+(r- 16rr-11B0 B8
0.. :=
Proof.
According to the compact update law, we have
| [W ((((x++)) 0c++ Σ
W'g (x))))()))) x=1
(81)
r=0
As Vit+ = W4+X144, we can obtain
| x-1 VV x²112 2n(V x', g(x(+7) Petr
Σ W'gder (x,))
r=0
(82)
+ 7² [g((((++) + Octt Σ
W'gder
r=0
For convenience, we define that l'+t = g(x(+T) + Oct Erzo W'gder((x.) Hence, the above equation can be rewritten as
X144++1 - x²1 = ||ve+t - xx 7 1|
+ +27(x" - VetT:g(V + +n Ve+ri V(++))(X(+T) g((++7))
(83)
+ 27(xx - Vitti Outt Σ (xgger(())))
Taking expectation both sides leads to the following relationship:
E[||x4+4+1 x11 < B[ixx(+7 11 + E 1
+ 2x/E((x Ve+T, VF (V(++)))) 2n)(((x VeLri VF(x++7) V
(84)
+ 2nE((x - Vitri Oets Σ (''g(-(xx)))
r=0
The inequality holds due the basic property for the projection Sundhar Ram et al (20I For the last two terms on the right hand side of the above incquality, we can leverage Cauchy-Schwar incquality to obtain the upper bounds. For [ V V we will use Lemmn 2 to reformulate. We next investigate [++ Before that, we introduce a theoretical fact for the generally convex smooth functions
Variance transfer: gradient noise (Lemma 4.20) Garrigos & Gower (2023). If F is smooth and convex, then for all we have that
[[[]g())]]] 47 F*) 20
(85)
31

---

Published in Transactions on Machine Learning Research (MM/YYYY)
where g(x) is the stochastic gradient, of is the variance of stochastic gradient at x". Rewrite |[ (1g(x++r)+ + VF(x(+)) - +((++++))))))))))) VV((+)) -V((vv)) + Erz W W'gder (x:)]1?.
We then have the following relationship:
Blllx++++1 - x=1 S E|||xt++ x* + 5n
- - -VF(v+++)1
+ 5v BilBB[ll (veeT)
+ 5n B[[]0
Σ W -
+ -
Vi+ II + Vi+r |11 Σ W' W'gder (x,)
|]]
(86)
The last incquality holds due to the basic incquality and obtained
Ex= a < NE |a the convexity property,
inequality. By substituting Eq. S3 into Eq. ND, the following relationship can be
[[|x - x*11 < X|| - x || + 7m
- F*] + 10
511 VF )|{]
VF
+
- V ) + B[ (
+ 51 Σ W de. (xx + 2n - F(
w'
+ 2 Vet - 21yB[[1x*
-ve+- [ Σ W'g (x:)((
r=
- x" - + - - F*1 + 10n200
+ 10 + 20m G² + 51 B² + 2nG + BB)
(87)
The second incquality follows from Assumption 3, Eq. 9 and bounds for the predicted gradients. mathematical manipulation, the above inequality can be written as
With
21y(1 10
F*] B||[x++ [13] -1| 1
10n²00 + 10n2 + 20m + 5n 72 + 2n + 6n BnTB)
B)
(88)
Due to 17 < 20
1 17 2 1 such that nB[[F(v+r)) - F+] < 27(11 (B -F'. Dividing
both sides of Eq. 88 by 7 yiclds the following
[[F(ve++) F*] [E[[] [|||xx++>=-1 - x - -
(89)
1 00 + 10n2 + G + 51 -2 B² + 2n + B)).
Similar to Lemma 6, we can obtain that F(V(+7) 2 F(x++)) - 2Gm G+ Then it is immodiately obtained that F(V++7) - F 2 F(x++7) - F 2Gn 1-82
1-62
G)(
With this, the following relationship can
be obtained
x*1 1 [B[l|x++ - - - - x1 + < 17
(90)
"
where = 10 + 20m + 5, 722 2 TB 2G (2C + 1). Recursively summing C over from to T and replacing + with grants the following relationship
T Σ
X x
AT
[[F(xx) - F+
(91)
1
32

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Dividing both sides by T in the last relationship attains the following
XI x
A
Σ (()
-
F
(92)
Using that F convex with Jensen inequality gives the desirable result.
In the sequel, we provide the details for the smooth nonconvex functions.
Theorem & Let Assumptions 1,2 and 3 hold. Assume that the delay compensated gradients uniformly bounded, ie., there exists scalar B 0 such that
lgg dgo (x+] S B,
Vt 0 and r sgrsT- 1,
(93)
and that
E Ellg (x,) || S M.
(94)
Then for the iterates generated by PC-ASGD, there exists 0 < 17
such that for all T 2 1,
7mm
1
11) 2(F(x1) F²)
R
E V
(95)
T
T'
where
Tmp M
no² +
R = C1
+
nor B + 2m)27((BB G)C1.
2
Proof. According to the smoothness condition of F(x), we have
F(x F(Ve+))
Yum +||x44+11 V++T 1|2
<(VF(V X - V24r)
2
J-1
2m
=(VF(V++T)) 7
Σ
W'g de (xx) + g(x++t))) +
W'gner
g der + g(x++))1l
2
r=0
7m
+ VF -V((E+) m
- (x(x++)
W'gderi(x dei + g(x++r)))
+
Σ
W W'g der + =g((++))1**
2
r=0
r=0
= -F ) Σ W' de, (xx)) +
VF((++T).
Σ
W' doi (x;) + g(x+++)))
1=
27 T
W' der + )g
g
2
r=0
IIV (x+++ || +|1 Σ W'
W'g de (xx) g(x++))11 [VF(x(+)) -
Σ W (x + g(xx++))11
722mm
+ +VF VF(v++)).
W' g der (x:: + g((x++))) +
W
g dew + g(x++))11
2
T-1
7-1
-V= 71
Σ
W don (xx) + g(x+++))1 7
[I - g(x++) M1 +11
7
Σ W'g der (xx))1
= 2
2
2
r=
-2((F((x++)) - -(x++T),
Σ
W W' de, (x:)))))))) + - VF(v++)).
g
Σ
W W' de, (x.) + g(x(+)))
g
0=
33

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Ym
W' dor +g(x+++)]l*
+
g
2
0=
--
V VF(x(++) )11 -
7m
W dew +gx
g
" [VF(xx-) g(x++))12++
+ 1/1
Σ
T-1
W g
des (xx)1?
2
2
2
2
r=0
r=1
-V++((++++ 8(x(+T))
Σ
W' g
de, (x+)) (x+)) + + (VP((x))))) VF(v++T); Σ
W'gder(x)) - g(x(+r))
r=0
)1 +1 1
7m
-
"
W ga
do,t (xx)]1
(ppnm "1
2 "11(((x+++111
22
2
r=0
pmm 2) ")((x())))
T-1
T-1
2
)
Σ
W'
g
de (xx)) + ? [F(x++)) - g(xx++)11
+2
!
Σ
W' W'g de (xi))
2
r=1
T-1
n (x((+++) 8(x(+T),
Σ
W' de, (x+)) + (V VF(v+++),
g
Σ
W' W'gge: (xx) + g(x(+)))
r=1
r=0
"
[V + 7m
"01
77
W der (x:)]1 + (ppnm - "
->)1((((+++)''''
2
g
2
2
2
2
r=
Im 2
+ 2
([x((+++)1111
Σ
W's W'g
der (x;)
+ 1 [F((x+++)) - -((x++))))
Σ W' der (x:))1
2
2
2
+ 7/| /[[(F(( - g(x
W W'g der (x+)ll + (V VF((+++)
Σ p=
de, W'gderrxx + g(x
The first inequality follows from the smooth property of the objective. The last inequality follows from inequality. The left hand side of the above incquality can be rewritten:
F(x(+++1) - F(x++)) + F(x++7) F(v++7)
Taking expectations for both sides, with the last inequality, we have
E[ - F(xx+T)]
<F( - F(x(++)]
7
1m - -"Ell
Σ W' der
g
(x:)]1
+
1/ -=
EElle [e[]g((x4 (xgg(((+))] 1)
2
2
2
1 pm - -1 El ([]]g((++>)ll |II| +
Σ
W'
g
dow (xx) + E1 V FF x(xx++))1
7
Elll
W'
gi dew (xx)11
2
2
2
P=
+
V [ 8(x++7))
W' do,
W'gdor
)ll + + VF(
|II|
Σ
W' W'g dc.r giggddrr (xx) + g(xx,))]] I|]]
r=1
p=0
SGE[IIvet> -x++++1 "
pm
2 BillwW
g de (x)))
7m 1
"
"Bllg(((++))
+
12'7m " El "Elllg [g( ||||
Σ
W' g
dow (xx)
? E1 [F((+++))+++))))))))))++)))) -g( +
)|1
7E
?
T-1
Σ
W' g dew d
2
2
+ +TB[|/F((x++)) - g(x+++)]ll
Σ
W'g dor (x: )11 + + VF( Σ
W" g de.r (x+) + g(xx=+)]l]
7=0
72
M
G G (1-1))
< 2
+
+ nor B + 2m7² (m G
2
2
7m
1-
(96)
34

---

Published in Transactions on Machine Learning Research (MM/YYYY)
The last incquality follows from the smoothness condition of F(x) and the bounded gradient, respectively, as well as 1 < Hence, by replacing i + with i, one can obtain
B[F(((1) F(x)) = "
2 (()))
(97)
where R indicates the constant term on the right hand side of the inequality. As we assume that F(x) is bounded from below, applying the last incquality from to T, one can get
T
F" F(xi) s F(xi)
(98)
which results in
T E ( 2((F(x))) F*) TR]
(99)
Dividing both sides by T, the desirable results are obtained.
C Detailed Settings of Deep Learning Models
Model Settings For the PreResNet1110 (model 1), DenseNet (model 2), ResNett2 (model 3) and Efficient- Net (model 4), models' architectures are shown in He et aL (20T6T) Huang et al (2017)) He all (201G))
and Tan L (2019) respectively. The batch size is selected as 128. After hyperparameter scarching 10.10.01, 0.001), the learning rate is set 0.01 for the first 160 epochs and changed to 0.001. The decays are applied in epochs (80, 120, 160, 200). The approxination coefficient À is set as 1. X = 0.001 is first tried suggested by DC-ASGD Zheng et al. (2 and the results show that the predicting step doesn't alfect the training process. By considering the upper bound of 1, set of values (0.001, 0.1, 1) are tried, and A = is applied according to the performance.
Hardware environment. Our experiments are implemented and evaluated at GTX-1080 with Intel Xenon 2.55GHz processor with 32GB RAM.
Table 5: Performance comparison in TinylmageNet and Time Series dataset
Prel10 TinyImageNet
DesNet TinyImageNe 61.4 0.7
Efficient TinyImageNet 74.8 0.9
LSTM
Model & dataset
Wind Turbine Data
PC-ASGD (Ours)
58.0 + 1.4
71.2 = 0.5
D-ASGD
52.1 0.3
57.5 + 0.2
70.4 0.5
66.2 + 0.1
Lian all (201
DC-s3gd
55.1 0.8
58.5 1.4
73.2 + 1.2
61.4 + 1.1
Rigazzi (21)
D-ASGD with IS
53.2 + 0.9
58.1 + 1.2
73.4 + 0.7
69.2 +: 0.2
Di all (212
Adaptive Braking
55.2 + 1.2
6.1
67.3 + 1.5
66.5 + 1.2
Venigalla et all (2020)
Table Performance evaluation of ResNet20 on CIFAR-10
20 agents
PC-ASGD
P-ASGD
C-ASGD
Baseline
Model & dataset
acc. (%)
o.p. (%) acc. (%) o.p. (%)
acc.(%)
o.p. (%)
acc. (%)
ResNet 20, CIFAR-10
84.9 + 0.6 2.4 + 0.7 82.9 0.7 0.4 0.8 83.8
0.8
1.3 = 0.9
82.5 - 0.1
acc.-accuracy, oup.-outeerfoomeed comparing to baseline.
35

---

Published in Transactions on Machine Learning Research (MM/YYX)
D More Empirical Results with different datasets
We also adopt our numerical studies on TinyImageNet Le & Yang (201 and Wind turbine data set Lin
al (201).. For Tit we adopt PreResNett 110 He el all (20166). DenseNet Huang et al (2017),
and Nef Tan La (Αпи). For the wind turbine data set, we use LSTM in Lei el all (2 to classify the fault in the wind turbine.
Results in Tab. E shows the effectiveness of our proposed methods in different models, datasets, and even different tasks (time series classification). Tt further demonstrates the generality of our proposed framework.
We also supplement the experiment with ResNet20 on CIFAR-10 to ablate the functions of the P-step and C-step in Tab. B. The quantitative results are consistent with Tab. 2, showing the benefits of our PC steps design.
3 Actually, we SGD-based optimizer for better analysis instead of Adam in LeL (201),, hence we achieve the
best. results (2пT). But our framework shows the best, performances among other framework handling delay.
36


Reviews:
[{"review_id": "hkWO9aLj7m", "reviewer": "Reviewer_7PTK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Novel Algorithm: A new algorithm, PC-ASGD, is proposed to address the challenge of stale weights and gradients in distributed optimization. Section 3.1 also provides a clear description of the idea behind the algorithm. \n\n2. Comprehensive Experiments: Lots of experiments are conducted, effectively illustrating the effectiveness of the newly proposed algorithms.\n\nWeakness:\n\n1. I am curious about the convergence rate in the convex setting. If PC-ASGD can match the state-of-the-art in the convex setting, it would make it even more impressive and highlight its versatility as a unified framework.\n\n2. For Section 5.8, testing one more example that satisfies the PL condition would be beneficial to further validate the convergence results.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The main contributions are the following:\n\n1. The paper addresses the challenge of stale weights or gradients in distributed optimization problems and introduces a novel algorithm, PC-ASGD, to mitigate these issues. Notably, it adopts a unified framework, considering both synchronous and asynchronous algorithms.\n\n2. PC-ASGD strategically balances the projection and clipping steps, enabling convergence for both smooth nonconvex problems and those with the PL condition. Under the bounded delay assumption, accounting for decentralized computation and gradient compensation, the paper establishes PC-ASGD as the first provable algorithm in this setting.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "It should be “AGP” in the tenth-to-last row on page 2.", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Hrc1Y3QdMm", "reviewer": "Reviewer_pyta", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Simple yet effective solution: The paper presents PC-ASGD as a straightforward yet highly effective solution to the challenges in distributed learning, which involves predicting and clipping gradients to alleviate the affect of communication delay from neighbor agents. It outperforms the existing methods in both accuracy and efficiency.\n\n2. Strong Theoretical Foundation: The paper provides a robust theoretical analysis of the algorithm, including a detailed examination of its convergence rate, which adds to the credibility of this proposed algorithm.\n\n\nWeaknesses:\n\n1. The paper's experimental section might be limited in its comparative analysis for different scenarios, such as in network settings with varying delays or in much larger scales.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "1. The introduction of PC-ASGD offers a novel solution to the persistent issue of stale weights in distributed systems due to communication delays. The proposed two-step approach, involving gradient prediction and clipping, is a clever strategy that adeptly balances the need for efficiency and accuracy in learning.\n\n2. By effectively addressing the challenges posed by variable delays, PC-ASGD significantly improves the accuracy of distributed learning systems compared with other async schemes.\n\n3. The authors provide a comprehensive theoretical analysis, confirming the algorithm's soundness, supplemented by empirical evidence from experiments with benchmark datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think this paper presents a simple yet effective algorithm for Asynchronous Federated Learning with robust theoretical backing. However, it would be beneficial for the authors to expand their experimental section.\n\n1. The paper currently assumes a uniform network delay for all agents in a connected graph, which may not align with the variability seen in real-world networks. In practical scenarios, communication delays can differ and change over time among agents. Therefore, it would be beneficial for the authors to conduct additional experiments that simulate time-varying and agent-specific communication delays. This would provide a more comprehensive and realistic assessment of the algorithm's performance under diverse and dynamic network conditions.\n\n2. The evaluation of the proposed method would benefit from incorporating a broader range of datasets and models. Additionally, expanding the scale of the network-connected agents would be crucial to thoroughly validate the algorithm's effectiveness in more extensive and varied network environments.\n\n3. The hardware environment used in the experiments should be involved in the paper.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ucu0WSDXFa", "reviewer": "Reviewer_N9HH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Proposed a novel algorithm that includes weighted delay compensation for asynchronous decentralized learning.\n2. Related work section gives a good overview of all the existing works.\n3. Theoretical guarantees for the convergence rate of PC-ASGD are presented.\n4. Experimental results are presented for CIFAR-10 and CIFAR-100 for two different model architectures and 3 different network sizes.\n5. Compared with relevant baselines\n6. Presents ablation study on parameter $\\theta$, delay time $\\tau$, and network size $N$.\n\nWeaknesses/Questions:\n1. The second term in the predicting step needs access to $x_t^k$ and $g_{t-\\tau}^k$. Does this mean the proposed method need $2\\times$ communication for unreliable clients as they have to send both model parameters and gradients? Also, shouldn't the predicting step be $x_{t+1, pre}^i = \\sum_{j \\in R} w_{ij} x_t^j - \\eta g_i(x_t^i) + \\sum_{k \\in R^c}x_{t-\\tau}^k-\\eta g_k^{dc}(x_{t-\\tau}^k)$?\n2. According to the given delay compensation step, we have $x_{t+2}^k = x_t^k - \\eta [g_k(x_t^k)+\\lambda g_k(x_t^k) \\odot g_k(x_t^k) \\odot (x_{t+1}^i - x_t^i)]$. It is not clear to me how predicting agent k's gradient $g_k(x_{t+1}^k)$ using the agent i's model differences is an estimate for $(x_{t+1}^k - x_t^k)$. I see that since we have no access to $x_{t+1}^k$, we replaced $(x_{t+1}^k - x_t^k)$ in the Taylor series expansion with $(x_{t+1}^i - x_t^i)$. Can you explain why this is reasonable?\n3. The clipping step is equivalent to $x_{t+1, clip}^i = \\sum_{j \\in R} w_{ij} x_t^j - \\eta g_i(x_t^i)$. Introducing $\\tilde{w}_{ij}$ is unnecessary. \n4. Assumption 2c requires the mixing matrix to be positive semi-definite. This is not a standard assumption in decentralized learning algorithms. Why does PC-ASGD need this assumption? \n5. Table 4 shows that PC-ASGD-PV gives the best performance. In this experiment, can you provide some insights on how many times $\\theta$ takes the value of 1 vs 0 for PC-ASGD-PV? Let's say the model is trained for T iterations using PC-ASGD-PV. Then for a given agent-$i$, the clipping step was activated for $c_i$ iteration and the predicting step was activated for $p_i$ iterations. what are the values of $\\frac{1}{N} \\sum_j \\frac{c_j}{T}$ and $\\frac{1}{N} \\sum_j \\frac{p_j}{T}$?\n6. PreResNet110 and DenseNet are over-parameterized networks for CIFAR networks. Do you get similar improvements in accuracy over baseline if compact networks such as ResNet-20 are used? \n7. Section 5.2 says \"The detailed model structures are illustrated in the Appendix\". I couldn't find any details on model architectures in the appendix.\n8. The experiments are only conducted on a fully connected network. Will the proposed algorithm work for sparser decentralized topologies such as Torus and Social Network?\n9. What are the communication and compute overheads of PC-ASGD as compared to D-ASGD?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents a new delay-tolerant algorithm for decentralized learning referred to as Predicting Clipping Asynchronous Stochastic Gradient Descent (PC-ASGD). PC-ASGD includes two steps - the predicting step leverages the gradient prediction using Taylor expansion to reduce the staleness of the outdated weights while the clipping step selectively drops the outdated weights to alleviate their negative effects. The authors also present a practical variant of PC-ASGD. Convergence analysis of PC-ASGD for weakly strongly convex functions\nand nonconvex functions is shown. Experimental results validate the efficiency of the proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Page 13 contains one figure and the rest is just empty space. The paper needs reformatting.\n2. In equation 2, the LHS is $g_k^{dc,r}$ but $r$ is fixed from 0 to $\\tau-1$. Correct the notation.\n3. The clipping step can be replaced by the first term of the predicting step.\n4. Add discussion on the algorithmic differences between DCS3GD and PC-ASGD especially in terms of the delay compensation used (the predicting step). \n5. Experiments on optimized models meant for CIFAR datasets such as ResNet-20 could be useful. The current results are presented on over-parameterized networks.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces PC-ASGD, a novel algorithm addressing the challenge of stale weights or gradients in distributed optimization problems. PC-ASGD employs a two-step approach involving gradient prediction and clipping to mitigate the effects of communication delays, offering a unified framework for both synchronous and asynchronous algorithms. Theoretical analysis confirms the soundness and convergence rate of PC-ASGD, while extensive experiments showcase its effectiveness in various scenarios, model architectures, and network sizes, supplemented by an ablation study. PC-ASGD outperforms existing methods in terms of accuracy and efficiency, supported by comparisons with relevant baselines. The paper also provides a comprehensive overview of related work and addresses potential questions regarding its application in different network topologies and the comparison of communication and compute overheads with other algorithms. The paper is well-written well, and the authors have addressed the comments that reviewers had and incorporated the suggested changes into the updated version.
Decision: Accept (poster)