Pith. sign in

REVIEW 1 major objections 3 minor 95 references

Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization

T0 review · 1 major / 3 minor · reviewed 2026-08-03 · deepseek-v4-flash

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

Pith's one-line read For non-convex costs, the probability that the best iterate of vanilla or clipped SGD fails to reach stationarity by time t decays like e^{-t/log t} — an order of magnitude faster than earlier finite-time bounds implied.

desk verdict The upper-bound LDP rates for SGD and clipped SGD are plausible and genuinely faster than prior finite-time bounds, but the advertised 'tight up to polylog' claim is not supported: the Theorem 3 lower bound decays at speed e^{-t} while the upper bounds are e^{-t/log t} or slower. read the letter →

arxiv 2602.05657 v2 pith:NLK45AKX submitted 2026-02-05 cs.LG math.OC

Aleksandar Armacki , Dragana Bajović , Dušan Jakovetić , Soummya Kar , Ali H. Sayed This is my paper · ORCID
classification cs.LGmath.OC MSC 60F1062L2090C1590C26
keywords largedeviationsstochasticgradientdescentclippedSGDheavy-tailednoisenon-convexoptimizationtailboundsfailureprobabilitymoment-generatingfunction
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

The paper asks a sharp question about individual runs: what is the probability that, after t iterations, no SGD iterate has gradient norm below a fixed threshold? It proves that this failure probability decays like e^{-t/log t} for vanilla SGD with almost-surely bounded noise, and like e^{-t^{β_p}/log t} (with β_p=4(p-1)/(3p-2), or e^{-t/log^2 t} when p=2) for clipped SGD with heavy-tailed noise having a bounded p-th moment. These rates are exponentially faster than the √t and t^{β_p/2} decays implied by earlier finite-time high-probability bounds, so the prediction for long training runs is qualitatively different. A constructed example with a piecewise-quadratic cost and symmetric two-point noise shows the rates are tight up to logarithmic factors.

What carries the argument

The engine is a sequence of uniform bounds on the log-moment-generating function of F_t, evaluated at λ n_t for every real λ, combined with the Fenchel–Legendre transform from large-deviations theory. For vanilla SGD, L-smoothness turns F_t into a sum of deterministic, noise, and squared-noise terms, and a sub-Gaussian inequality for the a.s. bounded noise yields a quadratic rate function. For clipped SGD, the clipping error is decomposed into an unbiased sub-Gaussian component with scale γ_t and a bias component bounded by 4σ_p γ_t^{1-p}; choosing γ_t to grow at the right rate balances the two and produces the exponent β_p. The lower bound is carried by a probabilistic invariant: for the co

What would settle it

The proof of the main upper bound reduces to inequality (19): after dividing by n_t = t/log t, all terms except 6λ^2M^2G^2 must vanish. If one can exhibit a cost and noise satisfying Assumptions 1–3 for which the empirical limsup of (log t / t) log P(F_t > ε) exceeds -ε^2/(24M^2G^2), or for which the stated log-MGF inequality fails at some λ, the t/log t rate is wrong. For the lower bound, the constructed event that the iterate stays at x_1 for t steps has probability 2^{-t+1}; verifying the piecewise-quadratic recursion with two-point noise at finite t is a direct check.

Watch

Extended reading notes

Core claim

The paper shows that under deterministic initialization, a smooth lower-bounded cost with gradients bounded by G, and unbiased noise bounded almost surely by M, vanilla SGD with step-size a/√(t+1) satisfies a large-deviations upper bound on F_t = min_{k≤t} ||∇f(x_k)||^2 at rate n_t = t/log t, with rate function I_v(x)=x^2/(24M^2G^2) for x≥0. Under heavy-tailed noise with a bounded moment of order p, clipped SGD with a suitably growing clipping threshold achieves rate t^{4(p-1)/(3p-2)}/log t for p∈(1,2) and t/log^2 t for p=2. The paper also constructs an instance — a piecewise-quadratic cost with symmetric two-point noise and a deterministic nonzero-gradient initialization — for which the tra

Load-bearing premise

The load-bearing premise is that the noise is almost surely bounded (for vanilla SGD) or has a bounded p-th moment with uniformly bounded gradients (for clipped SGD): the proof must control the moment-generating function at every real λ, and these boundedness conditions are what make that global control possible.

Editorial extensions

If this is right

  • If Theorem 1 is right, the asymptotic chance that a vanilla SGD run misses every ε-stationary point in its first t steps is at most exp(-ε^2 t / (24M^2G^2 log t)), much smaller than the exp(-c√t) decay implied by prior finite-time bounds.
  • For clipped SGD under heavy-tailed noise, the long-run tail rate improves from order t^{β_p/2} to order t^{β_p} (with an extra log^2 t factor at p=2), so clipping provides both robustness to unbounded noise and faster per-run failure decay.
  • Because the bounds fix the error threshold ε and let t grow, they speak directly to modern training regimes of millions of iterations, where finite-time bounds valid for every t are overly conservative in the long run.
  • The same proof technique delivers bounds on the average squared gradient norm, not just the minimum, so the result is not an artifact of the min-over-first-t metric.
  • The lower-bound instance shows some problems genuinely have P(F_t>ε) ≥ 2e^{-t ln2}, so no general upper bound can decay faster than exponential in t; the presented rates are tight up to logarithmic factors.

Reading between the lines

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

  • The logarithmic factors in the upper rates look like artifacts of the summation step that replaces ∑_{k=1}^t 1/(k+1) by log(t+1); closing that gap would likely yield e^{-ct} upper bounds that exactly match the constructed lower bound.
  • The bounded-gradient and almost-sure-bounded-noise assumptions exist to make the moment-generating function finite on the whole real line; if the argument can be reworked for sub-Gaussian or unbounded-gradient costs, the same t/log t prediction may hold more broadly.
  • A natural extension is to adaptive methods whose updates normalize or clip the gradient estimate, since the clipped-SGD analysis already produces a sub-Gaussian unbiased component with growing scale; similar large-deviations bounds may hold under only weak moment assumptions.
  • The constructed lower-bound instance is simple enough to simulate at finite t, so one could check numerically how quickly the e^{-t/log t} regime sets in and whether the asymptotic rate is visible at realistic iteration counts.
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.

Referee Report

1 major / 3 minor

Summary. The paper studies the long-term tail decay of the best-iterate gradient norm squared, F_t = min_{k<=t} ||grad f(x_k)||^2, for vanilla SGD under bounded noise and for clipped SGD under bounded p-th moment noise. Using MGF estimates and the Gartner-Ellis theorem, Theorem 1 gives an LDP upper bound for SGD with rate t/log(t), and Theorem 2 gives upper bounds for clipped SGD with rates t^{4(p-1)/(3p-2)}/log(t) for p in (1,2) and t/log^2(t) for p=2. Theorem 3 constructs a specific Huber-cost/Rademacher-noise instance and proves P(F_t>eps) >= a_1 e^{-a_2 t}. The paper advertises these results as showing that the upper-bound rates are tight up to polylogarithmic factors.

Significance. If the upper-bound derivations are correct, they are a genuine technical contribution: they obtain large-deviations upper bounds with global rate functions for non-convex SGD, improving on the tail decay implied by existing finite-time high-probability bounds, and the extension to clipped SGD under heavy-tailed noise is nontrivial. The Gartner-Ellis route and the control of the global MGF are interesting and largely self-contained. However, the advertised central claim of tightness is not established. The lower bound in Theorem 3 is at speed e^{-t}, while the upper bounds are at slower speeds e^{-t/log t} and e^{-t/log^2 t} / e^{-t^{beta_p}/log t}. Such a lower bound does not rule out upper bounds at speed e^{-O(t)}, so it cannot support the conclusion that the stated rates are tight. The upper-bound theorems may be publishable as standalone large-deviations bounds, but the paper as submitted overclaims its main result.

major comments (1)
  1. [Section 3.4, Theorem 3 and Eq. (6)] The lower bound P(F_t>eps) >= a_1 e^{-a_2 t} is at decay speed n_t=t, while Theorem 1's upper bound is at speed n_t=t/log(t). Under the normalization of Corollary 1, this lower bound only implies liminf (log t / t) log P >= -infinity, not a finite negative constant. Indeed, P(F_t>eps) >= e^{-a_2 t} is compatible with P(F_t>eps) <= e^{-c t}, i.e. with an upper bound at speed t, so it does not rule out a faster tail than the claimed t/log(t). To prove tightness one would need a lower bound at the same scale, e.g. P >= e^{-C t/log t}. The same mismatch holds for clipped SGD: for p=2 the comparison is e^{-t} versus e^{-t/log^2 t}, and for p in (1,2) it is e^{-t} versus e^{-t^{beta_p}/log t}, a polynomial gap. Thus Eq. (6) compares two different normalizations and cannot be read as showing tightness; the abstract's 'tight up to poly-logarithmic factors' claim is unsupported.
minor comments (3)
  1. [Section 3.3, Corollary 2] The constants in Corollary 2 are reversed relative to Theorem 2. Theorem 2 gives rate function x^2/(768 G^4) for p in (1,2) and x^2/(384 G^4) for p=2, but Corollary 2 states -eps^2/(384 G^4) for p in (1,2) and -eps^2/(768 G^4) for p=2. The corollary should match the theorem.
  2. [Lemma 3.2 / Theorem 3 proof] For p=2, the clipping threshold in (5) is gamma_t = 2G sqrt(log(t+1)); at t=1 this is about 1.66G, so gamma_1/2 < G and the condition ||grad f(x_t)|| <= gamma_t/2 used in Proposition 2 may fail at t=1. The proof of Theorem 3 states that the threshold (5) 'clearly' satisfies gamma_t >= 2G, which is not true at t=1. Finite initial exceptions do not affect the limsup, but the statements should be modified.
  3. [Appendix E, proof of Theorem 1] In the proof, the sequence is defined as n_t = t/log(T), later used as t/log(t); the capital T is a typo.

Circularity Check

0 steps flagged · score 0.0 of 10

No material circularity: upper-bound LDP derivations are self-contained; the lower-bound/tightness gap is a correctness concern, not a circular reduction.

full rationale

The main LDP upper bounds (Theorems 1 and 2) are derived from the stated assumptions and update rules: smoothness gives (16)/(21), MGF bounds are obtained via Lemmas 3.1/3.2, and the standard Gartner-Ellis theorem (external Proposition 1 in Appendix D) converts the pointwise log-MGF limit into an upper bound with rate function I_v or I_c. The constants M, G, sigma, and gamma_t are assumption parameters or chosen threshold values; none are fitted to the tail probability being predicted. The self-citations ([15], [16], [17], [87]) are used for comparison, context, or the elementary fact that the Huber cost has L=2; they do not carry the central derivation. Theorem 3's constructed Huber/Rademacher instance yields P(F_t > eps) >= 2 e^{-t ln 2}; this is an explicit example, not a restatement of the upper bound, so it is not circular. The skeptic's concern that an e^{-a_2 t} lower bound does not by itself certify tightness of e^{-t/log t} or e^{-t^{beta_p}/log t} upper bounds is a legitimate correctness/soundness criticism of the 'tight up to polylog' conclusion, but it is a non-sequitur in the argument, not a circular reduction of the result to its inputs.

Assumptions & free parameters 3 free parameters · 6 assumptions · 0 invented entities

The paper introduces no new physical or algorithmic entities; its free parameters are the theoretically chosen step-size and clipping-threshold schedules. The main assumptions are standard regularity conditions (bounded gradients, bounded/bounded-moment noise) plus one external clipping-bias lemma. No fitted constants or hidden oracle values are introduced; however, the hand-chosen schedules are part of the theorem statements rather than universal algorithm defaults.

free parameters (3)
  • Step-size schedule for SGD: alpha_t = a/sqrt(t+1) = a <= 1/L with L-smoothness constant
    Chosen by the authors to balance the descent and noise terms in the MGF bound; not fitted to data, but the asymptotic rates depend on the polynomial form of the schedule.
  • Step-size schedule for clipped SGD: alpha_t = (t+1)^{-p/(3p-2)} = exponent -p/(3p-2) for p in (1,2]
    Chosen to make the clipping-bias and variance terms vanish at the right rate in Appendix F; a design choice, not an empirical fit.
  • Clipping threshold schedule gamma_t (Eq. 5) = 2G (t+1)^{(2-p)/(6p-4)} for p in (1,2); 2G sqrt(log(t+1)) for p=2
    Hand-tuned by the authors so that Proposition 2 applies (||grad f|| <= gamma_t/2) and the MGF remains finite everywhere; it is a theoretical tuning parameter, not a fitted constant. Appendix I shows any C>0 works with the rate function rescaled.
assumptions (6)
  • domain assumption Assumption 1: deterministic initialization
    Used throughout to make the filtration and MGF arguments well-defined; mild, but part of the theorem statements.
  • domain assumption Assumption 2: f is lower bounded, L-smooth, and has uniformly bounded gradients ||grad f|| <= G
    Central to both Theorem 1 and Theorem 2: bounds the cross terms in the MGF estimates and, for clipped SGD, guarantees the condition ||grad f(x_t)|| <= gamma_t/2 needed by Proposition 2 in Lemma 3.2.
  • domain assumption Assumption 3: unbiased estimator with a.s. bounded noise ||z_t|| <= M
    Needed for Lemma 3.1 and to make E[exp(lambda F_t)] finite for every lambda in R, which is required to apply the Gartner-Ellis upper bound in Proposition 1.
  • domain assumption Assumption 4: unbiased estimator with bounded p-th moment E||z_t||^p <= sigma^p, p in (1,2]
    Used for clipped SGD in Theorem 2 to control the clipping bias via Proposition 2 and to obtain sub-Gaussian concentration of the clipped-noise fluctuation term.
  • standard math Gartner-Ellis theorem (Proposition 1)
    The standard large-deviations tool used to convert limsup bounds on scaled log-MGFs into LDP upper bounds; cited from Dembo & Zeitouni [11].
  • domain assumption Clipping-bias bound Proposition 2 (from [29], Lemma 5.1)
    A prior external result that bounds E[clipped(X)] - E[X] by 4 sigma_p gamma^{1-p} under a p-th moment condition. It is load-bearing for Lemma 3.2 and Theorem 2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization." pith.science (2026). https://pith.science/paper/NLK45AKX

@misc{pith2026260205657,
  author       = {Pith},
  title        = {Pith review of: Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NLK45AKX}},
  note         = {Machine review of arXiv:2602.05657}
}
abstract

The study of tail behaviour of SGD-induced processes has been attracting a lot of interest, due to offering strong guarantees with respect to individual runs of an algorithm. While many works provide high-probability guarantees, quantifying the error rate for a fixed probability threshold, there is a lack of work directly studying the probability of failure, i.e., quantifying the tail decay rate for a fixed error threshold. Moreover, existing results are of finite-time nature, limiting their ability to capture the true long-term tail decay which is more informative for modern learning models, typically trained for millions of iterations. Our work closes these gaps, by studying the long-term tail decay of SGD-based methods through the lens of large deviations theory, establishing several strong results in the process. First, we provide an upper bound on the tails of the gradient norm-squared of the best iterate produced by (vanilla) SGD, for non-convex costs and bounded noise, with long-term decay at rate $e^{-t/\log(t)}$. Next, we relax the noise assumption by considering clipped SGD (c-SGD) under heavy-tailed noise with bounded moment of order $p \in (1,2]$, showing an upper bound with long-term decay at rate $e^{-t^{\beta_p}/\log(t)}$, where $\beta_p = \frac{4(p-1)}{3p-2}$ for $p \in (1,2)$ and $e^{-t/\log^2(t)}$ for $p = 2$. Finally, we provide lower bounds on the tail decay, at rate $e^{-t}$, showing that our rates for both SGD and c-SGD are tight, up to poly-logarithmic factors. Notably, our results demonstrate an order of magnitude faster long-term tail decay compared to existing work based on finite-time bounds, which show rates $e^{-\sqrt{t}}$ and $e^{-t^{\beta_p/2}}$, $p \in (1,2]$, for SGD and c-SGD, respectively. As such, we uncover regimes where the tails decay much faster than previously known, providing stronger long-term guarantees for individual runs.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

95 extracted references · 7 linked inside Pith

  1. [1]

    Opt: Open pre-trained transformer language models,

    S. Zhang, S. Roller, N. Goyal, M. Artetxe, M. Chen, S. Chen, C. Dewan, M. Diab, X. Li, X. V. Lin,et al., “Opt: Open pre-trained transformer language models,”arXiv preprint arXiv:2205.01068, 2022

    arXiv 2022

  2. [2]

    A stochastic approximation method,

    H. Robbins and S. Monro, “A stochastic approximation method,”The annals of mathe- matical statistics, pp. 400–407, 1951

    1951

  3. [3]

    A. H. Sayed,Inference and Learning from Data: Foundations, vol. 1. Cambridge Uni- versity Press, 2023

    2023

  4. [4]

    Robust stochastic approximation approach to stochastic programming,

    A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro, “Robust stochastic approximation approach to stochastic programming,”SIAM Journal on optimization, vol. 19, no. 4, pp. 1574–1609, 2009

    2009

  5. [5]

    Stochastic first-and zeroth-order methods for nonconvex stochastic programming,

    S. Ghadimi and G. Lan, “Stochastic first-and zeroth-order methods for nonconvex stochastic programming,”SIAM Journal on Optimization, vol. 23, no. 4, pp. 2341–2368, 2013

    2013

  6. [6]

    Lower bounds for non-convex stochastic optimization,

    Y. Arjevani, Y. Carmon, J. C. Duchi, D. J. Foster, N. Srebro, and B. Woodworth, “Lower bounds for non-convex stochastic optimization,”Mathematical Programming, vol. 199, pp. 165–214, May 2023

    2023

  7. [7]

    Imagenet classification with deep convo- lutional neural networks,

    A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convo- lutional neural networks,” inAdvances in Neural Information Processing Systems, vol. 25, Curran Associates, Inc., 2012

    2012

  8. [8]

    Deep residual learning for image recognition,

    K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” inProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016

    2016

Show all 95 references
  1. [9]

    BERT: Pre-training of deep bidirec- tional transformers for language understanding,

    J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “BERT: Pre-training of deep bidirec- tional transformers for language understanding,” inProceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technolog...

    2019

  2. [10]

    Training Compute-Optimal Large Language Models,

    J. Hoffmann, S. Borgeaud, A. Mensch, E. Buchatskaya, T. Cai, E. Rutherford, D. de Las Casas, L. A. Hendricks, J. Welbl, A. Clark, T. Hennigan, E. Noland, K. Mil- lican, G. van den Driessche, B. Damoc, A. Guy, S. Osindero, K. Simonyan, E. Elsen, O. Vinyals, J. Rae, and L. Sifre...

    2022

  3. [11]

    Dembo and O

    A. Dembo and O. Zeitouni,Large deviations techniques and applications, vol. 38. Springer Science & Business Media, 2009

    2009

  4. [12]

    High probability conver- gence of stochastic gradient methods,

    Z. Liu, T. D. Nguyen, T. H. Nguyen, A. Ene, and H. Nguyen, “High probability conver- gence of stochastic gradient methods,” inInternational Conference on Machine Learning, pp. 21884–21914, PMLR, 2023. 14

    2023

  5. [13]

    High-probability bounds for non-convex stochastic opti- mization with heavy tails,

    A. Cutkosky and H. Mehta, “High-probability bounds for non-convex stochastic opti- mization with heavy tails,”Advances in Neural Information Processing Systems, vol. 34, pp. 4883–4895, 2021

    2021

  6. [14]

    Improved convergence in high probability of clipped gradient methods with heavy tailed noise,

    T. D. Nguyen, T. H. Nguyen, A. Ene, and H. Nguyen, “Improved convergence in high probability of clipped gradient methods with heavy tailed noise,” inAdvances in Neu- ral Information Processing Systems(A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, eds.), ...

    2023

  7. [15]

    Optimal High-probability Convergence of Nonlinear SGD under Heavy-tailed Noise via Symmetrization,

    A. Armacki, D. Bajovi´ c, D. Jakoveti´ c, and S. Kar, “Optimal High-probability Convergence of Nonlinear SGD under Heavy-tailed Noise via Symmetrization,” arXiv:2507.09093, 2025

    2025

  8. [16]

    Large Deviation Upper Bounds and Improved MSE Rates of Nonlinear SGD: Heavy-Tailed Noise and Power of Symme- try,

    A. Armacki, S. Yu, D. Bajovi´ c, D. Jakoveti´ c, and S. Kar, “Large Deviation Upper Bounds and Improved MSE Rates of Nonlinear SGD: Heavy-Tailed Noise and Power of Symme- try,”SIAM Journal on Optimization, vol. 36, no. 1, pp. 32–59, 2026

    2026

  9. [17]

    Armacki,High-Probability and Large Deviations Techniques for Design and Analysis of Large-Scale and Distributed Learning Systems

    A. Armacki,High-Probability and Large Deviations Techniques for Design and Analysis of Large-Scale and Distributed Learning Systems. PhD thesis, Carnegie Mellon University, 2025

    2025

  10. [18]

    An optimal method for stochastic composite optimization,

    G. Lan, “An optimal method for stochastic composite optimization,”Mathematical Pro- gramming, vol. 133, no. 1-2, pp. 365–397, 2012

    2012

  11. [19]

    Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization,

    E. Hazan and S. Kale, “Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization,”The Journal of Machine Learning Research, vol. 15, no. 1, pp. 2489–2512, 2014

    2014

  12. [20]

    Tight analyses for non-smooth stochastic gradient descent,

    N. J. Harvey, C. Liaw, Y. Plan, and S. Randhawa, “Tight analyses for non-smooth stochastic gradient descent,” inConference on Learning Theory, pp. 1579–1613, PMLR, 2019

    2019

  13. [21]

    A high probability analysis of adaptive sgd with momentum,

    X. Li and F. Orabona, “A high probability analysis of adaptive sgd with momentum,” Workshop on “Beyond first-order methods in ML systems”, 37th International Confer- ence on Machine Learning, 2020

    2020

  14. [22]

    Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods,

    Z. Liu and Z. Zhou, “Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods,” inThe Twelfth International Conference on Learning Representations, 2024

    2024

  15. [23]

    Stochastic optimization with heavy-tailed noise via accelerated gradient clipping,

    E. Gorbunov, M. Danilova, and A. Gasnikov, “Stochastic optimization with heavy-tailed noise via accelerated gradient clipping,”Advances in Neural Information Processing Sys- tems, vol. 33, pp. 15042–15053, 2020

    2020

  16. [24]

    Near-optimal high probability complexity bounds for non-smooth stochastic optimization with heavy- tailed noise,

    E. Gorbunov, M. Danilova, I. Shibaev, P. Dvurechensky, and A. Gasnikov, “Near-optimal high probability complexity bounds for non-smooth stochastic optimization with heavy- tailed noise,”arXiv preprint arXiv:2106.05958, 2021

    2021 arXiv

  17. [25]

    High probability bounds for stochas- tic subgradient schemes with heavy tailed noise,

    D. A. Parletta, A. Paudice, M. Pontil, and S. Salzo, “High probability bounds for stochas- tic subgradient schemes with heavy tailed noise,”arXiv preprint arXiv:2208.08567, 2022. 15

    2022 arXiv

  18. [26]

    High probability guarantees for nonconvex stochastic gradient descent with heavy tails,

    S. Li and Y. Liu, “High probability guarantees for nonconvex stochastic gradient descent with heavy tails,” inInternational Conference on Machine Learning, pp. 12931–12963, PMLR, 2022

    2022

  19. [27]

    General tail bounds for non-smooth stochastic mirror de- scent,

    K. Eldowa and A. Paudice, “General tail bounds for non-smooth stochastic mirror de- scent,”arXiv preprint arXiv:2312.07142, 2023

    2023 arXiv

  20. [28]

    High Probability Convergence Bounds for Non-convex Stochastic Gradient Descent with Sub-Weibull Noise,

    L. Madden, E. Dall’Anese, and S. Becker, “High Probability Convergence Bounds for Non-convex Stochastic Gradient Descent with Sub-Weibull Noise,”Journal of Machine Learning Research, vol. 25, no. 241, pp. 1–36, 2024

    2024

  21. [29]

    High-probability bounds for stochastic optimization and vari- ational inequalities: the case of unbounded variance,

    A. Sadiev, M. Danilova, E. Gorbunov, S. Horv´ ath, G. Gidel, P. Dvurechensky, A. Gas- nikov, and P. Richt´ arik, “High-probability bounds for stochastic optimization and vari- ational inequalities: the case of unbounded variance,” inInternational Conference on Machine Learning...

    2023

  22. [30]

    Breaking the lower bound with (little) structure: Accel- eration in non-convex stochastic optimization with heavy-tailed noise,

    Z. Liu, J. Zhang, and Z. Zhou, “Breaking the lower bound with (little) structure: Accel- eration in non-convex stochastic optimization with heavy-tailed noise,” inProceedings of Thirty Sixth Conference on Learning Theory(G. Neu and L. Rosasco, eds.), vol. 195 of Proceedings of...

    2023

  23. [31]

    From Gradient Clipping to Normalization for Heavy Tailed SGD,

    F. H¨ ubler, I. Fatkhullin, and N. He, “From Gradient Clipping to Normalization for Heavy Tailed SGD,” inThe 28th International Conference on Artificial Intelligence and Statistics, vol. 258, 2025

    2025

  24. [32]

    Sign Operator for Coping with Heavy-Tailed Noise: High Probability Convergence Bounds with Exten- sions to Distributed Optimization and Comparison Oracle,

    N. Kornilov, P. Zmushko, A. Semenov, A. Gasnikov, and A. Beznosikov, “Sign Operator for Coping with Heavy-Tailed Noise: High Probability Convergence Bounds with Exten- sions to Distributed Optimization and Comparison Oracle,”arXiv:2502.07923, 2025

    2025 arXiv

  25. [33]

    High- probability Convergence Bounds for Online Nonlinear Stochastic Gradient Descent un- der Heavy-tailed Noise,

    A. Armacki, S. Yu, P. Sharma, G. Joshi, D. Bajovi´ c, D. Jakoveti´ c, and S. Kar, “High- probability Convergence Bounds for Online Nonlinear Stochastic Gradient Descent un- der Heavy-tailed Noise,” inProceedings of The 28th International Conference on Arti- ficial Intelligence...

    2025

  26. [34]

    Large deviations,

    S. R. S. Varadhan, “Large deviations,”The Annals of Probability, vol. 36, no. 2, pp. 397 – 419, 2008

    2008

  27. [35]

    Ellis,Entropy, Large Deviations, and Statistical Mechanics

    R. Ellis,Entropy, Large Deviations, and Statistical Mechanics. Springer Berlin, Heidel- berg, 11 2005

    2005

  28. [36]

    The large deviation approach to statistical mechanics,

    H. Touchette, “The large deviation approach to statistical mechanics,”Physics Reports, vol. 478, no. 1, pp. 1–69, 2009

    2009

  29. [37]

    Distributed detection via gaussian running consensus: Large deviations asymptotic analysis,

    D. Bajovi´ c, D. Jakoveti´ c, J. Xavier, B. Sinopoli, and J. M. F. Moura, “Distributed detection via gaussian running consensus: Large deviations asymptotic analysis,”IEEE Transactions on Signal Processing, vol. 59, no. 9, pp. 4381–4396, 2011

    2011

  30. [38]

    Large deviations performance of consensus+innovations distributed detection with non-gaussian observa- tions,

    D. Bajovi´ c, D. Jakoveti´ c, J. M. F. Moura, J. Xavier, and B. Sinopoli, “Large deviations performance of consensus+innovations distributed detection with non-gaussian observa- tions,”IEEE Transactions on Signal Processing, vol. 60, no. 11, pp. 5987–6002, 2012. 16

    2012

  31. [39]

    Large deviations analysis of adaptive distributed detection,

    P. Braca, S. Marano, V. Matta, and A. H. Sayed, “Large deviations analysis of adaptive distributed detection,” in2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 6112–6116, 2014

    2014

  32. [40]

    Diffusion-Based Adaptive Distributed Detection: Steady-State Performance in the Slow Adaptation Regime,

    V. Matta, P. Braca, S. Marano, and A. H. Sayed, “Diffusion-Based Adaptive Distributed Detection: Steady-State Performance in the Slow Adaptation Regime,”IEEE Transac- tions on Information Theory, vol. 62, no. 8, pp. 4710–4732, 2016

    2016

  33. [41]

    Distributed Detection Over Adaptive Networks: Refined Asymptotics and the Role of Connectivity,

    V. Matta, P. Braca, S. Marano, and A. H. Sayed, “Distributed Detection Over Adaptive Networks: Refined Asymptotics and the Role of Connectivity,”IEEE Transactions on Signal and Information Processing over Networks, vol. 2, no. 4, pp. 442–460, 2016

    2016

  34. [42]

    Adaptive social learning,

    V. Bordignon, V. Matta, and A. H. Sayed, “Adaptive social learning,”IEEE Transactions on Information Theory, vol. 67, no. 9, pp. 6053–6081, 2021

    2021

  35. [43]

    Inaccuracy rates for distributed inference over random networks with ap- plications to social learning,

    D. Bajovi´ c, “Inaccuracy rates for distributed inference over random networks with ap- plications to social learning,”IEEE Transactions on Information Theory, vol. 70, no. 1, pp. 415–435, 2024

    2024

  36. [44]

    Matta, V

    V. Matta, V. Bordignon, and A. H. Sayed,Social Learning: Opinion Formation and Decision-Making over Graphs. Emerald Publishing Limited, 2025

    2025

  37. [45]

    Statistical hypothesis testing based on machine learning: Large deviations analysis,

    P. Braca, L. M. Millefiori, A. Aubry, S. Marano, A. De Maio, and P. Willett, “Statistical hypothesis testing based on machine learning: Large deviations analysis,”IEEE Open Journal of Signal Processing, vol. 3, pp. 464–495, 2022

    2022

  38. [46]

    Lindhe,Topics on Large Deviations in Artificial Intelligence

    A. Lindhe,Topics on Large Deviations in Artificial Intelligence. PhD thesis, KTH Royal Institute of Technology, 2023

    2023

  39. [47]

    On the diffusion approximation of nonconvex stochastic gradient descent,

    W. Hu, C. J. Li, L. Li, and J.-G. Liu, “On the diffusion approximation of nonconvex stochastic gradient descent,”Annals of Mathematical Sciences and Applications, vol. 4, no. 1, pp. 3–32, 2019

    2019

  40. [48]

    Large deviations rates for stochastic gradient descent with strongly convex functions,

    D. Bajovi´ c, D. Jakoveti´ c, and S. Kar, “Large deviations rates for stochastic gradient descent with strongly convex functions,” inProceedings of The 26th International Con- ference on Artificial Intelligence and Statistics(F. Ruiz, J. Dy, and J.-W. van de Meent, eds.), vol....

    2023

  41. [49]

    A large deviations perspective on policy gradient algorithms,

    W. Jongeneel, D. Kuhn, and M. Li, “A large deviations perspective on policy gradient algorithms,” inProceedings of the 6th Annual Learning for Dynamics and Control Con- ference(A. Abate, M. Cannon, K. Margellos, and A. Papachristodoulou, eds.), vol. 242 ofProceedings of Machin...

    2024

  42. [50]

    What is the long-run distri- bution of stochastic gradient descent? A large deviations analysis,

    W. Azizian, F. Iutzeler, J. Malick, and P. Mertikopoulos, “What is the long-run distri- bution of stochastic gradient descent? A large deviations analysis,” inProceedings of the 41st International Conference on Machine Learning, vol. 235 ofProceedings of Machine Learning Resea...

    2024

  43. [51]

    The global convergence of stochastic gradient descent in non-convex landscapes: Sharp estimates via large devia- tions,

    W. Azizian, F. Iutzeler, J. Malick, and P. Mertikopoulos, “The global convergence of stochastic gradient descent in non-convex landscapes: Sharp estimates via large devia- tions,” inICML 2025-42nd International Conference on Machine Learning, 2025. 17

    2025

  44. [52]

    Accelerated gradient methods with biased gradient estimates: Risk sensitivity, high-probability guarantees, and large deviation bounds,

    M. G¨ urb¨ uzbalaban, Y. Syed, and N. S. Aybat, “Accelerated gradient methods with biased gradient estimates: Risk sensitivity, high-probability guarantees, and large deviation bounds,”arXiv preprint arXiv:2509.13628, 2025

    2025

  45. [53]

    On the difficulty of training recurrent neu- ral networks,

    R. Pascanu, T. Mikolov, and Y. Bengio, “On the difficulty of training recurrent neu- ral networks,” inProceedings of the 30th International Conference on Machine Learning (S. Dasgupta and D. McAllester, eds.), vol. 28 ofProceedings of Machine Learning Re- search, (Atlanta, Geo...

    2013

  46. [54]

    A tail-index analysis of stochastic gra- dient noise in deep neural networks,

    U. Simsekli, L. Sagun, and M. Gurbuzbalaban, “A tail-index analysis of stochastic gra- dient noise in deep neural networks,” inInternational Conference on Machine Learning, pp. 5827–5837, PMLR, 2019

    2019

  47. [55]

    Why are adaptive methods good for attention models?,

    J. Zhang, S. P. Karimireddy, A. Veit, S. Kim, S. Reddi, S. Kumar, and S. Sra, “Why are adaptive methods good for attention models?,”Advances in Neural Information Processing Systems, vol. 33, pp. 15383–15393, 2020

    2020

  48. [56]

    The heavy-tail phenomenon in sgd,

    M. Gurbuzbalaban, U. Simsekli, and L. Zhu, “The heavy-tail phenomenon in sgd,” in Proceedings of the 38th International Conference on Machine Learning, vol. 139 ofPro- ceedings of Machine Learning Research, pp. 3964–3975, PMLR, 18–24 Jul 2021

    2021

  49. [57]

    Why gradient clipping accelerates train- ing: A theoretical justification for adaptivity,

    J. Zhang, T. He, S. Sra, and A. Jadbabaie, “Why gradient clipping accelerates train- ing: A theoretical justification for adaptivity,” inInternational Conference on Learning Representations, 2019

    2019

  50. [58]

    Understanding Clipping for Feder- ated Learning: Convergence and Client-Level Differential Privacy,

    X. Zhang, X. Chen, M. Hong, S. Wu, and J. Yi, “Understanding Clipping for Feder- ated Learning: Convergence and Client-Level Differential Privacy,” inProceedings of the 39th International Conference on Machine Learning, vol. 162 ofProceedings of Machine Learning Research, pp. ...

    2022

  51. [59]

    Llama: Open and efficient foundation language models,

    H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozi` ere, N. Goyal, E. Hambro, F. Azhar,et al., “Llama: Open and efficient foundation language models,”arXiv preprint arXiv:2302.13971, 2023

    2023 arXiv

  52. [60]

    Deepseek-v3 technical report,

    A. Liu, B. Feng, B. Xue, B. Wang, B. Wu, C. Lu, C. Zhao, C. Deng, C. Zhang, C. Ruan, et al., “Deepseek-v3 technical report,”arXiv preprint arXiv:2412.19437, 2024

    2024 arXiv

  53. [61]

    Safe model-based reinforce- ment learning with stability guarantees,

    F. Berkenkamp, M. Turchetta, A. Schoellig, and A. Krause, “Safe model-based reinforce- ment learning with stability guarantees,” inAdvances in Neural Information Processing Systems, vol. 30, Curran Associates, Inc., 2017

    2017

  54. [62]

    On the almost sure conver- gence of stochastic gradient descent in non-convex problems,

    P. Mertikopoulos, N. Hallak, A. Kavis, and V. Cevher, “On the almost sure conver- gence of stochastic gradient descent in non-convex problems,” inAdvances in Neural Information Processing Systems, vol. 33, pp. 1117–1128, Curran Associates, Inc., 2020

    2020

  55. [63]

    Efficient and accu- rate estimation of lipschitz constants for deep neural networks,

    M. Fazlyab, A. Robey, H. Hassani, M. Morari, and G. Pappas, “Efficient and accu- rate estimation of lipschitz constants for deep neural networks,” inAdvances in Neural Information Processing Systems, vol. 32, Curran Associates, Inc., 2019

    2019

  56. [64]

    On lipschitz bounds of general convolutional neural networks,

    D. Zou, R. Balan, and M. Singh, “On lipschitz bounds of general convolutional neural networks,”IEEE Transactions on Information Theory, vol. 66, no. 3, pp. 1738–1759, 2020. 18

    2020

  57. [65]

    Lipschitz certificates for layered network struc- tures driven by averaged activation operators,

    P. L. Combettes and J.-C. Pesquet, “Lipschitz certificates for layered network struc- tures driven by averaged activation operators,”SIAM Journal on Mathematics of Data Science, vol. 2, no. 2, pp. 529–557, 2020

    2020

  58. [66]

    Rethinking lipschitz neural networks and certified robustness: A boolean function perspective,

    B. Zhang, D. Jiang, D. He, and L. Wang, “Rethinking lipschitz neural networks and certified robustness: A boolean function perspective,” inAdvances in Neural Information Processing Systems, vol. 35, pp. 19398–19413, Curran Associates, Inc., 2022

    2022

  59. [67]

    The lipschitz constant of self-attention,

    H. Kim, G. Papamakarios, and A. Mnih, “The lipschitz constant of self-attention,” in Proceedings of the 38th International Conference on Machine Learning, vol. 139 ofPro- ceedings of Machine Learning Research, pp. 5562–5571, PMLR, 2021

    2021

  60. [68]

    Improved analysis of clipping algorithms for non-convex optimization,

    B. Zhang, J. Jin, C. Fang, and L. Wang, “Improved analysis of clipping algorithms for non-convex optimization,” inAdvances in Neural Information Processing Systems (H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, eds.), vol. 33, pp. 15511– 15521, Curran Associate...

    2020

  61. [69]

    Convergence of adam under relaxed assump- tions,

    H. Li, A. Rakhlin, and A. Jadbabaie, “Convergence of adam under relaxed assump- tions,” inAdvances in Neural Information Processing Systems(A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, eds.), vol. 36, pp. 52166–52196, Curran Associates, Inc., 2023

    2023

  62. [70]

    The price of adaptivity in stochastic convex optimization,

    Y. Carmon and O. Hinder, “The price of adaptivity in stochastic convex optimization,” inProceedings of Thirty Seventh Conference on Learning Theory, vol. 247 ofProceedings of Machine Learning Research, pp. 772–774, PMLR, 2024

    2024

  63. [71]

    Making gradient descent optimal for strongly convex stochastic optimization,

    A. Rakhlin, O. Shamir, and K. Sridharan, “Making gradient descent optimal for strongly convex stochastic optimization,” inProceedings of the 29th International Coference on International Conference on Machine Learning, pp. 1571–1578, 2012

    2012

  64. [72]

    Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework,

    S. Ghadimi and G. Lan, “Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework,”SIAM Journal on Optimization, vol. 22, no. 4, pp. 1469–1492, 2012

    2012

  65. [73]

    An improved analysis of stochastic gradient descent with momentum,

    Y. Liu, Y. Gao, and W. Yin, “An improved analysis of stochastic gradient descent with momentum,”Advances in Neural Information Processing Systems, vol. 33, pp. 18261– 18271, 2020

    2020

  66. [74]

    Distributed Pareto Optimization via Diffusion Strategies,

    J. Chen and A. H. Sayed, “Distributed Pareto Optimization via Diffusion Strategies,” IEEE Journal of Selected Topics in Signal Processing, vol. 7, no. 2, pp. 205–220, 2013

    2013

  67. [75]

    Better theory for SGD in the nonconvex world,

    A. Khaled and P. Richt´ arik, “Better theory for SGD in the nonconvex world,”Transac- tions on Machine Learning Research, 2023

    2023

  68. [76]

    Non- linear gradient mappings and stochastic optimization: A general framework with appli- cations to heavy-tail noise,

    D. Jakoveti´ c, D. Bajovi´ c, A. K. Sahu, S. Kar, N. Miloˇ sevi´ c, and D. Stamenkovi´ c, “Non- linear gradient mappings and stochastic optimization: A general framework with appli- cations to heavy-tail noise,”SIAM Journal on Optimization, vol. 33, no. 2, pp. 394–423, 2023

    2023

  69. [77]

    Nonconvex stochastic optimization under heavy-tailed noises: Op- timal convergence without gradient clipping,

    Z. Liu and Z. Zhou, “Nonconvex stochastic optimization under heavy-tailed noises: Op- timal convergence without gradient clipping,”ICLR, 2025. 19

    2025

  70. [78]

    Revisiting gradient normalization and clipping for non- convex sgd under heavy-tailed noise: Necessity, sufficiency, and acceleration,

    T. Sun, X. Liu, and K. Yuan, “Revisiting gradient normalization and clipping for non- convex sgd under heavy-tailed noise: Necessity, sufficiency, and acceleration,”Journal of Machine Learning Research, vol. 26, no. 237, pp. 1–42, 2025

    2025

  71. [79]

    Gradient convergence in gradient methods with errors,

    D. P. Bertsekas and J. N. Tsitsiklis, “Gradient convergence in gradient methods with errors,”SIAM Journal on Optimization, vol. 10, no. 3, pp. 627–642, 2000

    2000

  72. [80]

    On the convergence of stochastic gradient descent with adaptive stepsizes,

    X. Li and F. Orabona, “On the convergence of stochastic gradient descent with adaptive stepsizes,” inProceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics(K. Chaudhuri and M. Sugiyama, eds.), vol. 89 ofProceedings of Machine Learni...

    2019

  73. [81]

    Almost sure convergence rates for stochastic gradient descent and stochastic heavy ball,

    O. Sebbouh, R. M. Gower, and A. Defazio, “Almost sure convergence rates for stochastic gradient descent and stochastic heavy ball,” inProceedings of Thirty Fourth Conference on Learning Theory, vol. 134 ofProceedings of Machine Learning Research, pp. 3935– 3971, PMLR, 15–19 Aug 2021

    2021

  74. [82]

    Convex and non-convex opti- mization under generalized smoothness,

    H. Li, J. Qian, Y. Tian, A. Rakhlin, and A. Jadbabaie, “Convex and non-convex opti- mization under generalized smoothness,” inAdvances in Neural Information Processing Systems(A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, eds.), vol. 36, pp. 40238–40271,...

    2023

  75. [83]

    Does Standard Nonconvex SGD Really Diverge under Heavy-Tailed Noise?

    T. Sun, “Does Standard Nonconvex SGD Really Diverge under Heavy-Tailed Noise?.” ResearchGate Preprint, 2025

    2025

  76. [84]

    Can sgd handle heavy-tailed noise?,

    I. Fatkhullin, F. H¨ ubler, and G. Lan, “Can sgd handle heavy-tailed noise?,” inOPT25 Workshop at NeurlPS: Optimization for Machine Learning, 2025

    2025

  77. [85]

    NIST Digital Library of Mathematical Functions

    “NIST Digital Library of Mathematical Functions.”https://dlmf.nist.gov/, Release 1.2.5 of 2025-12-15, 2025. F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds

    2025

  78. [86]

    Robust Estimation of a Location Parameter,

    P. J. Huber, “Robust Estimation of a Location Parameter,”The Annals of Mathematical Statistics, vol. 35, no. 1, pp. 73 – 101, 1964

    1964

  79. [87]

    Gradient Based Clustering,

    A. Armacki, D. Bajovi´ c, D. Jakoveti´ c, and S. Kar, “Gradient Based Clustering,” in Proceedings of the 39th International Conference on Machine Learning, vol. 162 ofPro- ceedings of Machine Learning Research, pp. 929–947, PMLR, 2022. 20 A Introduction The appendix contains r...

    2022

  80. [88]

    As mentioned in Section 3.1, we consider the batch setting, where the costfis of the formf(x) = 1 m P i∈[m] ℓ(x;ξ i), for some finite dataset{ξ i}i∈[m] and the lossℓhasG-bounded gradients, i.e.,∥∇ℓ(x;ξ i)∥ ≤G, for allx∈R d and everyi∈[m] (e.g., satisfied by any G-Lipschitz los...

  81. [89]

    The noise isM-sub-Gaussian, i.e., we haveE h exp ∥zt∥2 M 2 Ft i ≤exp(1)

  82. [90]

    Proof.The first claim follows directly from Assumption 3 and Definition 1

    For anyF t-measurable vectorx∈R d, we haveE exp ⟨x, zt⟩ | Ft ≤exp 3M 2∥x∥2 4 . Proof.The first claim follows directly from Assumption 3 and Definition 1. To prove the second claim, we follow a similar approach to, e.g., [21, Lemma 1]. For ease of notation, let yt := zt M and n...

  83. [91]

    For anyF t-measurablex∈R d, we haveE exp ⟨x, θu t ⟩ | Ft ≤exp 3γ2 t ∥x∥2 . Proof.To prove the first claim, we use Assumption 2 and the fact that, for anyt≥1 ∥∇f(x t)∥ ≤G≤ γt 2 , where the second inequality follows from the choice of clipping threshold in (5). The claim now fol...

  84. [92]

    For allt≥B p, we have∥θ b t ∥ ≤4σpγ1−p t , whereB p =    2G C 6p−4 2−p , p∈(1,2) 2 4G2/C2 −1, p= 2

  85. [93]

    Proof.To prove the first part, note that from Assumption 2, the choice of clipping threshold in (42) and the definition ofB p, we have, for anyt≥B p ∥∇f(x t)∥ ≤G≤ γt 2

    For allt≥1and anyF t-measurablex∈R d, we haveE exp ⟨x, θu t ⟩ |Ft ≤exp 3γ2 t ∥x∥2 . Proof.To prove the first part, note that from Assumption 2, the choice of clipping threshold in (42) and the definition ofB p, we have, for anyt≥B p ∥∇f(x t)∥ ≤G≤ γt 2 . The claim now readily f...

  86. [94]

    Ifp∈(1,2), the decay rate isn t = t 4(p−1) 3p−2 log(t) , with rate function given byI c(x) =( x2 192C2G2 , x≥0 +∞, x <0

  87. [95]

    Proof.Recall that we showed the following inequality in Appendix F, for allk≥1 f(x k+1)≤f(x k)− αk 2 ∥∇f(x k)∥2 −α k⟨∇f(x k), θu k ⟩+ αk 2 ∥θb k∥2 + α2 kγ2 kL 2

    Ifp= 2, the decay rate isn t = t log2(t) , with rate function given byI c(x) = ( x2 96C2G2 , x≥0 +∞, x <0. Proof.Recall that we showed the following inequality in Appendix F, for allk≥1 f(x k+1)≤f(x k)− αk 2 ∥∇f(x k)∥2 −α k⟨∇f(x k), θu k ⟩+ αk 2 ∥θb k∥2 + α2 kγ2 kL 2 . Rearran...

Pith tools

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