Ordered Momentum for Asynchronous SGD
Authors: Chang-Wei Shi
Yi-Rui Yang
Wu-Jun Li
Venue: NeurIPS 2024 poster (2024)
Keywords: optimization
deep learning
distributed learning
asynchronous SGD
Primary area: optimization

Abstract: Distributed learning is essential for training large-scale deep models.
Asynchronous SGD (ASGD) and its variants are commonly used distributed learning methods, particularly in scenarios where the computing capabilities of workers in the cluster are heterogeneous.
Momentum has been acknowledged for its benefits in both optimization and generalization in deep model training. However, existing works have found that naively incorporating momentum into ASGD can impede the convergence.
In this paper, we propose a novel method called ordered momentum (OrMo) for ASGD. In OrMo, momentum is incorporated into ASGD by organizing the gradients in order based on their iteration indexes. We theoretically prove the convergence of OrMo with both constant and delay-adaptive learning rates for non-convex problems. To the best of our knowledge, this is the first work to establish the convergence analysis of ASGD with momentum without dependence on the maximum delay. Empirical results demonstrate that OrMo can achieve better convergence performance compared with ASGD and other asynchronous methods with momentum.

Ordered Momentum for Asynchronous SGD
Chang- Weing-Weitae Shi
Yi-Rui Yang Wu-Jun Li"
National Key Laboratory for Novel Software Technology. School of Computer Science, Nanjing University, Nanjing, China {shicw, yangyr nju. edu. en, lisujunEnju.ce eecennjuuudu...
Abstract
Distributed learning is essential for training large-scale deep models. Asynchronous SGD (ASGD) and its variants are commonly used distributed learning methods, particularly scenarios where the computing capabilities workers the cluster are heterogeneous. Momentum has been acknowledged for its benefits in both opti- mization and generalization in deep model training. However, existing works have found that naively incorporating momentum into ASGD can impede the conver- gence. this paper, we propose a novel method called ordered momentum (OrMo) for ASGD. In OrMo, momentum is incorporated into ASGD by organizing the gradients order based on their iteration indexes. We theoretically prove the convergence of OrMo with both constant and delay-adaptive learning rates for non-convex problems. To the best of our knowledge, this is the first work to estab- lish the convergence analysis of ASGD with momentum without dependence on the maximum delay. Empirical results demonstrate that OrMo can achieve better convergence performance compared with ASGD and other asynchronous methods with momentum.
Introduction
Many machine learning problems can be formulated as optimization problems of the following form:
min F(w) = -EgwD [)]; weRd
(I)
where w denotes the model parameter, d is the dimension of the parameter, D represents the distribution of the training instances and f(w; denotes the loss on the training instance &.
Stochastic gradient descent (SGD) (28) and its variants [6 12] are widely employed to solve the problem in ( At each iteration, SGD uses one stochastic gradient or mini-batch of stochastic gradients as an estimate of the full gradient to update the model parameter. In practice, momentum (26] 36 24 B3 is often incorporated into SGD crucial technique for faster convergence and better generalization performance. Many popular machine learning libraries, such as TensorFlow I and include SGD with momentum (SGDm)
PyTorch 25
of the optimizers.
Due to the rapid increase in the sizes of both models and datasets in recent years, a single machine often insufficient to complete the training task of machine learning models within reasonable time. Distributed learning [42 37 aims to distribute the computations across multiple machines (workers) to accelerate the training process. Because of its necessity for training large-scale machine learning models, distributed learning has become a hot research topic recent years. Existing distributed learning methods can be categorized into two main types: synchronous distributed learning (SDL)
methods [99] 35| 29 38 [4] (3] and asynchronous distributed learning (ADL) methods [2]27] 8 47
17 43].
In SDL methods, faster workers that have completed the computation must wait idly for
*Corresooning author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

the other slower workers in each communication round. Hence, the speed of SDL methods is often hindered by slow workers. In contrast, faster workers do not necessarily wait idly for the other slower workers in ADL methods, because ADI methods require aggregating information from only one worker or subset of workers in each communication round. Representative ADL methods include asynchronous SGD (ASGI) and its variants 2 8 46 30
7 B1 13 In ASGD, once a worker finishes its gradient computation, the parameter (typically on the server) is immediately updated using this gradient through an SGD step, without waiting for other workers.
49
48
Momentum has been acknowledged for its benefits in both optimization and generalization in deep model training [33]. In SDL methods, momentum is extensively utilized across various domains,
including decentralized algorithms [88 45]. communication compression algorithms [19] [2 38 40
34 41), infrequent communication algorithms 44
39 40]. and federated learning algorithms 21 32]
However, in ADI. methods, some works 25 have found that naively incorporating momentum into ASGD may decrease the convergence rate or even result in divergence. To tackle this challenge, some more sophisticated methods have been proposed to incorporate momentum into ASGDD. The recommend tuning the momentum coefficient to enhance convergence performance when naively incorporating momentum into ASGD, The work in [2] proposes shifted momentum, which maintains local momentum on each worker. Inspired by Nesterov's accelerated gradient, the work in [4] proposes SMEGA², which leverages the momentum to estimate the future parameter. However, the process of tuning the momentum coefficient in 23 9 is mmeeccosumiig and yields limited improvement in practice. Although shifted momentum and SMEGA² can achieve better empirical convergence performance than the method which naively incorporates momentum into ASGD, both of them lack theoretical convergence analysis.
works in 23 [
In this paper, we propose novel method, called ordered momentum (OrMo), for asynchronous SGD, The main contributions of this paper are outlined as follows:
OrMo incorporates momentum into ASGD by organizing the gradients in order based on their iteration indexes.
We theoretically prove the convergence of OrMo with both constant and delay-adaptive learning rates for non-conver problems. To the best of our knowledge, this the first work to establish the convergence analysis for ASGD with momentum without dependence on the maximum delay.
Empirical results demonstrate that OrMo can achieve better convergence performance compared with ASGD and other asynchronous methods with momentum.
2 Preliminary
In this paper, we use ||.|| to denote the L2 norm. For a positive integer n. we use [r]] to denote the set (0. 1,2...., 1}. V((w; denotes the stochastic gradient computed over the training instance and model parameter where the server is responsible for storing and updating the model parameter and the workers are responsible for sampling training instances and computing stochastic gradients. For simplicity, assume that each worker samples one training instance for gradient computation each time. The analysis of mini-batch sampling on each worker follows similar approach.
In this paper, we focus on the widely used Parameter Server framework (15).
One of the most representative methods for distributing SGD across multiple workers is Synchronous SGD (SSGD) (20 [0]. Distributed SGD (DSGD), presented in Algorithm 1 unifies SSGD and ASGD within single framework 13. The waiting set C in Algorithm T is a collection of workers (indexes) that are awaiting the server to send the latest parameter. The only difference between SSGD and ASGD the communication scheduler associated with the waiting set. SSGD corresponds to DSGD with synchronous communication scheduler, while ASGD corresponds to DSGD with asynchronous communication scheduler. We use Bite(k,.)) to denote the stochastic
gradient V V f (w )*x), where ky is the index of the worker whose gradient participates in the parameter update at iteration / and ght denotes a training instance sampled on worker kG, The function ite(k, 1) denotes the iteration index of the latest parameter sent to worker & before iteration I, where
k, k E [K] and E [T]. The delay of the gradient 8ite(k).)) is defined as 7, = t - ite(ks, t). When
K 1, DSGD degenerates to vamilla SGD, i.c., ite(ke, t) = t.

---

Algorithm Distributed SGD
1: Server:
2: Input: number of workers K, number of iterations T,, learning rate 7y;
3: Initialization: initial parameter wo, waiting set C = 0;
4: Send the initial parameter wo to all workers;
5: for = 0 to T - do
6: Receive stochastic gradient 4 (k)) from some worker kz;
7: Update the parameter Wt-1 = W; ng (k,,))
8: Add the worker be to the waiting set C (kz):
9: Execute the communication scheduler:
Option I: (Synchronous) only when all the workers are in the waiting set, i.e., C = [K]. send the parameter Wi+1 the workers in C' and set C 0:
Option II: (Asynchronous) once the waiting set is not empty, i.c., C + 0, immediately send the parameter We+1 to the worker in C' and set 0;
10: end for
Notify all workers stop:
12:
Worker : (A E [K])
repeat
14: Wait until receiving the parameter w from the server;
Randomly sample g ~ D and then compute the stochastic gradient g* VV[(w:gh)
Send the stochastic gradient g the server,
17: until receive server's s notification to stop
In ASGD, the latest parameter W will be immediately sent back to the worker after the server updates the parameter at each iteration. The function ite(k, t) in ASGD can be formulated follows:
0
0, k [K],
ite(k,t)
t 0, k
(it((k(-1)
1> 0, k + k1-1,
where & [K],t E [T].
In SSGD, there is a barrier in the synchronous communication scheduler since the latest parameter Wr+1 will be sent back to the workers only when all the workers are in the waiting set. The function
ite(k, t) in SSGD can be formulated as ite(k, t) =1 K, where k E [K], E (T] and [-] the floor function.
Remark 1. In existing works 10 22
SSGD is often presented in the form of mini-batch SGD:
i
W W.
vf(ws:E"),
K
KE[K]
where & E [S] and S denotes the number of iterations. Here, all workers aggregate their stochastic gradients to obtain the mini-batch gradient 1 EkE[K] f: which then used to update the parameter. To unify SSGD and ASGD into single framework in Algorithm ! we reformulate SSGD the form of mini-batch SGD in (2). Specifically, one update using mini-hatch gradient computed over K training instances in 2 is split into K updates, each using a stochastic gradient over a single training instance. Letting 17 K = KS and Wo = Wo. the sequence {Wak hee(s)
SSGD Algorithm matches (Ws)e in
Ordered Momentum
In this section, we first propose new reformulation of SSGD with momentum, which inspires the design of ordered momentum (OrMo) for ASGD. Then, we present the details OrMo, including the algorithm and convergence analysis.

---

3.1 Reformulation of SSGD with Momentum
The widely used SGD with momentum (SGDm)
26 can expressed follows:
W W++ = Ws Sü,
V (w.;E),
(3)
[
CEB,
n +++ Gü, +
V ().;
(4)
13
EEB,
where U, 0, [0,1), E [S] and denotes the number of iterations. 3 is the momentum coefficient. ü, represents the Polyak's 's momentum. [B_] LEEB. Vf (w,iE) denotes the stochastic gradient computed over the sampled training instance set B3, which contains either single training instance or a mini-batch of training instances sampled from D. 33) denotes the parameter update step and (4) denotes the momentum update step. When / 0, SGDm degenerates (mini-bated SGD.
Since SSGD can be presented in the form of mini-batch SGD as depicted in Remark I it's straight- forward to implement SSGD with momentum (SSGDm) as follows:
Wo+1 W, -Bū.-
Σ KE
Vf(Wsi
(5)
ú,+1 "ü, + K
Σ Vf(WsiE"),
Kε(K]
where ün 0. 1), [S] and denotes the number of iterations. Here, the server aggregates the stochastic gradients from all the workers obtain the mini-batch gradient 1 Σ V/((s: < which is then used update both the parameter and the momentum (
To gain insights from SSGDm on incorporating momentum into ASGD, we reformulate SSGDm in (5) to fit into the framework of Algorithm [ Similar the reformulation in Remark the updates using a mini-batch gradient computed over training instances in (5) are split into K updates, each using stochastic gradient over a single training instance. The corresponding implementation details of SSGDm are presented in Algorithm in Appendix B
In this way, the update rules of SSGDm in
(5) can be reformulated follows:
W:
Su,
K 1
W
W:
K t t
[Bur
K t,
u
[1
tt,
Wi+11 = W 118" & JKK
u++1 u 1 + ng |
where un = 0, 0, [
VS(w jii **) and E [T]. give the following proposition about
the relationship between the sequences in 5 and those in 6 The proof details can be found in Appendix(C..1.
Proposition 1. Letting 1j = á
R = KS and wo = Wo. the sequences {wak beefs] and hees)
in (6 are equivalent to {we).e(s) and
in 5) respectively.
We investigate how the momentum term u++1 evolves during the iterations in 66. For t K and
t [T), u1+1 can be formulated as:
LKJ-1
U = Σ
g Σ
+ +
Σ
ng K
ng.k KE[K]
5=
where the superscript of the scalar /3 indicates the exponent. For K, u,41 = 180 E ng Figure shows uno example when K 4. We define {ng.. mglk, ".. K- ,,, the i-th

---

nga
1
8
78
78
ng
09
Figure 1: An example of the momentum term U1o in SSGDm when K 4. The gradi- ents shown in red indicate those having not arrived at the server. In this case, u10 = B x (ng8 + 7go + ngō + ngo)) 3 (ngl + ngi + ngi + ngs) + +0 (ng) ngg)
(scaled) gradient group, which contains K gradients scaled by the learning rate 1j. The order of the gradient groups is based on the iteration indexes of their corresponding gradients. Though some gradients may be missing because they have not yet arrived at the server, the momentum is weighted sum of the gradients from the first several gradient groups. Hence, the momentum in SSGDm is referred to as an ordered momentum. Specifically, the gradients the i-th gradient group are weighted by BL - in the momentum u,+1, where i E [l + 1]. We refer to the gradient group whose gradients are weighted by 3 as the latest gradient group, which contains the latest gradients. For U in SSGDm, the latest gradient group corresponds to the J gradient group.
Due to the barrier in the synchronous communication scheduler in SSGDm as presented in Algo- rithm 3 the gradients in SSGDm consistently arrive at the server in the order of their iteration indexes. The arriving gradient always belongs to the latest gradient group at each iteration. Thus, maintaining such ordered momentum in SSGDm is straightforward. As shown in line 13 of Algorithm the scaled gradient (e is always added to the momentum with weight of 8 at each iteration. However, for ASGD, since the gradients arrive at the server out of order, it's not trivial to incorporate such an ordered momentum. To address this problem, we propose a solution in the following subsection.
3.2 Or.o for ASGD
In this subsection, we introduce our novel method called ordered momentum (OrMo) for ASGD, and present it in Algorithm? 2
Firstly, we define the (scaled) gradient groups in OrMo for ASGD. Due to the differences in the communication scheduler, the iteration indexes of the parameters used to compute the gradients in ASGD differ from those in SSGD (SSGDm). Specifically, the sequence of gradients computed in SSGD (SSGDm) can be formulated as:
go go:
go K gK BK
.8K
K-1
82K 82K
82k
K-1
In contrast, the sequence of gradients computed in ASGD given by:
kx B0 gd: k-1 to g gk
BK+1
kx
BK42
Jak 82k
....
(8)
Thus, the i-th (scaled) gradient group OrMo for ASGD defined as:
Íリ-クı ng (1) MB (B
R MB.K
where i i The 0-th (scaled) gradient group in OrMo is {ngh 7gh ...
K11. Despite the difference in the gradients' iteration indexes, each gradient group in OrMo for ASGD also contains K gradients scaled by the learning rate 17, similar to that in SSGDm as discussed in Subsection 3.1
We use 1,11 denote the index of the latest gradient group of ur+1 in OrMo. The iteration index of the latest gradient in us+1 can be at most. Since the gradient with iteration index belongs to the ( 1-th gradient group, the latest gradient group for ur+1 should be the [ 1-tt gradient group, i.c.. 4++1 = & Vt [T'. u,+1 is the weighted sum of the gradients from the first le+1 + 1 gradient groups, where some gradients may be missing because they have not yet arrived at the server. The gradients in the i-th gradient group are weighted by 3 + in the momentum u,+1s where i [7441 + 1] and the superscript of the scalar 3 indicates the exponent. Figure shows example of Uno in OrMo when K =
For the t-th iteration in OrMo, the server performs the following operations:
5

---

Algorithm 2 OrMo
1: Server:
2: Input: number of workers K, number of iterations T, learning rate y, momentum coefficient
B E 1);
3: Initialization: initial parameter Wo, momentum Ug 0, index of the latest gradient group
To = 0. waiting set C = 0;
4: Send the initial parameter wo and its iteration index all workers;
5: for = 0 to T 1 do
6: if the waiting set is empty and [ 1 then
7:
W = Wt Bu,, 4 = Su,, I++1 = I + 1;;
8: else
9:
W = Wr. 4++ = ue 1++1 = 45
10:
end if
11:
Receive a stochastic gradient 5 ()) and its iteration index ite(k;, t) from worker &, di (kee( belongs to);
and then calculate [(tekked)) (i.e., the index of the gradient group that
12: Update the momentum U u + 84 1 (t)
())) (MB(ic()))))
Update the parameter W.-1 W 1- 8 12
13:
1-B
14:
Add the worker & to the waiting set C' C (kr):
15:
Execute the asynchronous communication scheduler: once the waiting set not empty, i.e.,
C + 0, immediately send the parameter We+1 and its iteration index t + 1 to the worker in C and set C to 9;
16: end for
17:
Notify all workers to stop:
18: Worker k: (A [K])
19: repeat
20: Wait until receiving the parameter wy and its iteration index t' from the server;
21: Randomly sample ş ~ 'D and then compute the stochastic gradient g² <[wwes""
22:
Send the stochastic gradient g and its iteration index the server;
23:
until receive server's notification stop
1
ng
18
8
1
119:
B
n
18:
08
ngc
Figure 2: An example of the momentum term U1o in OrMo when K = 4. The gradients shown in red
indicate those having not arrived the server. this case, U10 93 (ng] ngg ngō ng))
B² ( + ng. ngg") + B² x (nge + ng. f0 x mB
I, has been sent to some worker, update the parameter using the momentum and multiply the momentum with B: We+1 = W. Su; u Su, Ic+1 = I
the parameter with iteration index t that satisfies [
In this way, the momentum changes the index of its latest gradient group to ready to accommodate the new gradient with iteration index t.
k and gets
A Receive stochastic gradient (ite(k..)) and its iteration index ite(k,, from some worker ke
& and calculate (kke))..) which is the index of the gradient group that Bite(kr,t) belongs
Update the momentum: u,+1 = u +
(e
Since the weight of the scaled gradients from the latest gradient group the momentum is go.
the weight of the gradients from the (ite(k..))) .!) -thh gradient group should be g4++1-1 stelky..)

---

OrMo updates the momentum by adding the scaled gradient (K into the momentum
with a weight of gle+1 sttckr.f)
Update the parameter: W W 1-8fe41 12
(ng (
1-8
The update rule the parameter in OrMo is motivated by that SSGDm, as presented in Algorithm 3 In SSGDm, the scaled gradient 1/g (tk,, always added to the momentum with weight of 130 At the current iteration, this scaled gradient updates the parameter with a coefficient -30. In subsequent iterations, this scaled gradient in the momentum updates the parameter with the coefficients 3, =B,, -B3 ..... By the time this scaled gradient is weighted by 3/441-1 -
in the momentum of SSGDm, it has already updated the
parameter for I++1 (k ) + steps, with a total coefficient E/=001 # 35, In OrMo, for the scaled gradient 1]Bite(k,..) which is added to the momentum with a weight of 3/
compensate for the missed I4+1 (ite(ks.() 1 + 1 steps compared with
SSGDm and update the parameter with the coefficient 1- 8 (ack)..) 1+1
the current
iteration. The design of the parameter update rule is crucial for the derivation of Lemma 2 which is further supported by the ablation study in Appendix A..3
Add the worker k to the waiting set C = C U {ka} and execute the asynchronous communi- cation scheduler.
Remark 2. Compared to ASGD, the additional communication overhead introduced by the iteration index OrMo is negligible since the iteration index only scalar.
Remark 3. When the momentum coefficient 3 is set to O, OrMo degenerates to ASGD in Algorithm 7 If the usynchronous communication scheduler in line 15 of Algorithm 2 is replaced by a synchronous communication scheduler: only when all the workers are in the wailing set, i.e., C = [K], send the parameter Wi11 and the iteration index L. to the workers in and set C to 0, OrMo degenerates SSGDm in Algorithm 3
3.3 Convergence Analysis
In this section, we prove the convergence OrMo in Algorithm for non-convex problems. We only present the main results here. The proof details can be found in Appendix C
We make the following assumptions, which are widely used in distributed learning 47
43
Assumption 1. For any stochastic gradient V f((w; E). we assume that it satisfies:
RE-D (V (w::([(])))) {)] = F(w)), Re- BI [WW: - VF(w))l S o², YWER..
Assumption 2. For any stochastic gradient V fw: E). we assume that it satisfies:
BEnD Be>D|V// (W: Gw, Vw Rd.
Assumption 3. F(w) is L-smooth (L > 0):
F(w) S F((') + VF(W') w') + 2 I 1l w w'l, WIR.V.. Vw, w' E ER.
Assumption 4. The objective function F(w) is lower bounded by F": F(w) 2 F*, Vw E Rd. Firstly, we define the auxiliary sequence (úr for the momentum: ú Eke(k] vgg. and
[ū, + ngi Re-1
K (1 1),
ú
ngt hi-1
K { (t 1),
for 2 1.
Lemma 1. For any t 2 0, the gap between u441 and ú4f1 can be formulated follows: Re((.)) K (ite((k.))
ú U141
Σ
a 1
(9)
7

---

Then, we define the auxiliary sequence [weh22 for the parameter: W1 = Wo ΣKE[K]] 7g2 and
W. Bü; ~//
he-1
K (t-1);
We+1
Ww 78t A
K kt (t(t-1);
for 2 1.
Lemma 2. For any t 2 O, the gap between Wi+1 and We+1 can be formulated as follows: 2t 3 (
W W++1 W++1
78 (k))))
(10)
kE[K],ATE,
Then, we define another auxiliary sequence (8:)e21: ÿ1 for t 2 Lemma 3. For any L 2 1, the gap between Vr. and we, can be formulated as follows:
Bwo
and Je+1 = -
h1-1
1-8
I-
83
y: W.
1-8 ú
(1I)
1-8 (1-8)
Theorem 1. With Assumptions 1
12 2
3 and 4 letting min
Algo-
2KT.
(LT)
[LKG)
rithm 2 has the following convergence rate:
1
E BVVF( 0o
1L02 +
Lo2
KKG T
KL
+ T
T
where F(wo) F and 2 K.
22 consider delay-adaptive methods for ASGD) The key insight of these methods is to penalize the gradients with large delays and reduce their contribution to the parameter update. OrMo is orthogonal to these delay-adaptive methods. Concretely, we can replace the constant learning rate 17 in Algorithm with delay-adaptive learning rate Th, which is dependent the delay of the gradient 7z. Inspired by [33, we adopt the following adaay-ade learning rate f/:-
Many works 46
S 2K,
VJr
min
Te > 2K.
4LT
The convergence of OrMo with the above delay-adaptic learning rate (called OrMo-DA) is guaran- teed by Theorem 2
Theorem 2. With Assumptions
1 and letting =min
(1-312 SKT.
V
(1-9)AA Th."
J. OrMo-DA has the
following convergence rate:
(
Loz T
KT. T
E VVF((T)) 2 so
+
where A = -(ww)) F and wT is randomly chosen from (Wo: W1, WT- ) according probubility distribution which is related to the delay-culeptive learning rales.
The proof details can be found in Appendix C.3 Compared with Theorem I Theorem removes the dependence on Assumption (bounded gradient) and provides better convergence bound.
Remark 4. We focus the scenario where the training instances across all workers independent and identically distributed (i.id.) from 'D. This scenario commonly appears in the data-center setup for distributed training [5V, where all workers have access the full training dataset. Our analysis for the i.i.d. scenario can also provide insights into the analysis in a non-i.i.d. scenario [22], which will be studied in future work.
Remark 5. Most existing theoretical analyses of ASGD 16
20 rely on the maximum delay
Tmaz (e.g., O61 "LL + +mmqr)) in (201), where Traa m Tt- However, since ASGD can still perform well even when the maximum delay is extremely large (Tmaz > K) in practice these theoretical analyses don') it accurately reflect the true behavior of ASGD. The most closely related works to this work are (13 22), which analyze ASGD without relying the muximum delay. But the works [3 22) do not consider momentum. To the best of our knowledge, this is the first work to establish the convergence guarantee of ASGD with momentum without relying the maximum delay.

---

Table 1: Empirical results of different methods on CIFAR10 10 dataset.
Number Workers
(Dom)) )
(hom.
16 (bei.)
64 (her)
Methods
Training Loss
Test Accunccy
Training Loss
Test Accuracy
Trmining Loss
Test Accunacy
Training Loss
Test Accuracy
ASCD
0.66 1: 0.00
89.77 1: 0.11
0.40 :: 0.00
83.14
0.55
0.06 =: 0.00
80.73 2 0.19
0.58 :: 0.00
83.94 0:2.11
nave ASGDm
0.20 0.07
88.15
1.70
0.44 0.06
82.39
1.79
0,58 0.86
73.23 1: 31.61
0.78 4: 0.77
68.75 1: 29.51
shifted momentum
90.23
0.38
83.72
0.02
89.95
SMEGA?
0.08 0.01
90.00
+ 0.42
0.25
+: 0.04
36,82
0.69
0.04 +: 0.01
90.88
0.25
0.22 +: 0.07
86.89
1.42
OrMo
0.01 0.01
90.95
1: 0.27
0.15 0
88,03
0.28
0.04 2: 0.00
91:01 0.10
0.16 1: 0.03
87.76
0.57
OrMo-DD DA
0.01
91.17 + 0.18
0.16 0.02
98.03
0.01
91.28
0.15 + 0.02
58.08
Table 2: Empirical results of different methods on C10AR100 dataset.
Number Woekers
16
(hom)
(bet.)
64
Methods
Training Loss
Test Accuracy
Training Loss
Test Accuracy
Training Loss
Test Accuracy
Training Loss
Test Accuracy
ASGD
0.51 0.01
66.16
0.95 0.03
61.61 0.59
0.51 +: 0.01
65.94 +: 0.39
0.95
61.74 =: 0,30
nahe ASCiDm
0.54 + 0.01
65.46:20330 0.20
1.03 = 0.05
59.96 = 0.90
0.53 = 0.00
65.69 4 0.42
0.97 2 0.06
61.13 =: 1.02
shifted momentum
0.47 0.01
66.77
0.82 1 0.01
63.55
0.32
0.47 2 0.00
66.18 1: 0.14
0.82 0.04
63.28 0.66
SMEGA
0.00
67.32:1003
0.69 0.00
64.16
= 0:12
0.40 0.01
67.29 4: 0.16
0.68
64.12 0.53
OrMo
0.41 1 0.01
67.56 0.34
0.56 1: 0:00
65.48
1: 0.17
0.40
2: 0.01
67.71
1: 0.33
0.58
1: 0.02
65.43
2: 0.35
OrMo- DA
0.40 0.00
67.72 1: 0.21
0,56 0.01
65.79
0.12
0.04 0.00
67.82
1 0.20
0.57 0.01
65.82 0.30
Experiments
In this section, we evaluate the performance of OrMo, OrMo-DA and other baseline methods. All the experiments are implemented based on the Parameter Server framework [T5]. Our distributed platform is conducted with Docker. Each Docker container corresponds to either a server or a worker. All the methods are implemented with PyTorch 1.3.
The baseline methods include ASGD, naive ASGDm which naively incorporates momentum into ASGD 233 shifted momentum 9 and SMEGA² [4]. The details of naive ASGDm are shown in
Algorithm 4 In OrMo-DA, for gradient with large delay satisfying T; 2K, its corresponding
learning rate will be multiplied by We evaluate these methods by training ResNet20 model [I]] on CIFAR1O and CIFAR 100 datasets [14. The number of workers is set to 16 and 64. The batch size on each worker is set to 64. The momentum coefficient is set to 0.9. Each experiment is repeated 5 times. The experiments are conducted under two settings:
Setting I [homogeneous (hom.)]: each worker has similar computing capabilities, which ensures comparable average time for gradient computations.
Setting II [heterogeneous (het.)]: some workers G of all) are designated as slow workers, with an average computation time that is 10 times longer than that of the others.
For the CIFARIO dataset, the weight decay set to 0.0001 and the model is trained with 160 epochs. The learning rate is multiplied by 0.1 at the 80-th and 120-th epoch, as suggested in [ The experiments for the CIFARIO dataset are conducted on NVIDIA RTX 2080 Ti GPUs. For the CIFAR100 dataset, the weight decay is set to 0.0005 and the model is trained with 200 epochs. The learning rate is multiplied by 0.2 at the 60-th, 120-th and 1 160-th epoch, as suggested in [40] The experiments for the CIFAR 100 dataset are conducted on NVIDIA V100 GPUs.
Table D and Table show the empirical results of different methods. Figure and Figure show the test accuracy curves of different methods. We also present the test accuracy curves of SSGDm for reference in Figure
Figure Training loss curves can found Appendix A.. Compared with other asynchronous methods, OrMo and OrMo-DA can achieve better training loss and test accuracy, As shown in Figure 3 naive ASGDm occasionally fails to converge under Setting II. We can find that naively incorporating momentum into ASGD will impede its convergence. Due to the existence of slow workers, the maximum delay under Setting II is far greater than that under Setting I. For example, when training the CIFAR 10 dataset with K 64, the maximum delay under Setting is about 30000, while it's around 300 under Setting I. OrMo and OrMo-DA perform well under both settings, which aligns with our theoretical results without dependence on the maximum delay.
presents the training curves of OrMo and SSGDm with respect to wall-clock time. As shown in Figure 5(b) OrMo can be 8 times faster than SSGDm under Setting II since the training speed of SSGDm is hindered by slow workers. In contrast, slow workers have limited impact on OrMo's 's training speed. Even under Setting where each worker possesses similar computing
Figure 5

---

30
ASGO
OHMADA
DA 120
(a) K 16 (hom.)
(b) 64 (hom.)
(c) K 16 (het.)
(d) K 64 (het.)
Figure 3: Test accuracy curves on CIFARIO with different numbers of workers.
ASSD
ASCD
ASCO
ADGO
29
D/M-DA
(a) 16 (hom.)
(b) 64 (hom.)
(c) K 16 (het.)
(d) 64 (het.)
Figure 4: Test accuracy curves on CIFARI00 with different numbers of workers.
1.55
1.5
1.5
1123
1.2
1130
5500m
0.5
630
6.9
Wencceok Trme
Wallcloo Time
Wel-Cboos 30
(a) homogencous
(b) heterogeneous
Figure 5: Training curves with respect to wall-clock time on CIFARIO when K = 16.
capability, OrMo still be more than twice fast as SSGDm, shown in Figure ((a) This advantage arises because the computation time of each worker varies within a certain range even under the homogeneous setting and some workers must wait for others finish gradient computations in SSGDm.
Conclusion
In this paper, we propose a novel method named ordered momentum (OrMo) for asynchronous SGD, We theoretically prove the convergence of OrMo with both constant and delay-adaptiv learning rates for non-conver problems. To the best of our knowledge, this is the first work establish the convergence analysis of ASGD with momentum without dependence on the maximum delay. Empirical results demonstrate that OrMo can achieve state-of-the-art performance.
Acknowledgment
This work is supported by National Key R&D Program of China (No. 2020YFA0711900), NSFC Project (No. 12326615), Major Key Project of Pengcheng Laboratory (No. PCI.2024A06) and Key R&D Project of Jiangsu Province (No. BE2023652).
10

---

References
[1] Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek Gordon Murray, Benoit Steiner, Paul A. Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. Tensorflow: A system for large-scale machine learning. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation, pages 265-283, 2016.
[2] Alekh Agarwal and John C. Duchi. Distributed delayed stochastic optimization. In Advances in Neural Information Processing Systems, pages 873 181, 2011.
[3] Yossi Arjevani, Ohad Shamir, and Nathan Srebro. A tight convergence analysis for stochastic gradient descent with delayed updates. In Proceedings of the International Conference on Algorithmic Learning Theory, pages 1 11--122 2020.
[4] Refael Cohen, Ido Hakimi, and Assaf Schuster. SMEGA2: distributed asynchronous deep neural network training with single momentum buffer. In Proceedings of the International Conference on Purallel Processing, pages 1-10, 2022.
[5] Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Quoc V. Le, Mark Z. Mao, Mare Aurelio Ranzato, Andrew W. Senior, Paul A. Tucker, Ke Yang, and Andrew Y. Ng. Large scale distributed deep networks. In Advances in Neural Information Processing Systems, pages 1232-1240, 2012.
[6] Aaron Defazio, Francis R. Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Information Processing Systems, pages 1646-1654, 2014.
[7] Sanghamitra Dutta, Gauri Joshi, Soumyadip Ghosh, Parijat Dube, and Priya Nagpurkar. Slow and stale gradients win the race: Error-runtime trade-offs in distributed SGD. In Proceedings of the International Conference on Artificial Intelligence and Statistics, pages 603-812, 2018.
[8] Hamid Reza Feyzmahdavian, Arda Aytekin, and Mikael Johansson. An asynchronous mini- batch algorithm for regularized stochastic optimization. IEEE Transactions on Automatic Control, (1(12):3740337555 2016.
[9] Niv Giladi, Mor Shpigel Nacson, Elad Hoffer, and Daniel Soudry. At stability's edge: How adjust hyperparameters to preserve minima selection in asynchronous training of neural networks? In Proceedings of the International Conference on Learning Representations, 2020.
[10] Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint arXiv: 110177066627777 2017.
[11] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for im- age recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 770-778, 2016.
[12] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, pages 315 1-5--23, 2013.
[13] Anastasia Koloskova, Sebastian U. Stich, and Martin Jaggi. Sharper convergence guarantees for asynchronous SGD for distributed and federated learning. In Advances in Neural Information Processing Systems, pages 17202-17215, 2022.
[14] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, 2009.
[15] Mu Li, David G. Andersen, Alexander J. Smola, and Kai Yu. Communication efficient dis- tributed machine learning with the parameter server. In Advances in Neural Information Processing Systems, pages 19-27, 2014.

---

[16] Xiangru Lian, Yijun Huang. Yuncheng Li, and Ji Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. In Advances in Neural Information Processing Systems, pages 2737-2745, 2015.
[17] Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. In Proceedings of the International Conference on Machine Learning, pages 3043-3055 2018.
[18] Tao Lin, Sai Praneeth Karimireddy, Sebastian U. Stich, and Martin Jaggi. Quasi-glober momentum: Accelerating decentralized deep learning on heterogeneous data. Proceedings of the International Conference on Machine Learning, pages 6654-6665, 2021.
[19] Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally. Deep gradient compression: Reduc- ing the communication bandwidth for distributed training. In Proceedings of the International Conference on Learning Representations, 2018.
[20] Ji Liu and Ce Zhang. Distributed learning systems with first-order methods. Foundations and Trends@ Databases, 911):1-100, 2020.
[21] Wei Liu, Li Chen, Yunfei Chen, and Wenyi Zhang. Accelerating federated learning via momen- tum gradient descent. IEEE Transactions on Parallel and Distributed Systems, (165) 2020.
[22] Konstantin Mishchenko, Francis R. Bach, Mathieu Even, and Blake Woodworth. Asyn- chronous SGD beats minibatch SGD under arbitrary delays. In Advances in Neural Information Processing Systems, pages 420-433, 433, 2022.
[23] loannis Mitliagkas, Ce Zhang, Stefan Hadjis, and Christopher Ré. Asynchrony begets momen- tum, with an application to deep learning. Proceedings of the Annual Allerton Conference on Communication, Control, and Computing, pages 997-1004, 2016
[24] Yurii Nesterov. Introductory lectures on corvex optimization: A basic course. Springer Science & Business Media, 2013.
[25] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang. Zachary Vito,o, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, pages 8024-8035, 2019.
[26] Boris Polyak. Some methods of speeding up the convergence of iteration methods. Ussr Computational Mathematics and Mathemutical Physics, 4:1-17, 12 1964.
[27] Benjamin Recht, Christopher Ré, Stephen J. Wright, and Feng Niu. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Advances in Neural Information Processing Systems, pages 693-701, 2011.
[28] Herbert Robbins and Sutton Monro. A stochastic approximation method. Annals of Mathemati- cal Statistics, 22:400-407, 1951.
[29] Chang- Shi, Shen-Y. Yi Zhao, Yin-Peng Xie, Hao Gao, and Wu-Jun Li. Global momentum compression for sparse communication distributed learning, arXiv preprint arXiv: /905. 12948, 2019.
[30] Suvrit Sra, Adams Wei Yu, Mu Li, and Alex Smola. Adadelay: Delay adaptive distributed stochastic optimization. In Proceedings of the International Conference on Artificial Intelligence and Statistics, pages 957-965, 2016.
[31] Sebastian U. Stich, Amirkeivan Mohtashami, and Martin Jaggi. Critical parameters for scalable distributed learning with large batches and asynchronous updates. Proceedings of the International Conference Artificial Intelligence and Statistics, pages 4042-4050, 2021.
12

---

[32] Jianhui Sun, Xidong Wu, Heng Huang, and Aidong Zhang. On the role of server momentum in federated learning. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 15164-15172, 2024.
[33] lyy Sutskever, James Martens, George E. Dahl, and Geoftrey E. Hinton. On the importance of initialization and momentum in deep learning. In Proceedings of the International Conference on Machine Learning, pages 1 1139- 147, 2013.
[34] Hanlin Tang, Shaoduo Gan, Ammar Ahmad Awan, Samyam Rajbhandari, Conglong Li, Xiangru Lian, Ji Liu, Ce Zhang, and Yuxiong He. 1-bit adam: Communication efficient large-scale scale training with adam's 's convergence speed. In Proceedings of the International Conference on Machine Learning, pages 10118-10129, 2021.
[35] Hanlin Tang. Shaoduo Gan, Ce Zhang, Tong Zhang, and Ji Liu. Communication compression for decentralized training. In Advances Neural Information Processing Systems, pages 1673, 2018.
[36] Paul Tseng. An incremental gradient(-projection method with momentum term and adaptive stepsize rule. SIAM Journal on Optimization, 8(2):506 531, 1998.
[37] Joost Verbraeken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg, Tim Verbelen, and Jan S Rellermeyer. A survey on distributed machine learning. ACM Computing Surveys, 53(2):1-33, 2020.
[38] Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. Powersgd: Practical low-rank gradi- ent compression for distributed optimization. In Advances Neural Information Processing Systems, pages 14236-14245 2019.
[39] Jianyu Wang, Vinayak Tantia, Nicolas Ballas, and Michael G. Rabbat. Slowmo: Improv- ing communication-efficeen distributed SGD with slow momentum. In Proceedings of the International Conference on Learning Representations, 2020.
[40] Cong Xie, Shuai Zheng, Oluwasanmi Koyejo, Indranil Gupta, Mu Li, and Haibin Lin. CSER: Communication-efficee SGD with error reset. In Advances in Neural Information Processing Systems, pages 12593-12603, 2020.
[41] An Xu and Heng Huang. Detached error feedback for distributed SGD with random sparsifica- tion. In Proceedings of the International Conference on Machine Learning, pages 24550-24575, 2022.
[42] Tao Yang, Xinlei Yi, Junfeng Wu, Ye Yuan, Di Wu, Ziyang Meng, Yiguang Hong, Hong Wang, Zongli Lin, and Karl H Johansson. survey of distributed optimization. Annual Reviews in Control, 47:278-305. 2019.
[43] Yi-Rui Yang and Wu-Jun Li. BASGD: buffered asynchronous SGD for byzantine learning. In Proceedings of the International Conference on Machine Learning, pages 1151-117711, 2021.
[44] Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum SGD for distributed non-convex optimization. In Proceedings of the International Conference on Muchine Learning, pages 7184-7193, 2019.
[45] Kun Yuan, Yiming Chen, Xinmeng Huang, Yingya Zhang, Pan Pan, Yinghui Xu, and Wotao Yin. Decentlam: Decentralized momentum sgd for large-batch deep training. Proceedings of the IEEF/CVF International Conference on Computer Vision, pages 3029-3039, 2021.
[46] Wei Zhang, Suyog Gupta, Xiangru Lian, and Ji Liu. Staleness-aware async-sgd for distributed deep learning. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 2350-2356 2016.
[47] Shen-Y Yi Zhao and Wu-Jun Li. Fast asynchronous parallel stochastic gradient descent: A lock- free approach with convergence guarantee. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 2379-2388 2016.
13

---

[48] Shen- Yi Zhao, Gong-Due Duo Zhang, and Wu-Jun Li. Lock-free optimization for non-convex problems. Proceedings of the AAAI Conference on Artificial Intelligence, pages 2935-2941, 2017.
[49] Shuxin Zheng, Qi Meng, Taifeng Wang, Wei Chen, Nenghai Yu, Zhiming Ma, and Tie- Yan Liu. Asynchronous stochastic gradient descent with delay compensation. In Proceedings of the International Conference Machine Learning, pages 4120-4129, 2017.
14

---

ARRD
ASRO
ASRO
ADED
Cella
GE 14
120 100
24 120
(a) K 16 (hom.)
(b) K 64 (hom.)
(c) K 16 (het.)
(d) K 64 (het.)
Figure 6: Training loss curves of different methods CIFAR10 dataset with different numbers of workers.
ARRD
ARRI
ARNO
ADRIO
ASGO
ISEN ASGOT
salve ASGO
86
30
30
GMOUA
SREGA
2..0
SNEGGA
OINODA
C4
22
20
1.8
50
1.3
50
08
855
0.5
8.5
(a) 16 (hom.)
(b) 64 (hom.)
(c) K 16 (het.)
(d) 64 (het.)
Figure 7: Training loss curves of different methods on CIFARIO0 dataset with different numbers of workers.
Table 3: Empirical results of naive ASGDm with different 3 when training ResNet20 on CIFARIO dataset.
workers
16 (hom.)
(hom))
16 (lot.)
64 (het.)
Algoritim (8)
Training Loss
Test Accunwy
Training Loss
Test Accuraty
Training Loss
Test Accurncy
Training Loss
Test Aucunay
naive ASCDD (0.1)
0.06 = 0.01
80:85 2: 0.24
0.38 + 0.01
83:03
1:
0.06 = 0.00
89:95 0.19
0.38 = 0.01
83.76 1.76:1000 0.3.
mave ASGDm (0.3)
0.06 0.00
39.91
1: 0.20
0.36 0.02
84:23
0.49
0.05 :: 0.01
90.26 1: 0.05
0.35 4 0.02
84.43
0.22
mive ASGDe
0.00
83:87
90.56:10.13
84.07
naive ASCDe (0.9)
0.20 0.07
58.15 1.70
0.06
82:30
1.79
0.58 0.96
71.23 31.61
0.78 - 0.77
29.51
OrMo (0.9)
0.04 :: 0,01
90,95 1 0.27
0.15 1 0.02
88.03 1: 0.28
0,04 1: 0.00
91.01 1: 0.10
0,16 -1 0.03
87.76 0.57
A
More Experimental Results
A.1 Loss Curves
Figure and Figure show the training loss curves of ResNet20 model.
A.2 Tuning 3 for Naive ASGDm
Following the suggestion in 23 9,, we conduct experiments tune the momentum coefficient for naive ASGDm and present the results when training ResNet20 on CIFARIO in Table While tuning the momentum coefficient can enhance the performance of naive ASGDm, hyperparameter tuning is quite time-consuming and costly. In contrast, OrMo achieves better performance using the commonly used momentum value of 0.9, without requiring extensive tuning.
A.3 Ablation Study
An ablation study also conducted to justify the parameter update rule in line 13 of Algorithm 2 We replace the update rule in line 13 of Algorithm 2 with vanilla SGD step, W++1 = W (kk.))) and name it OrMo (vanilla SGD step). The comparison between the experimental results of OrMo and OrMo (vanilla SGD step) are presented in Table 4 and Figure 8
15

---

Table 4: Empirical results of OrMo and OrMo (vanilla SGD step) when training ResNet20 CIFARIO dataset.
Number of Workers
16 (hom.)
64 (hom..)
(Pet.)
64 (Pet.)
Methods
Trnining Accunsey
Training Loss
Test Acceincy
Training
Accunccy
Training Loss
Test Accunccy
stop)
Octdo
0.04
0.01
90.95
0.27
0.15
0.02
$8.03
0.28
0.04
0.00
91.01
0.10
0.03
87.76 0.57
1ech 8
Orfe
Onlo
K 16 (hom.)
(b) 64 (hom.)
(c) K 16 (het.)
(d) K 64 (het.)
Figure 8: Test accuracy curves when training ResNet20 model CIFARIO dataset with different
numbers of worker number.
Table 5: Test accuracy of different methods when training ResNet18 CIFAR10 dataset.
homogeneous
heterogeneous
ASGD naive ASGDm
91.45
91.52
93,74
93.10
shifted momentum
94.02
94.20
SMEGA
93.72
93.36
OrMo
94.32
94.26
OrMo-DA
94.50
94.03
naw ASSOV
Orti
Sprehs
(a) homogeneous
(b) heterogeneous
Figure 9: Test accuracy curves when training ResNet18 model on CIFAR10 dataset.
A.4 Experimental Results on ResNet18 Model
Table 5 and Figure 9 show the performance of different methods when training the ResNet18 model on the CIFAR1O 10 dataset. The number of workers is set to In the homogeneous setting, each worker has similar computing capabilities. In the heterogeneous setting, worker is designated as the slow worker, whose average computation time is 10 times longer than that of the others.
B Algorithm Details
Algorithm B and Algorithm 4 show the details of SSGDm and naive ASGDm.
16

---

Algorithm 3 SSGDm
1: Server:
2: Input: number of workers K, number of iterations T, learning rate 7). momentum coefficient
B E 1);
Initialization: initial parameter Wo, momentum ug 0, waiting set 0;
4: Send the initial parameter wo to all workers;
5: for to T
do 6: if the waiting set C is empty then
7: W Wt Su, 4 = Su;;
8: else
9:
W We 1c+ = u4:
10: end if
11: Receive a stochastic gradient & (1)) from some worker ky;
12: Update the parameter W = W [Bitt(k;,
13: Update the momentum U6+1 = 4 + (k)
h
14: Add the worker k to the waiting set C = C U (kr);
15:
Execute the synchronous communication scheduler: only when all the workers are in the waiting set, i.e., C = [K], send the parameter Wi+1 to the workers in C' and set C' to 0;
16: end for
17:
Notify all workers stop:
18:
Worker :: (A E [K])
19:
repeat
20:
Wait until receiving the parameter w from the server;
21:
Randomly sample 5 'D and then compute the stochastic gradient g* Vi(w; gh);
22:
Send the stochastic gradient g* the server;
23:
until receive server's notification to stop
Algorithm naive ASGDm
Server:
2: Input: number of workers K, number of iterations T, learning rate momentum coefficient
[ E 1):
3: Initialization: initial parameter wo, momentum 0, waiting set C 0;
4: Send the initial parameter Wo to all workers;
5: for = 0 to T do
& 6: Receive a stochastic gradient (ste(k,.)) from some worker ky;
7: Update the momentum u,+1 = Su, + (kk.)
8: Update the parameter W = W, - u,11
9:
Add the worker k; to the waiting set C = CU (k+):
10: Execute the asynchronous communication scheduler: once the waiting set not empty, i.e.,
C. o immediately send the parameter W,+1 the worker in and set C. to ();
11: end for
Notify all workers stop:
13: Worker k: (k E [K])
repeat
15: Wait until receiving the parameter w from the server:
Randomly sample 5* ~ D and then compute the stochastic gradient g* V.(ww: Ek);
Send the stochastic gradient g the server;
18: until receive server's notification to stop
17

---

C Proof Details
C.1 Reformulation of SSGDm
C.1.1 Proof of Proposition]] 1
Proof. It's easy to verify that (ke, " K [K] ( where K
Base case: for s= 0, Wo wo and uo = uo-
Inductive hypothesis: for some arbitrary integer s' 0, assume that w. Work, ügs = U.K.
Inductive step:
ú 9ü. +
7 K
V((w>(:")= = =BUKK +1
Σ
KE[K]
kE|K]
W''+1 W. Bü,'
Vf(Wsr:E") = -WoKK W.K
Bu,K n Σ vf(wekiE
kE[K]
kE|K]
W(s++1)K
We conclude that w. wak and ü, usK for any [S].
C.2
OrMo
C.2.1 Proof of Lemma
Lemma [ can be viewed as a special case of Lemma 5 and its proof is completed by substituting each delay-adaptive learning rate T,, in the proof of Lemma 5 with ry for all k E [K] and t E [T].
C.2.2 Proof of Lemmal
Lemma 2 can be viewed as special case of Lemma 6 and its proof is completed by substituting each adaative learning rate fik., in the proof of Lemma with ry for all E [K] and E [T].
C.2.3 Proof of Lemma 3
Lemma can be viewed as a special case of Lemma] 7 and its proof is completed by substituting each delay-adaptive learning rate Íik. in the proof of Lemma 7 with n for all k [K] and (T].
Lemma 4. With Assumption the gap between ÿ, and w, can be bounded:
K²2
Bliy 2 <
(1 3) V 11
(12)
Proof. For any 2 ú, can be formulated as follows:
min{fK,l-1}
ú, = 2
Σ
KK
Σ
K3-1
ngo
+
ng
kE[K]
k=
182
11.. w
| ||
(1 -9
CiK
B2
B1
11K 2
R
Σ n
K
3 -
Σ
ng,
15-1
(1- (1-9)2
KE[K]
/=(s-1)K+1
18

---

Let qt = =KkE[K] 31 $
+ ==1
R
minn(sK
(s-1)) 3 x-2
then we have
min min(sKa-1]
182
11 wrll?
B x
Σ n
Σ
11
(1 -333
[E[K]
1)++
2
88
BL O
min(sK.l-1)
gL
J-s
780 k
+
R
7
9-1
(1 -1-88 3)2
91
98
KE|K]
==1
1|++
LiK
minfsk.t
8ºq
Σ
LL Q
|188|1
Σ
B LIK 2 --8
k3 -1
2
$ (1 132
K
78
KE[K]
(=(1-1)K+
[+ min (sk,t-1}
33
Blis: w. S (1 B3)
Σ
1
178 1
12 +
Σ
B
1+
|
118)
111
[E[K]
(+-1))
G
min(
B 2
Σ
3 -1
(1 -)2
KE|K]
(=
G2 1 (1 5)3
K2222222
(1 (1)
C.2.4 Proof of Theorem 1
Proof.
" EF ($++)s (8.)
1- 3 11
(VF())). (Fgg
k--)
2(1
Lr
3)2
TF
B:
lr 4--1 112
LTya
S F(G))
(VF())), VF(w.)) +
E lg
[F((W))?
B
2(1 3)²
Lxp
+ 2(1 - B)2 VF((:))12
VF(W.)) + L77202
Ln²
S F({:)) 1 3
/ /F(w.)l?
2(1 - 3y²
2(1 - B)2
-(VF())), VV())) (VF())) V.(..) + VF(W:)) VF(w.))
(VF()) VF(W.). VF - (VFF(
1
/VF())) - VF(W.)) 11 +
2
118r w.1l - IVF
1
x 2
w 2 + 2E W. w 2 K2G²
2Tp²
21
Eliy, 11 < 2
(1 -1-
(1-3)2
(1 3)
1 E EV.)())).. VF(w.) + LIf
Ln²
EF()++1 EF(())
+
E V ||
2(1 - B)
2(1 B)
< BF)))) + 2(1 B)
22
Ely. w +
w/1l2
La7
2(1 "
E VV((,))' || +
Lii²0²
2(1 B)²
3)
2(1 - By²
ms L
EF($.) +
2(1 LL
Eliy - w.ll2
4(1 1
E (VVF(W,)122
Liiz02
B)
3)
2(1 - -3)
2n
+ G2226222
< <EF())) 4(1 3)
E VFF() + 2(1-91
9153)3
19

---

Summing up the above equation from = 1 to t T, we can get that
- 4(1 () [}F())) F
2Ln
4r2
E VIFF (VFW(:
Tv
1
(1-B) 83
Since y1 Wo
I-3 1-3(w) Wi ww) = - EnE[K] gyi we have
EF())) S F(wo)
I-B -B-BB(V((WD) Σ
"1 EV(FF(wo)
go)
+
Laj²
E
2(1 - 8)2
kE(K)
RE(K]
K1 /VF(w))]| + 2(1 332
Lup
S =((w)
E
Σ
80
1-3
KE[A]]
K1 [VF(ww)]] $ F(wo) 1- 3
Lup
+
E
Σ go KVF((w) + KVF(W)) (W))
2(1 - 8)2 3/1-
kE[K]
F(wo) + LK211
Kn
KL
|VF((w))]
2(1 - -832
1-3
2(1 - B3)
1T02122
S F(wo) + 2(1 6)2
The last inequality above holds because 7) S Combining the above equations, we can get that
1-8
2KL
E [[FF(w:)]l < 4(1 (3) (3) (F(wo) - F.]
2n1
2TKoo
+
+
TT
1-3 3
(1- ByT
(1-B)- B)
T2K 4(1 B) [F(wo) F+]
ALmO²
L2
Tn
1-B
(1-B)-
Let min 1-8 (L (1-0)3 (1-0)3 ((wo)) },
then we can get that
2KL.
(LT)20
(IKG)3T
Loa
KLG
KL
E F[V
+
+
T
T
T
C.3
OrMo with Delay-Adaptive Learning Rate
C.3.1
Algorithm
The details of OrMo with delay-adaptive learning rate (OrMo-DA) are presented in Algorithm 5
C.3.2
Notation
For positive integer n, [n] {0, 1, .n .n- 1}. [0] is defined 0.
The function ite(k, t) denotes the iteration index of the latest parameter sent to worker & before iteration t, which can be formulated as
J0
t = 0, k E [K], > 0, k,-1
ite(k,t)
ste(ktt-1)
t 1> 0, k + k=-1
where & [K], E [T 1].
20

---

Algorithm 5 OrMo-DA
1: Server:
2: Input: number of workers K, number of iterations T, momentum coefficient 8 E [0, 1):
3: Initialization: initial parameter Wo, momentum Up 0, index the latest gradient group
Io O, waiting C = 0:
4: Send the initial parameter wo and its iteration index 0 to all workers;
5: for to 7
do
6: if the waiting set C is empty and [ 1
I then
7:
W = Wt Su, 1 = Su, 4+1 I, 1;
8: else
9:
W We Mct = Uc. 1+11 15
10:
end if
11:
Receive a stochastic gradient kt (,)e(k..a) and its iteration index ite(ks, t) from some worker ky & and then calculate rite(ks.))) (i.e., the index of the gradient group that gite(k..)) belongs to);
12: Update the momentum U,+1 = u + 841-1- ( x (nBBitttee.))):
13: Update the parameter W = W 8 1
x (I)
1-B
14:
Add the worker kę to the waiting set u }
15:
Execute the asynchronous communication scheduler: once the waiting set is not empty, i.e.,
C + 0, immediately send the parameter W and its iteration index + to the worker
and set C to 0;
16: end for
17:
Notify all workers stop:
18: Worker k: (A= E [K])
19: repeat
20:
Wait until receiving the parameter wy and its iteration index t' from the server;
21: Randomly sample g* DD and then compute the stochastic gradient g Vf(we;
22:
Send the stochastic gradient g and its iteration index e' the server;
23:
until receive server's notification to stop
Ne is the learning rate at iteration and satisfies that
S 2K,
V/r
1
min 17,
4LTe Te > 2K,
where [T).
The function next(k, 1) denotes the index of the next iteration that the gradient from worker will participate in the parameter update after iteration (including iteration (), which can be formulated as
min{j 2 t: K2 =k}
3j E
[
[ =,
next(k,1)
T
Vj
T [ ky #k.
where & E [K]. E [T'. It's easy to verify that ite(k, nezt (k: t)) ite(k, t), next(k, ite(k, t)) neat(k, , 1), where & E [K], [T].
We define fx.t = t itc t), where k E [K] and E [T + εr denotes the current delay of the gradient Site(k.e) at iteration t. which is the number of iterations that have happened since ite t).
It's ss easy to verify that fr,, = ite(ks, Tt. where t [T].
We also define an auxiliary sequence fe, for the adaptive learning rates. ńi,, denotes the learning rate corresponding the gradient k gite(k.))
"1
ne. $ 2K,
min (L
tk > 2K,
21

---

where E [K] and E [T]. Since next(kkt) t) = next(k, ite(k, t)), we can have that fe. (N..)) where & E [K] E [T]. If next(kk,)) t) [T', me,ttz(()..) FR g) (k. and then we have that
( { min((: AI(Tneat(kk))
Tnent(k,.) S 2K,
0k,t (R.0)(
Tneat(k.)) > 2K.
It's easy to verify that it (Meat(()s.)) n/. where E [T]. If next(k, t) = T,
("
*x S 2K,
m, min 4LFx,T
fr. 2K.
C.3.3 Convergence Analysis for OrMo-DA Firstly, we define one auxiliary sequence {ūrh. for the momentum: ú = EkE(Ky Me,0g8 and
[ũx + 188 he-1
K (t 1),
ú
(13)
iú + 11 Ke-1
K 1 - 1),
fort 2
Lemma 5. For any t 2 0, the gap between u,+1 and ú441 can be formulated as follows:
1- 5t0
Ú11 u111
(t. (itt((k)))
(14)
RE(K)),TA
Proof. Base case: for t = 0, új
EkE(K) mA.0g.
. then we have
g fm
U1
kE(K), Me
Σ
g 2 1
1e 0) (te (ice
kE (K Metkoo
Inductive hypothesis: for some arbitrary integer t' 0, assume that (14) is true for 1.
Inductive step: We will prove that (14) true for t'. Firstly, we divide our discussion into two cases based on whether t' is divisible by K and prove that
Σ
B 3 1 (all
it ( + May g. ke-
KE AE
B - 200lt)))
Ket ite p Bite(ky.
22

---

Case 1: K 1 (t' 1)
0p41 = Bür + Muv 1 By
u/+1 = Buy + 18(+(11111 - (
BI 1 x (
ue41 U/+1 = B(üu ue)) + The 1. 1 Byr
Mh ittelk 1n (aichee))
Σ
x
nech
e'
x
Ky--1 - -3( 1 1-1
+ M
May Hte Bitee(kyr.))
Σ
1 p
=
ito Bite(k.M-1)
1-
+ fay
Mi (ke (ke,
The second equation above holds because 1 ate "Teer((y. = 1/2- The last equation above holds because [x] = 11'-11
> K = Iv when K (t' - 1),
11), Iu+1 = =
R and
Case 2: K t (1' 11)
KV-1
úp-1 = ür + Mik - By
Up-1 = up + 3 1 staleyaees
be
May stel ,1 (i
u141 4p-1 (ūr uv)
fik
Bir
AV-1 g f (
ker ni 1n Bitelher
Σ
3
Mi.ite(ks. (ite(k))r
KE &E
ky ky--1 - 13 1 pellegeees Mir Butethe
+ flk
1.u ge
Σ
B B -1 sea _
11 sealty
+ ijy 1 ge
nhe Stelk Biteike.yy
The last equation above holds because 11=1"==
Since ile(k,t') = ite(ki 1' - 1), Vk: & ky- we can get the following equation for both cases above:
BT seak ne itokk, (ite(k.r)) + Ma 1. g
" by
ur+1 uW+1 =
KE k
3 # (
nh See 1¹) Bitekh..ey
If hi 11 then we have ike 1') 1' and
ür+1 u1+1
Σ
8 - 2t
mi ita (' Bheeheee
kE(A
23

---

If ky * -1, then we have
E
3 - 1
(k Bitel(ass) + o R
u U1+1
31 1 (allyy
ilke see (Be 11 (ite
E
B1 k 1 aete
Σ
8- ( ()
ke[K], harthrr-nn ketke
+ 31 k
Rep
fik tte
B # sealk.t
=
ite ("itoot))
We can conclude that u,+1 U4+11 = _kE(K], - te(k.e))
m ( true for any
t O.
Then, we define one auxiliary sequence (Wele21 for the parameter: W1 Wo -Kke(Kc) ne.ug and
W: Bū, n
R:
K (t - -1),
Wr41
Wr îik 1866
he-1
K K (t 1),
for 2 1.
Lemma 6. For any t 2 0, the gap between W and W2+1 can be formulated as follows:
31 1
1e 111
W411 W
Σ
Nh Ste (k))
(15)
3
kE[K]AATKk
Proof. Base case: for -= 0, wi = Wo
EkE[Ko in..g..
Wo 00k ko then we have
3-
3
steck.0)
W
W
it. (k
B
ke(K))
Inductive hypothesis: for some arbitrary integer /' 0, assume that 15 is true for 1. 1' 1.
Inductive step: We will prove that (15) is true for t'. Firstly, we divide our discussion into two cases based on whether t' 1 is divisible by K and prove that
B 4 tt
Σ
N stek, ( fi BB! Re
We41 Wr+1=
3
- B1 1
1- -tollgrre
1+1
kir My Ste Bite(he.)))
1-8
24

---

Case 1: K 1 (t' -)
We'+1 We Bûn Mh.,-11 1 8p
11--1
We41 We Eu - B1 #/ 1-1 seecky 29
1+1
He 1) ke
by
Wx+1 We+1 We 3 (úr 11!))
1 M -
By
1 - 3 x -1 , :4) '1+1
jteekk Steeky
1-
1 1 3I x 1 1
n it, 1)) (())(k)
E kE(K (.
3 3 stalk
1 3l%
seacey 1+1
(te (i)
1 B
1 1-B1 31 1-ppcch piclled 17 11+2
Σ
kE[K],
- 31 1-1 ( 1+1
by
Ker ne Stelk B
-
1-2 B
1 1 1-11% -- p 11
Σ
1- 3
kE|K],
- 33 1- stollyre 1+1
Ke' Me itelky 1 Baeeke.
Be
1 - 3
The last equation above holds because [ = [ + 1.
Case 2: f (t' 1)
Wrr+1 W.r f g::
Wx+1 Wr 1 31%
ke Map (kg N') 17
1-
1 - tt 14
Wy41 Wr+1 we Wr 1. Re-- 1 -
ita ( Betelkyr.
1- 3
33l - 1
3
1 - Blkk 1e - pual
1+1
Mi, 21) tet (8)
Mky- # Be
1 B
1 31 1-1 1calks
Σ
1 3
KE|K]AAKK/
1 - 8 1 piclly e
by
- Bg
1
25

---

The last equation above holds because 1 [
Since ite(k,t)) = ite(k: 1' - 1), Vk of 11, we can get the following equation for both cases above:
B1 ie
Me (Bte(kk))) - - By 8
We'1 We+1
3
ke Aeptlt
B k (
1+1
Ste (itekke,
3
If ky = -1, then we have (ker, (') = l' and
1- 31 1 senck
1+1
Σ
We++ We+1
1 B
kE
If kir + -1, then we have
BI
1-1
sea K
141
Wy41 We+1
Σ
(k, Bite(kar) - May 1. ge
3
kE|K]
31 --1 sealker.e") 1+1
Mik (k 1y (ita(kyr.))
1-
1 1 3 2
1+1
Σ
Ma e Site(kee)) nue 1 ge Ry-1
1 B
1 1-
31 1 stekkee
1+1
Σ
1-3
REAKTAAKK
1-81 11 100 1+1
We conclude that w W++1 for any & 0.
EkELKTAAK
nR italk (ite(kk.)) is true
1-8
Then, we define another auxiliary sequence (y:heı1: = Wh I-3 ENE[K] nn,08 and
9t+1 = ÿÿ. 1 Th, g.
for 2 1.
Lemma 7, For any 2 1, the gup between yr. and w, can be formulated as follows:
3
y: We
0
(16)
1 1 B
Proof.
Base case: For = 1, we have that
W1
Wo
1
Σ
nk.
Wo
Σ m..ogh
1
B
RE
K]
kE|K]
8
ú1
KE[K]
Inductive hypothesis: for some arbitrary integer t' 2 assume that ÿ. we
ú, is true for
1-3
t= t'.
Inductive step: We will prove that y: w. I- ú, is true for = 1. We divide our discussion into two cases based on whether E' - is divisible by K.
26

---

Case 1: K 1 (t' 1) 1)
h1--1
8r41 = Sy 1 mh 1 Ee
Ry
We+1 Wy -Bii n 1. Bi
8c' 1
Wey - Būdr - me 1. 1.. (1-1
8e+1 Wr+1
1.t By:
3
B
1. 1e-1
Yv We Büp
The
B
8
B
by
B ür
Be
Case 2: K 1 (t' 1)
ky-1
8/41 8r'
1- B
8e
kr-11
Wr+1 We fi,,- ge
1
kv
1 1. k1-11
Fe+1 Wy41
8r'
1 - B
1. Bi
W. - ma
Ry
yr
We
mie 1 By
1
B
B ür
B
by
8
0p41
8
We conclude that y: We
8 ú, is true for any t 2 1.
1-9
Lemma 8. For any t 2 1, ûU can be formulated as follows:
min(s
û, 3. 1-
Σ KE(K]
3 レ
Σ
f
(=(s-))K+
Proof. It's straightforward to get this conclusion from the definition of the sequence ú,
Lemma 9. (descent lemma) With Assumptions 7 and 3
we have the
the following descent lemma for
1 12 1,;
(00-2..))007 2(1 - B)²
EF()+41) S F(y.)+ +
/VF(W:))1
2(1 ²)2
2(1 - 3)
L 12
L Li
l1br w
l wwll.
3
B
27

---

Proof.
Vi+1 = 8: 1- -3 1. 4-1
1
L E libt1 - 50el
EF()++) S F(()) + B(VF(())))).. (.). 51)
20d
=F())
1
E E(VF())), Mu 1.88( k-
L
E
(fn
h 2
I-
3
2(11 33
= F()))
1
(V.( (. +
L
F
(1it
)²
Be
As
-10)
1-
3
2(1 3)2
Mh--11 (VF())), VF(w))
dRe (VF())) - VF(w:) + VF(we)) VF(we))
1- - 3
1- B
(VF().) - VF(W.), VF((.)) 1 3
|VF((,)]]
1 B
M/--11
[|VF(})) - VF(W:))1
||FF(w:))l
2(1 (3)
2(1 33
P |VF((.))l
$
115r - woll?
2(1 - B)
2(1 - 3)
2(1 3)² g)²e
L
E
(fn, 1.t)²
)²
Bi
R 2
L ((
2
E B
h- - + VF(w:)]
2(1 (3)²
L L(ika_1,0)
-- + +IVF(w)))l²)
B
2(1 /3)²
1.)
(02 + +[]F(())))>
2(1 - 3)²
EF()411) S F(y)+ + ((ii)_111)) 2
|VF(W.))| + (1)=21,1)200' L
2(1 83
2(1 - 3)
2(1 2(1-3)²
L' 1st 11:r - will -wel?
+ 2(1 B)
L(ii)_11)²
Mike
|VF(W.))1 + (in__1,))0021
< F(Y))+ +
2(1 100-3) /3)² 2(1 - 3)
2(1- - 13)²
L Li ls
11 well + L2 1.f
| l/
8
3
Lemma 10. With Assumption 7 the gap between ÿ, and w. in OrMo-DA can be bounded as follows:
n39nnK2
E Mi 11:e -w.1²)
< (1 - (9)
Σ
(f. 2
[VF
+
Σ
KE[K]
t=1
23311K022
+ T-1
+ (1 (1-
Σ (fx.0)
(it))
[E(KK
28

---

Proof.
[=2
min
E 0o/l = E
B x
Σ KE(K]
+
Bl ا -
Σ
1k5-1188 8j
(=(-1))K+
S 2E
3 x
Σ kE[K]
in.o (BO - VF((w))
(nin(sK.t-1)
+
Σ
nR -g)----F((W)))
j=(+-1)K+1
/iinfs,,-11)
2E
3 k
Σ
nk. VF(wo)
+
B 1 1-8
Σ
m /k..i.FF(vy FF(w,)
[E(
1)K+1
Litk min ft
2 Σ
3el 1 2 2
(1ix.0) 2002)2222200 +
Σ
gel | 1-20 20 (ikk- )
kE[K]
j=(x-1)K+ 1)
1ー2
1in
2E
g L 21
Σ kE[K]
nR VF(wo)
+
Σ
B x 1-8
Σ
nky- FF(w,)
(=(e-1)K+1
Let qi EkE[K]
91 -+
min(s 3 j= (--1) 1)k+1
11=---1 |-s then we have
min(aK
E
gl x
Σ kE[K]
MROO VW(w))
+
Σ
- FF(w,)
1)K+1
13L (
|
min (-1
B 1 1-
E
n V VV((wW) F(wo)
+
Σ
Σ
nk VF(w,)
qe
qt
KE[K]
j=(s-1)K++1
( 2 |VF(w))]
< 4t
KE(K]
minfsK (tinss
31 [4k-2]- 1 (- (
1=(+-1)K+1
K
3 LIK
( /F((w))] 2
1 3
K)
11K
min Σ
Σ
Bl
LiK 3 -8 ( /BI
K
1=(1-1)K++
29

---

Thus, we get that
E Gill
|
min(aK,t-1)
S 2E
g 11
Σ kE|K]
nN. (F(w))
+
11182
Σ
1 VF(w,)
(=(s-1)K+1
[EL
min(sK,t-1) 13
2 Σ
B2 1- (ok.0))22++ +2 Σ
Σ
3aL K -2 22 (1ng-11)) 302
kE|K]
j=(s-I)K++
minfsK,t-11
2K
gL [+K-2 1 (11k,0) (w)ll))ll 1|
+
Σ
BL BL**x x j-o (1k)-13) 'B VF(w,)))))) (w,))l )1(
1 1 B
KE(K]
(s-1))+1
min(aK,t-1)
2 Σ
32. 2 (f),0080²+2 +2
Σ
Σ
82l 1 - 1
(f1cz-1.) 2 802
kE[K]
s=1
j=(s-1)K++
T-1
8n T-1
Σ E
ff 115t - -wll") S (1 - (1-3) 1=1
E | 2
1=1
2
B 2 (ik,0) 2 |VF(wo)) ?
(1- - B)
1=1 kE[
+ 1t
28
3 - 1-8 (ite, 15) ' [II))(
(1 838
k1
202n0²
BaL LIK
(fk.0) 2 + Σ Σ
32L L 2- (fiss 15)) )²
(1-8) 3)²
kE|K]
j=(o-1)k++
< 2,8 nk²
Σ (Ak.0) (VF [EEK]
Σ
(i))
/B/ (VFF(w:))) 2
(1- -)
282nK0²
T-1
+
Σ (fn.0)²
2
+
(1)
(1 (1-3)3
[KE[K]
1=1
Lemma 11. With Assumption ? bounded as follows:
letting 17 S
1 the gap between w, and w, in OrMo-DA can be SKI.
T
E Mi I/ -wal²)
S
nk
E
/F(w:)] +
Σ inoo kE[A]
lVL((o))?
2T(11
3)²
1102
Σ M + Σ nr.o
2L(1 B)²
kE[K]
30

---

Proof.
T
T-1
E
(ik 1e Il: - woll²)
S 11
E ll: w
t=1
T-1
3 x
(
E
1 1 B
kE[K],,rz
21
T-1 Σ
E
Σ
31
R
iteik
A
++
(k.tto(k.t-) (ite(kes-1)
V VF(Wite(k.)-1))
1
1=1
T-1 Σ
B x 1-1
1150 11
1+1
+ 21
E
VF
1-8
1=1
kE[KK],
T-2
21
Σ
(Al.ateck.))) (o² (op KE (F(
(1-3)
t=0 ke
T-2T-2
21
(fr.tock.))) 2 KE (F 1 (k + ky) 1 (j it)(k,t))
(1- 91)
1=0 T=
KE[K]
T-2T-2
21
Σ
Σ
(iu.)ee(..))) 2 (0² KT (FF+
(j i))
31-
j=1
1=0
KE[K]
2m
T-2
Σ (fin.tt(k.))) (finate(h)))((²2))))))))))))))) KE / 1 (A: + kb) 1 (0 = ite(
(1 3)
t=0 KE[R]
20
T-2
2 (0² (o*+KBB (in)-115)
(d++KI]VE(ss))' (next(kk)11.))- -
(1 - 18) j=1
21)
Σ
(fkk.0) (o² K
( KV
(nert(k, 0) (neett())
-0)
(1 - B)²
kE[K]
T
E ( l/,, woll²) s
21
( ( *K*KEIIVE (VF+WI)V)( Am imeetthe
(1 B)²
27
(in.00) (o2 + K [VF Fk.,eaa((k.))
+
(1 -3)
kE[K]
T
M I ww - -
"
1it [02 + KI (VF(:))
+ Σ
neo
[02 + K V (wo) (wo))ll )|
2L(1- -B)²
kE[K]
nnK
E VF(w:))2
Σ Í
IVF((W)))
2L(1 - -3)²
kELKy
no²
n Σ nxo
21 -))
kE(K))
31

---

Theorem 3. With Assumptions 7 and letting
S 2K,
U)
1
min
(77
Tt >> 2K;
4LTe
and 1j min
(1-8)² 8KL V
(1-8)a TLo*
Algorithmi
has the following convergence rate:
Lo² KL T
+
T
where A F(wo)- and Wr randomly chosen from (Wo: Wi... - according probability distribution which is related to the delay-adapric learning rates as shown in (17
Proof. According Lemma 9
get that
EF(ÿT) - i5(
L L(ik)-1.1)
Lo
B B//VF(W:)1?
(fx, 12t)
2(1 - 3)
2(1 - 8)
2(1 - 3)²
L2
+ EE
(iu l| - will -w.l= + m
115: vir13)
T-1
Lo²
T-1
E V/
+
2(1 B)²
2(1 - 3)
2(1 - 3)
1=1
n2O0
+
1 + Σ
nk.0
2(1 - -3)3
kE(K]
+
nKL
Σ T E /V(())11 +
Σ
nk:0
|VEF(o)]l
2(1-3)) 3)3
KE(K
23 + (1-3))
T-1
Σ AE(A]
(m [VFF(w))]
+
Σ
(ii ..1) "1) (EI[(((.))))
23 2,3n2
Σ (M)
(it)).)))
+
(1 (1-
KE|K]
Lo
5
E (IVF(w:)ll'
(i, )
2(1 (8)
2(1 3)
2(1 8)
3/82 Loz
+
Σ ijku a.t
Σ in.
2(1 B)
4(1 3)
kE[A]
1KL 2(1
Mr |VF(W))) + Σ ne [F((o))
3)3 3)
KE[K]
BNKL 4(1 - 18)3
Σ nK. [VF(w)))1 [E[KK]
m n. E [VF(ws)))
32

---

[iik 1.1) )²
Tike 1tt
V )1
+
Lo²
T T-1
(fk 1e)
2(1- B32
2(1 - 8)
2(1 3)
nit + Σ in.o
+ (1 - -1)
kE[K]
IKT.
+ (1 (1-13) 3)²
The BII
Σ nkoo [VF
kE|K]
[(ikk-
Tik
VF (w:)) (w:))l
+
Lo²
T T-1
(fn 19)
2(1 3)²
2(1 - ()
2(1 33)
1=1
7o
T-1
ijk + Σ inko
+
(1 - 333
kE[K]
+ 1
VFF(
Σ
nE [[WF()))))
4(1-3)
KE[K]
EF(S1) S F(wo)- 1 B(VF(wo))
Σ og.
)
L
E
Σ
000
2(1 3)
KE[K]
KE[K]
EKETRT MN:O
= F(wo)
T.
+ 2(1 - 3)2 E
Σ n (g) kE|K]
VF(wo) + VF(wo))
L [Eke(KK] 11.00
EkE(K) fR:.
Lo²
< F(ww))
IVVF(wo)] +
Σ (fR.0)
2(1 21)
B
2(1 - 23)
kE[K]
EF(ST) F(wo)
L ((ii
Lo²
T-1
E [V])F()))l
+
2(1 -88²
2(1 3)
2(1 -3)
nLo²
M + Σ Āk.o0
(1 - 3)3
RE(KK
1
AN JE [IV ||
Σ n. [VF(w))]
4(1 3)
kE[K]
L Σ [REKK] )M.0)
ELEKK] nN.0
Lo²
IVF(wo)]1
(in.n)²
2(1 - -3)²
B
2(1 - -32 kE[R]
Liis, 1.a)²
ÚA, 1st
IE [VF())))
+ 2nLo²
Σ M
Σ fik
+
2(1 - -3)2 4(1 3)
(1 3))
RE K]
L Eket EKe[K]] mm..))
EnE(K] 1N.O
|VF(wo)]?
2(1 - -19)
4 (11 3)
33

---

EF(ST) F(wa) S 1
Tikt I. [.
Σ
nnk /1 [/))()) |
8(1 - (3)
kE[K]
+ 27
m + Σ Úu
(1 (1-3)) 3)
kE[K]
Thus, we can get that
8 - 3) (F(wu) - F*)
+ 16n
E
Σ
The (VF((w))l?
S
21=0 A
1=
Σl=0 f7c
(1 (1-8) B)
where 1/0- EkE[K] Ak.o and 17. fi 1t)
Then, we analyse the lower bound of Et=0 ne.
It's easy to verify that
F =t+1- ite(k, - [1 [1- ile(k:
[1-ile(k, 1) + = FRtt + 1 k # ke:
10 fk,t - Tt
k ke.
Since ExE[K] FR.0 O, have ExE(K] Ru, + Ex- To -KK- 1)T. Moreover, Toe 1.7
T TT-ite(NT-,,3) T) = O. We get that ExE(K]AKA नu. + EtT Te = =(K- -1)T. Thus, at least I
delays are smaller than 2K. Et The Etn Mis 1,t Eke(K) 100.0 2 I'm
16(1 - 3] (F(wo) (owo)-Fr F²) 16n Tn
E [V]())]
(1 3)
If we choose an output wT from (wo, W1, WT-1} according to P(WT- = W.) x Tr.
(17)
where E (T] and let 1 = min (1-a)² 2)2
(P FT) TLo
}. we have that
SKL
VV Wy 1 00 (1/42=+ KL
E
T
34

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope. We propose OrMo for ASGD in Subsection 3.2 We
prove the convergence of OrMo theoretically Subsection 3.3 and verify its superiority empirically in Section 4
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of the assumptions of OrMo in Subsection 3.3
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
35

---

Answer: [Yes]
Justification: The full set of assumptions and the proof sketch can found Section 3.3 Please refer to Appendix for the complete proof details.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: This paper fully discloses all the information needed to reproduce the main experimental results. The implementation details can be found in Section 4
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
36

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes)
Justification:
We provide the code. The dataset is public.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "cippscc/puullc//guu /utee//ggudddeeeedSuuuubmiibii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The implementation details can be found in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
Each experiment is repeated times as reported in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
37

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
The type of compute workers and the time of execution are presented in Section 4
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httt:::://eurrpsccc/pbbbb/
Answer: [Yes]
Justification: Our research conforms with the NeurlPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
38

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We have cited the original papers.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
39

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
40


Reviews:
[{"review_id": "zMUKZeIY83", "reviewer": "Reviewer_NjVh", "summary": "This paper introduces OrMo, a novel method to weight stale gradients received on the server in asynchronous SGD with momentum. The algorithm is based on the idea of organizing the sequence of gradients received on the server into \"buckets\" to approximate standard minibatch SGD with momentum. The method is shown to converge under arbitrary (possibly unbounded) delays, with experiments on CIFAR-10 and CIFAR-100 validating the strength of OrMo compared to some baseline.", "questions": "* In Theorem 1, the quantities $L,G$ do not appear in the convergence rate (contrary to what is displayed in Theorem 2 of [[Mishchenko et al., 2022]](https://arxiv.org/pdf/2206.07638 ) ). Is it normal?\n* Fig.5: As the Parameter Server is known to become a bottleneck for communications at scale, how does OrMo fair compared to synchronous SGDm at larger scale than $K=16$? (for instance, $K=64$)", "limitations": ".", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* **Convergence without bounded delay assumption:** Convergence is proved without relying on the bounded delay assumption, extending recent analysis of ASGD [[Mishchenko et al., 2022]](https://arxiv.org/pdf/2206.07638 ), [[Koloskova et al., 2022]](https://arxiv.org/pdf/2206.08307 ) to ASGD with momentum.\n* **Clear explanation of the \"momentum as a sum of weighted buckets\" idea:** Time is spent to clearly lay down the ideas of \"buckets\" and re-writing the momentum updates so that OrMo comes naturally, which is helped by Fig.1 \\& 2.\n* **Promising experimental results:** Compared to naive implementation (e.g., plain ASGD with momentum) and some chosen baselines, OrMo is shown to perform better in practice, especially in cases where the workers speed is heterogeneous.", "weaknesses": "* **Lack of discussion between OrMo and its approximation of standard synchronous SGD with momentum:** While the idea of OrMo may seem natural when we visualize standard momentum as a \"sum of weighted buckets of gradients\", the update performed by OrMo simply *approximate* synchronous momentum. Indeed, as the parameters hosted on the server are updated at each stochastic gradient in the asynchronous setting, the *points* $w_t$ on which the gradients are computed all differ even inside a given \"bucket\", which is not the case for synchronous SGDm. Yet, this is not discussed.\n* **Standard baselines are lacking in the experiments:** In Table 1\\&2, and in Fig. 3\\& 4, a comparison *(for reference only)* to synchronous SGDm could be interesting to have (to see whether or not there is still a gap to fill with synchronous methods in terms of \"performance per iteration\"). Moreover, it seems that the baselines \"tuning the momentum value\" for asynchronous SGD with momentum described in [[Zhang and Mitliagkas, 2018]]( https://arxiv.org/pdf/1706.03471 ) and [[Mitliagkas et al., 2016]]( https://arxiv.org/pdf/1605.09774 ) are lacking. Finally, we can see OrMo as a method to penalize stale gradients received by the server, using some sort of \"exponential weight\". Empirically, there have been other \"penalty functions\" that have been tried in Asynchronous Federated Learning, such as the ones described Part 5.2 of [[Xie et al., 2020]]( https://www.opt-ml.org/papers/2020/paper_28.pdf ). Have you compared OrMo to them?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the constructive comments and the support of our work. Below, we respond to the raised concerns and questions point by point.\n\n**Response to Weakness 1:** \n\nAs you pointed out, the gradients in SSGDm and OrMo are computed at different points due to the asynchronous nature of OrMo. In SSGDm, the set of the computed gradients can be expressed as $\\\\{{\\bf g}\\_0^0, \\cdots, {\\bf g}\\_0^{K-1}, {\\bf g}\\_K^0, \\cdots, {\\bf g}\\_K^{K-1}, {\\bf g}\\_{2K}^0, \\cdots, {\\bf g}\\_{2K}^{K-1}, \\cdots\\\\}$. In contrast, the set of the computed gradients in OrMo can be formulated as $\\\\{{\\bf g}\\_0^1, \\cdots, {\\bf g}\\_0^{K-1}, {\\bf g}\\_1^{k\\_0}, {\\bf g}\\_2^{k\\_1}, {\\bf g}\\_3^{k\\_2}, \\cdots, {\\bf g}\\_K^{k\\_{K-1}},\\cdots\\\\}$. This difference between SSGDm and OrMo makes it challenging to directly measure how closely OrMo approximates SSGDm. To address this, in the theoretical analysis presented in Subsection 3.3, we define two auxiliary sequences, $\\hat{\\bf w}\\_t$ and $\\hat{\\bf u}\\_t$, for the parameter and the momentum, respectively. These sequences are updated in a manner similar to SSGDm but use the gradient set from OrMo instead of SSGDm's gradient set. *Lemma $1$ and Lemma $2$ rigorously formulate the differences between OrMo and the auxiliary sequences, providing a theoretical foundation for understanding the relationship between OrMo and SSGDm despite their differences in gradient computation.*\n\nThanks for your very insightful comment which makes us think more deeply about the relationship and difference between our OrMo and its approximation of standard synchronous SGD with momentum. We will clarify this approximation in the final version.\n\n\n**Response to Weakness 2:** \n\n**2.1: A comparison (for reference only) to synchronous SGDm could be interesting to have.**\n\nThe results are presented in the following table, and we will refine the figures in the final version. \n\n|CIFAR10            | K=16             | K=64  |\n| -- |--|--|\n|OrMo (hom.)        | 90.95\\% $\\pm$ 0.27\\% | 88.03\\% $\\pm$ 0.28\\% |\n|OrMo (het.)        | 91.01\\% $\\pm$ 0.10\\% | 87.76\\% $\\pm$ 0.57\\% |\n|SSGDm              | 90.85\\% $\\pm$ 0.26\\% | 88.96\\% $\\pm$ 0.18\\% |\n\n|CIFAR100            | K=16             | K=64  |\n| -|-|-|\n|OrMo (hom.)        | 67.56\\% $\\pm$ 0.34\\% | 65.48\\% $\\pm$ 0.17\\% |\n|OrMo (het.)        | 67.71\\% $\\pm$ 0.33\\% | 65.43\\% $\\pm$ 0.35\\% |\n|SSGDm              | 67.86\\% $\\pm$ 0.32\\% | 66.43\\% $\\pm$ 0.50\\% |\n\n**2.2:  Moreover, it seems that the baselines \"tuning the momentum value\" for asynchronous SGD with momentum are lacking.**\n\nThanks for your insightful advice. Following the suggestion in [A], we conducted experiments to tune the momentum value $\\beta$ for naive ASGDm and present the results on CIFAR10 here. While tuning the momentum value can enhance the performance of naive ASGDm, hyperparameter tuning is quite time-consuming and costly. In contrast, our method achieves better performance using the commonly used momentum value of 0.9, without requiring extensive tuning. We will include the momentum value tuning experiments in the final version.\n|Algorithm ($\\beta$)           | K=16 (hom.)        | K=64 (hom.)        | K=16 (het.)        | K=64  (het.)       |\n| -|-|-|-|-|\n|naive ASGDm (0.1)             | 89.85\\% $\\pm$ 0.24\\% | 83.93\\% $\\pm$ 0.25\\% | 89.95\\% $\\pm$ 0.19\\% | 83.76\\% $\\pm$ 0.34\\% |\n|naive ASGDm (0.3)             | 89.91\\% $\\pm$ 0.20\\% | 84.23\\% $\\pm$ 0.49\\% | 90.26\\% $\\pm$ 0.05\\% | 84.43\\% $\\pm$ 0.22\\% |\n|naive ASGDm (0.6)             | 90.39\\% $\\pm$ 0.24\\% | 83.87\\% $\\pm$ 0.28\\% | 90.56\\% $\\pm$ 0.13\\% | 84.07\\% $\\pm$ 0.38\\% |\n|naive ASGDm (0.9)             | 88.15\\% $\\pm$ 1.70\\% | 82.39\\% $\\pm$ 1.79\\% | 73.23\\% $\\pm$ 31.61\\%| 68.75\\% $\\pm$ 29.51\\%|\n|OrMo (0.9)                    | **90.95\\% $\\pm$ 0.27\\%** | **88.03\\% $\\pm$ 0.28\\%** | **91.01\\% $\\pm$ 0.10\\%** | **87.76\\% $\\pm$ 0.57\\%** |\n\n**2.3: Finally, we can see OrMo as a method to penalize stale gradients $ \\cdots $**\n\nThe update rule in OrMo is motivated by that in SSGDm. The key insight of the update rule of the momentum and parameter in OrMo lies in tracking the sequences $\\hat{\\bf w}\\_t$ and $\\hat{\\bf u}\\_t$ defined in Subsection 3.3, which are updated in a manner similar to SSGDm. Hence, OrMo cannot be simply regarded as a method to penalize stale gradients received by the server. Due to limited space here, please refer to paragraphs 2-5 in our Author Rebuttal for the details.\n\n**Response to Question 1:** \n\nFor simplicity, we omit some quantities (e.g., $L$ and $G$) in Theorem $1$ due to the $\\mathcal{O}(\\cdot)$ notation. When considering $L$ and $G$ and setting $\\eta = \\min \\\\{\\frac{1}{2KL}, \\frac{1}{\\sigma \\sqrt{TL}}, \\frac{1}{{(KLG)}^{\\frac{2}{3}} T^{\\frac{1}{3}}}\\\\}$, the convergence rate in Theorem 1 can be expressed as:\n  $$\\frac{1}{T}\\sum\\_{t=1}^T \\mathbb{E} \\\\|\\nabla F({\\bf{w}}\\_t) \\\\| ^2 \\leq \\mathcal{O} (\\sqrt{\\frac{L\\sigma^2}{T}}+ (\\frac{KLG}{T})^{\\frac{2}{3}} + \\frac{KL}{T}).$$ \nWe will refine the presentation of Theorem $1$ using this convergence rate. Thanks a lot for pointing out this.\n\n**Response to Question 2:** \n\nBoth OrMo and SSGDm are implemented based on the Parameter Server framework. The implementation details of OrMo are outlined in Algorithm 2. For SSGDm, the only modification is to replace the asynchronous communication scheduler in line $15$ of Algorithm 2 with a synchronous communication scheduler (i.e., only when $\\mathcal{C}=[K]$, the server sends the parameter ${\\bf w}\\_{t+1}$ and its iteration index $t+1$ to all workers in $\\mathcal{C}$ and sets $\\mathcal{C} = \\emptyset$), as described in Remark 4.  This ensures a fair comparison between OrMo and SSGDm.\n\nWe sincerely thank the reviewers for their valuable time and support of our work. Meanwhile, we would greatly appreciate it if the reviewer could re-evaluate our work in light of our response.\n\n[A] Mitliagkas et al., Asynchrony begets Momentum, with an Application to Deep Learning. arXiv:1605.09774v2, 2016.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ia5P6gMuJ2", "reviewer": "Reviewer_M3Nx", "summary": "The paper introduces Ordered Momentum (OrMo), a novel method enhancing the performance of ASGD by systematically incorporating momentum based on the iteration indexes of gradients. The authors provide theoretical proofs demonstrating the convergence of OrMo for non-convex problems, marking an advancement as this is purportedly the first such convergence analysis for ASGD with momentum that does not rely on the bounded delay assumption. Empirical results further validate that OrMo outperforms standard ASGD and other asynchronous variants with momentum in terms of convergence rates.", "questions": "1. What is the impact of the size of the waiting set $\\mathcal{C}$? How to choose the size of $\\mathcal{C}$?\n2. What are the key insights that the convergence can be guaranteed without bounded delay?\n3. What is the complexity and cost in terms of the ordering of gradients?", "limitations": "The authors have partially addressed the limitations.", "rating": 3, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. The proposed OrMo algorithm addresses the common problem of momentum integration in asynchronous settings, which is often associated with convergence issues.\n2. The paper provides a convergence analysis of OrMo in non-convex settings without the need for a bounded delay assumption.", "weaknesses": "1. The writing and presentation of the paper seems to require substantial improvement. Especially for Section 3, it is hard to fully follow the algorithmic and theoretical details, making it laborious to check the correctness.\n2. The paper considers only scenarios with homogeneous data distributions, where the workers access to a shared dataset $\\mathcal{D}$.\n3. Assumption 1 includes a bounded gradient assumption, which is rather demanding.\n4. The experiment setup does not quite match the theoretical analysis. In the experiment, the learning rate is multiplied by a factor after a specific number of epochs, while Theorem 1 is based on a constant learning rate. There also lacks discussion on how the multiplication factors and the intervals are tuned.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the constructive comments. Below, we respond to the raised concerns and questions point by point.\n\n**Response to Weakness 1:** \n\nIn Section 3, we first propose a new reformulation of SSGDm, which serves as the inspiration for designing OrMo for ASGD. We then present the details of OrMo for ASGD, including the algorithm and convergence analysis. Thanks for your valuable feedback. We will refine the writing and presentation of this section.\n\n**Response to Weakness 2:** \n\nThank you for the constructive comment. Our analysis can be easily extended to heterogeneous data distributions with modified assumptions:\n\nAssumption 1' : For $\\forall {\\bf w} \\in \\mathbb{R}^d, \\forall k \\in [K]$,\n$\\mathbb{E}\\_{\\xi^k}[\\nabla f({\\bf w}; \\xi^k)]=\\nabla F\\_k({\\bf w}),$ $\\mathbb{E}\\_{\\xi^k}\\|\\nabla f({\\bf w}; \\xi^k)-\\nabla F\\_k({\\bf w})\\|^2 \\leq \\sigma^2,$ and $ \\mathbb{E}\\_{\\xi^k}\\\\|\\nabla f({\\bf w};\\xi^k)\\\\|^2 \\leq G^2.$\n\nAssumption 4 (heterogeneity): There exists $\\zeta \\geq 0$ such that $\\\\|\\nabla F\\_k({\\bf w})-F({\\bf w})\\\\|\\leq \\zeta^2, \\forall {\\bf w} \\in \\mathbb{R}^d, \\forall k \\in [K]$.\n\nOrMo has the following convergence rate for heterogeneous data distributions:\n$$\\frac{1}{T}\\sum\\_{t=1}^T \\mathbb{E}\\\\|\\nabla F({\\bf{w}}\\_t)\\\\|^2 \\leq \\mathcal{O} (\\frac{\\sigma}{\\sqrt{T}}+ (\\frac{K}{T})^{\\frac{2}{3}} + \\frac{K}{T} + \\zeta^2).$$\n\nCompared to the homogeneous setting, the convergence rate in the heterogeneous setting includes an additive term $\\zeta^2$, where the dependence on $\\zeta^2$ is unavoidable without additional assumptions in asynchronous methods. This result is also consistent with existing works [A]. \n\n\n**Response to Weakness 3:** \n\nThank you for pointing out the demanding nature of the bounded gradient assumption in Assumption $1$. We agree that the bounded gradient assumption is a little stronger compared to the other assumptions. However, we think it is acceptable since the bounded gradient assumption is widely used in theoretical analyses in existing distributed optimization works (e.g., [B] [C]). And the bounded gradient assumption is also aligned with our empirical experience during model training. We will add the discussion above in the final version and thank you for the valuable comment again.\n\n**Response to Weakness 4:** \n\nThank you for the valuable comments. Actually, the stage-wise decreasing learning rate in our experiment can be considered as a combination of constant learning rates and the widely-used restarting technique [D] [E].\n\nIn our experiments, we only tune the initial learning rate while the multiplication factors and the intervals are fixed. In particular, the settings of the multiplication factors and intervals in our experiment are exactly the same as those in previous works ([F] for CIFAR10 and [B] for CIFAR100). These are commonly used configurations for CIFAR training. \n\nWe sincerely apologize for not making it clear in the submission and promise to add the statements above in the final version.\n\n**Response to Question 1:** \n\nThank you for the question. The waiting set $\\mathcal{C}$ is the set of worker indexes that are waiting for the server to send the parameter. The size of the waiting set indicates the number of workers that are idle and waiting for the server to send the parameter. In other words, the size of the waiting set $\\mathcal{C}$ is not a hyper-parameter and thus does not need to be set manually. This concept is introduced to unify SSGD and ASGD into a single framework in Algorithm $1$.\n\n**Response to Question 2:** \n\nWe use the example in [A] to describe the insights. Suppose that there are two parallel workers: one fast worker that takes only $10^{-6}$ seconds to compute a stochastic gradient and one slow worker that takes $1$ second. If we implement ASGD with these two workers, the delay of the slow worker’s gradients will be $1$ million, since in the $1$ second that the server waits for the slower worker, the gradients from the fast worker will produce $1$ million updates. Consequently, analyses based on $\\tau\\_{max}$ degrades by a factor of $10^6$. However, ASGD actually performs very well in this scenario, since $99.9999\\\\%$ of the updates on the server use the stochastic gradients with no delay.\n\nBriefly speaking, slower workers which typically send heavily delayed gradients will engage in fewer training iterations.  And existing analyses for ASGD based on $\\tau\\_{max}$ aren't aligned with the actual performance.\n\n**Response to Question 3:** \n\nOrMo organizes the gradients into the momentum in order based on their iteration indexes. Since the momentum is a weighted sum of the gradients with predefined weights, each gradient is incorporated into momentum by multiplying it with a weight $\\beta^{b\\_{t+1} - \\lceil \\frac{ite(k\\_t, t)}{K}\\rceil}$. The complexity related to the ordering of the gradient is $\\mathcal{O}(1)$, making the cost negligible.\n\nWe hope that we have addressed the reviewer's concerns, and we are always willing to respond to any further concerns. Meanwhile, we would greatly appreciate it if the reviewer could re-evaluate our work based on our response.\n\n[A] Mishchenko et al., Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays. NeurIPS 2022.\n\n[B] Xie et al., CSER: Communication-efficient SGD with Error Reset. NeurIPS 2020.\n\n[C] Xu et al., Detached Error Feedback for Distributed SGD with Random Sparsification. ICML 2022.\n\n[D] Powell et al., Restart procedures for the conjugate gradient method. Mathematical Programming 1977.\n\n[E] Li et al., Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the in the O(epsilon^(-7/4)) Complexity. JMLR 2023.\n\n[F] He et al., Deep Residual Learning for Image Recognition. CVPR 2016.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZrZoUHyHeW", "reviewer": "Reviewer_5XzJ", "summary": "This paper proposed a new ordered momentum for asynchronous SGD based on the delayed update characteristic of asynchronous training, which weights the momentum according to the actual iteration index. The authors proved the convergence of the algorithm both theoretically and experimentally.", "questions": "1. The theoretical results in this paper do not contain asynchronous delay information and fail to reveal the effect of asynchronous delay on the convergence of the algorithm. This may be due to rough gradient upper bounds that obscure the delay gradient information. However, the reviewer believes that analyzing the effect of asynchronous delay is essential in a work that studies ASGD algorithms. Also, the experimental section did not test the empirical effect of different delays on the algorithm.\n\n2. Theorem 1 shows that the convergence of the algorithm is linearly dependent on the number of distributed workers $K$, which implies that the algorithm will fail to converge when $K$ is large. In light of this theoretical result, can't the algorithm proposed in this paper be applied to large-scale distributed training systems?\n\n3. The algorithm design and theoretical analysis in this paper relies on a fixed constant learning rate. Can this be extended to adaptive learning rates or decreasing learning rates that are more common in practice?\n\n4. The result of Lemma 4 in the main text is inconsistent with the proof in the Appendix.", "limitations": "Please refer to Weaknesses and Questions.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* This paper proposes a new momentum algorithm for ASGD and proves that the algorithm is convergent.\n\n* Experiments are conducted in this paper to verify the effectiveness of the OrMo algorithm.", "weaknesses": "* This paper studies asynchronous training algorithms but does not explore the effect of asynchronous delays on convergence.\n\n* The theoretical results in this paper are limited by the number of distributed workers $K$, i.e., the algorithm does not scale well to large-scale distributed training systems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the constructive comments and the support of our work. Below, we respond to the raised concerns and questions point by point.\n\n**Response to Question 1 (Weakness 1):** \n\nThis is a very good question. In fact, a core contribution of this paper is exactly the theoretical guarantee for OrMo, which doesn't contain the asynchronous delay information $\\tau_{max}$ (the maximum delay). In contrast, previous works, such as [B], show that ASGD has a convergence rate of $\\mathcal{O}(\\frac{\\sigma}{\\sqrt{T}}+\\frac{\\tau_{max}}{T})$. However, this convergence result containing the maximum delay $\\tau_{max}$ is not consistent with the actual convergence performance, since vanilla ASGD can converge well when $\\tau_{max}$ is extremely large in practice.\n\nThe most closely related work to ours is [A], which analyzes vanilla ASGD with unbounded gradient delays. We extend the analysis for vanilla ASGD in [A] to OrMo. Our analysis shows that the convergence of OrMo doesn't depend on the maximum delay $\\tau_{max}$. Our experimental results offer additional insights into the convergence rate. In the following table, we show the maximum delays of two different settings in CIFAR10 training when $K=64$. In heterogeneous settings, the existence of slow workers results in a maximum delay that exceeds that of the homogeneous setting by about 100 times. Our experiments show that OrMo can achieve comparable performances in these two settings, which aligns with our theoretical analysis results.\n\n|   | homogeneous |heterogeneous|\n| --- |--| --|\n| Maximum Delay       |    343  | 30911 |\n| Training Loss      |    0.15 $\\pm$ 0.02  | 0.16 $\\pm$ 0.03 |\n| Test Accuracy      |    88.03% $\\pm$ 0.28%  | 87.76% $\\pm$ 0.57% |\n\nOur analysis provides an upper bound for the convergence rate of OrMo and shows that the maximum delay doesn't affect the convergence rate. \n\n**Response to Question 2 (Weakness 2):** \n\nIn our analysis, OrMo achieves a convergence rate of $\\mathcal{O} (\\frac{\\sigma}{\\sqrt{T}}+ (\\frac{K}{T})^{\\frac{2}{3}} + \\frac{K}{T})$. Our convergence result aligns with the theoretical results in Theorem $2$ of [A], which are currently the tightest convergence analyses for vanilla ASGD. This convergence rate indicates that OrMo has a comparable convergence rate to SGD for non-convex problems when $T$ is sufficiently large, as the term $\\frac{\\sigma}{\\sqrt{T}}$ becomes dominant and the non-dominant terms $(\\frac{K}{T})^{\\frac{2}{3}}+\\frac{K}{T}$ have a minimal impact on the overall convergence rate. Thus, OrMo can be applied for large-scale algorithms.\n\nIn existing distributed optimization works (e.g., [C][D][E]), the non-dominant terms in their theoretical results are also constrained by the number of distributed workers. We take the convergence analysis for Gossip-PGA in [E] as an example. According to Subsection $1.1$ of [E], Gossip-PGA has a convergence rate of $\\mathcal{O} (\\frac{\\sigma}{\\sqrt{K\\tilde{T}}} + \\frac{1}{\\tilde{T}^{\\frac{2}{3}}}+\\frac{1}{\\tilde{T}})$, where $\\tilde{T}$ is the number of iterations. Please note that Gossip-PGA is a synchronous algorithm, which requires $K$ gradients on all workers for one update iteration of the parameter. In contrast, one update iteration of the parameter in OrMo requires only one gradient from a single worker. For fair comparison, we rewrite the convergence rate of Gossip-PGA in terms of the number of the gradient computations: $\\mathcal{O} (\\frac{\\sigma}{\\sqrt{C}} + \\frac{K^{\\frac{2}{3}}}{C^{\\frac{2}{3}}}+\\frac{K}{C})$, where $C$ is the number of the gradient computations and $C = K\\tilde{T}$. The convergence rate of OrMo in terms of the number of the gradient computations can be written as $\\mathcal{O} (\\frac{\\sigma}{\\sqrt{C}} + \\frac{K^{\\frac{2}{3}}}{C^{\\frac{2}{3}}}+\\frac{K}{C})$. We can observe that the non-dominant terms $\\mathcal{O}(\\frac{K^{\\frac{2}{3}}}{C^{\\frac{2}{3}}}+\\frac{K}{C})$ in [E] and OrMo are both constrained by the number of the workers.\n\n**Response to Question 3:** \n\nWe sincerely thank you for the constructive comment. We agree that incorporating adaptive learning rates into asynchronous methods is an important research direction. Due to limited space here, please refer to paragraphs 5-6 of our Author Rebuttal for more discussion about the adaptive learning rates. The theoretical analysis for a constant learning rate is a common setting in existing distributed optimization works [C][D][E]. Actually, the stage-wise decreasing learning rate in our experiment can be considered as a combination of constant learning rates and the widely-used restarting technique [F][G].\n\nWe promise to add the statements above in the final version.\n\n**Response to Question 4:** \n\nWe sincerely thank you for your careful review. There is a typo in Lemma 4 in the maintext. The right-hand side of the inequality in Lemma 4 should be $2\\frac{\\beta^2}{(1-\\beta)^4}\\eta^2K^2G^2$. We will fix the typo in the final version. \n\nWe sincerely thank the reviewers for their valuable time and their support of our work again. Meanwhile, we would greatly appreciate it if the reviewer could re-evaluate our work in light of our response.\n\n[A] Mishchenko et al., Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays. NeurIPS 2022.\n\n[B] Stich et al., The Error-Feedback framework: SGD with Delayed Gradients. JMLR 2020.\n\n[C] Xie et al., CSER: Communication-efficient SGD with Error Reset. NeurIPS 2020.\n\n[D] Yu et al., On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization. ICML 2019.\n\n[E] Chen et al., Accelerating Gossip SGD with Periodic Global Averaging. ICML 2021.\n\n[F] Powell et al., Restart procedures for the conjugate gradient method. Mathematical Programming 1977.\n\n[G] Li et al., Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the in the O(epsilon^(-7/4)) Complexity. JMLR 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Cqj9ByunYS", "reviewer": "Reviewer_dA6E", "summary": "In distributed learning environments, asynchronous SGD (ASGD) and its variants are often used to deal with computing nodes with uneven computing power. Momentum methods are beneficial for both optimization and generalization in deep model training, but directly applying momentum to ASGD may hinder its convergence. The paper proposes the OrMo method to integrate momentum into ASGD by sorting gradients based on iteration index. The paper provides a theoretical proof of the convergence of OrMo on non-convex problems.", "questions": "Figure 3 shows that the curve is very unstable. So, on which epoch, the model is used as the final model for testing?", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. A new asynchronous stochastic gradient descent optimization method (OrMo) is proposed, and a theoretical proof of convergence on non-convex problems is provided, which is the first time that it does not rely on the bounded delay assumption.\n2. Experiments show the advantages of the OrMo method in convergence performance.\n3. The paper provides detailed algorithm implementation details and open access links to the experimental code, which enhances the reproducibility.\n4. The experiment setting is clear, and the wall-clock time shows that the OrMo outperforms baseline methods significantly.", "weaknesses": "1. Although experimental validation was performed on the CIFAR dataset, the generalization ability of the OrMo method may need to be further tested in more types of datasets and different application scenarios.\n2. The paper does not discuss in detail the computational resource requirements of the OrMo method on data and models of different scales. Specifically, the ordered momentum need to be cached on the server, the extra storage costs should be considerred.\n3. The proposed re-ordering method inherently is like the staleness control. The difference is that the OrMo proposes using the exponentioal term on \\beta to control the staleness of the incoming gradients.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the constructive comments and the support of our work. Below, we respond to the raised concerns and questions point by point.\n\n**Response to Weakness 1:** \n\nThank you for your valuable feedback and suggestions regarding the generalization ability of the OrMo method. We acknowledge the importance of testing OrMo on a wider range of datasets and in various application scenarios to fully understand its generalization capabilities.\n\nWe conduct an additional experiment by training a Vision Transformer [[1](https://github.com/lucidrains/vit-pytorch/blob/main/vit_pytorch/vit_for_small_dataset.py)] model on CIFAR10 dataset. The experiments are conducted on TITAN XP GPUs. The hyperparameter settings are following that in the submitted paper. Due to current constraints in time and computational resources, the experiments are still ongoing.  More experimental results will be uploaded as soon as possible. The following table shows the test accuracy of OrMo and SMEGA$^2$ in the homogeneous setting when there are $32$ workers. \n\n|                   | SMEGA$^2$                 | OrMo  |\n| -- |--|--|\n|K=32 (homogeneous) | 60.67\\%  | 61.32\\%  |\n\n\nWe appreciate your understanding and hope that the current results still offer valuable insights into the potential of OrMo.\n\n**Response to Weakness 2:** \n\nCompared with vanilla ASGD, the only additional computational resource for OrMo is the storage cost for the momentum on the server. As a momentum method, the extra storage cost for the momentum in OrMo is inevitable. The total storage complexity for the momentum in OrMo is $\\mathcal{O}(d)$, where $d$ is the dimension of the momentum.\n\nMoreover, OrMo only maintains one momentum on the server. In contrast, shifted momentum [A] maintains one momentum on each worker. Therefore, the total storage complexity $\\mathcal{O}(d)$ for the momentum in OrMo is much less than the $\\mathcal{O}(Kd)$ complexity of shifted momentum [A], where $d$ is the dimension of the momentum and $K$ is the number of workers. \n\n**Response to Weakness 3:** \n\nThe update rule in OrMo is motivated by that in SSGDm. The key insight of the update rule of the momentum and parameter in OrMo lies in tracking the sequences $\\hat{\\bf w}_t$ and $\\hat{\\bf u}_t$ defined in Subsection 3.3, which are updated in a manner similar to SSGDm. OrMo cannot be simply regarded as a staleness control method. Due to limited space here, please refer to paragraphs 2-5 in our Author Rebuttal for the details.\n\n**Response to Question 1:** \n\nThe main reason for the instability of the curves in Figure $3$ is that naive ASGDm occasionally fails to converge, as shown in Table $1$. In contrast, our proposed method OrMo demonstrates stable convergence across all experiments. We use the model obtained after the last epoch (i.e., $160$-th epoch for CIFAR10 and $200$-th epoch for CIFAR100) as the final model for testing.\n\nWe hope that we have addressed the reviewer's concerns, and we are always willing to respond to any further concerns. Meanwhile, we would greatly appreciate it if the reviewer could re-evaluate our work based on our response.\n\n[A] Giladi et al., At Stability's Edge: How to Adjust Hyperparameters to Preserve Minima Selection in Asynchronous Training of Neural Networks? ICLR 2020.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank all the reviewers for the comments concerning our manuscript entitled "Ordered Momentum for Asynchronous SGD". These comments are valuable and very helpful. We have read through the comments carefully and responded to the comments point by point. Based on the comments of all the reviewers, we provide additional clarification on our proposed method OrMo.

The update rule in OrMo is motivated by that in SSGDm. The key insight of the update rule of the momentum and parameter in OrMo lies in tracking the sequences $\hat{\bf w}\_t$ and $\hat{\bf u}\_t$ defined in Subsection 3.3, which are updated in a manner similar to SSGDm. 

Moreover, OrMo cannot be simply regarded as a penalty function method, as described in Subsection 5.2 of [A] (or a staleness control method, as described in Subsection 3.2 of [B]). The key insight of both the penalty function methods and the staleness control methods is to reduce the contribution of gradients (or parameters in federated learning algorithms) with larger delays to the parameter update. Concretely, these two methods typically assign smaller weights to the gradients (or parameters in federated learning algorithms) with larger delays when updating the parameter. OrMo differs significantly from these methods.

In OrMo, the update rule of the momentum is formulated as
$${\bf u}\_{t+1} = {\bf u}\_{t+\frac{1}{2}} + \eta \beta^{b\_{t+1} - \lceil \frac{ite(k\_t, t)}{K}\rceil}{\bf g}\_{ite(k\_t, t)}^{k\_t},$$
where the gradient ${\bf g}\_{ite(k\_t, t)}^{k\_t}$ is incorporated into momentum by multiplying it with an exponential weight $\beta^{b\_{t+1} - \lceil \frac{ite(k\_t, t)}{K}\rceil}$, as shown in line $12$ of Algorithm $2$. The exponential weight $\beta^{b\_{t+1} - \lceil \frac{ite(k\_t, t)}{K}\rceil}$ indeed decreases as the delay of the gradient increases. However, when it comes to the update rule of the parameter, the situation changes. As shown in line $13$ of Algorithm $2$, the update rule of the parameter is $${\bf w}\_{t+1} = {\bf w}\_{t+\frac{1}{2}} - \eta \frac{1-\beta^{b\_{t+1} - \lceil \frac{ite(k\_t, t)}{K}\rceil + 1}}{1-\beta}{\bf g}\_{ite(k\_t, t)}^{k\_t},$$
where the gradient ${\bf g}\_{ite(k\_t, t)}^{k\_t}$ is used to update the parameter with the weight $\frac{1-\beta^{b\_{t+1} - \lceil \frac{ite(k\_t, t)}{K}\rceil + 1}}{1-\beta}$. For a given $t$, an increase of the delay $t-ite(k\_t, t)$ implies a decrease in $ite(k\_t, t)$, typically causing the weight $\frac{1-\beta^{b\_{t+1} - \lceil \frac{ite(k\_t, t)}{K}\rceil + 1}}{1-\beta}$ to increase. This is in direct contrast to the insight behind both the penalty function methods and the staleness control methods. The design of the parameter update rule with respect to the momentum value $\beta$ is crucial for formulating the gap between $\hat{\bf w}\_t$ and ${\bf w}\_t$ as outlined in Lemma $2$ in Subsection 3.3. An ablation study was also conducted to justify the parameter update rule in line $13$ of Algorithm $2$. We replaced the update rule in line $13$ of Algorithm 2 with a vanilla SGD step, ${\bf w}\_{t+1} = {\bf w}\_{t+\frac{1}{2}} - \eta {\bf g} \_{ite(k\_t, t)}^{k\_t}$ and name it OrMo (vanilla SGD step). The comparison between OrMo and OrMo (vanilla SGD step) is presented below. 

|Test Accuracy (CIFAR10)       | K=16 (hom.)        | K=64 (hom.)        | K=16 (het.)        | K=64  (het.)       |
| ---|---|-----|-----|----|
|OrMo (vanilla SGD step)       | 90.32\% $\pm$ 0.45\% | 86.08\% $\pm$ 1.33\% | 90.23\% $\pm$ 0.32\% | 86.10\% $\pm$ 1.71\% |
|OrMo                          | **90.95\% $\pm$ 0.27\%** | **88.03\% $\pm$ 0.28\%** | **91.01\% $\pm$ 0.10\%** | **87.76\% $\pm$ 0.57\%** |

The relationship between OrMo and the penalty function methods should be considered orthogonal. An adaptive learning rate, multiplied by a "penalty function" related to the delay of the gradient, can be incorporated into OrMo. For example, replace the learning rate $\eta$ in Algorithm 2 with $\eta\_t = \eta \times penalty(\tau\_t)$, where $penalty$ is the penalty function related to the gradient delay. In this way, the update rule in lines $12$ and $13$ will be 
$${\bf u}\_{t+1} = {\bf u}\_{t+\frac{1}{2}} + \eta\_t \beta^{b\_{t+1} - \lceil \frac{ite(k\_t, t)}{K}\rceil}{\bf g}\_{ite(k\_t, t)}^{k\_t},$$  $${\bf w}\_{t+1} = {\bf w}\_{t+\frac{1}{2}} - \eta\_t \frac{1-\beta^{b\_{t+1} - \lceil \frac{ite(k\_t, t)}{K}\rceil + 1}}{1-\beta}{\bf g}\_{ite(k\_t, t)}^{k\_t}.$$ 
Actually, incorporating adaptive learning rates into asynchronous methods is an important research direction. Some works, such as [C], provide convergence analysis for adaptive learning rates, but these analyses rely on demanding assumptions, such as bounded delays. Some works, such as [D] and [E], offer rigorous theoretical guarantees but lack sufficient empirical verification. Designing adaptive learning rates for asynchronous methods that provide both strong theoretical guarantees and promising empirical results remains an open challenge. Our focus in this paper is on incorporating momentum into ASGD, which is orthogonal to the adaptive learning rate schemes. We plan to explore integrating OrMo with an adaptive learning rate in future work.

We hope that we have addressed the reviewer's concerns, and we are always willing to answer any further questions. Meanwhile, we would greatly appreciate it if the reviewer could re-evaluate our work in light of our response.

[A] Xie et al., Asynchronous Federated Optimization. OPT 2020.

[B] Wu et al., HiFlash: Communication-Efficient Hierarchical Federated Learning with Adaptive Staleness Control and Heterogeneity-aware Client-Edge Association. IEEE TPDS 2023.

[C] Barkai et al., Gap Aware Mitigation of Gradient Staleness. ICLR 2020.

[D] Koloskova et al., Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning. NeurIPS 2022.

[E] Mishchenko et al., Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays. NeurIPS 2022.

Meta-review: Given the momentum information is a critical component in DL training, this paper proposed a novel method -- ordered momentum (OrMo) and focused on studying the convergence efficiency of its asynchronous parallelization. This paper provided a reasonable convergence efficiency proof. Considering the value of the marriage of the practical (asynchronous) parallel system and the practical (momentum based) optimization algorithm, we decide to accept this paper.

But in the meantime, this final version of this paper needs to be significantly improved and polished as suggested by reviewers, especially the following two aspects:
- The boundedness assumption is over strong, which is not essential in this proof. Please refer to [1] and [2] how to remove it. 
- The comparison to existing work about asynchronous/parallel momentum SGD [1] is missing. The discussion of differentiation needs to be more clear.

[1] momentum asynchronous SGD: 1-bit Adam: Communication Efficient Large-Scale Training with Adam’s Convergence Speed
[2] DISTRIBUTED LEARNING SYSTEMS WITH FIRST-ORDER METHODS.
Decision: Accept (poster)