Stability and Generalization of Asynchronous SGD: Sharper Bounds Beyond Lipschitz and Smoothness

Authors: xiaoge  deng
tao  sun
shengwei  li
dongsheng  li
xicheng  lu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-08 04:56:06

Abstract: Asynchronous stochastic gradient descent (ASGD) has evolved into an indispensable optimization algorithm for training modern large-scale distributed machine learning tasks. Therefore, it is imperative to explore the generalization performance of the ASGD algorithm. However, the existing results are either pessimistic and vacuous or restricted by strict assumptions that fail to reveal the intrinsic impact of asynchronous training on generalization. In this study, we establish sharper stability and generalization bounds for ASGD under much weaker assumptions. Firstly, this paper studies the on-average model stability of ASGD and provides a non-vacuous upper bound on the generalization error, without relying on the Lipschitz assumption. Furthermore, we investigate the excess generalization error of the ASGD algorithm, revealing the effects of asynchronous delay, model initialization, number of training samples and iterations on generalization performance. Secondly, for the first time, this study explores the generalization performance of ASGD in the non-smooth case. We replace smoothness with the much weaker Hölder continuous assumption and achieve similar generalization results as in the smooth case. Finally, we validate our theoretical findings by training numerous machine learning models, including convex problems and non-convex tasks in computer vision and natural language processing.

Main paper: 
 introduction: 
 The last decade has witnessed explosive growth in the scale of models and datasets in the machine learning (ML) community [9, 12] . In light of this tendency, asynchronous distributed optimization has become crucial to ensure efficient training of large-scale ML models [4] . Specifically, the asynchronous stochastic gradient descent (ASGD) algorithm eliminates the synchronization barrier between the distributed training workers, enabling each worker to independently perform idle-free asynchronous gradient updates, thereby accelerating model training. Despite this asynchronous updating introduces delays that result in model inconsistency, the convergence of ASGD is still guaranteed under some mild assumptions [1, 26, 42, 40, 19, 44] .An intriguing observation is that ML models learned by stochastic gradient descent (SGD) [35] not only achieve zero training error but also demonstrate good generalization performance on unknown test datasets [52] . Generalizability is a classical topic in the statistical ML fields, and associated analytical techniques include VC dimension [46] , Rademacher complexity [20] , PAC-Bayesian [27] , uniform convergence [29, 31] , information-based, and compression-based bounds [3, 50] . In this paper, we are going to study generalizability in the sense of algorithmic stability [8] . This stabilitybased analytical framework allows bypassing the model dimensionality so that we can focus on exploring the generalization properties of optimization algorithms. Hardt et al. [17] investigated the generalization error of SGD on the basis of algorithmic uniform stability. Assuming that the loss function is convex, L-Lipschitz and β-smooth, and running SGD for K iterations with a learning rate η k < 2/β, they obtained an upper bound on the generalization error of O(L 2 K k=1 η k /n), where n represents the total number of training samples. In a recent work [23] , they proposed the on-average model stability and established a tighter generalization bound of O(1/n) for low-noise settings, without requiring the L-Lipschitz assumption.Research on the generalization of asynchronous stochastic gradient descent algorithms mainly concentrates on parsing the effect of asynchronous delay τ on algorithm stability and generalization. Leveraging the algorithmic uniform stability tool, Regatti et al. [33] presented an upper generalization error bound of O(L 2 K βτ /nβτ ) in the non-convex case, assuming L-Lipschitz, β-smooth functions, and a decreasing learning rate. However, empirical experiments [13] show that this bound is too loose to reflect the effect of asynchronous delay on algorithmic stability accurately. Deng et al. [13] directed their attention towards convex quadratic functions and established an upper bound on the generalization error as O((K-τ )/nτ ) by utilizing the algorithmic average stability [36] . This bound suggests that the introduced asynchronous delays can enhance algorithm stability, consequently improving its generalization performance under appropriate learning rates. Unfortunately, the analytical technique proposed in [13] is confined to quadratic optimizations.In this study, we delve deeper into the generalization performance of the ASGD algorithm. In particular, we utilize the on-average model stability tool to conduct a fine-grained analysis of the stability and generalization for ASGD under much weaker assumptions. Our contributions are summarized as follows.• Without relying on the Lipschitz assumption, this study establishes the on-average model stability of ASGD and provides an upper bound on the generalization error of O(1/τ + 1/ √ K). In contrast to existing work [13, 33] , our results are non-vacuous and applicable to the general convex case.• For the first time, we study the excess generalization error and provide an upper bound of O(1/τ + ∥w 1 -w * ∥ 2 /n) for ASGD. Our findings demonstrate that appropriately increasing the asynchronous delay, selecting a good initial model, and increasing the number of training samples can improve the generalization performance. • Under the much weaker (α, β)-Hölder continuous gradient assumption, we establish an excess generalization error bound of O(1/ √ τ +∥w 1 -w * ∥ 4α 1+α / √ n 1+α ), which reveals similar properties to the smooth case. To the best of our knowledge, this is the first study of the stability and generalization of ASGD in the non-smooth case.• We conduct comprehensive experiments using the ASGD algorithm, covering convex optimization problems and non-convex computer vision and natural language processing tasks. Empirical evidence confirms that appropriately increasing the asynchronous delay improves the algorithm stability and reduces the generalization error, which is consistent with our theoretical findings. 
related work: 
 Asynchronous training, with origins dating back at least to [6, 45] , has emerged as an essential distributed method for training modern large-scale ML tasks. It effectively addresses the synchronization bottleneck among multiple workers and mitigates the straggler problem inherent in distributed systems [4] . This study focuses on the stochastic gradient descent algorithm with asynchronous updates [1, 30] . Lian et al. [26] proved that ASGD has an asymptotic sublinear convergence rate in non-convex smooth optimization, which is consistent with SGD. Arjevani et al. [2] provided tight upper and lower complexity bounds for ASGD in convex quadratic optimization. These theoretical results were subsequently extended to general quasi-convex and non-convex settings [40] . It is noteworthy that the aforementioned theoretical analyses are based on bounded or fixed delay assumptions, whereas recent studies [11, 28] explored the performance of ASGD under arbitrary delays.A crucial aspect of asynchronous research revolves around the interaction between learning rates and delays. For one thing, most existing theoretical analyses require the learning rate to be inversely proportional to the asynchronous delay to guarantee the convergence of the ASGD algorithm [2, 26, 40] . For another, numerous studies opt for adaptive adjustments of the learning rate based on varying asynchronous delays to improve the convergence rate of ASGD [34, 38, 49, 53] . The dependence of learning rate on asynchronous delay also influences the stability and generalization studies of ASGD presented in this paper.Algorithm stability originated from perturbation analysis [7] , which measures the difference in the algorithm's output from changing a single input training sample. Generalization error refers to the performance disparity of the output model between training and testing datasets. Hence, algorithm stability is naturally connected to generalizability [8, 16, 36] . For the mainstream SGD algorithm, extensive stability-based studies have been conducted for convex, non-convex, smooth and non-smooth cases [5, 17, 22, 23, 32, 54] . Recently, algorithm stability analysis has been extended to distributed training scenarios [48] . Considerable research has explored the generalization performance of distributed decentralized SGD from the stability perspective [14, 43, 55] .However, the current generalization studies for ASGD remain inadequate. Building upon the algorithmic uniform stability, Regatti et al. [33] presented a pessimistic generalization error bound O(K τ /nτ ) of ASGD in the smooth non-convex case, where τ represents the maximum delay.In a recent development, Deng et al. [13] established a tighter upper generalization error bound of O((K -τ )/nτ ) using average stability, and Sun et al. [41] investigated a high-probability PAC-Bayesian generalization error bound O(1/ √ n) for ASGD. However, the theoretical analyses presented in [13, 41] only hold in quadratic optimization problems, limiting their applications. To the best of the authors' knowledge, existing generalization analyses of ASGD are either pessimistic and vacuous or constrained by strict assumptions. Therefore, the objective of this study is to establish sharper stability and generalization bounds for ASGD under much milder assumptions. Let X ⊆ R d and Y ⊆ R denote the input and output spaces, respectively. In this study, we focus on the general supervised learning problem in ML. This task involves training a model on a data set S = {z 1 , . . . , z n }, where each data point z i = (x i , y i ) ∈ Z = X × Y is independently and identically distributed (i.i.d.) sampled from an unknown distribution D. We evaluate the performance of model w on training sample z with a loss function f (w; z). The training process can be formalized as learning a model parameter w ∈ Ω ⊆ R d to minimize the empirical risk, denoted asEQUATIONSGD is the workhorse for solving the empirical risk minimization (ERM) problem (1) , which iteratively updates the model parameter byw k+1 = w k -η k ∇f (w k ; z i k ).ASGD is a powerful variant of SGD for distributed learning, which fully exploits the computational power of distributed clusters to accelerate the training process. In the distributed parameter server architecture [25] , the distributed workers are responsible for computing gradients, while the model updates occur on the parameter server side. Upon receiving the gradient from a worker, the server immediately utilizes it to update the model without waiting for gradient information from other workers. The ASGD procedure is described in Algorithm 1 (located in Appendix A.1). It is noteworthy that although ASGD avoids synchronization overhead, it introduces delays in model updating. To be specific, while worker m is computing and uploading the gradient, the model parameter on the server side may has already been updated by another worker m ′ . In essence, the model used for gradient computation on the worker is inconsistent with the model updated by the server. This characteristic renders ASGD a delayed gradient update, expressed asEQUATIONwhere w k , η k , τ k , and z i k denote the model parameter, learning rate, asynchronous delay, and training sample at the k-th iteration, respectively. It is worth noting that the index i k is chosen uniformly at random from the set {1, . . . , n}.For the model w learned through ASGD by minimizing the empirical risk (1) on the training data set S, people are more concerned with its performance on the unknown distribution D, i.e., the following popular riskEQUATIONThe empirical risk (1) and the popular risk (3) of a model are not the same, and the difference between them is referred to generalization error. More formally, denote the model learned by algorithm A on data set S as A(S), and its generalization error is defined asEQUATIONThe expectation here is taken over the randomness of the algorithm and the training data. This study is dedicated to bounding ϵ gen by algorithmic stability. LetS ′ = {z ′ 1 , .., z ′ n }, S (i) = {z 1 , .., z i-1 , z ′ i , z i+1 , .., z n }.(5) S ′ is also a data set i.i.d. sampled from the unknown distribution D, but is independent of the data set S = {z 1 , . . . , z n }. S (i) is a perturbed data set formed by replacing the i-th sample in S with z ′ i . Based on these notations, Lei and Ying [23] defined the following on-average model stability. Definition 1 (On-average model stability). A randomized algorithm A is on-average model ϵ stabstable ifE S,S ′ ,A 1 n n i=1 A(S) -A(S (i) ) 2 ≤ ϵ stab .Leveraging the smoothness (Definition 2) assumption, the connection between this algorithmic stability and the generalization error ϵ gen is established in the following lemma [Theorem 2, [23] ]. Lemma 1. Let γ > 0. Assume that the function w → f (w; z) is non-negative and β-smooth for any z ∈ Z. Then, if algorithm A is on-average model ϵ stab -stable, the generalization error satisfiesE S,A [F (A(S)) -F S (A(S))] ≤ β γ E S,A [F S (A(S))] + β + γ 2 ϵ stab .While the smooth function assumption is common in optimization and generalization analyses [13, 17, 33, 40] , it does impose constraints on the applicability [5] . For instance, the hinge loss, which is widely used in the ML fields, does not satisfy the smooth property. In this paper, therefore, we also investigate the stability of ASGD under the much weaker Hölder continuous gradient assumption (Definition 3), so as to establish broader and fine-grained generalization results. With the Hölder continuous condition, stability and generalization can be connected similarly to Lemma 1. Lemma 2 (Theorem 2, [23] ). Let γ > 0. For any z ∈ Z, the function w → f (w; z) is non-negative, convex, and the gradient ∇f (w; z) is (α, β)-Hölder continuous. If algorithm A is on-average model ϵ stab -stable, then the generalization error satisfiesE S,A [F (A(S)) -F S (A(S))] ≤ c 2 α,β 2γ E S,A [F 2α 1+α (A(S))] + γ 2 ϵ stab .Here, α ∈ [0, 1], and c α,β is a constant dependent on α, β.Furthermore, since the generalization performance of a model is primarily reflected in the popular risk (3) , this study also examines the excess generalization error, denoted as ϵ ex-gen , where w * ∈ argmin w∈Ω F (w) andϵ ex-gen := E S,A [F (A(S)) -F (w * )] . (6) Definition 2 (Smoothness). The function w → f (w; z) is β-smooth (β > 0) if for any z ∈ Z and w, v ∈ R d , ∥∇f (w; z) -∇f (v; z)∥ ≤ β∥w -v∥. Definition 3 (Hölder continuous). Let α ∈ [0, 1], β > 0. The function w → ∇f (w; z) is (α, β)- Hölder continuous if for any z ∈ Z and w, v ∈ R d , ∥∇f (w; z) -∇f (v; z)∥ ≤ β∥w -v∥ α .It is noteworthy that the (α, β)-Hölder continuous gradient is equivalent to a β-smooth function when α = 1. Whereas α = 0 implies that the function gradient is bounded, i.e., there exists a constant L > 0 such that ∥∇f (w; z)∥ ≤ L. Although many analyses of ASGD are grounded on the bounded gradient condition [26, 28, 33] , this assumption is somewhat unrealistic [24] . Notably, our analysis of the algorithm stability and the generalization error does not rely on the bounded gradient assumption. 
theory assumptions and proofs: 
 Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?• 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.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. Justification: In Appendix D, we have provided sufficient information on the computer resources needed to reproduce the experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or 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 as 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 or failed experiments that didn't make it into the paper). 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 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). 
stability and generalization bounds: 
 This section explores the stability and generalization of the ASGD algorithm in the context of smooth loss functions, and the proof is given in Appendix B. Firstly, we present the assumption required for this study. Assumption 1. The parameter space Ω ⊆ R d is a bounded convex set. Then, for any w, v ∈ Ω, there exists a constant r > 0 such that ∥w -v∥ ≤ r.Assumption 1 is standard in analyzing SGD and its variants, as it is easy to hold with the projection operator [5, 17, 23, 30, 43] . More specifically, we consider the following projected ASGD updatesEQUATION) Since the projection operator Π Ω is non-expansive, it has no impact on the stability and generalization analysis of the ASGD algorithm.Remark 1. Let w k and w (i)k denote the models produced by ASGD (7) after k iterations on the datasets S and S (i) (defined in ( 5)), respectively. According to Assumption 1, it follows that ∥w k -w(i) k ∥ ≤ r.Notably, this result is intuitively understandable as the datasets S, S (i) differ only by a single sample, and the initialization is the same (w 1 = w (i) 1 ). In contrast to a recent work [55] , where the authors assumed a normal distribution with bounded mean and variance for the difference between models w k and w (i) k , our study does not necessitate such a strong assumption.The stability-based analysis of SGD hinges significantly on the non-expansiveness of the gradient update operator [17, 23] . Namely, if function f is convex and smooth, then∀w, v ∈ Ω, z ∈ Z ∥w -η∇f (w; z) -(v -η∇f (v; z))∥ ≤ ∥w -v∥.However, this well-posed property is no longer applicable in the context of asynchronous gradient updates. To address this issue, we present the following critical lemma to bound the delayed gradient update operator. as the models produced by ASGD (7) with learning rates η k ≤ 2/β for k iterations on the datasets S and S (i) , respectively. Thenw k -η k ∇f (w k-τ k ; z i k )-w (i) k -η k ∇f (w (i) k-τ k ; z i k ) 2 ≤ w k -w (i) k 2 + 2η k β 2 r 2 τ k j=1 η k-j .By leveraging the properties established in Lemma 3, we can demonstrate an approximately nonexpansive recursive property for ∥w k+1 -w(i)k+1 ∥ 2 and subsequently establish the on-average model stability (Definition 1) of the ASGD algorithm as follows. Theorem 1 (Stability). Suppose the loss function is non-negative, convex, and β-smooth. Let Assumption 1 holds. If we run ASGD (7) with a non-increasing learning rate η k ≤ 1/2β for k iterations, then the on-average model stability satisfies (e is the natural constant)ϵ stab = 16βe(1 + k/n) n η 1 ∥w 1 -w * ∥ 2 + 4βr 2 + 2F (w * ) k l=1 η 2 l + 2β 2 r 2 e k l=1 η l τ l j=1 η l-j .In line with the findings of study [17] , increasing the number of training iterations impairs the stability of ASGD. Compared to SGD [23] , we introduce an additional term O( k l=1 η l τ l j=1 η l-j ) to characterize the effect of asynchronous delay on the stability of ASGD. Also similar to the datadependent stability study [22] , Theorem 1 indicates that model initialization affects the algorithmic stability, i.e., selecting a better model initiation point w 1 can effectively improve the stability.Together with Lemma 1 and Theorem 1, we can now present the generalization error (4) of the ASGD algorithm under smooth conditions. Theorem 2 (Generalization error). Let Assumption 1 holds, and assume that the loss function is nonnegative, convex, and β-smooth. Running ASGD (7) with a non-increasing learning rate η k ≤ 1/2β for K iterations, then the generalization error is given byϵ gen = O E S,A [F S (w K )]+ K k=1 η k τ k j=1 η k-j + 1+K/n n η 1 ∥w 1 -w * ∥ 2 + 1+F (w * ) K k=1 η 2 k .This finding suggests that both the model initialization and optimization processes have an impact on the generalization performance. In practical applications, one can reduce the generalization error by selecting a good initial model w 1 to start the training task. Additionally, it is crucial to finish the optimization process promptly since too many training iterations can detrimentally affect the generalization performance.Furthermore, Theorem 2 reveals a close relationship between the generalizability of ASGD and the learning rate. As discussed in Section 2, asynchronous training typically utilizes delay-inverse correlated learning rates to ensure algorithmic performance. In the low-noise case, namely, F (w * ) = 0, Stich and Karimireddy [40] demonstrated that F S (w K ) = O(1/ √ K) for ASGD under the conditions of smooth and general quasi-convex loss functions, with a learning rate of η k = c(τ√ K) -1 .Employing this learning rate strategy, the following corollary can be derived. Corollary 1. Let F (w * ) = 0, K ≍ n, and the conditions specified in Theorem 2 hold. If we set the learning rate η k = c(τ √ K) -1 with a constant c > 0 and τ = K k=1 τ k /K, then the generalization error satisfiesE S,A [F (w K ) -F S (w K )] = O 1 τ + 1 √ K .At this point, although the asynchronous training also introduces an additional generalization error term of O(1/τ ), increasing the delay can instead mitigate this detriment. Unlike previous ASGD generalization research [14, 33] , this study does not rely on the Lipschitz assumption. In contrast to the vacuous upper bound of O(K τ /nτ ) in [33] , we provide a sharper result and demonstrate that increasing the asynchronous delay reduces the generalization error. While Deng et al. [13] present a similar result O((K -τ )/nτ ) with respect to the maximum delay τ in the convex quadratic optimization, our bound holds in general convex settings. Furthermore, our results are associated with the average delay τ rather than the pessimistic maximum delay τ in [13, 14, 33] .According to definitions (4) and ( 6), the excess generalization error ϵ ex-gen can be decomposed asEQUATIONwhere the second term is known as the optimization error. The analysis of optimization error for ASGD usually requires the following bounded gradient assumption [26, 28, 33] . Assumption 2. The gradient w → ∇f (w; z) is bounded. That is, for any w ∈ Ω, z ∈ Z, there exists a constant L > 0 such that ∥∇f (w; z)∥ ≤ L. Remark 2. Assumption 2, also known as the Lipschitz condition, is used in the optimization analysis of ASGD to bound the model deviations induced by asynchronous delays, i.e., ∥w k -w k-τ k ∥ ≤ L τ k j=1 η k-j .For the excess generalization error of ASGD, we shift our focus to the average model wK := K k=1 η k w k / K k=1 η k .It is noteworthy that since the parameter space Ω is a convex set, w K ∈ Ω and is frequently considered as the output of the ASGD algorithm. We first present the optimization error with respect to this average model in the following lemma, followed by the excess generalization error theorem of ASGD. Lemma 4. Assuming that the loss function is non-negative, convex, and β-smooth. Let Assumptions 1 and 2 hold, if we run ASGD (7) with a non-increasing learning rate η k ≤ 1/2β, then the optimization error satisfiesE S,A [F S (w K )-F S (w * )] = O ∥w 1 -w * ∥ 2 K k=1 η k + 1+F (w * ) K k=1 η 2 k K k=1 η k + K k=1 η k τ k j=1 η k-j K k=1 η k .Theorem 3 (Excess generalization error). Let Assumptions 1, 2 hold, and assume that the loss function is non-negative, convex, and β-smooth. Running ASGD (7) with the non-increasing learning rate η k ≤ 1/2β for K iterations, then the excess generalization error isϵ ex-gen =O 1 + K k=1 η 2 k K k=1 η k F (w * ) + 1 + K/n n η 1 ∥w 1 -w * ∥ 2 + 1 + F (w * ) K k=1 η 2 k + ∥w 1 -w * ∥ 2 K k=1 η k + K k=1 η k η k + τ k j=1 η k-j + k l=1 η l τ l j=1 η l-j / K k=1 η k .Compared to the generalization error in Theorem 2, the excess generalization error is no longer explicitly dependent on the optimization error F S (w K ) and is more closely coupled to the learning rate. Considering the low-noise case F (w * ) = 0, which is common in modern deep learning, the following corollary can be further derived. Corollary 2. Let F (w * ) = 0, K ≍ n and the conditions in Theorem 3 hold. Set the learning rate asη k = c(τ √ K) -1 with a constant c > 0 and τ = K k=1 τ k /K. Then if τ ≤ K 1 4, the excess generalization error satisfiesE S,A [F (w K ) -F (w * )] = O 1 τ + ∥w 1 -w * ∥ 2 n .To the best of our knowledge, this is the first excess generalization error result for the ASGD algorithm. Compared to Corollary 1, this generalization bound with appropriate delays is sharper and no longer relies on the optimization error result in [40] . 
generalization in non-smooth case: 
 This section investigates the stability and generalization of the ASGD algorithm in the context of non-smooth cases. The analysis follows a similar technical roadmap as in Section 4. Firstly, we derive the stability of ASGD by leveraging the approximately non-expansive property of the delayed gradient update operators. Then, the generalization error is given in conjunction with Lemma 2. Subsequently, we analyze the optimization process of ASGD and present the excess generalization error for the non-smooth settings.However, without the smooth condition, the non-expansive property of asynchronous gradient updates is further compromised, and the optimization process also introduces additional errors. Under the much weaker Hölder continuous gradient assumption, We establish similar stability and generalizability results for ASGD as in the smooth case, which has not been explored in existing research. Please refer to Appendix C for the proof details of this section. Lemma 5. Let Assumption 1 holds, and assume that the loss function is non-negative, convex, and has a (α, β)-Hölder continuous gradient. Then, the delayed gradient update operator satisfiesw k -η k ∇f (w k-τ k ; z i k )-(w (i) k -η k ∇f (w (i) k-τ k ; z i k )) 2 = ∥w k -w (i) k ∥ 2 +O(η k τ k j=1 η k-j + η 2 1-α k ).Compared to Lemma 3, an additional term O(η2 1-α k) is introduced here to compensate for the absence of smoothness. Fortunately, since the coefficient of ∥w k -w (i) k ∥ 2 is not larger than 1, the delayed gradient update of ASGD remains approximately non-expansive at an appropriate learning rate. Leveraging this property, we are able to give the on-average model stability of ASGD in the non-smooth case. Theorem 4 (Stability). Suppose the loss function is non-negative, convex, and has a (α, β)-Hölder continuous gradient. Let Assumption 1 holds. Then, the on-average model stability of ASGD satisfiesϵ stab = O 1 + k/n n k l=1 η 2 l E S,A F 2α 1+α S (w l-τ l ) + k l=1 η l τ l j=1 η l-j + k l=1 η 2 1-α l .Theorem 4 shows that the algorithmic stability of ASGD not only depends on the learning rate, but is also closely related to the optimization process. Similar to [23] , we replace the gradient bound (Lipschitz constant) in the uniform stability [17] with the loss function value, which leads to sharper stability and generalizability results when combined with the subsequent optimization analysis. Substituting this algorithm stability into Lemma 2 yields the generalization error of the ASGD algorithm under the Hölder continuous condition (omitted in Appendix C.3). Remark 3. Although Assumption 1 and the smooth (or Hölder continuous) condition implies Lipschitz continuity, our point is to replace the upper gradient bound with function value, thereby establishing sharper stability and generalization bounds that do not depend on the Lipschitz constant.Subsequently, we present the optimization error of ASGD in the non-smooth case, and the excess generalization error is followed by the decomposition (8) . Lemma 6. Assuming that the loss function is non-negative, convex, and has a (α, β)-Hölder continuous gradient. Let Assumptions 1 and 2 hold, then the optimization error of ASGD (7) with a non-increasing learning rate satisfiesE S,A [F S (w K )-F S (w * )] = O ∥w 1 -w * ∥ 2 + K k=1 η k τ k j=1 η α k-j K k=1 η k + K k=1 η 2 k 1-α 1+α K k=1 η k η 1 ∥w 1 -w * ∥ 2 + 1 + F (w * ) K k=1 η 2 k + K k=1 η 3-α 1-α k 2α 1+α.Theorem 5 (Excess generalization error). Let Assumptions 1, 2 hold, and assume that the loss function is non-negative, convex, and has a (α, β)-Hölder continuous gradient. Running ASGD (7) with the learning rateη k = c(τ √ K) -1 for K ≍ n iterations, then if F (w * ) = 0 and the average delay satisfies τ ≤ K α ′ with α ′ = min{ 1 3 , α 3-2α }, the excess generalization error is E S,A [F (w K ) -F (w * )] = O 1 √ τ + ∥w 1 -w * ∥ 4α 1+α √ n 1+α .Notably, the generalization performance decreases in the non-smooth case, but the underlying properties remain consistent with the smooth setting (Corollary 2). That is, the generalization performance can be improved by choosing a good initial model, increasing the number of training samples, and appropriately adjusting the asynchronous delays. Additionally, when there is no asynchronous delay in the training system, the first term in Theorem 5 vanishes, yielding an excess generalization error bound of O(1/ √ n 1+α ). This outcome is consistent with the findings from the study of the SGD algorithm in [23] , but without requiring more computation K ≍ n 2 1+α . 
experimental validation: 
 In this section, we extensively evaluated various machine learning tasks under the distributed parameter server architecture to investigate the practical stability and generalization performance of ASGD. Our experiments included convex optimization problems as well as non-convex computer vision (CV) and natural language processing (NLP) tasks. We simulated a distributed system with M = 16 workers and performed asynchronous training in a more general stochastic gradient descent format as followsEQUATIONHere, M k is a non-empty subset of {1, . . . , M } containing the workers that participated in asynchronous training at the k-th iteration, and g m k-τ k represents the delayed gradient computed by worker m on model w k-τ k . Our experiments also focus on parsing the impact of asynchronous delays on algorithmic stability and generalization. Following our theoretical findings, we set the learning rate to 0.1/τ for different delays, where τ denotes the average delay.For the convex optimization problem, we employed a single-layer linear network with the mean squared error for a classification task on the RCV1 data set from the LIBSVM database [10] . This data set contains 20, 242 training data with 47, 236 features per sample. In the field of computer vision, we chose the popular ResNet18 model for image classification on the CIFAR10 and CIFAR100 datasets. ResNet [18] , a convolutional neural network with residual modules and shortcut connections, has demonstrated remarkable performance across various CV tasks. CIFAR10 and CIFAR100 [21] are widely used image datasets, both containing 60, 000 color images of 32 × 32 pixels. For natural language processing tasks, we conducted experiments using BERT on the SST-2 task within the GLUE platform [47] . BERT [15] is a pre-trained language model based on the Transformer architecture, known for its impressive performance in handling various NLP tasks. The SST-2 [37] task in the GLUE evaluation benchmark comprises a total of 67, 350 training samples for single-sentence categorization.Due to computational resource limitations, this experiment cannot sequentially replace a single sample to train n models and calculate the on-average model stability (Definition 1). Instead, we construct a perturbed data set S (i) by randomly removing a sample from the data set S, and then train on the two datasets separately to record the model difference ∥A(S) -A(S (i) )∥ 2 . Repeating the process multiple times, we take the average value to approximate the algorithmic stability. As for the generalization error (4), it is directly approximated by the absolute difference between the training error and the testing error of the model. Conversely, when training with a learning rate that is inversely correlated with the asynchronous delay, an appropriate increase in the delay improves the algorithm stability and thus reduces the generalization error. This observation is in consistent with the theoretical bound in Corollary 1, which utilizes the specific learning rate η k = c/τ . 
concluding remarks: 
 This study establishes sharper and broader stability and generalization bounds for ASGD under much weaker assumptions. We provide upper bounds for the on-average model stability and generalization error of ASGD without relying on the Lipschitz continuous condition. Moreover, for the first time, we study the stability and generalizability of ASGD in the non-smooth setting. Our generalization results are non-vacuous and applicable to the general convex case. Furthermore, we validate our theoretical findings with experiments on various machine learning tasks.We also conducted experiments using delay-independent learning rates (Figures 3 and 4 send w back to worker m 9: end if Output: model w It is noteworthy that although ASGD avoids synchronization overhead, it introduces delays in model updating. To be specific, while worker m is computing and uploading the gradient, the model parameter on the server side may has already been updated by another worker m ′ . In essence, the model used for gradient computation on the worker (w in line 3 of Algorithm 1) is inconsistent with the model updated by the server (w in line 7 of Algorithm 1). This characteristic renders ASGD a delayed gradient update, expressed asw k+1 = w k -η k ∇f (w k-τ k ; z i k ),where w k , η k , τ k , and z i k denote the model parameter, learning rate, asynchronous delay, and training sample at the k-th iteration, respectively. It is worth noting that the index i k is chosen uniformly at random from the set {1, . . . , n}.Our analysis frequently uses the following inequalities. Lemma A.1 (Young's inequality). If p > 1 and q > 1 are real numbers such that1 p + 1 q = 1, then for any a, b ∈ R + , ab ≤ 1 p a p + 1 q b q . (A.1)Lemma A.2 (Cauchy-Schwarz inequality). For any w, v ∈ R d , the following inequality holds.Lemma A.3. Let p > 0. For any a, b ∈ R + , the following inequalities hold.2ab ≤ pa 2 + 1 p b 2 , (A.3) (a + b) 2 ≤ (1 + p)a 2 + (1 + 1 p )b 2 . (A.4)In addition, we rely on the self-bounding properties of the smooth and Hölder continuous gradient functions. The proof can be found in [24, 39, 51] . Lemma A.4. If the function w → f (w; z) is non-negative and the gradient ∇f is (α, β)-Hölder continuous (Definition 3) with α ∈ [0, 1], β > 0. Then for any w, z, we have∥∇f (w; z)∥ ≤ c α,β f α 1+α (w; z), (A.5)where the constant c α,β is defied asc α,β := (1 + 1/α) α 1+α β 1 1+α , if α > 0 sup z ∥∇f (0; z)∥ + β, if α = 0 (A.6)Remark A.1. The case α = 1 implies that the function w → f (w; z) is β-smooth (Definition 2). At this point, the constant c α,β = √ 2β, and the gradient satisfies∥∇f (w; z)∥ 2 ≤ 2βf (w; z). (A.7)Lemma A.5. The projection operator is defined as Π Ω (v) = argmin w∈Ω ∥w-v∥, and this operator is non-expansive, i.e.,∥Π Ω (w) -Π Ω (v)∥ ≤ ∥w -v∥, ∀w, v ∈ R d and ∥Π Ω (v) -w∥ ≤ ∥v -w∥, ∀v ∈ R d , w ∈ Ω. (A.8)The proof of Lemma A.5 can be found in [56] . This non-expansive property not only ensures the plausibility of Assumption 1, but also facilitates the stability and generalization analysis of the projected ASGD algorithm (7) , making it no inherently different from the standard ASGD (2).A.3 Proof of Lemma 1 and Lemma 2 (Section 3 in the main text)Lemma 1 and Lemma 2 were established by Lei et al. [Theorem 2, [23] ]. The following proof is derived from [Appendix B, [23] ]. Recall the following definitionsEQUATIONF (w) = E z∼D [f (w; z)], F S (w) = 1 n n i=1 f (w; z i ), ϵ gen := E S,A [F (A(S)) -F S (A(S))] .(A.9) Since for any i, the data samples z i and z ′ i are both drawn i.i.d. from D, then A(S (i) ) is independent of z i and we have the following factE S [F (A(S))] = E S,S ′ [f (A(S (i) ); z i )] = 1 n n i=1 E S,S ′ [f (A(S (i) ); z i )].Hence, the generalization error satisfiesϵ gen = E S,A [F (A(S)) -F S (A(S))] = E S,A E S ′ [f (A(S (i) ); z i )] - 1 n n i=1 f (A(S); z i ) = 1 n n i=1 E S,S ′ ,A f (A(S (i) ); z i ) -f (A(S); z i ) . (A.10)By incorporating the β-smoothness property of the function w → f (w; z), we haveE S,A [F (A(S))-F S (A(S))] ≤ 1 n n i=1 E S,S ′ ,A A(S (i) )-A(S), ∇f (A(S); z i ) + β 2 ∥A(S (i) )-A(S)∥ 2 .(A.11) Using the inequalities (A.2), (A.3) and self-bounding property (A.7), let γ > 0 then we know thatA(S (i) ) -A(S), ∇f (A(S); z i ) ≤ ∥A(S (i) ) -A(S)∥∥∇f (A(S); z i )∥ ≤ γ 2 ∥A(S (i) ) -A(S)∥ 2 + 1 2γ ∥∇f (A(S); z i )∥ 2 ≤ γ 2 ∥A(S (i) ) -A(S)∥ 2 + β γ f (A(S); z i ).Substituting back into inequality (A.11) yieldsE S,A [F (A(S))-F S (A(S))] ≤ β γ E S,A 1 n n i=1 f (A(S); z i ) + β +γ 2 E S,S ′ ,A 1 n n i=1 ∥A(S)-A(S (i) )∥ 2 .By further combining with (A.9) and Definition 1, Lemma 1 is thus derived, i.e.,E S,A [F (A(S)) -F S (A(S))] ≤ β γ E S,A [F S (A(S))] + β + γ 2 ϵ stab . (A.12)Without the smoothness assumption, we then need to utilize the convexity property of the function w → f (w; z), i.e.,f (A(S (i) ); z i ) -f (A(S); z i ) ≤ A(S (i) ) -A(S), ∇f (A(S (i) ); z i ) ≤ γ 2 ∥A(S (i) ) -A(S)∥ 2 + 1 2γ ∥∇f (A(S (i) ); z i )∥ 2 ≤ γ 2 ∥A(S (i) ) -A(S)∥ 2 + c 2 α,β 2γ f 2α 1+α (A(S (i) ); z i ),where the last two inequalities use (A.2), (A.3) and the self-bounding property (A.5). Substituting it back into inequality (A.10) leads to Lemma 2, i.e.,E S,A [F (A(S)) -F S (A(S))] ≤ c 2 α,β 2γ 1 n n i=1 E S,S ′ ,A f 2α 1+α (A(S (i) ); z i ) + γ 2 E S,S ′ ,A 1 n n i=1 ∥A(S) -A(S (i) )∥ 2 ≤ c 2 α,β 2γ E S,A [F 2α 1+α (A(S))] + γ 2 ϵ stab . (A.13)Here we use the concavity of the map x → x 2α 1+α and the following factE S,S ′ ,A f 2α 1+α (A(S (i) ); z i ) ≤ E S,S ′ ,A E zi f (A(S (i) ); z i ) 2α 1+α = E S,S ′ ,A F 2α 1+α (A(S (i) )) = E S,A F 2α 1+α (A(S)) .B Proof of Stability and Generalization Bounds (Section 4 in the main text)B.1 Proof of Lemma 3 (approximately non-expansive property of delayed gradient updates)Due to that the function w → f (w; z) is convex and β-smooth, the gradient ∇f is co-coercive, namelyw k-τ k -w (i) k-τ k , ∇f (w k-τ k ; z i k )-∇f (w (i) k-τ k ; z i k ) ≥ 1 β ∥∇f (w k-τ k ; z i k )-∇f (w (i) k-τ k ; z i k )∥ 2 .Using this co-coercivity with learning rate η k ≤ 2/β, we havew k -η k ∇f (w k-τ k ; z i k ) -w (i) k -η k ∇f (w (i) k-τ k ; z i k ) 2 = ∥w k -w (i) k ∥ 2 + η 2 k ∥∇f (w k-τ k ; z i k ) -∇f (w (i) k-τ k ; z i k )∥ 2 -2η k ⟨w k -w (i) k , ∇f (w k-τ k ; z i k ) -∇f (w (i) k-τ k ; z i k )⟩ = ∥w k -w (i) k ∥ 2 + η 2 k ∥∇f (w k-τ k ; z i k ) -∇f (w (i) k-τ k ; z i k )∥ 2 -2η k ⟨w k-τ k -w (i) k-τ k , ∇f (w k-τ k ; z i k ) -∇f (w (i) k-τ k ; z i k )⟩ -2η k ⟨w k -w k-τ k -(w (i) k -w (i) k-τ k ), ∇f (w k-τ k ; z i k ) -∇f (w (i) k-τ k ; z i k )⟩ ≤ ∥w k -w (i) k ∥ 2 -2η k ⟨w k -w k-τ k -(w (i) k -w (i) k-τ k ), ∇f (w k-τ k ; z i k ) -∇f (w (i) k-τ k ; z i k )⟩.From the iterative scheme of ASGD (7) , we know that⟨w k -w k-τ k -(w (i) k -w (i) k-τ k ), ∇f (w k-τ k ; z i k ) -∇f (w (i) k-τ k ; z i k )⟩ = τ k j=1 ⟨w k-j+1 -w k-j -(w (i) k-j+1 -w (i) k-j ), ∇f (w k-τ k ; z i k ) -∇f (w (i) k-τ k ; z i k )⟩ ≤ τ k j=1 η k-j ∥∇f (w k-j-τ k-j ; z i k-j )-∇f (w (i) k-j-τ k-j ; z i k-j )∥∥∇f (w k-τ k ; z i k )-∇f (w (i) k-τ k ; z i k )∥, (B.1)where the last inequality is due to (A.2) and (A.8). Following the β-smooth property and Assumption 1, we can derive ∥∇f (w s-τs ; z is )-∇f (w(i) s-τs ; z is )∥ ≤ β∥w s-τs -w (i) s-τs ∥ ≤ βr, for s = k, k -j; j = 1, . . . , τ k . (B.2)With inequalities (B.1) and (B.2), we are arrive atw k -η k ∇f (w k-τ k ; z i k )-w (i) k -η k ∇f (w (i) k-τ k ; z i k ) 2 ≤ w k -w (i) k 2 +2η k β 2 r 2 τ k j=1 η k-j . (B.3)B.2 Proof of Theorem 1 (algorithm stability under the smooth assumption)Let w k and w(i)k denote the models produced by ASGD (7) after k iterations on the datasets S and S (i) , respectively. Given that the index i k at the k-th iteration is chosen randomly from the set {1, 2, . . . , n}, there is a probability of 1 -1/n that i k ̸ = i. Then, by the approximately non-expansive property (B.3) of the ASGD iteration and (A.8), we have∥w k+1 -w (i) k+1 ∥ 2 ≤ w k -η k ∇f (w k-τ k ; z i k ) -w (i) k -η k ∇f (w (i) k-τ k ; z i k ) 2 ≤ ∥w k -w (i) k ∥ 2 + 2η k β 2 r 2 τ k j=1 η k-j .On the other hand, there is a probability of 1/n such that the algorithm accurately selects the i-th sample point (i k = i) that is different in the two datasets S and S (i) . In this case, we can perform the following analysis based on the inequality (A.4) with p > 0, self-bounding property (A.7) and non-expansive projection (A.8)∥w k+1 -w (i) k+1 ∥ 2 ≤ ∥w k -η k ∇f (w k-τ k ; z i ) -w (i) k + η k ∇f (w (i) k-τ k ; z ′ i )∥ 2 ≤ (1 + p)∥w k -w (i) k ∥ 2 + (1 + 1/p)η 2 k ∥∇f (w k-τ k ; z i ) -∇f (w (i) k-τ k ; z ′ i )∥ 2 ≤ (1 + p)∥w k -w (i) k ∥ 2 + 2(1 + 1/p)η 2 k ∥∇f (w k-τ k ; z i )∥ 2 + ∥∇f (w (i) k-τ k ; z ′ i )∥ 2 ≤ (1 + p)∥w k -w (i) k ∥ 2 + 4β(1 + 1/p)η 2 k f (w k-τ k ; z i ) + f (w (i) k-τ k ; z ′ i ) .Combining the two cases above and taking the expectation with respect to the randomness of the algorithm yieldsE A ∥w k+1 -w (i) k+1 ∥ 2 ≤(1 + p n )E A ∥w k -w (i) k ∥ 2 + 2η k β 2 r 2 (n -1) n τ k j=1 η k-j + 4β(1 + 1/p)η 2 k n E A f (w k-τ k ; z i ) + f (w (i) k-τ k ; z ′ i ) .Since z i and z ′ i are i.i.d. sampled from the same distribution D, we have the following factE S,S ′ ,A [f (w (i) k-τ k ; z ′ i )] = E S,A [f (w k-τ k ; z i )].A subsequent expectation over the randomness of data producesE S,S ′ ,A ∥w k+1 -w (i) k+1 ∥ 2 ≤ (1 + p n )E S,S ′ ,A ∥w k -w (i) k ∥ 2 + 8β(1 + 1/p)η 2 k n E S,A [f (w k-τ k ; z i )] + 2η k β 2 r 2 τ k j=1 η k-j ≤ k l=1 (1 + p n ) (k-l)   8β(1 + 1/p)η 2 l n E S,A [f (w l-τ l ; z i )] + 2η l β 2 r 2 τ l j=1 η l-j   ,where the second inequality is due to the same initializationw 1 = w (i) 1 . Let p = n/k, then (1 + p/n) (k-1) ≤ e (where e is the natural constant), and the on-average model stability of ASGD satisfiesE S,S ′ ,A 1 n n i=1 ∥w k+1 -w (i) k+1 ∥ 2 ≤ k l=1 (1 + p n ) (k-l) 8β(1 + 1/p)η 2 l n E S,A [F S (w l-τ l )] + 2η l β 2 r 2 τ l j=1 η l-j ≤ (1 + p n ) (k-1) 8β(1 + 1/p) n k l=1 η 2 l E S,A F S (w l-τ l ) + 2β 2 r 2 k l=1 η l τ l j=1 η l-j ≤ 8βe(1 + k/n) n k l=1 η 2 l E S,A [F S (w l-τ l )] + 2β 2 r 2 e k l=1 η l τ l j=1 η l-j . (B.4)For the further investigation of the algorithm stability of ASGD, it is imperative to bound errork l=1 η 2 l E S,A [F S (w l-τ l )] of the delayed model. With the ASGD update (7) , inequality (A.8), convexity and smooth property (A.7), we have the following derivation∥w k+1 -w * ∥ 2 ≤ ∥w k -η k ∇f (w k-τ k ; z i k ) -w * ∥ 2 = ∥w k -w * ∥ 2 + η 2 k ∥∇f (w k-τ k ; z i k )∥ 2 + 2η k ⟨w * -w k , ∇f (w k-τ k ; z i k )⟩ ≤ ∥w k -w * ∥ 2 + 2βη 2 k f (w k-τ k ; z i k ) + 2η k ⟨w * -w k-τ k , ∇f (w k-τ k ; z i k )⟩ + 2η k ⟨w k-τ k -w k , ∇f (w k-τ k ; z i k )⟩ ≤ ∥w k -w * ∥ 2 + 2βη 2 k f (w k-τ k ; z i k ) + 2η k (f (w * ; z i k ) -f (w k-τ k ; z i k )) + 2η k ⟨w k-τ k -w k , ∇f (w k-τ k ; z i k )⟩ ≤ ∥w k -w * ∥ 2 -η k f (w k-τ k ; z i k ) + 2η k f (w * ; z i k ) + 2η k ⟨w k-τ k -w k , ∇f (w k-τ k ; z i k )⟩,where w * ∈ argmin w∈Ω F (w), and the last inequality is due to η k ≤ 1/2β. Thenη k f (w k-τ k ; z i k ) ≤∥w k -w * ∥ 2 -∥w k+1 -w * ∥ 2 + 2η k f (w * ; z i k ) + 2η k ⟨w k-τ k -w k , ∇f (w k-τ k ; z i k )⟩. (B.5)Following the inequality (A.2), self-bounding property (A.7), and Assumption 1, we know that2η k ⟨w k-τ k -w k , ∇f (w k-τ k ; z i k )⟩ ≤ 2rη k ∥∇f (w k-τ k ; z i k )∥ ≤ 2rη k 2βf (w k-τ k ; z i k ) ≤ 2r 2βη k • η k f (w k-τ k ; z i k ) ≤ 4βr 2 η k + η k 2 f (w k-τ k ; z i k ),where last inequality uses (A.3) with p = 1. Turning to (B.5), we haveη k f (w k-τ k ; z i k ) ≤ 2∥w k -w * ∥ 2 -2∥w k+1 -w * ∥ 2 + 4η k f (w * ; z i k ) + 8βr 2 η k .Multiplying both sides with the non-increasing learning rate, we getη 2 k f (w k-τ k ; z i k ) ≤ 2η k ∥w k -w * ∥ 2 -2η k+1 ∥w k+1 -w * ∥ 2 + 4η 2 k f (w * ; z i k ) + 8βr 2 η 2 k .Taking an expectation on both sides followed by a summation leads tok l=1 η 2 l E S,A [F S (w l-τ l )] ≤ 2η 1 ∥w 1 -w * ∥ 2 + 4 k l=1 η 2 l F (w * ) + 8βr 2 k l=1 η 2 l , (B.6)where we useE S [f (w * ; z i k )] = E S [F S (w * )] = F (w *). Substituting (B.6) into (B.4), we are arrive atE S,S ′ ,A 1 n n i=1 w k+1 -w (i) k+1 2 ≤ 16βe(1 + k/n) n η 1 ∥w 1 -w * ∥ 2 + 2 k l=1 η 2 l F (w * ) + 4βr 2 k l=1 η 2 l + 2β 2 r 2 e k l=1 η l τ l j=1 η l-j .(B.7)Together with Lemma 1 (A.12) and Theorem 1 (B.7), we haveE S,A [F (w k+1 ) -F S (w k+1 )] ≤ β γ E S,A [F S (w k+1 )] + β + γ 2 E S,S ′ ,A 1 n n i=1 ∥w k+1 -w (i) k+1 ∥ 2 ≤ β γ E S,A [F S (w k+1 )] + 8βe(β + γ)(1 + k/n) n η 1 ∥w 1 -w * ∥ 2 + 2 k l=1 η 2 l F (w * ) + 4βr 2 k l=1 η 2 l + β 2 r 2 (β + γ)e k l=1 η l τ l j=1 η l-j . (B.8)Let γ = 1, then the generalization error ϵ gen of ASGD satisfiesE S,A [F (w K ) -F S (w K )] = O E S,A [F S (w K )] + K k=1 η k τ k j=1 η k-j + 1+K/n n η 1 ∥w 1 -w * ∥ 2 + 1 + F (w * ) K k=1 η 2 k . (B.9)B.4 Proof of Corollary 1 (generalization error with specific learning rates)Let K ≍ n. Following Theorem 2 (B.9), if we use the delay-independent constant learning rate η k ≡ η, the generalization error ϵ gen satisfiesE S,A [F (w K ) -F S (w K )] = O K k=1 τ k + ∥w 1 -w * ∥ 2 n + E S,A F S (w K ) + F (w * ) . (B.10)In comparison to SGD [23] , asynchronous training with a fixed learning rate η introduces an additional error O( K k=1 τ k ) due to delay. This error accumulates as iterations increase, which subsequently deteriorates the generalization performance of ASGD. However, the experimental results in Appendix D demonstrate that the generalization error bound in (B.10) is pessimistic.In the low-noise case, i.e., F (w * ) = 0, Stich and Karimireddy [40] proved that F S (w K ) = O(1/ √ K) under the smooth and general quasi-convex loss function conditions with the learning rateη k = c(τ √ K) -1 (c > 0 is a constant, τ = K k=1 τ k /K).At this point, the generalization error of ASGD isE S,A [F (w K ) -F S (w K )] = O 1 √ K + O 1 + K/n n c∥w 1 -w * ∥ 2 τ √ K + c 2 τ 2 + c 2 Kτ 2 K k=1 τ k = O 1 τ + 1 √ K .Remark B.1. Under the assumptions of β-smoothness and (M, σ 2 )-bounded noise, Stich and Karimireddy [40] proved that F S (wK ) = O(1/ √ K)when the learning rate is chosen as η k ≤ 1 10β(τ +M ) . In the above proof, we can flexibly adjust the constant c to make the learning rate satisfy the requirements of the study [40] , enabling the safe utilization of its optimization results. Remark B.2. The notation O hides the numerical values and specific fixed constants, such as c, e, β, and r. This notation facilitates the reader's comprehension by allowing for an intuitive understanding of the effects of important variables such as asynchronous delay τ , the number of iterations K, and the amount of training data n on stability and generalization.By the ASGD update (7) , convexity, smooth property (A.7) and the non-expansive projection (A.8), we can derive∥w k+1 -w * ∥ 2 ≤ ∥w k -η k ∇f (w k-τ k ; z i k ) -w * ∥ 2 = ∥w k -w * ∥ 2 + η 2 k ∥∇f (w k-τ k ; z i k )∥ 2 + 2η k ⟨w * -w k , ∇f (w k-τ k ; z i k )⟩ ≤ ∥w k -w * ∥ 2 + 2βη 2 k f (w k-τ k ; z i k ) + 2η k ⟨w * -w k , ∇f (w k ; z i k )⟩ + 2η k ⟨w * -w k , ∇f (w k-τ k ; z i k ) -∇f (w k ; z i k )⟩ ≤ ∥w k -w * ∥ 2 + 2βη 2 k f (w k-τ k ; z i k ) + 2η k (f (w * ; z i k ) -f (w k ; z i k )) + 2βη k ∥w k -w * ∥ • ∥w k -w k-τ k ∥. (B.11)From the iterative scheme of ASGD ( 7) and (A.8), we know that∥w k -w k-τ k ∥ ≤ τ k j=1 ∥w k-j+1 -w k-j ∥ ≤ τ k j=1 η k-j ∥∇f (w k-j-τ k-j ; z i k-j )∥.(B.12)Then taking an expectation on both sides of (B.11) and combing with Assumptions 1 and 2, we have2η k E S,A [F S (w k ) -F S (w * )] ≤ E S,A ∥w k -w * ∥ 2 -E S,A ∥w k+1 -w * ∥ 2 + 2βη 2 k E S,A [F S (w k-τ k )] + 2βLrη k τ k j=1 η k-j .Subsequently a summation of the inequality produces2 K k=1 η k E S,A [F S (w k )-F S (w * )] ≤ ∥w 1 -w * ∥ 2 +2β K k=1 η 2 k E S,A [F S (w k-τ k )]+2βLr K k=1 η k τ k j=1 η k-j .Leveraging the optimization bound (B.6) with η k ≤ 1/2β, we can deriveK k=1 η k E S,A [F S (w k )-F S (w * )] ≤ 1 2 ∥w 1 -w * ∥ 2 +β K k=1 η 2 k E S,A [F S (w k-τ k )]+βLr K k=1 η k τ k j=1 η k-j ≤ ( 1 2 + 2βη 1 )∥w 1 -w * ∥ 2 + 4β K k=1 η 2 k F (w * ) + 8β 2 r 2 K k=1 η 2 k + βLr K k=1 η k τ k j=1 η k-j . (B.13)Let the average modelw K := K k=1 η k w k K k=1 η k ∈ Ω.Following the convexity of the function F S , we know thatE S,A [F S (w K ) -F S (w * )] ≤ K k=1 η k E S,A [F S (w k ) -F S (w * )] K k=1 η k ≤ ( 1 2 + 2βη 1 ) ∥w 1 -w * ∥ 2 K k=1 η k + 4β F (w * ) + 2βr 2 K k=1 η 2 k K k=1 η k + βLr K k=1 η k τ k j=1 η k-j K k=1 η k .Multiplying both sides of the generalization error (B.8) by η k+1 followed with a summation givesK k=1 η k E S,A [F (w k )] ≤ (1 + β γ ) K k=1 η k E S,A [F S (w k )] + β 2 r 2 (β + γ)e K k=1 η k k l=1 η l τ l j=1 η l-j + 8βe(β + γ) n K k=1 η k (1 + k n ) η 1 ∥w 1 -w * ∥ 2 + 2 k l=1 η 2 l F (w * ) + 4βr 2 k l=1 η 2 l . (B.14)Substituting the optimization error (B.13) into the above inequality (B.14), we haveK k=1 η k E S,A [F (w k ) -F (w * )] ≤ β 2 r 2 (β + γ)e K k=1 η k k l=1 η l τ l j=1 η l-j + β γ K k=1 η k F (w * ) + (1 + β γ )   ( 1 2 + 2βη 1 )∥w 1 -w * ∥ 2 + 4β K k=1 η 2 k F (w * ) + 8β 2 r 2 K k=1 η 2 k + βLr K k=1 η k τ k j=1 η k-j   + 8βe(β + γ) n K k=1 η k (1 + k n ) η 1 ∥w 1 -w * ∥ 2 + 2 k l=1 η 2 l F (w * ) + 4βr 2 k l=1 η 2 l .Utilizing the convexity property of the function F , we can deriveE S,A [F (w K ) -F (w * )] ≤ K k=1 η k E S,A [F (w k ) -F (w * )] K k=1 η k ≤ 1 + β/γ K k=1 η k   ( 1 2 + 2βη 1 )∥w 1 -w * ∥ 2 + 4β K k=1 η 2 k F (w * ) + 8β 2 r 2 K k=1 η 2 k + βLr K k=1 η k τ k j=1 η k-j   + 8βe(β + γ)(1 + K/n) n η 1 ∥w 1 -w * ∥ 2 + 2 K k=1 η 2 k F (w * ) + 4βr 2 K k=1 η 2 k + β 2 r 2 (β + γ)e K k=1 η k k l=1 η l τ l j=1 η l-j / K k=1 η k + β γ F (w * ).By setting γ = 1, we conclude that the excess generalization error ϵ ex-gen isϵ ex-gen = O 1 + K k=1 η 2 k K k=1 η k F (w * ) + 1 + K/n n η 1 ∥w 1 -w * ∥ 2 + 1 + F (w * ) K k=1 η 2 k + ∥w 1 -w * ∥ 2 K k=1 η k + K k=1 η 2 k + K k=1 η k τ k j=1 η k-j + K k=1 η k k l=1 η l τ l j=1 η l-j / K k=1 η k .Let the learning rate η k = c(τ √ K) -1 with a constant c > 0, and τ = K k=1 τ k /K, direct calculation givesK k=1 η k = c √ K/τ , K k=1 η 2 k = c 2 /τ 2 , K k=1 η k τ k j=1 η k-j = c 2 τ 2 K K k=1 τ k = c 2 τ , K k=1 η k k l=1 η l τ l j=1 η l-j = c τ √ K 3 K k=1 k l=1 τ l ≤ c 3 √ K τ 2 .From the excess generalization error (B.15), we can deriveE S,A [F (w K ) -F (w * )] ≤ (1 + β γ ) ( 1 2 + 2βc τ √ K )∥w 1 -w * ∥ 2 + 4βc 2 τ 2 F (w * ) + 8β 2 r 2 c 2 τ 2 + βLrc 2 τ • τ c √ K + 8βe(β + γ)(1 + K/n) n c τ √ K ∥w 1 -w * ∥ 2 + 2c 2 τ 2 F (w * ) + 4βr 2 c 2 τ 2 + β 2 r 2 (β + γ)e c 3 √ K τ 2 • τ c √ K + β γ F (w * ) ≤ (1 + β γ ) τ √ K ∥w 1 -w * ∥ 2 2c + βrc( 8βr √ Kτ + L √ K ) + 2β∥w 1 -w * ∥ 2 K ) + 8βe(β + γ)(1 + K/n) n c τ √ K ∥w 1 -w * ∥ 2 + 2c 2 τ 2 F (w * ) + 4βr 2 c 2 τ 2 + β 2 r 2 (β + γ)ec 2 τ + β γ + (1 + β γ ) 4βc τ √ K F (w * ).Let F (w * ) = 0, K ≍ n and γ = 1. If the average delay satisfies τ ≤ K 1 4 (quite reasonable in asynchronous training), we havemax{ τ √ K , 1 √ Kτ , 1 √ K } ≤ 1τ . Then the excess generalization error isE S,A [F (w K ) -F (w * )] = O 1 τ + ∥w 1 -w * ∥ 2 n .C Proof of Generalization in Non-smooth Case (Section 5 in the main text)C.1 Proof of Lemma 5 (approximately non-expansive property in the non-smooth case)Under (α, β)-Hölder continuous condition, the gradients exhibit the following co-coercivity⟨w k-τ k -w (i) k-τ k , ∇f (w k-τ k ; z i k )-∇f (w (i) k-τ k ; z i k )⟩ ≥ 2β -1 α α 1 + α ∥∇f (w k-τ k ; z i k )-∇f (w (i) k-τ k ; z i k )∥ 1+α α .A detailed proof of this co-coercivity can be found in [24, 39, 51] , and also in Lemma D.2 of [23] .Then we have∥∇f (w k-τ k ; z i k )-∇f (w (i) k-τ k ; z i k )∥ 2 ≤ 1 + α 2β -1 α α ⟨w k-τ k -w (i) k-τ k , ∇f (w k-τ k ; z i k )-∇f (w (i) k-τ k ; z i k )⟩ 2α 1+α = 1 + α η k α ⟨w k-τ k -w (i) k-τ k , ∇f (w k-τ k ; z i k ) -∇f (w (i) k-τ k ; z i k )⟩ 2α 1+α • 2 -2α 1+α η 2α 1+α k β 2 1+α ≤ 2 η k ⟨w k-τ k -w (i) k-τ k , ∇f (w k-τ k ; z i k ) -∇f (w (i) k-τ k ; z i k )⟩ + 1 -α 1 + α η 2α 1-α k 2 -α β 2 1-α ,where the last inequality we use the Young's inequality (A.1) with p = 1+α 2α , q = 1+α 1-α . That isη 2 k ∥∇f (w k-τ k ; z i k ) -∇f (w (i) k-τ k ; z i k )∥ 2 ≤ 2η k ⟨w k-τ k -w (i) k-τ k , ∇f (w k-τ k ; z i k ) -∇f (w (i) k-τ k ; z i k )⟩ + d 2 α,β η 2 1-α k , (C.1)where d α,β = 1-α 1+α 2 -α β 1 1-α > 0 is a constant dependent on α, β. Without smoothness, the non-expansive property of delayed gradient updates would be further compromised. However, in conjunction with inequality (C.1), we can make the following derivation.w k -η k ∇f (w k-τ k ; z i k ) -w (i) k -η k ∇f (w (i) k-τ k ; z i k ) 2 = ∥w k -w (i) k ∥ 2 + η 2 k ∥∇f (w k-τ k ; z i k ) -∇f (w (i) k-τ k ; z i k )∥ 2 -2η k ⟨w k -w (i) k , ∇f (w k-τ k ; z i k ) -∇f (w (i) k-τ k ; z i k )⟩ = ∥w k -w (i) k ∥ 2 + η 2 k ∥∇f (w k-τ k ; z i k ) -∇f (w (i) k-τ k ; z i k )∥ 2 -2η k ⟨w k-τ k -w (i) k-τ k , ∇f (w k-τ k ; z i k ) -∇f (w (i) k-τ k ; z i k )⟩ -2η k ⟨w k -w k-τ k -(w (i) k -w (i) k-τ k ), ∇f (w k-τ k ; z i k ) -∇f (w (i) k-τ k ; z i k )⟩ ≤ ∥w k -w (i) k ∥ 2 -2η k ⟨w k -w k-τ k -(w (i) k -w (i) k-τ k ), ∇f (w k-τ k ; z i k ) -∇f (w (i) k-τ k ; z i k )⟩ + d 2 α,β η 2 1-α k .Following the (α, β)-Hölder continuous condition and Assumption 1, we can derive ∥∇f (w s-τs ; z is )-∇f (w(i) s-τs ; z is )∥ ≤ β∥w s-τs -w (i) s-τs ∥ α ≤ βr α , for s = k, k -j; j = 1, . . . , τ k .(C.2) By combing (B.1) and (C.2), the asynchronous gradient updates satisfy the following approximately non-expansive property under the (α, β)-Hölder continuous condition.w k -η k ∇f (w k-τ k ; z i k ) -w (i) k -η k ∇f (w (i) k-τ k ; z i k ) 2 ≤ w k -w (i) k 2 + d 2 α,β η 2 1-α k + 2β 2 r 2α η k τ k j=1 η k-j . (C.3)C.2 Proof of Theorem 4 (algorithm stability under the (α, β)-Hölder continuous gradient assumption)We now examine the on-average model stability of the ASGD algorithm under the (α, β)-Hölder continuous gradient assumption. Following (C.3), if ASGD selects the same sample in both S and S (i) at the k-th iteration (with probability 1 -1/n), we havew k+1 -w (i) k+1 2 ≤ w k -η k ∇f (w k-τ k ; z i k ) -w (i) k -η k ∇f (w (i) k-τ k ; z i k ) 2 ≤ ∥w k -w (i) k ∥ 2 + 2η k β 2 r 2α τ k j=1 η k-j + d 2 α,β η 2 1-α k ,where the first inequality uses the no-expansive projection (A.8). On the other hand, with probability 1/n the selected example is different (i k = i), then∥w k+1 -w (i) k+1 ∥ 2 ≤ ∥w k -η k ∇f (w k-τ k ; z i ) -w (i) k + η k ∇f (w (i) k-τ k ; z ′ i )∥ 2 ≤ (1 + p)∥w k -w (i) k ∥ 2 + (1 + 1/p)η 2 k ∥∇f (w k-τ k ; z i ) -∇f (w (i) k-τ k ; z ′ i )∥ 2 ≤ (1 + p)∥w k -w (i) k ∥ 2 + 2(1 + 1/p)η 2 k ∥∇f (w k-τ k ; z i )∥ 2 + ∥∇f (w (i) k-τ k ; z ′ i )∥ 2 ≤ (1 + p)∥w k -w (i) k ∥ 2 + 2(1 + 1/p)c 2 α,β η 2 k f 2α 1+α (w k-τ k ; z i ) + f 2α 1+α (w (i) k-τ k ; z ′ i ) .Here we use the inequality (A.4) and the self-bounding property of the α, β-Hölder continuous gradient (A.5). Combining the above two cases gives∥w k+1 -w (i) k+1 ∥ 2 ≤(1 + p n )∥w k -w (i) k ∥ 2 + 2η k β 2 r 2α τ k j=1 η k-j + d 2 α,β η 2 1-α k + 2(1 + 1/p)c 2 α,β η 2 k n f 2α 1+α (w k-τ k ; z i ) + f 2α 1+α (w (i) k-τ k ; z ′ i ) . (C.4)Following the factE S,S ′ ,A [f 2α 1+α (w (i) k-τ k ; z ′ i )] = E S,A [f 2α 1+α (w k-τ k ; z i )],and the same model initialization w 1 = w (i)1 , taking the expectation followed by summation of inequality (C.4) yieldsE S,S ′ ,A ∥w k+1 -w (i) k+1 ∥ 2 ≤ (1 + p n )E S,S ′ ,A ∥w k -w (i) k ∥ 2 + 2η k β 2 r 2α τ k j=1 η k-j + d 2 α,β η 2 1-α k + 4(1 + 1/p)c 2 α,β η 2 k n E S,A f 2α 1+α (w k-τ k ; z i ) ≤ k l=1 (1+ p n ) (k-l)   4(1+1/p)c 2 α,β η 2 l n E S,A f 2α 1+α (w l-τ l ; z i ) + 2η l β 2 r 2α τ l j=1 η l-j + d 2 α,β η 2 1-α l   .By the concavity of the function x → x 2α 1+α , the on-average model stability of ASGD satisfiesE S,S ′ ,A 1 n n i=1 ∥w k+1 -w (i) k+1 ∥ 2 ≤ (1+ p n ) (k-1) k l=1   4(1+1/p)c 2 α,β η 2 l n E S,A F 2α 1+α S (w l-τ l ) + 2η l β 2 r 2α τ l j=1 η l-j + d 2 α,β η 2 1-α l   . Let p = n/k, we have (1 + p/n) (k-1) ≤ (1 + 1/k) (k-1) ≤ e, then E S,S ′ ,A 1 n n i=1 w k+1 -w (i) k+1 2 ≤ 4e(1 + k/n)c 2 α,β n k l=1 η 2 l E S,A F 2α 1+α S (w l-τ l ) + 2β 2 r 2α e k l=1 η l τ l j=1 η l-j + ed 2 α,β k l=1 η 2 1-α l = O 1 + k/n n k l=1 η 2 l E S,A F 2α 1+α S (w l-τ l ) + k l=1 η l τ l j=1 η l-j + k l=1 η 2 1-α l . (C.5)From the algorithm stability (C.5), it follows that we need to boundk l=1 η 2 l E S,A [F 2α 1+α(w l-τ l )] under the α, β-Hölder continuous gradient condition. Using the non-expansive projection (A.8) and the self-bounding property (A.5), we can derive∥w k+1 -w * ∥ 2 ≤ ∥w k -η k ∇f (w k-τ k ; z i k ) -w * ∥ 2 = ∥w k -w * ∥ 2 + η 2 k ∥∇f (w k-τ k ; z i k )∥ 2 + 2η k ⟨w * -w k , ∇f (w k-τ k ; z i k )⟩ ≤ ∥w k -w * ∥ 2 + c 2 α,β η 2 k f 2α 1+α (w k-τ k ; z i k ) + 2η k ⟨w * -w k , ∇f (w k-τ k ; z i k )⟩.By the young's inequality (A.1) with p = 1+α 1-α , q = 1+α 2α , we havec 2 α,β η k f 2α 1+α (w k-τ k ; z i k ) = 2α 1 + α 2α 1+α c 2 α,β η k • 1 + α 2α f (w k-τ k ; z i k ) 2α 1+α ≤ 1 -α 1 + α 2α 1 + α 2α 1+α c 2 α,β η k 1+α 1-α + 2α 1 + α 1 + α 2α f (w k-τ k ; z i k ) 2α 1+α 1+α 2α = f (w k-τ k ; z i k ) + c ′ α,β η 1+α 1-α k ,where we define the constant c ′α,β = 1-α 1+α 2α 1+α 2α 1-α c 2+2α 1-α α,β > 0.With the convexity of f , we can further derive∥w k+1 -w * ∥ 2 ≤ ∥w k -w * ∥ 2 + η k f (w k-τ k ; z i k ) + 2η k ⟨w * -w k , ∇f (w k-τ k ; z i k )⟩ + c ′ α,β η 2 1-α k ≤ ∥w k -w * ∥ 2 + η k f (w k-τ k ; z i k ) + 2η k (f (w * ; z i k ) -f (w k-τ k ; z i k )) + 2η k ⟨w k-τ k -w k , ∇f (w k-τ k ; z i k )⟩ + c ′ α,β η 2 1-α k ≤ ∥w k -w * ∥ 2 -η k f (w k-τ k ; z i k ) + 2η k f (w * ; z i k ) + 2η k ⟨w k-τ k -w k , ∇f (w k-τ k ; z i k )⟩ + c ′ α,β η 2 1-α k .(C.6) Here, with the inequality (A.2), (A.5) and Assumption 1, we have the following derivation2η k ⟨w k-τ k -w k , ∇f (w k-τ k ; z i k )⟩ ≤ 2η k r • c α,β f α 1+α (w k-τ k ; z i k ) ≤ (1 + α)η k 2α f (w k-τ k ; z i k ) α 1+α • 2 1+2α 1+α η 1 1+α k α 1 + α α 1+α c α,β r ≤ η k 2 f (w k-τ k ; z i k ) + c ′′ α,β η k ,where the last inequality we use the young's inequality (A.1) with p = 1+α α , q = 1 + α, andEQUATION1+α is a constant. Substituting it into (C.6) yieldsη k f (w k-τ k ; z i k ) ≤ 2∥w k -w * ∥ 2 -2∥w k+1 -w * ∥ 2 + 4η k f (w * ; z i k ) + 2c ′ α,β η 2 1-α k + 2c ′′ α,β η k .Multiplying both sides by the non-increasing learning rate yieldsη 2 k f (w k-τ k ; z i k ) ≤ 2η k ∥w k -w * ∥ 2 -2η k+1 ∥w k+1 -w * ∥ 2 +4η 2 k f (w * ; z i k )+2c ′ α,β η 3-α 1-α k +2c ′′ α,β η 2 k .Taking the expectation and summing the inequalities as above givesk l=1 η 2 l E S,A [F S (w l-τ l )] ≤ 2η 1 ∥w 1 -w * ∥ 2 + 4 k l=1 η 2 l E S [F S (w * )] + 2c ′ α,β k l=1 η 3-α 1-α l + 2c ′′ α,β k l=1 η 2 l .According to the concavity of the function x → x 2α 1+α , we know thatk l=1 η 2 l E S,A [F 2α 1+α S (w l-τ l )] ≤ k l=1 η 2 l k l=1 η 2 l E S,A [F S (w l-τ l )] k l=1 η 2 l 2α 1+α ≤ 2 k l=1 η 2 l 1-α 1+α η 1 ∥w 1 -w * ∥ 2 + 2 k l=1 η 2 l F (w * ) + c ′ α,β k l=1 η 3-α 1-α l + c ′′ α,β k l=1 η 2 l 2α 1+α . (C.7)Now, we are ready to analysis the generalization error of ASGD under (α, β)-Hölder continuous gradient condition. From Lemma 2 (A.13) and stability (C.5), we have we haveE S,A [F (w k+1 ) -F S (w k+1 )] ≤ c 2 α,β 2γ E S,A [F 2α 1+α (w k+1 )] + γ 2 n i=1 E S,S ′ ,A 1 n ∥w k+1 -w (i) k+1 )∥ 2 ≤ c 2 α,β 2γ E S,A [F 2α 1+α (w k+1 )] + 2eγ(1 + k/n)c 2 α,β n k l=1 η 2 l E S,A F 2α 1+α S (w l-τ l ) + eγβ 2 r 2α k l=1 η l τ l j=1 η l-j + eγd 2 α,βE S,A [F 2α 1+α (w k+1 )] ≤ E S,A [F (w k+1 ) -F S (w k+1 )] + E S,A [F S (w k+1 )] 2α 1+α ≤ ϵ 2α 1+α k+1 + E S,A F S (w k+1 ) 2α 1+α .Substituting this back into (C.8) givesϵ k+1 ≤ c 2 α,β 2γ ϵ 2α 1+α k+1 + E S,A F S (w k+1 ) 2α 1+α + 2eγ(1 + k/n)c 2 α,β n k l=1 η 2 l E S,A F 2α 1+α S (w l-τ l ) + eγβ 2 r 2α k l=1 η l τ l j=1 η l-j + eγd 2 α,β 2 k l=1 η 2 1-α l .Using the young's inequality (A. 1) with p = 1+α 1-α , q = 1+α 2α yields c 2 α,β 2γ ϵ 2α 1+α k+1 = 4α 1 + α 2α 1+α c 2 α,β 2γ • 1 + α 4α ϵ k+1 2α 1+α ≤ 1 -α 1 + α 4α 1 + α 2α 1-α c 2 α,β 2γ 1+α 1-α + 1 2 ϵ k+1 .It then holds thatE S,A [F (w k+1 ) -F S (w k+1 )] ≤ 2(1 -α) 1 + α 4α 1 + α 2α 1-α c 2 α,β 2γ 1+α 1-α + c 2 α,β γ E S,A F S (w k+1 ) 2α 1+α + 4eγ(1 + k/n)c 2 α,β n k l=1 η 2 l E S,A F 2α 1+α S (w l-τ l ) + 2eγβ 2 r 2α k l=1 η l τ l j=1 η l-j + eγd 2 α,β k l=1 η 2 1-α l .Substituting (C.7), we can get the following generalization error of ASGD under the (α, β)-Hölder continuous gradient conditionE S,A [F (w k+1 ) -F S (w k+1 )] ≤ 2(1 -α) 1 + α 4α 1 + α 2α 1-α c 2 α,β 2γ 1+α 1-α + c 2 α,β γ E S,A F S (w k+1 ) 2α 1+α + 8eγ(1 + k/n)c 2 α,β n k l=1 η 2 l 1-α 1+α η 1 ∥w 1 -w * ∥ 2 + 2 k l=1 η 2 l F (w * ) + c ′ α,β k l=1 η 3-α 1-α l + c ′′ α,β k l=1 η 2 l 2α 1+α + 2eγβ 2 r 2α k l=1 η l τ l j=1 η l-j + eγd 2 α,β k l=1 η 2 1-α l . (C.9)C.4 Proof of Lemma 6 (Optimization error under the (α, β)-Hölder continuous gradient assumption)Leveraging the non-expansive projection property (A.8), convexity and α, β-Hölder continuous property (A.5), we can derive∥w k+1 -w * ∥ 2 ≤ ∥w k -η k ∇f (w k-τ k ; z i k ) -w * ∥ 2 = ∥w k -w * ∥ 2 + η 2 k ∥∇f (w k-τ k ; z i k )∥ 2 + 2η k ⟨w * -w k , ∇f (w k-τ k ; z i k )⟩ ≤ ∥w k -w * ∥ 2 + c 2 α,β η 2 k f 2α 1+α (w k-τ k ; z i k ) + 2η k ⟨w * -w k , ∇f (w k ; z i k )⟩ + 2η k ⟨w * -w k , ∇f (w k-τ k ; z i k ) -∇f (w k ; z i k )⟩ ≤ ∥w k -w * ∥ 2 + c 2 α,β η 2 k f 2α 1+α (w k-τ k ; z i k ) + 2η k (f (w * ; z i k ) -f (w k ; z i k )) + 2βη k ∥w * -w k ∥∥w k-τ k -w k ∥ α .(C.10) From the iterative scheme of ASGD ( 7), (A.8) and the sub-additivity of x → x α , we know that∥w k -w k-τ k ∥ α ≤ τ k j=1 ∥w k-j+1 -w k-j ∥ α ≤ τ k j=1 η α k-j ∥∇f (w k-j-τ k-j ; z i k-j )∥ α . (C.11)Taking the expectation followed by a summation of (C.10) yields2 K k=1 η k E S,A [F S (w k ) -F S (w * )] ≤ ∥w 1 -w∥ 2 + c 2 α,β K k=1 η 2 k E S,A [F 2α 1+α S (w k-τ k )] + 2βL α r K k=1 η k τ k j=1 η α k-j ,where we used (C.11), Assumptions 1 and 2. Combing with (C.7), we get the following optimization error bound of ASGD with the (α, β)-Hölder continuous gradient.K k=1 η k [F S (w k ) -F S (w * )] ≤ 1 2 ∥w 1 -w * ∥ 2 + βL α r K k=1 η k τ k j=1 η α k-j + c 2 α,β K k=1 η 2 k 1-α 1+α η 1 ∥w 1 -w * ∥ 2 + 2 K k=1 η 2 k F (w * ) + c ′ α,β K k=1 η 3-α 1-α k + c ′′ α,β K k=1 η 2 k 2α 1+α .(C.12)According to the convexity of the function F S , we know thatE S,A [F S (w K ) -F S (w * )] ≤ K k=1 η k E S,A [F S (w k ) -F S (w * )] K k=1 η k = O K k=1 η 2 k 1-α 1+α K k=1 η k η 1 ∥w 1 -w * ∥ 2 + 1 + F (w * ) K k=1 η 2 k + K k=1 η 3-α 1-α k 2α 1+α + ∥w 1 -w * ∥ 2 + K k=1 η k τ k j=1 η α k-j K k=1 η k .C.5 Proof of Theorem 5 (Excess generalization error under the (α, β)-Hölder continuous gradient assumption)Multiplying both sides of the generalization error (C.9) by the learning rate η k+1 followed by summation yieldsK k=1 η k E S,A [F (w k )] ≤ K k=1 η k E S,A [F S (w k )] + c 2 α,β γ K k=1 η k E S,A F S (w k ) 2α 1+α + 2 4α 1+α 2α 1-α c 2 α,β 2γ 1+α 1-α K k=1 η k + 8eγ(1+K/n)c 2 α,β n K k=1 η k k l=1 η 2 l 1-α 1+α • η 1 ∥w 1 -w * ∥ 2 + 2 k l=1 η 2 l F (w * ) + c ′ α,β k l=1 η 3-α 1-α l + c ′′ α,β k l=1 η 2 l 2α 1+α + 2eγβ 2 r 2α K k=1 η k k l=1 η l τ l j=1 η l-j + eγd 2 α,β K k=1 η k k l=1 η 2 1-α l .According to the concavity of the function x → x 2α 1+α , we know thatK k=1 η k E S,A F S (w k ) 2α 1+α ≤ K k=1 η k K k=1 η k E S,A [F S (w k )] K k=1 η k 2α 1+α = K k=1 η k 1-α 1+α K k=1 η k E S,A [F S (w k )] 2α 1+α ≤ 1 -α 1 + α K k=1 η k + 2α 1 + α K k=1 η k E S,A [F S (w k )],where the last inequality uses the young's inequality (A.1) with p = 1+α 1-α , q = 1+α 2α . ThenK k=1 η k ES,A [F (w k )] ≤ 1+ 2αc 2 α,β γ(1+α) K k=1 η k ES,A [FS (w k )]+ 2 4α 1+α 2α 1-α c 2 α,β 2γ 1+α 1-α + (1-α)c 2 α,β γ(1+α) K k=1 η k + 8eγ(1+K/n)c 2 α,β n K k=1 η k k l=1 η 2 l 1-α 1+α η1∥w1 -w * ∥ 2 + 2 k l=1 η 2 l F (w * ) + c ′ α,β k l=1 η 3-α 1-α l + c ′′ α,β k l=1 η 2 l 2α 1+α + 2eγβ 2 r 2α K k=1 η k k l=1 η l τ l j=1 η l-j + eγd 2 α,β K k=1 η k k l=1 η 2 1-α l .From the optimization error (C.12), we then haveK k=1 η k ES,A [F (w k )-F (w * )] ≤ 2αc 2 α,β γ(1+α) K k=1 η k F (w * )+ 1+ 2αc 2 α,β γ(1+α) 1 2 ∥w1 -w * ∥ 2 +βL α r K k=1 η k τ k j=1 η α k-j + 1 + 2αc 2 α,β γ(1 + α) c 2 α,β K k=1 η 2 k 1-α 1+α η1∥w1 -w * ∥ 2 + 2 K k=1 η 2 k F (w * ) + c ′ α,β K k=1 η 3-α 1-α k + c ′′ α,β K k=1 η 2 k 2α 1+α + 8eγ(1+K/n)c 2 α,β n K k=1 η k k l=1 η 2 l 1-α 1+α η1∥w1 -w * ∥ 2 + 2 k l=1 η 2 l F (w * ) + c ′ α,β k l=1 η 3-α 1-α l + c ′′ α,β k l=1 η 2 l 2α 1+α + 2eγβ 2 r 2α K k=1 η k k l=1 η l τ l j=1 η l-j +eγd 2 α,β K k=1 η k k l=1 η 2 1-α l + 2 4α 1+α 2α 1-α c 2 α,β 2γ 1+α 1-α + (1-α)c 2 α,β γ(1+α) K k=1 η k .By the convexity of F , the excess generalization error of ASGD under the (α, β)-Hölder continuous gradient satisfiesES,A [F (w k ) -F (w * )] ≤ K k=1 η k ES,A [F (w k ) -F (w * )] K k=1 η k ≤ 1+ 2αc 2 α,β γ(1 + α) c 2 α,β K k=1 η 2 k 1-α 1+α η1∥w1 -w * ∥ 2 +2 K k=1 η 2 k F (w * )+c ′ α,β K k=1 η 3-α 1-α k +c ′′ α,β K k=1 η 2 k 2α 1+α / K k=1 η k + 8eγ(1 + K/n)c 2 α,β n K k=1 η 2 k 1-α 1+α η1∥w1 -w * ∥ 2 + 2 K k=1 η 2 k F (w * ) + c ′ α,β K k=1 η 3-α 1-α k + c ′′ α,β K k=1 η 2 k 2α 1+α + 2eγβ 2 r 2α K k=1 η k k l=1 η l τ l j=1 η l-j +eγd 2 α,β K k=1 η k k l=1 η 2 1-α l / K k=1 η k +2 4α 1+α 2α 1-α c 2 α,β 2γ 1+α 1-α + (1-α)c 2 α,β γ(1+α) + 1 + 2αc 2 α,β γ(1 + α) 1 2 ∥w1 -w * ∥ 2 + βL α r K k=1 η k τ k j=1 η α k-j / K k=1 η k + 2αc 2 α,β γ(1 + α) F (w * ). (C.13)Let γ > 1, then we are arrive atϵ ex-gen = O K k=1 η 2 k 1-α 1+α η 1 ∥w 1 -w * ∥ 2 + K k=1 η 2 k F (w * ) + K k=1 η 3-α 1-α k + K k=1 η 2 k 2α 1+α / K k=1 η k + γ(1 + K/n) n K k=1 η 2 k 1-α 1+α η 1 ∥w 1 -w * ∥ 2 + K k=1 η 2 k F (w * ) + K k=1 η 3-α 1-α l + K k=1 η 2 k 2α 1+α + γ K k=1 η k k l=1 η l τ l j=1 η l-j + K k=1 η k k l=1 η 2 1-α l / K k=1 η k + γ 1+α α-1 + ∥w 1 -w * ∥ 2 + K k=1 η k τ k j=1 η α k-j / K k=1 η k + 1 γ 1 + F (w * ) .(C.14)η k = c(τ √ K) -1Set the learning rate η k = c(τ√ K) -1 with c > 0, and τ = K k=1 τ k /K, direct calculation gives K k=1 η k = c √ K/τ , K k=1 η 2 k = c 2 /τ 2 , K k=1 η k k l=1 η l τ l j=1 η l-j = c τ √ K 3 K k=1 k l=1 τ l ≤ c 3 √ K τ 2 K k=1 η k τ k j=1 η α k-j = c 1+α K 1-α 2 τ α , K k=1 η 3-α 1-α k ≍ K 1-3-α 2(1-α ) τ -3-α 1-α , K k=1 η k k l=1 η 2 1-α l ≍ K 2-3-α 2(1-α) τ -3-α 1-α .Following the excess generalization error (C.14), we know thatϵ ex-gen = O 1 τ 2 1-α 1+α ∥w 1 -w * ∥ 2 √ Kτ + 1 τ 2 1 + F (w * ) + K 1-3-α 2(1-α) τ 3-α 1-α 2α 1+α • τ √ K + γ(1 + K/n) n 1 τ 2 1-α 1+α ∥w 1 -w * ∥ 2 √ Kτ + 1 τ 2 1 + F (w * ) + K 1-3-α 2(1-α) τ 3-α 1-α 2α 1+α + γ √ K τ 2 + K 2-3-α 2(1-α) τ 3-α 1-α • τ √ K + γ 1+α α-1 + ∥w 1 -w * ∥ 2 + K 1-α 2 τ α • τ √ K + 1 γ 1 + F (w * ) .By the sub-additivity of x → x 2α 1+α , (α ∈ [0, 1]), we can deriveϵ ex-gen = O τ √ K + γ(1 + K/n) n τ -2(1-α) 1+α ∥w 1 -w * ∥ 4α 1+α K α 1+α τ 2α 1+α + 1 τ 4α 1+α 1 + F 2α 1+α (w * ) + K -α 1-α τ 2α(3-α) (1+α)(1-α) + γ 1 τ + K -α 1-α τ 2 1-α + τ ∥w 1 -w * ∥ 2 √ K + τ 1-α K α 2 + γ 1+α α-1 + 1 γ 1 + F (w * ) = O τ √ K + γ(1 + K/n) n K -α 1+α τ 2 1+α ∥w 1 -w * ∥ 4α 1+α + 1 τ 2 1 + F 2α 1+α (w * ) + K -α 1-α τ 2 1-α + γ 1 τ + K -α 1-α τ 2 1-α + τ √ K + τ 1-α K α 2 + γ 1+α α-1 + 1 γ 1 + F (w * ) .Omitting the non-dominant term gives (with γ > 1)ϵ ex-gen = O τ √ K + γ(1 + K/n) n K -α 1+α τ 2 1+α ∥w 1 -w * ∥ 4α 1+α + 1 τ 2 1 + F 2α 1+α (w * ) + γ τ + τ √ K + τ 1-α K α 2 + 1 γ 1 + F (w * ) .If F (w * ) = 0, K ≍ n, then the excess generalization error isϵ ex-gen = O τ √ K + γ n K -α 1+α τ 2 1+α ∥w 1 -w * ∥ 4α 1+α + 1 τ 2 + γ τ + τ √ K + τ 1-α K α 2 + 1 γ . Let γ = √ τ , we have that max{ τ √ K , γ n } = τ √ K, and thenϵ ex-gen = O ∥w 1 -w * ∥ 4α 1+α K 1+3α 2(1+α) τ 1-α 1+α + 1 √ Kτ + 1 √ τ + τ √ K + τ 1-α K α 2.Furthermore, if the average delay satisfies τ ≤ K α ′ with α ′ = min{ 1 3 , α 3-2α }, we know thatmax 1 √ Kτ , 1 √ τ , τ √ K , τ 1-α K α 2 = 1 √ τ .On the other hand, since τ ≥ 1 in the asynchronous training and α ∈ [0, 1], we haveK 1+3α 2(1+α) τ 1-α 1+α ≥ K 1+3α 2(1+α) ≥ K 1+α 2 ≍ n 1+α 2. Then, we are arrive atϵ ex-gen = E S,A [F (w k ) -F (w * )] = O 1 √ τ + ∥w 1 -w * ∥ 4α 1+α √ n 1+α .The proof is complete. This section provides additional details on the experimental setup, as well as the stability and generalization results trained with a delay-independent constant learning rate. Our experiments use the more general asynchronous stochastic gradient descent format (9), i.e.,w k+1 = w k -η k m∈M k g m k-τ k .In practical applications, the gradient g m k-τ k is evaluated on a mini-batch of the training data. The batch size of each worker in this experiment was set to 16. It should be noted that we only simulated 8 workers in the BERT experiments due to memory limitations. All of our experiments were implemented with PyTorch on Nvidia RTX-3090 24 GB GPUs.In Figure 3 and 4 , the stability and generalization results of the ASGD algorithm, employing a delayindependent learning rate of η k = 0.01, are illustrated. In this scenario, increasing the delay still improves the algorithm stability and reduces the generalization error, indicating that asynchronous training is indeed beneficial for generalization. Figure 5 shows the training, testing and generalization errors of three categories of machine learning models. The generalization errors are roughly of the same order of magnitude as the training and testing errors. In certain model tasks, particularly BERT on the SST-2 task, overfitting phenomena are present, contributing significantly to the generalization gap. Therefore, we need to complete the training process as soon as possible to improve the model generalization performance, which is consistent with our theoretical analysis in Section 4.2. The main challenge of this study is to establish sharper generalization bounds for the ASGD algorithm under much weaker assumptions.Notably, the existing studies on the generalization of ASGD are limited. Study [33] provides only vacuous exponential generalization bounds and relies on strict assumptions such as Lipschitz continuous and smooth functions. Another work [13] establishes tighter generalization bounds, but its analytical techniques only applicable to smooth quadratic convex problems.Our contributions have been detailed in Section 1, and the following table further compares the required assumptions and theoretical results of the related works. K τ nτ O K-τ nτ O 1 τ + 1 √ K Excess generalization error N/A N/A O 1 √ τ + ∥w1-w * ∥ 4α 1+α √ n 1+αAssumption. In Assumptions 1 and 2, we have listed the assumptions required for this paper and explained their roles and plausibility. It is crucial to note that this study aims to establish sharper stability and generalization error bounds under much weaker assumptions. If we adopt stronger assumptions, such as the assumption in paper [55] that the difference between models w k and w Non-convex study. In the non-convex setting, the delayed gradient update operator cannot maintain the approximately non-expansive property. Consequently, directly extending the analysis of this paper to non-convex scenarios would yield an exponential generalization error bound, similar to the findings in study [33] . Unfortunately, this upper bound is pessimistic and vacuous. Exploring sharper stability and generalization error bounds of ASGD in non-convex scenarios is extremely challenging. Future research on non-convex problems could focus on demonstrating that asynchronous gradient updates are approximately non-expansive even without the convexity property, then leading to non-vacuous stability and generalization results.Additionally, while our theoretical analysis is grounded in the general convex condition, our nonconvex experiments show that the theoretical results in this paper are applicable in a broader range of non-convex machine learning tasks (particularly deep learning), which motivates us to further explore tighter stability and generalization results for ASGD in the non-convex scenarios in the future.NeurIPS Paper Checklist Guidelines:• The answer NA means that the paper has no 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 a separate "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 on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 of 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This paper focuses on stability and generalizability analysis of fundamental optimization algorithm. No societal impacts are discussed or related to the research.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 alone 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). 
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 focuses on stability and generalizability analysis of fundamental optimization algorithm and 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: The models and datasets used in this paper are publicly available and we have cited the corresponding 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. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
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/model 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. 
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 as 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 crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
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 nor 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 NeurIPS 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. 
 
 Appendix:  


Decision: All the reviewers agreed that the paper has significant contributions and the rebuttal letter provided by the authors alleviated several concerns raised by the reviewers. I recommend an acceptance. Please implement carefully all the promised changes in the camera-ready version.

Reviews: review: paper_summary: paper_summary: The paper explores the generalizability of ASGD through the lens of on-average stability, revealing how asynchronous delay, model initialization, the number of training samples, and iterations impact the generalization performance under both Lipschitz smooth and Hölder continuity conditions. The authors also conduct extensive experiments on various tasks to validate their theoretical findings.
strength_weakness: strength_weakness: - The main contribution should focus on *sharper*; however, it is not clearly illustrated in the paper. Please refer to the **Questions** below for clarification. Additionally, there is a lack of necessary comments or remarks following each theorem and corollary to explain their implications and comparisons.

- It should be emphasized what technical tools enable authors to derive *sharper* or better results compared to existing works.
questions: questions: 1. *Suggestion:* Including a table that summarizes all the theoretical results (including necessary assumptions), along with their comparisons with existing works, would help clarify the contributions of this paper.

2. What do authors mean by ***sharper*** : 
    - In *Line 233*, the result $\mathcal{O}(K^{\hat{\tau}}/n\hat{\tau})$ can also demonstrate that, increasing the pessimistic maximum delay $\hat{\tau}$ after $\frac{1}{\ln{K}}$ reduces the generalization error, why is this paper's result $\mathcal{O}(\frac{1}{\bar{\tau}}+\frac{1}{\sqrt{K}})$ sharper?
    - Can authors give more detailed explanations about the ***sharper*** in *Line 292* and *Line 297*?

3. Why the result presented in **Theorem 5** that $\mathcal{O}(\frac{1}{\sqrt{\bar{\tau}}}+\frac{||\omega_1-\omega^*||^{\frac{4\alpha}{1+\alpha}}}{\sqrt{n}^{1+\alpha}})$, which holds the same assumptions and requirements with **Corollary 2** when $\alpha=1$, is inconsistent with the corresponding result that $\mathcal{O}(\frac{1}{\bar{\tau}}+\frac{||\omega_1-\omega^*||^2}{n})$?
limitations: limitations: Yes.
paper_summary: paper_summary: The paper provides generalization analysis of Asynchronous stochastic gradient descent (ASGD) for both smooth and non-smooth (Holder smooth) lesses. For generalization error, the Lipschitzness of losses assumption is  removed, while for excess generalization error, the loss is also required to be Lipschitz. The excess generalization error rates $O\big( \frac{1}{\bar{\tau}} + \frac{ || w_1-w* || }{n}\big)$ and $O\big( \frac{1}{\sqrt{\bar{\tau}}} + \frac{ || w_1-w* ||^{\frac{4\alpha}{1+\alpha}} }{n^{\frac{\alpha+1}{2}}}\big)$ which outperform previous results.
strength_weakness: strength_weakness: 1.  Although the problem studied is slightly different, the proofs of the main results almost follow from Lei (2021). The novelty of the paper remains a question. Specifically, Lei (2021) studies the generalization analysis of standard SGD for both  smooth and nonsmooth (Holder smooth) losses through the lens of on-average model stability under the same assumptions. 

2. The error bounds in all theorems rely on the radius of the parameter space $r$ and the paper hides the occurrence of $r$ in the results.. If $r$ is very large, the bounds would be bad. Indeed, the estimation of the paper is rough, since for SGD, one can prove that $||w_k - w_1||^2\lesssim \sum_{t=1}^{k} \eta_k  $ for both smooth and Holder smooth looses, I believe that a similar result could be established for ASGD. It will improve the results of the paper.

3. Establishing the excess generalization error bounds require the loss to be Lipschitz, the statement "....provides a non-vacuous upper bound on the generalization error, without relying on the Lipschitz assumption" in the abstract is somewhat misleading.
questions: questions: 1. $\bar{\tau}$ is not introduced in line 58.
2.  Is it possible to remove the Lipschitz assumption?
3. If $\tau_k=0$ for all $k$, wiil the results of ASGD recover the results of SGD?
limitations: limitations: NA
paper_summary: paper_summary: For distributed machine learning tasks, Asynchronous Stochastic Gradient Descent (ASGD) is an indispensable optimization algorithm. Considering the existing results that fail to reveal the intrinsic impact of asynchronous training, this paper establishes sharper stability and generalization bounds for ASGD with convex loss function under much weaker assumptions, i.e., without Lipschitz assumption or smoothness. Furthermore, excess generalization error is investigated after deriving optimization upper bound. Several experiments validate these theoretical results.
strength_weakness: strength_weakness: - The authors provide the approximately non-expansive recursive property for ASGD. Without some limitations to $r$ and $\tau$, the terms $2\eta_k\beta^2r^2\sum\limits_{j=1}^{\tau_k}\eta_{k-j}$ in Lemma 3 and $\mathcal{O}\left(\eta_k\sum\limits_{j=1}^{\tau_k}\eta_{k-j}+\eta_{k}^{\frac{2}{1-\alpha}}\right)$ in Lemma 5 may be very large.
- There are some terms related to learning rates in almost all results, such as $\sum\limits_{k=1}^K\eta_k\sum\limits_{j=1}^{\tau_k}\eta_{k-j}$ in Theorem 2, $\sum\limits_{k=1}^K\tau_k$ in Corollary and $\sum\limits_{l=1}^k\eta_l\sum\limits_{j=1}^{\tau_l}\eta_{l-j}$ in Theorem 4. Therefore, these results may not converge but in the case with stringent learning rate conditions like Corollary 2.
- In the remarks of the key results, authors rarely compare their results with previous work, which prevents readers from understanding the advantages of the article sufficiently.
questions: questions: 1.Should the learning rate upper bound $\eta_k \leq 1/2\beta$ be $\frac{1}{2\beta}$?

2.The experiments authors conduct include non-convex tasks but their theoretical analysis doesn’t. In Concluding Remarks, the study of non-convex problems is one of the directions for future research. What is the aim of these additional experiments?
limitations: limitations: From Preliminaries and Algorithms, it seems that authors just consider the gradient update in a local worker but the server. Could the analysis of this paper be applied to the study of the server like Lian et al,. 2018, Deng et al,. 2023 and Chen et al., 2023? 

- X. Lian, W. Zhang, C. Zhang, and J. Liu. Asynchronous decentralized parallel stochastic gradient descent. ICML, 2018.

- X. Deng, T. Sun, S. Li, and D. Li. Stability-based generalization analysis of the asynchronous decentralized SGD. AAAI, 2023

- J. Chen, H. Chen, B. Gu, H. Deng. Fine-Grained Theoretical Analysis of Federated Zeroth-Order Optimization. NeurIPS, 2023.
paper_summary: paper_summary: This paper talks about the generalization error and the excess generalization error of Asynchronous SGD, mainly under convex, smooth or holder continuous conditions.
strength_weakness: strength_weakness: In th2, the generalization error is written as the form of containing w1 and wk. This is some what not reasonable. I want to see the generalization error which is depended on the already setting constants like η，K，n and so on, in this way, theorem can be applied to more situations.

In cor1, cor2 and th5, if we want the generalization bound to be small, then τk should be big. This is very strange, why is training with higher latency-update better, but poor with lower latency-update, this seems to contradict intuition and the real world?

I see your paper and experiment is talking about networks. I have some concerns about the connection between this article and neural networks.

1: May I ask if your theorems can guide the training of networks, or give some helps to training?

2: The f(w,z) is convex about w is a very strong conditions when considering network, if we see w as the parameters of network F, at this point, the f(w,z) is hard to be convex about w. I understand that ‘convex‘ is an important condition, and with this condition, many mathematical tools can be used， but for adapting to real-world-network-situation, is it possible for this condition to be more lenient?
questions: questions: Can we take τk=0 in this paper? At in this situation, can the result lead to the generalization bound of SGD?

In section 5, author replace smooth by holder continuous.  I don't quite understand the necessity of doing this. Can this be helpful in some practical problems or can it provides new mathematical tools?
limitations: limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work

Comments: title: Thanks for your response
Response
comment: Thank you for your time and acknowledgment of our submission. You are welcome to continue the discussion if you have any further questions.
Thank the authors for their careful responses. All my concerns have been well addressed, and I will raise my score.
Thank you for your time and acknowledgment of our submission. You are welcome to continue the discussion if you have any further questions.
Thanks, most of my concerns are addressed, and I would like to raise my score.
Dear Reviewer CbYp,

Thank you again for your selfless dedication and valuable comments. Considering the great effort we put in together on this submission, would you please give us some feedback on our response?

Best regards,

Submission2646 Authors
Dear Reviewer UzMC,

Thank you again for your selfless dedication and valuable comments. Considering the great effort we put in together on this submission, would you please give us some feedback on our response?

Best regards,

Submission2646 Authors
Thank you for your time and acknowledgment of our submission. You are welcome to continue the discussion if you have any further questions.
Thank you for your time and acknowledgment of our submission. You are welcome to continue the discussion if you have any further questions.
The rebuttal addresses my concerns and I will raise my score.
Thank you for the authors' rebuttal. Most of my concerns are well addressed, and I would like to raise my score.
Dear Reviewer UzMC,



We sincerely appreciate your valuable comments and eagerly await your assessment of whether our responses have sufficiently addressed your concerns. Please do not hesitate to contact us if you require any further clarification. 

Additionally, if our response has successfully addressed your concerns, we kindly request that you re-evaluate our paper and reconsider the score. Thank you very much for dedicating your time and effort to our submission.

We earnestly look forward to receiving your response.



Best regards,

Submission2646 Authors
Dear Reviewer CbYp,



We sincerely appreciate your valuable comments and eagerly await your assessment of whether our responses have sufficiently addressed your concerns. Please do not hesitate to contact us if you require any further clarification. 

Additionally, if our response has successfully addressed your concerns, we kindly request that you re-evaluate our paper and reconsider the score. Thank you very much for dedicating your time and effort to our submission.

We earnestly look forward to receiving your response.



Best regards,

Submission2646 Authors
Dear Reviewer pPuN,



We sincerely appreciate your valuable comments and eagerly await your assessment of whether our responses have sufficiently addressed your concerns. Please do not hesitate to contact us if you require any further clarification. 

Additionally, if our response has successfully addressed your concerns, we kindly request that you re-evaluate our paper and reconsider the score. Thank you very much for dedicating your time and effort to our submission.

We earnestly look forward to receiving your response.



Best regards,

Submission2646 Authors
Dear Reviewer yEhD,



We sincerely appreciate your valuable comments and eagerly await your assessment of whether our responses have sufficiently addressed your concerns. Please do not hesitate to contact us if you require any further clarification. 

Additionally, if our response has successfully addressed your concerns, we kindly request that you re-evaluate our paper and reconsider the score. Thank you very much for dedicating your time and effort to our submission.

We earnestly look forward to receiving your response.



Best regards,

Submission2646 Authors