High Probability Bounds for Non-Convex Stochastic Optimization with Momentum
Authors: Shaojie Li
Pengwei Tang
Bowei Zhu
Yong Liu
Venue: ICLR 2026 Poster (2026)
Keywords: Momentum
nonconvex learning
generalization
Primary area: learning theory

Abstract: Stochastic gradient descent with momentum (SGDM) is widely used in machine learning, yet high-probability learning bounds for SGDM in non-convex settings remain scarce. In this paper, we provide high-probability convergence bounds and generalization bounds for SGDM. First, we establish such bounds for the gradient norm in the general non-convex case. The resulting convergence bounds are tighter than existing theoretical results, and the obtained generalization bounds seem to be the first for SGDM. Next, under the Polyak-{\L}ojasiewicz condition, we derive bounds for the function-value error instead of the gradient norm, and the corresponding learning rates are faster than in the general non-convex case. Finally, by additionally assuming a mild Bernstein condition on the gradient, we obtain even sharper generalization bounds whose learning rates can reach $\widetilde{\mathcal{O}}(1/n^2)$ in the low-noise regime, where $n$ is the sample size. Overall, we provide a systematic study of high-probability learning bounds for non-convex SGDM.

Published as a conference paper at ICLR 2026
HIGH PROBABILITY BOUNDS FOR NON-CONVEX STOCHASTIC OPTIMIZATION WITH MOMENTUM
Shaojie Li', Pengwei Tang', Bowei Zhu', Yong Liu
'College of Design and Engineering. National University of Singapore, Singapore Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China 1i_s{ @euus. edu. sg, (tangpwei, bowei. zhu, Liuyonggsal
ABSTRACT
Stochastic gradient descent with momentum (SGDM) is widely used in machine learning, yet remain scarce. In this paper, we provide high-probability convergence bounds and generalization bounds for SGDM. First, we establish such bounds for the gradi- ent norm in the general non-convex case. The resulting convergence bounds are tighter than existing theoretical results, and the obtained generalization bounds seem to be the first for SGDM. Next, under the Dalyak-Lojasiewinn condition, we derive bounds for the function-value error instead of the gradient norm, and the corresponding learning rates are faster than in the general non-convex case. Fi- nally, by additionally assuming mild Bernstein condition on the gradient, we ob- tain even sharper generalization bounds whose learning rates can reach ((1nn²) in the low-noise regime, where is the sample size. Overall, we provide a sys- tematic study high-probability learning bounds for non-convex SGDM.
learning bounds for SGDM in non-convex settings
INTRODUCTION
Stochastic optimization plays an essential role in modern statistics and machine learning, as many learning problems can be cast stochastic optimization tasks. Over the past decades, there has been substantial progress the development of stochastic optimization algorithms, among which stochastic gradient descent with momentum (SGDM) has attracted particular attention due to its simplicity and low per-iteration computational cost (Goodfellow et al., 2016: Li & Orabona 2020). As fundamental algorithm for stochastic optimization, SGDM has been remarkably successful in natural language understanding, computer vision, and speech recognition (Krizhevsky et al. 2012 Hinton al. 2012 Sutskever al. 2013).
Typically, SGDM augments stochastic gradient descent (SGD) with momentum term in the update rule, i.e., uses the difference between the current and previous iterates. The intuition is that, when the recent update direction is informative about the local descent direction, SGDM can leverage this inertial signal-scaled by the momentum parameter-to smooth stochastic gradients rather than relying solely on the instantancous gradient at the current iterate, as in plain SGD, Much of the state- of-the-art empirical performance deep learning has been achieved using SGDM (Huang et al.)
2017 Howard et al., 2017]] He et al.] 2016; Kim et al. 2021a) Yet, from a theoretical standpoint, analysis of learning bounds for SGDM remains relatively underdeveloped (Li al. 2022 &
Orabona 2020).
The learning performance of SGDM can be studied from two complementary perspectives: con- vergence bounds and generalization bounds. Convergence bounds focus on how well the algo- rithm optimizes the empirical risk, whereas generalization bounds quantify how the learned model performs unseen test data. From the convergence perspective, existing analyses of SGDM or deterministic gradient descent with momentum (DGDM) in non-convex settings are mostly in ex- pectation (Ochs al. 2014 2015 Ghadimi et al.; 2015 Lessard et al. 2016 Yang al. 2016 Wilson et al., 2021 Gadat et al. [018]] Orvieto et al.] [020 Can et al. 2019 Li et al.) 2022 Yan
al. 2018 Liu et 2020), to mention only few. However, expected bounds do not rule out
"Corresponding Author.

---

Published as a conference paper at ICLR 2026
the possibility of extremely bad outcomes (Li & Orabona 2020: Liu et al. 2023 Moreover, in practical large-scale applications, the training procedure is typically run only once, since it can be very tume-consuming For such single-run performance, prooh--bbbbblity bounds are more infor- mative than expectation bounds (Harvey et al. 2019). To the best of our knowledge, there are two works that provide high-probability convergence bounds for SGDM (Li & Orabona 2020 Cutkosky & Mehta, 2021). Specificallyy, Cutkosky& & Mehta (2021) assume that the gradient noise satisfies a 50-2) for
0-order moment condition with 9 E (1. and obtain a convergence rate of order Ö the gradient norm, where T denotes the number of iterations. Li & Orabona (2020) establish a convergence bound of order ((1/vT) for the squared gradient norm under sub-Gaussian gradient noise. As discussed in Li et al. (2022). it is unclear whether this rate can be improved or extended to more general noise models beyond the sub-Gaussian case. Overall, the convergence rates in Li & Orabona (2020); Cutkosky & Mehta (2021) are relatively slow, and, importantly, no generalization bounds provided in either work.
From the generalization perspective, existing results for SGDM and DGDM are even scarcer. Ong (2077): Chen et al. (2018) derive expected generalization error bounds for DGDM with a specific quadratic loss by using algorithmic stability (Bousquet & Elisseefi 2002 Hardt et al. 2016). Their analysis, however, does not extend easily to general loss functions. It is conjectured in Chen et al. (2018) that their uniform stability bound might also hold for general convex losses. Motivated by this conjecture, [Ramezami- Kebrya et al. (2024) study generalization error bounds for SGDM with general loss functions. Somewhat surprisingly. they construct a counterexample showing that, even for convex loss functions, the uniform stability gap (in expectation, over the internal randomness of the algorithm) of SGDM run for multiple epochs can diverge. In a related direction, AAtii & Koren (202I) show that, in the general convex case, the uniform stability gap of deterministic Nes- terov's 's accelerated gradient (NAG) can diverge exponentially fast with the number of iterations. We emphasize that uniform stability is only sufficient condition for generalization: it remains unclear how weaker stability notions (such on-average stability (Shalev-Shwarzz et al. 2010 behave for SGDM. Overall, there are significant obstacles to establishing general generalization guarantees for SGDM, especially for broad classes of loss functions. Furthermore, in the convergence analysis of SGDM, high-prohability generalization bounds are substantially more challenging to derive than expectation-based bounds (Bousquet et al. 2020 Bassily et al. 2020 Feldman & Vondrak, 2019).
Therefore, both high-probability convergence bounds and high-probability generalization bounds for SGDM remain far from fully understood. Motivated by the above limitations, this paper aims to establish such bounds for SGDM, with a particular focus on non-convex settings. For brevity, we will refer all bounds on the performance of the learned model on test data (including generaliza- tion error bounds and excess-risk bounds) simply as generalization bounds. Our main contributions can be summarized as follows.
At high level, we study the case where the stochastic gradient noise follows a sub- Weibull distribution (Vladimirova et al. 2019 2020 Kuchibhotla & Chakrabortty) 2018), which generalizes the sub- sub-Gaussian noise considered in Li & Orabonal (2020) to poten- tially heavier-tailed distributions. Our learning bounds under this assumption reveal how the rates of convergence and generalization change one moves from sub- aab-Gaussian| / sub- exponential (light-tailed) noise to heavy-tailed noise with exponential -tape tails.
We first provide high-probability analysis of SGDM in the general non-convex case. In this setting, we derive convergence bounds of order ((L/T)/2) and generalization bounds of order O (d' /nn/22 for the squared gradient norm, where d is the dimension and n is the sample size. The convergence bounds are tighter than those in related work, and the generalization bounds seem to be the first such results for SGDM.
We next analyze SGDM under the Polyak-Lojasiewize condition for non-convex objec- tives. In this case, we obtain sharper convergence bounds of order Ö(1/T). Furthermore, these bounds are established for the last iterate of SGDM and for the function-vulue er- ror, rather than for the average iterate and gradient norm considered in the general non- convex case. In addition, we derive generalization bounds of faster order Ö (+ for SGDM, which, to our knowledge, have not been previously available.
Finally, we impose mild Bernstein condition on the gradient. Under this additional as- sumption, improve the generalization bound of order O d+log(1/8)) a bound of order n
2

---

Published as a conference paper at ICLR 2026
+ where F denotes the optimal population risk. In the low-noise regime where F* is small, this bound yields faster learning rate of order ((Lnn"), showing tighter dependence on the sample size n. Another attractive feature of this bound is that the dimension d no longer appears, allowing it to easily incorporate massive neural networks that are often high-dimensional.
In summary, by considering increasingly strong structural conditions on the objective function (from general non-convexity, to PL., to PT. plus Bernstein condition), we establish hierarchy of improved learning bounds with different rates. This provides systematic picture of the high-pree high-probability learning guarantees for SGDM from both convergence and generalization perspectives.
The rest of the paper is organized as follows. Preliminaries presented in Section Our main results are stated in Section 3 We conclude in Section 4 Numerical experiments are reported in Section [A] Appendix [ together with Table summarizes main results and the most relevant related bounds of SGDM. All proofs are deferred to the Appendix.
2
PRELIMINARIES
2.1 NOTATIONS
Let X' C Rdd be the parameter space and let IP be probability measure on sample space 2. Let f: x - R,+ be (possibly non-convex) loss function. We consider the stochastic optimization problem
min F(x) == [x
x
where F is referred the population risk and Egar denotes expectation with respect to (w.r..) the random variable z drawn from P.
In practice the distribution P is unknown and only observe dataset 5 {21, ........ 2n ) drawn independently and identically (i.id.) from P. One typically optimizes the empirical risk
min Fs(x) XEX
[(x 2:).
To optimize Fs. SGDM has been widely adopted (Polyak 1964 Qian 1999 Sutskever al. 2013 Li & Orabona 2020). In this work we focus on Polyak's ' momentum, also known as the heavy-ball algorithm or classical momentum, which is arguably the most popular form of momentum in current machine learning practice (Liu et al. 2020). The pseudocode of SGDM (Polyak's momentum) is given in Algorithm The vanilla SGD update is
X
x; 7h V fx 2,
In Step 3 of Algorithm ] SGDM introduces a momentum vector m;-1 and forms a momentum term weighted by parameter to adjust the gradient estimate V fxx; 2,.) of SGD. In Step 4, SGDM then updates the iterate via
x X, m,
Equivalently, the SGDM update can be written as
X++1 = x, 7 V (x 24,) + 7(x - x(-1).
We now introduce some notation. Let B sup V (0)= where (f(;z) denotes the gradi-
ent of f w.r.t. the first argument and || denotes the Euclidean norm. For any Rt > O, we define B(xo, R) {x E Rdd x < Rt} which denotes ball with center x E Bd and radius R.
Let x(S) E arg minxex Fx(x) and x* E arg min Fx)). We write x b if there exist universal
constants e' > such that ca < S c'a. Throughout the paper we use standard order-notation such as (-) and (())
2.2 ASSUMPTIONS
In this subsection collect the assumptions that will be invoked in our main theorems.
3

---

Published as a conference paper at ICLR 2026
Assumption 2.1. The differentiable function is (possibly) non-convex and, for any 2, the mapping x x f(x;2( 2) is L-smooth, i.e., for every X2:
V - V fx(x2 =)1l S - x2ll
where the gradient operator and || is the Euclidean norm.
Remark 2.2. Further properties of smooth functions are collected in Lemma C.7
Assumption 2.3. The gradient at satisfies Bernstein-type moment condition: there exists B. 0 such that for all integers with k 2 2,
E. [IV I| - E. [IV][[IV B
Remark 2.4. The Bernstein condition standard in learning theory. As shown in Wainwright (2019). for random variable X with mean μ [E[X] and variance o² =E[x3]- say that X satisfies the Bernstein condition with parameter if for all integers k
E - - m0 S kl o
The Bernstein condition essentially equivalent X being sub-ex uub-exxonential: see the discussion in Remark 4 of Lei (2020). Classical sub-Gaussian and sub-exponential distributions satisfy this con- dition, since their k-th moments are controlled by the second moment. this sense, the Bernstein condition is quite mild and, for instance, weaker than assuming that X is almost surely bounded. Assumption 2.3 simply applies this Bernstein condition to the random variable [x";; =)]: is weaker than assuming that || f(x; =) Vx E X, is uniformly bounded, while the latter bounded- gradient assumption is widely used in stochastic optimization (Zhang et al. 2017).
Assumption 2.5. For all z", and for some positive G 0, the empirical risk satisfies
T/ (xs(x))l S G, E.
Remark 2.6. In the theoretical analysis of stochastic optimization, is common to assume uni- formly bounded stochastic gradient,
[x(x)
Vx X, Vz 2,
which is sometimes referred to as the Lipschitz continuity of f (Li 202.2 Li & Orabona 2020).
Assumption 2.5 relaxation of this bounded-gradient assumption: it multiplies the gradient norm of Fs by the stepsize instead of bounding each stochastic gradient V /x(xx; =). Since the stepsizes decrease to zero, the gradients of F's are allowed to grow. For typical decay rates = O(t
or V/+ = (1-2)) (Lei & Tang 2021 Assumption 2.5 permits [x)))x))] to grow at rates ( and (L), respectively.
In the next, we introduce the Solyak--Lojsseewic. (PL) condition.
Assumption 2.7. Fix set X' and let f* := minxex f(x). We say that differentiable function f X + R satisfies the Lojasieeiii condition with parameter on A' if for all x E X,
1 [v(())1 2μ
f(x)
Remark 2.8. Fast rates cannot be achieved for free. The Polyak-Lojjsiewicz condition widely used in the optimization community to obtain fast convergence rates (Necoara et al., 2019
Karimi
al. 2016) and one of the weakest curvature conditions to replace the strong convexity
Karimi
et al. 2016). Many important models are known to satisfy PL inequality, at least locally. Notable
examples satisfying the PL. condition include two-layer neural networks (Li Yuan 2017) matrix
completion (Sun & Luo| 2016). dictionary learning (Arora et al., 2015), and phase retrieval (Chen
Candes 2015). Kleinberg et al. (2018) provide empirical evidence that the (smoothed) loss of
practical deep networks locally exhibits one- ine-point convexity property of PL type. More rigorously, Soltanolkotabl et al. (2018) analyze over-parameteriee shallow networks with quadratic activations and prove that, in the interpolation regime where the training loss is zero, the empirical risk satisfies a PL inequality. These examples motivate our focus on studying SGDM under the PL curvature assumption.
4

---

Published as a conference paper at ICLR 2026
Algorithm SGD with Momentum (SGDM)
Require: stepsizes {Te ft. dataset (21, (.,, ... 2n). and momentum parameter < 1.
Initializtion: X1 0, mo O,
1: for /- ..., T do
2: sample j/: from the uniform distribution over the set (j : j E [n]].
update m, = - V (xx;
4: update X = m.
5: end for
In our analysis we will apply Assumption 2.7 both the empirical risk Fs and the population risk F. When studying optimization (training) performance, we assume that P's satisfies PL inequality with parameter (()); when studying generalization and excess risk, we assume that satisfies a (possibly different) PL inequality with parameter μs. We keep the notation μ(S) and separate to emphasize that the curvature at the sample level need not coincide exactly with that of the underlying population.
Finally, we specify an assumption the noise of the stochastic gradient. Assumption 2.9. The gradient noise f 2z.) Vxs(x)) satisfies
E, exp(IIV/
VF'((x)l//K)) 2,
for positive K and 1/2.
Remark 2.10. Li & Orabona 2020) assume the sub-Gaussian-type condition
Ej. exp [ z,,) VFs(x.))|//33) 2,
which ensures that the noise tails are dominated by those of Gaussian distribution. In contrast, Assumption 2.9 generalizes this richer class of distributions, including sub-exponential noise (corresponding to = 1) and even heavier-tailed noise (0 > 1). Condition
( is precisely the defining property of sub- Weibull random variable (Vladimirova et al. 2020): random variable X satisfying Ejexp( (pp(((())) ((XI/K)1//)) tail parameter 0, and larger means heavier tails (Kuchibhotla & Chakrabortty 2018). Hence, the learning bounds in this paper apply broad class of heavy-ttailed gradient noise distributions. Our motivation for studying neb-Weibull gradient noise is twofold. First, it allows us to explicitly quan- tify how the convergence and generalization rates degrade when moving from aub-Gaussian/sub> exponential (light-tailed) noise to heavy-tailed noise with exponential-yye body of work provides empirical and theoretical evidence that the noise in stochastic optimization algorithms is often heavier-tailed than Sub-Gaussian (Panigrahi et al. 2019; Madden et al. 2024
2 for some K and > 1/2 called
with
tails. Second, a growing
Gurbuzbalaban et al. 2021 Simsekli et al. 2019; Şimşekli et al., 2019 Zhang et al. 2020 Wang et al. 2021 Gurbuzbalaban & Hul 2021).
2019
MAIN RESULTS
This section presents main theoretical results.
3.1 LEARNING BOUNDS IN THE GENERAL NON-CONVEX CASE
In the general non-convex case, we cannot guarantee that the algorithm finds global mini- mizer, focus on approximate first-order stationary points. For the convergence analysis, we are interested in iterates X, satisfying [[V & c, while for generalization we con- sider [>x))2) c. As is standard in the non-convex literature, measure optimization and generalization performance via the average squared gradient norms ([FFsxx) and T DE [|V respectively.
3.1.1 CONVERGENCE BOUNDS
We first provide gig-probabbiltty convergence bounds for SGDM. These bounds characterize how the algorithm minimizes the empirical risk Fs.
5

---

Published as a conference paper at ICLR 2026
Theorem 3.1. Let be the sequence of iterates generated by Algorithm 7
Set the stepsize
= ct where e I 1 (1-7)² 4 31.-1y
(1)- 1f0 suppose Assumptions 2.1 and 2.9
hold. Then for any (0,1), with probability 1
T
o
(log(110) log
VT
(2). 1f < 0 < 1, suppose Assumptions
2.1 2.5 and 2.9
hold.
Then for any å E (0, 1), with
probability 1 6,
1
T
= o log (1/8) log T
Σ
[VF((x))1
T
VT
[=1
(3). 1f0 1, suppose Assumptions 1-
2.1 2.5 and 2.9 hold. Then for any 8 E (0, 1), with probability
|VFs(x))1 o log ( log(1 (5((1/))/
log (1/0) log T
VT
Remark 3.2. The bounds in Theorem 3.1 are all of order ((IVV)). The dependence on the tail parameter 0 shows that larger 0 leads worse (slower) convergence, which matches the intuition that heavier-tailed gradient noise degrades optimization performance. We now compare these results with related work (Li Orabonal 2220;; Cutkosky & Mehtal 202T). Cutkosky & Mehta (202I) analyze different algorithmic setting that combines gradient clipping, variant of momentum (distinct from Polyak's 's momentum), and normalized gradient descent. Building on this line of work, [i & Liu (2023) further considers clipping variants of momentum. We primarily compare against (Cutkosky Mehta (02T), its setting aligns more closely with this paper (iee. momentum without clipping). The Theorem 2 of (Cutkosky & Mehta 2021) establishes a convergence bound of order
log (T/5)
T
for (VFss())) under smoothness and O-moment condition the gradient, where 0 (1, 2]. In the case 2, this rate becomes 1/4). By Jensen's inequality,
T
2
1 T
(x.))
S
VFs(x))11
T
so Theorem 3.1 implies the same O(T-1/4 rate for + ET= study Polyak's momentum and, in their Theorem 1, obtain a convergence bound of order
(x))) Li & Orabona (000
o (los
log (oog(T/) (T/8) log T
vT
[Vx(())) under smoothness and sub-Gaussian gradient noise (i.e., 0 = 1/2). Since we also analyze Polyak's momentum, the comparison with Li & Orabonal (2020) is more natural. Under the same assumptions, part (1) of Theorem refines this to
for + -
o (og(1/8) log vT
Although this improvement is only logarithmic, it may be the strongest possible refinement in the general nonconvex setting we consider. For smooth nonconvex stochastic optimization with a first- order oracle and controlled noise, the rate (L)VVT) terms of the expected squared gradient norm known be optimal (up logarithmic factors) (Arjevani al. 2019). Consequently, under the same structural assumptions, any further progress can only affect constants and logarithms but not the leading 1/ //VT scaling. Theorem 2 in Li Orabona 2020) further analyzes a variant of AdaGrad with Polyak's 's momentum, called delayed AdaGrad, whose stepsize does depend on the current gradient (Li & Orabonal 2019). The corresponding convergence bound is of order
max o dl 3/2 ((T/))
dB log 2 (T/6)
VT
T

---

Published as a conference paper at ICLR 2026
When the dimension d is small, this gives rate of order Od log logx (T/8)/VT) which is clearly weaker than the dimension bounds in Theorem 3.1
In the non-convex, stochastic setting, clear separation between SGD and SGDM remains clusive (Li & Orabona 2020; Zou et al. 2018), even at the empirical level. For example, Kidambi et al. 2018)) provide theoretical and empirical evidence that standard momentum schemes schemes-Polyak'ss mo- mentum and Nesterov Accelerated Gradient-de do not enjoy a universal acceleration guarantee in the stochastic regime. Even with optimally tuned hyperparameters, there exist instances where Polyak's momentum and Nesterov's method do not outperform vanilla SGD. In particular, when the batch size small (e.g.. 1), their performance is often nearly indistinguishable from, or even worse than, that of SGD. This batch-size-one regime is exactly the setting we study here, and our theory is con- sistent with these observations. A work (Li & Liul 2022) derives high-probability convergence and generalization results for SGD without momentum under the same assumptions, yielding rates of the same order as those obtained here (up to constants and mild logarithmic factors). This paper closes the theoretical gap for SGDM: we show that the widely used momentum method, under the general nonconvex PL/ Bernstein assumptions, also enjoys high- high-probability convergence and gen- eralization guarantees of comparable order to those known for SGD, that SGDM has essentially the same theoretical performance as SGD under these conditions. A promising direction for future work is to extend our analysis to the large-batch regime and to investigate how the potential benefits of momentum depend on batch-induced noise reduction.
3.1.2 GENERALIZATION BOUNDS
We now present high-probabilite generalization bounds for SGDM, which quantify how well the learned models perform the underlying data distribution.
Theorem 3.3. Let be the sequence of iterates generated by Algorithum ! Set the stepsize as ? at 2 where e S 17 and choose the number of iterations as x n/d.
(1-))²
(1). If 2. suppose Assumptions 2.1 and 2.9
hold. Then any 8 E (0,1), with probability 1 1
1 T
o((5)
d
1/2
log" 10gg( (1))
|F
log
(2). 1f < A <
1, suppose Assumptions
2.1 2.5 and
2.9 hold. Then for any 5 E (0,1), with
probability - 6,
T T
[F((2)))
(
1/2
log
n
log
20g20+2 20+2 )
1=1
(3). 1f0 1, suppose Assumptions
2.1
2.5 and 2.9 hold. Then for any 8 E (0, 1), with probability
1-6, 6,
1
Σ IIF(())) = (
1/2
log 20+2 20+2 (1) + log 0-1 n log" (1))
log
T
Remark 3.4. The bounds in Theorem 3.3 are of order Õ((d/ (idd/n)) 1/2) and again heavier tails (larger 0) lead to slower rates. As in Theorem 3.1 when = 1/2 Assumption 2.5 no longer needed. As discussed in the introduction, algorithmic stability-in particular uniform stability- to fail for SGDM with general loss functions, since the uniform stability gap may diverge even in convex settings (Ramezani- KebrryaKKeKaaaa et al., 2024). This consistent with the general principle that there is a trade-off between convergence speed and stability: faster-converging algorithms tend to be less stable, and vice versa (Chen et al.
2018). Our proof technique instead belongs to the uniform con-
vergence approach (Xu & Zeevi 2020: Lei & Tang 2021). which shows that the empirical risks of all hypotheses in a class converge uniformly to their population risks. the general non-convex case, dependence on the ambient dimension d is typically unavoidable for such uniform conver- gence bounds (Xu & Zeevi 2020; Lei Tang 2021). which is reflected in the d-dependence in Theorem 3.3 We emphasize, however, that in Section 3.3 we will obtain dimension-free gener- alization bounds by imposing additional structure (a Bernstein condition) and working in the PL regime.

---

Published as a conference paper at ICLR 2026
3.2 LEARNING BOUNDS WITH POLYAK- LEATA---OISIEIICZZZZ CONDITION
In non-convex optimization under the Polyak-Lojasiewiczz (PL) condition, we are interested in up- per bounds the function-value error. Accordingly, we measure optimization performance and generalization performance via (x(x++1) - Fs (x()))) and F(xT+1) - F(x*), respectively.
3.2.1 CONVERGENCE BOUNDS
We first present pregh-robbbility convergence bounds for SGDM under the PL condition.
Theorem 3.5. Let Xt be the sequence of iterates generated by Algorithm 7 Set the stepsize as 12L-ALs (8C-)L
T [() such that to 2 max| ((S)[117)3 [I-7)P((S] + 1, SC, E 1,, where
(1-7)a(S)
C. = 1 7 Inq
3 is constant that depends only on
(1). 1f = 3. suppose Assumptions 2.1 and 2.9 hold, and assume that Fs satisfies Assumption 2.7 with parameter Sp(S). Then, for any 0 (0, 1J. with probability 1 -88
Fs(XT+1) - Fs(x(S)) = O 1og(1/6)
T
(2). 1 < < 1, suppose Assumptions 2.1 2.5 and 2.9
hold, and assume that F' satisfies with probability 1 d,
Assumption 2.7 with parameter 2y(S). Then, for any
(0,
log" a+ (1/8) log 1/2 1/2T
Fs(XT+1) - Fx((((S) o
(3). If > 1, suppose Assumptions 2.1 2.5 and 2.9 hold, and assume that Fs satisfies Assumption 2.7 with parameter 2p(S). Then, for any (0,1). with probability 1 8, have the following inequality
Fs(x Fs (x()))) = o log + log
(T/5) 1/2 122
T
Remark 3.6. Theorem 3.5 shows that, under the PL condition, SGDM enjoys fast convergence rates:
the O(/vVT) rate in Theorem 3.1 is improved a faster ( IT) rate. By the smoothness property the bounds in Theorem 3.5
in Lemma C.7
VF5(XT+1)
< (F(Fs(XT+1) (S)))
also apply (up constants) to the squared gradient 1/2, Assumption 2.5 is not needed. As in the non-PL case, larger 0 (heavier tails) deteriorates the convergence rate. One can also verify that these PL-based convergence bounds are strictly sharper than the corresponding results in Li & Orabonal (2020): Cutkosky & Mehta (2021). To the best of our knowledge, fast (1/TT) high-probability rates for SGDM in non-convex settings under PL-ttpe assumptions have not previously been established in the literature.
||V (x Moreover, when
3.2.2 GENERALIZATION BOUNDS
We next present figh-probability generalization bounds for SGDM under the PL condition.
Theorem 3.7. Let X, be the sequence of iterates generated by Algorithm Set the stepsize as
(o) such that to Z max{ ((S)(17))) [1~7)=M(S) + 1, LC,(
12L-4Ly (8C,)L
1, 1, where
(1-7)n(S)
3 is a constant that depends only on 7,, and choose x C, = = h lnq
(1). 1f suppose Assumptions 2.1 and 2.9 hold, assume that Fs satisfies Assumption 2.7 with parameter SS), and that F satisfies Assumption 2.7 with parameter 2p. Then, for any E0, 1), with probability -
1 = o(
d + log(1/0)
log (2) log
n
(2). If < < 1, suppose Assumptions 2.1 2.5 and 2.9 hold. and assume that Fs satisfies Assumption [2. with parameter 2Ss(S), and that satisfie Assumption 2.7 with parameter 2p. Then, for any ó E (0. 1), with probability 1 -
F(xT+1) - -F(x)) = 0 d log(1/6) log
log 28+1 2001(11 ( log
8

---

Published as a conference paper at ICLR 2026
(3). If 1, suppose Assumptions 2.7 2.5 and 2.9 hold, and assume that Fs satisfies Assumption
2.7 with parameter 2,(S), and that satisfies Assumption 2.7 with parameter 2p. Then, for any
0 (0, 1), with probability 1
dd log(1/0) 2 log
(xT+1)-P((x) = 0
log
log
n
measures the gap between the population risk of the last iterate and the optimal population risk, and is often referred to the excess risk in learning theory (ellmaan & Vondrak 2019 Bassily et al. 2020).. Theorem 3.7 shows that, when both the empirical risk F's and population risk F satisfy the PL condition, SGDM enjoys generalization bounds of order ( + log lolllog//)//0 (1/8))/m). improving the dependence on n compared to the general non-convex case T'eeorem 3.3 By the smoothness property in Lemma C.7
Remark 3.8.
The quantity 1(
(F(x++1) < (F.(F((++1) -
We also emphasize that, in contrast with Section [.1 the bounds Section 3.2 are stated for the last iterate of SGDM rather than the time-averaged iterate. Overall, the pair of results Theorems and 3.7 illustrates the qualitative picture that in the general non-convex regime can expect O(1/v and ( (n) rates, while under PL-type curvature the rates improve O(1TT) and (1/nn), respectively.
F(x")), so the bounds in Theorem 3.7 also directly control
3.3 LEARNING BOUNDS WITH BERNSTEIN CONDITION
In this section, we derive sharper generalization bounds by imposing the Bernstein condition.
Theorem 3.9. Assume that the set satisfies X' S. B(x", R). Let X2 be the sequence
of iterates generated by Algorithm 1 Set the stepsize as ((S)(c+1o) such that to z (&C,)L
3 constant max 12L-1L- (((5) (1-7)+a(S) +1, SC, SC,, LL++(())) 1,13, where Cty 1+ ln la7
111 (1-7)u(S)
that depends only on and choose T=m²
(1).
1 3. suppose Assumptions 2.1 2.3 and 2.9 hold, assume that Fs satisfies Assump-
tion 2.7 with parameter 2p(S), and that F satisfies Assumption 2.7 with parameter 2p. If
cL (d++og 2lox(2nB-21
where is an absolute constant, then for any d (0, with probabil-
ity 6,
F(xT+1)- - F(x") = o log (1/8), n
F(x") F(x*) log(1/6)
n
2.3 2.5 and 2.9 hold, assume that F's satisfies As- sumption 2.7 with parameter 25((),, and that F satisfies Assumption 2.7 with parameter 2p. If > (d='(ll 8lox(2n
(2). 1f 0 1, suppose Assumptions 2.1
where is an absolute constant, then for any d E (0,1), with probabil-
ity 5,
F(xT4)) o log 0+ (1/6)
1/2 /2,,, F(xx)
n²
n
(3). 0 0 1, suppose Assumptions 2.1 2.3 2.5 and 2.9 hold, assume that Fs satisfies As- sumption 2.7 with parameter Ss(S), and that satisfies Assumption 2.7 with parameter 2p. If (d'(dd 2boa(2np-21
where is an absolute constant, then any d (0, with probabil-
iry 1 6,
F(xr+1) F(x") = o (logg log 3(0-1) (n/6) log 0+3 (1/8) log 1/2 F(x*) log(1/5)
n²
n
(4). Furthermore, if we additionally assume F(x*) O(1/n), then the bounds in (1)-(3) simplify, respectively,
log (1/8) o
log" o+ ( log 1/2
log
3(9-1)
(n/6) log 0+ (1/8) log
0
n22
n2
n2

---

Published as a conference paper at ICLR 2026
Remark 3.10. Theorem 3.9 shows that, under the assumptions of Theorem 3.7 together with the Bernstein condition, the excess risk can be improved to
F (F(x) ((F(x)+1) 72
n2
Here Fxx") the minimal population risk and typically very small. Compared with Theorems 3.3 and 3.7 Theorem 3.9 therefore yields strictly sharper bounds. A well-known drawback of the approach is that, for general non-convex problems. usually leads to learning bounds with square-root dependence on the dimension d (Feldman 2016). seen in Theorem 3.3 distinctive advantage of Theorem 3.99 that, by exploiting Assumption 2.3 we remove the de- pendence on d in the upper bound, making the bounds more suitable for high-dimensional models. The auxiliary assumption F(x") ((1/n) part (4) only used to illustrate the attainable rates under low-noise condition. Strictly speaking, F(x") is independent of n, but assumptions such as are standard in the literature; see, for example, Zhang et al. 2017 Srebro al. (2010); Liu et al. (2018): Lei & Ying (2020). In general, ((1/n")-tyr gen- eralization bounds are rare in learning theory. Theorem 3.9 provides, to the best of our knowledge,
F(x")
O(1/n) or even (xx")
the first high-probabilin Ö(1/n²) generalization guarantees for SGDM.
4 CONCLUSIONS
This paper investigates high-probabilityy convergence and generalization bounds for stochastic gra- dient descent with momentum (SGDM) in non-convex settings, thus providing unified view of its optimization and generalization behavior. We hope that these results offer clearer theoretical picture of when and how SGDM guaranteed to perform well, and that they serve as a foundation for further studies of momentum-ben baased methods in modern non-convex learning problems.
ACKNOWLEDGMENTS
This work was supported by the National Key Research and Development Program of China (No. 2024YFE0203200), the National Natural Science Foundation of China (No. 62476277), the CCF- ALIMAMA TECH Kangaroo Fund (No. CCF-ALIMAMA OF 2024008), and the SuaawiiRRenae 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 Engincering 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
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint 191.v.19 2019.
Sanjeev Arora, Rong Ge, Tengyu Ma, and Ankur Moitra. Simple, efficient, and neural algorithms for sparse coding. In Conference on learning theory, pp. 113-149, PMLR, 2015.
Amit Attia and Tomer Koren. Algorithmic instabilities of accelerated gradient descent. In Advances in Neural Information Processing Systems, 2021.
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent nonsmooth convex losses. In Advances in Neural Information Processing Systems, pp. 4381-4391, 2020.
Nicola Bastianello, Liam Madden, Ruggero Carli, and Emiliano Dall' Anese. A stochastic operator framework for inexact static and online optimization. arXiv preprint arXiv:2
200ix:20050090 205. 09884, 2021.
10

---

Published as a conference paper at ICLR 2026
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2:499-522 526, 2002.
Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, pp. 610-626, 2020.
Bugra Can, Mert Gurbuzbalaban, and Lingjiong Zhu, Accelerated linear convergence of stochastic momentum methods in wasserstein distances. In International Conference on Machine Learning, pp. 891-901, 2019.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM trans- actions on intelligent systems and technology (TIST), 2(3):1-27. 2011.
Yuansi Chen, Chi Jin, and Bin Yu. Stability and convergence trade-off of iterative optimization algorithms. arXiv preprint arXiv: 180.001619 2018.
Yuxin Chen and Emmanuel Candes. Solving random quadratic systems of equations is nearly as casy as solving linear systems. Advances in Neural Information Processing Systems, 28, 2015.
Ashok Cutkosky and Harsh Mchta. high-probabiiltyy bounds for non-convex stochastic optimization with heavy tails. In Advances in Neural Information Processing Systems, 2021.
Xiequan Fan and Davide Giraudo. Large deviation inequalities for martingales in banach spaces. arXiv preprint arXiv: 909.05584, 2019.
Vitaly Feldman. Generalization of erm in stochastic convex optimization: The dimension strikes back. In Advances in Neural Information Processing Systems, pp. 3576-3584, 2016.
Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable algo- rithms with nearly optimal rate. In Conference on Learning Theory, pp. 1270-1279, 2019.
Sébastien Gadat, Fabien Panloup, and Sofiane Saadane. Stochastic heavy ball. Electronic Journal of Statistics, ((11)461-529 2018.
Fuhanna Ghadimi, Hamid Reza Feyzmahdavian, and Mikael Johansson. Global convergence of the heavy-ball method for convex optimization. In European control conference (ECC), pp. 310-315, 2015.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Mert Gurbuzbalaban and Yuanhan Hu. Fractional moment-pree ppeeert-preserving initialization schemes for training deep neural networks. In International Conference Artificial Intelligence and Statis- fics, pp. 2233-2241, 2021.
Mert Gurbuzbalaban, Umut Simsekli, and Lingjiong Zhu. The heavy-tail phenomenon in sgd. In International Conference on Machine Learning, p 3964-3975, 2021.
Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 1225-1234, 2016.
Nicholas JA Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. Tight analyses for non-smooth stochastic gradient descent. In Conference on Learning Theory, pp. 1579-1613, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In conference on computer vision and patlern recognition, pp. 770-778, 2016.
Geoffrey Hinton, Deng, Dong Yu, George E Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, Tara N Sainath, et al. Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups 1EEE Signal processing magazine, 2966)82297 2012.

---

Published as a conference paper at ICLR 2026
Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications. arXiv preprint arXiv: arXiv:1704.04861, 2017.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recogmition, pp. 4700-4708, 2017.
Hamed Karimi. Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-tojasewwccz condition. In European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 795-811, 2016.
Rahul Kidambi, Praneeth Netrapalli, Prateek Jain, and Sham M Kakade. On the insufficiency of ex- isting momentum schemes for stochastic optimization. In International Conference on Learning Representations, 2018.
Junhyung Lyle Kim, Panos Toulis, and Anastasios Kyrillidis. Convergence and stability of the stochastic proximal point algorithm with momentum. arXiv preprint arXiv:21 2021a.
Seunghyun Kim, Liam Madden, and Emiliano Dall' Anese. Convergence of the inexact on- line gradient and proximal-gradient under the polyak-tojasiewicz condition. arXiv preprint arXiv:2108.03288 2021b.
Bobby Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does sgd escape local minima? In International conference on machine learning. pp. 2698-2707. PMLR, 2018.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, 2012.
Arun Kumar Kuchibhotla and Abhishek Chakrabortty. Moving beyond sub- uub-gaussianity in high- dimensional statistics: Applications in covariance estimation and linear regression. arXiv preprint arXiv: 1804.0280000 2018.
Jing Lei. Convergence and concentration of empirical measures under wasserstein distance in un- bounded functional spaces. Bernoulli, 2020.
Yunwen Lei and Ke Tang. Learning rates for stochastic gradient descent with nonconvex objectives. IEEE Transactions on Puttern Analysis and Machine Intelligence, 2021.
Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning, pp. 5809-5819, 2020.
Laurent Lessard, Benjamin Recht, and Andrew Packard. Analysis and design of optimization algo- rithms via integral quadratic constraints. SIAM Journal on Optimization, 26(1):57-95, 2016.
Chris Junchi Li. note on concentration inequality for vector-valued martingales with weak exponential-type tails. arXiv preprint arXiv: (009:vv80000029990 2021.
Shaojie Li and Yong Liu. High probability guarantees for nonconvex stochastic gradient descent with heavy tails. In International Conference on Machine Learning, pp. 12931-12963, 2022.
Shaojie Li and Yong Liu. High probability analysis for non-convex stochastic optimization with clipping. arXiv preprint arXiv:2307.13680 2023.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In International Conference on Artificial Intelligence and Statistics, pp. 983-992) 2019.
Xiaoyu Li and Francesco Orabona. A high probability analysis of adaptive sgd with momentum. In Workshop Beyond First Order Methods in ML Systems at ICML'20 20, 2020.
Xiaoyu Li, Mingrui Liu, and Francesco Orabona. On the last iterate convergence of momentum methods. In International Conference on Algorithmic Learning Theory, pp. 699-717, 2022.
Yuanzhi Li and Yang Yuan. Convergence analysis two-layer neural networks with relu activation. In Advances in Neural Information Processing Systems, pp. 597-607, 2017.
12

---

Published as a conference paper at ICLR 2026
Mingrui Liu, Xiaoxuan Zhang. Lijun Zhang, Rong Jin, and Tianbao Yang. Fast rates of erm and stochastic approximation: Adaptive to error bound conditions. In Advances Neural Information Processing Systems, pp. 4678-4484440 1778-4689,41 2018.
Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. In Advances in Neural Information Processing Systems, pp. 18261-18271, 2020.
Zijian Liu, Ta Duy Nguyen, Thien Hang Nguyen, Alina Ene, and Huy Nguyen. High probability convergence of stochastic gradient methods. In International Conference on Machine Learning, pp. 21884-21914, 2023.
Liam Madden, Emiliano Dall' Anese, and Stephen Becker. High probability convergence bounds for non-convex stochastic gradient descent with sub-weibull noise. Journal of Machine Learning Research, 25(241):1-366 2024.
Ion Necoara, Yu Nesterov, and Francois Glineur. Linear convergence of first order methods for non-strongly convex optimization. Mathematical Programming, 175(1):69-107, 2019.
Yurii Nesterov. Introductory Lectures on Convex Optinization: A Basic Course. 2014.
Peter Ochs, Yunjin Chen, Thomas Brox, and Thomas Pock. ipiano: Inertial proximal algorithm for nonconvex optimization. SIAM Journal on Imaging Sciences, 7(2):1388-1419 2014.
Peter Ochs, Thomas Brox, and Thomas Pock. ipiasco: inertial proximal algorithm for strongly convex optimization. Journal of Mathematical Imaging and Vision, 53(2):171-181, 2015.
Ming Yang Ong. Understanding generalization. PhD thesis, Massachusetts Institute of Technology, 2017.
Antonio Orvieto, Jonas Kohler, and Aurelien Lucchi. The role of memory in stochastic optimization. In Uncertainty Artificial Intelligence, pp. 356-366, 2020.
Abhishek Panigrahi, Raghav Somani, Navin Goyal, and Praneeth Netrapalli. Non-gaussianity of stochastic gradient noise. arXiv preprint arXiv: 10l:::990009200 2019.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr compu- tational mathematics and mathematical physics, 4(5):1-17, 1964.
Ning Qian. On the momentum term in gradient descent learning algorithms. Neural networks, 12 (1):145-151, 1999.
Ali Ramezani-Kebrya, Kimon Antonakopoulos, Volkan Cevher, Ashish Khisti, and Ben Liang. On the generalization of stochastic gradient descent with momentum. Journal of Machine Learning Research, 25(22):1-56, 2024. htt
20068 html
Shai Shalev-Shwarzz Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. Journal of Machine Learning Research, 11990):263--266 2010.
Umut Şimşekli, Mert Gürbüizbalaban, Thanh Huy Nguyen, Gaël Richard, and Levent Sagun. On the tailed theory of stochastic gradient descent for deep neural networks. arXiv preprint /9/2. 2019.
Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis of stochastic gradient noise deep neural networks. International Conference on Machine Learning, pp. 5827-5837, 2019.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of over-parameterized shallow neural networks. IEEE Transactions on Information Theory, 65(2):742-76) 2018.
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Optimistic rates for learning with smooth
loss. arXiv preprint arXiv: 1009_3896 2010.
Ruoyu Sun and Zhi- Quan Luo. Guaranteed matrix completion via non-convex factorization. JEEE Transactions Information Theory, 52(11)663356677 2016.
13

---

Published as a conference paper at ICLR 2026
Iya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initial- ization and momentum in deep learning. In International conference on machine learning, pp-
1139-1147,201 2013.
Mariia Vladimirova, Jakob Verbeek, Pablo Mesejo, and Julyan Arbel. Understanding priors in bayesian neural networks at the unit level. In International Conference on Machine Learning, pp. 6458-6467, 2019.
Mariia Vladimirova, Stéphane Girard, Hien Nguyen, and Julyan Arbel. Sub-weibull distributions: Generalizing sub-gaussian and sub-exponential properties to heavier tailed distributions. Stat, (1):e318, 2020.
Martin Wainwright. High-dinenssonal statistics: A non-asymptotic viewpoint, volume 48. Cam- bridge University Press, 2019.
Hongjian Wang, Mert Gürbüzzalabann Lingjiong Zhu, Umut Şimşekli, and Murat A Erdogdu. Con- vergence rates of stochastic gradient descent under infinite noise variance. In Advances in Neural Information Processing Systems, 2021.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. In International Conference on Machine Learning, pp. 6677-6686, 2019.
Ashia C Wilson, Ben Recht, and Michael I Jordan. A Iyapumov analysis of accelerated methods in optimization. J. Mach. Learn. Res., 22: 121-11 2021.
Kam Chung Wong, Zifan Li, and Ambuj Tewari. Lasso guarantees for ß-mixing heavy-tailed time series. The Annals of Statistics, 48(2): 124-1142, 2020.
Yunbei Xu and Assaf Zeevi. Towards optimal problem dependent generalization error bounds in statistical learning theory. arXiv preprint arXiv:201 1.06/86 2020.
Yan Yan, Tianbao Yang, Zhe Li, Qihang Lin, and Yi Yang. A unified analysis of stochastic mo- mentum methods for deep learning. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pp. 2955-2961, 2018.
Tianbao Yang, Qihang Lin, and Zhe Li. Unified convergence analysis of stochastic momentum 0666000257. 2016.
methods for convex and non-convex optimization. arXiv preprint
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Rep- resentations, 2019.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? In Advances in Neural Information Processing Systems, 2020.
Lijun Zhang, Tianbao Yang, and Rong Jin. Empirical risk minimization for stochastic convex op- timization: O(1nn)- and O(1/n")-yype of risk bounds. In Conference on Learning Theory, pp- 1954-1979, 2017.
Fangyu Zou, Li Shen, Zequn Jie, Sun, and Wei Liu. Weighted adagrad with unified momentum. arXiv preprint arXiv: a 1808.00000000 03400, 2018
A NUMERICAL EXPERIMENTS
now present numerical experiments illustrating how the generalization bounds behave as tail parameter ( varies. Let (x(x) and (x) denote the risks built the training set S and the test set S'. respectively, where
Fs- (x)
Σ f(x;2,, ZES!
S
and | is the cardinality of S¹. We (x) empirical proxy for the population risk F(x).
14

---

Published as a conference paper at ICLR 2026
We consider six datasets available from the LIBSVM dataset: Heart, Fourclass, German, Australian, Diabetes, and Phishing (Chang & Lim 2011). For each dataset, we take 80 percents as the training dataset and leave the remaining 20 percents as the testing dataset. According to Algorithm T the momentum update can be written as
mi = 7-1-1 + 7 (x))) + (
VFs(x:)) -m
(m 7 (VF() ex),
where e; (x(x;; 2j. V (xx)) is the gradient noise. In each update of our experiments, for each coordinate we independently draw sample from a sub-Weibull distribution to model e, in Assumption 2.9 If every coordinate of e, is sub-Weibull, then |er is also sub- sub-Weibull; this follows from Lemma 3.4 of BBsttaanello et al. (202)) and part (c) of Proposition 2.1 of Kim et al. (2021b). Since we assume that the stochastic gradient an unbiased estimator of the exact gradient, we shift and scale the distribution in order to get random vector with zero mean and the variance equal 1. To examine the effect the tail parameter, we consider
(1/2,1,5),
We work with generalized linear model (((xxx) x)) for binary classification, where is the logistic link function {(s) = (1+--*)-- Our first experiment uses the Huber loss: f(x, z) = 2 [ x)) =.1, 0.1, = 0.9 and 1/: =
8) if [[(((( x)) - yl S r and =(((((xxx)) yl r) otherwise. We set r == 0.11- run the algorithm for given number of passes the data, repeat experiments 100 times, and report the average of results. The behavior the empirical quantity 7 Ei=1 F/V (xx)] as function of the number of passes is shown in Fig. [ The curves are consistent with the generalization bounds of Theorem 3.3 larger 0 (heavier tails) yield worse generalization behavior, and the case
0 = 5 performs noticeably worse, in line with the theoretical regime 0 > 1.
Our second experiment uses the squared loss: f(x, 2)
(e((x, x)) - y)² The corresponding
behavior of + Σグ= 5x,((x)))l versus the number of passes is reported in Fig. 2 Again, increas-
ing systematically leads worse generalization performance, which is in clear agreement with Theorem 3.3
nnos
2001
3.63
Samden
(a) Australian.
(b) Diabctes.
(c) Fourclass.
00003
4000
00055
50000
4002
0482
50000
0089
Huther
(d) Heart.
(c) German.
(1) Phishing.
Figure I: The generalization bound + Σt (V=F((x:)l versus the number of passes for different choices of 0 E 1,) and different datasets in the setting of huber loss.
B SUMMARY OF RESULTS
We compare the main results of this paper with the most relevant biggh-roobbbiity results of SGDM
in the literature in Table
We briefly explain the notation used in Table
Entry [1] corresponds to Li & Orabonal (200))
and entry [2] to Cutkoskk & Mehta (2021 The second result of [1] is derived for variant of
15

---

Published as a conference paper at ICLR 2026
133
0.30
330
63
12
120
120
6.0
6.66
(a) Australian.
(b) Diabetes.
(c) Fourclass.
6.04
230
290
Honbersl
Mundersl
(d) Heart.
(c) German.
(1) Phishing.
VV (xx versus the number of passes for different choices of 0 E 1,/2,1,5) and different datasets in the setting of square loss.
Figure 2:
The generalization bound + Σ
SGDM, namely delayed AdaGrad with momentum, whose stepsize does not depend on the current gradient. The assumption "0-order moment" means that the gradient satisfies f 1) G for some constant G and 0 (1,2). "S-S" denotes second-order smoothness assumption (Cutkosky & Mehta, 202T). Cutkosky & Mehta (2021) also derive two additional convergence bounds (Theorems 3 and therein) for the last iterate of SGDM under a warm-up learning-rate schedule and several other tricks. These bounds have rates similar to those reported for [2] in Table T but their assumptions are rather involved and hard to summarize concisely. so we omit them for brevity. "LN" stands for the low-noise condition F F(x") = (11nn), and the parameter 0 in the table refers to Assumption 2.9
The detailed comparisons between bounds and those of Li & Orabona (0200 and Cutkosky & Mehta (2021) have already been discussed the main text (see the corresponding remarks), so do not repeat them here. At glance, Table shows that our work provides collection of generalization bounds that are not available in the prior literature, together with convergence bounds that achieve strictly faster rates under comparable assumptions.
C PRELIMINARIES
This section collects preliminaries, including basic properties of the sub- Weibull distribution and several auxiliary lemmas used in the proofs.
C.I SUB- WEIBULL DISTRIBUTION
Define the Lp norm of a random variable X by || = (/) for any p 2 1. A sub-Weibull random variable (denoted ~ subW (0, K)) can characterized in several equivalent ways.
Proposition C.1 ((Vladimirova et al. 2020: Bastianello et al. 2021 Given 0 0, the following properties are equivalent:
3 0 such that P([X) 2 t) 2xxp (- (-(//K,) Vt 0:
3k2 > 0 such that || S Kzhe, Ak 2 1;
3K3 0 such that Elexp (110 & exp (19)))1/9), AA E (0, 1/KK))));
16

---

Published as a conference paper at ICLR 2026
Table 1: Summary of Results.
ASSUMPTION
[1]
2.1
[Fs(x:]]
$ Σ>
[Fs(x:))
max 1
d (1va)
Pax (276)
(1,2)
$ + [x.)).)]
[2]
0-ORDER MOMENT @ (1,2)
S.S.
EE [x.)]
EEL
V1F(xx))1
loptt (-4) log vT (1 (o)
2.1
2.5
A
+E
vX tnel-ker// Logit Legit//// /e1 tig /rlllngy
2.1
2.3
8
+E
VFF(xx))
2.1
0
+E
[/
((2))* 9 kog (O8()) log (t) o logt log (2))))
2.1 2.5
0
C (1
[[x))]))
OURS
2.1 2.5
8>1
+E
[Vx(())]
o (1)) (log( @ log ( (4) log
( log (H1)
2.1
Fs(xr+:) Fs(x(8))
2.1
2.5
2.7
(5.)
Fs(xr+1) Fs(x(8))
200-30
2.1
2.5
2.7
Fs(xr+:) Fs(x(8))
Jox
(2316) log
2.1
2.7
F(xra1) F(x")
O aa log" log
2.1
2.5
(1.1)
F(xr+1) F(x")
desosfe ( log
1 log
F(xr+1) F(x))
log (2 log
200-33 1ee
log
F(xr+1) F(x")
F(xr+1) F(x')
log
4) 1ogd
314
F(Xr+1) F(x")
L.N.
F(xr+1) F(x")
(37 28
10+ 2 blae
2.1 2.5
2.3
LN. (
F(xr.1) F(x")
IN.0>1
F(xr+1) F(x")
log
(n/40) log H
17

---

Published as a conference paper at ICLR 2026
= > 0 such that E eexp ((IXI/Ka)V)) 2.
The parameters K1, K2, K3, K4 differ each by constant that only depends on 0.
We list several concentration inequalities for sums and martingales with aab-Weibulll increments.
Lemma C.2 (Vladimirova et al., 2020, Wong et al.] 2020; Madden et al. 2024)). Suppose X1,... Xn are sub- sub-Weibull()) random variables with respective parameters K - Kn. Then, for all t 2 0,
)
1/0
1
Σ Xi 21 2
S 2exp
= K, >i=
where g(0) (4e)² for 0 S and g(0) 2(2e0)) for 0 2 1.
The next two lemmas provide sub- Weibull analogues of martingale concentration bounds.
Lemma C.3 (Theorem 2 in (Li 2021); see also (Fan & Giraudo 2019)). Let 0 E (0, o)) be given.
Assume that ( = 1, 1.... Nj is sequence of & -valuee martingale differences with respect to
filtration F,, Lee [-x1 O, and it satisfies the following weak exponential -ype tail condition:
for some 0 > 0 and all L, .... N we have for some scalar 0 < K₁. E exp
x
Assume that K2 < 0o for each i = I,... N. Then for an arbitrary 2 1 and t > 0.
128
12 K?
t² 64
max nSN
Σ X
2 1
<4
3 (30)20
exp
12
G 1= K?
Lemma C.4 (Sub-Weibull Freedman Inequality; Proposition 11 in (Madden et al. (R, (Fi), P) be filtered probability space. Let (E:) and (Ki) be adapted (Fi). then for all i E [n). assume K₁-1 2 0,
2024 ). Let
Let E N.
= 0, and
E exp ((&/// (1)
[F-1] 22
where 0 1/2. If0 > 1/2, assume there exists (m4) such that Ki- S mi
If = 1/2, let 2. Then for all 3 2 O, and > O, and X E [0, 2.]]
{
ak? S a Σ E + s8) S expl( Ax 212B).
P U
Σ
x and Σ
(2)
kE(n)
1=1
i=1
for all x. B, 1220 0,
b Σ & 2 x and Σ aak S o0) s sexp (-xe+ 3
X2
P
U
kE/n|
If 0 E (1.
let = (40)20 e² and = (. For all k O, and a 2 b maxxeg]n Mi and
E
[0, 1.
Σ E x and Σ ak? Sa Σ & (++) 18) s <epp(- Ax + -2x23). (3)
kE[n]
for all x, 3 2 O, and A E (0. bmaxec(()
X2 S 88) exp (-xx
P
U kEju]
E&
Ezz and Σ
ak?
33
18

---

Published as a conference paper at ICLR 2026
If 0 > 1, let ā E (0,1), a (220+1 2) + 11 136++1
and 2loo"~t(n/0 For all
3
x, 3 2 0, and a 2 b ma my, and E [0. 2a.
U
Σ Ee and Σ aK S
Σ E. +2++
83) s exp(--xx -Ax -2223 + 28. (4)
KE(N)
and all z, B 2 O, and AE E
0. maxxe||) m
& E I and Eaki_ S {8)) S eexp
X2 (Ax + 2 + 28.
U AE(n]
Σ
i=1
C.2 AUXILIARY LEMMAS
Lemma C.5 (Leei & Tang 2021 Let e be the base of the natural logarithm. There holds the following elementary inequalities.
(a) If (0, then Ei= k- S st /(1 0):
(b) If 1, then Eim k-0 log(et):
(c) 0 > 1, then Ei=1 k- 8-1
(d) E kt log(t +1-
Lemma C.6 (LL & Orabona 2020 For any T 2 1 and sequences (as) and (bt), it holds that
T
T
T-1
Qt
b
0 and Σ
at
Σ
d:.
i=t+1
Lemma C.7. Let ) denote the inner product. If f is L-smooth, then the following standard properties hold (Nesterov) 2014 Ward et al.) 2019): for any 2 E 2 and every X1, X2:
[(x;==) - f(x2;=) S (x1 X2, 4 2)) + 2 x||x1 x2l1?
(2L) | < (x: =) - inf fx;
The next two lemmas uniform-connvrgeent results that control the gap between the population gradient F and the empirical gradient V.s: they are key tools in our generalization analysis.
Lemma C.8 (Corollary
(Lei & Tang, 202I)). Denoted by Bg BO,, R). Let (0, 1) and S = {21, ..y 2n) I be set of i.i.d. samples. Suppose Assumption 2.7 holds. Then with probability at least 1 we have
sup |VF(() - VFs(x)] S (LR+B) B)
2 2 48c 48e 220gg 2 + dloog(e)) + 2 2lo8((
Vn.
xe BR
where B = supzez [V)(0=)) and L is the smoothness constant.
Lemma C.9 (Lemma B.4 in (Li & Liu 2022); (Xu & Zeevi 2020)). Suppose Assumptions 2. and
2.3
hold, and assume that the population risk F satisfies the PL-type inequality F(x) F(x') S
V F(x))] for some μ > 0. nf 2 eL? (d+Hog) 2l
then, for all x E X C B(x", R) and
2μ
any 8 > O, with probability at least - 6
2B. log(4/6)
SE f log (4/8)
VF - VFs(x)] < [VF((x)1l +
where is absolute constant, and where B. the constant from Assumption 2.3
19

---

Published as a conference paper at ICLR 2026
D PROOF OF MAIN RESULTS
D.1 PROOF OF THEOREM 3.1
Proof. By Assumption 2.1 have
Fx(X (x(
S(x++1 X1, X4, (x(()))) + 2 T||x(+1- - xx11 (m,, VFs(x.)) + + m,l? (5)
We first control the term - (m,, VFs(x))). We have
(mg (xs()))
7 1, Vl'((x))) - (T) V VFs(xx) - (Fs(x.)) (no Vf(x; VFs(x))
= (m,-1, (Fs((x:11) +
S (m,-1, (Fs( VF /
Vx)(x))]
S 1,,,1, (xs(x, 1)) + //|[m:-1| (m) V /
zj.); VFs(x:)),
(6)
where the last inequality uses L-smoothness of Fs and the update x X
-m.-1. By
recurrence and using mg = 0. we derive
mm VFs(x))) S L
Vf(x; 2)) VFs(x.))
Taking summation from / = 1 to = T yields
Fs((T+1) - (s((x)
1
m, 1|?
(x)
|m: 12
(8)
2
i=1
1=1
By Lemma
C.6
we have
T
7
L
T
m: 1
ST
L
m
2
7
S
I
m: 11
m.
11
1
Furthermore, using Lemma C.6 we have
V(xx (xs()))
T
( - - VFs(x)))
mm (VFs(x)), VFs(x.))
1=1
s=1
T
(Vf(x;z)) - - (F
(VFF(())) VFs(x.)) Σ
( (Vf(x; -VF(x))) VFF(())),
7
T
T-111
(Vf(x;2,, - VFs(x,)), FFs(x:))
(10)
Plugging
(9) and 10
into
we obtain
T
L T
V | < Fs(x.) - Fs(xs) +
|mmll m
1 1- 7
T-141
1
T
(m (Vf(x 23.) (Fs(xx))) (Fs(
Σ
m ||
(11)
1-7
1
20

---

Published as a conference paper at ICLR 2026
It is clear that
E 1 TT- (X(i (x)(()))), (x'((x:)) 0,
implying that it is martingale difference sequence (MDS). We thus use Lemma to bound Specifically, we set &t 1--"-111 (m) ( V (xx; =j,) (xs()))), (x.)). K
1-y
T-++1 K| V 3 = 0, 2n and æ 2a (1)))
If 0 2. for all O, we have the following inequality with probability 1-6
T
T-1
(V
VFs(x))), VFs(xx))
ak
T
T-111
$ 2a log(116))
+
1/1
[Fs(x)))
1-7
t=1
aK²
- 7T
s 2a log(0(100)
)²
M:
V (Fs
If 0 E (g. 1].
according to Assumption have the following inequality with probability 1 8
2.5 we set m = 1-2 KG. Then for all 2 - KG,
1- ++1
$2a 12glog(1/)) aK?
1- )
th (Fs(x)))1
7
1-y" KG and d 5. Then, for all 2 1 كساي" 1-7 KG, we have the following inequality with probability 36
If > 1, according Assumption
2.5
m,
1-
(ne ( (Fs(x)))
ak² 1- T
T 2
22x loollog(//01
-
Then, we control the term
Σ T
|m,l?
t=1
M (1-7) 11t V fxei Rgi) 2
m
(2llm-- 1| + (1 ->)
(1->))
1/. fx 23.)
- 7
T
1/c V f 231) ||
7||mm 2 Σ (1 - 1)
- y
t=1
1/ V ( Fzi) ||, Σ (1- >)
>||mm||
||2
1 y
1=1
t=1
where the first inequality holds due to the Jensen's inequality and the second equality follows from |mo]| 0. Thus, we have
T
1
<
7)2 Im Vx(x V 23.111
(12)
1=1 (1
21

---

Published as a conference paper at ICLR 2026
This inequality implies that
T
2 T
T Σ 1=1
2
m: 12 -
(f(x)))) - Vx,(( +
(1-7)
--)
(1-
Since [x(33))))
V
(x,)) is sub-Weibull random variable, we have
#
M/i
[x: 23.)
FFs F
E
exp
2
n/ K2
which means that ni V fx,; 2,,) get the following inequality with probability 1 - 8
(x,))1 subW(28, K2). 1)²).
Applying Lemma C.2 we
Σ
2 "1 f((x22)))) VFs(xx)11 S (1-
(1 -)2 K2 g(2)) log 2og20(())) (2/5) Σ m
2
Then, we plug the bound of E
1-7 (ne (V - vFs(x))), VFs(x:)) and the
bound of Σ 1=1 |mell into we obtain
T
2 T
Σ
Me (Fs(sx)))
& Fs(x)) Fs(x(S)) +
+ 2
Σ
2
FF(x))l
1 1-7
(1 7)
ak² 1 --
T
+ 2a log(1/8)))+
( 1 7
)
V Fs 12
t=1
(1-x+
L
+
1 1.)
2 (1 7)2
T.
2
K2 ((0) log 20 (2/5)
Σ
2 7
implying that
nh (1- (1- +
1 n 2 (1
T, 1 1.)
2
7)2
T
ak2
(
1 1-
1 -
12111 |VFF((x)]2
1=1
T
$ FF((x1) - Fs(xs) + 2a log(1/0) +
L
+ 2
1
L)
2
K2 ((²))(2) log 2 (2/6) Σ n/
1-
(1-
When c I (1-1)² 1 -
13L-by then
1 +
(1- + 21)
1
2
(1 - 7)2 S Vt.
(13)
4'
When ak² 1--g pm1 < 1 then
z.
4 1- x
2 aakk?
1 1-7
Thus, a 2 4( - maak = 4( 411-2=)-2 ceak2 and m S 1 (1-7))²
we derive that
8 1 +
T
m VFs(x)]11
<2(Fs(x1)) Fs((()))) + 4alog(1/8) + 2(
L
+ L)
2 K2 K2KKgg200 ((2) log 20 (2/8)
Σ n
1-7
(1 21-
1=1
22

---

Published as a conference paper at ICLR 2026
Putting the previous bounds together. Hence, if 0
1. taking a 4( 1(" ) Pmak?
8( - pm K2, with probability 26, we have
1 1-1 --
Σ ne VFs(x;)) =((F((() - Fs(x(S))) + 32(
n 22 log(1/6)
1 y-7
T Σ
T 1 L)
4
+ ( 7 2
+
K²
m/c
(1 11-7) 7)2
If 2 < 2 1, taking max { 1-
1-9 KG, 4( 1 j'm makk]
maax (40) --
20 e2 222) ). with probability 1 - 26, we have I-7 KG, 4( 1- )m (40)
Ne [x:)) - (x)s - Fs((((S))
+ max (40))e²
--
KG, 4( 1 1-
7"
x2x2
10g( )
1 1-7
1
T
+ ( 1-7
I.
+ I.)
1
K² (2)( log (2/8)
Σ np
2
(1 - 7)
If 0 > taking = max
2b- KG, 4( |1-ي" )2 /mak2) j. that
1-7
1 7T (T (2log"
KG, 4( 1 1-7
)m +2)I(20+11) 238 +1)
max 22
k 5
1 1- 7
1 1-
Thus, with probability 1 48, we have
Σ (x:))1111 2((ss(x)) Fs(((()))
(
L
2
1 L))
K2 k2)(20) log (00g22((22)) (2/6) Σ o/ (1 - 7)2
7
1 --
+ 4 llog(1/)) max 2 log -- (TT/8)
1 1-7 KG,
T (m(2 + 220 + 1) + 230 1) )k²
Note that the dependence on confidence parameter 1/5 in above bounds is logarithmic. One can replace 8 to 8/2 or 0/4. Through this simple transformation, we have the following results: (1.) if A = 1, under Assumptions 2.1 and 2.9 with probability - 5, we have
1 VT
[Fs(x))11
= o nell [
log log((/))
2 Σ
m
T
cVT
0
log log(1/8)
(14)
(2.) if 1 < 0 < 1, under Assumptions
2.1
2.5 and 2.9 with probability 1 - 6, we have
2
1 T
T
<
nh
[VFssx)))
= O
log 20 (1/8)
Σ
n
2
T
CVT
VT
1
log 20
(1/5) log log
(15)
23

---

Published as a conference paper at ICLR 2026
(3.) if 1, under Assumptions
2.1
2.5 and 2.9
with probability 1 - 6, we have
(Fs(x,) 1|
1/s
(x,)(1
T
cVT
log (T/0) log(1/0) log 20 (1/6)
- 111
-
VT
log" log"- (TT6) log(1/0)
log 29 (1/8) log T
=0
(16)
VT
where the bound of Σt= th follows from Lemma
C.5
The proof complete.
D.2 PROOF OF THEOREM 3.3
Proof. The proof is divided into three parts.
(1.) In the first part, we prove the bound of ||x,|| ||xe]] characterizes the bound of B(0, R), i.e. at iterate I, = Rg = ||xel. because X, traverses over ball with an increasing radius increases. Therefore one should apply Lemma C.8 with an increasing R.
From the update Xx+11
Mr by summation and using m = O, we get X -E 2i=1 Using m, = --,-- 1 + 13: V f(xx;) aj,) and recurrence, we have
m,
ms (x(xi
According to Lemma
C.6. this gives that
- xtitt1 y-9 n [((;))))))
X141
k ni Vf(xxi
Σ
(17)
k=1
Thus, we have
|x+1|| || = 1-9- 1=1
VFS(x)))
Σ
it mm v (xx)
i=1
(18)
Let's consider the first term
clear that [xs(xx))] = O, which means that it is MDS. Moreover, since [V VFs II subW(B, we have
Ei=(( (1 - ) VFs(x:))
E, [[1 - (n
(nm(1- (V (V((x;))) - VFss())I
$1
E
exp
2.
(1 K)
Then, we can apply Lemma C.3 to derive the following inequality
P
m
VFs(xx))
2x
1
128K
7
x²a
20+1
(3
1=
exp
x.2
64 TT) Σin
24

---

Published as a conference paper at ICLR 2026
{-
Setting the term 4 exp
(I12(1->")) Eim 1/
TT
equal to 6, we get 2 = 8 log (0+ (4)
+ 2 1 x² Thus, with probability - -30-
8(30) a0
6, we have
log Tog---1
Σ i=1
m (Vf(Waz))) -Fs(w:))
S <8log 18+ (
()
Σ n
1stsT
(19)
Since 2 1/2 and 8 E (0, 1), we have log log $ > 1. Thus, 19 means that with probability 1 1-36 8(30)20 20 8, we have
20+1
T
Σ (1
mi (V VFFs
4 [( - -Z) S 8logg (
max ISEST
Now, with probability
6, we can derive
Σ
mo (V FFs(w:))
max 1
[(33 (1(3-8(36)) -8(30)20) 20)
T 7/
<8 <8log (0+5)
K(1 - 7
= O())
(20)
8
E (1 - - m Fx5ss;) //. we have
For the second term
m / /|
5
(1 - mm)
i=1
V Fs (x:)1²).
(21)
where the first inequality follows form the Schwarz's inequality, and where the second inequality follows from the fact that < 7 1, m/ and (x:))( 2 O. For the sake of the presenta- tion. we introduce notation (0 log"-1 (TT/)) 5) log (1/8) where Iø>1 an indication function. Thus with probability - 5 we have the following inequality uniformly for all t. = 1,... T
Σ (1 x )x
m VFs((()))11
7
i=1
( 0 0 A(0.T.0)) + 20
(1/8)
2
(22)
where the last equation follows from the results of 14
15 and (6)
Plugging 200 (2 and (22 into (8) we have the following inequality uniformly for all t = I,...? T
with probability at least
28
1/2
T
(())
t
[|x+1|| [8e+1l==00 =
log (0+ ( [1 - 77 (000
(OA(0,T,)))) 29 (1(6) Σ 112)
mh [=l
(23)
00 log (0+ 1)) 1 (1(1---)) "
log²r) b
+ +)
(o (1/6)logt))
50 (A (0, T) + log 10+ (0 ( m
(24)
where the second equation follows from Lemma
25

---

Published as a conference paper at ICLR 2026
(2.) In the second part. prove the bound of maxigisT VF(x)) VFs(x))] According to with probability 5 we have
Lemma C.8
[VF((x)) VFs(x))] 15tST
max
LRT + B)
2+ 2 48 48ev2(1ogg 2 + dlog(33)) + 2 log( 1 (3)
Vn
[L] x + B)
+ 2 48e 48ev2(log 2 d3log(3e)) + V 2 loog {)
(25)
Vn
Plugging (24) into 25
with probability 36 have the following inequality uniformly for all
7
max ISET
Fxx)
(xs(x))11 -
LO ( 0, T, + log (0+ (t) T)) + B
2 2/ 48e 2 2 + dlog(3ee) +
2 log
Vn
which means that we have the following inequality uniformly for all = 1....T with probability 1 --0 5
max 18ST
VF(x)) Fxx(x))11
T (AO,,,, T) + log (20 12 ( log
(b)
(d+ (d+ tog(
(26)
n
(3.) In the third part, we prove the bound of T EL [Vx)2 Firstly, we can derive the follow- ing inequality with probability 28
nc VF(x))1
M/ [x)))(() (xs(x))1 Σ Mel (x)))xl
T
2
1/t max IS1TT
VF VFs(X1)11 2 Σ 1e V
1=1
1
T (A(O, T,8) log (20+1) (2)
(d + log (
2
1=1
+
0
A (0, (,0) + log 20 (1/5) log T).
where the last inequality follows from Therefore, we have
26 and the results of 14). 15 and
[x(x))1 CVT
Th (x:)111
(T T, + Log (20+1)
log T
x (d (a+ (og(t)
n
A(0,T,0) log" 28 (1/8) log
+
VT
Taking T x 2, we have the following inequality with probability 1 - 25
1
|2 =0 ((,)) (1og( n log (20+2)
(())(((ss)))
log(20+2) (2) (00 n d log(1/8))
T
26

---

Published as a conference paper at ICLR 2026
which means with probability at least 1 - 8 we have
T
[F(x))]
-0 (())) log( n j
$
log
1 + A00, 1) (20+2)
log log(1/
T
((m)
d [188( ( log
(2042)
1 + log 8- (m/dd) log (1/8)lo21)
The proof is complete.
D.3 PROOF OF THEOREM 3.5
Proof. The proof of Theorem 3.5 relatively complex and is divided into two parts.
(1.) the first part, we prove the bound of ||x characterizing the bound of B(0, R). i...
(1-7)² + Since
iterate 1 1, R Re+1 ||++ Recall that in (13), need Mp
8( 8 12)
12L-4L7 we have Th (1-))
n [(S)(t+()) when to
+ Thus, we
p(S1I-7)3
23 to bound [|x++]||: |l. According unformly for all t = I,...
23
we have the following inequality with probability 1
|x++1| 0
log (0g)))
11
7h
(0,T + log logo (1/6)
Σ
t=1
i=1
1=1
00 (110g(0+3) 2)
$ (0, T) 5)) log² T
(27)
where A(0, T, 5) = log (TT)) log( (1g(1 (0g(1/6)llg 10) and where the last inequality follows from The (SS(++t)) with to 2 and Lemma C.5
(
(2.) In the second part, we prove the bound of Fs(xr+1) - Fs(x(S)). It is clear that
Fs(xe-1) - Fx(x))
1
S(x111 - x., (Fs(x:)) +
+ [||x(+1 - x
S <-7(m,-1, (x + Ty||mm- (m
/ V)) 1
- -
X k3.)) VFs (x,)),,, (Ps(x))) = - --7( V Px -x, )) + / V
1 - V 2| + m|
where the second inequality follows from We can derive that
1 2 nh (xx(x)l + (s(x++1) (x(
7 VFs(x Ty|[mm-1||1 (1) (((332)))))) VFs(x;), VFs(x:))
2 n1 VF X 2 411m
Since (S)(+t))) it implies that
1
2 Tc (FF(())) + Fs(x(41) Fs(xs)
2
5(1
1. 1 (Fs(xx) - Rs(xs)) -7 (m VFs(xx + Ly|[m--111
(1 V[(ex VFs(x.), VFs(x.)) + [mm.11
27

---

Published as a conference paper at ICLR 2026
Multiplying both sides by (t + to)(t + to 1), we get
(t + tn - 1)
2μ((S |VFs(x))1 + (t to + to -
+ - S 11 11/00m111mmm-- ( +4++ to - ( 11)1)//lmm-- 11
+ +t++ + 1 /||m,||
+ (1+ 10 10 (x(s(x)) (x(xs))
- (t+ - 1000-11m- (V((xiz)z)) (Is(xx), VFs(x)))
Taking a summation from f = 1 to = T. we derive that
(L 10 - 1)
to 1)(Fs(xr+1) - Fs(xs))
(p((s)
Σ
> (t+ to) tto 1)4 1
T
Σ (++ (t) to -1), L |||mi||²
1=1
+ (to 1)(to - (x)()((x)) - Fx(xs))
T
Σ
(t (0) to 1)m (V((((())))))) (Fs(()),VPs(
t=1
Since m. = 0, we get
T to 1) [FFs(x))] + (T + to 1)(Fs(X(+)) Fs(xs))
S)((S)
T-1
+ to 1 (1 + Σ
+ to + 1)(t + Ly|mml
1=1
T
(1 + to) + to - -1) T.|mm.|?
E
+ (lo - 1)((o - (F)((x)) - Fs()s)
Σ (1 + (o)(( + la 1)m (V/(x,))))))) - VFs(x.), VFs(x:))
(28)
We first bound the term ET- to + 1)(t + to)]|mml Note that from the Jensen's inequality,
we have
1 1- +
m = |/m
1 m v V (xx;) s 1 + 1-7 Il V fxx:s2,,))1
By recurrence, it gives that
7
m,
2
11 V
(x
fxx;
7
i=1
28

---

Published as a conference paper at ICLR 2026
Thus, have
t t + 1)(t to)mmm 1
(1+ 40 + +1)(1+ 40)
Σ
1/ V (x
1=1
117 f 23 I11
(i + tu + +
(29)
Considering
(1 + l0 + +1( + 10)7' we have
(i to + +1)(+++++ to)
(i+10- - -)i + di
T-1
(i+ to -)
T-
T-1
In (1 ( to + 1)
-
(t to + 1)yAdi
i=t
=-
i=--1 - -fr T-1
In (i to + 1)²
-2
(i + to + 1)
In y
Solving the above integral, and since In y < O, we get
T-1
Σ (i+ + +)
S 2
2' In S (C,))'t+ to + +
+ to + 1)3 2 In
(t to
(30)
ln
where
C.
2 In
ing. which constant only depend on y. Thus, according (9). we
3
have
T-1
T-1
(t + to + 1)2 (C₂)
Σ (t + to + +1((t + to)
m 2 <
Σ
(1 (1 |1 ff(x
(Cz)
T-1
(t + to + 1)2
| (V
71-7)u(S)2 1=1
(1 + 1o)2
And since (f+te)²
(b+t++1)2
= (1+ + ztto
1
)2 < 4, then we have
T
to + 1)( + 4o) m. ?
(4C,)
5 (1 S))
V 12
(8C,)
< (1 (S12
- Vxx(x)) -V
)-
27
Since [V ) - V Fs(:))l ~ subW (0, K), we get EE exp
< 2.
K
According to Lemma
C.2
we get the following inequality with probability least 1 -
(xx;2,))
VFs(x))) S (T 1)K2 9(20) log 20
29

---

Published as a conference paper at ICLR 2026
Thus, with probability at least 6, we have
(8C,)
to + +) to) 1| - (1 ())
(T' 9(0) log 20 (2/0)
(8C,)
t=1 (1 - (S)) /Fs((x))1
(31)
Similarly, with probability at least 1 - 8, we can derive
I
Σ 10 - m|)
1=1
(8C.))
T (8C,) (S)
$ (11 (5)2
T TK2 ((0) log 20 (2/0) +
V Fxxxx)11
t=1
We then bound- Et=r(t to 11m ( Recall that from 7 we know
Σ (m,, (xs((x)) S L t-1
:- m 1
VFF(x)).
Since mo 0, we have
(1+ 11
Σ (l (1+ + +) (F)())))))
[-1
(t+ + +)(
+ ()) Σ
, - m
Σ (t + to + tt(
Σ
1- (m4 (
[x:: V(s(x)
==1
(++ to +t) Σ
11 m ||
T-1
(t t + 1)((t+ + to)
yd 1- (Fs(x))
T-1
||mm|| ||
Σ 1=t
7 + to + 1) tt)
(mp V fxxx ). ) (xs(x;)) Σ (i to + 1)(i+ to)?
T-1
||m,|1 1|22
Σ
1=t
T-1
(1 - vxs(x))), (Fs(
Σ
(i + lo + 1)(++
(. vFs(x))
Σ
+ to + l) +
i=1
30

---

Published as a conference paper at ICLR 2026
where the second equation holds by using Lemma C.6
With a similar analysis to (1.. p. it is clear that with probability 1
T-1
m
Σ
ri + +)((++++ + to) S LC,,
|m/ [t to + 1)
(8C,)
(8C,)
SL(C,) (1 (1-)) (T 1) g(0)) log 28 (2/6) + Σ I(C,) (1 (1=)) /Vss(x))1?
And we also have
T-1
(FF)))))) Σ
(i + to + +)(
7(t - to + 1) + to VF)(.))
2=
Σ (e+ 1o + +1)(t + Vo (Fs(x)))
(1+ 10 + + 1)
Thus, we have
(o) - V
Y ( (Fs(x)))
Σ (i + to 1)(i + +to)
(8C₂)
(t to + +)((t + (a)%+ |Vs(xxx + I(C,)
(1 1 ()}) (T -
(2/0)
(8C,)
I(Cr)) (1 1 (S-) [x)s(x
We now consider the term - T-1 x (m - V VFs(x)
Eist (i +
1=1
VFs() Σ +1) () 4o) Denoted by & = - )
fo) We know that E,,S: = (,, -
(x)(x,)), VFs
(i + to +
1)(+tto)" = O. implying that it is a martingale difference sequence. We use Lemma this term.
C.4 to bound
From 30p. is clear that - (Fs(x:)) (c+t++)))))t (E,)
+ to + 1)² n/ Vf(x V/sx
We set
K,-1= = (t + + + = -C 1)² (t)((t+ K VFs
We also set 3 = 0, A = 1. and r = 2a log 1/8). For brevity, we denote E = 2C, (t + to + Za.
1)x(S)-1K and E = (T, + + (S) Moreover, according to the smoothness as- sumption, we know [|V < (L|x|| B).
If 0 = 2, for all a > 0, we have the following inequality with probability 1- 1
T-1
Σ
E( to + 1)( +o)?
1=
52alog(1/0) +
= V (x
31

---

Published as a conference paper at ICLR 2026
If 0 1, set my [||||,
|| + B). Then for all a 2 (Er(L| + B), have the
following inequality with probability 1-6
T-1
(ne V (x,())))
Σ
(i + to 1)(i to)
T
120log (100)
Σ
2 V (x,)11
I > 1, we set m, |[ + B) and 5 = 8. Then, for all a 2 (E + B), we have the
following inequality with probability 35
T-1
(xxix (Ps(x)))
Σ
(i to + +)(
220log(1100
Σ
We now consider the last term -1 (1 (1) VFs(x)) (x.)).) With a similar analysis, we set & (1: + (o) + lo 1)) (x)() (x,)) and
K = + (t + to - 1)m, K (Vs = (( 1) VFs(x)
We also set f = 0, - and x = 2a log 16)). According to the smoothness assumption, we know (x,)) I (L||<e] B).
If ( = 2'
for all a > 0, we have the following inequality with probability at least 1 -
T
Σ
- 1) - VFs(x;),
ak²
12a
M(S)za Σ (t+ -o 1))1
If 2 < < 1, we set my = p(S)) ( tu - [L|([l + B). Then for all a 2 bu( '(T +
to 1))K(( x B), we have the following inequality with probability at least 1 8
T
Σ
tt - V) - (x))))), (F((x)
1=1
22x log(1)/ +
1
p(S)2a
If > 1, we set my = (t B) and 5. Then, for all 2 hu(()) IT+
to 1L |I B), we have the following inequality with probabilityy least 1 - 35
Σ (t+ + tt) - ()xx))(())))) - VFs(x))
1=1
aK? p(S)Pa
52a loglog(1/8))
(t+ + to - 1)
1=1
32

---

Published as a conference paper at ICLR 2026
Finally, combining with these terms, we derive
(1+ 10 1)
ak?
T
[Vss(x))1
10 - (1113x1111
2p((5)
MSSPa
L (8C,)
[x)(()))1
T-1
T-1 (1 - ()) [VF((x))1 + Σ
(8C.)
Σ
tt+ + +)(++++++ tomel (
(8C,)
(C,)
(1- VFs(x))]1
V + 40) + ()(F((x++))- - Fs(((S))
1=1
<In (1 (1-)) (T - 1)33)) (2/8) + (8C,)
(SC,)
2 (1 - ()) TK TK2)(20)
9(2)) (222200))g))) log (2/8)
(8C,)
+ (T,,, (1 (1-) (T 1)K2 9(2)))((0))o)))) log (2/0) + (to - () - 2)(Fs( F's (x())
+ 2a log (1/6) + 22a log(1/6).
(32)
We want
(1+ 40 -1) 1)
aK²
(t - 1) L (8C,)
2 2) 20 0
(5( u(s)2a
and
(t + to + +1
(8C,) - Lr((C, (1 (1-))
(8C+)
7 -=² 2
m(S)
(1-7)u(S))
Thus, assume that to satisfies the following conditions
(to 1)
2 L (8C,)
S))
2 (1 (1)))
and
(to 1) p(8)
(8C,)
(8C,)
L (1 (S) + LL((
(1 (1-))u(S)²
which means that
(8C,)L + 1;
40 2 (1 ())))s
and
8C, + [n((,))
to 2
1.
(1 (1- (S)
Thus, we can further derive that a 2 (11
ak² (1420
and (1-))"1(07²
(60.))
(( -K)²
(1 La (1 ()133 Lx(C,), (1 =)3)() (())
(8C5)
(825)
When 1 the above lower bounds of a are: a 2 0 2 (1+ttg 1)3
2,
(80.)
2x(3)
[18)
7a(2C, ()+
and > 0, which implies that we should choose
Lo (805)
7 Lg(C,) (804)
0 (T).
33

---

Published as a conference paper at ICLR 2026
When 1 < < 1, the above lower bounds of a are: a
ak (1-to 11+ 1]
2
(E+fu-1) 2p(3)
(8(
- (1-3)
[e+tn+3)) ya(2C- (t++aa ( K)²
( + B), and (5) ( to
M(8) (1-5) Lx(( (8C
(8C,)
( + B), which implies that we should choose O (Tlo (0+ (++ log T)
ak 2 1)2
When 0 1, the above lower bounds of a are:
10:40 2p(3)
(u=)) + B), and a 2 bp(55- +
(t (1 (a)
2 teti bn (B02))
2
2215)² Lo(C,) (t 1F-11
(665)
to (L X + B), which implies that we should choose
a= o (
T
log
(og 2))))))))) + log " (I/6) log (og-)()))))) log r
Note that the bound of ||xT|| comes from 27
Thus, derive that
(T + (T + 40 1)(FFs Fs(()))))
(8C,)
L (8C,)
<by (1 ()))) (T 1)K
(2/0) (T))) log
(1 (1 (S)) TK3 (0 (2/6)
+ [y(C,) (8C.)
(S) (T 1)K2 ((20) log 20 (2/5)
+ (to - 1)( 2)(Fs(x)) Fs(x(S))) +o + 72a log(1/5).
Putting the previous bounds together.
If 0 with probability 1 66, we have
(log(1 (og(1/))
Fs(XT+1) - Fs(())))
T
If < < 1, with probability 1 7ō, have
log (0+ (og
log (2)
Fs(XT+1) - FF((x(S) = o
T
If 0 > 1, with probability 1 106, we have
Fs(xT+1) Fs(x(S)) = o log (0+ 11
(0,
log T
log 8-1 1 1- (0g(())) (
T
The above bounds mean that with probability
- 8, there holds
O
log(1/8)
if
A=
Fs(XT41) - F(((()))
o
log + $
log
t
if
0 E (2, 1],
(33)
(0
log
310-1)
(T/6) log
if 0> 1.
The proof is complete.
D.4 PROOF OF THEOREM 3.7
Proof. Recall Assumption 2.7 (Polyak-Lojasiewicz condition), conditioon which gives
F(x1+1) - -((") < 1 [ <
1
-VP(x+)+))) + [VVFg(x++\)l3)
Ap
2p
(34)
34

---

Published as a conference paper at ICLR 2026
From 27 and Lemma
C.8
with probability 1 - 8 we have
( log ||T+1
VP V ([(((T+1)] o
n
d (d+ log (og.20-1( A0,, 81) log logT)
(35)
n
From the smoothness property in Lemma
C.7 and the convergence bound in 33 with probability
1 6, there holds
1)]1
< (FL)(Fs( - Fs(x(5)))
log(1/6)
0 2
log 2) log 2
if 0 0E (1.
(36)
log
(4) log
30-
2
(7)5) 1og)
if 0>1
Plugging 35 and 36) into 34). we derive that with probability 26, there holds: (1.) if
2
F(xT+1) F(x)) = (1/()/)) + log ()) log² 8 log log
T
(2. E (t. 1).
log (log(0+ (0+ (1)) log² T
d + log(t)
log 20+ log
F(XT+1) - F(x)) =
+
T
if) F(xT+1) - F(x')
=0( log 10- (0- log
(T/8)
+ log(?) (1og (10g(20+1) + log T)
+
T
We choose n, then with probability least there holds
d+log()) log² log if 0= 1
o
(xx44)=F(x') =
o
d+loR(#) log (20+1) ( log
if 0 ( 1],
dtlogit) log (20+
11 (20+ log 3(0-1)
(4) 0>1. 1.
The proof is complete.
D.5 PROOF OF THBOREM 3.9
Proof. By Lemma with probability we have
[VF(wr+1) VFs(w++1)1
|VFs + 1 +
B. log(4/8)
2
xx ;2)
log log (4/5))
2/
B² log 2 (4/8)
E | Vf(x" 2 || log (4/0) 2
<4 VFs +
+ n²
n²
From the smoothness property in Lemma if is nonnegative and L-smooth, have [V](x"; < (xV implying that [[IV & 2LF(x*).. Thus, with proba- bility 1 we have
[VF(WT+1) FFS(W++1)1
Ba 1og 16LF(Xx) log(4/8)
4²
(37)
n2
n²
35

---

Published as a conference paper at ICLR 2026
Again, from the smoothness property in Lemma C.7 and the convergence bound in ability - 6, there holds
33 with prob-
V (xT+1)1l
& (2L) (XT+1) Fs(x(5)))
1og(1/6)
if 0 2:
log (0 () lop
if 0 (3:1) 1],
(38)
log log!"+ (1))+))())0))))))))))))
1og
310
(T/6) log t T
if 0 1>1.
Plugging
38 into 37
with probability 1 25, we have: (1.) if 2'
[VF((T++) VFs((T++)ll== ( (og((100)
log
log'(1// (1/6)
F(x" log(1/0))
(39)
T
n²
n
(2. if ($.1) lJ.
VV((T++) -Fs(--=)) 0 loo (0+ (0+)) log T
log²(1/) (1/0)
F(x" log(1100 (1)0)/))))))))))
T
n²
n
(40)
(f) 1,
[VF((T+1) - VVs (W+(W1+
=0( 10 (0+ log
si0-1)
(T/5) T log (1/5)
F(x*) log(1/0)
(41)
T
n²
n
According to the Polyak-Lojasiewiic. condition, we know
F(wT+1)- - F(x*) < | /F(w<+1)11
VF's I/
(42)
Plugging the convergence bound 38) and the generalization bound 339-- into with probability - 35, we have (1.) if 0
F(WT-1)- -(x=)) = o log (1/)
log (1/5)
n² + F(x*)log(111 log(1/0)
T +
if 12.1).
P(WTH))F(66 - = 0 log (0+ 8) (2)
log(0+
log
T
log log (1/8)
F(x" log(1/5)
(18)
+
T
n²
n
(3.) if 1.
F(WT+1) - F(x")= 0 log (gg(++))(3
log
3)e-1)
(T/8)
log2
F(x") log(1/0))
T
n²
n
We choose T n?? then the following inequality holds with probability 1-8
(1/8)
F(x*) log(1/8)
if
n²
n
P(WT+))-F(x
o
log
(0- 3) logo
F(xx) log((1)))
if (2, 1),
log
3(0-1)
(n/8) log ()
F(x F(x") log((1))) if 0 1.
n²
n
The proof is complete.
36


Reviews:
[{"review_id": "VREohmk8eC", "reviewer": "Reviewer_WfMC", "summary": "The authors have obtained high probability gradient norm bounds in a general non-convex problem for stochastic gradient descent with momentum (SGDM). Then under PL condition of loss, they show high probability bounds on the function values and achieve faster rates under Bernstein condition for gradients.", "questions": "Please check the weaknesses", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The authors have done a very good job in terms of literature review. The paper is overall very well written. The assumptions are clearly provided and the theoretical results are well stated. Establishing both convergence and generalization bounds in high probability with clear description is very interesting.", "weaknesses": "This is a nice submission. While I note that the authors have focused on theory, providing a toy experiment in Appendix A will be the main weakness of this submission. I think the paper will be significantly improved by providing more relevant experiments with clear connection with the developed rates under various assumptions and potentially in a more practical setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cCnhOzTRe8", "reviewer": "Reviewer_ctUE", "summary": "The paper studies high-probability convergence and generalization bounds for SGDM in non-convex settings, achieving faster rates under the Polyak-Łojasiewicz (PL) and a Bernstein-type gradient condition.  \nSpecifically, assuming that the stochastic noise follows a sub-Weibull distribution parameterized by $\\theta$, the authors establish a slightly tighter bound at $\\theta = 1/2$ (improving the logarithmic factor from $\\log(T/\\delta)$ to $\\log(1/\\delta)$) and extend the analysis to the case $\\theta > 1$, compared with prior work.", "questions": "1. Under the same assumptions as in the main theorems, are there corresponding high-probability convergence and generalization results for SGD (without momentum)? A direct comparison would help clarify whether momentum offers any provable benefit in this setting.\n\n2. Which concrete model classes (e.g., deep neural networks) are known to satisfy the PL condition?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. The paper provides convergence and generalization bounds for SGDM under arbitrary values of $\\theta$, offering a unified treatment that covers a wide range of noise distributions from sub-Gaussian to heavy-tailed cases.\n\n2. The focus on SGDM rather than plain SGD is interesting, as understanding how momentum affects convergence and generalization remains an important open question in stochastic optimization.", "weaknesses": "1. For the case $\\theta = 1/2$, the improvement over related work is essentially from $\\log(T/\\delta)$ to $\\log(1/\\delta)$ while keeping the same leading-order rate. This represents a mild tightening rather than a substantive advance.\n\n2. The extension to the case $\\theta > 1$ relies on general concentration inequalities applicable to arbitrary $\\theta$ (Appendix Lemmas C.2–C.4). It seems that the main change lies in using a more general tail inequality, which does not introduce substantial technical difficulty or genuine novelty.\n\n3. The paper is difficult to follow, with many typos and inconsistencies. Examples include:\n\n   Line 161: “smothness” → “smoothness”.  \n   Assumption 2.1: The definition of smoothness should not be embedded in the assumption itself.  \n   Theorems: All numbering “(1.) (2.) (3.) (4.)” should be corrected to “(1). (2). (3). (4).”. \n\n   Line 286: “study” should be “studied”.  \n   Theorem 5: The term $\\mu(S)$ appears before being defined.  \n   Line 373: “theFS” should be “the FS”.  \n   Table 1: The first two rows list identical assumptions but yield different error bounds—this should be clarified.\n\n\nTo enhance coherence and credibility, I recommend that the authors thoroughly revise the paper for both clarity and presentation quality.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OPyTEQY18b", "reviewer": "Reviewer_tgE3", "summary": "Strengths\n\n1. First high-probability analysis of SGDM in non-convex settings: The paper provides the first comprehensive high-probability convergence and generalization guarantees for stochastic gradient methods with momentum under nonconvex objectives, bridging an important theoretical gap in stochastic optimization.\n\n2. Sharp convergence rates with structural conditions: The results establish an \\tilde{O}(1/\\sqrt{T}) high-probability convergence rate in the general nonconvex case, improving to \\tilde{O}(1/T) under the Polyak–Łojasiewicz condition and even \\tilde{O}(1/n^2 + F^*/n) under a Bernstein assumption—showing remarkable theoretical depth.\n\n3. Empirical results align with the theory: Experiments on multiple LIBSVM datasets systematically verify the predicted influence of the tail parameter $\\theta$ on convergence speed, offering intuitive visual confirmation of the theoretical high-probability trends.\n\nWeaknesses\n\n1. Limited experimental scope and scalability: Experiments are confined to small-scale logistic regression tasks. The absence of results on large-scale or deep learning benchmarks makes it unclear how well the high-probability bounds manifest in practical training.\n\n2. Lack of practical runtime validation: Theoretical IFO complexity and convergence bounds are not accompanied by empirical runtime or gradient-call comparisons, leaving efficiency gains largely unquantified.", "questions": "NA", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "see Summary", "weaknesses": "see Summary", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Hi3gn8SfLN", "reviewer": "Reviewer_jh4H", "summary": "This paper establishes high probability convergence and generalization upper bounds for non-convex SGDM. Specifically, it first considers the general non-convex case. The convergence results are better than previous works and the generalization bounds are the first ones for SGDM. Then, when PL condition holds, faster rates are achieved than the general non-convex case. Finally, further assuming Bernstein condition brings sharper generalization bounds in the case of low noise.", "questions": "1.Why do the authors use two symbols $f$ and $g$ in Assumption 2.1?\n\n2.There are some typos, such as “smothness”in the last line of page 3 and $k=2,...，$ in Remark 2.3.\n\n3.The whole analysis framework is very similar to [1] except for the lemma which interchanges the order of summation (Lemma C.6) to enable the analysis of [1] in the SGDM case. Due to this reason, all results are the same as those of [1]. Is my understanding right? If so, do these results give us any insights?\n\nNote: From my perspective, the major innovation of proof is mainly presented in Theorem 3.1 and Theorem 3.3, which is listed in **Q3**. If any other innovations exist in the proofs of other results compared with [1], please make them clear. If so, I will improve my score.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.This paper utilizes some special properties of a heavy-tailed distribution, Sub-Weibull distribution, to develop the theoretical analysis of SGDM.\n\n2.The whole paper is written clearly and easy to be understood.", "weaknesses": "1.The inequality in line 1240 may not be true, considering that $(1-\\gamma^{t-i+1})$ is the coefficient of the gradient $\\nabla F_S(x_i)$. We can not ensure the norm with $(1-\\gamma^t)$ is larger than the one with $(1-\\gamma^{t-i+1})$. Therefore, it may greatly affect the subsequent proof.\n\n2.It is better to make a table to list all convergence and generalization results and all previous results, which facilitates readers' understanding of the advantages of their results over previous works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)