Stability and Sharper Risk Bounds with Convergence Rate $\tilde{O}(1/n^2)$
Authors: Bowei Zhu
Shaojie Li
Mingyang Yi
Yong Liu
Venue: NeurIPS 2025 poster ()
Keywords: algorithmic stability
generalization bounds
excess risk bounds
stochastic gradiet descent
Primary area: theory
TL;DR: We derive high probability excess risk bounds to  at most $\tilde{O}(1/n^2)$ for ERM, GD and SGD and our high probability results on the generalization error of gradients for nonconvex problems are also the sharpest.

Abstract: Prior work (Klochkov \& Zhivotovskiy, 2021) establishes at most $O\left(\log (n)/n\right)$ excess risk bounds via algorithmic stability for strongly-convex learners with high probability. We show that under the similar common assumptions — Polyak-Lojasiewicz condition, smoothness, and Lipschitz continous for losses — rates of $O\left(\log^2(n)/n^2\right)$ are at most achievable. To our knowledge, our analysis also provides the tightest high-probability bounds for gradient-based generalization gaps in nonconvex settings.

Stability and Sharper Risk Bounds with Convergence Rate O(1/n²)
Bowei Zhu! 1:2.3 Shaojie Li 1.,,,,,. Mingyang Yi! Yong Liu L 1.2,3,
"Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China Beijing Key Laboratory of Research on Large Models and Intelligent Governance 8 Engineering Research Center of Next-Generation Intelligent Search and Recommendation, MOE (bowei.zhu, lishaojie95, yimingyang, liuyonggsai) @ @uuc.edu.cn
Abstract
Prior work (Klochkov Zhivotovskiy, 2021) establishes at most O (log(n) (n)/n) excess risk bounds via algorithmic stability for strongly-convex learners with high probability, We show that under the similar common assumptions - Polyak- Lojasiewicz condition, smoothness, and Lipschitz continous for losses - rates of O (n)/n²) are at most achievable. To our knowledge, our analysis also provides the tightest high-probability bounds for gradient- generalization gaps in nonconvex settings.
Introduction
Algorithmic stability a fundamental concept in learning theory [3] which can be traced back the foundational works of Vapnik and Chervonenkis [46] and has a deep connection with learnability
[37 40 39]. Roughly speaking, an algorithm is stable if a substitution of single example in the training dataset leads to minor change of the output model. With such algorithmic stability, the generalization ability of model is guaranteed. Owing to the relationship, the algorithmic stability recognized as powerful tool to explore the generalization.
In practice, researchers built the generalization bounds expressed in-expectation in-high proba- bility. While providing in in-expectation bounds is relatively straightforward. their high probability counterparts are more crucial for practical optimization algorithms [12 4 220). Because we often train models single time in practice, and high probability bounds offer more informative insights. Therefore, we focus on improving high probability risk bounds through an exploration of algorithmic stability.
Exploring the high-probability generalization gap bounded via algorithmic stability firstly chased to Bousquet and Elisseeff (3), and was further developed by Feldman and Vondrak [[] 12). Within these literature, the optimal high-probability bound of generalization error" O (log(n)/ /n) plus the algorithmic stability parameter for bounded loss function. Owing to the existence of sampling error, deriving the bound within the framework [4] can not be improved, since the lower bound of sampling error is proven to be O(1/vn). To resolve this, Klochkov and Zhivotovskiy [20] propose to alternatively explore the excess risk, which directly reveals the performance of learned model, and can be decomposed into optimization and generalization errors. Without considering the sampling error, Klochkov and Zhivotovskiy (20] improve the high- probabiiyyyy bound to excess risk of Olog (n)/n) plus algorithmic stability parameter, under a Bernstein type condition [49] Moreover, under strongly convexity condition, the algorithmic stability parameter of projected gradient descent (PGD) is O (log(n)/n) 20 Following this, the algorithmic stability-
consists of the "sampling
Cooresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

based excess risk bounds were further explored by Yuan and Li [52 53 Yi et al. [5]] while their results are all weaker than Ollog (n)/n). Thus, a natural question
Can algorithmic stabilätybaseed technique provide high probability excess risk bounds better than O(1/n)?
The main results of this paper answer this question positively. Roughly speaking, under proper regularity conditions, we establish the first high probability excess risk bounds that are dimension- free with the rale O (log" (n)/n²) for models obtained by empirical risk minimization (ERM), PGD and stochastic gradient descent (SGD). To do so, our core technique is generalizing the standard concept of algorithmic stability of loss function to its gradient, i.e., the "uniform stability in gradients" in Definition 2 [24]. With this, we can connect it with a sharper generalization bound, compared with the classical ones
Next, we outline our idea the sharper bound excess risk. Notably, under some regularity conditions e.g. strongly convexity or upper bounded by the square of its gradient norm. Then, by invoking the algorithmic stability of gradient, we prove generalization bound w.r.. gradient of loss function. With this, an upper bound to the gradient of excess risk is obtained, which naturally leads to the bound of excess risk, under strongly convexity of PL. conditions. During the proof, our generalization bound w.r.t. gradient consists of algorithmic stability coefficient, gradient of loss function on trained parameters, and terms in (1/nn). Intuitively, the gradient related term trained model tends to close zero. Thus, combining the derived generalization bound on gradient and analysis on optimization error induces our sharper bound O (log" (n)/n²) on excess risk.
(PL) condition [20], the loss function is
Finally, we summarize our contributions as follows, and compare our results with the previous ones in T
Under proper regularity conditions, we sharpen the algorithmic stability-based generalization bound i.e., from Ô (1 (1/n) 20 to Ô (1/n²) via the stability of gradients. To the best of our knowledge, this is optimal dimension-free results based on algorithmic stability up till now.
With our framework, we derive the first dimension- frree high probability excess risk bounds of O (log (n)) /n²) for ERM, PGD, and SGD, addressing an open problem posed in Xu and Zeevi [50]. For SGD, we have also shown that under the same assumptions, an equally tight bound can be achieved with fewer iterations.
Notations. In this paper, we consider a set of training data independent and identically distributed (i.i.d.) observations S -z {z1...., ] sampled from a probability distribution p defined on Z, S (zi,-.., } be its independent copy. For any [n]. define 5(i) (Zi..... 2;-1, 2/1 244 1,...... Zn. by replacing the i-th sample in S with another i.i.d. sample z/. Based on the training set S, our goal is to build model with parameter w E W C IRd We denote the performance of model with parameters w evaluated on by loss function f [w; =), where f: W x 2 + R,, Then the population risk and the empirical risk of E W, are respectively denoted
Fs(w)= 1 Σ fw:;))
F(w) EE-p (w;:))]
We respectively denote w² E arg willwww F(w), and w E arg win Fs (w). and learned model parameters A(S) W be the output of (possibly randomized) algorithm on the training set S. In general, we will care the generalization error of model A(S) defined as the gap between population risk and empirical risk i.e., F F(A(S)) Fs(A(S)). Besides, the excess risk F(A(S)) F(w*) decides the performance of model is more important in practice. Finally, the notation (()) hides logarithmic factors and we denote Ly-norm of real value Y as ||Y||, (B]])Y)")) Similarly, let || denote the norm in a Hilbert space H. For a random variable X taking values Hilbert space, its norm is defined by X 1p = (E [| )
2 Related Work
Algorithmic stability is a classical approach in generalization analysis, which can be traced back to the foundational works of Vapnik and Chervonenkis [46). It gave the generalization bound by

---

Table 1: Summary of high probability excess risk bounds. All conclusions herein assume Lipschitz continuity, and all SGD algorithmss presuppose bounded variance of the gradients; therefore, these two assumptions are omitted in the table. Abbreviations: uniform convergence - UC, algorithmic
stability - AS, strongly convex + SC, low noise [55] + LN, Polyak-LLojasewicz condition - PL.
Reference
Algorithm
Method
Assumptions
Iterations
Sample Size
Bounds
55
ERM
UC
Smooth, SC, LN
Ω
x'd M=
Ô (
ERM
UC
Smooth, PL, LN
Ô (+tz)
50
AP
PGD
UC
Smooth, PL, LN
x
log(n)
f
Y'd
Ô (
UC
Smooth, PL. LN
T n²
Ô (+))
SGD
AS
Smooth, SC
Tx n²
Ô (
ERM
AS
SC
Ô (
20
PGD
AS
Smooth, SC
T x log(n)
Ô (
ERM
AS
Smooth, PL, LN
Ω
Ô
PGD
AS
Smooth, PL, LN
T x log(n)
Ω
This work
PGD
AS
Smooth, PL, LN
x log(n)
Ω
SGD
AS
Smooth, PL., LN
Tx n
Ô (
SGD
AS
Smooth, PL
Txn n
Ω
analyzing the sensitivity of particular learning algorithm when changing one data point in the dataset. Modern method of stability analysis was established by Bousquet and Elisseeff (3] where they presented the concept of uniform stability.
Since then, lot of works based uniform stability have emerged. Some of the existing results built their bound in expectation 51 5 8, while it is weaker than the high probability bound as discussed. To resolve this, Bousquet and Elisseeff [3), Elisseeff et al. 19]. Feldman and Vondrak
[2], Bousquet et al. 4) Klochkov and Zhivotovskiy (20), Yuan and Li [52] 53 Fan and Lei considered high probability bounds. Besides that, some other generalized algorithmic stabil- ity measures are further developed to study the generalization. For instances, uniform argument stability [ uniform stability in gradients [24[10) [10, average stability [40] (1). hypothesis stabil-
11
10
ity 3 hypothesis set stability
[13], pointwise uniform stability (10), PAC-Bayesian stability (28), [8), and collective stability [32]. However, the optimal generalization bound
locally elastic stability
among these results is O(log(n)/n) which is weaker than our O (log* (n)/n²) in this paper.
Notably, the O (Iog"(n)/m) (n)/n²) /2²) generalization bound under PL condition or strongly convexity has also been developed by uniform convergence technique as in Zhang et al. [55), Xu and Zeevi [50]. However, in contrast to ours, their results are restricted to the number of samples n M(d).
3 Stability and Generalization
In this section, we first introduce the stability of gradient, and connect it to the generalization bound w.r.t. gradient. Following this, under proper regularity condition, i.e., PI. condition, we can extrapolate the generalization of gradient to the loss function. With the desired generalization bound, by combining it with the optimization error, we can further bound the excess risk.
Firstly, let us introduce some basic definitions here. Before presenting our main results (Theorem) | and Theorem 2 i.e., the generalization bound w.r.t. gradient, we emphasis that they do not require the smoothness assumption and PL condition. This indicates their potential applications within the nonconvex problems as well.
Definition 1. Let f W + R. Let M, M.Y.P 0.
3

---

We say f is M -ipischhtt if
If(w) - f(ww)) -Wwwwwlla Vw, w/ E W.
We say f is 7-smooth if
[VS(w) WV((w)-V((w)ll S - Vw, E..
Let Let win f(w). We say f satisfies the Polyak-Lojasien (PL) condition with parameter μ 0 W
f(w) - f 1 [V Vw e W.
2μ
3.1 Sharper Generalization Bounds in Gradients
Let us start with the notation of algorithmic stability w.r.t. gradient.
Definition 2 (Uniform Stability in Gradients). Let A be a randomized algorithm. We say A is Suniformlysttbbbe in gradients for all neighboring datasets S,S(), we have
sup BA
V((((()))))(((( ): 5
(I)
Remark 1. The notation of gradient-based stability was firstly introduced by Lei [24]. Fan and Lei [10] to describe the generalization performance for nonconvex problems. Because in this regime, the exploration usually focuses on the first-order critical condition i.e., VF(A(S)) Then, with the stability on gradient, the "generalization of gradient" can be expressed |VF((A(S)) (Fs(A(S))]la Thus, combining with triangle inequality and standard results on gradient of empirical risk |/ (A()))) characterizes the desired (VF(A())) Further more, under a small ([)F(A()))lle 2 the PL condition (see Definition] T leads the desired bound on excess risk. This explains why the gradient-based stability is the core idea of this paper.
With the uniform stability in gradients, we prove that implies the generalization of gradient following theorem.
Assume for any z, f(,,2) M- M-Lipschitz. If A is E-umiformly-sabllee in gradients, then for any E (0, 1), the following inequality holds with probability at least
Theorem 1 (Generalization via Stability in Gradients [TO).
4M (1 eetee/loog (e/0)
EA (FF((())) (A(S)))) $23
+8x 2 (V2 1) [no] log (e/6).
Remark 2. Notably, our Theorem T is similar to Theorem 3 in [10], while ours has a constant-level improvement owing sharper concentration inequality i.e., Lemma in Appendix. However, the generalization bounds in both of the aforementioned theorems have dependence O (M/ Vi), which leads to a O /n) generalization bound of loss function, and it is weaker than desired result. Thus, we derive the following sharper generalization bound of gradients under same assumptions.
Theorem 2 (Sharper Generalization via Stability in Gradients). Assume for any f(, z) is M- Lipschitz. If A is B-uniformlyy-tahbe in gradients, then for any (0, 1), the following inequality holds with probability at least
Ex V7S
1EZ, II [[A((S)) log (6/8)
(1 + 32n 1og(3/5)) log (6/5)
M log(6/8)
+ 16 2 VeB (n)] log (3e/8) + 32 [og2(n)] Vlog (3e/8).
Remark We begin by comparing the generalization bound of gradient in the proposed The- orem 2 with Theorem The critical difference is that constants in 1/v'n is improved from
o M / log (e/0) to O /EEz [[V]f(((): 2) log (1/8) + log(1/))) since M is the max- imal gradient norm. Notably, the proved dependence Ez [|| (AA()) 1 is interpreted as the

---

squared gradient norm of the loss functions on test data, under the optimized model parameters A(S). Thus, it is supposed to be small, compared with constant M, since the optimization algorithms often provide parameters approaching the optimal solution.
Moreover, our bound is restricted to any specific algorithm and without dependence on the numher of optimization iterations. Clearly, this is an improvement to the results constructed under a specific algorithm, e.g., the ((T/n) generalization bound under SGD in Bassily al. [T] Lei [24 which is only applied to SGD, and becomes vacuous when iteration steps I" exceeds n.
Next, we give the proof sketch to our Theorem 2 which is motivated by the analysis in Klochkov and Zhivotovskiy [20]. Similar to the standard result in Bousquet and Elisseeff [3], which says the general- ization of loss function is implied by its stability and the variance of stabiliity Similar result is general- ized to the gradient. During our proof, such algorithmic stability of gradient is characterized by the gap (S) (5) [s, [b, with h, = Ex Ez V 2)] - Vf(A(S()), =)] and variance. The stability is 3 appears in Theorem 2 While instead of controlling its variance with maximal gradient norm, we can link it to the coefficient Ez [[/V ((A(S); 2) which implies
our result. We refer readers for more details to the proof in Appendix.
To further characterize the Ez [IV fA((): 2
need the strong growth condition (SGC) imposed in Solodov [42]. Vaswani et al. (48). Lei 24). which is satisfied many important loss function, e.g., squared-hinge loss with finite support
48
Definition 3 (Strong Growth Condition). The SGC holds, if
Ez ((;; 2) S XI[VF(w)lB.
Proposition 1 (SGC case). Let assumptions in Theorem any 0, r > O, with probability at least 5, we have
2 hold and suppose SGC holds. Then for
EA VE $ EA [I 1+ (AM log(1/) + 3 llg(n)) log (1/5)
n
Proposition build a connection between the population gradient error and the empirical ones under Lipschitz, nonconvex, nonsmooth and SGC conditions. The conclusion is directly obtained from the triangle inequality, Young's inequality, and SGC. Since the model parameters A(5) is optimized, the [A()) is supposed be small. Thus, the Proposition | valuable upper bound that of population error, for algorithm with stability w.r.t. gradient (small (3).
Remark Finally, we make discussion to the priority of our Theorem 2 solely in that of gradient
generalization. In a word, we address an open problem posed by [50), namely achieving bound to generalization error of gradient independent of the dimension d. Concretely, Xu and Zeevi [50] prove
generalization bound via uniform convergence technique [47 is
(VA()))) (As()
Ez V/www; 3 (1g()/0)
+ log(1/0) + max |IA(S)- -
10000-wwllaa w'll,, 1
d
(2)
n
which is the optimal result when we only consider the order of n. The uniform convergence results related to the dimension d, which are unacceptable in high-dimensional learning problems. Note that (2) requires an additional smoothness-type assumption. As a comparison, when f is smooth and A is a deterministic algorithm, our result in Theorem becomes
[FF((())) - VFs(A(S))ls
1olog log(1/5) Ez [IV](w' 2) log(1/8) + |[A(S) w'lly log(1/5)
Above inequality also holds in nonconvex problems and implies that when the uniformly stable in gradients parameter is smaller than 1/ /n, our bound tighter than 2 and dimension
independent.
3.2 Sharper Excess Risk Bounds
In this subsection, we proceed to the desired upper bound of excess risk. The result is obtained by applying PL condition to Theorem 2 as in the following Theorem.
5

---

Theorem 3. Let assumptions in Theorem 2 hold. Suppose the function f is 7-smooth and the population risk F satisfies the PL condition with parameter p. w is the projection of A(S) onto the solution set arg wew F(w). Then for any ō E (0, 1). when 2 32,² log (0/8), with probability
at least 5, we have
E [A(((A(SM) - F(w")
BA IIV FF(w") log(1/0) M (1/0) jnn
8 log"* log" (1/6)
1
pan
Remarks 5. Notably, in Theorem 3 the PL condition is imposed the population risk. This can be hold for many cases within classical learning theory. For instance, the classical linear regression setup: fwu; (ar 3)) lyy (w, 2)11,, where y = (w", x) v, with (0, and N(0, a² laxa). In this case, we have μ 2.
Theorem implies that excess risk can be bound by the optimization gradient enror FVFs(A(S)) and uniform stability in gradients B. Notably, the theorem is applied to any algorithm with uniform stability in gradient. Latter, we will analyze the stability for specific algorithm in the next Section. Note that the assumption F (w*) < ((1/n) in) is common and can be found in Srebro et al. 44), Lei and Ying [26], Liu et al. 30, Zhang
al. (55), Zhang and Zhou [54] when analyzes sharper bounds. In our bound, when F(w") < O(1/n), and the stability 3 = O(1/n), we can obtain the desired O(1/vi /n²) upper bound for excess risk when the empirical risk is sufficiently minimized by algorithm A.
To further compare result with the optimal results based algorithmic stability, i.e., 20), they only impose the assumption of bounded loss function, which is relative weaker than ours (smoothness and PL condition). However, our result is supposed to be sharper than their Ö(3 + 1/n), since ours has the potential to be Ö(1/r²) but their results are at most ((1/n) even if the algorithm is stable enough. More than that, the imposed smoothness and PL conditions in our theorem
also used in Klochkov and Zhivotovskiy (20 to further analysis the algorithmic stability for PGD, whereas their excess risk bound becomes ((1/n). However, our sharper bound indicates that they do not fully leverage these assumptions. The improvement is mainly from the novel stability in gradient during our analysis. This is also why our work can fully utilize these assumptions.
In addition, results provide a more granular analysis dependent optimal parameters. On one hand, when the algorithm's 's stability 3 = O(1/vn) the upper bound, according to [20), can at most reach the order of ((1/vn) due to the algorithm's stability constraints. In contrast, our result shows that even under the assumption that (F(w") O(1), treating F(w") ) as a constant, we achieve an order of (1/nn) under the same algorithmic stability. On the other hand, their result is insensitive to the stability parameter being smaller than O11/n) and their best rates can only up to Ö(1/n). Our results can be up to ((1/n²) under some specific assumptions. We will discuss
Section
While Theorem 3 considers the algorithm's uniform stability in gradients rather than the classic uniform stability, calculating the uniform stability in gradients is not more challenging than the classic uniform stability. We discuss uniform stability in gradients for common algorithms such as ERM, PGD, and SGD in Section 4 Our results can be easily extended other stable algorithms. Due the smoothness property linking uniform stability in gradients with uniform argument stability, many that explore uniform argument stability can also utilize our method.
works I 12 17
Finally, we notice that there are currently several studies based on Klochkov and Zhivotovskiy 20
addressing different settings, such as differentially private models [18] and pairwise learning [27]. These studies also utilize the smoothness assumption in their optimization analysis. However, since they rely on the method established in Klochkov and Zhivotovskiy 20 for the generalization aspect
of their research, they can only achieve an Ö(L/n) bound at most. In contrast, they can easily achieve better results without making additional assumptions using our method.
4 Application
In this section, we take ERM, PGD, and SGD as examples to provide detailed discussion of how our algorithm can be applied to common methods, resulting in tighter upper bounds.

---

4.1 Empirical Risk Minimizer
Empirical risk minimizer one of the classical approaches for solving stochastic optimization (also referred to as sample average approximation (SAA)) in machine learning community. The following lemma shows the uniform stability in gradient for ERM under the PL condition and y-smoothness assumptions.
Lemma (Stability of ERM). Suppose the objective function f is M-Lipschitz and y-smooth, the empirical risk Fg and Fgo, satisfy the PL condition with parameter μ.. Let w (S be the ERM of f.s. Ego (w) that denotes the empirical risk on the samples S = ... 20,22/ ... knd and w (S) be the
ERM of Fs(w) the samples S {21, 2,,... Zn.. For any S and S, there holds the following
uniform stability bound of ERM:
16M
V2 2,
| (S(("(("));:)
(S)= -v
n²y²
Then, we present the application our main sharper Theorem 2 In the PL condition and smooth case, we provide a up to Ô (1/n²) high probability excess risk guarantee valid for any algorithms depending on the optimal population error F(w").
Theorem 4. Let assumptions in Theorem areoremaand Jndd hoodd Suppose the function f is nonnegative.
Then for any 5 E (0, 1), when 32, log (6/6) with probability at least 1 8, we have
F(w" (S)) F(w') yf((") log (1/0)
log? lologg((1)))
Jan
n=
Remark 6. Theorem shows that when the objective function f is M M-Lipschitz, 7-smooth and nonnegative, at the same time, both the empirical risk P's and the population risk F' satisfies PL condition with parameter μı, then the high probability risk bounds can be up to Ô (1/n²) for ERM. The most related work to ours Zhang et al. (55). They also obtain the Ô (1/n2)-typp bounds for ERM by uniform convergence of gradients approach under the same assumptions. However, they need the sample number n 22(rdd/"²), which related to the dimension d. Our risk bounds are dimension independent and only require the sample number 1(>>/ /1²)) Comparing with
Klochkov and Zhivotovskiy (20), we add two assumptions, smoothness and F(w < (1/n),
the later of which is a common assumption towards sharper risk bounds 44 26 30 55 low-noise, but our bounds are also tighter, from ((1/n) to Ô (1/n²).
called
Our results are asymptotically optimal, which aligns with existing theories. According to the classical asymptotic theory, under some local regularity assumptions, when n. - oc, it is shown in the asymptotic statistics monographs 45 that
Vn(w (S) (1S)-w w') -4 N(O, X(0, "HH
(3)
where w (SS) denotes the ERM algorithm, H = V²F(w"), Q is the covariance matrix of the loss gradient at w" (also called Fisher's ' information matrix): Q = E 2 f (AT
denotes the transpose of matrix A), and - means convergence in distribution. The second-order Taylor expansion of the population risk around w" then allows to derive the same asymptotic law for the scaled excess risk 2n(F'ww (w (S) F(w")). Under suitable conditions, this asymptotic rate is usually theoretically optimal [44] For example, when f(w; is a negative log-likelihood, this asymptotic rate matches the Hajek-LeeCam asymptotic minimax lower bound [16] 23) We then analyze the result in Theorem
the self-bounded smoothness property |/ fw 2 Ayff(":z), we get the following result for Theorem
4 In the proof of Theorem 3, before
F(w (S)) F(w") B[IVs(w"; =))] (og(1/8) log(1//))))))) + 222,21 log² (1/6(
u²n²
Our result is the finite sample version of the asymptotic rate 3). which characterizes the critical sample size sufficient to enter this "asymptotic regime". This is because the excess risk error F(w* (S)) - F(w*) can be approximated by the quadratic form (W)(S) w H(w" (S) w*). 1/u is a natural proxy for the inverse Hessian H and E[llV f[w"; 2)] is natural proxy for Fisher's information matrix Q. Furthermore, when discussing sample complexity, Xu and Zeevi 50 constructed simple linear model to demonstrate the constant-level optimality of the sample complexity lower bound Q ((d32/ /2²) under such conditions. Our theorem further reveals, through the use of stability methods, that this complexity lower bound can be independent of the dimensionality d.
7

---

4.2 Projected Gradient Descent
Note that when the objective function f is smooth and the empirical risk Fs satisfies the PL condition, the optimization error can be ignored. However, Klochkov and Zhivotovskiy (20) does not use smoothness assumption for their generalization bounds, which only derive high probability excess risk bound of order (1/n)) after T (Iog(n)) steps. In this subsection, we provide sharper risk bound under the same iteration steps, which is because our generalization analysis also fully utilized the smooth assumptions. Here we introduce the procedure of the PGD algorithm.
Let Wi E I&d be an initial point and } be sequence of positive step sizes. PGD updates parameters by
W++1 = 1l (we- - TN V (w:)),
where V Fs(w,) denotes a subgradient of Fs w.r.t. w, and Tl is the projection operator onto W.
Lemma 2 (Stability of Projected Gradient Descent [22 17). Suppose the objective function f is M- Mipipschitz and 7-smooth, the empirical risk Fs and Fgin satisfy the PL condition with parameter
μ.. Let w be the output of Fg (w) on 1-th iteration on the samples 5(6) = {21,-.., 2.p-.. 2n) in running PGD, and w, be the output of F's Fs( on t-th iteration on the samples S {21, ..1 ... Ris ...y 2n, in running PGD. Let the constant step size Tht 4. For any ( and S, there holds the following uniform stability bound of PGD:
V ff(wl; V Vf(w:))) 4M²72 n²y²²
Ya E 2,
The derivations of Feldman and Vondrak [12] in Section 4.1.2 (See also [17 in Section 3.4) imply that the objective function f is 7-smooth and M-Lipschitz, and the empirical risk Fs and Fitoo satisfy the PL condition with parameter μa, then PGD with the constant step size 1) = is 2M
-uniformly np
argument stable for any number of steps, which means that PGD gradients regardless of iteration steps.
(2M+)
-uniformly-stablee in
Theorem 5. Let assumptions in Theorem Jand Lemma Toold. Suppose the function f is nonnegative and w belongs to the projected set W. Let (Welt be the sequence produced by PGD with 1/: = 1/7-
Then for any 5 E (0, 1), when 32,² log (6/5), with probability at least
5, have
F(WT+1) - -F(+))))(ww))) - (1-14)
14
27
"f("")
log log (1/8)
2² log² log (1/8))
pam
Furthermore, assume F'w") < ( and let T x llo(()) we have
F F(wr+1) F(w") S M27a log? n log?
n²n²
Remark Theorem 5 shows that under the same assumptions as Klochkov and Zhivotovskiy 20
our bound is O F(w [1g(11/8) log" log" Comparing with their bound O log(n) log(1/8)
we are sharper because ((w*) is the minimal population risk, which is common assumption towards
sharper risk bounds 43 26
30 55 (54) We use this assumption to demonstrate that under low-noise
conditions, our bounds can achieve the tightest possible rate of Ô(1/n²). This is because we also fully utilized the properties of smooth in the process of analyzing generalization errors. Considering that smooth a very common assumption in optimization communities, our work can better utilize existing optimization work and obtain better excess risk bounds under the same assumptions.
4.3 Stochastic Gradient Descent
Stochastic gradient descent optimization algorithm has been widely used machine learning due to its simplicity in implementation, low memory requirement and low computational complexity per iteration, as well as good practical behavior. We provide the excess risk bounds for SGD using our method in this subsection. Here we introduce the procedure of the standard SGD algorithm.
Let W1 Rd be an initial point and {nc) be sequence of positive step sizes. SGD updates parameters by
W Hw (we Vf (We) (w))
8

---

where Vf(;;; 2,,) denotes a subgradient of f w.r.t. Wy and it is independently drawn from the uniform distribution over [n]] := [1.
Lemma 3 (Stability of SGD). Suppose the objective function f M Lipschhitz and y-smooth, the empirical risk Fs and gg satisfy the PL. condition with parameter μs. Let wi be the ouiput of Fgua (w) on t-th iteration the samples 5(1) = {=1,... 24y.., 2n3 in running SGD with The 22+1 Bntt+1yz and we be the output of Fs(w) on t-th iteration on the samples S == -=1zz {zi,... ..., Ze..... 2n in running SGD with th 2u(141)z For any 563) and S and any E Z, there holds the following
2++
uniform stability bound of SGD:
6M 48M2 fpr
BA ff(wE=)- V
+
n²p²²
Next, we introduce necessary assumption in stochastic optimization theory. Assumption 1. Assume the existence of > 0 satisfying
EN (ww a.) - VFs (w:)ll)) So? VEN,,
(4)
where Ei, denotes the expectation w.r.t it-
Remark 8. Assumption D is a standard assumption from the stochastic optimization theory 34
14
15 21
56 2 25). which essentially bounds the variance of the stochastic gradients for dataset S.
Theorem 6. Let Assumptions in Theorem 2ndd Lemma L Suppose Assumption [ holds and the
21+11 function f is nonnegative. Let {weht be the sequence produced by SGD with πhe 2p(1+1yz Then
for any 8 > when n 32,² log (6/8) with probability at least 1,8, we have
n²
EA [F(W++1]] - F(w") x FF('") log(1/8)
(
Mº log? n log? (1.6).
an
Tp
n2
1
Furthermore, assume T x n² and F(w*)= < O we huve
F(wr+1) - F(ww) M2ya log" log2 (1/8)
ntn²
Remark Theorem implies that high probability risk bounds for SGD optimization algorithm can be up to ((1n?²) and the rate is dimension-free in high dimensional learning problems. We compare Theorem 6 with most related work. For algorithmic stability, high probability risk bounds in Fan and Lei [0] is up to ((1/n) when choosing optimal iterate number T for SGD optimization algorithm. To the best of knowledge, we are faster than all the existing bounds. The best high probability risk bounds ((/nn) are given by [29] via uniform convergence, which require the same iterate number T > n and the sample number n = 9(> h//dd/pp depending on dimension d.
Although a considerable amount of theoretical (eg: [27] and practical (eg: 335 evidence indicates that multi-pass SGD can enhance the model's generalization performance. Someone may only utilize one-pass SGD in practice due the large volume of data, which means that T x n. In fact, when T Txx n and F( F(w*) O(1), our bound is Ö(1nn), which is also the sharpest hight probability bound under T x iterations. For comparison, there are two results in stability analysis that are similar to ours. One is the (11nn) result when 7 = n 226] but it pertains to the expected version and also needs (ww") = 0. The sigh-probbbility version significantly more challenging. Currently, the best result under the high-probability version is also ((1nn) (29 but 29 requires x n² iterations.
5 Conclusion
In this paper, we derive sharper generalization bounds in gradients nonconvex problems, which can further be used to obtain sharper high probability excess risk bounds for stable optimization algorithms. In application, we study three common algorithms: ERM, PGD, SGD. To the best of our knowledge, we provide the sharpest high probability dimension independent (11/n2)-typ for these algorithms.

---

Acknowledgments and Disclosure of Funding
This research was supported by National Key Research and Development Program of China (NO. 2024YFE0203200), National Natural Science Foundation of China (No.62476277) CCF-ALIMAMA TECH Kangaroo
ACA-ALIMAA OF 2024008), and Huawei-Renmin University joint program on Information Retrieval. We also acknowledge the support provided by the fund for building worldclass universities (disciplines) of Renmin University of China and by the funds from Beijing Key Laboratory of Big Data Management and Analysis Methods, Gaoling School of Artificial Intelligence. Renmin University of China, from Engineering Research Center of Next- Generation Intelligent Search and Recommendation. Ministry of Education, from Intelligent Social Governance Interdisciplinary Platform, Major Innovation & Planning Interdisciplinary Platform for the "DoubleFirst Class" Initiative, Renmin University of China, from Public Policy and Decision- making Research Lab of Renmin University of China, and from Public Computing Cloud, Renmin University of China.
References
[1] R. Bassily. V. Feldman, C. Guzmán, and K. Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. In Proceedings of the 34th International Conference on Neural Information Processing Systems (NeurlPS), volume 33, pages 4381-439) 2020.
[2] L. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. SIAM
review, 60(2):23-3111, 2018.
[3] O. Bousquet and A. Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:
499-526, 2002.
[4] O. Bousquet, Y. Klochkov, and N. Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, pages 610-626. PMIR, 2020.
[5] Z. Charles and D. Papailiopoulos. Stability and generalization of learning algorithms that converge global optima. In International conference machine learning, pages 745-754. PMIR, 2018
[6] P. J. Davis. Gamma function and related functions. Handbook of mathematical functions, 256, 1972.
[7] V. De la Pena and E. Giné. Decoupling: from dependence to independence. Springer Science & Business
Media, 2012.
[8] Z. Deng, H. Hc, and W. Su. Toward better generalization bounds with locally clastic stability. In International Conference on Machine Learning, pages 2590-2600. PMLR, 2021.
191 A. Flisseeff, T. Exgeniou, M. Pontil, and I.. P. Kaclbing. Stability of randomized learning algorithms. Journal of Machine Learning Research, 6(1), 2005.
[10] J. Fan and Y. Lei. High-probability generalization bounds for pointwise uniformly stable algorithms. Applied and Computational Harmonic Analysis, 70: 632,, 2024.
[11] V. Feldman and J. Vondrak. Generalization bounds for uniformly stable algorithms. Advances in Neural Information Processing Systems, 31, 2018.
[12] V. Feldman and J. Vondrak. High probability gencralization bounds for uniformly stable algorithms with nearly optimal rate. In Conference on Learning Theory, pages 1270-1279. PMLR, 2019.
[13] D. J. Foster, S. Greenberg, S. Kalc, H. Luo, M. Mohri, and K. Sridharan. Hypothesis set stability and generalization. Advances in Neural Information Processing Systems, 32, 2019.
[14] S. Ghadimi and G. Lan, Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on optimization, ((4))2341122368 2013.
[15] S. Ghadimi, G. Lan, and H. Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic
composite optimization. Mathematical Programming, 155(1):267-33)) 2016.
[16] J. Hájek. Local asymptotic minimax and admissibility in estimation. In Proceedings of the sixth Berkeley
symposium on mathematical statistics and probability, volume 1, pages 175-194, 194, 1972.
[17] M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pages 1225-1234. PMLR, 2016.
[18] Y. Kang, Y. Liu, J. Li, and W. Wang. Sharper utility bounds for differentially private models: Smooth and non-smooth. In P Proceedings of the 31 ACM International Conference on Information & Knowledge Management, pages 951 961, 2022.
[19] H. Karimi, J. Nutini, and M. Schmidt. Linear convergence of gradient and moximal-graddien methods under the polyak- tojasikwoaiiiiczzz condition. In ECML, pages 795-811. Springer, 2016.
[20] Y. Klochkov and N. Zhivotovskiy. Stability and deviation optimal risk bounds with convergence rate
o /m). Advances in Neural Information Processing Systems, 34:506555076, 2021.
[21] 1. Kuzborskij and C. Lampert. Data-dependent stability of stochastic gradient descent. In Proceedings of the 35th International Conference Machine Learning (ICML), pages 3815-2824 PMLR, 2018.
10

---

[22] R. Latala and K. Oleszkiewicz. On the best constant in the khinchin-kahann inequality. Studia Mathematica, 109(1):101-104, 1994.
[23] L. Le Cam et al. Limits of experiments. In Proceedings of the Sixth Berkeley Symposiun on Mathematical
Statistics and Probability, volume I, pages 245-261. University of California Press, 1972.
[24] Y. Lei. Stability and generalization of stochastic optimization with nonconvex and nonsmooth problems.
In The Thirty Sixth Annual Conference on Learning Theory, pages 191 191-227. PMLR, 2023.
[25] Y. Lei and K. Tang. Learning rates for stochastic gradient descent with nonconvex objectives. IEEE
Transactions on Pattern Analysis and Machine Intelligence, 43(12):4505 4511, 2021.
[26] Y. Lei and Y. Ying. Fine- line-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning, pages 5809-5819. PMLR, 2020.
[27] Y. Lei. M. Liu, and Y. Ying. Generalization guarantee of sgd for pairwise learning. Advances in neural information processing systems, 34:21216-22 21228, 2021.
[28] J. Li, X. Luo, and M. Qiao. On generalization etror bounds of noisy gradient methods for non-convex learning. In International Conference Learning Representations, 2020.
[29] S. Li and Y. Liu. Improved learning rates for stochastic optimization: Two theoretical viewpoints. arXiv preprint 1XXYx:2107.0880
2021.
[30] M. Liu, X. Zhang, L. Zhang, R. Jin, and T. Yang. Fast rates of erm and stochastic approximation: Adaptive to error bound conditions. Advances in Neural Information Processing Systems, 31, 2018.
[31] T. Liu, G. Lugosi, G. Neu, and D. Tao. Algorithmic stability and hypothesis complexity. In International Conference on Machine Learning, pages 2155--1667. PMLR, 2017.
[32] B. London, B. Huang, and L. Getoor. Stability and generalization in structured prediction. The Journal of Machine Learning Research, 17(1):7808 7859, 2016.
[33] X. Luo and D. Zhang. Khintchine incquality on normed spaces and the application to banach-mazur distance. arXiv preprint wwXiv:2005.03722 2020.
[34] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4):1574-160) 2009.
[35] L.. Pillaud- Vivien, A. Rudi, and F. Bach. Statistical optimality of stochastic gradient descent on hard lcarning problems through multiple passes. Advances in Newral Information Processing Systems, 31, 2018.
[36] I. Pinelis. Optimum bounds for the distributions of martingales in banach spaces. The Annals of Probability,
pages 1679-1706, 1994.
[37] A. Rakhlin, S. Mukherjee, and T. Poggio. Stability results in learning theory. Analysis and Applications, 3
(04):397-417, 2005.
[38] O. Rivasplata, E. Parrado-Hernánddzz,, J. S. Shawe-Taylor, S. Sun, and C. Szepesvári. Pac-bayes bounds for stable algorithms with instance-dependent priors. Advances in Neural Information Processing Systems, 31, 2018.
[39] S. Shalev-Shwart and S. Ben-David. Understunding machine learning: From theory to algorithmss Cambridge university press, 2014.
[40] S. Shalev-Shwarvz, O. Shamir, N. Srebro, and K. Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 11:2635-2670, 2010.
[41] S. Smale and D.-X. Zhou. Learning theory estimates via integral operators and their approximations. Constructive approximation, 26(2):153 172, 2007.
[42] M. V. Solodov. Incremental gradient algorithms with stepsizes bounded away from zero. Computational Optimization and Applications, 11:23-35 35, 1998.
[43] N. Srebro, K. Sridharan, and A. Tewari. Optimistic rates for learning with smooth loss. arXiv preprint arXiv: arXiv:1009 10090089996 2010.
[44] A. van der Vaart. On the asymptotic information bound. The Annals of Statistics, pages 1487-1500, 1989.
[45] A. W. Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
[46] V. Vapnik and A. Chervonenkis. Theory of Pattern Recognition. 1974.
[47] V. N. Vapnik. An overview of statistical learning theory. IEEE transactions on neural networks, 10(5):
988 999, 1999.
[48] S. Vaswani, F. Bach, and M. Schmidt. Fast and faster convergence of sgd for wer-parameterized models and an accelcrated perceptron. The 22nd international conference on artificial intelligence and statistics, pages 1195-1204, PMLR, 2019.
[49] R. Vershynin. High-dimensional probability: introduction with applications in data science, volume 47, Cambridge university press, 2018
[50] Y. Xu and A. Zeevi. Towards optimal problem dependent generalization error bounds in statistical learning theory. Mathematics of Operations Research, 2024.
[51] M. Yi, R. Wang, and Z.-M. Ma. Characterization of excess risk for locally strongly convex population risk. Advances in Neural Information Processing Systems, 15:21270-21288, 2022.

---

[52] X. Yuan and P. Li. Exponential generalization bounds with near-optimal rates for 1 q-staalle algorithms. In The Eleventh International Conference on Learning Representations, 2023.
[53] X. Yuan and P. Li. I. 2-uniform stability of randomized learning algorithms: Sharper generalization bounds
and confidence boosting. Advances in Neural Information Processing Systems, 36, 2024.
[54] L. Zhang and Z.-H. Zhou, Stochastic approximation of smooth and strongly convex functions: Beyond the o(1/)) convergence rate. In Conference Learning Theory, pages 3160 3 1199. PMLR, 2019.
[55] L. Zhang. T. Yang, and R. Jin. Empirical risk minimization for stochastic convex optimization: O(1/n)-and and
22 of risk bounds. In Conference Learning Theory, pages 1954 1979-1979. PMLR, 2017.
[56] Y. Zhou, Y. Liang, and H. Zhang. Generalization error bounds with probabilistic guarantee for sgd in nonconvex optimization, arXiv preprint arXiv:1802.06900 06900, 2018
12

---

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: We have checked that the abstract and introduction accurately reflect our contributions and scope.
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 long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have clearly stated the required assumptions for each theorem and lemma, and the conditions for the assumptions hold are also stated the main text.
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 a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an 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 set of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification: We have clearly stated the required assumptions for each theorem and lemma, and all proofs are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors 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 or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
This paper focuses on learning theory.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to 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 to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to 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 new 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.
5. Open access to data and code
14

---

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

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper focuses on learning theory and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, 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 the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:///rrrrp..ccoooooc/caaacaaa
Answer: [Yes]
Justification:
We have reviewed the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not 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 in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper focuses on learning theory and there is no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

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

---

If this information is not available online, the authors are encouraged to reach out to the asset'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: The 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/mmoel 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. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve 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 the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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 expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this paper does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
19

---

A Additional definitions and lemmata
Lemma 4 (Equivalence of tails and moments for random vectors (.. Let X be random variable with
||
I vpa + pb
for some b 2 0 and for any 2 2. Then for any å (0, we have, with probability at least 1 8,
| S e av log (7) + blog blog
Let {X+]i=1 be a sequence of i..d. random variables taking values in a real separable Hilbert space. Assume that [[[x;] = and || s M, v1 sis n, then for all 8 E (0, 1), with probability at least we have
Lemma 5 (Vector Bernstein's inequality (36 4T).
= o²,
20 log(3)
M Mogg? 3
S
n
n
72
Definition (Weakly caff-Bounded Function). Assume that a, function f = [0, +00) is said to be (a, b)-wellly seff-buunded if there exist functions fo -n + [0, +o0) that satisfies for all d n",
Lemma (20)) Suppose that 21,...,22, 2 are independent random variables and the function f: n DD, +oo) is (a, be-wkllly self-bounded and the corresponding function fi satisfy fc(Z") z
f(Z") for Vi E [n] and any Zn E Z". Then, for any > O.
Pr(B.(().....,,.) 2 f(z1,..., zn. + < exp
2uBBf(z1, Zn + 2b
Definition Rudemacher random variable is a Bernoulli variable that takes values #1 with probability each.
B Summary of Our High Probability Excess Risk Bounds.
Our high probability excess risk bounds can be summarized in Table
C Proofs of Section
C.1 An Improved Moment Bound for Sums of Vector-valued Functions
In this section, we present our sharper moment bound for sums of vector-valued functions of independent variables, which is constant-level improvement comparing with [10]. With this inequality, further prove the connection between algorithmic stability w.r.t. gradient and generalization. Notably, our bound relies on the "bounded difference" property, which is similar to uniform stability in gradient. Thus the bound can be further applied in deriving generalization bound gradient, under stability condition.
Lemma 7. Let Z (Z1...., Zn) be vector of independent random variables each taking values in Z, is a independent random variable taking values in A and let g...... gn be some functions: g: - A H. such that the following holds for any i [ni]:
[Eg. (Z) 71]| S G.a.
E Ig. [z. a.s.,
g: satisfies the bounded difference property with B, namely, for any 1,...,n, n, the following inequality holds
sup EA ..... (3.. 2j+1, ..,
(5)
gi (31, ,,,,,,,,,,-1,,, 2/ 2n) $ B.
20

---

Then, for any p 2 2, we have
<4 x 2 (v:) (v2p 2p + 1)n [log, nl
2
+ 2p 1)VGG.
Remark 10. We compare with existing results. The proof is motivated by 4 20
52
53
have also
explored several related problems based on this approach. However, all of them focus specifically on upper bounds for sums of real-valued functions. The result most closely related to Lemma is provided by [1]]. Under the same assumptions, [00 established the following inequality
g
S 5 + 1)p3 [log, n] 2(v2 1)/npG.
(6)
It is easy to verify that our result is tighter than result provided by [10] for both the first and second term. Comparing Lemma] with (6) the larger p is, the tighter our result is relative to (6). In the worst case, when p 2, the constant of our second term is 0.879 times tighter than (6). and the constant of our first term is 0.634 times tighter than (6). This because we derive the optimal Marcinkiewicz-Zyggumre proof.
inequality for random variables taking values in Hilbert space in the
Although Lemma 7 seems to the constant-level improvement, considering that this theorem has other broad applications, we report this result as well. On the other hand, the proof was challenging, as involved establishing the best constant in Marcinkiewicz-Zyymmnn taking values in a Hilbert space, which has its foundations in Chintchine-Kahanee 's inequality. To prove the best constant, utilized Stirling's formula for the Gamma function to construct appropriate functions, establishing both upper and lower bounds. Then using Mean Value Theorem, this approach ultimately led the convergence of the constant as p approaches infinity.
inequality for random variables
The proof of Lemma 7 is motivated by 4. which need the Marcinklewicz--yymmnntt inequality for random variables taking values in Hilbert space and the McDiarmid's inequality for vector-valued functions.
Firstly, we derive the optimal constants in the Marcinkiewicz-Zyygmmad inequality for random variables taking values in Hilbert space.
Lemma (Marcinkiewicz Zyggiin'' s Inequality for Random Variables Taking Values in Hilbert Space). Let X1,.... X, be random variables taking values in Hilbert space with E[X,] = 0. all E [n]. Then for p 2 we have
n
a
Σ X
2 2
np
e
Remark 11. Comparing with Marcinkiewiez-Zygmund inequality given by 100 we provide best constants. Next, we give the proof of Lemma
The Marcinkiewicz-Zyygmnd
inequality can be proved by using its connection to Khintchine- Kahane's 's inequality. Thus, we introduce the best constants in Khintchine-Kahhae &inequality for random variables taking values from a Hilbert space here.
Lemma 9 (Best constants in Khintchine- Kaantehine-Kahane's inequality in Hilbert space
22
33
For all
p E [2, oo) and for all choices of Hilbert space H. finite sets of vectors X....., X, X H, and independent Rademacher variables Ti, rI,...; Tns
E
X
< SCp
X
[(elt
where C₁ = =2
V=
'They assume 2 lc E N. Here give the version of their result with general
21

---

Proof of Lemma g The symmetrization argument goes as follows: Let (r1..... Tn) be i.i.d with
P(r; 1) P(r; -) 1/2 and besides such that r...... In and (Xi...., ,,,) are independent. Then by independence and symmetry, according to Lemma 1.2.6 of 7 conditioning on (X1,.. x,) yields
n x
n Σ
2
2
x
X
X
(7)
As for the conditional expectation in
notice that by independence
E
rxx;
X1 = X1,
X, Xx
E
r;
(8)
According to Lemma 9 for un -ammss every Xiy..., Xn. E X,, where Un = Po (X),..,,,,
denotes the distribution of (X1.... Xn), we have
rix;
SC
X
(9)
where 2 ((()))
and is optimal. This means that for any constant C" such that
Vir
E
Σ
TiX
C
Σ
(10)
for all n E N and for each collection of vectors XI: X,, follows that C' 2 C.
From 8 and
we can infer that
E
X
Σ r
X
X
XI=XI
XI
X Xn SC.
X
i==l
Taking expectations in the above inequalities and yield that
E
Σ
x
C
X
(11)
To see optimality let the above statement hold for some constants C' in place of C. Then we choose X; x,r,, S i with arbitrary reals vectors XI....,XA follows that
E
Σ
rixi
C'
E
Σ
|
whence we can conclude from (10 that C'
2 C.
Thus we obtain that C' = C.
Notice that by Holder's inequality
1
< 2/2 1
I.
(12)
Plugging 12 into
we have
E
X
<C
2D 2/2-12111
X
where C= 23 2
is constant.
22

---

Next, we use the following form of Stirling's formula for the Gamma-functinn which follows
from (6.1.5). (6.1.15) and (6.1.38) [6] bound the constant C. For every 0, there exists
(())) E (0, 1/(2x)) such that
T(x)= 2 - "c((o))
Thus
r p+1
C = 27 2
g(p) 1/2 20p2)/2--0/2011
VT
with s(p) = (1+ p/2
e (x)-1112 where 0 < v(p) < <//(6(p + 1)). By Taylor's formula we have
that
log(1 + x
Σ
2
1 (-1)m-12"
Vx (-1,1), 1),
m
and that for every & No
2k++
(-1)"-122 S log(1 +
Σ
1
(-1)
xmh Vx 0.
m
Therefor obtain with 1: that
1
log sp) log(1 + p + up)
2 5
I
4p 6p2
6(p 1)
18p"
where the last equality follows from elementary calculus. Similarly,
log P
log(1 + p
1 v(p) 1
1
v(p) 2
1
4p
4p
Thus, we have
e P/22
p/2 p/2 <0 < T&p 2// 2/121
which implies that C is strictly smaller than /2e p/2 p12 for all p 2
Since C==
g(p) V2e 2/2 and g()) 2 e we can obtain that the relative error between C' and
V2e 222-2/2,p0 2/2 is equal to
1 15 4p
-1 1
4p 4
g(p)
using Mean Value Theorem. This implies that the corresponding relative errors between and V2e -P22 converge to zero as p tends to infinity.
The proof is complete.
Then we introduce the McDiarmid's inequality for vector-valued functions. We firstly consider real-valued functions, which follows from the standard tail-bount of McDiarmid's inequality and Proposition 2.5.2 49).
Lemma 10 (MeDiarnid's Inequality for real-valued functions). Let Zi...., Zn be indepen- dent random variables, and f 2h + R such that the following inequality holds for any Fiy Zi 1 Zet1.... Fn
sup [ ..... 21 24, 2111. 2n) f(2 ... 2i 2/1 2411 2n) $ B #
Then for any > 1 we have
[[ Zn) -Ef(Z,,,..... ...,, Zn)ll
22m,.
23

---

To derive the McDiarmid's 's inequality for vector valued functions, we need the expected distance between f( I. Zn.) and its expectation.
Lemma 11 38 Let Zi...., Zn be independent random variables, and f: - H. is a function into a Hilbert space H such that the following inequality holds for any 2, ................................ Zi-1 1 Zn
sup [f ..., 2;-1; 24, 2141s-.... 2n) f(21,- 21-1, 2/1 2+11. 2n) B s..4
Then have
E (Z..... 2x) - (2, Z S vnB.
Now, we can easily derive the p-norm McDiarmid's inequality for vector-valued functions which refines from [O] with better constants.
Lemma 12 (McDiarmid's inequality for vector- valuued functions). Let Zi...., Vn be independent random variables, and f: n" A H is function into Hilbert space H such that the following inequality holds for any 2,,..., 25-1, Zi+1, Zn
sup BAllf(2)..... 2,-1, 23, 2411. 2n) f(21...., 24..,,,,,,1,,,//.. 24 ................................ 2n)1 S 3, (13) 20,24
Then for any >> 1 we have
[|| - ..., 2n) S (V2p + 1)
Proof of Lemmal
12
Define real-valued function h 2 R
he =n)) = [ Rlf 71,
7n I|
We notice that this function satisfies the increment condition. For any i and 21, 21,.... 21-1, 2641,-.. 2ns
we have
sup MEE....., 24-1, Ri, 2.-1...., 2n) -(22,........ 2:-1, 2/, 24, 11.,,...,,, 2n)
sup || (B.f(21,..... 2n) Elf(Zi,,... Zn)]ll |Baf(s1, ......... 21 24, 2411...., - Z
S sup EA =
f(21...., 21 24 Zitl...... 2n S.3.
Therefore, we can apply Lemma 10 to the real- valued function and derive the following inequality
|| Z.) - Elh(Z Z.)Illp S v 2pn...
According to Lemma 11 we know the following inequality [[,(21,.... 2n)] S vnB. Combing the above two inequalities together and we can derive the following inequality
E Zn) Ef( ... Inll, | Zz, .., Zn.) ( Zi..... ... Zn)Il,, + [ Z1, ... Zn1
<(v2p 2p + 1n33.
The proof is complete.
Proof of Lemma For g(Z,...., 7n) and [n], we write I|Il|||),.? Without loss of generality, we suppose that 2 Otherwise, we can add extra functions equal to zero, increasing the number of therms by at most two times.
(I|] 7p) 2
Consider sequence of partitions Po...., Pa with Po {(i) i [n]], Pa with P., {[n]). and to get P, from Pi+1 we split each subset in P4t into two equal parts. We have
Po = ({1).... .... 12*1), Pi ({1,2). (3. .,.,,...,.
Pa = {(1....,2 1,2
24

---

We have [P:] = - and [P] = 2 for each P E Pt. For each i E [n]] and = O.....k, denote by (1( E Pi the only set from Pi that contains i. In particular, (i) = {i) and pk (i) - [m].
For each i [r|] and every / 0, ... k consider the random variables
g: g. (Z,, (p)) Elg, Z, (x)))
i.e. conditioned on and all the variables that are not in the same set as Zq in the partition Pt. In particular, g, = gi and y [ We can write a telescopic sum for each E [n].
k-1
g
Elg Z
g
g +1
Then, by the triangle inequality
Σ g:
E Eg
Z
Σ
(14)
To bound the first term, since
E g: Z,]
<
G. we check that the vector- valued function
f(Z,..... Zn) = >"= [Zg.
satisfics
13)
with 3 = 2G, and E[E[g [,]]] O, applying Lemma
12 with 8 = 2G, we have
Σ Elg 1=1
Z
+
(15)
P
Then we start to bound the second term of the right hand side of (14). Observe that
g: (Z,, (1)))))))))) E (Z, P1))))())) (()) Z, ((+))
where the expectation is taken with respect to the variables Zy.j E pl+ p'+) Changing any
Zj would change g! by 3. Therefore, we apply Lemma 12 with = g! where there are 2 random variables and obtain uniform bound
||||s: gi -Ill,, (Zi, ((n)))))))) S (v2p + 1) (v 2
vp 2 2,
Taking integration over (Z,, [1]] 1()). we have |||g: g. *
3 as well.
Next, we turn to the sum ExEp g: gi for any pl E Pt. Since g! g! 1+1 for E ps depends
only on Z; Zn pl, the terms are independent and zero mean conditioned on pnn Applying Lemma 8 we have for any 2 2,
Σ g! g!" 1+1 iEP
(Z)))rr) S
2 2
2'p
P
1
Σ
|1
g "II' (z))))
2
iEN!
Integrating with respect to |m] pt) and using ||||s
(+
I (v2p + 1) 2 we have
gi
2
Σ g! g! ++
< 2
2
x 2 2p + 1)V2'8
2
iEPe
(12
2 +
p
2p + 1)2/3.
e
Then using triangle inequality over all sets p E Pt. we have
Σ g :E|n]
g 1+1
Σ
Σ g! g
PlEP
iEP!
<2k-1 1 x 21+ (v²)
(D) ( 2p + 1)2'3
22 10 (v:) (v2p +
(12p+110 1)243.
25

---

Recall that 2 < n2 due to the possible extension of the sample. Then we have
2 #
(V²)
(v 2p 1)mB8 flog2 n]
We can plug the above bound together with
15 into 14 to derive the following inequality
Σ
g
22(V2p
1)VGG + 2 x
(v?))
2
(v 2p 1)n33 [ogg nl]
The proof is completed.
C.2 Proofs of Subsection 3.1
Proof of Theorem 7 Let S = fzi,..., 2n} be set of independent random variables each taking values in Z and S' fz'..... 2 be its independent copy. For any i E. [n], define s {2y,..., 1 2/2 1.......; ] be a dataset replacing the i-th sample in S with another i..dd sample
2/. Then we can firstly write the following decomposition
(VF(A())) -VVFs(((S)
Ez VS(A(S); 2) - Eeg (VS(A(SO)) ])]
Ez (S(AAS())))) |) (S(A(S()) =1]
E VF(A(S()) 21 - - v))
+
We denote that (S( = E
Ez Vf(A(S)) 2) Vf(A(SO)) =1)]. thus we have
EA [IIVF((A(S) (V
Σ Ez ([ E.: VS(A(S()) 2.2)]]
AA
Byy Ex VS(A(S ),2) - V)(A(S()) ),
(16)
VS(A(S()) ) x0)
Σ V)(A()), 2;)
+
< 2n + EA
Σ (S)
where the inequality holds from the definition of uniform stability in gradients. According to our assumptions, we get [lg. S 2M and
E,, [g:( = E,, Ez Vf(A(S()): ): 27] - VF(A(S()): 24) B2z Ex (/((A((()): 2))] - Ez, (VI(A()()); =0,
26

---

where this equality holds from the fact that 2, and Z follow from the same distribution. For any i E [n]. any j o and any 2/j. have
Ea
B
(21....: 2j-1; Fy. 2it1 ................................ .n)) ( 25-1; 25,t,,,, - ]11]]
SEA
Ex
Bz
Vf(A(S 2: VI(AAS 2n) -Bay [B (V((A(S)) 3; 3:2] - V((A(S))):
SEA
Ex
V V)(A(S))); )=]]]11
EA
Exg
Ez
VI(A(S()) 2)] v.(A(S))) xx)a [
$28,
where ( { (2...... 2/-1; 2/, 2++1 ....... 2n ). Since the noise introduced by the algorithm's 's inherent randomness A is typically assumed to be independent of the dataset S, we have verified that three conditions in Lemma are satisfied for g: (S)). We have the following result for any 2
(v²)
Σ (S)
S 4(v 2p 1) +8x2
2p 1)n3 llog2 n|
According to Lemma for any 5 E (0, 1), with probability at least - 8, we have
Σ (S)
<4VRM + 8 x 2 VenB [log, n log (e/6) + (4eV/mM + 8 x 2t Ven [logz I e/ō.
We can finally combine the above inequality and (16) to derive that, for forany d E (0, 1), with probability least 1 8, we have
EA [A (Fs(A(())
4M (1 (1+e log (e/0)
2 +
48x x 2 (V2+ 1)ve8 [log, n log (e/8).
Vn
The proof is completed.
Proof of Theorem
We can firstly write the following decomposition
-VF(A(S))- -
Ez VS(A(S); - E.g VI(A(S()), 20]]
Ez (T((ASS))))) 2) VS(A(S()), ), =+)
+
Eyy
VF(A(S(() ) 21) Σ Vf(A(S), 2:). "
+
Σ
E
We denote that h,( Ezg
Ez
VS(A(S()) 2)] (f(((S()) ), =)) have
"
n
- - Σ h.(S)
VS(A(S): 2) Egy V)(A(S()) ) ]
Ez
ES VF(A(S(O).)) 23) Σ ()(AS)),2)
+
27

---

which implies that
E
n (F(((()) - - Σ h;(
-AA
Bz
(F(A(S): - Ry VI(A(S()) -))
(17)
B VS(A(S()) ) VS(A(S), z:)
< 2m,3,
where the inequality holds from the definition uniform stability in gradients.
Then, for any = ..... we define (:(S) h.(S) (s ).4 h (S)]. is easy to verify that and Ez, [q:(() = Ez, [S]] - E., (s,)) [S)] = 0 0 = 0. Also, for
(=, [S)(
any E [r]] with j * and z E Z, we have the following inequality
AA (5) q:(21 ,. 21 2j+1: 22)
<EA (1,)(,)) (31,,...., 1 2/) 2j+11..., , 12
+ EA (hi - Es (21. Zj-1; 2/
zn ].]l2]]]
For the first term (; (2), 2j- 24 2j+1..... 2n) ll2]. it can be bounded by 2B accord- ing to the definition of uniform stability. Similar result holds for the second term Es( [S)] Es [2, 2 = 1 ...... ................................ Zn ]][p]] according to the uniform stability. By a combination
of the above analysis, we get E (S) - 2/-1,, zjj 25+1, 2x) - 43.
Thus, we have verified that three conditions Lemma are satisfied for (S). We have the following result for any p 2 2
(v
Σ (
22471
(v 2p 1)n,3 [log n
According to Lemma for any å (0, 1), with probability at least 8/3, have
Σ (S)
16 x 2eB [log2 n log (3e/8) + 16 2 Ves [log2 n Vlog 3e/8. (18)
Furthermore, we can derive that
n
RVF(A(S)) (VIS(A(S)) Σ (.) Σ (i())
=RVF(A(S)) -VPPs E Es (br(())
=RVF(A(S)) -VFF(A(S) nE
28

---

Due to the i.i.d. property between S and S'. we know that Es = Es|VF(A(S))) Thus, combined above equality. (17 and (88 we have
EA
[VF(A(()) (VFs(A(S)) n.S, VF(A(S))+ + (
mVF((((S) ~VFs(A(S)) Σ (.))
+
h:(5) nE ( N.E (fsss((S))) Σ
(19)
n1 nVF((A(S) -NFF)) Σ (S) 1 + EA
1
EAA
Σ q: (S)
<2n3 16 2 Ven loga ni log (3e/o) 16 x 2 Ven [log2 ni v log 3e/8
<16 x 2 Ven [loge n log (3e/8) + 32 [loge n Vlo3ee/.
This implies that for any 5 (0, 1), with probability least 1 5/3, we have
E |II - E A
(20)
16 x 2 VEB [log2 n1 log (3e/ö) + eBB flog2 n Vlg 3e/5.
Next, we need to bound the term |E VFs(((()))] Es, Es.n There holds that ||Es, A.s,ABss Es (A())(()))] we obtain the following inequality with probability at least 5/3,
Then, by the Bernstein inequality in Lemma 5
2E, I| (J((((');)))))) log (6/
M (6/5)
| [ES.. -Vx.((A(((S))) S
(21)
Then using Jensen's inequality, we have
E. E LA AAA.ESAAAVVVA VA(((S))) =+) < B. (AA((( =
(22)
Ez A (AA"") 2)11 B2Bs.AlIfAAES Z)13.
Combing 20
21
with
22
we finally obtain that with probability at least 1 - -25/3.
EA |1 (FF(A
2E VV (6/8)
M log(6/5)
(23)
16 x 2 VeB [log, n log (3e/0) + /2 [log, n / log 3e/5.
Next, since (2,.... 2,,, we define p p(21..... 2n) Ez,A ( and p:
Pa P1(21..... 2n) sup,, p( ..., 2n). So there holds p: p for any 1,...,7 and any
29

---

, E z". Also, there holds that
2nd
-p)²
sup Ez.A [V
EZ.A -
Ez,
sup 2
Rz,a
sup
- 2)1l2
sup [V(((S); 2)1la [VI(A(S): F.EZ
2)1la)
Ez,A
[V(((S)) 2)122
sup [V(((SS) 2.E2
2)[|>
Sn8² (2
([(((S);;
2)11 +
I8nB3p p 2n
(24)
where the first inequality follows from the Jensen's inequality. The second and third inequalities follow from definition of uniform stability gradients. The last inequality holds from that (a + b)2
< 2a + 212.
From 24 we know that p is (8n,52 2nB²) weakly self-bounded. Thus, by Lemma we obtain that with probability at least 8/3,
E S. 12
(B3EE2.,IIVV/(((3))))))11 12))
8 6") +
(IIB) 2)
log(3/6),
where the last inequality follows from that vab < a+è for all a, b > Thus, have
( 12 + } 3 + 16n 16 log(3/0). (25)
Ey 201
Substituting
25
into
23
we finally obtain that with probability at least 1 -
EΛ ((VF((((()) - VV(s((()))
(2 + 3,32 16n log(3/8) log(6/6) +
M log(6/5)
(26)
+ 16 2 Veßl [log, n log (3e/8) + 32 [lgg, nl / log 3e/5.
According inequality va+b = vā Vb for any a, b > O, with probability least 6, we have
EA [IIFF(()(S) (A()((l)
EE ((A(())) log (g///)))
(2 32 + 32m,3 log(3/0)) log(6/5) M log(6/8)
"
+ 16 x 2 VeB [log, ni log (3e/0) + 32.e8 [log, n Vlog 3e/ō.
The proof is complete.
30

---

Proof of Proposition 7
According to the proof in Theorem
2
we have the following inequality with
probability least 1
EA V
(EE2.AIIV
+ 12 16n,3 log(36)) log(6/6)
(27)
M (og(6/0)
+ 16 x 23 VeB [log n log (3e/o) + 32veB [log2 n log 3e/0.
X| F()) according inequalities Vab na+ 1,b Since SGC implies that Bz [IV/ 2)
and Va + S Va + vb for any b, O, we have the following inequality with probability at
least 1
EA (IVF(((())) (Fs(((
2 A2pBA [IFF(A())) + 1 + 16n,3² log(3/6)) (og(6/))
M log(6/8)
+ 16 x 2 VeB [oga n log (3e/8) + 32veB [log n Vog3ee/8
3e/8
gg + 32n log (3/)) (6g()/6)
1 1 4XM log(6/6) EA (AIIVF(A()))
SV
1+n
n
log(6608
16 x 2 VeB [log2 n log (3e/8) + 32veB [log2 n v Vlog 3e/8.
which implies that
+1 AM
E (I (I
log(6/8) Blog log (1/0)
"
The proof is complete.
Proof of Remark 4
According to the proof in Theorem
2
we have the following inequality that with
probability least
E [I - (FS(((
4E2.A V (f(A(S): (6/5)
(2 + 32n,3 log(3/6)) log(6/8)
M (og(6/8)
+ +16 2 VeB [log, n) log (3e/o) + 32ve8 Dogz n1 Vlog 3e/8.
(28)
Since f(w) is 7-smoohh, we have
Ez, 211
E2 Z) - Vf(w": Z) + [Vf(w": 2)
(29)
SA [[[(S)) -
-w w
+ Ez Vlw ;
31

---

Plugging 29 into 28
we have
EA IIV F( (A(S)) - VFs(A()))]la)
B [I A| w [ + Ez 2ol
(330 + 32n, log (3/6)) log(6/0)
M log(6/6)
+
+ 16
2
V Togg ni log (3e/6) 32
Moga n log 3e/8
n
E ||() w
log (6/8)
4E Vf(w"; 2) (og(6)))
.27
T
(2,02 + 32n log (3/)) (6/)
M log(6/5)
+
16 2 Veß Moga log (3e/6) + 32, [ogz n v log 3e/6,
(30)
where the second inequality holds because va + b S va + vb for any a, b > 0, which means that
(x())F((((S) (Fs(A()))
log(1/6) + 3 log(188) +
Ez VIIs(w ( log(1/0)
EA [[A(S))
w' log(1/8)
n
n
7
The proof is complete.
C.3 Proofs of Subsection 3.2
Lemma 13. Assume for any 2, f(,2) 2) is M M-Lipschitz. If A is 3-umiformly-stable in gradients, then for any 5 E (0, 1), the following inequality holds with probability least 5
EA VFs(A))))
4 VV(A(S); | log (6/5)
g + 32m,3 log(3/8) log (6/8)
n
n
Mlg((6/8)
16 2 VeB (n)) log (3e/0) + 32 [log((n)] Vlog (3e/0).
Proof of Lemma
13
According to proof of Theorem
similar to 19 we have the following
inequality.
E
| - (FF((A(S) )
<EEA
-V
h,)
+2
h:(S) nl (VF(A(S)) n.g. Fs (ASS))
=2E A nVF((A(S) - -VFS((((S) Σ (S)
2E
Σ q (S)
1=1
<8n 82 1024 2 2em 32 (nog, n1)² log? (3e/8) + 51m 8² ( (Nog, n n1) log (3e/8)
28n 2 + 2048 2048 Sen2 32 (fog, n1 n=) log" (3e/8),
where the second inequality follows from the definition of uniform stability in gradients and Cauchy- SanyakkosskySchhwar incquality.
32

---

This implies that for any ò E (0,1), with probability at least 1 - 6/3, we have
A [IVFF(A(S) - VFs(A I
LA -B.
832 2048V228 ([log, n1)² log (3e/0).
(31)
According to 21 22 and (25 using Cauchy-
Sataay-BBBnnnkkkkkkyettttrrrneee for any & E (0,1)
with probability at least 20/ we have
Es A (FF.A Es.A | (V(A(S))]
( 2 + 3 (og( log(6/)) 2M log(6/0)
n²
Combing above incquality with (1), with probability least 1 8, we have
AA [IIFF(((S) VFs((A())
8T SE ( [] _ + 64m,32 log(3/5)) log(6/8) 2M log(6/8)
n
n²
+ 883 + 2048 (flog2 log² (3c/5).
The proof is complete.
Proof of Theorem
Since f(w) is y-smooth, we have
B2 2)
< <B,,ll\V/(A(SS))
V/(w"; Z) + IV/(w"; [
(32)
s> EA [I|A(5) -000))ww1333 + E2 VV 2))
Combing above inequality with Lemma 13 with probability least 6, we have
EA [IVF((((S)
VFss(A())
R (1IA(S)
w*1 log(6/0)
8E VV[(": 1 log(6/8)
n2
n
+ 65,32 log(3/6) lo((/))) 2o
n + 8 + 2048 2e (Mog, n 2 (3e/8).
(33)
When F(w) satisfies the PL condition and w is the projection of A(S) onto the solution set arg new F(w), there holds the following error bound property (refer to Theorem 2 in [I9
|VF(((())) 2 AlIA(S) w w*ll2-
Thus, we have
EA [ILA(S) I < E [IAS)()
2EE [IIFF(A(S) (Fs(A(()) 3] A [IVFs(
EA [||A(S) - w | log(6/0)
16E₂ [[W :2)13 log(6/5)
2 (6/))
+ 130,32 (3/(3 (6/8)
16/3² + 40 (flogz n log (3e/o).
n²
When 2
32,² log (6/8) μ²
we have
16- log (6/8)
n² <
then we can derive that
E [[|A(S) 1
16Ez
V (w": Z)[ log(6/8)
22E (
+
EA [IA(S) w
2
n
4M² log(6/0)
+ 130,3 log(3/5) 1/g(
+ 16
+ 4096 (floge n1)² log" (3e/5).
n²
33

---

This implies that
BA(l)A(5) - - w'1
2 1
16E2 [IV/[w" 2)1 log(6/6)
22 (
4.2 log(
+ 130,3 (3/(3/6) 16/()/)) +
16,32 + 2096 (flogz n log" (3c/0)
n²
(34)
Then, substituting (34 into 333.
when n 2
32.² (0/8)
with probability at least 1 - 8
EA [IIFF(A(S)
(A(((
16Ez [V
2)1 log(6/6)
SEA [IVFs(A())
+ 130,3 log(3/8)log(((/)) (35)
1632 + 20.6 (flog2 n1)² log" (3e/o).
Since F satisfies the PL condition with μe, we have
EA
VF(A()))
Ex(F(A(S)) - F(w")
Vw W.
(36)
24
So to bound Ex[F(A(S)) F(w*), we need to bound the term EA |IF((A()) And there
holds
EA /FFAAS)) A [IFF(A(S) VFs(A(S))I + 2IE (Fs((
(37)
On the other hand, when / is nonegative and 7-smooth, from Lemma 4.1 of we have | |V/(("; = - 47f(w";;))
which implies that
Ez f
2) < 4,Ezf(ww (w": 2) 4yF(w").
(38)
Combing
35
36
37
and
38).
using
incquality, we can derive
that
E (F(AS)) F(w")
E [A())()
FF(w*) log(1/0)
M log (1/8) un?
+ 88 log n 11gg(1/1 (1/6)
The proof is complete.
D Proofs of ERM
Proof of Lemmal 7 Since Fs (w) = (s(W; + S(W, &Ejzi((, we have Fs(W)(((1)) Fs(WW(S))
f(w f(W"(5()) ); 2;) f(w (S):::)
(f -f12z)-[((--- ((W((())
f(w((s()) 23) ((WW((())))))))) [(W f(w" (S())
n
n
+ (FFit (w (S())) FwwssssWW0 (w*(S))
f(w ); f(w (S);
+ S(w (S):: - (s
2M
(W((()) (S)
34

---

where the first inequality follows from the fact that w (S is the ERM of F Fsc and the second inequality follows from the Lipschitz property. Furthermore. for w" (S()), 1 the PL condition and smoothness property of F's imply that its closest optima point of Fs w (S) (the global minimizer of Fs is unique (50). Then, Fs satisfies the quadratic growth property [99. which means that
Fs(w )S Fs(w" (S)) 2 ~"
w (S)1
2
Then we get
2M W - S Fs(w' (S()))((()))) (ws - " S/ (S())
|| (S(i)) w (8)
n
which implies that (S(00 w'(S)l22 S obtain that for any 500 and
1M
Combined with the smoothness property of f we np
2 S n²u²
16M2
V Z,
The proof is complete.
Proof of Theorem 4 From Lemma we have (ss""") = O, we have |/ Fs(( w ] O. According to Theorem 3 since ERM is a deterministic algorithm, we can derive that
- Vf(WW(("): - < 1Mg Since
up
?F(w") log (1/0)
M2 log" n log log"(110)))
((W*(S) - F(w") = B[F(( - F(w*)= S
+
pn
E
Proofs of PGD
Proof of Theorem
According smoothness assumption and 17 1/7, we derive that
Fs(W (s(w::)
S( Wt, FFs(w:)) + |We+1 - wwel2
2
=-m - (w,,, 11 + 7 V
2
(2 mz) [Fs(w))l
2 FFs
According to above inequality and the assumptions that Fs satisfies the PL. condition with parameter 14, we can prove that
Fs(We+1)- - Fs(..) < 1 IVP - - Fs(w"))
which implies that
Fs(We+1) - Fs(W") S (Fs(())) Fs(w")).
According to the property for y-smooth for Fs and the PL condition property with parameter y for Fs, we have
1
1 [VFs(w)]l
|VFs(w))B Fs(w) Fs(W') -
2
2p
which means that $ < 1.
35

---

Then If = 1/y, S 1- - pm < 1, taking over T iterations, we get
Fs(We+1) - Fs( (w" - (1 - (Fs(w)) - Fs(ww)).
(39)
Combined (3 the smoothness of Fs and the nonnegative property of it can be derive that (VFs(wT+))IE) O ( (1-
On the other hand, from Lemma we have [V/(wr++ (S); - V/(wT=1(S";==)1 4M
n²y²"
FVVs(WT+))l 1212 = = ( ))²) and PGD is a deterministic algorithm, according to Theo-
Since
rem 3
we can derive that
F(wr+1)
F(w") F[ ([((T+++)) F(w")
27
F log (1/6)
M2y² log" n nlog" (1/5)
x (1-
+
pn
n&n2
Let T x llogn, n, have
((WT+))-FT F(w") x 7f((') log (1/0)
M2 log n log (1/0)
+
un
nzn
The proof is complete.
F Proofs of SGD
We first introduce the necessary lemma for the optimization error bound.
Lemma 14 (199). ). Let {we]: be the sequence produced by SGD with t
Suppose 2u(1+177
20+11
Assumption 7 hold. Assume for all 2, the function w ++ f(w; 2) M M-Lipschitz and smsoohh and assume Fs satisfies PL condition with parameter μ. There holds that
M2
EA (Fs - -Fs("") - 2T
Proof of Lemma We have known that Fsco (w) = 1/ (s(w; 2/) Ejes (wW; We denote
w" (S()) be the ERM of Fst)(w) and w be the ERM of Fs(w). From Lemma we know that (5()); Vf( (S)="(S);))
16M2₂2
V2 E 2,
n²2²²
Also, for W., the PL condition property of Fg implies that its closest optima point of Fs is (S) (the global minimizer of Fs is unique (50). Then, there holds that
" EA [|[w, (S) < EA EAI [Fs(w:)] Fs(w (S)) S 21
M2
Thus we have EAll|w; w (S) < Combined with the Lipschitz property of f obtain that for Vz Z, there holds that
M²2 A similar relation holds between (S(+)) and w/.
f(wa=)) - vs(w =) 1][]]
E
< 3E
[Vf(we))
Vf( (S): +3 (f(W((S):2) vf(w (S()))))):
|| ((S()))
Vf(w": 2) 1
+ 3EA
48
< ST [l|w, w (8)
n²n² + BR ||(*(((0)) will3
6M223
48M222
tu
n²n²
The proof is complete.
36

---

Proof of Theorem 6 From Lemma
3 we have
6M2y3
4
EA Vf Vf(w) 2) [ -
+
(40)
Tμ²
n²p²
On the other hand, according to the smoothness property of Fs and Lemma we have
M²
EA [IFFs(WT+)))) - Tp²
(41)
Using Theorem 3 with probability at least 1 8, we have
EA [WT+)] - F(w")
2² log(1/8)
M log (1/8)
2 1
2 log lllgggg////)) (1/6)
Tp3
um
un?
Tp
n2
P(w)) log(1/0)
( TH
2 2 log 2 log (1/8)
+
+
pm
n²
Furthermore, choosing x n², we finally obtain that when n least 1 -
32-² log (6/6) μ
with probability at
yF(w*) log(1/8)
2 log² n nlo 2 (1/8)
F(WI+1) F(w")= 2
un
4 n
37


Reviews:
[{"review_id": "liOvDJshRj", "reviewer": "Reviewer_t9CR", "summary": "This paper presents high-probability excess risk bounds for empirical risk minimization (ERM) problems and projected gradient descent (PGD)/ stochastic gradient descent (SGD) algorithms. The authors achieve dimension-free, O(1/n) generalization bounds by generalizing the standard\nconcept of algorithmic stability of loss function to its gradient. This approach allows for sharper generalization bound. \n\nThis work also combines the derived generalization bound on gradient and analysis on optimization error for strongly convexity or Polyak-Lojasiewicz (PL) condition and implies a sharp bound on the excess risk.", "questions": "Comment: The authors should specify what you mean by PGD. I thought it was GD but I have to find the original reference to know it was projected GD.", "limitations": "NA", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths \n- The generation bounds were developed before, but the one in this paper is dimension free. \n- The results are well-presented. \n\nWeaknesses\n- The technical novelty is somewhat limited, with proofs heavily relying on appropriate combinations or refinements of existing techniques (e.g., Zhang & Zhou 2019, Klochkov & Zhivotovskiy 2021, Fan & Lei 2024).\n- In the strongly convex/ PL setting, if $\\mu$ is small, the bound is not good as it has $1/\\mu^3$ \n- The assumption $n \\geq \\frac{16\\gamma^2 \\log(6/\\delta)}{\\mu^2}$ and $F(w*) < O (1/n)$ might not be practical in the strongly convex applications.", "was_revised": true, "final_justification": "Thanks for the author rebuttal.\n\nI updated my review.", "rebuttal": "Thanks for your review. Here are the replies.\n\n> Strength 1: The generation bounds were developed before, but the one in this paper is dimension free.\n\n\nAnswer: We disagree with your claim presented in this paper that \"generalization bounds were developed before\". High-probability stability-based excess risk upper bounds achieving $O(1/n^2)$ have never been presented before; the best existing result only achieves $O(1/n)$.\n\nFurthermore, the stability-based generalization error bound for the gradients we derived is also tightest known. By utilizing the vector Bernstein inequality, the constant coefficient preceding the $\\sqrt{1/n}$ term now depends not on the maximum gradient norm $M$, but on a coefficient related to the variance. Critically, this conclusion also holds (is applicable) in non-convex settings.\n\n\n\n\n\n> Weakness 1: The technical novelty is somewhat limited, with proofs heavily relying on appropriate combinations or refinements of existing techniques (e.g., Zhang \\& Zhou 2019, Klochkov \\& Zhivotovskiy 2021, Fan \\& Lei 2024).\n\nAnswer: We respectfully disagree with the assessment of limited novelty.  We summarize the difference with the mentioned literature.\n\n1. **(Zhang \\& Zhou, 2019) studied optimization problems, whereas we study generalization problems.** I guess you intended to cite the paper (Zhang et al., 2017) here.\n\n\n2. **Totally different techniques to (Zhang et al. 2017)**: They use the uniform convergence techniques to get generalization bounds which dependent on dimension $d$. As the uniform convergence method inevitably introduce a dimension-dependent bound, we **improve this** with a **totally different** techniques, **the gradient stability**, and get our dimension-free $O(1 / n^{2})$ bound.\n\n3. **From function stability to gradient stability**. Compared to (Klochkov \\& Zhivotovskiy 2021), they prove their high probability generalization bound via function stability (Definition 6 in (Bousquet and Elisseeff, 2002)), which typically implies only a $O(1/n)$ bound. We improve this by introducing gradient stability (Definition 2 in this paper), which leads to the $O(1/n^2)$ generalization bound demonstrated in this paper.\n\n\n4. We sharpen the fundamental gradient stability bound via a **novel Bernstein's inequality** (Theorem 2): In (Fan \\& Lei 2024), they built the gradient stability (we show this in this paper in Theorem 1), similar to our Theorem 2. But the critical difference is that constants in $1/\\sqrt{n}$ is improved from $O\\left(M \\sqrt{\\log{(e/\\delta)}} \\right)$ to $ O \\left( \\sqrt{\\mathbb{E}\\_{Z} \\left[ || \\nabla f(A(S);Z) ||^2 \\right] \\log{(1/\\delta)}} \\right)$, since $M$ is the maximal gradient norm. Notably, the proved dependence $\\mathbb{E}_{Z} \\left[||\\nabla f(A(S); Z) ||_2^{2} \\right]$ via novel Bernstein's inequality is interpreted as the squared gradient norm of the loss functions on test data, under the optimized model parameters $A(S)$. Thus, it is supposed to be small when the algorithm is good, compared with constant $M$.\n\n\n\n\n\n> Weakness 2: In the strongly convex/ PL setting, if $\\mu$ is small, the bound is not good as it has $1/\\mu^3$.\n\nAnswer: \n1. The $\\mu$ is not necessary to be small: We only require the population risk $F$ to satisfies PL condition (weaker than the PL condition for empirical risk $F_S$) in Theorem 3, and we verify it is $2$ under a linear regression example in Remark 5.\n\n2. **The dependence on $\\mu$ is standard**: Existing works have also dependence on $\\mu$ as presented in the following table.\n\n\n|Reference | Algorithm | Method | Assumptions | Iterations  | Sample Size | Bounds  |\n|:---:|:---:|:---:|:---:|:---:| :---:|:---:|\n| (Zhang et al., 2017) | ERM | UC |  Smooth, SC, LN | - | $ \\Omega \\left( \\frac{\\gamma^2 d}{\\mu^2} \\right) $ |  $ \\tilde{O}\\left(\\frac{M^2}{\\mu n^2}\\right) $  |\n| (Xu and Zeevi, 2024) | ERM | UC  | Smooth, PL, LN | - |  $ \\Omega \\left( \\frac{\\gamma^2 d}{\\mu^2} \\right) $ |  $ \\tilde{O} \\left( \\frac{M^2 + \\mu^2}{\\mu n^2} \\right) $  |\n| (Xu and Zeevi, 2024) | PGD | UC  | Smooth, PL, LN | $T \\asymp \\log(n)$  |  $ \\Omega \\left( \\frac{\\gamma^2 d}{\\mu^2} \\right) $  |  $\\tilde{O} \\left( \\frac{M^2 + \\mu^2}{n^2} \\right)$  |\n|(Li et al., 2021)| SGD  | UC  | Smooth, PL, LN | $T \\asymp n^2$  |  $ \\Omega \\left( \\frac{\\gamma^2 d}{\\mu^2} \\right) $  |  $\\tilde{O} \\left( \\frac{M^2 + \\mu^2}{n^2} \\right)$  |\n| (Li and Liu, 2021)  | SGD | AS  | Smooth, SC | $T \\asymp n^2$  | -  |  $\\tilde{O} \\left( \\frac{\\gamma^2 M^2 }{\\mu n} \\right)$  |\n|(klochkov and Zhivotovskiy, 2021)| ERM | AS  | SC | -  |  -  |  $ \\tilde{O} \\left( \\frac{M^2}{\\mu n} \\right) $  |\n|(klochkov and Zhivotovskiy, 2021)| PGD | AS  | Smooth,  SC | $T \\asymp \\log(n)$  |  -  |  $\\tilde{O} \\left( \\frac{\\gamma M^2}{\\mu^2 n} \\right)$  |\n|This work| ERM | AS  | Smooth, SC, LN | -  | $\\Omega \\left( \\frac{\\gamma^2}{\\mu^2} \\right) $ |  $\\tilde{O} \\left( \\frac{M^2 \\gamma^2}{\\mu^3 n^2} \\right)$   |\n|This work | PGD | AS  | Smooth, SC, LN | $T \\asymp \\log(n)$  |  $\\Omega \\left( \\frac{\\gamma^2}{\\mu^2} \\right) $  |   $\\tilde{O} \\left( \\frac{M^2 \\gamma^2}{\\mu^3 n^2} \\right)$ |\n|This work| SGD | AS  | Smooth, SC, LN | $T \\asymp n^2$ |  $\\Omega \\left( \\frac{\\gamma^2}{\\mu^2} \\right) $  |  $\\tilde{O} \\left( \\frac{M^2 \\gamma^2}{\\mu^3 n^2} \\right)$ |\n|This work | SGD | AS  | Smooth, SC | $T \\asymp n$ |  $\\Omega \\left( \\frac{\\gamma^2}{\\mu^2} \\right) $  |  $\\tilde{O} \\left( \\frac{\\gamma^2}{\\mu n} + \\frac{M^2 \\gamma^2}{\\mu^3 n^2} \\right)$ |\n\n\n\n\n> Weakness 3: The assumption $n\\geq\\frac{16\\gamma^2\\log(6/\\delta)}{\\mu^2}$  and $F(w^*)<O(1/n)$ might not be practical in the strongly convex applications.\n\nAnswer: \n\n1. For the condition on $n$, this is a standard condition to expect the machine learning model **can generalize**: In general, when consider generalization bound, the sample size is expected goes to infinity. Our assumption only requires the sample size is larger than a constant size, if the condition is not satisfied, none of existing literature obtain a small generalization bound.\n\n\n2. In many cases, the optimal population risk $F(w^{\\ast})$ can be extremely small, and it is a standard assumption in related works to reach $O(1/n^2)$ bounds, e.g., Remark 2 in (Zhang et al. 2017), Theorem 3 in (Xu and Zeevi, 2024), Corollary 5 in (Lei and Ying, 2020) and Theorem 22 in (Li and Liu, 2021) and so on. To see this more clear, we check the following mean estimation example.\n\nIf we denote the observed data as $X_1, X_2, \\ldots, X_n$ drawn from an unknown distribution, we assume that this distribution is bounded (for example, any random variable $X$ that follows this distribution satisfies $a \\leq X \\leq b$). \n\nTo estimate the mean of the random variable, our objective function is defined as $f(m; X) = (X - m)^2$, which yields the usual least squares estimator. Using the definition of M-estimators, our goal becomes: \n\n$$\n\\hat{m} = \\arg\\min_m \\frac{1}{n} \\sum_{i=1}^{n} (X_i - m)^2.\n$$\n\nWe can easily verify that $f(m; X)$ satisfies the following properties: it is $4(b-a)$-Lipschitz, $2$-strongly convex, and $2$-smooth with respect to $m$. According to Theorem 4, we know that the mean estimated by this method, which minimizes the least squares loss (or the second central moment), will converge to \n\n$$\n\\frac{\\mathbb{V}[X] \\log{(1/\\delta)}}{n} + \\frac{\\log^2 n \\log^2(1/\\delta)}{n^2}\n$$\n\nas the sample size $n$ increases, where $\\mathbb{V}[X]$ is the variance of the distribution. It’s worth noting that since this example pertains specifically to estimating the mean of a random variable, we have no additional parameters involved. Therefore, in this case, $F(w^{\\ast}\n)$ in Theorem 5, which represents the variance of the distribution, can be very small if $\\mathbb{V}[X]$ is small. \n\n\n\n> Question: Comment: The authors should specify what you mean by PGD. I thought it was GD but I have to find the original reference to know it was projected GD.\n\nAnswer: At line 31, we explained that PGD stands for Projected Gradient Descent upon its first appearance. At the beginning of Section 4.2, we also provided a detailed description of the Projected Gradient Descent iterative algorithm. We appreciate your feedback and will optimize this in the final version to enhance the paper's readability.\n\n\n\n\n## We’re happy to address any further questions you may have.\n\nReference\n\nL. Zhang and Z.-H. Zhou. Stochastic approximation of smooth and strongly convex functions: Beyond the $O(1/t)$ convergence rate. COLT 2019.\n\nL. Zhang, T. Yang, and R. Jin. Empirical risk minimization for stochastic convex optimization: $O(1/n)$-and $O(1/n^2)$-type of risk bounds. COLT 2017.\n\nO. Bousquet and A. Elisseeff. Stability and generalization. JMLR 2002.\n\nY. Xu and A. Zeevi. Towards optimal problem dependent generalization error bounds in statistical learning theory. Mathematics of Operations Research 2024.\n\nS. Li and Y. Liu. Improved learning rates for stochastic optimization: Two theoretical viewpoints. 2021\n\nY. Klochkov, and N. Zhivotovskiy. Stability and deviation optimal risk bounds with convergence rate $O(1/n)$. NeurIPS 2021.\n\n\nY. Lei and Y. Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. ICML 2020."}, {"review_id": "46fX1Pw10O", "reviewer": "Reviewer_D3wC", "summary": "This paper focuses on the question whether tighter high-probability excess risk bound tighter than $O(1/n)$ can be obtained using algorithmic stability-based methods and under common assumptions (e.g., strong convexity, smoothness, Lipschitz, PL ...).\nTo answer this question, an dimension-free $\\tilde{O}(1/n^2)$ bounds are derived under Lipschitzness, smoothness and PL condition. \nA dimension-free improved gradient generalization is first proved to potentially allow $O(1/n)$ rates under suitable stability and regularity. Then combined with PL condition, the generalization of gradient is translated into the generalization of model weight, where the square in the PL condition promotes the rate to potentially $O(1/n^2)$ under suitable stability. Finally, the stability bounds are applied to ERM, PGD and SGD by proving plugging-in their stability.", "questions": "1. Is it possible to decrease the order of $\\log \\frac{1}{\\delta}$ terms in Theorems 6 and 7?\n2. The following questions may be not necessary. It would be greatly appreciated if the authors could satisfy our curiosity. In [19], an $\\tilde{O}(1/n)$ bound is established under strong convexity and Lipschitzness, and in this paper an $\\tilde{O}(1/n^2)$ bound is established under strong convexity, Lipschitzness and Smoothness, which can be seen as the Lipschitzness of gradients or \"first-order Lipschitzness\". Therefore, is it possible that given strong convexity and $0-, 1-, \\dots p-$th order Lipschitzness (perhaps with more minor assumptions), an $\\tilde{O}(1/n^{p+1})$ convergence can be established. It is particularly interesting after realizing that given high-order Lipschitzness (e.g., 2-order Lipschitzness on Hessian) and extra assumptions of boundedness of hypothesis space, one can prove lower-order Lipschitzness by integral and obtain lower-order (at least 2-order) convergence. Then the only remained question is whether the high-order Lipschitzness can be \"fully\" exploited to achieve $(p+1)$-order convergence.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n1. This paper derives the first dimension-free $\\tilde{O}(1/n^2)$ bound on excess risk under commonly assumed strong convexity/PL, smoothness, Lipschitzness. The results are carefully compared (e.g., Table 1 and the remarks after each Theorems) and are optimal under some conditions, demonstrating the superiority in convergence rate or dimension dependence. \n2. The idea of using PL condition to bring a square in stability bounds and accelerate its rate is quite novel.\n3. The contribution is not limited to generalization of risks, but also the generalization w.r.t. gradients. The new generalization bound w.r.t. gradient has the same convergence rage but has dimension-free requirements on $n$ and also applies to non-convex and non-smooth cases under Lipschitzness and SGC.\n4. The paper is clearly structured and well written.\n\n## Weaknesses\n\n\n1. For SGD results to have $O(1/n^2)$ rate, the step number has to be $T = n^2$. Moreover, Theorems 6 and 7 have $\\log^{\\{3, 5\\}} \\frac{1}{\\delta}$ terms of very high order.\n2. Aside from the use of PL condition and the consequential order improvement in convergence rate, the technique to achieve them is based on Klochkov and 147 Zhivotovskiy [19]. Nevertheless, I believe this is minor compared to the $\\tilde{O}(1/n^2)$ rate.\n3. Minor/Typos: \n   1. The sentence in L267-L269 is quite confusing: \"However, the generalization analysis method proposed by Klochkov and Zhivotovskiy [19] does not use smoothness assumption, which only derive ... under strongly convex and smooth assumptions.\"", "was_revised": true, "final_justification": "The authors have addressed all my concerns, and I keep my rating.", "rebuttal": "Thank you for your thorough review. Here are the replies.\n\n> Weakness 1 \\& Question 1: Is it possible to decrease the order of $\\log\\frac{1}{\\delta}$ terms in Theorems 6 and 7?\n\n\nAnswer: After careful consideration, we acknowledge that the current analysis does not readily support a further reduction in the logarithmic order of these terms. While we recognize the theoretical importance of optimizing such bounds, our present framework relies on concentration inequalities and union-bound arguments that inherently introduce this logarithmic dependency. We agree that this is an important direction for future work, and we are actively exploring alternative techniques that might mitigate these terms.\n\n\n> Weakness 2: Aside from the use of PL condition and the consequential order improvement in convergence rate, the technique to achieve them is based on Klochkov and 147 Zhivotovskiy [19]. Nevertheless, I believe this is minor compared to the $\\tilde{O}(1/n^2)$ rate.\n\nAnswer: Thank you for acknowledging our work. Although our proof approach was inspired by theirs, we encountered significant challenges. The existing method is fundamentally built upon a one-dimensional framework, while ours operates in a high-dimensional regime. Their technique cannot be generalized to our case.\n\n\n> Weakness 3: Minor/Typos.\n\nAnswer: Thanks for noting these typos. We'll fix all minor errors in the final version to the best of our ability.\n\n> Weakness 4: The sentence in L267-L269 is quite confusing: \"However, the generalization analysis method proposed by Klochkov and Zhivotovskiy [19] does not use smoothness assumption, which only derive ... under strongly convex and smooth assumptions.\"\n\nAnswer: This statement suggests that Klochkov and Zhivotovskiy [19] did not employ the smoothness assumption. Instead, under the same number of iterations, their use of the PGD algorithm can only achieve $O(1/n)$ rates. Thanks for your advice. We will thoroughly polish the paper in the final version.\n\n\n\n> Question 2: The following questions may be not necessary. It would be greatly appreciated if the authors could satisfy our curiosity...\n\nAnswer: The core idea of our approach rests on performing an expansion at  first-order stationary point where the gradient vanishes. The point where we perform this expansion is itself sufficiently small, enabling higher-order generalization. However, if we attempt an analogous expansion involving higher-order terms like the Hessian, the Hessian at that point is not guaranteed to be sufficiently small, preventing us from achieving tighter generalization bounds.\n\n\n**We’re happy to address any further questions you may have.**\n\nReference\n\nYegor Klochkov, and Nikita Zhivotovskiy. Stability and deviation optimal risk bounds with convergence rate $O(1/n)$. NeurIPS 2021."}, {"review_id": "nyXiKS9a14", "reviewer": "Reviewer_EPgb", "summary": "In this paper, the authors introduce new high-probability excess risk upper bounds based on uniform stability in gradients. They first develop a general theoretical framework for deriving such bounds, under the assumptions of a Polyak–Łojasiewicz (PL) condition, smoothness, and Lipschitz continuity of the loss function. They then apply this framework to several learning algorithms, including Empirical Risk Minimization (ERM), Projected Gradient Descent (PGD), and Stochastic Gradient Descent (SGD). In particular, they show that in low-noise regimes, the excess risk bounds can achieve the fast rate of $\\tilde{O}(1/n^2)$, notably without any dependence on the dimension $d$.", "questions": "1) Could you confirm that the upper bound in Definition 2 holds almost surely with respect to the randomness of the algorithm $A$? If so, this is not standard and actually corresponds to a stronger notion of stability than what is typically considered in the literature, where an expectation is usually taken with respect to the randomness of $A$ (see, e.g., [23]). I would appreciate it if the authors could clarify this point and clearly discuss this aspect in the main text.\n\n2) The results in Section 3 are derived under the Polyak–Łojasiewicz (PL) condition, while in the applications, the objectives considered are strongly convex. Could the application part be extended to handle objectives that satisfy only the PL condition, without requiring strong convexity? Some discussion on this point would help clarify the generality of the framework.\n\n3) I believe there may be a missing $M^2$ factor in the third term of the upper bound in Theorem 3. While $M^2$ can be regarded as a constant, it is not purely numerical and should likely appear explicitly in the bound. Could the authors clarify this point? Also, is it possible that the dimension $d$ is implicitly hidden in $M$? An explicit statement on this would be useful.\n\n4) In Definition 3, is $\\rho$ meant to be a constant? If so, I suggest using a different notation, as $\\rho$ is already used to denote the distribution of $z$. Additionally, did you absorb the dependence on $\\rho$ into $C$ in the proof of Proposition 1? As above, it would be clearer if these constants appeared explicitly in the final bounds.", "limitations": "### Limitations \n\n- Please see my earlier comment regarding the specific notion of stability in gradients adopted in this paper. I am concerned that this almost-sure notion of stability might be more restrictive to establish for randomized optimization algorithms (beyond SGD), and could potentially lead to suboptimal bounds, especially in terms of the number of iterations $T$ required to achieve the stated rates. I would strongly encourage the authors to discuss this limitation explicitly. I am open to raising my overall score if this point is properly addressed.\n\n- I believe Theorem 1 and Remark 2 could be moved to the appendix. This would free up space in the main text and allow the authors to expand on the proof sketch or main ideas behind Theorem 2, which currently deserve more emphasis.\n\n- I recommend that the authors include precise cross-references to the proofs provided in the appendix. At present, the appendix sections are not explicitly cited in the main text, which makes it harder for readers to follow the technical arguments.\n\n- It should be clearly stated in the notation section that the symbol $\\lesssim$ is used to hide (numerical?) constant factors in the upper bounds, while $\\mathcal{O}$ and $\\tilde{\\mathcal{O}}$ follow the Landau notation conventions for asymptotic comparisons (the latter hiding polylogarithmic factors). In machine learning papers, $\\lesssim$ and $\\mathcal{O}$ are sometimes used interchangeably, but here they have distinct meanings. Clarifying this would avoid confusion.\n\n### Typos\n\n- l.12 \"algorithmic\" $\\rightarrow$ \"algorithmic stability\"?\n- l.50 \"and $\\mathcal{O}(1/n)$\"$\\rightarrow$ \"and terms in $\\mathcal{O}(1/n)$\"?\n- l.120 \"under\" $\\rightarrow$ \", the\"\n- l.164 \"stable\" $\\rightarrow$ \"stability\"\n- l.171 \"$\\gamma$-smoothness\" $\\rightarrow$ \"$\\gamma$-smooth\"\n- l.198  \"even IF the algorithm\"\n- l.235-236 \"can BE up to\"? \n- l.254 \"analysis\" $\\rightarrow$ \"analyze\"\n- Proof of Theorem 2 (l.630), first equality: there is an extra bracket \"]\". This is repeated several times in the proof.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\nOverall, the paper presents a very interesting, original, and tighter approach to deriving high-probability upper bounds on the excess risk of learning and optimization algorithms. I particularly appreciate that the authors focus on high-probability bounds, in contrast to the vast majority of stability-based generalization results that primarily address the expected excess risk. Moreover, the theoretical results are thoroughly analyzed, the optimality of the bounds is discussed, and the comparisons to related literature are well-executed and informative.\n\n### Weaknesses\n\nOne weakness I see concerns the notion of stability in gradients that the authors adopt. From my understanding, the stability upper bound holds almost surely with respect to the randomness of the algorithm $A$, which is not standard and appears to be a significant limitation that deserves further discussion. Besides that, the paper is relatively dense, and the writing could be improved in places to enhance clarity and accessibility. For example, it is not entirely clear whether all results need to be stated in the main text (e.g., Theorem 1 does not seem essential and could be moved to the appendix). On the other hand, some of this saved space could be better used to provide more intuition or discussion about the proof techniques behind Theorems 2 and 3, which are the core contributions of the paper. Beyond these points, please see my detailed suggestions and questions below.", "was_revised": true, "final_justification": "The authors have addressed most of my concerns. I recommend acceptance, provided the promised revisions are made and the paper is carefully proofread to catch any remaining typos I may have missed.", "rebuttal": "Thank you for your thorough review. Here are the replies.\n\n> Weakness 1 \\& Question 1 \\& Limitation 1: Expectation is usually taken with respect to the randomness of $A$.\n\nAnswer: This is a typo. Our Definition 2, consistent with the definition of uniformly-stable in gradients in (Lei. 2023), also needs to take expectation over the randomness of the algorithm $A$. For the ERM and PGD algorithms, since they are deterministic, this does not affect our results. For the proof regarding SGD, we need to add an expectation with respect to the randomness of the algorithm (since the noise introduced by the algorithm's inherent randomness is typically assumed to be independent of the dataset $S$). Our conclusion remains unchanged, meaning for Theorem 3, for any $\\delta \\in (0,1)$, when $n \\geq \\frac{16\\gamma^2 \\log\\frac{6}{\\delta}}{\\mu^2}$, with probability at least $1-\\delta$, we have:  \n$$\\mathbb{E}_A [F(A(S))] - F(w^{\\ast}) \\lesssim \\frac{|| \\mathbb{E}_A [\\nabla F_S(A(S))]||\n_2^2}{\\mu} + \\frac{\\gamma F(w^{\\ast}) \\log(1/\\delta)}{\\mu n} + \\frac{M^2\\log^2(1/\\delta)}{\\mu n^2} + \\frac{\\beta^2 \\log^2 n \\log^2(1/\\delta)}{\\mu}$$.\n\nFor Theorem 7, for any $\\delta \\in (0,1)$, when $n \\geq \\frac{16\\gamma^2 \\log\\frac{6}{\\delta}}{\\mu^2}$, with probability at least $1-\\delta$, we have \n$$\n\\mathbb{E}\\_A [F(w\\_{T+1})] -F(w^*) =  O \\left(\\frac{ \\left\\lceil \\log\\_2 (n) \\right\\rceil^2 \\log(T) \\log^5(1/\\delta)}{T}\\right)  + O \\left(\\frac{ \\left\\lceil \\log\\_2 (n) \\right\\rceil^2 \\log^2(1/\\delta)}{n^2}  +  \\frac{ F ( w^{\\ast} ) \\log (1 / \\delta ) }{n}  \\right).\n$$\n\nFor the training set $S$, we still only need to sample once, but we need to train multiple times through optimization algorithms to address algorithmic randomness.\n\n> Question 2: The results in Section 3 are derived under the Polyak–Łojasiewicz (PL) condition, while in the applications, the objectives considered are strongly convex. Could the application part be extended to handle objectives that satisfy only the PL condition, without requiring strong convexity? Some discussion on this point would help clarify the generality of the framework.\n\nAnswer: The derivation of Theorem 3 requires the PL condition. Observing Theorem 3, we see that to achieve rates of $O(1/n^2)$, the algorithm's stability needs to reach $O(1/n)$. Based on (Hardt et al. 2016)'s derivation, achieving stability at this level requires the loss function to satisfy the Quadratic Growth condition, i.e., $\\mu ||x - x^{\\ast}||^2 \\leq f(x) - f(x^*)$.\n\nIn fact, if the function is weakly-convex (A function f : $\\mathbb{R}^n \\to \\mathbb{R}$ is called $\\lambda$-weakly convex if the function $f (x) + \\frac{\\lambda}{2}||x||^2$ is convex.), then the PL condition can lead to the Quadratic Growth condition (Liao et al. 2024).\n\nIn this paper, we felt that introducing too many new assumptions might confuse readers. Considering that achieving rates of $O(1/n^2)$ is challenging, and the strongly convex assumption is also a common assumption in research on fast rates. Therefore, we did not elaborate in detail on this aspect. Thank you for your suggestion; we will include this discussion in the final version.\n\n\n> Question 3: I believe there may be a missing $M^2$ factor in the third term of the upper bound in Theorem 3. While $M^2$ can be regarded as a constant, it is not purely numerical and should likely appear explicitly in the bound. Could the authors clarify this point? Also, is it possible that the dimension $d$ is implicitly hidden in $M$? An explicit statement on this would be useful.\n\nAnswer: Yes, the parameter $M$ will be explicitly displayed in the final version of the theoretical bound. The norm of the gradients may indeed have a potential relationship with the dimension d. However, on the one hand, practical optimization algorithms commonly employ gradient clipping to prevent gradient explosion; on the other hand, existing works also include an $M$ of comparable magnitude in their bounds. We have updated the table to include Lipschitzness $M$, smoothness $\\gamma$, and strong convexity parameters/PL condition $\\mu$ and compared with existing works. Thus, we did not incorporate the dimension $d$ into $M$ implicitly as a means to achieve theoretical improvements.\n\n\n\n\n|Reference | Algorithm | Method | Assumptions | Iterations  | Sample Size | Bounds  |\n|:---:|:---:|:---:|:---:|:---:| :---:|:---:|\n| (Zhang et al., 2017) | ERM | UC |  Smooth, SC, LN | - | $ \\Omega \\left( \\frac{\\gamma^2 d}{\\mu^2} \\right) $ |  $ \\tilde{O}\\left(\\frac{M^2}{\\mu n^2}\\right) $  |\n| (Xu and Zeevi, 2024) | ERM | UC  | Smooth, PL, LN | - |  $ \\Omega \\left( \\frac{\\gamma^2 d}{\\mu^2} \\right) $ |  $ \\tilde{O} \\left( \\frac{M^2 + \\mu^2}{\\mu n^2} \\right) $  |\n| (Xu and Zeevi, 2024) | PGD | UC  | Smooth, PL, LN | $T \\asymp \\log(n)$  |  $ \\Omega \\left( \\frac{\\gamma^2 d}{\\mu^2} \\right) $  |  $\\tilde{O} \\left( \\frac{M^2 + \\mu^2}{n^2} \\right)$  |\n|(Li et al., 2021)| SGD  | UC  | Smooth, PL, LN | $T \\asymp n^2$  |  $ \\Omega \\left( \\frac{\\gamma^2 d}{\\mu^2} \\right) $  |  $\\tilde{O} \\left( \\frac{M^2 + \\mu^2}{n^2} \\right)$  |\n| (Li and Liu, 2021)  | SGD | AS  | Smooth, SC | $T \\asymp n^2$  | -  |  $\\tilde{O} \\left( \\frac{\\gamma^2 M^2 }{\\mu n} \\right)$  |\n|(klochkov and Zhivotovskiy, 2021)| ERM | AS  | SC | -  |  -  |  $ \\tilde{O} \\left( \\frac{M^2}{\\mu n} \\right) $  |\n|(klochkov and Zhivotovskiy, 2021)| PGD | AS  | Smooth,  SC | $T \\asymp \\log(n)$  |  -  |  $\\tilde{O} \\left( \\frac{\\gamma M^2}{\\mu^2 n} \\right)$  |\n|This work| ERM | AS  | Smooth, SC, LN | -  | $\\Omega \\left( \\frac{\\gamma^2}{\\mu^2} \\right) $ |  $\\tilde{O} \\left( \\frac{M^2 \\gamma^2}{\\mu^3 n^2} \\right)$   |\n|This work | PGD | AS  | Smooth, SC, LN | $T \\asymp \\log(n)$  |  $\\Omega \\left( \\frac{\\gamma^2}{\\mu^2} \\right) $  |   $\\tilde{O} \\left( \\frac{M^2 \\gamma^2}{\\mu^3 n^2} \\right)$ |\n|This work| SGD | AS  | Smooth, SC, LN | $T \\asymp n^2$ |  $\\Omega \\left( \\frac{\\gamma^2}{\\mu^2} \\right) $  |  $\\tilde{O} \\left( \\frac{M^2 \\gamma^2}{\\mu^3 n^2} \\right)$ |\n|This work | SGD | AS  | Smooth, SC | $T \\asymp n$ |  $\\Omega \\left( \\frac{\\gamma^2}{\\mu^2} \\right) $  |  $\\tilde{O} \\left( \\frac{\\gamma^2}{\\mu n} + \\frac{M^2 \\gamma^2}{\\mu^3 n^2} \\right)$ |\n\n\n\n\n\n> Question 4: In Definition 3, is $\\rho$ meant to be a constant? If so, I suggest using a different notation, as $\\rho$ is already used to denote the distribution of $z$. Additionally, did you absorb the dependence on $\\rho$ into $C$ in the proof of Proposition 1? As above, it would be clearer if these constants appeared explicitly in the final bounds.\n\nAnswer: Thanks for catching these points. We will select different symbols to avoid confusion. We'll also revise the bound to show constants depending on $\\rho$ in the final version.\n\n\n\n> Weakness 2 \\& Limitation 2  \\& Limitation 3 \\& Limitation 4: Writing suggestions.\n\nAnswer: We appreciate your feedback and will implement your suggestions in the final version to the best of our ability, enhancing the paper's readability and eliminating ambiguities.\n\n> Limitation 5: Typos.\n\nAnswer: Thanks for noting these typos. We'll fix all minor errors in the final version to the best of our ability.\n\n\n**We’re happy to address any further questions you may have.**\n\nReference\n\nMoritz Hardt et al. Train faster, generalize better: Stability of stochastic gradient descent. 2016.\n\nF. Liao et al. Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods. 2024.\n\nY. Lei. Stability and generalization of stochastic optimization with nonconvex and nonsmooth problems. COLT 2023.\n\nL. Zhang, T. Yang, and R. Jin. Empirical risk minimization for stochastic convex optimization: $O(1/n)$-and $O(1/n^2)$-type of risk bounds. COLT 2017.\n\nY. Xu and A. Zeevi. Towards optimal problem dependent generalization error bounds in statistical learning theory. Mathematics of Operations Research 2024.\n\nS. Li and Y. Liu. Improved learning rates for stochastic optimization: Two theoretical viewpoints.\n\nY. Klochkov, and N. Zhivotovskiy. Stability and deviation optimal risk bounds with convergence rate $O(1/n)$. NeurIPS 2021."}, {"review_id": "la8G5MAF89", "reviewer": "Reviewer_n1ME", "summary": "The paper provides a method to show generalization bounds under uniform stability of gradients for methods optimizing Lipschitz, smooth and strongly convex functions. Starting with a generic generalization bound that replaces that dependence on the Lipschitz constant in prior work to expectation of squared length of the gradient, the paper then shows sharper bounds for ERM, PGD and SGD. Notably, in the low noise regime ($F(w^∗) <O(1/n)$), the bounds for ERM, PGD  is $\\tilde{O}(1/n^2)$. For SGD in a single pass ($T=n$), the bound is $\\tilde{O}(1/n)$ in high probability, and when $T=n^2$, the bound is $\\tilde{O}(1/n^2)$, sharper than previously known results. Another result is a constant-level improvement to concentration of sums of vector valued functions.", "questions": "- Can the authors provide a comparison with prior works in terms of the dependence on the problem parameters (Lipschitzness, smoothness, strong convexity parameters)?", "limitations": "Adequately addressed.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- I find the paper technically strong and all results are presented clearly. In particular, all results are presented in detailed comparison with prior works, which highlights where both the improvements and limitations are.\n- The improvements in the bounds are meaningful and interesting. I think improving the generalization bound from $\\tilde{O}(1/n)$ (limit of prior works) to $\\tilde{O}(1/n^2)$ even under more restrictive assumptions is non-trivial. \n- I don't find any big issues in the proofs except some minor typos.\n\n**Weaknesses**\n- As mentioned above, the main weakness of the paper comes from the fact that the analysis requires stronger assumptions than do prior works (eg, PL vs SC, requiring lower bounds for the sample size). Here, I think the authors should revise the language in the abstract (\"under the same common assumptions\"), which is not correct.\n- Since the paper mainly focuses on the dependence on the sample size $n$, it is unclear how the bounds in terms of problem parameters are improved or degraded. Here a comparison with prior work will be helpful.\n\nMinor:\n- Sentence fragments in Line 337-339. \n- Missing $C_p$ in Eq (7) Line 530.", "was_revised": true, "final_justification": "I maintain my score after the discussion phase.", "rebuttal": "Thanks for your careful review. Here are the replies.\n\n> Weakness 1: As mentioned above, the main weakness of the paper comes from the fact that the analysis requires stronger assumptions than do prior works (eg, PL vs SC, requiring lower bounds for the sample size). Here, I think the authors should revise the language in the abstract (\"under the same common assumptions\"), which is not correct.\n\nAnswer: Thanks for your feedback. We will revise the language in the final version to avoid any potential misunderstanding. We appreciate your valuable feedback.\n\n> Weakness 2: Since the paper mainly focuses on the dependence on the sample size $n$, it is unclear how the bounds in terms of problem parameters are improved or degraded. Here a comparison with prior work will be helpful.\n\nAnswer: Thank you for your suggestion. We have updated the table to include Lipschitzness $M$, smoothness $\\gamma$, and strong convexity parameters/PL condition $\\mu$ and compared with existing works. We will use this revised table in the final version, as it presents comparisons with prior studies more clearly and straightforwardly.\n\n\n|Reference | Algorithm | Method | Assumptions | Iterations  | Sample Size | Bounds  |\n|:---:|:---:|:---:|:---:|:---:| :---:|:---:|\n| (Zhang et al., 2017) | ERM | UC |  Smooth, SC, LN | - | $ \\Omega \\left( \\frac{\\gamma^2 d}{\\mu^2} \\right) $ |  $ \\tilde{O}\\left(\\frac{M^2}{\\mu n^2}\\right) $  |\n| (Xu and Zeevi, 2024) | ERM | UC  | Smooth, PL, LN | - |  $ \\Omega \\left( \\frac{\\gamma^2 d}{\\mu^2} \\right) $ |  $ \\tilde{O} \\left( \\frac{M^2 + \\mu^2}{\\mu n^2} \\right) $  |\n| (Xu and Zeevi, 2024) | PGD | UC  | Smooth, PL, LN | $T \\asymp \\log(n)$  |  $ \\Omega \\left( \\frac{\\gamma^2 d}{\\mu^2} \\right) $  |  $\\tilde{O} \\left( \\frac{M^2 + \\mu^2}{n^2} \\right)$  |\n|(Li et al., 2021)| SGD  | UC  | Smooth, PL, LN | $T \\asymp n^2$  |  $ \\Omega \\left( \\frac{\\gamma^2 d}{\\mu^2} \\right) $  |  $\\tilde{O} \\left( \\frac{M^2 + \\mu^2}{n^2} \\right)$  |\n| (Li and Liu, 2021)  | SGD | AS  | Smooth, SC | $T \\asymp n^2$  | -  |  $\\tilde{O} \\left( \\frac{\\gamma^2 M^2 }{\\mu n} \\right)$  |\n|(klochkov and Zhivotovskiy, 2021)| ERM | AS  | SC | -  |  -  |  $ \\tilde{O} \\left( \\frac{M^2}{\\mu n} \\right) $  |\n|(klochkov and Zhivotovskiy, 2021)| PGD | AS  | Smooth,  SC | $T \\asymp \\log(n)$  |  -  |  $\\tilde{O} \\left( \\frac{\\gamma M^2}{\\mu^2 n} \\right)$  |\n|This work| ERM | AS  | Smooth, SC, LN | -  | $\\Omega \\left( \\frac{\\gamma^2}{\\mu^2} \\right) $ |  $\\tilde{O} \\left( \\frac{M^2 \\gamma^2}{\\mu^3 n^2} \\right)$   |\n|This work | PGD | AS  | Smooth, SC, LN | $T \\asymp \\log(n)$  |  $\\Omega \\left( \\frac{\\gamma^2}{\\mu^2} \\right) $  |   $\\tilde{O} \\left( \\frac{M^2 \\gamma^2}{\\mu^3 n^2} \\right)$ |\n|This work| SGD | AS  | Smooth, SC, LN | $T \\asymp n^2$ |  $\\Omega \\left( \\frac{\\gamma^2}{\\mu^2} \\right) $  |  $\\tilde{O} \\left( \\frac{M^2 \\gamma^2}{\\mu^3 n^2} \\right)$ |\n|This work | SGD | AS  | Smooth, SC | $T \\asymp n$ |  $\\Omega \\left( \\frac{\\gamma^2}{\\mu^2} \\right) $  |  $\\tilde{O} \\left( \\frac{\\gamma^2}{\\mu n} + \\frac{M^2 \\gamma^2}{\\mu^3 n^2} \\right)$ |\n\n\n\n> Weakness 3: Minor.\n\nAnswer: Thanks for noting these typos. We'll fix all minor errors in the final version to the best of our ability.\n\n\n\n> Question: Can the authors provide a comparison with prior works in terms of the dependence on the problem parameters (Lipschitzness, smoothness, strong convexity parameters)?\n\n\nAnswer: Please refer to the answer for Weakness 2 and the table given above.\n\n\n**We’re happy to address any further questions you may have.**\n\nReference\n\nL. Zhang, T. Yang, and R. Jin. Empirical risk minimization for stochastic convex optimization: $O(1/n)$-and $O(1/n^2)$-type of risk bounds. COLT 2017.\n\nY. Xu and A. Zeevi. Towards optimal problem dependent generalization error bounds in statistical learning theory. Mathematics of Operations Research 2024.\n\nS. Li and Y. Liu. Improved learning rates for stochastic optimization: Two theoretical viewpoints.\n\nY. Klochkov, and N. Zhivotovskiy. Stability and deviation optimal risk bounds with convergence rate $O(1/n)$. NeurIPS 2021."}]

Author rebuttal:

Meta-review: The paper proves fast rates for strongly convex, smooth and Lipschitz losses via stability. Specifically rates of order 1/n^2. 

The reviewers agree that the results are strong. While the conditions are restrictive the paper does provide a strong theoretical push. I recommend an accept.
Decision: Accept (poster)