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 2024 poster (2024)
Keywords: Asynchronous SGD
algorithm stability
generalization error
excess generalization error
Primary area: learning_theory
TL;DR: This study establishes sharper and broader stability and generalization bounds for the ASGD algorithm under much weaker assumptions.

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.

Stability and Generalization of Asynchronous SGD: Sharper Bounds Beyond Lipschitz and Smoothness
Xiaoge Deng
Tao Sun' Shengwei Li Dongsheng Li' Xicheng Lu
College of Computer Science and Technology National University of Defense Technology. China
dengxg@nudt. edu. .nd suntao. waltffsh@outtlon com, lucasleesw9@gmail.. com dsli@nudt. edu. en, xclu@nudt. edu. cn
Abstract
Asynchronous stochastic gradient descent (ASGD) has evolved into indispens- able optimization algorithm for training modern large-scale distributed machine learning tasks. Therefore, it is imperative explore the generalization performance of the ASGD algorithm. However, the existing results are either pessimistic and vacuous or restricted by strict assumptions that fail 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 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 asynchronous delay, model initial- ization, 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 computer vision and natural language processing.
Introduction
The last decade has witnessed explosive growth in the scale of models and datasets in the machine learning (ML) community [2] 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 [
40 19
An intriguing observation is that ML models learned by stochastic gradient descent (SGD) 335 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 200] PAC-Bayesian (7). uniform convergence (29 31, information-basee
and compression-basee -based bounds 3 50) In this
paper, we are going to study generalizability in the sense of algorithmic stability [8] This stability-
based analytical framework allows bypassing the model dimensionality so that we can focus on
Corresponding authors
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

exploring the generalization properties of optimization algorithms. Hardt et al. [17 investigated the generalization eπror of SGD on the basis of algorithmic uniform stability. Assuming that the loss function is convex, T--Lipschit and B-smooth, and running SGD for K iterations with a learning rate Te <2/B, they obtained upper bound the generalization error of O 2k=1 7k/ nk/n), where represents the total number of training samples. In recent work [23]. they proposed the on-average model stability and established tighter generalization bound of (1/nn) for low-noise settings, without requiring the I-Lipsshitz assumption.
Research on the generalization of asynchronous stochastic gradient descent algorithms mainly concentrates on parsing the effect asynchronous delay on algorithm stability and generalization. Leveraging the algorithmii uniform stability tool, Regatti et al. (33) presented upper generalization error bound of OLL2 ([L2K*T/p ((L"k=+/n3TT) in the non-convex case, assuming L-Lipschitz, f-smooth functions, and a decreasing learning rate. However, empirical experiments I show that this bound is too loose to reflect the effect of asynchronous delay on algorithmic stability accurately. Deng et al. [I3] directed their attention towards convex quadratic functions and established upper bound on the
generalization error as (((KFr)/m 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 [3] 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 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 (/1//++1/V// In contrast to existing work [13 (3), our results are non- con-vacuous and applicable to the general convex case.
For the first time, study the excess generalization eπrrr and provide upper bound of O(1/7 || w 111///n for ASGD, Our findings demonstrate that appropriately increasing the asynchronous delay, selecting good initial model, and increasing the number of training samples can improve the generalization performance.
Under the much weaker (a, () -ööldrr continuous gradient assumption, we establish an excess 4a.
|| /vn" w/ 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.
generalization error bound of OLL/ w
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 theoretical findings.
2 Related Work
Asynchronous training, with origins dating back at least to 65). has emerged as essential distributed method for training modern large-scale ML tasks. It effectively addresses the synchroniza- tion bottleneck among multiple workers and mitigates the straggler problem inherent in distributed systems This study focuses on the stochastic gradient descent algorithm with asynchronous 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]. is note- worthy that the aforementioned theoretical analyses are based on bounded or fixed delay assumptions, whereas recent studies
updates
30
[1] 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 77 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 R 16 36). For the mainstream SGD) algorithm, extensive stability -baed studies have been conducted for convex, non-convex, smooth and non-smooth cases [3] 17
54]. Recently, algorithm stability analysis has been extended to distributed training scenarios [48] Considerable research has explored the generalization performance
22
23
32
of distributed decentralized SGD from the stability perspective
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* /nf) of ASGD in the smooth non-convex case, where + represents the maximum delay. In a recent development, Deng et al. [33 established a tighter upper generalization error bound of O((K' - +)/mf) using average stability, and Sun et al. [41] investigated a proobbbibyyylity PAC-Bayesian generalization error bound ((L/Vn) 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 constrained by strict assumptions. Therefore, the objective of this study is to establish sharper stability and generalization bounds for ASGD under much milder assumptions.
3 Preliminaries
Notations. Lowercase and bold letters represent scalars and d-dimensional column vectors, re- spectively, The fz-norm of a vector x is denoted by ||x||_ Calligraphic capital letters represent mathematical sets. We write ((b) if there exists constant 0 < < +oc such that e b, and Ö()) hides logarithmic factors. Moreover, we denote b if (b)) and b (
Let X' S _e and y S 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 where each data point z; (x,, 14) E Z X' x ) is independently and
set S = (Zi..... . Zn identically distributed (i.id.) sampled from an unknown distribution D. We evaluate the performance of model w training sample with loss function f(w; z). The training process can be formalized as learning a model parameter E Ω C Rd to minimize the empirical risk, denoted as
min Fs(w) = 1 Σ f (w: w well
n
SGD the workhorse for solving the empirical risk minimization (ERM) problem iteratively updates the model parameter by W = W 7/6 V/Wk; R.,))
1.. which
ASGD is 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 225, 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 to update the model without waiting for gradient information from other workers. The ASGD procedure is described in Algorithm [ (located in Appendix A. 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'. 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 as
Wk+1 = W 1E (w.)))
where Wa; 7k, Tk, and Zig denote the model parameter, learning rate, asynchronous delay, and training sample at the k-tth iteration, respectively. It is worth noting that the index in chosen uniformly at random from the set n2).
3

---

For the model w learned through ASGD by minimizing the empirical risk ① on the training data set S. people are more concerned with its performance on the unknown distribution D, i.e. the following popular risk
F(w) Ff
The empirical risk ① and the popular risk (3) of 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 S as AS), and its generalization error defined as
Egen :- E [F((()) FssA(S))
(4)
The expectation here is taken over the randomness of the algorithm and the training data. This study is dedicated to bounding Egen by algorithmic stability, Let
S' [zi z S [z1,... 2;-1, Z,, Zit1, Z
(5)
S' is also data set i.idd sampled from the unknown distribution D, but is independent of the data set S = .zi..... }. S(() is perturbed data set formed by replacing the i-th sample in S with z, Based on these notations, Lei and Ying (3 defined the following on-average model stability.
Definition 1 (On-average model stability). A randomized algorithm A is on-average model Estab" stable if
1 ||(()) |((
S Estah-
Leveraging the smoothness (Definition 2 assumption, the connection between this algorithmic stability and the generalization error (gen is established the following lemma [Theorem 2, [3]]]-
Lemma 1. Let 7 > O. Assume that the function w w f(:; 2) is non-negative and 8-smooth for any the generalization error satisfies
z E Z. Then, algorithm A is on-average model Estab
Es,A (F(A(S) - Fs(A(S)) & 3 (Fs(A((((A(S) + 3+7 2 Estab-
7
While the smooth function assumption is common in optimization and generalization analyses
13 17 33 40), does impose constraints on the applicability (5. For instance, the hinge loss, which widely used in the MI. 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 to establish broader and fine-graine fine-grained generalization results. With the Hölder continuous condition, stability and generalization can be connected similarly to Lemma
(Definition 3),
Lemma 2 (Theorem 2. (23)). ). Let > O. For any z E Z, the function w + f(w; z) is non-negative, convex, and the gradient f((;; z) is (a,3))Höldte continuous. If algorithm is on-average model (stab-Stable, then the generalization error satisfies
C
Es,A (F(A(S)) Fs(A(S))) S
[F (A(S)) +
2 Cstab.
2n
Here, a E [0, 1], and Ca.3 is a constant dependent on a,
Furthermore, since the generalization performance of model is primarily reflected in the popular risk 3 this study also examines the excess generalization error, denoted 6ex where w* argminwen F(w) and
Eex-gon := Es.A (F(A(S)) - F(w"))
(6)
Definition 2 (Smoothness). The function w + f(w;z) is 3-smooth (3 > 0) if for any z E and w, E Rdd
[V((;z) V [[vvz)] < 3|
Definition 3 (Hölder continuous). Let [0, 11, 8 > 0. The function + Vf(w; z) is (a, B)-
Hölder continuous if for any 2 and w, Rd
fV(wwz) v fv z) S B -wwwvv v
It is noteworthy that the (a, -ööler continuous gradient is equivalent to a 9-smmooth function when
= Whereas a = 0 implies that the function gradient bounded, i.e., there exists a constant
L >> 0 such that / /V[(w (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 emror does not rely the bounded gradient assumption.

---

4 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 Ω C TRd is a bounded convex set. Then, for any w, V E S2 there exists constant
0 such that w v|| S
Assumption is standard in analyzing SGD and its variants, as it is easy hold with the projection operator [ 17 23 30 43). More specifically, we consider the following projected ASGD updates
Wk+1 = 11 Wa - "Je
Zi.
(7)
Since the projection operator 1I is non-expansive, it has no impact on the stability and generalization analysis of the ASGD algorithm.
Remark 1. Let Wa and w (4) denote the models produced by ASGD 7 after & iterations on the follows that || - - S r. Notably, this result is intuitively understandable as the datasets S, S differ only by a single sample, and the initialization the same (w, = w()).. In contrast to a recent work (55), where the authors assumed normal distribution with bounded mean and variance for the difference between models Wy and w our study does not necessitate such a strong assumption.
datasets S and S (defined in (5)), respectively. According to Assumption
(6)
4.1 Algorithmic Stability of ASGD
The stability -base analysis of SGD hinges significantly on the non-expansiveness of the gradient update operator 17 233 Namely, if function J is convex and smooth, then vw,, St E
|w [)(w;) (v 7/ /V;((z
||w -vll.
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.
Lemma 3. Let the loss fanction be convex, B-smooth, and Assumption I holds. Denote w and w (3) as the models produced by ASGD 7 with learning rates S 2/3 for K iterations on the datasets S and 8(0,, respectively. Then
[W - 774 V (w
Zi.) (w)) mh V Zi. 1)
Wx w (011 82,2
n--
By leveraging the properties established Lemma we can demonstrate an approximately non- expansive recursive property for || W stability (Definition]) I of the ASGD algorithm follows.
(2) 2 and subsequently establish the on-average model
Theorem 1 (Stability). Suppose the loss function is non-negative, convex, and B-smooth. Let Assumption 7 holds. we run ASGD (7) with a non-increasing learning rate тыk S 1/23 for iterations, then the on-average model stability satisfies (c is the natural constant)
Estab 163e(1 - k/n) Mi millwi w"1 (43r2 2F(w"))
Σ
m
+ 2,3
n-
increasing the number of training iterations impairs the stability of ASGD. Compared SGD 233 we introduce an additional term O m Σ}= m--)) characterize the effect of asynchronous delay on the stability of ASGD. Also similar the data- dependent stability study (22). Theorem indicates that model initialization affects the algorithmic stability, i.e., selecting better model initiation point w can effectively improve the stability.
In line with the findings of study
4.2 Generalization Error Bounds
Together with Lemma T and Theorem we can now present the generalization emorr 44 of the ASGD algorithm under smooth conditions.
5

---

Theorem 2 (Generalization enror). Let Assumption 1 holds, and assume that the loss function is non- negative, convex, and B-smooth. Running ASGD 7 with a non-increasing learning rate TiK S 1/2, for K terations, then the generalization error is given by
'gen = -O(Fs.((Fs(MA))
1 K/n I/k
n
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 W1 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 reveals close relationship between the generalizability of ASGD and the learning rate. As discussed in Section 2 asynchronous training typically utilizes delay-inverse corre- lated learning rates to ensure algorithmic performance. In the low-noise case, namely, F(w") = 0, Stich and Karimireddy [40] demonstrated that Fs( = (11/V/) for ASGD under the condi- tions of smooth and general quasi-convex loss functions, with a learning rate of 1/2- - c( Employing this learning rate strategy, the following corollary can be derived.
Corollary 1. Let F(w*)=(O -0, 0, K xn, and the conditions specified in Theorem 2 hold. If we set the learning rate пи c(F K) with a constant c >> 0 and 7 =E Tk/K, then the generalization error satisfies
1 )
Es,A (F(Wk) - =s(ww)]==
At this point, although the asynchronous training also introduces additional generalization error term of O(1/T), increasing the delay can instead mitigate this detriment. Unlike previous ASGD generalization research [14. (33, this study does rely the Lipschitz assumption. In contrast to the vacuous upper bound of (K* /nf) in [33], we provide a sharper result and demonstrate that increasing the asynchronous delay reduces the generalization error. While Deng al. [I3 present a similar result O((K -00- ff//f) with respect to the maximum delay 7 in the convex quadratic optimization, our bound holds in general convex settings. Furthermore, results are associated
with the average delay F rather than the pessimistic maximum delay f in B3 33
4.3 Excess Generalization Error
According to definitions 4 and (6), the excess generalization error Exx-gen can be decomposed
Gex-gen
Cgen + Es.A (Fs(A(S)) - Fs ),
(8)
where 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 + V fw: z) is bounded. That is, for any W E Q2 z E Z, there exists constant
such that [V; 2) S 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.c., || Wk- S L LE fk--j
1==1
For the excess generalization error of ASGD, we shift our focus to the average model WK Ek_ w Ek= M7.- It is noteworthy that since the parameter space is a convex set, Wk E Ω 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-negante non-negative, convex, and B-smooth. Let Assumptions hold, we run ASGD (7) with non-increasing learning rate m) 1/28, then the optimization error satisfies
Es.A - Fs(w"), 0
||1 w011 + (1+F(w"))
k== The
ΣK_
Mike >i= 1)=
+
1= 7h
k= 7
Σk

---

Theorem 3 (Excess generalization error). Let Assumptions 7 hold, and assume that the loss function non non-negative, convex, and Smoohhh. Running ASGD / with the non non-incree increasing learning rate Tj S 1/ 2 for K iterations then the excess generalization error is
Gex-gen =0 -0
K k=
14 K/n
K
F(w*)
+
Th W1
ww11 + (1 F(w*)
T
72
[1
w=l
K
k
K
K k= 1 1k
The mT
+
Th
==1
Compared to the generalization enror in Theorem 2 the excess generalization error is no longer explicitly dependent on the optimization error Fs((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 x and the conditions in Theorem hold. Set the learning rate as Tlk K)= with a constant >> 0 and F = Ex=1 Tw/K. K. Then if < K3, the excess generalization error satisfies
| w=ll
Es.A (F(WR) - F(w")] = 0
n
To the best of our knowledge, this is the first excess generalization error result for the ASGD algorithm. Compared to Corollary | this generalization bound with appropriate delays is sharper and no longer relies on the optimization error result in [40].
5 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 similar technical roadmap in Section [ Firstly, derive the stability of ASGD by leveraging the approximately non- non-cxpansive 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 in the smooth case, which has not been explored in existing research. Please refer to Appendix forr the proof details of this section.
Lemma 5. Let Assumption I holds, and assume that the loss function is non-negative, convex, and has (ax, HHörrr continuous gradient. Then, the delayed gradient update operator satisfies
W The Vf(w : 2
((w(()
( R-TZ 211 = || (8) 12 mk- T
Compared to Lemma
3 additional term 0mp-a) is introduced here to compensate for the
absence of smoothness. Fortunately, since the coefficient of [ww, w (1) is not larger than 1, the delayed gradient update of ASGD remains approximately non-expansive 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 (Stability). Suppose the loss function is non-negative, convex, and has (a, -HöHöee continuous gradient. Let Assumption 7 holds. Then, the on-average model stability of ASGD satisfies
1+ k/n
Estab
O
P.s. A F5 (w/nz)
+
Σ 1=1
m
m
M
1=1
7

---

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 I7 with the loss function value, which leads to sharper stability and generalizability results when combined with the subsequent optimization analysis. Substiuting 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 I 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 (ax, 3-Hölder con- tinuous gradient. Let Assumptions non-increasing learning rate satisfies
7 andd 2 hold, then the optimization error of ASGD 7 with
W1
1²1 + ΣX
k= 7K 21=1
Tk-1
Es. (ss.A(F(WK)--B Fs((
Σk 17
TFa
K
2a
1=
71 W1 w (1+
Σ
2
7k
===1
k=
Theorem 5 (Excess generalization error). Let Assumptions hold, and assume that the loss function is non-negative, convex, and has (ax, 3--Hölder contimuous gradient. Running ASGD 7 with the learning rate mh c(TvK)-1 1 for K xn iterations, then if F((") and the average delay satisfies 7 < Ka' with a' min { 3 3-2a }. the excess generalization error is
Es.A ((wx) F(w"((()))))) = 0 (+7 |[
Notably, the generalization performance decreases in the non-smooth case, but the underlying properties remain consistent with the smooth setting (Corollary ( 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/vn (/)). This outcome is consistent with the findings from the study of the SGD algorithm in (23). but without requiring more computation K x nia.
Experimental Validation
In this section, we extensively evaluated various machine learning tasks under the distributed pa- rameter server architecture 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 distributed system with M M= 16 workers and performed asynchronous training in a more general stochastic gradient descent format as follows
Σ
Wk+1
TJk
8K-TE
MEMA
Here, M₁ is non-empty subset of {1. {I..... M} containing the workers that participated in asyn- chronous training at the k-th iteration, and gh- represents the delayed gradient computed by worker model W 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/7 for different delays, where 7 denotes the average delay.
For the convex optimization problem, we employed a single-layer linear network with the mean squared error for classification task on the RCV1 data set from the LIBSVM database [00] This data set contains 20, 242 training data with 47, 236 features per sample. In the field of computer vision, chose the popular ResNet18 model for image classification on the CIFAR10 and CIFAR100

---

1e-2
T-4
T
1.6
Cemeraliznn cemeralization crror
Generalization error
aatioalizatoon
12
T-8
1-16
t-32
0.8-
0.4
0.0
0.4
1.0
104
Iteration
(a) Convex optimization on RCV1
(b) CV task on CIFAR100
(c) NLP task on SST-2
The generalization errors of three categories of machine learning models trained using ASGD with learning rate 7パk 0.1/F. The horizontal axis denotes the number of asynchronous training iterations, and the legend represents the average delay. degradation in generalization performance is observed as the number of training iterations increases, and the generalization performance can be improved by appropriately increasing the asynchronous delay.
Figure 1:
datasets. ResNet [88, 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 x 32 pixels. For natural language processing tasks, conducted experiments using BERT on the SST-2 task within the GLUE platform [47]. BERT [T5] 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 models and calculate the on-average model stability (Definition [ Instead, we construct a perturbed data set (t) 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()) Repeating the process multiple times, take the average value 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.
Figure I and Figure 2 (located Appendix D) illustrate the generalizability and stability of the ASGD algorithm in training the three types of machine learning tasks. The experimental results show that continuous training impairs the stability and generalization of ASGD, which is consistent with the theorems presented in Sections and Conversely, when training with 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 consistent with the theoretical bound in Corollary which utilizes the specific learning rate c/F.
4
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 enror 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-vace van-uuu 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-independee learning rates (Figures 3 and in Appendix D). Interestingly, these results also suggest that asynchronous training is beneficial for generalization. This empirical finding challenges the pessimism of our generalization error result under constant learning rates (omitted in Appendix [B.4), and motivates further exploration of the generalizability of ASGD. There are several directions for future research. The study of non-convex problems can focus on showing that asynchronous updates are approximately non-expansive even without convexity, then leading to non-vacuous stability and generalization results. Another avenue for research involves investigating tighter high probability bounds that attenuate the dominant role the learning rate on generalization, thereby elucidating the experimental phenomena in Appendix

---

Acknowledgments and Disclosure of Funding
This work is sponsored in part by the National Natural Science Foundation China under Grant No. 62025208, 62421002, and 62376278, Hunan Provincial Natural Science Foundation of China (No. 2022JJ10065), Young Elite Scientists Sponsorship Program by CAST (No. 2022QNRC001), Continuous Support of PDL (No. WDZC20035250101),
References
[1] Alekh Agarwal and John C Duchi. Distributed delayed stochastic optimization. In J. Shawe- Taylor, R. Zemel, P. Bartlett, F. Percira, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
[2] Yossi Arjevani, Ohad Shamir, and Nathan Srebro. A tight convergence analysis for stochastic gradient descent with delayed updates. In Aryeh Kontorovich and Gergely Neu, editors, Proceedings of the 31st International Conference on Algorithmic Learning Theory, volume 117, pages 111-132. PMLR, 2020.
[3] Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach. In Jennifer Dy and Andreas Krause, editors, International Conference on Machine Learning. volume 80, pages 254-263. PMLR, 2018.
[4] Mahmoud Assran, Arda Aytekin, Hamid Reza Feyzmahdavian, Mikael Johansson, and Michael G Rabbat. Advances in asynchronous parallel and distributed optimization. Pro- ceedings of the IEEE,
2020.
[5] Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 4381 4391. Curran Associates, Inc., 2020.
[6] Gérard M Baudet. Asynchronous iterative methods for multiprocessors. Journal of the ACM (JACM), 25(2):226-22) 244, 1978.
[7] J Frédéric Bonnans and Alexander Shapiro. Optimization problems with perturbations: A guided tour. SIAM review, 40(2):228 264, 1998.
[8] Olivier Bousquet and André Elisseeff. Stability and generalization, Journal of Machine Learning Research, 2:499-5200 2002.
[9] Tom Brown, Benjamin Mann. Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Vone Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1877-1901. Curran Associates, Inc., 2020.
[10] Chih Chih-Chung Chang and Chih-Jen Lin. LIBSVM: library for support vector machines. ACM Transactions Intelligent Systems and Technology, 2:27:1-27:27, 2011.
[11] Alon Cohen, Amit Daniely, Yoel Drori, Tomer Koren, and Mariano Schain. Asynchronous stochastic optimization robust to arbitrary delays. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 9024-9035. Curran Associates, Inc., 2021.
[12] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In 2009 IEFE Conference on Computer Vision and Pattern Recognition, pages 248-255. IEEE, 2009,
10

---

[13] Xiaoge Deng. Li Shen, Shengwei Li, Tao Sun, Dongsheng Li, and Dacheng Tao. Towards understanding the generalizability of delayed stochastic gradient descent. arXiv preprint (iXiv:2308.09430 2023.
[14] Xiaoge Deng, Tao Sun, Shengwei Li, and Dongsheng Li. Stability-bard based generalization analysis of the asynchronous decentralized SGD. In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pages 7340-7348, 2023.
[15] Jacob Devlin, Ming-Wor Heig-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT:
Pre-training of deep bidirectional transformers for language understanding. In Jill Burstein, Christy Doran, and Thamar Solorio, editors, Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 4171 1186. Association for Computational Linguisties, 2019.
[16] Andre Elisseeff, Theodoros Evgeniou, Massimiliano Pontil, and Leslie Pack Kaelbing. Stability of randomized learning algorithms. Journal of Machine Learning Research, 6(3):55-79, 2005.
[17] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochas- tic gradient descent. In Maria Florina Balcan and Kilian Q. Weinberger, editors, International Conference on Machine Learning. volume 48, pages 1225-1234. PMLR, 2016.
[18) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Puttern Recognition, pages 770-778, 2016.
[19) Anastasiia Koloskova, Sehastian U Stich, and Martin Jaggi. Sharper convergence guarantees for asynchronous SGD for distributed and federated learning. In S. Koyejo, S. Mohamed, A. Agar- wal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 17202-17215. Curran Associates, Inc., 2022.
[20] Vladimir Koltchinskii and Dmitriy Panchenko. Rademacher processes and bounding the risk of function learning. In High dimensional probability II, pages 443-457. Springer, 2000.
[21] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. pages 32-33, 2009.
[22] Ilja Kuzborskij and Christoph Lampert. Data-dependent stability of stochastic gradient descent. In Jennifer Dy and Andreas Krause, editors, International Conference on Machine Learning. volume 80, pages
PMLR, 2018
[23] Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In Hal Daumé III and Aarti Singh, editors, International Conference on Machine Learning, volume 1 119, pages 1809-5819 PMLR, 2020.
[24] Yunwen Lei, Ting Hu, Guiying Li, and Ke Tang. Stochastic gradient descent for nonconvex learning without bounded gradient assumptions. IEEE Transactions on Neural Networks and Learning Systems, 3 31(10):4394-400 2019.
[25] Mu Li, David G Andersen, Jun Woo Park, Alexander Smola, Amr Ahmed, Vanja Josifovski, James Long. Eugene J Shekita, and Bor-Yiigg Yúing Su. Scaling distributed machine learning with the parameter server. In 1 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14), pages 583-598. USENIX Association, 2014.
[26] Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
[27] David A McAllester. PAC-Bayesian model averaging. In Proceedings of the twelfth annual conference on Computational learning theory, pages 164-170. Association for Computing Machinery, 1999.
11

---

[28] Konstantin Mishchenko, Francis Bach, Mathieu Even, and Blake E Woodworth. Asynchronous SGD beats minibatch SGD under arbitrary delays. In S. Koyejo. S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 420 433. Curran Associates, Inc., 2022.
[29] Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain generalization in deep learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. Alché-Buce E. Fox, and R. Garnett, editors, Advances Neural Information Procexsing Systems, volume 32. Curran Associates, Inc., 2019.
[30] Angelia Nedić, Dimitri P Bertsekas, and Vivek S Borkar. Distributed asynchronous incremental subgradient methods. Studies Computational Mathematics, 8(C):381-40) 2001.
[31] Jeffrey Negrea, Gintare Karolina Dziugaite, and Daniel Roy. In defense of uniform conver- gence: Generalization via derandomization with an application to interpolating predictors. In Hal Daumé III and Aarti Singh, editors, International Conference on Machine Learning, volume 119, pages 7263-7272 PMLR, 2020.
[32] Anant Raj. Lingjiong Zhu, Mert Gurbuzbalaban, and Umut Simsekli. Algorithmic stability of heavy-tailed SGD with general loss functions. Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, volume 202, pages 28578-257888 28599728977. PMLR, 2023.
[33] Jayanth Regatti, Gaurav Tendolkar, Yi Zhou, Abhishek Gupta, and Yingbin Liang. Distributed SGD generalizes well under asynchrony. In 2019 57th Annual Allerton Conference on Commu- nication, Control, and Computing (Allerton), pages 863-870. IEEE, 2019.
[34] Zhaolin Ren, Zhengyuan Zhou, Linhai Qiu, Ajay Deshpande, and Jayant Kalagnanam. Delay- adaptive distributed stochastic optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5503-5510, 2020.
[35] Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Statistics, 22(3))4000440) 1951.
[36] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. Journal of Machine Learning Research, 16600):235-26700 2010.
[37] Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Ng. and Christopher Potts. Recursive deep models for semantic compositionality over sentiment treebank. In David Yarowsky, Timothy Baldwin, Anna Korhonen, Karen Livescu, and Steven Bethard, editors, Proceedings of the 2013 Conference Empirical Methods in Natural Language Processing, pages 1631-1642. Association for Computational Linguistics, 2013.
[38] Suvrit Sra, Adams Wei Yu, Mu Li, and Alex Smola. Adadelay: Delay adaptive distributed stochastic optimization. In Arthur Gretton and Christian C. Robert, editors, Artificial Intelligence and Statistics, volume 51, pages 957-965. PMLR, 2016.
[39] Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. In
J. Lafferty, C. Williams, J. Taylor,, R. Zemel, and A. Culotta, editors, Advances in neural information processing systems, volume 23. Curran Associates, Inc., 2010.
[40] Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for SGD with delayed gradients and compressed updates. Journal of Machine Learning Research, 21(237):1-36, 2020.
[41] Jianhui Sun, Ying Yang, Guangxu Xun, and Aidong Zhang. Scheduling hyperparameters to improve generalization: From centralized SGD to asynchronous SGD. ACM Transactions on Knowledge Discovery from Data, 17(2):1-37, 2023.
[42] Tao Sun, Robert Hannah, and Wotao Yin. Asynchronous coordinate descent under more realistic assumptions. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
12

---

[43] Tao Sun, Dongsheng Li, and Bao Wang. Stability and generalization of decentralized stochastic gradient descent. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages
2021.
[44] Tao Sun, Baihao Wu, Dongsheng Li, and Kun Yuan. Gradient normalization makes heteroge- neous distributed learning as easy as homogenous distributed learning. arXiv preprint, 2024.
[45] John Tsitsiklis, Dimitri Bertsekas, and Michael Athans. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE Transactions Automatic Control, 31 (9)8003-122, 1986.
[46] VN Vapnik and A Ya Chervonenkis, On the uniform convergence of relative frequencies of events their probabilities. Theory of Probability & its Applications, 16(2):244-280, 1971.
[47] Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. GLUE: A multi-task benchmark and analysis platform for natural language understanding, In International Conference on Learning Representations, 2019.
[48] Xinxing Wu, Junping Zhang, and Fei- Yue Wang. Stability- based generalization analysis of distributed learning algorithms for big data. IEEE Transactions Neural Networks and Learning Systems, 31(3):801-812, 2019.
[49] Xuyang Wu, Sindri Magnusson, Hamid Reza Feyzmahdavian, and Mikael Johansson. Delay- adaptive step-sizes for asynchronous learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, volume 162. pages 24093-24113, PMLR. 2022.
[50] Aolin Xu and Maxim Raginsky. Information c analysis of generalization capability of learning algorithms. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, Vishwanathan, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[51] Yiming Ying and Ding Xuan Zhou. Unregularized online learning algorithms with general loss functions. Applied and Computational Harmonic Analysis, (2(2):224-244) 2017.
[52] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017.
[53] Wei Zhang, Suyog Gupta, Xiangru Lian, and Ji Liu. Staleness-aware async-SGD for distributed deep learning. In Subbarao Kambhampati, editor, Proceedings of the Twenty-Fift International Joint Conference on Artificial Intelligence, pages 2350-2200 2006.2356..2 JJCALAAAI Press, 2016.
[54] Yikai Zhang, Wenjia Zhang, Sammy Bald, Vamsi Pingali, Chao Chen, and Mayank Goswami. Stability SGD: Tightness analysis and improved bounds. In James Cussens and Kun Zhang, editors, Uncertainty in Artificial Intelligence, volume 180, pages 2364-2373, PMLR, 2022.
[55] Tongtian Zhu, Fengxiang He, Lan Zhang, Zhengyang Niu, Mingli Song, and Dacheng Tao. Topology-aware generalization of decentralized SGD. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, volume 162, pages 27479- -7503. PMLR, 2022.
[56] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, pages 928-936. AAAI Press, 2003.
13

---

Appendix for
Stability and Generalization of Asynchronous SGD: Sharper Bounds Beyond Lipschitz and Smoothness
A Background Knowledge
A.1 ASGD Process
In the distributed parameter server architecture, the distributed workers are responsible for computing gradients, while the model updates oceur on the parameter server side. Upon receiving the gradient from worker, the server immediately utilizes it to update the model without waiting for gradient information from other workers. The ASGD procedure is described Algorithm T
Algorithm Asynchronous SGD
Initialization: model parameter
Input: learning rate ?
// Worker
1: repeat
2: pull the current model from the server
3: compute gradient g =""VV[(;:)) with local data z
4: push g" to the server
5: until terminated
// Server
6: if server received gradient from any worker m then
7: update the model as w <- w 77
8: 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. be specific, while worker m 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 [ is inconsistent with the model updated by the server (w in line of Algorithm| I This characteristic renders ASGD delayed gradient update, expressed as
Wk+1 W/ - 17x V ff
where Wi: M,, Tk, and zi, denote the model parameter, learning rate, asynchronous delay, and training sample at the k-th iteration, respectively. It is worth noting that the index ig is chosen uniformly at random from the set (1....,n..
A.2 Useful Inequalities
Our analysis frequently uses the following inequalities. Lemma A.1 (Young's inequality). If 1 and q > 1 are real numbers such that for any a, E gt,
1, then
1 6a. ab < -a" +
(A.1)
q
14

---

Lemma A.2 (Cauchy-Schwarz Schwarz inequality). For any V E R the the following inequality holds.
(w.v) |w|l ||vll
(A.2)
Lemma A.3. Let p 0. For any a, b R+, the following inequalities hold.
Zab pa + 18.
(A.3)
1 )62
(a + b)2 < (1 p) (1
(A.4)
In addition, rely the self-bounding properties of the smooth and Hölder continuous gradient functions. The proof can be found [24] 39 [1].
Lemma A.4. the function w + f( [w; z) is non-negative and the gradient f is (a, -)-Hler continuous (Definition 3 with a E [0, 1 3 > O. Then for any w, 2, we have
IVS(w; 2| S Co.3. T=o (w;z),
(A.5)
where the constant Co. is defied as
(1 1/4) sup2 [V: + if a=
if
Go,8
(A.6)
Remark A.1. The case a = implies that the function w + f(w; z) is B-smooth (Definition this point, the constant C /233 and the gradient satisfies
2 At
[V 2)1 - 2Bf(w;z).
(A.7)
Lemma A.S. The projection operator is defined as ll argminwen |w and this operator non-expansive, i.e.
[[[](w)= [1((v)l < |w Vw, e ad and [[][()) w|l | w V w E Ω.
(A.8)
The proof of Lemma A.5 can be found in [66. This non-expansive property not only ensures the plausibility of Assumption T but also facilitates the stability and generalization analysis of the projected ASGD algorithm 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 D and Lemma were established by Lei al. [Theorem 2, [23]] The following proof is derived from [Appendix B. [23]]. Recall the following definitions
S == (Z),..., 2, 1, Zit1..... 2n.. S' = ( ................................ 2/1
5(0) (Zi..... 2, z 2......., znd.
and
Fs(w)= = 1 Σ f(w:zz), Egen := Es.A (F(A(S)) - Fs(A(S)))
F(w) = (w)))
==1
(A.9)
Since for any i, the data samples z; and zł, are both drawn i.i.d. from D, then A(S()) is independent of z; and we have the following fact
Es(F(A(S)) = =Ess.))((A((S));
Σ Es.s ((((S()) z.)].
Hence, the generalization error satisties
- Σ f(A(S):)))
Egen = ES.A (F - Fs(A(S))) = Es,A
Es (s((S( );:)] -
1=1
(A.10)
n Es.s..A -()A()))))
7
15

---

By incorporating the B-smoothness property of the function w + fww we have
Es,4 -F(A(S)) -
Σ
"
S , )(1441)) 6
(A(S))
(A.11)
Using the inequalities (A.2).
A.3
and self bounding property
A.7
let y > then we know that
( ( Vf(A(S): - ||A(s()) - [(S))
< 2 14(00(0))
A(8)] -
1 [VS(A(():
2-
s (A((S - _
A(S)II
((A(S))))
Substituting back into inequality (A.11) yields
8
72 f()(S);z))
+ B+7
n [|A(S)) A(80))1
Es.A (F(A(S))=Fs(A(())
E
7
2
7
By further combining with A.9 and Definition
Lemma
is thus derived, i.e.,
8 (F.s(F(()(S))
B +
Es.A (F(((S)) Fs(A(S))
Cstab.
(A.12)
7
Without the smoothness assumption, we then need to utilize the convexity property of the function f(w; i.e i.e.
);)) - ((A();2)) < (A(S()) - A(S), ([(A(S(0);24)
(1A(8 A(S))I + (VS(A((()) 21))
$ 2
27
2 (A(00) A(S)]I+ +
Ca.3
f T (A(S(i)); 2;).
2
24
where the last two inequalities use (A.2)
A.3) and the self- self-bounding property A.5
Substituting
back into inequality (A.10) leads to Lemma i.e.,
ES.A [F(A(S)) Fs(A(S))
2. 1
Es.s ,A 1 Ao (A(S )zi)
+ 7
Es.S' i
[ n i=1
Σ
||A(S)
A(8(0)11)))
27 n
(A.13)
2a.9 Es, A [ 14 (A(S))) + 2 Estab.
< 27
Here we use the concavity of the map x + rea and the following fact
Es. [ (A(8(i));)) 5 Es.. [[A,[((((S()))..))) 1a
Es,,' + (A(S())) EE.A
[F 2 (A(S))
B Proof of Stability and Generalization Bounds (Section 4 in the main text)
B.1 Proof of Lemma (approximately non-expansive property delayed gradient updates)
Due to that the function w + f(w:z) is convex and 3-smoohh, the gradient V is co-coercive, namely
(W--e W. WR-T Vf(We-rzi izi V/ i 2 | (2 (W k- 11.
16

---

Using this co-coercivity with learning rate 77 S 2/5, we have
[w TJe V f[w R- Zi.) (w (6)
7M V f( (w (6) b-TH" 2in,)) )1
=lIws
(6)
12 n V WW 33 VS(w
()) KーTH Fig )1
lc
27T (wk w
Vf(w (8)
Zin))
-l/Wk
l. + n
(6)
W ) V :zze)12
27T (Wk Tz
w (8)
W
V f k-Te mine)
2TJ (Wh Wk- (w
V f/(ww=n'
V Vf(ww (6)
k- zir))
< ||Ws- (0) 21 ( (Wk- Wk-Te (wk
k - V/(W 2i.) VV/VV/ k-r 22.))
From the iterative scheme of ASGD we know that
(W*- WK-Tk - (w/ k (WRR-TH Zin)
(1)
VS( k- Zin. ))
WA-j+1 Wk-j (w 1- Vf(Wk-rui V f k-7z zin))
Tk
Tk- / ) k- 2i, l:
()
(B.1)
where the last inequality is due to (A.2) and A.8
Following the 3-smooth property and Assumption
we can derive
V/(W z.,)l S 8
w S Br, for 8 = k; k - j: j 1,
Tk-
(B.2)
With inequalities B. and B.2 we are arrive at
Wk The V/(Wk- ;2,) - (w?" (6) Ti f k (())))))))))
Wk - hok--(()) w2 2m b2,2
m---j
(B.3)
B.2 Proof of Theorem 1 (algorithm stability under the smooth assumption)
Let wa and w sti), respectively. Given that the index in at the k-th iteration is chosen randomly from the set {1, ... ................. there is probability of 1 11n that in * i. Then, by the approximately non-expansive property (B3) of the ASGD iteration and (A.8), we have
(8) denote the models produced by ASGD ( after & iterations on the datasets S and
W
12 <
Ww: 7h V f(W
(w
T7s f :z.))
Wk w (2) 12 27 ,2,
m--s-
On the other hand, there is a probability of 1 1/n such that the algorithm accurately selects the i-th sample point (ix- i) that is different in the two datasets S and S(i) In this case, can perform the following analysis based on the inequality (A.4) with > O, self-bounding property (A.7) and non-expansive projection A.8)
| w 2
(8)
WR 7h V/(WW :2:)
(
Th V ( iz)) (3)
< <1+p)) W/ w
( k
12 (1 1/+11/mm
Vf(w
TT 21
<1 W/ - -( (0) 2(1 + 1
W 2:) 12 + V (w =
< (1++))|l w - -w 4331 + 1/2) [(W 22 x)+ ʃ (4) kー 24)
17

---

Combining the two cases above and taking the expectation with respect to the randomness of the algorithm yields
w 1112+ 2Tx 32x:3222(n
Th π
EA Wk+1 w
S(1+ R)AA
n
43 + 1/p) EA [(WW-rz22)) + 1 s( kW 24i
Since 2; and 2/ are i.i.d. sampled from the same distribution D, we have the following fact
A subsequent expectation over the randomness of data produces
Bs,s Wk+11
(6) Wk+ll
P (1 Bs
+
- 11
83(1 + 1/p)n
ES.A [f( (f(WW-re + 2n 82,2
Σ
j=l
Py (k-1)
ES,A [f(Winn 2i]] + 3 88(1 + 1/p)ni
n M
n
j=1
where the second inequality due to the same initialization Wi (1+ + (/n)(k-1) S (where is the natural constant), and the on-average model stability of ASGD satisfies
w
Let p n/k, then
ES, A
W
(1) 113 W++Il
71
+ 72
P 2y(k-1) (1-
[8 + 1/p)m
ES.A [Fs(wi-n) + 3mp
7
? ?/-
n
j=1
(B.4)
< (1 + 2y (k-1)
188(1 1/p)
PE FF 2
TL
171
171
n
n
j=1
88e(1 + k/n)
ES.A 1)
111
T--j-
7
[=1
5=1
For the further investigation of the algorithm stability of ASGD, it is imperative to bound error Et E... FFFFs..Fs(WW))) (Fs((: of the delayed model. With the ASGD update 77) inequality (A.8).
convexity and smooth property (A.7). we have the following derivation
| 12 < || Th V (fw((ww (Wk-Tui 2i,) w²
|| 2² + 12 [[]lV/(Wa-a (W Zi. )12 + (w" Wk. Vf(Wk- Zix))
< || w012 + 2,3 f f(wk- Z.n.) + 277 (w- WK-TE: Vf( Zia
+ 27 (W (W--L WE. V/(W n. kin)))
< |W w w01 + 2, ( (W 2.d + 27k (f([f;;;; f Zix
+ 2m (Wh-r Wk. V /f(w=-- Ziz
W/ w w01 / W 2ix 21 (w"": zi.)) (Wk/WWKTT WK, W/(Wk-r,i2h))
where w' E argmin F ((w), and the last inequality is due to 1Js S 1/2.3. Then
ma fof(Ww-rr 2 Wx w | w0 27x f(=": Zie
(B.5)
+ 21T6 21 (WK-TE - WK. (W(Wknzzii
18

---

Following the inequality A.2 self- bolndinn property A.7 and Assumption |
we know that
21/x WK. - We: V :2.))) 2r7H V (w
T Zz S 2r7hs V 235(Wx-ra
- 2r 2,8 223k2
(Wk7Zi - 4 T)s
+
f(Wk-Ti Bin);
2
where last inequality uses A.3 with p = Turning to B.5 we have
mef(Wk-TA" Zic) W/ w "1 Wk+1 w I12 + 4mxf(w' (w":: + 88r2
Multiplying both sides with the non-increasing learning rate, we get
n Z 277 [ w²12 2 27/++1 ||-+1 - w= + 4n fw'f(w": : 88
Taking expectation on both sides followed by summation leads
k
k o F(w") 83,,
Σ
(FF 2m [| - 1| +
Σ
n
(B.6)
where we use Is [f(": zi. ==(FF((*s)) = F(w*). Substituting B.6 into
B.4
we are arrive
n Wk+1 - w (1) 1
E
Es,
n
163c(1 + k/n)
k
- aallw-w"Il"
mi F(w") + 45r Σ 1=1
+
2
m-
1=1
1=1
f=1
(B.7)
B.3 Proof of Theorem 2 [generalization error under the smooth assumption)
Together with Lemma A. 12 and Theorem B.7). we have
8+7
1
Es.A [F(W - Fs(( < Es. (F
ES..
Wk+11 w R41 1
2
i=1
8
83e(B + +1) k/n)
[ss 7
mllwi w112 Σ
mi F (w"" + 4.3r
2 m
k
+ + + d) Σ
7 Σ n n-j-
j=1
(B.8)
Let 1, then the generalization enror Egen of ASGD satisfies
Es.A (F(Wk)= Fs(WK))
= -o (F(ssAlFF((W))
Σ
K
11
The 1+K/n
nl
+
71 [w - w (1+ F(w"))
Σ n
j=1
(B.9)
B.4 Proof of Corollary I (generalization error with specific learning rates)
we use the delay-independens constant learning rate 7h = 77 the generalization eгrоr Egen satisfies
Let K x n. Following Theorem
2
B.9 9
Es.A [F(Wk) Fs(WK)]
Σ
Th
w1 Wi
+ ESS.|[F((Wx. F(w"))) (B.10)
n
1=1
19

---

In comparison to SGD 23 asynchronous training with fixed learning rate 7) introduces an additional error O Th) due to delay. This error accumulates as iterations increase, which subsequently deteriorates the generalization performance of ASGD. However, the experimental results in Appendix dddmonstrrtee that the generalization enror bound in (B.00) is pessimistic.
In the low-noise case, i.e., [ww")= = Stich and Karimireddy 440 proved that Fs(wk)=0(1/V under the smooth and general quasi-convex loss function conditions with the learning rate = c(TVK)- (c>00s constant, 7 = >
Ziml Tk/ K). At this point, the generalization error of ASGD is
TR/K).
1+ K/n
W1
W
E [F(WK) Fs(wx)] 0
+ 0
Tk
v K
TVK
KT
k=
1
0
VK
Remark B.1. Under the assumptions of 3-smoothness and (M, (M,,o")-oundde' noise, Stich and Karimireddy [40] proved that Fs(wx) = O(1/V)) when the learning rate is chosen 7/ < T0p[T+M] In the above proof, we can flexibly adjust the constant e 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, B, and r. This notation facilitates the reader's comprehension by allowing for an intuitive understanding of the effects of important variables such asynchronous delay 7, the number of iterations K, and the amount of training data n on stability and generalization.
B.5 Proof of Lemma (optimization error under the smooth assumption)
By the ASGD update we can derive
convexity, smooth property A.7 and the non-expansive projection (A.8).
Wk+1
w 112 S |W ?) (W
w"11
|| - w w1 + nill V
21 )11 21 (w" WR. Vf(wk-rz 2ie))
Zi:
I l/Wk w1 + 2,37 (W : (m1(ww" Wk. Vf( Zi.
(B.11)
+ ( (w"
.k: V W Z.,) V ff(wniz
< || WW w| + 2,3 [Wo/s[Www-- Wk-Tw -0:-7:2000 %i,)) 2m (f(w"; (i,)) s(Wk;
+ 231 [W w'll l| WK- ||-
From the iterative scheme of ASGD and
A.8
we know that
|
S
Wk-
mh WV i Zz.
(B.12)
Then taking an expectation on both sides of B.1l and combing with Assumptions ]and we have 2/F(s,.((s(ww) Fs(w*)] s Es.allWa-
w
ES.Al || - -w'1 + Es [s (s((
+ 23Lrnk
n カ-
Subsequently a summation of the inequality produces
Tk
M (FFss)(Fs(w:)-FF -FF)))(W)))))))))))))) s ||w w1| 212
7
M----
k=1
Leveraging the optimization bound B.6 with 77 I 1/23, we can derive
K
Th
mk (Fs FFs))))FFsw))))) S || ||ww- - w 1| Σ n As (Fs(W
/=1
1 2-2 ()9m))/wi-wl 11 + 43
76
2
F(
8,32
2
BTr
TjK
M
k=1
j=1
(B.13)
20

---

Let the average model
Σ Thk Wi S.
WK
Sk=1 me
Following the convexity of the function Fs, we know that
(F,A(Fs(WK) - Fs(w")] = E M.s.,,, (Fs())))(W)))))))) Ps((*)]
Σ 1/1:
||1 1 43(F(w") + 23r
k= 1h
2k=1 7/K Σj= M
K
< 2 + 23mm)
+
3Lr
Σ k== 771
2k=1
k= 1
B.6 Proof of Theorem
3 (excess generalization error under the smooth assumption)
Multiplying both sides of the generalization error B.8) by Mh+11 followed with summation gives
K
3
m BsAA [F(w S (1+
Es a + p + 7
Tk
カリー
1=1
j=1
8,3e + +7)
K
+ k )
(1
n
m [[l
mllw1--'1f w113 +
M
2
F( w
+ 4,82
M
1=1
1=1
1=1
(B.14)
Substituting the optimization error (B.13) into the above inequality (B.14). we have
K
k
n
K
mh Es [F(w)) - =
83,
+ 7)e
716
711
m
mwF(w")
k=1
1=1
j=1
+ (1 + -
K
K
[ + (23m)]lwiww']) -w'1 + 43
mh
2 (("((w) ) + +8882p
1k + LL
2
k=1
k=1
k=1
j=
83e(B + 7)
Σ
Th (1 + } mllw1 w 113 2
k
n 2 F (w")) + 48r2
M
1=1
Utilizing the convexity property of the function F, we can derive
k= Es [F(w)) F(w*)]
ES.A [F(WK) F(w")]
Σk=1 7k
1 + 8/4
K
K
K
(2 28mm)lll w11 + 4,3
2 F(w*) + 8,32,3 Σ
Σ U
2
+
Brr
Σ
nR-3
k== 7h
k=1
k=1
k=1
==1
83e(B + (1 + K/n)
K
mallw w01 1| +
Σ
Th F(w") + 48r2
m
n
k=1
1=1
K
K
+ BB, + 7)
Σ 1is + F(w").
M
n-
1=1
(B.15)
By setting 7 1, we conclude that the excess generalization error 6xx Fex.gen is
Cex-gen 0 |+ KK
1h F(w")
1 K/n
K M1 Fnllwi - w1 + F1+FF(W))
+
7
Σ M
n
k=1
+ [ w11
K
K
K Σ
1
7/k
T
m
T
11
1k=1 m
k=
k=1
j=1
k=1
[=1
1=1
21

---

B.7 Proof of Corollary 2 (excess generalization error with a specific learning rate)
Let the learning rate 7/k c(Tv/) 1 with constant c>> 0, and T= => gives
Th/ K, direct calculation
K
K
K
K
c²
ev K/T,
2 2
Th
=
K
T
k=1
k=
k=1
K
k
T
K
CVK
Σ k=1
1k
Σ
1
1|
S
TVK
72
1=1
j=1
k=
From the excess generalization error 1.15 we can derive
Es.A (F(x) F[w")]
S +1+ 3 1 TVK
+ 23c
4
72 F(w*)+ 8,82262
BIre
7
w011
+
+
72
7
cVK
830(3 + + K/n)
W1 1wwww"pp w0112+ + 20²
4
F(w"))
+
n
LVVK
72
72
CVK
B
+ (33 + 7)0
CVK +
F((w")
7²
< 51+ T -W''""
83r
23 W1 - w=
+ Bro(
+
+
LV
2c
VKF
VK"
K
+
8 + +1)(1 + K/n)
c
| - w 1 +
2c²
(ww' + 2
+
8 + eec
TVR
7
72
7
3 + (1 + 3 4,c
+
F(w").
K
Let F(w*)= = 0, K x n and y = 1. If the average delay satisfies 7 S K (quite reasonable in asynchronous training), we have max VK VKF
S z. Then the excess generalization error is
VK
Es. [F(Ak)())) - F(w = 0 +
1 7
1
|| -w1
n
C Proof of Generalization in Non-smooth Case (Section in the main text)
C.1 Proof of Lemma 5 (approximately non-expansive property in the non-smooth case)
Under (a, 3-HHöder continuous condition, the gradients exhibit the following co-coercivity
2 a
V (WK-FE- R- Vf(We-n f(w k- )
-tt k- Ziz 21 +
i
(8)
1
detailed proof of this co-coercivity can be found in Then we have
24
39 51
and also in Lemma D.2 of 23
[V (W
<
a
(Wi-
(t) w W Vf(Wk-r2i2 VJ(
K-TA Zio (1))))
28- +
23
1 1+a
(Wh-72
W W Vf(Wb-r2 2ie)
V
(w
k-Tz ; 1 1))
(i)
20
(2
1+a
2u
1
1+a
B )و.
The
2
(Wk-Te
(1) W ((W
: zir)) +
1 - a
1//
2n
(2- () 1²a
1]K
1 a
where the last inequality we use the Young's inequality (A.] with p
1+a
,9 = 1ta That
2a
i-a'
n V f(We- mu z..) vf(w k zi, 2 < 27k (Wa W TH
k Vf(W :...),)))))) v.(w (ww.-izzz))
+ d
(C.1)
22

---

where da,g / taa
> 0 is a constant dependent on a, 3. Without smoothness, the non-expansive property of delayed gradient updates would be further compromised. However, in conjunction with incquality (C.T), we can make the following derivation.
Wk 1/ V (WWk(www- - Zia) (w (1)
ThR f
T2 2iz ))
= =II 112 + n V
vs(w Tu Bia 1112
-2TT (Wk= w (1) V
V Zin))
Iw w/ 1012 + h V Th 2
fW Zii )12
27T (Wk- P- V (W i 2. Vf(w -2 Zir))
(2)
(1)
20TH (WE: Wh-TE (w w Wk-re V Vf(wk-nx Zie) ff(w (i)
k- Zix))
< [W
(wE Wk-Te (wl w (1)
- ) V (WWW - VS(w [[[Wi-rr 2i
(8)
dh 2
Following the (a. 3) -Hölder continuous condition and Assumption we can derive
(1) [Vf(we-r,iz.. ff( z.,) = Bl[warr. w -
(0 11 S 3r" for s = k k - ji j = I..... -ke
(C.2)
By combing B. and C.2 the asynchronous gradient updates satisfy the following approximately non-expansive property under the (a, 3) Hööler continuous condition.
W& 7h Vf(WW=ra zin) (w/ (8) m7 (
))
S WE
(2) W
+
d 77
Tk + 252 1
n--
(C.3)
C.2 Proof of Theorem (algorithm stability under the (a, H)-Hlerr continuous gradient assumption)
We now examine the on-average model stability of the ASGD algorithm under the (a, H)Höder continuous gradient assumption. Following (C.3) if ASGD selects the same sample in both S and ( at the k-th iteration (with probability - 1/n), we have
|
WHill I
ww mp V f 2.
(w 7h f k- Zi
ww w (0 12
22,20 1
da
where the first inequality uses the no-expansive projection 1/n the selected example is different (i+ i), then
A.8). On the other hand, with probability
| W 2| < [w 7h V f(
(6)
Th V f( iz))
(1 (11+)) +|++)||/e w + 12 + 1 / (1 Vs(w k- 221
< <1++)]|ww
+ 1/p)m || | 2.) | [V[(W/// k- 11
$ + (1+p)llww w/
f (Wk-rz 2i) + f + (w z
Here we use the inequality (.4)) and the self-bounding property of the a, H-Hölder continuous gradient (A.5) Combining the above two cases gives
Tk
We+1 w (1)
w 1 5(1 + I
w 10)11 12 2T 32 2
n mk- + d
(C.4)
2(1 + 1/p) 2/
fftt 20
( (Wk- 2.) + f (w/=,,:))) 243
n
23

---

Following the fact
Es.s & (wh i =21] = Es,Alf Ita (wa-rz:z:)) iz)]]
and the same model initialization W1 w| taking the expectation followed by summation of inequality (C.4) yields
Es,st,a w 1
$1 +
P n
Es.. w| -w w//1l2 + 2 2a
j + da ol
Ta
EsiA f (Wx-re 4(1 + 1/p)
n1
11++1p)<22
0. R
7 π de on
(1+ (a--
ES,A [fis (WI-mizi)) + 2m
j=1
20
By the concavity of the function + x 140, the on-average model stability of ASGD satisfies
E ,A
Wk+11
w 11
n
$ <(1+2)(k n
P (k-1)
411+1/p)
ESS
F
2x
(WI-n)
7 2m
Σ
M--
de
1h
==1
Let n/kk we have (1 11+ 1/pn S (1 (1+11k))) 1/k)(111) S. then
E
-
1
Wk
w (1)
1
n1
k 4e(1 + kkn)eaa
Σ
Es.A
F
2a + 2232,20
(w/ (w/-n)
k
71
Σ
7
n
+
ed
8,
k
m
n2
1=1
j=1
1=1
O
1 + (
k/n
k
Mp
Es.A
F5
Fula
2a
(Wl-
Σ
171
n
+
M
n
1=1
1=1
j=1
1=1
(C.5)
C.3
Generalization Error with (a, -)-öder Continuous Gradient
From the algorithm stability ( it follows that we need to bound ΣS under the a, 3-Hölder continuous gradient condition. Using the non-expansive projection (A.8) and the self- bounding property (A.5). we can derive
7/ Es. A ta (wi )
2u
|| w012 12 < |/
7) V f[Wk((ww (wi-roi Zi,)) w²
|W w2 + n // Vf(W<-r 111 2m= Wk. f((Wk-r Zir)) ))
< WE - w² + e 1 14a (Wk-rzi 2i.) + 21JR (w" Wk. V/(Wk- Zin.))
By the young's 's inequality A.I with = Ita
I-a q
Ita 2a
we have
2a 2a. f 1:a
(Wk Zi.) =
(1,20
2a
1ta -2 ( (1 I f(Wi-To 2in))
A
11+0 a
2a
< 1ta a
1- 00
((
(1+ a
2a
)
1
2a
2
11a
1
+
20
(
1 f(Wk-nu izee)
1Te 20
20 L
1 1+a
a
2a
1tu
-(Wk--ri2ly + 60
24

---

24 1-a
where we define the constant further derive
Ca.
1-a 1+a
( 14
2a
Ca.8
1-
0. With the convexity of f, we can
Wk++1 w=11 S l/ w 112 + (Wk + 2176 (w" Wk: (zim) c ca,
$ ||w w012 + -T.. ( zi.) + 217 (f (/w(w""" :ww)) - f (Wk-TRi Bix))
+ 27t (W TH WE, V )in,) + ")
< |W w012 nk (Wk-< 2i.)) 2mp (w": 2in 2nk (Wk-TT WKY Vi(Wk-niiiu)))
-
+ 57
(C.6)
Here, with the inequality
A.2
A.5
and Assumption 1 have the following derivation
27/ (Wk-TH
WkY (Wk-nii S 2ner Ca. 14a
(Wk T ;i.))
(1 a1+a) f(Wk-ro 2i.))
ITo 2T
1k
C
2a
1+a
Tk
[ (i.)) d
2
where the last inequality we use the young's inequality
A.1 with = 1+a 19 1 + a, and
1+a d.o = a T4a )
is a constant. Substituting it into (C.)) yields
ma i I 2|[w>- 1 2/| 2|| w"ll + f Zi.)) 26
- 26
Multiplying both sides by the non-increasing learning rate yields
a-a 20
n i iz.) S 27 |w www-w"y 2 | || - w w1| + f(w" ((""::""; izi,) )
2T
Taking the expectation and summing the inequalities above gives
EFSs.(FF((II-)) s 2mp ||] - w0 +
Es (F((")) + 26
71
+ 2c
n1-
2
1=1
1=1
According to the concavity of the function + 1T
20
we know that
2 Ei=1 of (Fs.A(F((WW-pp
IF
(wi (wi- -
Σ
1=1
1=1
(C.7)
1a mi
millw w²11 +
m F(w") +
ca,B
m
m
Now, we are ready to analysis the generalization error of ASGD under (a, HH)Hlld continuous
gradient condition. From Lemma 2 (3) and stability (C.5) we have
Es.A [F( - Fs((++1)]
0,8 Es.
1Ta
(W
1
+
7
ES.
|
W
w
1
27
2
2
2ey(1 + kkn)ca.
n
0 Es, A [Fi (Wa.
11
Es.A A
F5
144 (Wi-7)
oyyB2,220
77
m
2y
e
+
111
1-a
1=1
(C.8)
Let EK == max (Es,A [F(wa) - Fs((w)) By the concavity and sub-additivity of x + x 1Ta
2n
we have
2a.
Es.A fi (W*+1)l < (Es.A [F (WE+1) Fs (W++1)) Es.A [F' (Wx+1)l)
1+a
2n. S 4+1
22 + (Es.A (Wx+2)l)
1+a
25

---

Substituting this back into C..
gives
c 2
207(1
kkkn)
cx+1 -
(++]
+ (Es,A [s (Wk+1)]
17a
+
Σ
ni
Es,A
(w(_())))
1=
eyda 0.
2
+
T
+
111
2
j=1
Using the young's inequality
A.1 with
1+a
1 yields
1-a
0,3
(1+a)
4a
1 ++
2a
1 -
a
4ax
2a
Hia
1 + +2
2y
k+1
1 1
27
4a
(k+1
1
1+a
27
It then holds that
Es.A [F(W - Ps( Fs((W++))
2(1 -a]
4a
2a
Ca
Lia
a.
ES.A [Fs (Wi+1)))
20
1
11
2
?
40 + k//))
k
m EsAA
1's 1 (WL-n))
)
+
8,2
20x
M
M- eryde
[=1
j=1
1=1
Substituting CC77 we can get the following generalization error of ASGD under the (a, B)-Höleer continuous gradient condition
Es,A [F(w*+1) [s(WW++))] S
2(1 a))
4a
2a
0,
ES,A [Fs (Wa.1)))
1 a
1+
27
7
Sey + k/n)aa.
La
20_
111
m//ww/
M
w=1
+ Σ
111
2
FF(w" +6 62,8
Σ
11
c
2
1=1
k
k
+ 20y,3² 20
111
M + ordo
0,
Σ
7
1-a
j=1
1=1
(C.9)
C.4 Proof of Lemma 6 (Optimization error under the (a, 3)-Hölerr continuous gradient assumption)
Leveraging the non-expansive projection property (A.8.. convexity and 8-Hölder continuous property (A.5), we can derive
||++1 211 <
|| w 1/s W[(Wk-T
w01
l| w 2 + n/ V 2ic )1 2 277h (w" Wk. ff(Wk=rz :i.))
/ "11 -12 +
ca 2
T 1+a (Wk-rz Zice) + 201// W
Wk. V Vf(Wwizz Zix))
+ (w"" -Wk, WW Ziee - V Vf Z1,))
I l| - w=12 + ea. Ti. I (Wk-rui zie) +
- f(wx:
+ 2.Th//W" W W w
(C.10)
From the iterative scheme of ASGD A.8) and the
sub sub-additivity of x + x", we know that
[w - W W Wk
W (C.11)
Taking the expectation followed by a summation of C..0
yields
k
K
2 m Es. Es Fs((w)) < [[w; - w|1
m
U.S.A [F5 1t
(Wa-r,))
k=1
K
+ 2T
17p
k=1
26

---

where we used (C.11. Assumptions I and 2 Combing with C77 we get the following optimization error bound of ASGD with the (a, Ho-der continuous gradient.
K
K
1 2/l - w01l + g mh (Fs(WL) - Fs(w*)]
-w"l
r
1]K
n
2
1=1
k=1
j=1
+ Ca,B
Fillw - w01l +
K
The
F(F"(w))>))) +
ca,8
1
3 a
+
d
7
17a
2a
(C.12)
According to the convexity of the function Fs. know that
Ek mhe Ls AlFs(WW))))) F's [ww)
- Ps((w))]
S
Σx kk
=0 1> K
R= mK)
m / w=12 (1 F(w*)w)))
Σ
11
mh
77g
Σk= ?K
K
k=1
W1
w' 112 + Ex k= Me E}=1 Mh-
k= 77
C,5 Proof of Theorem 5 (Excess generalization error under the (o,,))-Hölder continuous gradient assumption)
Multiplying both sides of the generalization error (C.9) by the learning rate 4 followed by summation yields
2a
2a
EsE. [F(w&)] <
E. A [F((W))]
Es.A [F's (wx)
m7
k=1
+ 2
4a
1-a
2
1k +
80y(1 + KKn))KK .
K
1/k
11{
I-c I+a
1+
27
n
b
J-n
2a
1/1 [m//wi-
W1
w 1-12 +2
Ti F (ww)
+
Sa.
Σ
111
1-
+
C
Iml
mml
[m1
T2 T
+ 22,,32,20
eyd
7hk
T
T1
j=1
According to the concavity of the function x + x 1+o,
2n
we know that
K
K
K
Mh Es, A.s.s[/f5 [Fs(WW))
Ho
14
Σ
mh
<
mK
Ek=1
A=1
k=1
116
Es IFFSs.lFs(We))
7k
km
k=
K
K
2a
Σ
I...AA(F(WW.))
1]
1 a
1 +
a
k=1
27

---

where the last inequality uses the young's inequality A.1 with 1+a
I-a
.
1-a
2a
Then
Σ
K
EEss [P(wa]] - (1+
2arans
nu Bs.A [ws( + (2( 1a
1+a )
(Ca.s) ta (1 (1-a)ra.s)
Σ
K
x(1aa)
27
7(+aa
m
km1
+ (oy(1K//n)er
20c
11
- - -2 >
ni F(w') + Ca.s
Σ
ni
+ c
m
n
K
k
71
207
20
1/k
T/
end
8.
j=1
k=1
From the optimization error (C.12 we then have
K
Es (P(W))-F((T) 5
+1+a)
2
FxF("")+ )+ (1 20
x(1aa) (² |w] -w ww
"1'1"++- ([lli--'11
+0"
K
77
mi-s
(1 + 7(1 ())
2ac2.0
Σ
K
112
2
14a
m ||]
w w01 + Σ
K
The Flw"(w) ) + &o
Σ
K
1/4
g-m
+ 60,0
K
1/x
2
1+a
km
kml
kml
km 1
(1 + KKn)ea.
3-n
2a
17
- -w"ll""' [nllwi-w''1'- - 2 Σ ni F(w') ) + ca.f
Σ
Th
+ Co
r
[=1
2 (2(114))
4a
20
2
1i
(1 - (1-a)en
30 20
Tjk
T
M
+
eyda
+
ita)
27
?(++a)
1/k-
By the convexity of F, the excess generalization error of ASGD under the (a, 3)-Hölder continuous gradient satisfies
X
- The BABs, a [F(ws) - F(w")]
ES,A [F(we)- F(w')l
Σt= 1/6
2002. $ (1+ 7(1 + a))
K
K F( -o.9
K
K
K
co.o
1
1iu
111 -w'1+=
mi
Ca.8
ME
7/6
k=1
km1
km
km1
k= 1
8ey(1 + K/n)coa.
K
K
3-a
2u
mk
(milw] - -w'1l3 +
mh F(W'()) ") + 63.8
1/
+ Ca.
m
n
(2078 20
K
1/
Σ
m1
7
!1- tydd 1
K
1/k
Σ
1/(
K
1/k
+2
Ita
4a
1-a
2a
(Ca.9
2
2y
Ita
(1 -
(1-a)ca.
7(++a)
2
km
1=1
1=1
k=1
1=1
h=1
(1 + 7(1 + a)
20c2.
(
[ | - w + , r
1
1
K
7
Σ
K
?
+
200
F(w").
7(1 + a)
k=1
(C.13)
Let >>>>> 1, then we are arrive at
K
K
K
K
K
Eex-gen = -
2 iro
m ||] - 12 +
Σ T F(w") +
1k
+
11
7)k
k=
1=1
k=1
k=
(1 +
K K/n)
K
1-a
K
K
2a.
+
m
m
|| - w1113+ +
m F F(w")
+
11
1
n
k=1
k=1
K
K
K
utz
+
7
1
+
m
1] +
1=1
1=1
k=1
1=1
1=1
K
+
11
+
1|
Σ
m
+ g
1
(1 + F F(w')))
j=1
(C.14)
28

---

C.5.1 Excess Generalization Error with the Learning Rate T7 = c ((TV))-)
Set the learning rate 77 = c(TVK)*
11 with c> 0, and T
> 1= Tx/ K, direct calculation gives
K
k
k
k
K A
CV
Σ
K
Σ
th 1=22/T
mh
1
7
1=1
k=1
1=1
j=1
i=1
Σ
1k
The
clta
K
T
S-a
K
T11
K
21
--
k=1
j=1
k=1
|=1
Following the excess generalization error CC14), we know that
Wi
1
K
20
J-n
-n]
2a
Eex- Cox-gen gen =0
11 + F(w"))
K
3-a
K
71 + K/n)
1
1-a
14a
||w w²11
(1 11+ FL+F(w)) +
K²
2(10)
20 1+0
n
VKr
72
7
T
VK
k²-
x1-0|
+ +y-11 1ta
K 1-a
2
7
+(1+
+
+
VK
VK
7
By the sub-additivity of + 1ia
(a [0, 1)), we can derive
Eex-gen =
=0(17
T
7(1 + K/n)
2(1-a)
[w w
+1+ F 2a
(w")) +
K T-x
K 1+a 7 20
Bo(3-o)
7 71+0
(1t0)t101) aj
+
+
K I
I
7|I w012
71-a
70-1
1ta
+
- (1 + (1+
T TI-a
VK
K
=0
(1
F
7(1 + K/n)
K Tir
1
K
V
+
||W]
w
|
+ マ
(1 + F t+i (w*)) +
K
Fl-a
+ 1
(1+ (1++F(wv
F(w+)(ww))
7
+
VK
K
7
Omitting the non-dominant term gives (with y >>>
1)
Cex-gen (0(1
7
+
7(1 + K/n)
K lta
W
+ 1
(1 +
F F fw''(w)))
VK
2
72
7 Tक
7
Zl-a
-1 + F(w"))
1
+
VK
k
?
If F(w)) = 0, K x n. then the excess generalization error is
Cex-gen = =0 (((
F
2)
K
F
")
+ n
|[
+
VK
T
T
72
K
K
Let VT, we have that max
7
F
and then
VK*
n
VK*
||
w
1
7
Gex-gen
1-0 F
VKT
VF
VK
K
1+a
Furthermore, if the average delay satisfies F S Ka with a'
min 31 3- ).
we know that
max
VK
K
V
On the other hand, since F 2 in the asynchronous training and a E [0. 1]. we have
140
K 2(1=))
K 2(10)
k
x x
n
Then, we are arrive at Cox- gen
Es.A (F(ws) - F(w')) = 0
1
W
w
da
n
The proof is complete.
29

---

T-4
T-4
T
Algoritlm stabiity
Algorithan siability
Algorithm stahiity
1e16
T-16
16
160
2-
300
1.0
1o4
Itenttion
(a) Convex optimization on RCV1
(b) CV task on CIFAR100
(c) NLP task SST-2
Figure The on-average model stability in training various machine learning tasks using ASGD with learning rate 0.1/7. The horizontal axis denotes the number of asynchronous training iterations, and the legend represents the average delay. A degradation in algorithm stability observed the number of training iterations increases.
D More Experiment Results
This section provides additional details on the experimental setup, as well as the stability and generalization results trained with delay-independent constant learning rate. Our experiments use the more general asynchronous stochastic gradient descent format (9. i...
Wk+1
Wk
TJ
MEM
In practical applications, the gradient th 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 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 the stability and generalization results of ASGD algorithm, employing delay- independent learning rate of 7/s- = 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.
135
132
Algorihm stablity
Algoridbu stability
T-8
Algorithm stabilit
T-16
T-16
T-16
144
136
300
126
128
Iteration
lteration
lef
Itration
(a) CV task on CIFAR10
(b) CV task on CIFAR100
(c) NLP task on SST-2
Figure 3: The on on-average model stability in training various machine learning tasks using ASGD with delay-independent constant learning rate = 0.01. The horizontal axis denotes the number of asynchronous training iterations, and the legend represents the average delay. degradation in algorithm stability is observed with an increase in training iterations.
Figure 5 shows the training, testing and generalization errors of three categories of machine learning models. The generalization testing errors. In certain model tasks, particularly BERT on the SST-2 task, overfitting phenomena present, contributing significantly to the generalization gap. Therefore, 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
roughly of the same order of magnitude the training and
30

---

Generaliztion etror
4.5
Generalization srror
T-4
T-4
T-16
T-16
3.0-
T-32
Generalization
1.5
0.0
2
0.0
0.2
0.4
0.6
0.8
1.0
Iteration
164
Iteration
164
Iteration
1e5
(a) CV task CIFAR10
(b) CV task CIFAR100
NLP task SST-2
Figure 4: The generalization enrors in training various machine learning tasks using ASGD with delay-independent constant learning rate `is = 0.01. The trend of generalizability with the number of iterations is analogous to the algorithm stability depicted in Figure 3 and appropriately increasing the asynchronous delay can enhance generalization performance.
16-2
0.32
0.32
General Generalization error
1.6
Twd
Training error
T=16
Testing error
T=16
0.24
1.2
T-32
0.8
0.4
0.08
0.08
0.0
Iteration
Iteration
Iteration
(a) Convex optimization on RCV1
(b) Convex optimization on RCV1
(c) Convex optimization on RCV1
Generalizzaton error
T-B
T=B
Training error
Testing error
T-32
T-32
T-32
Iteration
1c4
Iteration
164
Iteration
104
(d) CV task on CIFAR100
(e) CV task on CIFAR100
(1) CV task on CIFAR100
T
T-4
Apple M M
Generalization error
Te4
Training error
0.6
Tw
Testing error
Tw16
T-16
T=33
0.4
1.0
0.8
0.2
0.0
0.4
0.6
0.5
1.0
0.4
1.0
le5
Iteration
le5
Iteration
les
(g) NLP task SST-2
(h) NLP task SST-2
NLP task SST-2
Figure 5: The training, testing and generalization errors of three categories of machine learning models trained using ASGD with learning rate 7 = 0.1/7. The horizontal axis denotes the number of asynchronous training iterations, and the legend represents the average delay.
31

---

E
Contributions and Limitations
E.1
Contributions
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 only vacuous exponential generalization bounds and relies strict assumptions such as Lipschitz continuous and smooth functions. Another work [3] establishes tighter generalization bounds, but its analytical techniques only applicable to smooth quadratic convex problems.
33 provides
Our contributions have been detailed in Section | and the following table further compares the required assumptions and theoretical results of the related works.
Table 1: Comparison with related work.
Regatti al. 33
Deng al.
B3
Ours
Lipschitz assumption?
L L--Lipschiz
Not required
Not required
Smoothness assumption?
B-smooth
f-smooth
(a, B) --ölder continuous
Convexity?
Non-convex
Quadratic convex
General convex
Generalization error
K (
K-2 Ö
0
nF
nf
Excess generalization error
N/A
N/A
0
Wi
/ni
E.2 Limitations
Assumption. In Assumptions | 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. we adopt stronger assumptions, such as the assumption in paper (55) that the difference between models Wa and w follows normal distribution with bounded mean and variance, we can obtain better results (in terms of the training sample size 11).
Pessimistic result. The experiments Appendix D concerning delay-independent fixed learning rates, show that the generalization error bound I0. is pessimistic, i.e., asynchronous training beneficial for generalization even a fixed learning rate is used. A potential avenue for future research lies in exploring tighter high probability bounds that attenuate the dominant role of the learning rate on generalization, thereby elucidating the experimental phenomena in Appendix D
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 exponential generalization error bound, similar to the findings in study [33]. Unfortunately, this upper bound is pessimistic and vacuous. Exploring sharper stability and generalization eиror bounds of ASGD in non-convex scenarios is extremely challenging. Future research on non-convex problems could focus on demonstrating that asynchronous gradient updates 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, non- convex 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-con con-conve scenarios the future.
32

---

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

---

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

---

reproducible, they 5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification: We have submitted the source code the Supplementary Material and provided sufficient instructions for usage in the README.md file.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nnis.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/nipss wwtpcc/pcpppcpcceeeooooooop gwwcc//gu/es//eee /wwedeeeeooobebbiiccccee setbbmmsssionp swiniioisiiiyccy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have described the experimental setup in detail in Section 6 and Appendix D and provided more details in the source code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
we have repeated the experiment several times by choosing Justification: Section 6
different random seeds verify the theoretical findings.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
35

---

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 the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: In Appendix D have provided sufficient information on the computer resources needed to reproduce the experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums 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).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httppssss//eerrpssccppibiieeeee ctw.eeeeeeeiiciiceeeeneeneee
Answer: [Yes]
Justification: We have reviewed the NeurIPS Code of Ethics and the research conducted in the paper conform with the NeurIPS Code Ethics in every respect.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper focuses on stability and generalizability analysis of fundamental optimization algorithm. No societal impacts discussed or related to the research.
Guidelines:
36

---

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 negatíve societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (c.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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper focuses on stability and generalizability analysis of fundamental optimization algorithm and poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make 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]
The models and datasets used in this paper are publicly available and we have cited the corresponding papers.
Justification:
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 dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
37

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.com//aaaa datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given 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 contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS 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.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
38

---

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.
39


Reviews:
[{"review_id": "ZsH5UcT4SD", "reviewer": "Reviewer_UzMC", "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.", "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.\n\n2. What do authors mean by ***sharper*** : \n    - 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?\n    - Can authors give more detailed explanations about the ***sharper*** in *Line 292* and *Line 297*?\n\n3. 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": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- It's interesting to investigate the generalization performance of ASGD for distributed learning and analyze the impact of different factors.\n\n- The paper appears to be theoretically solid, with clearly presented results, required assumptions, and detailed proofs.\n\n- Extensive experiments, simulating convex and nonconvex conditions, including CV and NLP tasks, convincingly validate the theoretical results.", "weaknesses": "- 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.\n\n- It should be emphasized what technical tools enable authors to derive *sharper* or better results compared to existing works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **Question 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.\n\n**Response.** Yes, we completely agree with your suggestion, and we have already included the corresponding table and explanations in Appendix E.1. Please refer to the response to Question 2 in **Author Rebuttal**.\n\n---\n\n> **Question 2.** What do authors mean by ***sharper*** :\n>\n> - 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}{\\overline{\\tau}}+\\frac{1}{\\sqrt{K}})$ sharper?\n> - Can authors give more detailed explanations about the ***sharper*** in *Line 292* and *Line 297*?\n\n**Response.** Firstly, direct computation shows that the result $K^{\\hat{\\tau}}/n\\hat{\\tau}$ monotonically increases with the delay $\\hat{\\tau}$ when $\\hat{\\tau}>\\frac{1}{\\ln K}$. Here, $K$ is the number of training iterations, hence $\\frac{1}{\\ln K}<1$, whereas in asynchronous training, the maximum delay $\\hat{\\tau}\\geq1$, ensuring that $\\hat{\\tau}>\\frac{1}{\\ln K}$ always holds. Moreover, the result $K^{\\hat{\\tau}}/n\\hat{\\tau}$ exhibits an approximately exponential growth with the delay $\\hat{\\tau}$, hence $K^{\\hat{\\tau}}/n\\hat{\\tau}\\gg1$, which is very loose and vacuous for the generalization upper bound. In contrast, our theoretical findings clearly show that increasing the asynchronous delay reduces the generalization error of ASGD at an appropriate learning rate, a finding that is further supported by experimental evidence. Besides, since $\\frac{1}{\\overline{\\tau}}+\\frac{1}{\\sqrt{K}}\\leq1$, our result is sharper and non-vacuous.\n\nIn *Line 292* and *Line 297*, we explain the reasons behind the sharper results presented in this paper. Specifically, the result $\\mathcal{O}(K^{\\hat{\\tau}}/n\\hat{\\tau})$ in study [33] relies on the bounded gradient assumption, i.e., $\\text{sup}_{\\mathbf{z}}\\\\|\\nabla f(\\cdot; \\mathbf{z})\\\\|\\leq L$. Whereas, in our study, we use the self-bounding property of the gradient function, i.e., $\\\\|\\nabla f(\\mathbf{w}\\_k; \\mathbf{z})\\\\|\\leq c\\_{\\alpha, \\beta}f^{\\frac{\\alpha}{1+\\alpha}}(\\mathbf{w}\\_k; \\mathbf{z})$ (Lemma A.4 in Appendix A.2).\nAs the algorithm converges, the empirical risk $f(\\mathbf{w}_k; \\mathbf{z})$ would be significantly smaller than the uniform gradient bound $L$. Therefore, we can derive sharper and non-vacuous generalization error bounds.\n\n---\n\n> **Question 3.** Why the result presented in **Theorem 5** that $\\mathcal{O}(\\frac{1}{\\sqrt{\\overline{\\tau}}}+\\frac{\\\\|\\mathbf{w}\\_{1}-\\mathbf{w}^{\\*}\\\\|^{\\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}{\\overline{\\tau}}+\\frac{\\\\|\\mathbf{w}_{1}-\\mathbf{w}^{*}\\\\|^{2}}{n})$?\n\n**Response.** The parameter $\\alpha$ in Theorem 5 is defined within the range $[0, 1)$. Specific reasons are given below. Section 5 of this paper studies the generalization performance under the $(\\alpha, \\beta)$-Hölder continuous gradient condition. Lemma 5 indicates that an additional term $\\mathcal{O}(\\eta_{k}^{\\frac{2}{1-\\alpha}})$ is introduced to compensate for the absence of smoothness. Consequently, $\\alpha$ cannot take the value of $1$ here. \n\nIn short, this paper examines the two cases separately. Section 4 studies the smooth loss function, i.e., $\\alpha=1$. Section 5 extends the analysis to the non-smooth function, i.e., the $(\\alpha, \\beta)$-Hölder continuous gradient case, in which case $\\alpha\\in[0, 1)$. Following Theorem 5, we also provide a comparative discussion of these results, i.e.,\n\n* **Section 5, Lines 307-310, below Theorem 5**\n\n  *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.*", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0vVVW1m48T", "reviewer": "Reviewer_CbYp", "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.", "questions": "1. $\\bar{\\tau}$ is not introduced in line 58.\n2.  Is it possible to remove the Lipschitz assumption?\n3. If $\\tau_k=0$ for all $k$, wiil the results of ASGD recover the results of SGD?", "limitations": "NA", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper provides a comprehensive generalization analysis for ASGD for both smooth and nonsmooth losses through the lens of on-average model stability.\n\n2. The error bounds outperform previous works.", "weaknesses": "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. \n\n2. 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.\n\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">  **Question 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.\n\n**Response.** Firstly, this paper studies the generalization performance of the distributed asynchronous SGD algorithm, mainly focusing on parsing the effect of asynchronous delays on algorithm stability and generalization. Our results exhibit sharper and non-vacuous generalization bounds compared to existing ones for ASGD [13, 33].\n\nMoreover, when extending the bounds of this paper to the synchronized SGD algorithm, our results surpass those of Lei (2021). Specifically, we achieve the same generalization error results with fewer iterative computations compared to Lei (2021). For details, please refer to the response to Question 6.\n\nLastly, while Lei (2021) is a purely theoretical research work, this paper conducts numerous experiments to validate our theoretical findings, including convex problems and non-convex tasks in computer vision and natural language processing.\n\n---\n\n> **Question 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 $\\\\|\\mathbf{w}\\_k-\\\\mathbf{w}\\_1\\\\|^2\\lesssim\\sum\\_{t=1}^{k}\\eta_k$, I believe that a similar result could be established for ASGD. It will improve the results of the paper.\n\n**Response.** This paper studies the projected ASGD algorithm (Lines 178-183), i.e., $\\mathbf{w}\\_{k+1}=\\Pi\\_{\\Omega}\\big(\\mathbf{w}\\_{k}-\\eta\\_{k}\\nabla f(\\mathbf{w}\\_{k-\\tau\\_{k}}; \\mathbf{z}\\_{i\\_{k}})\\big)$. Thus, we can effectively control the radius $r$ of the parameter space by projection operations. We appreciate the reviewer's valuable insight that one can prove that $\\\\|\\mathbf{w}\\_k-\\mathbf{w}\\_1\\\\|^2\\lesssim\\sum\\_{t=1}^{k}\\eta_k$. However, it is important to note that the radius of the parameter space is mainly used to estimate the difference between models $\\mathbf{w}\\_{k}$ and $\\mathbf{w}\\_{k}^{(i)}$, rather than analyze the optimization error. A detailed description can be found in Remark 1, i.e.,\n\n* **Remark 1, Lines 184-189**\n\n  *Let $\\mathbf{w}\\_{k}$ and $\\mathbf{w}\\_{k}^{(i)}$ denote the models produced by projected ASGD (7) after $k$ iterations on the datasets $\\mathcal{S}$ and $\\mathcal{S}^{(i)}$ (defined in (5)), respectively. According to Assumption 1, it follows that $\\\\|\\mathbf{w}\\_{k}-\\mathbf{w}\\_{k}^{(i)}\\|\\leq r$. Notably, this result is intuitively understandable as the datasets $\\mathcal{S}$, $\\mathcal{S}^{(i)}$ differ only by a single sample, and the initialization is the same ($\\mathbf{w}\\_{1}=\\mathbf{w}\\_{1}^{(i)}$). In contrast to a recent work [53], where the authors assumed a normal distribution with bounded mean and variance for the difference between models $\\mathbf{w}\\_{k}$ and $\\mathbf{w}\\_{k}^{(i)}$, our study does not necessitate such a strong assumption.*\n\nAdditionally, we have further explained the assumption limitations in Appendix E.2, i.e.,\n\n* **Appendix E.2, Lines 782-786**\n\n  *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 [53] that the difference between models $\\mathbf{w}\\_{k}$ and $\\mathbf{w}\\_{k}^{(i)}$ follows a normal distribution with bounded mean and variance, we can obtain better results (in terms of the training sample size $n$).*\n\n---\n\n>  **Question 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.\n\n**Response.** When analyzing the stability and generalization error of ASGD in this paper, we depart from the traditional approach of relying on the Lipschitz assumption. Instead, we replace the fixed Lipschitz constant with the empirical risk, leading to theoretically sharper and non-vacuous results. Please also refer to the response to Question 2 of reviewer UzMC.\n\nAs for the excess generalization error, it is known from the decomposition (8) that this error consists of two parts: generalization error and optimization error. The Lipschitz assumption is used to analyze the optimization error of ASGD. We have thoroughly discussed the applicability of Assumption 2, i.e.,\n\n* **Section 4, Lines 240-246**\n\n  *The analysis of optimization error for ASGD usually requires the following bounded gradient assumption [26, 28, 33]... 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.*\n\n---\n\n>  **Question 4.** $\\overline{\\tau}$ is not introduced in line 58.\n\n**Response.** Throughout the paper, $\\overline{\\tau}$ is defined as $\\overline{\\tau}=\\sum_{k=1}^{K}\\tau_{k}/K$, denoting the average delay in the asynchronous training system.\n\n---\n\n> **Question 5.**  Is it possible to remove the Lipschitz assumption?\n\n**Response.** In the analysis of the optimization error of ASGD, the Lipschitz condition is a standard assumption widely used to bound the error introduced by asynchronous updates [26, 28, 33]. However, this study specifically concentrates on investigating the generalization error of ASGD, and one potential future research direction involves completely removing the Lipschitz assumption.\n\n---\n\n> **Question 6.** If $\\tau_{k}=0$ for all $k$, will the results of ASGD recover the results of SGD?\n\n**Response.** Yes. Please refer to the response to Question 1 in **Author Rebuttal**.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CneLF9NdZE", "reviewer": "Reviewer_pPuN", "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.", "questions": "1.Should the learning rate upper bound $\\eta_k \\leq 1/2\\beta$ be $\\frac{1}{2\\beta}$?\n\n2.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": "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? \n\n- X. Lian, W. Zhang, C. Zhang, and J. Liu. Asynchronous decentralized parallel stochastic gradient descent. ICML, 2018.\n\n- X. Deng, T. Sun, S. Li, and D. Li. Stability-based generalization analysis of the asynchronous decentralized SGD. AAAI, 2023\n\n- J. Chen, H. Chen, B. Gu, H. Deng. Fine-Grained Theoretical Analysis of Federated Zeroth-Order Optimization. NeurIPS, 2023.", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "+ The manuscript develops the stability-based generalization analysis of ASGD to weaker cases, i.e., the case without either Lipschitz condition or smoothness.\n\n+ Through numerical experiments including both convex and non-convex optimization problems, authors validate their theoretical results.", "weaknesses": "- 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.\n- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **Question 1.** The authors provide the approximately non-expansive recursive property for ASGD. Without some limitations to $r$ and $\\tau$, the terms $2\\eta_{k}\\beta^{2}r^{2}\\sum_{j=1}^{\\tau_{k}}\\eta_{k-j}$ in Lemma 3 and $\\mathcal{O}\\Big(\\eta_{k}\\sum_{j=1}^{\\tau_{k}}\\eta_{k-j}+\\eta_{k}^{\\frac{2}{1-\\alpha}}\\Big)$ in Lemma 5 may be very large. \n\n**Response.** In this paper, we study the projected ASGD algorithm (Lines 178-183), i.e., $\\\\mathbf{w}\\_{k+1}=\\Pi\\_{\\Omega}\\big(\\mathbf{w}\\_{k}-\\eta\\_{k}\\nabla f(\\mathbf{w}\\_{k-\\tau\\_{k}}; \\mathbf{z}\\_{i\\_{k}})\\big)$. Thus, we can effectively control the radius $r$ of the parameter space by projection operations. In addition, $\\overline{\\tau}$ is defined as $\\overline{\\tau}=\\sum_{k=1}^{K}\\tau_{k}/K$, denoting the average delay, which is also bounded.\n\nFurthermore, these two terms are closely related to the learning rate. Similar to the previous work [40], we can control these two terms by utilizing a learning rate inversely proportional to $r$ and $\\overline{\\tau}$. Specifically, the learning rate for asynchronous training is set to $\\eta_{k}=c/(\\overline{\\tau}\\sqrt{K})$, where $c$ is a constant inversely proportional to $r$ and $\\beta$. In this case, these two terms correspond to $\\mathcal{O}(1/\\overline{\\tau})$ and $\\mathcal{O}(1/\\sqrt{\\overline{\\tau}})$ in Corollary 2 and Theorem 5, respectively, which is significantly better than the existing exponential upper bound $\\mathcal{O}(K^{\\hat{\\tau}}/n\\hat{\\tau})$.\n\n---\n\n> **Question 2.** There are some terms related to learning rates in almost all results, such as $\\sum_{k=1}^{K}\\eta_{k}\\sum_{j=1}^{\\tau_{k}}\\eta_{k-j}$ in Theorem 2, $\\sum_{k=1}^{K}\\tau_{k}$ in Corollary and $\\sum_{l=1}^{k}\\eta_{l}\\sum_{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.\n\n**Response.** First of all, it should be clarified that the **generalization error does not converge to zero** in general, and our experimental results can verify this argument.\n\nMoreover, the stability and generalization of an algorithm are inherently related to its learning rate, a phenomenon observed in SGD as well [17] (whose result is $\\frac{2L^{2}}{n}\\sum_{k=1}^{K}\\eta_k$). Researchers typically employ a learning rate that is inversely correlated with the number of training iterations $K$ and the asynchronous delay $\\tau$ to obtain the corresponding theoretical results [13, 17, 33, 40].\n\n---\n\n> **Question 3.** 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.\n\n**Response.** Please refer to the response to Question 2 in **Author Rebuttal**.\n\n---\n\n> **Question 4.** Should the learning rate upper bound $\\eta_k\\leq1/2\\beta$ be $\\frac{1}{2\\beta}$?\n\n**Response.** In the proof of Theorem 1, we need the learning rate to satisfy $\\eta_{k}<1/2\\beta$, a slightly different condition from that in Lemma 3, $\\eta_{k}<2/\\beta$. This condition is standard in analyzing SGD and its variants [13, 17, 23, 30, 33].\n\n---\n\n> **Question 5.** 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?\n\n**Response.** While our theoretical analysis is grounded in the general convex condition, additional non-convex 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 of the ASGD algorithm in the non-convex scenarios in the future. \n\nFurthermore, we have also discussed the limitations of the convex function assumption and explored the difficulties and potential research directions for non-convex optimization in Appendix E.2, i.e.,\n\n* **Appendix E.2, Lines 792-799**\n\n  *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.*\n\n---\n\n> **Question 6.** 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?\n\n**Response.** As shown in Algorithm 1 (located in Appendix A), ASGD is performing asynchronous gradient updates on the server side. This paper studied the distributed parameter server (PS) architecture with multiple workers. In PS, each distributed worker (in the experimental part, we use 16 workers) has been performing idle-free gradient computation, while the parameter updates are performed in an asynchronous manner on the server side.\n\nUnlike the centralized parameter server employed in this study, the research listed by the reviewer further involves a decentralized communication topology. The theoretical analysis of this study can be extended to the decentralized setup, but a more in-depth analysis is needed. The main challenges are to examine the mixing matrix properties in decentralized settings and to bound the differences between local and global models. This is also a promising avenue for future investigation.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OgcpTJ9kJ5", "reviewer": "Reviewer_yEhD", "summary": "This paper talks about the generalization error and the excess generalization error of Asynchronous SGD, mainly under convex, smooth or holder continuous conditions.", "questions": "Can we take τk=0 in this paper? At in this situation, can the result lead to the generalization bound of SGD?\n\nIn 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": "The authors have adequately addressed the limitations and potential negative societal impact of their work", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The theorems are sound, and the results are new.", "weaknesses": "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.\n\nIn 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?\n\nI see your paper and experiment is talking about networks. I have some concerns about the connection between this article and neural networks.\n\n1: May I ask if your theorems can guide the training of networks, or give some helps to training?\n\n2: 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **Question 1.** In th2, the generalization error is written as the form of containing $\\mathbf{w}_1$ and $\\mathbf{w}_K$. This is some what not reasonable. I want to see the generalization error which is depended on the already setting constants like $\\eta, K, n$ and so on, in this way, theorem can be applied to more situations.\n\n**Response.** Theorem 2 provides a generalization error result by directly substituting the stability of the ASGD algorithm into Lemma 1. The inclusion of $\\mathbf{w}_1$ and $\\mathbf{w}_K$ aims to demonstrate the impact of the optimization process of the algorithm ($F\\_{\\mathcal{S}}(\\mathbf{w}\\_{K})$) and the initial state of the model ($\\mathbf{w}\\_1$) on the algorithm's generalization performance. \n\nIn the subsequent Corollary 1, Theorem 3, and Corollary 2, we further analyzed the optimization error, and these results no longer contain $\\mathbf{w}\\_K$, but instead reveal the effects of asynchronous delay, model initialization, number of training samples and iterations on generalization performance.\n\n---\n\n> **Question 2.** In cor1, cor2 and th5, if we want the generalization bound to be small, then $\\tau_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?\n\n**Response.** Yes, this is the key finding of this study, i.e., increasing the asynchronous delay appropriately in asynchronous training improves the stability of the ASGD algorithm and reduces the generalization error. \n\nIn this paper, we study the generalization performance rather than the convergence of ASGD, and our theoretical results (Corollaries 1 and 2, Theorem 5) show that the noise introduced by asynchronous training makes the algorithm more robust at the proper learning rate, and thus improves the generalization performance. \n\nA similar bound $\\widetilde{\\mathcal{O}}(\\frac{K-\\hat{\\tau}}{n\\hat{\\tau}})$ for quadratic optimization problems is established in study [13]. This paper extends these findings to general convex problems under the weaker $(\\alpha, \\beta)$-Hölder continuous gradient assumption. Additionally, we have also conducted a number of real-world experiments (Section 6), which further corroborate that appropriately increasing the asynchronous delay improves algorithmic stability and thus reduces the generalization error (see Figures 1, 2, 3 and 4).\n\n---\n\n> **Question 3.** I have some concerns about the connection between this article and neural networks. May I ask if your theorems can guide the training of networks, or give some helps to training?\n\n**Response.** Yes, our theoretical results reveal the effects of asynchronous delay, model initialization, number of training samples and iterations on generalization performance. Moreover, we have discussed in the paper how these theoretical generalization results can provide guidance for practical training, e.g.,\n\n* **Lines 208-209, below Theorem 1**\n\n  *Theorem 1 indicates that model initialization affects the algorithmic stability, i.e., selecting a better model initiation point $\\mathbf{w}_{1}$ can effectively improve the stability.*\n\n* **Lines 216-220, below Theorem 2**\n\n  *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 $\\mathbf{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.* \n\n* **Lines 308-310, below Theorem 5**\n\n  *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.*\n\n---\n\n> **Question 4.** 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?\n\n**Response.** The existing non-vacuous generalization error results for ASGD [13, 41] are only applicable to quadratic convex problems, and the study [41] does not reveal the effect of asynchronous delays on the algorithm's generalization performance. \n\nIn this paper, we establish the non-vacuous generalization error and excess generalization error results of ASGD under weaker assumptions for the general convex case. Furthermore, we have discussed the limitations of the convex function assumption and explored the challenges and potential research directions for non-convex optimization in Appendix E.2 (lines 792-803).\n\n---\n\n> **Question 5.** Can we take $\\tau_k=0$ in this paper? At in this situation, can the result lead to the generalization bound of SGD?\n\n**Response.** Yes. Please refer to the response to Question 1 in **Author Rebuttal**.\n\n---\n\n> **Question 6.** 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?\n\n**Response.** In the Preliminaries section of the paper, we have described the motivation for doing this, i.e.,\n\n* **Section 3, Lines 152-156**\n\n  *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.*\n\nIn short, the Hölder continuous gradient is a weaker assumption than the smooth function and can be applied to a wider range of machine learning tasks.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
**We sincerely appreciate the reviewers for their meticulous review and valuable feedback.** We are encouraged by their endorsements:
1. It's interesting to investigate the generalization performance of ASGD for distributed learning and analyze the impact of different factors. [Reviewer UzMC]
2. The paper provides a comprehensive generalization analysis for ASGD in weaker cases. [Reviewers CbYp, pPuN]
3. The theorems are sound, the results are new, and the error bounds outperform previous works. [Reviewers UzMC, CbYp, yEhD]
4. Extensive experiments simulating convex and non-convex conditions, including CV and NLP tasks, convincingly validate the theoretical results. [Reviewers UzMC, pPuN]

---

In the following, we begin by responding to two common questions.

> **Question 1.**
> * [Reviewer CbYp, Question 6.] If $\tau_{k}=0$ for all $k$, will the results of ASGD recover the results of SGD?
> * [Reviewer yEhD, Question 5.] Can we take $\tau_k=0$ in this paper? At in this situation, can the result lead to the generalization bound of SGD?

**Response.** Yes, we have compared our result with the SGD algorithm after Theorem 5, i.e.,
* **Section 5, Lines 310-313**

  *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 $\mathcal{O}(1/\sqrt{n}^{1+\alpha})$. This outcome is consistent with the findings from the study of the SGD algorithm in [23], but without requiring more computation $K\asymp n^{\frac{2}{1+\alpha}}$.*

More specifically, when considering the synchronized SGD algorithm (i.e., $\tau_{k}=0$ for all $k$), the terms involving $\sum_{j=1}^{\tau_k}\cdot$ vanish in the proof. Consequently, the excess generalization error of Theorem 5 becomes $\mathcal{O}(1/\sqrt{n}^{1+\alpha})$, aligning with the theoretical result of SGD (Theorem 8 (c), [23]). Notably, while the result in paper [23] requires the iteration number to satisfy $K\asymp n^{\frac{2}{1+\alpha}}$, our paper requires only $K\asymp n$, highlighting the superiority of our findings over [23].

---

> **Question 2.**
> * [Reviewer UzMC, Question 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.
> * [Reviewer pPuN, Question 3.] 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.

**Response.** Yes, we completely agree with the suggestion of Reviewer UzMC, and we have already included the corresponding table and explanations in Appendix E.1, i.e.,

* **Appendix E.1, Lines 771-779**

  |                             | Regatti et al. [33]                               | Deng et al. [13]                                            | Ours                                                         |
  | --------------------------- | ------------------------------------------------- | ----------------------------------------------------------- | ------------------------------------------------------------ |
  | Lipschitz assumption?       | $L$-Lipschitz                                     | Not required                                                | Not required                                                 |
  | Smoothness assumption?      | $\beta$-smooth                                    | $\beta$-smooth                                              | $(\alpha, \beta)$-Hölder continuous                          |
  | Convexity?                  | Non-convex                                        | Quadratic convex                                            | General convex                                               |
  | Generalization error        | $\mathcal{O}(\frac{K^{\hat{\tau}}}{n\hat{\tau}})$ | $\widetilde{\mathcal{O}}(\frac{K-\hat{\tau}}{n\hat{\tau}})$ | $\mathcal{O}(\frac{1}{\overline{\tau}}+\frac{1}{\sqrt{K}})$  |
  | Excess generalization error | N/A                                               | N/A                                                         | $\mathcal{O}(\frac{1}{\sqrt{\overline{\tau}}}+\frac{\|\mathbf{w}_{1}-\mathbf{w}^{*}\|^{\frac{4\alpha}{1+\alpha}}}{\sqrt{n}^{1+\alpha}})$ |

In addition, we have discussed this study in comparison with previous work, including the stability and generalization research on the SGD and ASGD algorithms, which further highlights the advantages of our study, e.g.,

* **Section 4, Lines 206-209**

  *Compared to SGD [23], we introduce an additional term to characterize the effect of asynchronous delay on the stability of ASGD. Also similar to the data-dependent stability study [22], Theorem 1 indicates that model initialization affects the algorithmic stability...*

* **Section 4, Lines 231-237**

  *Unlike previous ASGD generalization research [14, 33], this study does not rely on the Lipschitz assumption. In contrast to the vacuous upper bound of $\mathcal{O}(K^{\hat{\tau}}/n\hat{\tau})$ in [33], we provide a sharper result and demonstrate that increasing the asynchronous delay reduces the generalization error. While [13] present a similar result $\mathcal{O}((K-\hat{\tau})/n\hat{\tau})$ with respect to the maximum delay $\hat{\tau}$ in the convex quadratic optimization, our bound holds in general convex settings. Furthermore, our results are associated with the average delay $\overline{\tau}$ rather than the pessimistic maximum delay $\hat{\tau}$ in [13, 14, 33].*

* **Section 5, Lines 310-313**

  Please refer to **Question 1**.

---

Regarding the remaining questions raised by the reviewers, we have provided point-to-point responses in **Rebuttal**. Please feel free to comment again if you have any further suggestions or require additional clarification on any aspects of the paper.

Note: The references cited in the rebuttal correspond to the serial numbers in the paper.

Meta-review: 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.
Decision: Accept (poster)