betaFeedback

WorksMathematics

Acceleration Survives Heavy Tails and Generalized Smoothness

Abstract

We establish high-probability accelerated convergence guarantees for convex (L0,L1)(L_0,L_1)-smooth optimization with unbiased stochastic gradients under heavy-tailed noise, assuming a central αα-th noise moment bounded by σασ^α, α∈(1,2]α\in(1,2]. Such guarantees are known under classical LL-smoothness, but extending them through localization over an O(R)O(R)-radius ball may introduce an eO(L1R)e^{O(L_1R)} factor. We avoid this dependence in two ways. First, a two-phase scheme uses Clip-SGD to reach a low-curvature regime, after which clipped stochastic similar triangles (Clip-SSTM) attains, with probability at least 1−δ1-δ, f(yK)−f⋆≤O~(L0R2/K2+σRK−(α−1)/α),f(y_K)-f^\star\le\widetilde{\mathcal O}\big(L_0R^2/K^2+σRK^{-(α-1)/α}\big), where RR bounds the distance from the Phase-II starting point to a minimizer. Second, a modified deterministic weight schedule allows Clip-SSTM to start directly from the initial point, controlling the high-curvature transient before recovering acceleration. With the prescribed initialization, both approaches recover the classical accelerated rate, with L1L_1 confined to an accuracy-independent transient, up to logarithmic factors. The two-phase analysis uses two coupled potentials to preserve the low-curvature regime despite momentum; the one-phase analysis controls the initial high-curvature regime using a modified version of the classical SSTM weight schedule.

Introduction

Accelerated stochastic optimization is well understood under classical smoothness, where the gradient is globally Lipschitz. Two additional difficulties arise in settings relevant to modern learning. First, the local smoothness of the objective may grow with the gradient norm, a dependence observed by Zhang et al. [24] along training trajectories. Second, stochastic gradient noise can be heavy-tailed, as observed, for example, in BERT pre-training ([25]). Together, these effects make acceleration challenging: high curvature may require smaller steps, while large stochastic gradient errors can be amplified by momentum. Gradient clipping can limit the effect of such errors, but introduces bias that must also be controlled. Under classical LL-smoothness, high-probability accelerated guarantees under heavy-tailed noise have been established by Sadiev et al. [18]; Nguyen et al. [17].

The (L0,L1)(L_0,L_1)-smoothness condition provides a natural model for such nonuniform curvature. For twice-differentiable objectives, this dependence is captured by

∥∇2f(x)∥≤L0+L1∥∇f(x)∥\lVert\nabla^2 f(x) \rVert\le L_0 + L_1 \lVert\nabla f(x) \rVert

(Zhang et al. [24]). First-order formulations for continuously differentiable functions were studied by Zhang et al. [23] and Chen et al. [1]; we adopt the formulation in Assumption 2. In this model, the curvature can be large when the gradient norm is large, while becoming comparable to L0L_0 when ∥∇f(x)∥\lVert\nabla f(x) \rVert is of order L0/L1L_0/L_1.

A natural approach is to take an accelerated method with guarantees under classical smoothness, show that its iterates remain in a ball of radius O(R)O(R) (Sadiev et al. [18]), and use (L0,L1)(L_0,L_1)-smoothness to obtain an effective smoothness constant over this ball. One could then apply the standard accelerated analysis with this local constant. However, the resulting smoothness parameter can be as large as L0exp⁡(O(L1R))L_0 \exp(O(L_1R)), leading to an exponential dependence on L1RL_1R.

Deterministic acceleration under generalized smoothness has been studied in several recent works. Gorbunov et al. [9] proposed an accelerated Similar Triangles method for convex (L0,L1)(L_0,L_1)-smooth optimization, although its convergence guarantee retains an exponential dependence on L1RL_1R, where RR bounds the initial distance to a minimizer. Vankov et al. [21] subsequently established accelerated guarantees without such an exponential dependence, using a method that requires solving a one-dimensional line-search subproblem at each iteration, making a direct extension to stochastic gradients nontrivial. More recently, Tyurin [20] obtained deterministic accelerated guarantees under an ℓ\ell-smoothness assumption that generalizes (L0,L1)(L_0,L_1)-smoothness. They consider both a gradient-descent warm start followed by acceleration and a method that starts directly from the initial point, adjusting its stepsizes to control the initial high-curvature regime. Under (L0,L1)(L_0,L_1)-smoothness, these methods recover an L1L_1-independent leading high-accuracy rate after an initial transient. Our two-phase and one-phase approaches follow similar principles, but use Clip-SSTM with different weight choices. The additional challenge is to control curvature and accumulated clipping errors simultaneously along the accelerated trajectory, with high probability under heavy-tailed noise.

Stochastic accelerated-gradient methods under (L0,L1)(L_0,L_1)-smoothness have also been analyzed recently. Yu et al. (2025) study randomized stochastic accelerated gradient methods under (L0,L1)(L_0,L_1)-smoothness and relaxed affine noise assumptions, obtaining high-probability convergence guarantees for convex optimization; their analysis, however, does not yield an accelerated convergence rate in this setting. Dvinskikh et al. [4] establish high-probability accelerated guarantees for convex (L0,L1)(L_0,L_1)-smooth optimization under unbiased stochastic gradients with additive norm-sub-Gaussian noise, while avoiding an exponential dependence on L1RL_1R. Their guarantees assume light-tailed noise, whereas we assume only a bounded central α\alpha-th moment with α∈(1,2]\alpha\in(1,2], which is a weaker condition.

This gap raises a natural question:

Can classical clipped accelerated schemes achieve high-probability acceleration under (L0,L1)(L_0,L_1)-smoothness and heavy-tailed noise without exponential dependence on L1RL_1R?

We answer affirmatively.

Our contributions. Under Assumptions 1 (convexity), Assumptions 2 ((L0,L1)(L_0,L_1)-smoothness), and Assumptions 3 (bounded central α\alpha-th moment, α∈(1,2]\alpha\in(1,2]), we establish high-probability accelerated guarantees for two approaches. Let ∥x0−x⋆∥≤R0\lVert x_0-x^\star\rVert\le R_0. Our total complexity bounds avoid exponential dependence on L1R0L_1R_0.

  • Two-phase acceleration. We use a nonaccelerated method as a warm start to obtain a point xˉ\bar{x} satisfying f(xˉ)−f⋆≤cL0/L12f(\bar{x})-f^\star\le cL_0/L_1^2, an accuracy-independent threshold implying ∥∇f(xˉ)∥=O(L0/L1)\lVert\nabla f(\bar{x})\rVert= O(L_0/L_1) with high probability. Starting from xˉ\bar{x}, Clip-SSTM satisfies, with probability at least 1−δ1-\delta,

f(yK)−f⋆≤O~(L0R2/K2+σRK−(α−1)/α)f(y_K)-f^\star\le\widetilde{O}\left(L_0R^2/K^2+\sigma RK^{-(\alpha-1)/\alpha}\right)

after KK additional stochastic gradient evaluations, where ∥xˉ−x⋆∥≤R\lVert\bar{x}-x^\star\rVert\le R and O~\widetilde{O} hides logarithmic factors in KK and 1/δ1/\delta. The analysis couples two potentials, anchored at xˉ\bar{x} and x⋆x^\star, to keep the accelerated trajectory in the low-curvature region despite momentum.

  • One-phase acceleration. Clip-SSTM can also start directly from x0x_0, using a modified deterministic weight schedule to control the high-curvature transient before recovering acceleration. With the prescribed initialization, it recovers the classical LL-smooth accelerated rate after a transient that is accuracy-independent up to logarithmic factors. Here the distance bound is R0R_0.

Complexity guarantees. For the two-phase method, the warm start also guarantees ∥xˉ−x⋆∥≤2R0\lVert\bar{x}-x^\star\rVert\le2R_0 on its success event, so the accelerated phase can use R=2R0R=2R_0. Including the warm-start cost, Corollary 1 ensures f(y)−f⋆≤εf(y)-f^\star\le\varepsilon with probability at least 1−δ1-\delta using

O~(1+(L1R0)2+L0R02ε+(σR0ε)αα−1)\widetilde{O}\left(1+(L_1R_0)^2+\sqrt{\frac{L_0R_0^2}{\varepsilon}}+\left(\frac{\sigma R_0}{\varepsilon}\right)^{\frac{\alpha}{\alpha-1}}\right)

stochastic gradient evaluations. For the one-phase method, Theorem 2 with the initialization in Remark 1 ensures f(yK)−f⋆≤εf(y_K)-f^\star\le\varepsilon with the same probability using

O~(K0+L0R02ε+(σR0ε)αα−1)\widetilde{O}\left(K_0+\sqrt{\frac{L_0R_0^2}{\varepsilon}}+\left(\frac{\sigma R_0}{\varepsilon}\right)^{\frac{\alpha}{\alpha-1}}\right)

stochastic gradient evaluations. The transient K0K_0 depends logarithmically on the initial-gap bound. Using the worst-case gap bound gives K0=O~((1+L1R0)2)K_0=\widetilde{O}((1+L_1R_0)^2); a tighter bound can give a smaller transient. Up to logarithmic factors and an additional initial transient, both methods recover the complexity of accelerated methods for classical LL-smooth convex optimization under heavy-tailed noise, with LL replaced by L0L_0. The dependence on L1L_1 is confined to the transient.

Table 1: Comparison with related results for convex optimization. HP denotes a high-probability guarantee. Here α\alpha-moment means bounded central α\alpha-th moment noise, α∈(1,2]\alpha\in(1, 2], and “No exp. dep.” means no exponential dependence on L1RL_{1}R (or H1R\sqrt{H_{1}}R under (H0,H1)(H_{0}, H_{1})-smoothness).

ReferenceSmoothnessNoiseHPAccel. rateNo exp. dep.
Classical LL-smooth optimization under heavy-tailed noise
Sadiev et al. [18]LL-smoothα\alpha-moment✓✓N/A
Nguyen et al. [17]LL-smoothα\alpha-moment✓✓N/A
(L0,L1)(L_{0}, L_{1})-smooth optimization: nonaccelerated guarantees
Gorbunov et al. [9] (nonaccel.)(L0,L1)(L_{0}, L_{1})Det.N/A✗✓
Vankov et al. [21] (nonaccel.)(L0,L1)(L_{0}, L_{1})Det.N/A✗✓
Lobanov et al. [14](L0,L1)(L_{0}, L_{1})Det.N/A✗✓
Gaash et al. [6](L0,L1)(L_{0}, L_{1})sub-Gaussian✓✗✓
El Bakkali El Kadi et al. (2026)(L0,L1)(L_{0}, L_{1})α\alpha-moment✓✗✓
Generalized-smooth optimization: acceleration and momentum methods
Gorbunov et al. [9] (accelerated)(L0,L1)(L_{0}, L_{1})Det.N/A✓✗
Vankov et al. [21] (accelerated)1(L0,L1)(L_{0}, L_{1})Det.N/A✓✓
Tyurin [20]ℓ\ell-smoothDet.N/A✓✓
Yu et al. (2025)2(L0,L1)(L_{0}, L_{1})relaxed affine noise✓✗✓
Dvinskikh et al. [4](L0,L1)(L_{0}, L_{1})norm-sub-Gaussian✓✓✓
Lobanov et al. [13]3(H0,H1)(H_{0}, H_{1})generalized α\alpha-moment✓✓✓
This work(L0,L1)(L_{0}, L_{1})α\alpha-moment✓✓✓

Table 1.

Det. = deterministic. 1 Vankov et al. [21] use a one-dimensional line search with function values for their accelerated method. 2 Yu et al. (2025) analyze stochastic accelerated-gradient schemes under relaxed affine almost-sure noise, with a sub-Gaussian extension. Their convex high-probability guarantee does not establish an accelerated rate. 3 Concurrent work. Lobanov et al. [13] consider (H0,H1)(H_{0}, H_{1})-smoothness and a generalized central moment bound with constant, gradient-dependent, and objective-gap-dependent terms. Their method uses projections and phase restarts; our methods require neither projections nor repeated restarts. See the discussion of concurrent work for details.

Preliminaries

Notation. We work in Rd\mathbb{R}^{d}, equipped with the standard Euclidean inner product ⟨⋅,⋅⟩\langle\cdot, \cdot\rangle and norm ∥⋅∥\lVert\cdot\rVert. For λ>0\lambda> 0, let B(0,λ):={x∈Rd:∥x∥≤λ}B(0, \lambda) := \{x \in\mathbb{R}^{d} : \lVert x \rVert\le\lambda\}. We define the clipping operator clip⁡(x,λ)\operatorname{clip}(x, \lambda) as the Euclidean projection onto this ball:

clip⁡(x,λ):=ΠB(0,λ)(x)={x,∥x∥≤λ,λ∥x∥x,∥x∥>λ.\operatorname{clip}(x, \lambda) := \Pi_{B(0,\lambda)}(x) = \begin{cases} x, & \lVert x \rVert\le\lambda,\\ \frac{\lambda}{\lVert x \rVert}x, & \lVert x \rVert> \lambda. \end{cases}

References

  1. [1]Chen, Z., Zhou, Y., Liang, Y., and Lu, Z. (2023). Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization. In International Conference on Machine Learning, pages 5396–5427. PMLR.arxiv.org/abs/2303.02854
  2. [2]Chezhegov, S., Klyukin, Y., Semenov, A., Beznosikov, A., Gasnikov, A., Horváth, S., Takač, M., and Gorbunov, E. (2024). Clipping improves Adam-norm and AdaGrad-norm when the noise is heavy-tailed. arXiv preprint arXiv:2406.04443.arxiv.org/abs/2406.04443
  3. [3]Cutkosky, A. and Mehta, H. (2021). High-probability bounds for non-convex stochastic optimization with heavy tails. Advances in Neural Information Processing Systems, 34:4883–4895.arxiv.org/abs/2106.14343
  4. [4]Dvinskikh, D., Gasnikov, A., Lobanov, A., and Latypov, I. (2026). Localize, restart, accelerate: Stochastic optimization under generalized smoothness. arXiv preprint arXiv:2609.06555.arxiv.org/abs/2609.06555
  5. [5]El Bakkali El Kadi, T., Chezhegov, S., Beznosikov, A., Horváth, S., and Gorbunov, E. (2026). High-probability convergence of clipped SGD under heavy-tailed noise and (L_0, L_1)-smoothness. arXiv preprint arXiv:2505.20817.
  6. [6]Gaash, O., Levy, K. Y., and Carmon, Y. (2025). Convergence of clipped SGD on convex (L_0, L_1)-smooth functions. arXiv preprint arXiv:2502.16492.
  7. [7]Ghadimi, S. and Lan, G. (2013). Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341–2368.DOI
  8. [8]Gorbunov, E., Danilova, M., and Gasnikov, A. (2020). Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. Advances in Neural Information Processing Systems, 33:15042–15053.arxiv.org/abs/2005.10785
  9. [9]Gorbunov, E., Tupitsa, N., Choudhury, S., Aliev, A., Richtárik, P., Horváth, S., and Takač, M. (2025). Methods for convex (L_0, L_1)-smooth optimization: Clipping, acceleration, and adaptivity. In International Conference on Learning Representations, volume 2025, pages 97261–97305.
  10. [10]Koloskova, A., Hendrikx, H., and Stich, S. U. (2023). Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In International Conference on Machine Learning, pages 17343–17363. PMLR.
  11. [13]Lobanov, A., Dvinskikh, D., and Gasnikov, A. (2026). Accelerated stochastic method under $(H_0,H_1)$-smoothness and heavy-tailed noise. arXiv:2609.33415.arxiv.org/abs/2609.33415
  12. [14]Lobanov, A., Gasnikov, A., Gorbunov, E., and Takáč, M. (2024). Linear convergence rate in convex setup is possible! gradient descent method variants under $(L_0,L_1)$-smoothness. arXiv preprint arXiv:2412.17050.arxiv.org/abs/2412.17050
  13. [15]Nazin, A. V., Nemirovsky, A. S., Tsybakov, A. B., and Juditsky, A. B. (2019). Algorithms of robust stochastic optimization based on mirror descent method. Automation and Remote Control, 80:1607–1627.arxiv.org/abs/1907.02707
  14. [16]Nemirovski, A. S., Juditsky, A. B., Lan, G., and Shapiro, A. (2009). Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574–1609.DOI
  15. [17]Nguyen, T. D., Nguyen, T. H., Ene, A., and Nguyen, H. (2023). Improved convergence in high probability of clipped gradient methods with heavy tailed noise. In Thirty-seventh Conference on Neural Information Processing Systems.DOI
  16. [18]Sadiev, A., Danilova, M., Gorbunov, E., Horváth, S., Gidel, G., Dvurechensky, P., Gasnikov, A., and Richtárik, P. (2023). High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J., editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 29563–29648. PMLR.arxiv.org/abs/2302.00999
  17. [19]Takáč, M., Bijral, A., Richtárik, P., and Srebro, N. (2013). Mini-batch primal and dual methods for SVMs. In 30th International Conference on Machine Learning (ICML 2013).arxiv.org/abs/1303.2314
  18. [20]Tyurin, A. (2026). Near-optimal convergence of accelerated gradient methods under generalized and $(L_0,L_1)$-smoothness. In Zhang, T., Dudik, M., Jaggi, M., Agarwal, A., Li, S., Schuurmans, D., Zhu, J., Berkenkamp, F., Dong, H., and Bietti, A., editors, Proceedings of the 43rd International Conference on Machine Learning, volume 306 of Proceedings of Machine Learning Research, pages 122876–122905. PMLR.arxiv.org/abs/2508.06884
  19. [21]Vankov, D., Rodomanov, A., Nedich, A., Sankar, L., and Stich, S. (2025). Optimizing $(L_0,L_1)$-smooth functions by gradient methods. In International Conference on Learning Representations, volume 2025, pages 15953–15979.arxiv.org/abs/2410.10800
  20. [23]Zhang, B., Jin, J., Fang, C., and Wang, L. (2020a). Improved analysis of clipping algorithms for non-convex optimization. In Advances in Neural Information Processing Systems.arxiv.org/abs/2010.02519
  21. [24]Zhang, J., He, T., Sra, S., and Jadbabaie, A. (2020b). Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations.arxiv.org/abs/1905.11881
  22. [25]Zhang, J., Karimireddy, S. P., Veit, A., Kim, S., Reddi, S., Kumar, S., and Sra, S. (2020c). Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33:15383–15393.arxiv.org/abs/1912.03194

Paper details

vlnc:W_65xghpca
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 4

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents