Ordered Momentum for Asynchronous SGD

Authors: chang-wei  shi
yi-rui  yang
wu-jun  li
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 05:32:29

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.

Main paper: 
 introduction: 
 Many machine learning problems, such as support vector machine (SVM), logistic regression, and deep learning models, can be formulated as the following empirical risk minimization problem:EQUATIONwhere w denotes the model parameter, d is the dimension of the parameter, D represents the training dataset, |D| is the number of the training instances and f (w; ξ) denotes the empirical loss on the training instance ξ.Stochastic gradient descent (SGD) [28] and its variants [6, 12] are widely employed to solve the problem in (1) . At each iteration, SGD uses one stochastic gradient or a mini-batch of stochastic gradients as an estimate of the full gradient to update the model parameter. In practice, momentum [26, 36, 24, 33] is often incorporated into SGD as a crucial technique for faster convergence and better generalization performance. Many popular machine learning libraries, such as TensorFlow [1] and PyTorch [25] , include SGD with momentum (SGDm) as one of the optimizers.Due to the rapid increase in the sizes of both models and datasets in recent years, a single machine is often insufficient to complete the training task of machine learning models within a 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 in recent years. Existing distributed learning methods can be categorized into two main types: synchronous distributed learning (SDL) methods [19, 35, 29, 38, 44, 39] 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 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 ADL methods require aggregating information from only one worker or a subset of workers in each communication round. Representative ADL methods include asynchronous SGD (ASGD) and its variants [2, 8, 46, 30, 49, 48, 7, 3, 31, 22, 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.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 [18, 45] , communication compression algorithms [19, 29, 38, 40, 34, 41] , infrequent communication algorithms [44, 39, 40] , and federated learning algorithms [21, 32] . However, in ADL methods, some works [23, 9] 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 ASGD. The works in [23, 9] recommend tuning the momentum coefficient to enhance convergence performance when naively incorporating momentum into ASGD. The work in [9] proposes shifted momentum, which maintains local momentum on each worker. Inspired by Nesterov's accelerated gradient, the work in [4] proposes SMEGA 2 , which leverages the momentum to estimate the future parameter. However, the process of tuning the momentum coefficient in [23, 9] is time-consuming and yields limited improvement in practice. Although shifted momentum and SMEGA 2 can achieve better empirical convergence performance than the method which naively incorporates momentum into ASGD, both of them lack theoretical convergence analysis.In this paper, we propose a 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-convex problems. To the best of our knowledge, this is 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. 
preliminary: 
 In this paper, we use ∥ • ∥ to denote the L 2 norm. For a positive integer n, we use [n] to denote the set {0, 1, 2, . . . , n -1}. ∇f (w; ξ) denotes the stochastic gradient computed over the training instance ξ and model parameter w. In this paper, we focus on the widely used Parameter Server framework [15] , 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, we assume that each worker samples one training instance for gradient computation each time. The analysis of mini-batch sampling on each worker follows a similar approach.One of the most representative methods for distributing SGD across multiple workers is Synchronous SGD (SSGD) [20, 10] . Distributed SGD (DSGD), as presented in Algorithm 1, unifies SSGD and ASGD within a single framework [13] . The waiting set C in Algorithm 1 is a collection of workers (indexes) that are awaiting the server to send the latest parameter. The only difference between SSGD and ASGD is the communication scheduler associated with the waiting set. SSGD corresponds to DSGD with a synchronous communication scheduler, while ASGD corresponds to DSGD with an asynchronous communication scheduler. We use g kt ite(kt,t) to denote the stochastic gradient ∇f (w ite(kt,t) ; ξ kt ), where k t is the index of the worker whose gradient participates in the parameter update at iteration t. The function ite(k, t) denotes the iteration index of the latest parameter sent to worker k before iteration t, where k ∈ [K] and t ∈ [T ]. When K = 1, DSGD Algorithm 1 Distributed SGD 1: Server: 2: Input: number of workers K, number of iterations T , learning rate η, waiting set C = ∅; 3: Initialization: initial parameter w 0 ; 4: Send the initial parameter w 0 to all workers; 5: for iteration t ∈ [T ] do 6:Receive a stochastic gradient g kt ite(kt,t) from some worker k t ;7:Update the parameter w t+1 = w t -ηg kt ite(kt,t) ;Add the worker k t to the waiting set C = C ∪ {k t }; Randomly sample ξ k and compute the stochastic gradient g k = ∇f (w; ξ k );Send the stochastic gradient g k to the server; 17: until receive server's notification to stop degenerates to vanilla SGD, i.e., ite(k t , t) ≡ t. The delay of the gradient g kt ite(kt,t) is defined asτ t = t -ite(k t , t).In ASGD, the latest parameter w t+1 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 as follows:ite(k, t) =    0 t = 0, k ∈ [K], t t > 0, k = k t-1 , ite(k, t -1) t > 0, k ̸ = k t-1 , where k ∈ [K], t ∈ [T ].In SSGD, there is a barrier in the synchronous communication scheduler since the latest parameter w t+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)= ⌊ t K ⌋K, where k ∈ [K], t ∈ [T ]and ⌊•⌋ is the floor function. Remark 1. In existing works [10, 22] , SSGD is often presented in the form of mini-batch SGD:EQUATIONwhere s ∈ [S] and S denotes the number of iterations. Here, all workers aggregate their stochastic gradients to obtain the mini-batch gradient 1 
reformulation of ssgd with momentum: 
 The widely used SGD with momentum (SGDm) [26] can be expressed as follows:EQUATIONEQUATIONwhere ũ0 = 0, β ∈ [0, 1), s ∈ [S] and S denotes the number of iterations. ũs represents the Polyak's momentum. Since SSGD can be presented in the form of mini-batch SGD as depicted in Remark 1, it's straightforward to implement SSGD with momentum (SSGDm) as follows:EQUATIONwhere ũ0 = 0, β ∈ [0, 1), s ∈ [S] and S denotes the number of iterations. Here, the server aggregates the stochastic gradients from all the workers to obtain the mini-batch gradient 1 K k∈[K] ∇f ( ws ; ξ k ), which is then used to update both the parameter and the momentum in (5) .To gain insights from SSGDm on incorporating momentum into ASGD, we reformulate SSGDm in (5) to fit into the framework of Algorithm 1. Similar to the reformulation in Remark 1, the updates using a mini-batch gradient computed over K training instances in (5) are split into K updates, each using a stochastic gradient over a single training instance. The corresponding implementation details of SSGDm are presented in Algorithm 3 in Appendix B. In this way, the update rules of SSGDm in (5) can be reformulated as follows:EQUATIONwhere u 0 = 0, g kt⌊ t K ⌋K = ∇f (w ⌊ t K ⌋K ; ξ kt ) and t ∈ [T ].We 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.1. We investigate how the momentum term u t+1 evolves during the iterations in (6) . For t ≥ K and t ∈ [T ], u t+1 can be formulated as:u t+1 = ⌊ t K ⌋-1 i=0   β ⌊ t K ⌋-i × k∈[K] ηg k iK   + β 0 × t j=⌊ t K ⌋K ηg kj ⌊ t K ⌋K ,where the superscript of the scalar β indicates the exponent. For t < K, u t+1 = β 0 × t j=0 ηg kj 0 . Figure 1 shows u 10 as an example when K = 4. We define {ηg 0 iK , ηg u 10 = β 2 × ηg 0 0 + ηg 1 0 + ηg 2 0 + ηg 3 0 + β 1 × ηg 0 4 + ηg 1 4 + ηg 2 4 + ηg 3 4 + β 0 × ηg 0 8 + ηg 3 8 .(scaled) gradient group, which contains K gradients scaled by the learning rate η. 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 a 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 in the i-th gradient group are weighted byβ ⌊ t K ⌋-i in the momentum u t+1 , where i ∈ [⌊ t K ⌋ + 1].We refer to the gradient group whose gradients are weighted by β 0 as the latest gradient group, which contains the latest gradients. For u t+1 in SSGDm, the latest gradient group corresponds to the ⌊ t K ⌋-th gradient group. Due to the barrier in the synchronous communication scheduler in SSGDm as presented in Algorithm 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 an ordered momentum in SSGDm is straightforward. As shown in line 13 of Algorithm 3, the scaled gradient ηg kt ite(kt,t) is always added to the momentum with a weight of β 0 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.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:EQUATIONOn the contrary, the sequence of gradients computed in ASGD is given by:EQUATIONThus, the i-th (scaled) gradient group in OrMo for ASGD is defined as:ηg k (i-1)K (i-1)K+1 , ηg k (i-1)K+1 (i-1)K+2 , • • • , ηg k iK-1 iK , where i ≥ 1. The 0-th (scaled) gradient group in OrMo is {ηg 0 0 , ηg 1 0 , • • • , ηg K-1 0 }.Despite the difference in the gradients' iteration indexes, each gradient group in OrMo for ASGD also contains K gradients scaled by the learning rate η, similar to that in SSGDm as discussed in Subsection 3.1.We use I t+1 to denote the index of the latest gradient group of u t+1 in OrMo. The iteration index of the latest gradient in u t+1 can be t at most. Since the gradient with iteration index t belongs to the ⌈ t K ⌉-th gradient group, the latest gradient group for u t+1 should be the ⌈ t K ⌉-th gradient group, i.e., I t+1 ≡ ⌈ t K ⌉, ∀t ∈ [T ]. u t+1 is the weighted sum of the gradients from the first I t+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 β ⌈ t K ⌉-i in the momentum u t+1 , where i ∈ [I t+1 + 1] . Figure 2 shows an example of u 10 in OrMo when K = 4.For the t-th iteration in OrMo, the server performs the following operations: Algorithm 2 OrMo 1: Server: 2: Input: number of workers K, number of iterations T , learning rate η, momentum coefficient β ∈ [0, 1), waiting set C = ∅; 3: Initialization: initial parameter w 0 , momentum u 0 = 0, index of the latest gradient group I 0 = 0; 4: Send the initial parameter w 0 and its iteration index 0 to all workers; Receive a stochastic gradient g kt ite(kt,t) and its iteration index ite(k t , t) from some worker k t and then calculate ⌈ ite(kt,t) K ⌉ (i.e., the index of the gradient group that g kt ite(kt,t) belongs to);12:Update the momentumu t+1 = u t+ 1 2 + β It+1-⌈ ite(k t ,t) K ⌉ × ηg kt ite(kt,t) ; 13:Update the parameter w t+1 = w t+ 1 2 -1-β I t+1 -⌈ ite(k t ,t) K ⌉+1 1-β × ηg kt ite(kt,= β 3 × ηg 0 0 + ηg 1 0 + ηg 2 0 + ηg 3 0 + β 2 × ηg k0 1 + ηg k1 2 + ηg k2 3 + β 1 × ηg k5 6 + ηg k7 8 + β 0 × ηg k8 9 .• If the parameter with iteration index t that satisfies ⌈ t K ⌉ > I t has been sent to some worker, update the parameter using the momentum and multiply the momentum with β: w t+ 1 2 = w t -βu t , u t+ 1 2 = βu t , I t+1 = I t + 1. In this way, the momentum changes the index of its latest gradient group to ⌈ t K ⌉ and gets ready to accommodate the new gradient with iteration index t.• Receive a stochastic gradient g kt ite(kt,t) and its iteration index ite(k t , t) from some worker k t and calculate ⌈ ite(kt,t) K ⌉, which is the index of the gradient group that g kt ite(kt,t) belongs to.• Update the momentum:u t+1 = u t+ 1 2 + β It+1-⌈ ite(k t ,t) K ⌉ × ηg kt ite(kt,t). Since the weight of the scaled gradients from the latest gradient group in the momentum is β 0 , the weight of the gradients from the ⌈ ite(kt,t) K ⌉-th gradient group should be β It+1-⌈ ite(k t ,t) K ⌉ .OrMo updates the momentum by adding the scaled gradient ηg kt ite(kt,t) into the momentum with a weight of β It+1-⌈ ite(k t ,t) K ⌉ .• Update the parameter:w t+1 = w t+ 1 2 -1-β I t+1 -⌈ ite(k t ,t) K ⌉+1 1-β× ηg kt ite(kt,t) . The update rule of the parameter in OrMo is motivated by that in SSGDm, as presented in Algorithm 3. In SSGDm, the scaled gradient ηg kt ite(kt,t) is always added to the momentum with a weight of β 0 . At the current iteration, this scaled gradient updates the parameter with a coefficient -1.0. In subsequent iterations, this scaled gradient in the momentum updates the parameter with the coefficients -β, -β 2 , -β 3 , • • • . By the time this scaled gradient is weighted by β It+1-⌈ ite(k t ,t) K ⌉ in the momentum of SSGDm, it has already updated the parameter for I t+1 -⌈ ite(kt,t) K ⌉ + 1 steps, with a total coefficient -It+1-⌈ ite(k t ,t) K ⌉ j=0β j . In OrMo, for the scaled gradient ηg kt ite(kt,t) which is added to the momentum with a weight of β It+1-⌈ ite(k t ,t) K ⌉ , we compensate for the missed I t+1 -⌈ ite(kt,t) K ⌉ + 1 steps compared with SSGDm and update the parameter with the coefficient -1-β I t+1 -⌈ ite(k t ,t) K ⌉+11-β at 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 t to the waiting set C = C ∪ {k t } and execute the asynchronous communication scheduler. Remark 2. Compared to ASGD, the additional communication overhead introduced by the iteration index in OrMo is negligible since the iteration index is only a scalar. Remark 3. When the momentum coefficient β is set to 0, OrMo degenerates to ASGD in Algorithm 1. If the asynchronous communication scheduler in line 15 of Algorithm 2 is replaced by a synchronous communication scheduler: only when all the workers are in the waiting set, i.e., C = [K], send the parameter w t+1 and the iteration index t + 1 to the workers in C and set C to ∅, OrMo degenerates to SSGDm in Algorithm 3.In this section, we prove the convergence of OrMo in Algorithm 2 for non-convex problems. We only present the main results here. The proof details can be found in Appendix C.2.We make the following assumptions, which are widely used in distributed learning [47, 43, 41, 22] . Assumption 1. For any stochastic gradient ∇f (w; ξ k ), we assume that it satisfies:E ξ k [∇f (w; ξ k )] = ∇F (w), E ξ k ∥∇f (w; ξ k ) -∇F (w)∥ 2 ≤ σ 2 , ∀w ∈ R d , ∀k ∈ [K].Assumption 2. For any stochastic gradient ∇f (w; ξ k ), we assume that it satisfies:E ξ k ∥∇f (w; ξ k )∥ 2 ≤ G 2 , ∀w ∈ R d , ∀k ∈ [K]. Assumption 3. F (w) is L-smooth (L > 0): F (w) ≤ F (w ′ ) + ∇F (w ′ ) T (w -w ′ ) + L 2 ∥w -w ′ ∥ 2 , ∀w, w ′ ∈ R d . Assumption 4. The objective function F (w) is lower bounded by F * : F (w) ≥ F * , ∀w ∈ R d .Assumption 1 indicates that the data distributions across all workers are independent and identically distributed (i.i.d.). It's commonly satisfied in the data-center scenario for distributed training [5] , where all workers have access to the full dataset. Our analysis based on Assumption 1 also provides insights into the analysis in a non-i.i.d. setting [22] , which will be studied in future work.Firstly, we define the auxiliary sequence {û t } t≥1 for the momentum: û1 = k∈[K] ηg k 0 , andût+1 = β ût + ηg kt-1 t K | (t -1), ût + ηg kt-1 t K ∤ (t -1), for t ≥ 1.Lemma 1. For any t ≥ 0, the gap between u t+1 and ût+1 can be formulated as follows:EQUATIONThen, we define the auxiliary sequence { ŵt } t≥1 for the parameter: ŵ1 = w 0 -k∈[K] ηg k 0 , andŵt+1 = ŵt -β ût -ηg kt-1 t K | (t -1), ŵt -ηg kt-1 t K ∤ (t -1), for t ≥ 1.Lemma 2. For any t ≥ 0, the gap between w t+1 and ŵt+1 can be formulated as follows:EQUATIONThen, we define another auxiliary sequence {ŷ t } t≥1 : ŷ1 = ŵ1-βw0 1-β , and ŷt+1 = ŷtη 1-β g kt-1 t , for t ≥ 1. Lemma 3. For any t ≥ 1, the gap between ŷt and ŵt can be formulated as follows:EQUATION)Theorem 1. With Assumptions 1, 2, 3 and 4, lettingη = min{ 1-β 2KL , (1-β)∆ 1 2(LT )1 2 σ , (1-β) 5 3 ∆ 1 3 (LKG) 2 3 T 1 3}, Algorithm 2 has the following convergence rate:1 T T t=1 E∥∇F (w t )∥ 2 ≤ O Lσ 2 T + KLG T 2 3 + KL T ,where ∆ = F (w 0 ) -F * and T ≥ K.Many works [46, 30, 7, 13, 22] consider delay-adaptive methods for ASGD. The key insight of these delay-adaptive 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 η in Algorithm 2 with a delay-adaptive learning rate η t , which is dependent on the delay of the gradient τ t . Inspired by [13] , we adopt the following delay-adaptive learning rate η t :η t =    η τ t ≤ 2K, min{η, 1 4Lτ t } τ t > 2K.The convergence of OrMo with the above delay-adaptive learning rate (called OrMo-DA) is guaranteed by Theorem 2.Theorem 2. With Assumptions 1, 3 and 4, lettingη = min{ (1-β) 2 8KL , (1-β) 3 ∆ T Lσ 2 }, OrMo-DA has the following convergence rate: E ∥∇F ( wT )∥ 2 ≤ O Lσ 2 T + KL T ,where (17) .∆ = F (w 0 ) -F * and wT is randomly chosen from {w 0 , w 1 , • • • , w T -1 } according toThe proof details can be found in Appendix C.3. Compared with Theorem 1, Theorem 2 removes the dependence on the bounded gradient assumption in Assumption 2 and provides a better convergence bound. Remark 4. Most existing theoretical analyses of ASGD [16, 49, 3, 20] rely on the maximum delayτ max (e.g., O( Lσ 2 T + τmaxL T) in [20] ). However, since ASGD can still perform well even when the maximum delay is extremely large (τ max ≫ K) in practice, these theoretical analyses don't accurately reflect the true behavior of ASGD. The most closely related works to this work are [13, 22] , which analyze ASGD without relying on the maximum delay. But the works in [13, 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 on the maximum delay. The baseline methods include ASGD, naive ASGDm which naively incorporates momentum into ASGD [23] , shifted momentum [9] and SMEGA 2 [4] . The details of naive ASGDm are shown in Algorithm 4. In OrMo-DA, for a gradient with a large delay satisfying τ t > 2K, its corresponding learning rate will be multiplied by 1 τt . We evaluate these methods by training ResNet20 model [11] on CIFAR10 and CIFAR100 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 ( 116 of all) are designated as slow workers, with an average computation time that is 10 times longer than that of the others.For the CIFAR10 dataset, the weight decay is 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 [11] . The experiments for the CIFAR10 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 160-th epoch, as suggested in [40] . The experiments for the CIFAR100 dataset are conducted on NVIDIA V100 GPUs. Table 1 and Table 2 show the empirical results of different methods. Figure 3 and Figure 4 show the test accuracy curves of different methods. We also present the test accuracy curves of SSGDm for reference in Figure 3 and Figure 4 . Training loss curves can be found in Appendix A.1. 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 on the CIFAR10 dataset with K = 64, the maximum delay under Setting II 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. capability, OrMo can still be more than twice as fast as SSGDm, as shown in Figure 5 (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 to 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-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 state-of-the-art performance.  
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses 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 not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: Following the suggestion in [23, 9] , we conduct experiments to tune the momentum coefficient β for naive ASGDm and present the results when training ResNet20 on CIFAR10 in Table 3 . 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.An ablation study is 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 a vanilla SGD step, w t+1 = w t+ 1 2 -ηg kt ite(kt,t) , 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 . Table 5 and Figure 9 show the performance of different methods when training the ResNet18 model on the CIFAR10 dataset. The number of workers is set to 8. In the homogeneous setting, each worker has similar computing capabilities. In the heterogeneous setting, one worker is designated as the slow worker, whose average computation time is 10 times longer than that of the others.Algorithm 3 and Algorithm 4 show the details of SSGDm and naive ASGDm. if the waiting set C is empty then 7: Wait until receiving the parameter w from the server; 21:w t+ 1 2 = w t -βu t ,Randomly sample ξ k and calculate the stochastic gradient g k = ∇f (w; ξ k ); Receive a stochastic gradient g kt ite(kt,t) from some worker k t ;7:Update the momentum u t+1 = βu t + ηg kt ite(kt,t)Update the parameter w t+1 = w t -u t+1 9:Add the worker k t to the waiting set C = C ∪ {k t }; Base case: for s = 0, w0 = w 0 and ũ0 = u 0 .Inductive hypothesis: for some arbitrary integer s ′ ≥ 0, assume that ws ′ = w s ′ K , ũs ′ = u s ′ K .Inductive step:ũs ′ +1 = β ũs ′ + η K k∈[K] ∇f ( ws ′ ; ξ k ) = βu s ′ K + η k∈[K] ∇f (w s ′ K ; ξ k ) = u (s ′ +1)K , ws ′ +1 = ws ′ -β ũs ′ - η K k∈[K] ∇f ( ws ′ ; ξ k ) = w s ′ K -βu s ′ K -η k∈[K] ∇f (w s ′ K ; ξ k ) = w (s ′ +1)K .We can conclude that ws = w sK and ũs = u sK for any s ∈ [S].Lemma 1 can be viewed as a special case of Lemma 5, and its proof is completed by substituting each delay-adaptive learning rate ηk,t in the proof of Lemma 5 with η for all k ∈ [K] and t ∈ [T ].Lemma 2 can be viewed as a special case of Lemma 6, and its proof is completed by substituting each delay-adaptive learning rate ηk,t in the proof of Lemma 6 with η for all k ∈ [K] and t ∈ [T ].Lemma 3 can be viewed as a special case of Lemma 7, and its proof is completed by substituting each delay-adaptive learning rate ηk,t in the proof of Lemma 7 with η for all k ∈ [K] and t ∈ [T ].Lemma 4. With Assumption 2, the gap between ŷt and ŵt can be bounded:EQUATIONProof. For any t ≥ 1, ût can be formulated as follows:ût = β ⌊ t+K-2 K ⌋   k∈[K] ηg k 0   + ⌊ t+K-2 K ⌋ s=1 β ⌊ t+K-2 K ⌋-s   min{sK,t-1} j=(s-1)K+1 ηg kj-1 j   . ∥ŷ t -ŵt ∥ 2 = β 2 (1 -β) 2 ∥û t ∥ 2 = β 2 (1 -β) 2 β ⌊ t+K-2 K ⌋   k∈[K] ηg k 0   + ⌊ t+K-2 K ⌋ s=1 β ⌊ t+K-2 K ⌋-s   min{sK,t-1} j=(s-1)K+1 ηg kj-1 j   Let q t = k∈[K] β ⌊ t+K-2 K ⌋ + ⌊ t+K-2 K ⌋ s=1 min{sK,t-1} j=(s-1)K+1 β ⌊ t+K-2 K ⌋-s , then we have ∥ŷ t -ŵt ∥ 2 = β 2 (1 -β) 2 β ⌊ t+K-2 K ⌋   k∈[K] ηg k 0   + ⌊ t+K-2 K ⌋ s=1 β ⌊ t+K-2 K ⌋-s   min{sK,t-1} j=(s-1)K+1 ηg kj-1 j   2 = β 2 q 2 t (1 -β) 2 k∈[K] β ⌊ t+K-2 K ⌋ q t ηg k 0 + ⌊ t+K-2 K ⌋ s=1 min{sK,t-1} j=(s-1)K+1 β ⌊ t+K-2 K ⌋-s q t ηg kj-1 j 2 ≤ β 2 q t (1 -β) 2   k∈[K] β ⌊ t+K-2 K ⌋ ηg k 0 2 + ⌊ t+K-2 K ⌋ s=1 min{sK,t-1} j=(s-1)K+1 β ⌊ t+K-2 K ⌋-s ηg kj-1 j 2   E∥ŷ t -ŵt ∥ 2 ≤ β 2 q t (1 -β) 2   k∈[K] β ⌊ t+K-2 K ⌋ E∥ηg k 0 ∥ 2 + ⌊ t+K-2 K ⌋ s=1 min{sK,t-1} j=(s-1)K+1 β ⌊ t+K-2 K ⌋-s E∥ηg kj-1 j ∥ 2   ≤ β 2 η 2 G 2 q t (1 -β) 2   k∈[K] β ⌊ t+K-2 K ⌋ + ⌊ t+K-2 K ⌋ s=1 min{sK,t-1} j=(s-1)K+1 β ⌊ t+K-2 K ⌋-s   = β 2 η 2 G 2 q 2 t (1 -β) 2 ≤ β 2 η 2 K 2 G 2 (1 -β) 4 C.2.4 Proof of Theorem 1 Proof. EF (ŷ t+1 ) ≤ F (ŷ t ) - η 1 -β ⟨∇F (ŷ t ), Eg kt-1 t ⟩ + Lη 2 2(1 -β) 2 E∥g kt-1 t ∥ 2 ≤ F (ŷ t ) - η 1 -β ⟨∇F (ŷ t ), ∇F (w t )⟩ + Lη 2 2(1 -β) 2 E∥g kt-1 t -∇F (w t )∥ 2 + Lη 2 2(1 -β) 2 ∥∇F (w t )∥ 2 ≤ F (ŷ t ) - η 1 -β ⟨∇F (ŷ t ), ∇F (w t )⟩ + Lη 2 σ 2 2(1 -β) 2 + Lη 2 2(1 -β) 2 ∥∇F (w t )∥ 2 -⟨∇F (ŷ t ), ∇F (w t )⟩ = -⟨∇F (ŷ t ) -∇F (w t ) + ∇F (w t ), ∇F (w t )⟩ = -⟨∇F (ŷ t ) -∇F (w t ), ∇F (w t )⟩ -∥∇F (w t )∥ 2 ≤ 1 2 ∥∇F (ŷ t ) -∇F (w t )∥ 2 + 1 2 ∥∇F (w t )∥ 2 -∥∇F (w t )∥ 2 ≤ L 2 2 ∥ŷ t -w t ∥ 2 - 1 2 ∥∇F (w t )∥ 2 E∥ŷ t -w t ∥ 2 ≤ 2E∥ŷ t -ŵt ∥ 2 + 2E∥ ŵt -w t ∥ 2 ≤ 2β 2 η 2 K 2 G 2 (1 -β) 4 + 2η 2 K 2 G 2 (1 -β) 2 ≤ 2η 2 K 2 G 2 (1 -β) 4 EF (ŷ t+1 ) ≤ EF (ŷ t ) - η 1 -β E⟨∇F (ŷ t ), ∇F (w t )⟩ + Lη 2 σ 2 2(1 -β) 2 + Lη 2 2(1 -β) 2 E∥∇F (w t )∥ 2 ≤ EF (ŷ t ) + ηL 2 2(1 -β) E∥ŷ t -w t ∥ 2 + Lη 2 2(1 -β) 2 - η 2(1 -β) E∥∇F (w t )∥ 2 + Lη 2 σ 2 2(1 -β) 2 η≤ 1-β 2KL ≤ EF (ŷ t ) + ηL 2 2(1 -β) E∥ŷ t -w t ∥ 2 - η 4(1 -β) E∥∇F (w t )∥ 2 + Lη 2 σ 2 2(1 -β) 2 ≤ EF (ŷ t ) - η 4(1 -β) E∥∇F (w t )∥ 2 + Lη 2 σ 2 2(1 -β) 2 + η 3 K 2 G 2 L 2 (1 -β) 5Summing up the above equation from t = 1 to t = T , we can get that1 T T t=1 E∥∇F (w t )∥ 2 ≤ 4(1 -β) [EF (ŷ 1 ) -F * ] T η + 2Lησ 2 1 -β + 4η 2 K 2 G 2 L 2 (1 -β) 4 Since ŷ1 -w 0 = 1 1-β ( ŵ1 -w 0 ) = -η 1-β k∈[K] g k 0 , we have EF (ŷ 1 ) ≤ F (w 0 ) - η 1 -β E⟨∇F (w 0 ), k∈[K] g k 0 ⟩ + Lη 2 2(1 -β) 2 E k∈[K] g k 0 2 ≤ F (w 0 ) - Kη 1 -β ∥∇F (w 0 )∥ 2 + Lη 2 2(1 -β) 2 E k∈[K] g k 0 2 ≤ F (w 0 ) - Kη 1 -β ∥∇F (w 0 )∥ 2 + Lη 2 2(1 -β) 2 E k∈[K] g k 0 -K∇F (w 0 ) + K∇F (w 0 ) 2 ≤ F (w 0 ) + LK 2 η 2 2(1 -β) 2 - Kη 1 -β ∥∇F (w 0 )∥ 2 + KLσ 2 η 2 2(1 -β) 2 ≤ F (w 0 ) + KLσ 2 η 2 2(1 -β) 2The last inequality above holds because η ≤ 1-β 2KL . Combining the above equations, we can get thatEQUATION(LT )1 2 σ, (1-β) (LKG)2 3 T 1 3}, then we can get that1 T T t=1 E∥∇F (w t )∥ 2 ≤ O Lσ 2 T + KLG T 2 3 + KL T .The details of OrMo with delay-adaptive learning rate (OrMo-DA) are presented in Algorithm 5.For a positive integer n,[n] = {0, 1, 2, • • • , n -1}. [0] is defined as ∅.The function ite(k, t) denotes the iteration index of the latest parameter sent to worker k before iteration t, which can be formulated asite(k, t) =    0 t = 0, k ∈ [K], t t > 0, k = k t-1 , ite(k, t -1) t > 0, k ̸ = k t-1 , where k ∈ [K], t ∈ [T + 1].Algorithm 5 OrMo-DA 1: Server: 2: Input: number of workers K, number of iterations T , momentum coefficient β ∈ [0, 1); 3: Initialization: initial parameter w 0 , momentum u 0 = 0, index of the latest gradient group I 0 = 0; 4: Send the initial parameter w 0 and its iteration index 0 to all workers; 5: for iteration t ∈ [T ] do 6:if the waiting set C is empty and ⌈ t K ⌉ > I t then 7: Receive a stochastic gradient g kt ite(kt,t) and its iteration index ite(k t , t) from some worker k t and then calculate ⌈ ite(kt,t) K ⌉ (i.e., the index of the gradient group that g kt ite(kt,t) belongs to);w t+ 1 2 = w t -βu t ,12:Update the momentumu t+1 = u t+ 1 2 + β It+1-⌈ ite(k t ,t) K ⌉ × η t g kt ite(kt,t) ; 13:Update the parameterw t+1 = w t+ 1 2 -1-β I t+1 -⌈ ite(k t ,t) K ⌉+1 1-β × η t g kt ite(kt,t) ; 14:Add the worker k t to the waiting set C = C ∪ {k t };15:Execute the asynchronous communication scheduler: once the waiting set is not empty, i.e., C ̸ = ∅, immediately send the parameter w t+1 and its iteration index t + 1 to the worker in C and set C to ∅; Wait until receiving the parameter w t ′ and its iteration index t ′ from the server; 21:Randomly sample ξ k and calculate the stochastic gradient g k t ′ = ∇f (w t ′ ; ξ k );Send the stochastic gradient g k t ′ and its iteration index t ′ to the server; 23: until receive server's notification to stop We define τk,t = t -ite(k, t), where k ∈ [K] and t ∈ [T + 1]. τk,t denotes the current delay of the gradient on worker k at iteration t, which is the number of iterations that have happened since ite(k, t). It's easy to verify that τkt,t = t -ite(k t , t) = τ t , where t ∈ [T ].The function next(k, t) denotes the index of the next iteration that the gradient from worker k will participate in the parameter update after iteration t (including iteration t), which can be formulated asnext(k, t) = min{j ≥ t : k j = k} ∃j ∈ [T ] \ [t] , k j = k, T ∀j ∈ [T ] \ [t] , k j ̸ = k, where k ∈ [K], t ∈ [T ]. It's easy to verify that ite(k, next(k, t)) = ite(k, t), ∀k ∈ [K], t ∈ [T ].η t is the learning rate at iteration t and satisfies thatη t =    η τ t ≤ 2K, min{η, 1 4Lτ t } τ t > 2K, where t ∈ [T ].We also define an auxiliary sequence ηk,t for the learning rate. ηk,t denotes the learning rate corresponding to the gradient on worker k at iteration t.ηk,t =    η τk,next(k,t) ≤ 2K, min{η, 1 4Lτ k,next(k,t) } τk,next(k,t) > 2K,wherek ∈ [K] and t ∈ [T ]. If next(k, t) ∈ [T ], τk,next(k,t) = τk next(k,t) ,next(k,t) = τ next(k,t) and then we have thatηk,t = η next(k,t) =    η τ next(k,t) ≤ 2K, min{η, 1 4Lτ next(k,t) } τ next(k,t) > 2K.It's easy to verify that ηkt,t = η next(kt,t) = η t = η next(kt,ite(kt,t)) = ηkt,ite(kt,t) , where t ∈ [T ].If next(k, t) = T , ηk,t =    η τk,T ≤ 2K, min{η, 1 4Lτ k,T} τk,T > 2K.Firstly, we define one auxiliary sequence {û t } t≥1 for the momentum: û1 = k∈[K] ηk,0 g k 0 , andEQUATIONfor t ≥ 1. Lemma 5. For any t ≥ 0, the gap between u t+1 and ût+1 can be formulated as follows:EQUATION)Proof. Base case: for t = 0, û1 = k∈[K] ηk,0 g k 0 , u 1 = ηk0,0 g k0 0 , then we haveû1 -u 1 = k∈[K],k̸ =k0 β ⌈ 0 K ⌉-⌈ 0 K ⌉ ηk,0 g k 0 = k∈[K],k̸ =k0 β ⌈ 0 K ⌉-⌈ ite(k,0) K ⌉ ηk,ite(k,0) g k ite(k,0) .Inductive hypothesis: for some arbitrary integer t ′ -1 ≥ 0, assume that ( 14) is true for t = t ′ -1.Inductive step: We will prove that ( 14) is true for t = t ′ . Firstly, we divide our discussion into two cases based on whether t ′ -1 is divisible by K and prove thatût ′ +1 -u t ′ +1 = k∈[K],k̸ =k t ′ -1 β ⌈ t ′ K ⌉-⌈ ite(k,t ′ ) K ⌉ ηk,ite(k,t ′ ) g k ite(k,t ′ ) + ηk t ′ -1 ,t ′ g k t ′ -1 t ′ -β ⌈ t ′ K ⌉-⌈ ite(k t ′ ,t ′ ) K ⌉ ηk t ′ ,ite(k t ′ ,t ′ ) g k t ′ ite(k t ′ ,t ′ ) . Case 1: K | (t ′ -1) ût ′ +1 = β ût ′ + ηk t ′ -1 ,t ′ g k t ′ -1 t ′ , u t ′ +1 = βu t ′ + β ⌈ t ′ K ⌉-⌈ ite(k t ′ ,t ′ ) K ⌉ ηk t ′ ,ite(k t ′ ,t ′ ) g k t ′ ite(k t ′ ,t ′ ) , ût ′ +1 -u t ′ +1 = β(û t ′ -u t ′ ) + ηk t ′ -1 ,t ′ g k t ′ -1 t ′ -β ⌈ t ′ K ⌉-⌈ ite(k t ′ ,t ′ ) K ⌉ ηk t ′ ,ite(k t ′ ,t ′ ) g k t ′ ite(k t ′ ,t ′ ) = k∈[K],k̸ =k t ′ -1 β ⌈ t ′ -1 K ⌉+1-⌈ ite(k,t ′ -1) K ⌉ ηk,ite(k,t ′ -1) g k ite(k,t ′ -1) + ηk t ′ -1 ,t ′ g k t ′ -1 t ′ -β ⌈ t ′ K ⌉-⌈ ite(k t ′ ,t ′ ) K ⌉ ηk t ′ ,ite(k t ′ ,t ′ ) g k t ′ ite(k t ′ ,t ′ ) = k∈[K],k̸ =k t ′ -1 β ⌈ t ′ K ⌉-⌈ ite(k,t ′ -1) K ⌉ ηk,ite(k,t ′ -1) g k ite(k,t ′ -1) + ηk t ′ -1 ,t ′ g k t ′ -1 t ′ -β ⌈ t ′ K ⌉-⌈ ite(k t ′ ,t ′ ) K ⌉ ηk t ′ ,ite(k t ′ ,t ′ ) g k t ′ ite(k t ′ ,t ′ ) .⌈ t ′ K ⌉ = ⌈ t ′ -1 K ⌉ + 1. Case 2: K ∤ (t ′ -1) ût ′ +1 = ût ′ + ηk t ′ -1 ,t ′ g k t ′ -1 t ′ , u t ′ +1 = u t ′ + β ⌈ t ′ K ⌉-⌈ ite(k t ′ ,t ′ ) K ⌉ ηk t ′ ,ite(k t ′ ,t ′ ) g k t ′ ite(k t ′ ,t ′ ) , ût ′ +1 -u t ′ +1 = (û t ′ -u t ′ ) + ηk t ′ -1 ,t ′ g k t ′ -1 t ′ -β ⌈ t ′ K ⌉-⌈ ite(k t ′ ,t ′ ) K ⌉ ηk t ′ ,ite(k t ′ ,t ′ ) g k t ′ ite(k t ′ ,t ′ ) = k∈[K],k̸ =k t ′ -1 β ⌈ t ′ -1 K ⌉-⌈ ite(k,t ′ -1) K ⌉ ηk,ite(k,t ′ -1) g k ite(k,t ′ -1) + ηk t ′ -1 ,t ′ g k t ′ -1 t ′ -β ⌈ t ′ K ⌉-⌈ ite(k t ′ ,t ′ ) K ⌉ ηk t ′ ,ite(k t ′ ,t ′ ) g k t ′ ite(k t ′ ,t ′ ) = k∈[K],k̸ =k t ′ -1 β ⌈ t ′ K ⌉-⌈ ite(k,t ′ -1) K ⌉ ηk,ite(k,t ′ -1) g k ite(k,t ′ -1)+ ηk t ′ -1 ,t ′ g k t ′ -1 t ′ -β ⌈ t ′ K ⌉-⌈ ite(k t ′ ,t ′ ) K ⌉ ηk t ′ ,ite(k t ′ ,t ′ ) g k t ′ ite(k t ′ ,t ′ ) .The last equation above holds because⌈ t ′ K ⌉ = ⌈ t ′ -1 K ⌉. Since ite(k, t ′ ) = ite(k, t ′ -1), ∀k ̸ = k t ′ -1, we can get the following equation for both cases above:ût ′ +1 -u t ′ +1 = k∈[K],k̸ =k t ′ -1 β ⌈ t ′ K ⌉-⌈ ite(k,t ′ ) K ⌉ ηk,ite(k,t ′ ) g k ite(k,t ′ ) + ηk t ′ -1 ,t ′ g k t ′ -1 t ′ -β ⌈ t ′ K ⌉-⌈ ite(k t ′ ,t ′ ) K ⌉ ηk t ′ ,ite(k t ′ ,t ′ ) g k t ′ ite(k t ′ ,t ′ ) . If k t ′ = k t ′ -1 , then we have ite(k t ′ , t ′ ) = t ′ and ût ′ +1 -u t ′ +1 = k∈[K],k̸ =k t ′ β ⌈ t ′ K ⌉-⌈ ite(k,t ′ ) K ⌉ ηk,ite(k,t ′ ) g k ite(k,t ′ ) . If k t ′ ̸ = k t ′ -1 , then we have ût ′ +1 -u t ′ +1 = k∈[K],k̸ =k t ′ -1 β ⌈ t ′ K ⌉-⌈ ite(k,t ′ ) K ⌉ ηk,ite(k,t ′ ) g k ite(k,t ′ ) + ηk t ′ -1 ,t ′ g k t ′ -1 t ′ -β ⌈ t ′ K ⌉-⌈ ite(k t ′ ,t ′ ) K ⌉ ηk t ′ ,ite(k t ′ ,t ′ ) g k t ′ ite(k t ′ ,t ′ ) = k∈[K],k̸ =k t ′ -1 ,k̸ =k t ′ β ⌈ t ′ K ⌉-⌈ ite(k,t ′ ) K ⌉ ηk,ite(k,t ′ ) g k ite(k,t ′ ) + ηk t ′ -1 ,t ′ g k t ′ -1 t ′ = k∈[K],k̸ =k t ′ -1 ,k̸ =k t ′ β ⌈ t ′ K ⌉-⌈ ite(k,t ′ ) K ⌉ ηk,ite(k,t ′ ) g k ite(k,t ′ ) + β ⌈ t ′ K ⌉-⌈ ite(k t ′ -1 ,t ′ ) K ⌉ ηk t ′ -1 ,ite(k t ′ -1 ,t ′ ) g k t ′ -1 ite(k t ′ -1 ,t ′ ) = k∈[K],k̸ =k t ′ β ⌈ t ′ K ⌉-⌈ ite(k,t ′ ) K ⌉ ηk,ite(k,t ′ ) g k ite(k,t ′ ) .We can conclude that ût+1 -u t+1 = k∈[K],k̸ =kt β ⌈ t K ⌉-⌈ ite(k,t) K ⌉ ηk,ite(k,t) g k ite(k,t) is true for any t ≥ 0.Then, we define one auxiliary sequence { ŵt } t≥1 for the parameter: ŵ1 = w 0 -k∈[K] ηk,0 g k 0 , andŵt+1 = ŵt -β ût -ηkt-1,t g kt-1 t K | (t -1), ŵt -ηkt-1,t g kt-1 t K ∤ (t -1), for t ≥ 1.Lemma 6. For any t ≥ 0, the gap between w t+1 and ŵt+1 can be formulated as follows:EQUATIONProof. Base case: for t = 0, ŵ1 = w 0 -k∈[K] ηk,0 g k 0 , w 1 = w 0 -ηk0,0 g k0 0 , then we haveŵ1 -w 1 = - k∈[K],k̸ =k0 1 -β ⌈ 0 K ⌉-⌈ ite(k,0) K ⌉+1 1 -β ηk,ite(k,0) g k ite(k,0) .Inductive hypothesis: for some arbitrary integer t ′ -1 ≥ 0, assume that ( 15) is true for t = t ′ -1.Inductive step: We will prove that ( 15) is true for t = t ′ . Firstly, we divide our discussion into two cases based on whether t ′ -1 is divisible by K and prove thatŵt ′ +1 -w t ′ +1 = - k∈[K],k̸ =k t ′ -1 1 -β ⌈ t ′ K ⌉-⌈ ite(k,t ′ ) K ⌉+1 1 -β ηk,ite(k,t ′ ) g k ite(k,t ′ ) -ηk t ′ -1 ,t ′ g k t ′ -1 t ′ + 1 -β ⌈ t ′ K ⌉-⌈ ite(k t ′ ,t ′ ) K ⌉+1 1 -β ηk t ′ ,ite(k t ′ ,t ′ ) g k t ′ ite(k t ′ ,t ′ ) . Case 1: K | (t ′ -1) ŵt ′ +1 = ŵt ′ -β ût ′ -ηk t ′ -1 ,t ′ g k t ′ -1 t ′ , w t ′ +1 = w t ′ -βu t ′ - 1 -β ⌈ t ′ K ⌉-⌈ ite(k ′ ,t ′ ) K ⌉+1 1 -β ηk t ′ ,ite(k t ′ ,t ′ ) g k t ′ ite(k t ′ ,t ′ ) , ŵt ′ +1 -w t ′ +1 = ŵt ′ -w t ′ -β (û t ′ -u t ′ ) -ηk t ′ -1 ,t ′ g k t ′ -1 t ′ + 1 -β ⌈ t ′ K ⌉-⌈ ite(k t ′ ,t ′ ) K ⌉+1 1 -β ηk t ′ ,ite(k t ′ ,t ′ ) g k t ′ ite(k t ′ ,t ′ ) = - k∈[K],k̸ =k t ′ -1 1 -β ⌈ t ′ -1 K ⌉-⌈ ite(k,t ′ -1) K ⌉+1 1 -β ηk,ite(k,t ′ -1) g k ite(k,t ′ -1) - k∈[K],k̸ =k t ′ -1 β ⌈ t ′ -1 K ⌉-⌈ ite(k,t ′ -1) K ⌉+1 ηk,ite(k,t ′ -1) g k ite(k,t ′ -1) -   ηk t ′ -1 ,t ′ g k t ′ -1 t ′ - 1 -β ⌈ t ′ K ⌉-⌈ ite(k t ′ ,t ′ ) K ⌉+1 1 -β ηk t ′ ,ite(k t ′ ,t ′ ) g k t ′ ite(k t ′ ,t ′ )   = - k∈[K],k̸ =k t ′ -1 1 -β ⌈ t ′ -1 K ⌉-⌈ ite(k,t ′ -1) K ⌉+2 1 -β ηk,ite(k,t ′ -1) g k ite(k,t ′ -1) -ηk t ′ -1 ,t ′ g k t ′ -1 t ′ + 1 -β ⌈ t ′ K ⌉-⌈ ite(k t ′ ,t ′ ) K ⌉+1 1 -β ηk t ′ ,ite(k t ′ ,t ′ ) g k t ′ ite(k t ′ ,t ′ ) = - k∈[K],k̸ =k t ′ -1 1 -β ⌈ t ′ K ⌉-⌈ ite(k,t ′ -1) K ⌉+1 1 -β ηk,ite(k,t ′ -1) g k ite(k,t ′ -1) -ηk t ′ -1 ,t ′ g k t ′ -1 t ′ + 1 -β ⌈ t ′ K ⌉-⌈ ite(k t ′ ,t ′ ) K ⌉+1 1 -β ηk t ′ ,ite(k t ′ ,t ′ ) g k t ′ ite(k t ′ ,t ′ ) .The last equation above holds because⌈ t ′ K ⌉ = ⌈ t ′ -1 K ⌉ + 1. Case 2: K ∤ (t ′ -1) ŵt ′ +1 = ŵt ′ -ηk t ′ -1 ,t ′ g k t ′ -1 t ′ , w t ′ +1 = w t ′ - 1 -β ⌈ t ′ K ⌉-⌈ ite(k t ′ ,t ′ ) K ⌉+1 1 -β ηk t ′ ,ite(k t ′ ,t ′ ) g k t ′ ite(k t ′ ,t ′ ) , ŵt ′ +1 -w t ′ +1 = ŵt ′ -w t ′ -   ηk t ′ -1 ,t ′ g k t ′ -1 t ′ - 1 -β ⌈ t ′ K ⌉-⌈ ite(k t ′ ,t ′ ) K ⌉+1 1 -β ηk t ′ ,ite(k t ′ ,t ′ ) g k t ′ ite(k t ′ ,t ′ )   = - k∈[K],k̸ =k t ′ -1 1 -β ⌈ t ′ -1 K ⌉-⌈ ite(k,t ′ -1) K ⌉+1 1 -β ηk,ite(k,t ′ -1) g k ite(k,t ′ -1) -ηk t ′ -1 ,t ′ g k t ′ -1 t ′ + 1 -β ⌈ t ′ K ⌉-⌈ ite(k t ′ ,t ′ ) K ⌉+1 1 -β ηk t ′ ,ite(k t ′ ,t ′ ) g k t ′ ite(k t ′ ,t ′ ) = - k∈[K],k̸ =k t ′ -1 1 -β ⌈ t ′ K ⌉-⌈ ite(k,t ′ -1) K ⌉+1 1 -β ηk,ite(k,t ′ -1) g k ite(k,t ′ -1) -ηk t ′ -1 ,t ′ g k t ′ -1 t ′ + 1 -β ⌈ t ′ K ⌉-⌈ ite(k t ′ ,t ′ ) K ⌉+1 1 -β ηk t ′ ,ite(k t ′ ,t ′ ) g k t ′ ite(k t ′ ,t ′ ) .The last equation above holds because⌈ t ′ K ⌉ = ⌈ t ′ -1 K ⌉. Since ite(k, t ′ ) = ite(k, t ′ -1), ∀k ̸ = k t ′ -1, we can get the following equation for both cases above:ŵt ′ +1 -w t ′ +1 = - k∈[K],k̸ =k t ′ -1 1 -β ⌈ t ′ K ⌉-⌈ ite(k,t ′ ) K ⌉+1 1 -β ηk,ite(k,t ′ ) g k ite(k,t ′ ) -ηk t ′ -1 ,t ′ g k t ′ -1 t ′ + 1 -β ⌈ t ′ K ⌉-⌈ ite(k t ′ ,t ′ ) K ⌉+1 1 -β ηk t ′ ,ite(k t ′ ,t ′ ) g k t ′ ite(k t ′ ,t ′ ) . If k t ′ = k t ′ -1 , then we have ite(k t ′ , t ′ ) = t ′ and ŵt ′ +1 -w t ′ +1 = - k∈[K],k̸ =k t ′ 1 -β ⌈ t ′ K ⌉-⌈ ite(k,t ′ ) K ⌉+1 1 -β ηk,ite(k,t ′ ) g k ite(k,t ′ ) . If k t ′ ̸ = k t ′ -1 , then we have ŵt ′ +1 -w t ′ +1 = - k∈[K],k̸ =k t ′ -1 1 -β ⌈ t ′ K ⌉-⌈ ite(k,t ′ ) K ⌉+1 1 -β ηk,ite(k,t ′ ) g k ite(k,t ′ ) -ηk t ′ -1 ,t ′ g k t ′ -1 t ′ + 1 -β ⌈ t ′ K ⌉-⌈ ite(k t ′ ,t ′ ) K ⌉+1 1 -β ηk t ′ ,ite(k t ′ ,t ′ ) g k t ′ ite(k t ′ ,t ′ ) = - k∈[K],k̸ =k t ′ -1 ,k̸ =k t ′ 1 -β ⌈ t ′ K ⌉-⌈ ite(k,t ′ ) K ⌉+1 1 -β ηk,ite(k,t ′ ) g k ite(k,t ′ ) -ηk t ′ -1 ,t ′ g k t ′ -1 t ′ = - k∈[K],k̸ =k t ′ 1 -β ⌈ t ′ K ⌉-⌈ ite(k,t ′ ) K ⌉+1 1 -β ηk,ite(k,t ′ ) g k ite(k,t ′ )We can conclude that ŵt+1 -w t+1 = -k∈[K],k̸ =kt 1-β ⌈ t K ⌉-⌈ ite(k,t) K ⌉+1 1-β ηk,ite(k,t) g k ite(k,t) is true for any t ≥ 0.Then, we define another auxiliary sequence {ŷ t } t≥1 : ŷ1 = w 0 -1 1-β k∈[K] ηk,0 g k 0 , andŷt+1 = ŷt - 1 1 -β ηkt-1,t g kt-1 t , for t ≥ 1.Lemma 7. For any t ≥ 1, the gap between ŷt and ŵt can be formulated as follows:EQUATIONProof. Base case: For t = 1, we have thatŷ1 -ŵ1 =   w 0 - 1 1 -β k∈[K] ηk,0 g k 0   -   w 0 - k∈[K] ηk,0 g k 0   = - β 1 -β k∈[K] ηk,0 g k 0 = - β 1 -β û1 .Inductive hypothesis: for some arbitrary integer t ′ ≥ 1, assume that ŷtŵt = -β 1-β ût is true for t = t ′ .Inductive step: We will prove that ŷtŵt = -β 1-β ût is true for t = t ′ +1. We divide our discussion into two cases based on whether t ′ -1 is divisible by K.Case 1: K | (t ′ -1) ŷt ′ +1 = ŷt ′ - 1 1 -β ηk t ′ -1 ,t ′ g k t ′ -1 t ′ ŵt ′ +1 = ŵt ′ -β ût ′ -ηk t ′ -1 ,t ′ g k t ′ -1 t ′ ŷt ′ +1 -ŵt ′ +1 = ŷt ′ - 1 1 -β ηk t ′ -1 ,t ′ g k t ′ -1 t ′ -ŵt ′ -β ût ′ -ηk t ′ -1 ,t ′ g k t ′ -1 t ′ = ŷt ′ -ŵt ′ + β ût ′ - β 1 -β ηk t ′ -1 ,t ′ g k t ′ -1 t ′ = - β 2 1 -β ût ′ - β 1 -β ηk t ′ -1 ,t ′ g k t ′ -1 t ′ = - β 1 -β ût ′ +1 Case 2: K ∤ (t ′ -1) ŷt ′ +1 = ŷt ′ - 1 1 -β ηk t ′ -1 ,t ′ g k t ′ -1 t ′ ŵt ′ +1 = ŵt ′ -ηk t ′ -1 ,t ′ g k t ′ -1 t ′ ŷt ′ +1 -ŵt ′ +1 = ŷt ′ - 1 1 -β ηk t ′ -1 ,t ′ g k t ′ -1 t ′ -ŵt ′ -ηk t ′ -1 ,t ′ g k t ′ -1 t ′ = ŷt ′ -ŵt ′ - β 1 -β ηk t ′ -1 ,t ′ g k t ′ -1 t ′ = - β 1 -β ût ′ - β 1 -β ηk t ′ -1 ,t ′ g k t ′ -1 t ′ = - β 1 -β ût ′ +1We can conclude that ŷtŵt = -β 1-β ût is true for any t ≥ 1.Lemma 8. For any t ≥ 1, ût can be formulated as follows:ût = β ⌊ t+K-2 K ⌋   k∈[K] ηk,0 g k 0   + ⌊ t+K-2 K ⌋ s=1 β ⌊ t+K-2 K ⌋-s   min{sK,t-1} j=(s-1)K+1 ηkj-1,j g kj-1 j   .Proof. It's straightforward to get this conclusion from the definition of the sequence ût in (13) .Lemma 9. (descent lemma) With Assumptions 1 and 3, we have the following descent lemma for t ≥ 1,:EF (ŷ t+1 ) ≤ F (ŷ t ) + L(η kt-1,t ) 2 2(1 -β) 2 - ηkt-1,t 2(1 -β) ∥∇F (w t )∥ 2 + (η kt-1,t ) 2 σ 2 L 2(1 -β) 2 + L 2 ηkt-1,t 1 -β ∥ŷ t -ŵt ∥ 2 + L 2 ηkt-1,t 1 -β ∥ ŵt -w t ∥ 2 .Proof.EQUATIONLemma 10. With Assumption 1, the gap between ŷt and ŵt in OrMo-DA can be bounded as follows:T -1 t=1 E ηkt-1,t ∥ŷ t -ŵt ∥ 2 ≤ 2β 2 ηK 2 (1 -β) 4   k∈[K] (η k,0 ) 2 ∥∇F (w 0 )∥ 2 + T -1 t=1 ηkt-1,t 2 E ∥∇F (w t )∥ 2   + 2β 2 ηKσ 2 (1 -β) 3   k∈[K] (η k,0 ) 2 + T -1 t=1 ηkt-1,t 2   .Proof.E ∥û t ∥ 2 = E β ⌊ t+K-2 K ⌋   k∈[K] ηk,0 g k 0   + ⌊ t+K-2 K ⌋ s=1 β ⌊ t+K-2 K ⌋-s   min{sK,t-1} j=(s-1)K+1 ηkj-1,j g kj-1 j   2 ≤ 2E β ⌊ t+K-2 K ⌋   k∈[K] ηk,0 g k 0 -∇F (w 0 )   + ⌊ t+K-2 K ⌋ s=1 β ⌊ t+K-2 K ⌋-s   min{sK,t-1} j=(s-1)K+1 ηkj-1,j g kj-1 j -∇F (w j )   2 + 2E β ⌊ t+K-2 K ⌋   k∈[K] ηk,0 ∇F (w 0 )   + ⌊ t+K-2 K ⌋ s=1 β ⌊ t+K-2 K ⌋-s   min{sK,t-1} j=(s-1)K+1 ηkj-1,j ∇F (w j )   2 ≤ 2 k∈[K] β 2⌊ t+K-2 K ⌋ (η k,0 ) 2 σ 2 + 2 ⌊ t+K-2 K ⌋ s=1 min{sK,t-1} j=(s-1)K+1 β 2⌊ t+K-2 K ⌋-2s ηkj-1,j 2 σ 2 + 2E β ⌊ t+K-2 K ⌋   k∈[K] ηk,0 ∇F (w 0 )   + ⌊ t+K-2 K ⌋ s=1 β ⌊ t+K-2 K ⌋-s   min{sK,t-1} j=(s-1)K+1 ηkj-1,j ∇F (w j )   Let q t = k∈[K] β ⌊ t+K-2 K ⌋ + ⌊ t+K-2 K ⌋ s=1 min{sK,t-1} j=(s-1)K+1 β ⌊ t+K-2 K ⌋-s , then we have E β ⌊ t+K-2 K ⌋   k∈[K] ηk,0 ∇F (w 0 )   + ⌊ t+K-2 K ⌋ s=1 β ⌊ t+K-2 K ⌋-s   min{sK,t-1} j=(s-1)K+1 ηkj-1,j ∇F (w j )   2 = q 2 t E   k∈[K] β ⌊ t+K-2 K ⌋ q t ηk,0 ∇F (w 0 )   + ⌊ t+K-2 K ⌋ s=1   min{sK,t-1} j=(s-1)K+1 β ⌊ t+K-2 K ⌋-s q t ηkj-1,j ∇F (w j )   2 ≤ q t   k∈[K] β ⌊ t+K-2 K ⌋ (η k,0 ) 2 ∥∇F (w 0 )∥ 2 + ⌊ t+K-2 K ⌋ s=1 min{sK,t-1} j=(s-1)K+1 β ⌊ t+K-2 K ⌋-s ηkj-1,j 2 E ∥∇F (w j )∥ 2   ≤ K 1 -β   k∈[K] β ⌊ t+K-2 K ⌋ (η k,0 ) 2 ∥∇F (w 0 )∥ 2 + ⌊ t+K-2 K ⌋ s=1 min{sK,t-1} j=(s-1)K+1 β ⌊ t+K-2 K ⌋-s ηkj-1,j 2 E ∥∇F (w j )∥ 2  Thus, we get thatE ∥û t ∥ 2 ≤ 2E β ⌊ t+K-2 K ⌋   k∈[K] ηk,0 ∇F (w 0 )   + ⌊ t+K-2 K ⌋ s=1 β ⌊ t+K-2 K ⌋-s   min{sK,t-1} j=(s-1)K+1 ηkj-1,j ∇F (w j )   2 + 2 k∈[K] β 2⌊ t+K-2 K ⌋ (η k,0 ) 2 σ 2 + 2 ⌊ t+K-2 K ⌋ s=1 min{sK,t-1} j=(s-1)K+1 β 2⌊ t+K-2 K ⌋-2s ηkj-1,j 2 σ 2 ≤ 2K 1 -β   k∈[K] β ⌊ t+K-2 K ⌋ (η k,0 ) 2 ∥∇F (w 0 )∥ 2 + ⌊ t+K-2 K ⌋ s=1 min{sK,t-1} j=(s-1)K+1 β ⌊ t+K-2 K ⌋-s ηkj-1,j 2 E ∥∇F (w j )∥ 2   + 2 k∈[K] β 2⌊ t+K-2 K ⌋ (η k,0 ) 2 σ 2 + 2 ⌊ t+K-2 K ⌋ s=1 min{sK,t-1} j=(s-1)K+1 β 2⌊ t+K-2 K ⌋-2s ηkj-1,j 2 σ 2 T -1 t=1 E ηkt-1,t ∥ŷ t -ŵt ∥ 2 ≤ β 2 η (1 -β) 2 T -1 t=1 E ∥û t ∥ 2 ≤ 2β 2 ηK 2 (1 -β) 4   k∈[K] (η k,0 ) 2 ∥∇F (w 0 )∥ 2 + T -1 t=1 ηkt-1,t 2 E ∥∇F (w t )∥ 2   + 2β 2 ηKσ 2 (1 -β) 3   k∈[K] (η k,0 ) 2 + T -1 t=1 ηkt-1,t 2   .Lemma 11. With Assumption 1, letting η ≤ 1 8KL , the gap between ŵt and w t in OrMo-DA can be bounded as follows:T -1 t=1 E ηkt-1,t ∥ ŵt -w t ∥ 2 ≤ ηK 2L(1 -β) 2   T -1 t=1 ηkt-1,t ∥∇F (w t )∥ 2 +   k∈[K] ηk,0   ∥∇F (w 0 )∥ 2   + ησ 2 2L(1 -β) 2   T -1 t=1 ηkt-1,t + k∈[K] ηk,0   Proof. T -1 t=1 E ηkt-1,t ∥ ŵt -w t ∥ 2 ≤ η T -1 t=1 E ∥ ŵt -w t ∥ 2 = η T -1 t=1 E k∈[K],k̸ =kt-1 1 -β ⌈ t-1 K ⌉-⌈ ite(k,t-1) K ⌉+1 1 -β ηk,ite(k,t-1) g k ite(k,t-1) 2 ≤ 2η T -1 t=1 E k∈[K],k̸ =kt-1 1 -β ⌈ t-1 K ⌉-⌈ ite(k,t-1) K ⌉+1 1 -β ηk,ite(k,t-1) g k ite(k,t-1) -∇F (w ite(k,t-1) ) 2 + 2η T -1 t=1 E k∈[K],k̸ =kt-1 1 -β ⌈ t-1 K ⌉-⌈ ite(k,t-1) K ⌉+1 1 -β ηk,ite(k,t-1) ∇F (w ite(k,t-1) ) 2 ≤ 2η (1 -β) 2 T -2 t=0 k∈[K],k̸ =kt ηk,ite(k,t) 2 σ 2 + KE ∇F (w ite(k,t) ) 2 = 2η (1 -β) 2 T -2 j=0 T -2 t=0 k∈[K] ηk,ite(k,t) 2 σ 2 + KE ∇F (w ite(k,t) ) 2 1 (k ̸ = k t ) 1 (j = ite(k, t)) = 2η (1 -β) 2 T -2 j=1 T -2 t=0 k∈[K] ηk,ite(k,t) 2 σ 2 + KE ∇F (w ite(k,t) ) 2 1 (k ̸ = k t ) 1 (j = ite(k, t)) + 2η (1 -β) 2 T -2 t=0 k∈[K] ηk,ite(k,t) 2 σ 2 + KE ∇F (w ite(k,t) ) 2 1 (k ̸ = k t ) 1 (0 = ite(k, t)) = 2η (1 -β) 2 T -2 j=1 ηkj-1,j 2 σ 2 + KE ∥∇F (w j )∥ 2 (next(k j-1 , j) -j) + 2η (1 -β) 2 k∈[K] (η k,0 ) 2 σ 2 + K ∥∇F (w 0 )∥ 2 (next(k, 0) -0) T -1 t=1 E ηkt-1,t ∥ ŵt -w t ∥ 2 ≤ 2η (1 -β) 2 T -1 t=1 ηkt-1,t 2 σ 2 + KE ∥∇F (w t )∥ 2 τkt-1,next(kt-1,t) + 2η (1 -β) 2 k∈[K] (η k,0 ) 2 σ 2 + K ∥∇F (w 0 )∥ 2 τk,next(k,0) T -1 t=1 E ηkt-1,t ∥ ŵt -w ∥ 2 ≤ η 2L(1 -β) 2   T -1 t=1 ηkt-1,t σ 2 + KE ∥∇F (w t )∥ 2 + k∈[K] ηk,0 σ 2 + K ∥∇F (w 0 )∥ 2   ≤ ηK 2L(1 -β) 2   T -1 t=1 ηkt-1,t E ∥∇F (w t )∥ 2 +   k∈[K] ηk,0   ∥∇F (w 0 )∥ 2   + ησ 2 2L(1 -β) 2   T -1 t=1 ηkt-1,t + k∈[K] ηk,0   .Theorem 3. With Assumptions 1, 3 and 4, lettingη t =    η τ t ≤ 2K min{η, 1 4Lτ t } τ t > 2K,and η = min{ (1-β) 2 8KL , (1-β) 3 ∆ T Lσ 2 }, Algorithm 5 has the following convergence rate:E ∥∇F ( wT )∥ 2 ≤ O( Lσ 2 T + KL T ).where wT is randomly chosen from w 0 , w 1 , • • • , w T -1 according to (17) .Proof.EF (ŷ 1 ) ≤ F (w 0 ) - 1 1 -β E⟨∇F (w 0 ),   k∈[K] ηk,0 g k 0   ⟩ + L 2(1 -β) 2 E k∈[K] ηk,0 g k 0 2 = F (w 0 ) - k∈[K] ηk,0 1 -β ∥∇F (w 0 )∥ 2 + L 2(1 -β) 2 E k∈[K] ηk,0 g k 0 -∇F (w 0 ) + ∇F (w 0 ) 2 ≤ F (w 0 ) +    L k∈[K] ηk,0 2 2(1 -β) 2 - k∈[K] ηk,0 1 -β    ∥∇F (w 0 )∥ 2 + Lσ 2 2(1 -β) 2 k∈[K] (η k,0 ) 2 EF (ŷ T ) -EF (ŷ 1 ≤ E T -1 t=1 L(η kt-1,t ) 2 2(1 -β) 2 - ηkt-1,t 2(1 -β) ∥∇F (w t )∥ 2 + Lσ 2 2(1 -β) 2 T -1 t=1 (η kt-1,t ) 2 + E L 2 1 -β T -1 t=1 ηkt-1,t ∥ ŵt -w t ∥ 2 + ηkt-1,t ∥ŷ t -ŵt ∥ 2 ≤ E T -1 t=1 L(η kt-1,t ) 2 2(1 -β) 2 - ηkt-1,t 2(1 -β) ∥∇F (w t )∥ 2 + Lσ 2 2(1 -β) 2 T -1 t=1 (η kt-1,t ) 2 + ηLσ 2 2(1 -β) 3   T -1 t=1 ηkt-1,t + k∈[K] ηk,0   + ηKL 2(1 -β) 3   T -1 t=1 ηkt-1,t E ∥∇F (w t )∥ 2 +   k∈[K] ηk,0   ∥∇F (w 0 )∥ 2   + 2β 2 ηK 2 L 2 (1 -β) 5   k∈[K] (η k,0 ) 2 ∥∇F (w 0 )∥ 2 + T -1 t=1 ηkt-1,t 2 E ∥∇F (w t )∥ 2   + 2β 2 ηKL 2 σ 2 (1 -β) 4   k∈[K] (η k,0 ) 2 + T -1 t=1 ηkt-1,t 2   ≤ E T -1 t=1 L(η kt-1,t ) 2 2(1 -β) 2 - ηkt-1,t 2(1 -β) ∥∇F (w t )∥ 2 + Lσ 2 2(1 -β) 2 T -1 t=1 (η kt-1,t ) 2 + ηLσ 2 2(1 -β) 3 + ηβ 2 Lσ 2 4(1 -β) 2   T -1 t=1 ηkt-1,t + k∈[K] ηk,0   + ηKL 2(1 -β) 3   T -1 t=1 ηkt-1,t E ∥∇F (w t )∥ 2 + k∈[K] ηk,0 ∥∇F (w 0 )∥ 2   + β 2 ηKL 4(1 -β) 3   k∈[K] ηk,0 ∥∇F (w 0 )∥ 2 + T -1 t=1 ηkt-1,t E ∥∇F (w t )∥ 2   ≤ E T -1 t=1 L(η kt-1,t ) 2 2(1 -β) 2 - ηkt-1,t 2(1 -β) ∥∇F (w t )∥ 2 + Lσ 2 2(1 -β) 2 T -1 t=1 (η kt-1,t ) 2 + ηLσ 2 (1 -β) 3   T -1 t=1 ηkt-1,t + k∈[K] ηk,0   + ηKL (1 -β) 3   T -1 t=1 ηkt-1,t E ∥∇F (w t )∥ 2 + k∈[K] ηk,0 ∥∇F (w 0 )∥ 2   ≤ E T -1 t=1 L(η kt-1,t ) 2 2(1 -β) 2 - ηkt-1,t 2(1 -β) ∥∇F (w t )∥ 2 + Lσ 2 2(1 -β) 2 T -1 t=1 (η kt-1,t ) 2 + ηLσ 2 (1 -β) 3   T -1 t=1 ηkt-1,t + k∈[K] ηk,0   + 1 4(1 -β)   T -1 t=1 ηkt-1,t E ∥∇F (w t )∥ 2 + k∈[K] ηk,0 ∥∇F (w 0 )∥ 2   EF (ŷ T ) -F (w 0 ≤ E T -1 t=1 L(η kt-1,t ) 2 2(1 -β) 2 - ηkt-1,t 2(1 -β) ∥∇F (w t )∥ 2 + Lσ 2 2(1 -β) 2 T -1 t=1 (η kt-1,t ) 2 + ηLσ 2 (1 -β) 3   T -1 t=1 ηkt-1,t + k∈[K] ηk,0   + 1 4(1 -β)   T -1 t=1 ηkt-1,t E ∥∇F (w t )∥ 2 + k∈[K] ηk,0 ∥∇F (w 0 )∥ 2   +    L k∈[K] ηk,0 2 2(1 -β) 2 - k∈[K] ηk,0 1 -β    ∥∇F (w 0 )∥ 2 + Lσ 2 2(1 -β) 2 k∈[K] (η k,0 ) 2 ≤ T -1 t=1 E L(η kt-1,t ) 2 2(1 -β) 2 - ηkt-1,t 4(1 -β) ∥∇F (w t )∥ 2 +    L k∈[K] ηk,0 2 2(1 -β) 2 - k∈[K] ηk,0 4 (1 -β)    ∥∇F (w 0 )∥ 2 + 2ηLσ 2 (1 -β) 3   T -1 t=1 ηkt-1,t + k∈[K] ηk,0   ≤ - 1 8 (1 -β) E   T -1 t=1 ηkt-1,t ∥∇F (w t )∥ 2 + k∈[K] ηk,0 ∥∇F (w 0 )∥ 2   + 2ηLσ 2 (1 -β) 3   T -1 t=1 ηkt-1,t + k∈[K]ηk,0   Thus, we can get that1 T -1 t=0 ηt E T -1 t=0 ηt ∥∇F (w t )∥ 2 ≤ 8 (1 -β) (F (w 0 ) -F * ) T -1 t=0 ηt + 16ηLσ 2 (1 -β) 2 ,where η0 = k∈[K] ηk,0 and ηt = ηkt-1,t (t ≥ 1).Then, we analyse the lower bound ofT -1 t=0 ηt . It's easy to verify that τk,t+1 = τk,t + 1 k ̸ = k t , 1 = 1 + τk,t -τ t k = k t . Since k∈[K] τk,0 = 0, we have k∈[K] τk,T + T -1 t=0 τ t = KT . Moreover, τk T -1 ,T = T - ite(k T -1 , T ) = 0. We get that k∈[K],k̸ =k T -1 τk,T + T -1 t=0 τ t = KT . Thus, at least T 2 delays are smaller than 2K. T t=0 ηt = T -1 t=1 ηkt-1,t + k∈[K] ηk,0 ≥ T η 2 . 1 T -1 t=0 ηt T -1 t=0 ηt E ∥∇F (w t )∥ 2 ≤ 16(1 -β) T η (F ( ŵ0 ) -F * ) + 16ηLσ 2 (1 -β) 2 .If we choose an output wT according toEQUATIONwhere t ∈ [T ] and let η= min{ (1-β) 2 8KL , (1-β) 3 (F ŵ0)-F * ) T Lσ 2 }, we have that E ∥∇F ( wT )∥ 2 ≤ O Lσ 2 T + KL T .• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar the standard deviation or the standard error of the mean. • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in 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 is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: * **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.
* **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?
questions: 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?
* 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: limitations: .
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. The paper considers only scenarios with homogeneous data distributions, where the workers access to a shared dataset $\mathcal{D}$.
3. Assumption 1 includes a bounded gradient assumption, which is rather demanding.
4. 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.
questions: questions: 1. What is the impact of the size of the waiting set $\mathcal{C}$? How to choose the size of $\mathcal{C}$?
2. What are the key insights that the convergence can be guaranteed without bounded delay?
3. What is the complexity and cost in terms of the ordering of gradients?
limitations: limitations: The authors have partially addressed the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: * This paper studies asynchronous training algorithms but does not explore the effect of asynchronous delays on convergence.

* 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.
questions: 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.

2. 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?

3. 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?

4. The result of Lemma 4 in the main text is inconsistent with the proof in the Appendix.
limitations: limitations: Please refer to Weaknesses and Questions.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
3. 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.
questions: 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: limitations: N/A

Comments: title: Thanks for explanations
comparison to existing results
Thanks for responses
comment: We sincerely thank the reviewer for the willingness to increase the rating and the follow-up comments. Meanwhile, we would like to address the remaining concern below.

**Q: The paper integrates momentum into ASGD. Compared to vanilla ASGD [1], this paper requires stronger assumption, while not improving the convergence rate.**

+ We would like to first clarify that momentum is widely used in distributed machine learning and has a good performance in many practical applications. There are several existing works that integrate momentum into ASGD [2][3][4]. However, as far as we know, there is almost no convergence analysis of these methods in existing works. In view of this challenge, we introduce the ordered momentum to ASGD and present the method OrMo, which is theoretically proven to be convergent and empirically performs better than existing methods.
+ Although the analysis of ASGD for adaptive learning rates in [1] does not require the bounded gradient assumption, the analysis of ASGD for constant learning rates in [1] is based on the bounded gradient assumption. Therefore, the analyses in our work and in [1] for constant learning rates are under the same assumptions ($L$-Lipschitz smoothness, lower-bounded objective, and bounded gradient). 
+  As presented in Remark 6 at the end of Section 3, OrMo can also be used with adaptive learning rates. We have discussed this point in the general response, and will further explore it in future work. 

Given the reasons above, we carefully think that there are adequate theoretical contributions in our work. We hope that our response can address the reviewer's concern. Meanwhile, we would greatly appreciate it if the reviewer could re-evaluate our work based on our response.


[1] Mishchenko el al., Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays, NeurIPS 2022.

[2] Giladi et al., At stability’s edge: How to adjust hyperparameters to preserve minima selection in asynchronous training of neural networks?, ICLR 2020.

[3] Cohen et al., SMEGA2: distributed asynchronous deep neural network training with a single momentum buffer, ICPP 2022.

[4]  Mitliagkas et al., Asynchrony begets momentum, with an application to deep learning. In Proceedings of the Annual Allerton Conference on Communication, Control, and Computing, 2016.
I thank the authors for the response. 

The paper integrates momentum into ASGD. Compared to vanilla ASGD [1], this paper requires stronger assumption, while not improving the convergence rate. I am inclined to change my score to 4. As I have not carefully checked the technical details of the analysis, my confidence remains limited.

[1] Mishchenko el al., Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays, NeurIPS 2022.
Thank you for the response. We are grateful for your support of our work.
We greatly appreciate the insightful comments, which help us rethink our work. The additional results, the more "standard" presentation of convergence results, and the discussions will be included in the final version of the paper, as we promised. Thank you deeply for the support of our work.
I thank the authors for their rebuttals, and their thorough discussion of the points I raised. I hope the authors will include these additional experimental results, the more "standard" presentation of convergence results, as well as the discussions (especially the one about the difference with penalty function methods which I found particularly instructive) in their final version of the paper. Given that my concerns were answered, I raise my score.
We greatly appreciate the insightful follow-up comments, which helps us rethink about our work. We agree that OrMo can be considered as another type of staleness-control methods since the weights in OrMo are depended on the staleness. We will add the discussion in the final version and sincerely thank you for your support of our work.
Thanks for the efforts and explanations. As illustrated by authors, 
> In penalty function methods, gradients with larger delays are given smaller weights when updating the parameter. In OrMo, gradients with larger delays are given smaller weights when updating the momentum, but larger weights when updating the parameter. 

Thus, the main differences between the penalty and the OrMo is the updating object, i.e., parameter v.s. momentum. Inherently, the core idea is similar, as adjusting the weights according to the staleness. In light of this, I think the claim that the OrMo is not a staleness-control method is not appropriate. Maybe authors should reconsider this claim. Nevertheless, I appreciate the idea of integrating momentum into ASGD by sorting gradients based on iteration index. Thus, I'd like to keep the positive score.
Dear Area Chair,

We greatly appreciate your valuable time on our submission and the insightful comments, which make us rethink our method. We would like to briefly summarize the theoretical results in our work and then compare our results with those in existing works [1][2].

**Theoretical results in our work:**
In our submission, we propose an asynchronous momentum method called OrMo and give a theoretical analysis of the convergence rate of OrMo without relying on the maximum delay of the gradients. In Theorem $1$ of our submission, OrMo has the following convergence rate:
$$ \frac{1}{T}\sum_{t=1}^T \mathbb{E}\\|\nabla F({\bf w}_t)\\|^2\leq \mathcal{O} (\frac{\sigma}{\sqrt{T}}+ \frac{K^{\frac{2}{3}}}{T^{\frac{2}{3}}} + \frac{K}{T}), $$
where $T$ is the number of iterations and $K$ is the number of workers. Below, we will make a comparison between the theoretical convergence rate of OrMo and those of the existing works in [1][2]. 

**Comparison with [1]:**
[1] provides a theoretical analysis for vanilla asynchronous SGD (ASGD). As shown in Theorem $1$ and Corollary $2$ in [1], for smooth non-convex problems, ASGD has a convergence rate of $\frac{1}{T}\sum\_{t=1}^T \mathbb{E}\\|\nabla F({\bf w}\_t)\\|^2\leq \mathcal{O} (\frac{\sigma}{\sqrt{T}})$ when $T \geq \Omega(\tau_{max}^2)$. For OrMo, the same convergence rate can be achieved when $T \geq \Omega(K^4)$. 

Although the convergence rate are the same, our analysis is based on weaker assumptions since we do not assume a bounded delay. To the best of our knowledge, this is the first work to establish the convergence analysis of ASGD with momentum without relying on the bounded delay assumption. 

**Comparison with [2]:**
[2] proposes 1-bit Adam, which is a communication efficient momentum SGD algorithm pre-conditioned with Adam optimizer. As shown in Theorem $1$ and Corollary $1$ in [2], 1-bit Adam has the following convergence rate:
$$ \frac{1}{\tilde{T}}\sum_{t=1}^{\tilde{T}} \mathbb{E}\\|\nabla F({\bf w}_t)\\|^2\leq \mathcal{O} (\frac{\sigma}{\sqrt{K\tilde{T}}}+ \frac{1}{\tilde{T}^{\frac{2}{3}}} + \frac{1}{\tilde{T}}), $$
where $K$ is the number of workers and $\tilde{T}$ is the number of iteration. We notice that the server in 1-bit Adam needs to aggregate the information from all the $K$ workers at each iteration and every worker executes a gradient computation for each iteration. For fair comparison, we can rewrite the convergence rate of 1-bit Adam in terms of the number of gradient computations as $\mathcal{O} (\frac{\sigma}{\sqrt{C}}+ \frac{K^{\frac{2}{3}}}{C^{\frac{2}{3}}} + \frac{K}{C})$, where $C$ is the number of gradient computations and $C = K \tilde{T}$. At each iteration of OrMo, the server only needs one stochastic gradient. Thus, the convergence rate of OrMo in terms of the number of  gradient computations is $\mathcal{O} (\frac{\sigma}{\sqrt{C}}+ \frac{K^{\frac{2}{3}}}{C^{\frac{2}{3}}} + \frac{K}{C})$. We can find that OrMo and 1-bit Adam have the same convergence rate in terms of gradient computations. 

Meanwhile, we would like to clarify that although the two methods have the same convergence rate, the application scenarios of 1-bit Adam and OrMo are quite different. The communication compression technique in 1-bit Adam can greatly reduce the communication cost while the asynchronous updating technique in OrMo is mainly to reduce the synchronization overhead when the computing capabilities of workers are heterogeneous. Additionally, combining OrMo with the communication compression technique used 1-bit Adam can reduce its communication overhead, which can be considered in future work.

---

We sincerely thank you again for the valuable comments, which greatly help us improve our work. We promise that the discussion and the references [1][2] will be added in the final version.

[1] Lian et al., Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization. NeurIPS 2015.

[2] Tang et al., 1-bit Adam: Communication Efficient Large-Scale Training with Adam’s Convergence Speed. ICML 2021.
How is the theoretical convergence rate in this paper comparable to existing results such as

vanilla asynchronous SGD:
Asynchronous parallel stochastic gradient for nonconvex optimization.

momentum asynchronous SGD:
1-bit Adam: Communication Efficient Large-Scale Training with Adam’s Convergence Speed
We sincerely thank you for your timely response. We would like to answer the questions point by point as follows:

1. In the maintext of our submission, we have presented the empirical results of training a ResNet20 model on the CIFAR-10 dataset. More experimental results about ResNet20 are given in the response to Reviewer NjVh. 
Meanwhile, we promise to add the experimental results of training a Vision Transformer model on CIFAR-10 in our initial responses. The number of workers is set as $32$. The additional experiments are finished now. We would like to present the results below. Each experiment is repeated 3 times. 

    |Test Accuracy      |  (hom.)  | (het.)      |
    | -------|--------|---------|
    |ASGD             | 56.09\% $\pm$ 0.41\% | 56.33\% $\pm$  0.56\% | 
    |naive ASGDm      | 55.66\% $\pm$ 0.15\% | 55.74\% $\pm$  0.35\% | 
    |shifted momentum | 57.43\% $\pm$ 0.28\% | 57.39\% $\pm$  0.47\% |
    |SMEGA$^2$        | 60.54\% $\pm$ 0.05\% | 60.66\% $\pm$  0.12\% | 
    |OrMo             | **61.21\% $\pm$ 0.17\%** | **61.30\% $\pm$  0.11\%** | 


    We have also tested the performance of the OrMo method on the ResNet18 model, as you mentioned, over the past three days. Compared to the above Vision Transformer model which has about $0.5$ million parameters, ResNet18 has $10$ million parameters. OrMo achieves around 94% test accuracy on the ResNet18 model, as shown in the table below. Please note that while shifted momentum performs well in terms of final test accuracy, it converges more slowly than OrMo. Specifically, OrMo requires approximately 30 epochs to reach 85% test accuracy, whereas shifted momentum requires 60 epochs. Due to format constraints in the discussion period, we are unable to include figures in this response. We will provide more details (e.g., training curve figures) in the final version. These additional results are consistent with those in the main text and further support the conclusions of our work.

    |Test Accuracy      |  (hom.)  | (het.)      |
    | -------|--------|---------|
    |ASGD             | 91.45\% | 91.52\% | 
    |naive ASGDm      | 93.74\% | 93.10\% | 
    |shifted momentum | 94.02\% | 94.20\% |
    |SMEGA$^2$        | 93.72\% | 93.36\% | 
    |OrMo             | **94.32\%** | **94.26\%** | 

2. We sincerely thank you for the valuable comment, which makes us rethink about our method. We have provided a discussion about the differences between OrMo and existing penalty function methods in the general response, and we will add the discussion in the final version. Meanwhile, we would like to briefly summarize the differences between OrMo and existing methods that use a penalty function below.

    +  For penalty function methods, the key insight is to reduce the contribution of gradients with larger delays to the parameter update.
    For OrMo, the key insight 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. 

    + In penalty function methods, gradients with larger delays are given smaller weights when updating the parameter. 
    In OrMo, gradients with larger delays are given smaller weights when updating the momentum, but larger weights when updating the parameter. Both theoretical derivations and empirical ablation studies highlight the importance of giving larger weights to gradients with larger delays when updating the parameter

For more details, please refer to our general responses.

Thank you again for letting us know your remaining concerns. We are always willing to answer any further questions.
Thanks to the authors for their responses. I currently have no further questions.
I have two follow-up comments:
- 1. Why do you train ViT on CIFAR-10, instead of ResNet? The ResNet 18 trained with SGD momentum can obtain round 94% test accuracy, which should be the most standard baseline to compare optimizers with SGD momentum.
- 2. While the derivation of how to adjust the momentum is complex, the core of it is still like staleness control and a penalty function.