Algorithmic Stability of Stochastic Gradient Descent with Momentum under Heavy-Tailed Noise

A K M Rokonuzzaman Sonet; Lingjiong Zhu; Melih Barsbey; Mert Gurbuzbalaban; Thanh Dang; Umut Simsekli

REVIEW 2 major objections 4 minor 54 references

Algorithmic Stability of Stochastic Gradient Descent with Momentum under Heavy-Tailed Noise

T0 review · 2 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For quadratic losses, adding momentum provably makes heavy-tailed SGD's generalization bound worse.

desk verdict Solid technical work on general non-convex stability and degenerate-noise discretization, but the headline claim about momentum harming generalization rests on a flawed bound in Theorem 6 that vanishes for zero initial condition. read the letter →

arxiv 2502.00885 v1 pith:XC2YWXMK submitted 2025-02-02 stat.ML cs.LGmath.OCmath.PR

Thanh Dang , Melih Barsbey , A K M Rokonuzzaman Sonet , Mert Gurbuzbalaban , Umut Simsekli , Lingjiong Zhu This is my paper · ORCID

classification stat.MLcs.LGmath.OCmath.PR MSC 60G5160G5260H1068T05

keywords algorithmicstabilitygeneralizationstochasticgradientdescentmomentumheavytailsWassersteindistanceLévy-drivenSDEdegeneratenoise

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper extends algorithmic-stability analysis of heavy-tailed gradient noise from plain SGD to SGD with momentum (SGDm), modeling the algorithm's continuous-time limit as a Lévy-driven underdamped stochastic differential equation. Its central quantitative claim is that for quadratic losses the p-Wasserstein stability bound—and hence the generalization bound—for SGDm is always at least as large as the corresponding bound for SGD without momentum. The mechanism is algebraic: the smallest singular value of the momentum dynamics' drift matrix is never larger than the smallest singular value of the data-covariance matrix that controls plain SGD. The paper also proves a uniform-in-time discretization bound showing that the discrete recursion inherits the SDE's generalization behavior for suitably small step sizes, and reports experiments on quadratic problems and neural networks that match the predicted ordering. A careful reader should care because momentum is a default optimizer choice; if heavy-tailed noise is present, this analysis identifies a regime where the default choice carries a provable generalization penalty.

What carries the argument

The load-bearing object is the drift matrix $A=\begin{pmatrix}0&-I\\ X^\top X/n&\gamma I\end{pmatrix}$ of the underdamped linear SDE that is the continuous-time limit of SGDm; its block structure couples position and velocity and makes the noise term degenerate, since only the velocity component is driven by the Lévy process. The comparison with SGD reduces to comparing $σ_{\min}$, the smaller of the smallest singular values of the two momentum drift matrices, with $θ_{\min}$, the smaller of the smallest singular values of the two empirical covariance matrices $X^\top X/n$ and $\hat X^\top \hat X/n$. Proposition 8 proves $σ_{\min}\le\u03b8_{\min}$ by diagonalizing $AA^\top$ into $2\times2$ blocks with eigenvalues $μ_{i,\pm}$ and showing $μ_{i,-}\le\kappa_i^2$ for every positive friction parameter $γ$. The Wasserstein bounds themselves are carried by the explicit solution of the linear SDEs together with a small-jump/large-jump split of the stochastic integral, and the general non-quadratic stability bound is carried by a Lyapunov-function contraction estimate plus a Lindeberg-exchange decomposition of the semigroup difference.

What would settle it

A direct computation of the p-th moment of the difference of the two stochastic integrals in the linear quadratic case, with initial condition $Y_0=0$ and two datasets differing in one point, would settle the bound: if that moment is positive and does not scale as $|\sigma_1+\sigma_2|\,\|Y_0\|/n$, the displayed Wasserstein bound cannot be correct.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is a comparison: for quadratic losses, the algorithmic-stability upper bound of SGD with momentum under heavy-tailed noise is always at least as large as the corresponding upper bound for SGD without momentum. The argument writes both continuous-time limits as linear SDEs driven by the same rotationally symmetric $α$-stable Lévy process; the momentum dynamics have a drift matrix $A$ whose smallest singular value $σ_{\min}$ is shown in Proposition 8 to be no larger than $θ_{\min}$, the smallest singular value of the empirical covariance $X^\top X/n$. Since every factor multiplying these singular values in the Wasserstein bound is monotone decreasing, Corollary 7 extracts the ordering of the generalization bounds. The discrete-time extension, Theorem 12 with Corollaries 13–14, shows that for sufficiently small step sizes the recursion inherits the continuous-time bound up to a uniform $O(\eta^{1/\alpha})$ discretization error. The synthetic and neural-network experiments are presented as consistent with the predicted ordering.

Load-bearing premise

The load-bearing premise is that the random-noise part of the difference between the two processes obeys the same bound, with the same initial-condition factor, as the deterministic part, so that the displayed stability bound vanishes when the initial condition is zero.

Editorial extensions

If this is right

For quadratic losses, no choice of the momentum/friction parameter $γ>0$ can make the SGDm generalization bound tighter than plain SGD's; at best smaller $γ$ shrinks the gap.
The tail index $α$ enters the bound through factors like $(2-α)^{-1/2}$ and $(\alpha-1)^{-1}$, so the looser momentum bound is amplified as the noise gets heavier.
For general non-convex losses satisfying the dissipativity and pseudo-Lipschitz conditions, the continuous-time stability bound is linear in the dataset distance $ρ(X_n,\hat X_n)$ up to explicit constants, giving an $O(D/n)$ generalization bound under bounded data.
With step size $η<\bar\eta$, the discrete-time SGDm recursion has a unique invariant measure, and its invariant measure is within $O(\eta^{1/\alpha})$ in Wasserstein distance of the SDE's, so the discrete dynamics inherit the generalization comparison for small step sizes.
The synthetic quadratic and neural-network experiments show the median generalization gap of SGDm is consistently at least as large as SGD's, and it grows with $γ$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The comparison is a statement about upper bounds, not about realized generalization error; a direct finite-time comparison of the stochastic integrals would show whether actual generalization gaps follow the same ordering as the bounds.
If the degenerate velocity noise is the mechanism behind the loss, then other momentum variants whose continuous-time limits share the same block-drift structure may face the same comparison, which the paper does not address.
The bounds scale with the initial condition $‖Y_0\|$, so the momentum penalty should be most visible from nonzero starts; a warm-started run may shrink the apparent penalty, a prediction the paper leaves untested.
For locally quadratic non-convex losses, one could replace $X^\top X$ with the Hessian at a minimum and test whether the same $σ_{\min}\le\u03b8_{\min}$ ordering predicts momentum's generalization gap on neural networks beyond the reported experiments.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The headline is that the paper contains real technical work, but its central claim about momentum is unsupported as proven. The quadratic-loss comparison (Theorem 6, Corollary 7, Proposition 8) has a load-bearing flaw: the bound in (20) multiplies everything by ||Y0||, including the stochastic integral term, which is independent of Y0. Setting Y0=0 makes the right-hand side vanish, but A and A-hat differ, giving distinct stationary laws, so the Wasserstein distance is strictly positive. The proof applies the deterministic estimate (54) to the stochastic integrand, which is not justified. This is not looseness; a valid upper bound cannot be zero for a positive quantity. Since Corollary 7 is the only bridge to the 'momentum is harmful' conclusion, that conclusion collapses.

What stands: Theorem 3 gives a quantitative W1 stability bound for a general non-convex class under heavy-tailed noise, extending the Raj et al. framework to the underdamped (momentum) SDE. The constants are explicit, and the Lindeberg/semigroup decomposition proof is coherent as far as I checked. The uniform-in-time discretization result for stable SDEs with degenerate noise (Theorem 12) appears new and is a genuine contribution to the SDE approximation literature; the step-size condition and ergodicity arguments are substantial. The experiments are honest, and the limitation statement is candid.

The soft spots: aside from Theorem 6, the paper compares upper bounds, not actual generalization errors; even a corrected bound might not imply that momentum is worse in reality. The general non-convex bound is too implicit to compare. The authors acknowledge they cannot explain the phenomenon, which is fine but underscores how fragile the headline is.

Who this is for: researchers in heavy-tailed ML theory, especially those working on stability of optimization algorithms and SDE discretization. The discretization result deserves attention. But the paper needs major revision: either fix Theorem 6 with a correct operator-norm estimate (which would likely involve ||A - A-hat|| instead of ||Y0|| and may not rank the bounds) or reframe the contribution without the strong momentum-is-harmful claim. I would send this to peer review — a serious referee is warranted — but with the expectation of heavy revision. The general non-convex and discretization parts deserve a fair shot.

Referee Report

2 major / 4 minor

Summary. The paper studies algorithmic stability and generalization bounds for stochastic gradient descent with momentum (SGDm) under heavy-tailed noise. It analyzes the continuous-time limit as a degenerate Lévy-driven SDE, proves a Wasserstein stability bound for a class of potentially non-convex losses (Theorem 3), and derives a generalization error bound (Corollary 4). For quadratic losses, it claims a p-Wasserstein stability estimate (Theorem 6) and, combining it with Proposition 8, concludes that SGDm always has a worse generalization bound than SGD without momentum (Corollary 7). The paper also proves a uniform-in-time discretization error bound (Theorem 12) and derives discrete-time stability and generalization bounds. The central quadratic comparison claim is the main advertised contribution.

Significance. If valid, the claim that momentum provably harms generalization under heavy-tailed noise would be a notable and broadly interesting result for optimization and learning theory. The paper also contains a substantial technical component in the uniform-in-time Wasserstein discretization bound for degenerate stable SDEs (Theorem 12), which appears to be new and of independent interest. The general non-convex stability bound (Theorem 3) is plausible and built on sound external tools. However, the headline negative result for momentum rests on Theorem 6, and the proof of that theorem contains a load-bearing error. The comparison claim is therefore not established by this manuscript.

major comments (2)

[Appendix B.1, Eq. (53)-(57)] The stochastic-integral estimate is not supported by the displayed inequality. Equation (54) bounds the norm of e^{-At}Y0 - e^{-\hat A t}Y0 by a multiple of ||Y0||/n; it does not bound the operator norm ||e^{-A(t-s)} - e^{-\hat A(t-s)}||. In the stochastic integrals in (55), the integrand is (e^{-A(t-s)} - e^{-\hat A(t-s)})Σz, so the required estimate is an operator-norm bound applied to the arbitrary jump vector z. The proof instead substitutes the right-hand side of (54) into the integrand, introducing the factor ||Y0||. Setting Y0 = 0 makes the displayed bound in (20) exactly zero, while W_p(μ, μhat) is strictly positive whenever A ≠ \hat A and the two stationary laws differ. A valid upper bound cannot vanish for a strictly positive quantity, so Theorem 6 is unsound as written.
[Theorem 6 and Corollary 7] The stationary bound in (20) depends on the initial condition Y0, but the invariant measures μ and μhat are unique and do not depend on Y0. After passing to t → ∞, the left-hand side W_p(μ, μhat) is independent of Y0, while the right-hand side contains ||Y0||. This is not merely a looseness issue: for Y0 = 0 the right-hand side is zero, contradicting the fact that W_p(μ, μhat) > 0 in the setting of the theorem. Consequently, the comparison in Corollary 7 and the statement that the SGDm bound is always larger than the SGD bound are unsupported. Proposition 8 establishes only the ordering σmin ≤ θmin; without a valid Theorem 6 it cannot carry the generalization comparison. A corrected stochastic-integral estimate would have to be based on an operator-norm bound for e^{-A(t-s)} - e^{-\hat A(t-s)}, which would introduce a factor depending on the difference of the drift matrices rather than on ||Y0||, and there is no reason that the resulting bound would satisfy the same monotone comparison.

minor comments (4)

[Abstract and Section 6] The dataset name is written as 'CIF AR10' in a few places; it should be 'CIFAR-10'.
[Appendix B.1] The word 'erdogicity' should be 'ergodicity'.
[Section 7] The sentence 'On the other hand, Liu et al. (2023), showed that ...' contains a comma splice; it should read 'On the other hand, Liu et al. (2023) showed that ...'.
[Equation (54)] It would help the reader if the text explicitly stated that (54) is an estimate for the fixed vector Y0, not an operator-norm estimate, since the subsequent application is the source of the error in Theorem 6.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the momentum-vs-SGD comparison is derived from independent contraction and coupling estimates, not from the paper's own conclusions.

full rationale

No circular step is present. The paper's central comparison (Corollary 7) is an upper-bound comparison: Theorem 6 bounds the p-Wasserstein distance between stationary laws of two linear heavy-tailed SDEs via explicit coupling estimates (Kunita's inequality and maximal inequalities), and Proposition 8 proves sigma_min <= theta_min algebraically from eigenvalue decompositions; the ordering of the bounds then follows from the monotonicity of x |-> (1-e^{-x})/x and x |-> e^{-x}(1/x+2/x^2+2/x^3). None of the constants are fitted to data, and the comparison is not encoded in the statement of the theorems. Prior work by overlapping authors supplies model definitions and the quadratic-loss baseline (Simsekli et al. 2020; Raj et al. 2023a), but the load-bearing contraction and semigroup-decomposition inputs are Bao and Wang (2022) and Chen et al. (2023c), which are external to the present authors. The apparent Y0-dependence that persists in the Theorem 6 bound after taking t to infinity is a mathematical gap or correctness concern, not a circularity: it does not make the conclusion true by construction, and the proof does not assume the compared upper bounds. Therefore the derivation chain is self-contained with respect to circularity.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The central claims rest on the modeling assumption that heavy-tailed noise is alpha-stable, on the dissipativity and pseudo-Lipschitz conditions, on external Wasserstein contraction results, and on an unsupported operator-norm step in Theorem 6. No constants are fitted to data.

assumptions (7)

domain assumption Conditions H1, H2, and H3 hold (smooth loss, pseudo-Lipschitz gradient, dissipativity with lambda2*lambda4 < lambda1 and the step restriction in equation (12)).
Invoked in Section 3 and Appendix A to build the Lyapunov function and apply the Wasserstein contraction result of Bao and Wang (2022).
domain assumption Gradient noise is modeled as an i.i.d. rotationally symmetric alpha-stable Levy process with alpha in (1,2), independent of the data.
The SDEs (8) and (9) replace the discrete SGDm recursion (5); this is the heavy-tailed proxy inherited from Simsekli et al. (2020) and Raj et al. (2023a,b).
domain assumption A surrogate loss l is L-Lipschitz and the data space has diameter D with 0 in X.
Needed for the Wasserstein-to-generalization transfer in equation (10) and for the explicit bounds in Corollaries 4 and 14.
domain assumption For the quadratic comparison, X^T X and Xhat^T Xhat are positive definite and the loss is f(theta, x) = (theta^T x)^2.
Used in Section 4 to obtain ergodicity and explicit semigroup estimates for the linear SDEs.
standard math The exponential Wasserstein contraction and Lyapunov bounds from Bao and Wang (2022), with constants c0, C0, lambda*, C*, are valid for the zeta-scaled stable Levy noise and carry over unchanged.
Used in Lemmas 16 through 18 and in Theorem 3; the paper only checks that the Levy measure scales with zeta.
standard math The Lindeberg exchange / Markov process approximation framework of Chen et al. (2023c) and the ergodicity criterion of Meyn and Tweedie (1992) apply to the momentum chain.
Used in Appendix A and Appendix C for Theorem 3 and Theorem 11.
ad hoc to paper For Theorem 6, the difference of the two stochastic integrals is controlled by the same operator estimate as the deterministic initial-condition term, implicitly requiring the bound to be independent of Y0 after passing to stationarity.
This is the unsupported step; the displayed inequality keeps ||Y0|| in all terms, causing W_p <= 0 for Y0 = 0.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Algorithmic Stability of Stochastic Gradient Descent with Momentum under Heavy-Tailed Noise." pith.science (2026). https://pith.science/paper/XC2YWXMK

@misc{pith2026250200885,
  author       = {Pith},
  title        = {Pith review of: Algorithmic Stability of Stochastic Gradient Descent with Momentum under Heavy-Tailed Noise},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XC2YWXMK}},
  note         = {Machine review of arXiv:2502.00885}
}

read the original abstract

Understanding the generalization properties of optimization algorithms under heavy-tailed noise has gained growing attention. However, the existing theoretical results mainly focus on stochastic gradient descent (SGD) and the analysis of heavy-tailed optimizers beyond SGD is still missing. In this work, we establish generalization bounds for SGD with momentum (SGDm) under heavy-tailed gradient noise. We first consider the continuous-time limit of SGDm, i.e., a Levy-driven stochastic differential equation (SDE), and establish quantitative Wasserstein algorithmic stability bounds for a class of potentially non-convex loss functions. Our bounds reveal a remarkable observation: For quadratic loss functions, we show that SGDm admits a worse generalization bound in the presence of heavy-tailed noise, indicating that the interaction of momentum and heavy tails can be harmful for generalization. We then extend our analysis to discrete-time and develop a uniform-in-time discretization error bound, which, to our knowledge, is the first result of its kind for SDEs with degenerate noise. This result shows that, with appropriately chosen step-sizes, the discrete dynamics retain the generalization properties of the limiting SDE. We illustrate our theory on both synthetic quadratic problems and neural networks.

Figures

Figures reproduced from arXiv: 2502.00885 by the authors.

**Figure 2.** Comparing SGD with and without momentum, using the following modeldataset combinations: (top left) MNIST - FCN, (top right) MNIST - CNN, (bottom left) CIFAR-10 - FCN, and (bottom right) CIFAR-10 - CNN. 13 [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

54 extracted references · 51 canonical work pages

[1]

Akiyama and T

S. Akiyama and T. Suzuki. Excess risk of two-layer ReLU neural networks in teacher-student settings and its superiority to kernel methods. In International Conference on Learning Representations, 2023

work page 2023
[2]

Andreeva, B

R. Andreeva, B. Dupuis, R. Sarkar, T. Birdal, and U. Simsekli. Topological generalization bounds for discrete-time stochastic optimization algorithms. In The Thirty-Eighth Annual Conference on Neural Information Processing Systems (NeurIPS), 2024

work page 2024
[3]

Applebaum

D. Applebaum. L \'e vy Processes and Stochastic Calculus . Cambridge University Press, 2009

work page 2009
[4]

F. Bach. Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression. Journal of Machine Learning Research, 15 0 (1): 0 595--627, 2014

work page 2014
[5]

Bao and J

J. Bao and J. Wang. Coupling approach for exponential ergodicity of stochastic H amiltonian systems with L évy noises. Stochastic Processes and their Applications, 146: 0 114–142, 2022

work page 2022
[6]

Barsbey, M

M. Barsbey, M. Sefidgaran, M. A. Erdogdu, G. Richard, and U. Simsekli. Heavy tails in SGD and compressibility of overparametrized neural networks. In Advances in Neural Information Processing Systems, volume 34, pages 29364--29378, 2021

work page 2021
[7]

J. Bertoin. L\' e vy Processes . Cambridge Tracts in Mathematics. Cambridge University Press, 1996

work page 1996
[8]

Camuto, G

A. Camuto, G. Deligiannidis, M. A. Erdogdu, M. Gurbuzbalaban, U. Simsekli, and L. Zhu. Fractal structure and generalization properties of stochastic optimization algorithms. In Advances in Neural Information Processing Systems, volume 34, pages 18774--18788, 2021

work page 2021

Show all 54 references

[9]

Cao and Q

Y. Cao and Q. Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in Neural Information Processing Systems, volume 32, 2019

2019
[10]

H. Cartan. Differential Calculus. International Studies in Mathematics. Hermann, 1983

1983
[11]

Chen, C.-S

P. Chen, C.-S. Deng, R. L. Schilling, and L. Xu. Approximation of the invariant measure of stable SDE s by an E uler-- M aruyama scheme. Stochastic Processes and their Applications, 163: 0 136--167, 2023 a

2023
[12]

P. Chen, X. Jin, Y. Xiao, and L. Xu. Approximation of the invariant measure for stable SDE by the E uler- M aruyama scheme with decreasing step-sizes. arXiv preprint arXiv:2310.05390, 2023 b

2023 arXiv
[13]

Chen, Q.-M

P. Chen, Q.-M. Shao, and L. Xu. A probability approximation framework: M arkov process approach. The Annals of Applied Probability, 33 0 (2): 0 1619--1659, 2023 c

2023
[14]

Damek and S

E. Damek and S. Mentemeier. Analysing heavy-tail properties of stochastic gradient descent by means of stochastic recurrence equations. arXiv preprint arXiv:2403.13868, 2024

2024 arXiv
[15]

Dang and L

T. Dang and L. Zhu. Euler- M aruyama schemes for stochastic differential equations driven by stable L \' e vy processes with iid stable components. arXiv preprint arXiv:2402.12502, 2024

2024 arXiv
[16]

C. Deng, X. Li, R. L. Schilling, and L. Xu. Total variation distance between SDE s with stable noise and B rownian motion with applications to P oisson PDE s. arXiv preprint arXiv:2407.21306, 2024

2024
[17]

Dupuis and U

B. Dupuis and U. Simsekli. Generalization bounds for heavy-tailed SDE s through the fractional F okker- P lanck equation. In International Conference on Machine Learning, volume 235, pages 12087--12137. PMLR, 2024

2024
[18]

M. A. Erdogdu, R. Hosseinzadeh, and M. S. Zhang. Convergence of L angevin M onte C arlo in C hi-squred and R \' e nyi divergence. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), volume 151. PMLR, 2022

2022
[19]

X. Gao, M. G \"u rb \"u zbalaban, and L. Zhu. Global convergence of stochastic gradient H amiltonian M onte C arlo for nonconvex stochastic optimization: Nonasymptotic performance bounds and momentum-based acceleration. Operations Research, 70 0 (5): 0 2931--2947, 2022

2022
[20]

Gurbuzbalaban, U

M. Gurbuzbalaban, U. Simsekli, and L. Zhu. The heavy-tail phenomenon in SGD . In International Conference on Machine Learning, volume 139, pages 3964--3975. PMLR, 2021

2021
[21]

Hardt, B

M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, volume 48, pages 1225--1234. PMLR, 2016

2016
[22]

Hodgkinson and M

L. Hodgkinson and M. Mahoney. Multiplicative noise and heavy tails in stochastic optimization. In International Conference on Machine Learning, volume 139, pages 4262--4274. PMLR, 2021

2021
[23]

Hodgkinson, U

L. Hodgkinson, U. Simsekli, R. Khanna, and M. Mahoney. Generalization bounds using lower tail exponents in stochastic optimizers. In International Conference on Machine Learning, volume 162, pages 8774--8795. PMLR, 2022

2022
[24]

Jiao and M

Z. Jiao and M. Keller-Ressel. Emergence of heavy tails in homogenized stochastic gradient descent. In The Thirty-Eighth Annual Conference on Neural Information Processing Systems (NeurIPS), 2024

2024
[25]

X. Jin, G. Pang, Y. Wang, and L. Xu. Approximation of the steady state for piecewise stable O rnstein- U hlenbeck processes arising in queueing networks. arXiv preprint arXiv:2405.18851, 2024

2024 arXiv
[26]

Krizhevsky, I

A. Krizhevsky, I. Sutskever, and G. E. Hinton. ImageNet classification with deep convolutional neural networks. Communications of the ACM, 60 0 (6): 0 84--90, May 2017

2017
[27]

Lecun, L

Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86 0 (11): 0 2278--2324, 1998

1998
[28]

Lei and Y

Y. Lei and Y. Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning, volume 119, pages 5809--5819. PMLR, 2020

2020
[29]

S. H. Lim, Y. Wan, and U. Simsekli. Chaotic regularization and heavy-tailed limits for deterministic gradient descent. In Advances in Neural Information Processing Systems, volume 35, pages 26590--26602, 2022

2022
[30]

Z. Liu, J. Zhang, and Z. Zhou. Breaking the lower bound with (little) structure: Acceleration in non-convex stochastic optimization with heavy-tailed noise. In The Thirty Sixth Annual Conference on Learning Theory, volume 195, pages 2266--2290. PMLR, 2023

2023
[31]

J. Lu, Y. Tan, and L. Xu. Central limit theorem and self-normalized C ram \'e r-type moderate deviation for E uler- M aruyama scheme. Bernoulli, 28 0 (2): 0 937--964, 2022

2022
[32]

Mahoney and C

M. Mahoney and C. Martin. Traditional and heavy tailed self regularization in neural network models. In International Conference on Machine Learning, volume 97, pages 4284--4293. PMLR, 2019

2019
[33]

C. H. Martin, T. Peng, and M. W. Mahoney. Predicting trends in the quality of state-of-the-art neural networks without access to training or testing data. Nature Communications, 12 0 (1): 0 4122, 2021

2021
[34]

S. P. Meyn and R. L. Tweedie. Stability of M arkovian processes I : Criteria for discrete-time chains. Advances in Applied Probability, 24 0 (3): 0 542--574, 1992

1992
[35]

G. Neu, G. K. Dziugaite, M. Haghifam, and D. M. Roy. Information-theoretic generalization bounds for stochastic gradient descent. In Conference on Learning Theory, volume 134, pages 3526--3545. PMLR, 2021

2021
[36]

B. K. ksendal. Stochastic Differential Equations: An Introduction with Applications. Springer, 5th edition, 2002

2002
[37]

S. Park, U. Simsekli, and M. A. Erdogdu. Generalization bounds for stochastic gradient descent via localized -covers. In Advances in Neural Information Processing Systems, volume 35, pages 2790--2802, 2022

2022
[38]

Paszke, S

A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. K \"o pf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. PyTorch : An Imperative Style , Hi...

2019
[39]

K. L. Pavasovic, A. Durmus, and U. Simsekli. Approximate heavy tails in offline (multi-pass) stochastic gradient descent. In Thirty-Seventh Conference on Neural Information Processing Systems (NeurIPS), 2023

2023
[40]

Raginsky, A

M. Raginsky, A. Rakhlin, M. Tsao, Y. Wu, and A. Xu. Information-theoretic analysis of stability and bias of learning algorithms. In 2016 IEEE Information Theory Workshop (ITW), pages 26--30. IEEE, 2016

2016
[41]

Raginsky, A

M. Raginsky, A. Rakhlin, and M. Telgarsky. Non-convex learning via stochastic gradient L angevin dynamics: A nonasymptotic analysis. In Conference on Learning Theory, volume 65, pages 1674--1703. PMLR, 2017

2017
[42]

A. Raj, M. Barsbey, M. G\" u rb\" u zbalaban, L. Zhu, and U. S im s ekli. Algorithmic stability of heavy-tailed stochastic gradient descent on least squares. In International Conference on Algorithmic Learning Theory, volume 201, pages 1292--1342. PMLR, 2023 a

2023
[43]

A. Raj, L. Zhu, M. G\" u rb\" u zbalaban, and U. S im s ekli. Algorithmic stability of heavy-tailed SGD with general loss functions. In International Conference on Machine Learning, volume 202, pages 28578--28597. PMLR, 2023 b

2023
[44]

Samoradnitsky

G. Samoradnitsky. Stable Non-Gaussian Random Processes: Stochastic Models with Infinite Variance. CRC Press, 2017

2017
[45]

Schertzer and L

A. Schertzer and L. Pillaud-Vivien. Stochastic differential equations models for least-squares stochastic gradient descent. arXiv preprint arXiv:2407.02322, 2024

2024 arXiv
[46]

Shalev-Shwartz and S

S. Shalev-Shwartz and S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014

2014
[47]

S im s ekli, O

U. S im s ekli, O. Sener, G. Deligiannidis, and M. A. Erdogdu. Hausdorff dimension, heavy tails, and generalization in neural networks. In Advances in Neural Information Processing Systems, volume 33, pages 5138--5151, 2020

2020
[48]

Simonyan and A

K. Simonyan and A. Zisserman. Very Deep Convolutional Networks for Large-Scale Image Recognition , Apr. 2015

2015
[49]

S im s ekli, L

U. S im s ekli, L. Zhu, Y. W. Teh, and M. G \"u rb \"u zbalaban. Fractional underdamped L angevin dynamics: Retargeting SGD with momentum under heavy-tailed gradient noise. In International Conference on Machine Learning, volume 119, pages 8970--8980. PMLR, 2020

2020
[50]

S im s ekli, M

U. S im s ekli, M. G \"u rb \"u zbalaban, S. Y ld r m, and L. Zhu. Differential privacy of noisy (S)GD under heavy-tailed perturbations. arXiv preprint arXiv:2403.02051, 2024

2024 arXiv
[51]

C. Villani. Optimal Transport: Old and New. Grundlehren der mathematischen Wissenschaften. Springer Berlin Heidelberg, 2008

2008
[52]

Y. Wan, M. Barsbey, A. Zaidi, and U. Simsekli. Implicit compressibility of overparametrized neural networks trained with heavy-tailed SGD . In Proceedings of the 41st International Conference on Machine Learning, volume 235, pages 49845--49866. PMLR, 2024

2024
[53]

J. Zhu, Z. Brzezniak, and W. Liu. Maximal inequalities and exponential estimates for stochastic convolutions driven by L \' e vy-type processes in B anach spaces with application to stochastic quasi-geostrophic equations. SIAM Journal on Mathematical Analysis, 51 0 (3): 0 2121...

2019
[54]

L. Zhu, M. Gurbuzbalaban, A. Raj, and U. Simsekli. Uniform-in-time wasserstein stability bounds for (noisy) stochastic gradient descent. In Advances in Neural Information Processing Systems, volume 36, 2024

2024

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.

[1] [1]

Akiyama and T

S. Akiyama and T. Suzuki. Excess risk of two-layer ReLU neural networks in teacher-student settings and its superiority to kernel methods. In International Conference on Learning Representations, 2023

work page 2023

[2] [2]

Andreeva, B

R. Andreeva, B. Dupuis, R. Sarkar, T. Birdal, and U. Simsekli. Topological generalization bounds for discrete-time stochastic optimization algorithms. In The Thirty-Eighth Annual Conference on Neural Information Processing Systems (NeurIPS), 2024

work page 2024

[3] [3]

Applebaum

D. Applebaum. L \'e vy Processes and Stochastic Calculus . Cambridge University Press, 2009

work page 2009

[4] [4]

F. Bach. Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression. Journal of Machine Learning Research, 15 0 (1): 0 595--627, 2014

work page 2014

[5] [5]

Bao and J

J. Bao and J. Wang. Coupling approach for exponential ergodicity of stochastic H amiltonian systems with L évy noises. Stochastic Processes and their Applications, 146: 0 114–142, 2022

work page 2022

[6] [6]

Barsbey, M

M. Barsbey, M. Sefidgaran, M. A. Erdogdu, G. Richard, and U. Simsekli. Heavy tails in SGD and compressibility of overparametrized neural networks. In Advances in Neural Information Processing Systems, volume 34, pages 29364--29378, 2021

work page 2021

[7] [7]

J. Bertoin. L\' e vy Processes . Cambridge Tracts in Mathematics. Cambridge University Press, 1996

work page 1996

[8] [8]

Camuto, G

A. Camuto, G. Deligiannidis, M. A. Erdogdu, M. Gurbuzbalaban, U. Simsekli, and L. Zhu. Fractal structure and generalization properties of stochastic optimization algorithms. In Advances in Neural Information Processing Systems, volume 34, pages 18774--18788, 2021

work page 2021