betaFeedback

Reading v1View latest version

WorksComputer Science

The Cost of an Unknown Horizon for the Last Iterate of Clipped SGD under Heavy-Tailed Noise

Abstract

Training is often stopped at a data-dependent time, so guarantees for the last iterate must hold at all times simultaneously. We determine the optimal time-uniform rate for the last iterate of clipped SGD on smooth convex objectives under heavy-tailed noise with a bounded central ppth moment, 1<p≤21<p\le2. A schedule without horizon or confidence inputs attains O~(t−βp)\tilde O(t^{-β_p}) at all times, with βp=2(p−1)/(3p−1)β_p=2(p-1)/(3p-1), also almost surely, and no rule that steps along the stochastic gradient at its current iterate attains O~(t−r)\tilde O(t^{-r}) for any r>βpr>β_p, even with adaptive step sizes and thresholds. This rate lies between the optimal rate O(T−αp)O(T^{-α_p}) for a known horizon TT, αp=(p−1)/pα_p=(p-1)/p, and the previous time-uniform rate O~(t−2(p−1)/(3p))\tilde O(t^{-2(p-1)/(3p)}) (Chezhegov et al., ICLR 2026); under finite variance, the exponents are 1/21/2, 2/52/5, and 1/31/3. Their conjecture that a better schedule reaches the optimal rate thus holds with a known horizon (Liu; Jiang et al.) but fails without one. Querying gradients at the running average attains O~(t−αp)\tilde O(t^{-α_p}) at all times, whereas heavy-ball momentum with geometric forgetting and polynomially bounded steps cannot improve on βpβ_p.

Introduction

The length of a training run is often not fixed in advance. Early stopping and checkpoint selection depend on the observed trajectory ([2]), large-scale training increasingly avoids committing to a duration ([21]), and schedule-free methods are designed so that no stopping time has to be specified ([13]). The model kept is the state of the run at the chosen time rather than an average of iterates. The stochastic gradients are often heavy-tailed ([56, 69]), and gradient clipping ([48]) is a standard remedy, used routinely in training large language models ([61]). This paper asks what an unknown stopping time costs: how fast can the last iterate of clipped stochastic gradient descent (SGD; [51]) converge with high probability when the time at which it is used is not fixed in advance?

Fixed-time guarantees do not answer this question. A bound that holds with probability 1−δ1-\delta at each fixed time may fail at a time chosen from the observed trajectory, just as A/B tests that are monitored continuously with methods assuming a fixed sample size have inflated Type I error ([23]). A guarantee holds at every data-dependent stopping time exactly when it holds on one event, of probability at least 1−δ1-\delta, at all times simultaneously (§ 2). Under sub-Gaussian noise, passing to such time-uniform guarantees costs only logarithmic factors around the exponent 1/21/2 ((Li et al., 2026)).

Under heavy-tailed noise the price is polynomial, and we determine it: for noise with a bounded central ppth moment, 1<p≤21 < p \le2, clipped SGD attains the last-iterate errors

O(T−αp) with a known horizon T,O(T^{-\alpha_p}) \text{ with a known horizon } T,
O~(t−βp) at all times t simultaneously,\widetilde{O}(t^{-\beta_p}) \text{ at all times } t \text{ simultaneously},

where αp=(p−1)/p\alpha_p = (p - 1)/p, βp=2(p−1)/(3p−1)\beta_p = 2(p - 1)/(3p - 1), and O~\widetilde{O} hides logarithmic factors; under finite variance, the exponents are 1/21/2 and 2/52/5. The known-horizon rate is due to Liu [35] and Jiang et al. [26]; the time-uniform rate is our main result. Both exponents are optimal, αp\alpha_p among all algorithms that query stochastic gradients and βp\beta_p among all rules that query their current iterate and step along the resulting stochastic gradient. For fixed δ≤1/8\delta\le1/8, every algorithm making TT stochastic gradient queries has error Ω(T−αp)\Omega(T^{-\alpha_p}) with probability at least 2δ2\delta on some instance ([26 Proposition 1]), and we prove that no such rule attains O~(t−r)\widetilde{O}(t^{-r}) at all times for any r>βpr > \beta_p, whatever its step sizes and clipping thresholds. The best previous time-uniform rate, O~(t−2(p−1)/(3p))\widetilde{O}(t^{-2(p-1)/(3p)}) or O~(t−1/3)\widetilde{O}(t^{-1/3}) at p=2p = 2, is due to Chezhegov et al. [8], who suggest that the gap to the optimal rate may be an artifact of the analysis; our results show that, for such rules, part of this gap is inherent. We also find that where gradients are queried matters more than how they are scaled: querying them at the running average of the iterates attains O~(t−αp)\widetilde{O}(t^{-\alpha_p}) at all times.

With clipping, high-probability guarantees can depend only logarithmically on the confidence level ([40, 20, 10, 53, 44]), as for robust mean estimators ([5, 14, 39]), whereas unclipped SGD can require polynomial dependence ([53]); most of these guarantees concern an averaged or auxiliary output and need not apply to the last iterate. Formally, we consider a convex LL-smooth objective f:Rd→Rf : \mathbb{R}^d \to\mathbb{R} with a minimizer x⋆x^\star satisfying ∥x1−x⋆∥≤R\lVert x_1 - x^\star\rVert\le R, and stochastic gradients gtg_t that are conditionally unbiased with

E[∥gt−∇f(xt)∥p∣Ft−1]≤σp,1<p≤2.\mathbb{E}[\lVert g_t - \nabla f(x_t) \rVert^p \mid\mathcal{F}_{t-1}] \le\sigma^p, \qquad1 < p \le2.

Clipped SGD performs the updates

xt+1=xt−ηtclip⁡(gt,λt),clip⁡(g,λ)=min⁡{1,λ/∥g∥}g,(1)\begin{aligned} x_{t+1} &= x_t - \eta_t \operatorname{clip}(g_t,\lambda_t),\\ \operatorname{clip}(g,\lambda) &= \min\{1,\lambda/\lVert g\rVert\}g, \tag*{(1)} \end{aligned}

where ηt\eta_t is the step size and λt\lambda_t the clipping threshold. For an averaged output of clipped stochastic mirror descent, Nguyen et al. [44] proved that TT oracle calls suffice to reach, with probability at least 1−δ1-\delta, the scale

σR(log⁡(1/δ)T)(p−1)/p(2)\sigma R\left(\frac{\log(1/\delta)}{T}\right)^{(p-1)/p} \tag*{(2)}

plus a deterministic term of order LR2log⁡(1/δ)/TLR^2\log(1/\delta)/T. For δ≤1/8\delta\le1/8 and T≥log⁡(1/δ)T \ge\log(1/\delta), the lower bound of Jiang et al. [26] shows that no algorithm using TT stochastic gradients improves the minimum of LR2LR^2 and the scale (2) by more than a constant factor.

For the last iterate, the horizon-free rate T−2(p−1)/(3p)T^{-2(p-1)/(3p)} of Chezhegov et al. [8] holds up to logarithms with a schedule that takes δ\delta as input, and their experiments led them to conjecture that an improved schedule could attain the optimal rate (Chezhegov et al. [8]). With a known horizon the conjecture holds: linearly decaying step sizes attain (2) at the last iterate, as shown by Liu [35] and Jiang et al. [26] (Theorem 1 below). Liu [35], § 5 leaves the case of an unknown horizon open. This is the case we study, and we find that there the conjecture fails for rules that query their current iterate and step along its stochastic gradient, both for time-uniform guarantees and for fixed-time guarantees with polylogarithmic confidence dependence (Theorems 4 and 6).

Main Results

Table 1 summarizes our results and compares them with previous and concurrent work; αp\alpha_p is the statistical exponent of (2). We write error bounds as O~(t−r)\widetilde{O}(t^{-r}), where O~\widetilde{O} hides constants and factors polylogarithmic in t/δt/\delta. An upper bound shows that the exponent rr is attained; a lower bound with exponent rr shows that for every r′>rr' > r, any claimed bound O~(t−r′)\widetilde{O}(t^{-r'}) fails on some instance with probability more than δ\delta, rather than a pointwise bound Ω(t−r)\Omega(t^{-r}).

Our main result is the optimal time-uniform rate (§ 4). We give a deterministic schedule that uses neither the horizon nor the confidence level and prove that clipped SGD with this schedule attains error O~(t−βp)\widetilde{O}(t^{-\beta_p}) at all times simultaneously (Theorem 2). Because one trajectory serves every confidence level, the rate also holds almost surely. This improves the rate O~(t−2(p−1)/(3p))\widetilde{O}(t^{-2(p-1)/(3p)}) of Chezhegov et al. [8], whose schedule needs δ\delta. We then prove that βp\beta_p cannot be improved: no gradient-only rule (Definition 3) attains a time-uniform bound O~(t−r)\widetilde{O}(t^{-r}) with r>βpr > \beta_p, even if its step sizes and clipping thresholds respond adaptively and randomly to the history and the current gradient (Theorem 4). At p=2p = 2, Anonymous [1] prove, concurrently, that deterministic unclipped step sizes cannot attain almost sure rates O~(t−r)\widetilde{O}(t^{-r}) for any r>1/3r > 1/3, and in Remark 16 we show that their construction also excludes such time-uniform rates on our class. With our results, this shows that deterministic unclipped schedules are limited to the exponent 1/31/3, whereas our clipped schedule attains 2/52/5.

The lower bound raises the question whether a method outside this class can recover αp\alpha_p without a known horizon (§ 6). It can: if gradients are queried at the running average of the iterates, the error is O~(t−αp)\widetilde{O}(t^{-\alpha_p}) uniformly over time (Theorem 9, with a schedule that uses δ\delta). The accelerated method of Nguyen et al. [44] also attains αp\alpha_p without a known horizon; their theorem is stated at each fixed time, and its proof gives the time-uniform form (Appendix § 20). The barrier therefore depends on where gradients are queried rather than on how they are scaled. Written as heavy-ball momentum (Polyak, [49]), this update has 1−βt1-\beta_t of order 1/t1/t, so its memory grows. We show that memory that does not grow is not enough. With zero initial velocity, polynomially bounded step sizes, and geometrically decaying memory, heavy-ball momentum attains no bound O~(t−r)\widetilde{O}(t^{-r}) with r>βpr > \beta_p, even in one dimension. Under polynomial forgetting 1−βt≥ρ(1+t)−a1-\beta_t \ge\rho(1+t)^{-a}, we prove the barriers (1+a)βp(1+a)\beta_p in one dimension (Theorem 7) and max⁡{βp,a}\max\{\beta_p,a\} under constants shared across dimensions (Theorem 8). Both also hold for fixed-time guarantees with polylogarithmic confidence dependence when the rule’s constants depend on δ\delta only through a polynomial factor in the step-size bound.

The price also depends on what the guarantee must cover: at a single fixed time, we show that it moves into the confidence factor (§ 5). Our horizon-free schedule attains O~(δ−1/pt−αp)\widetilde{O}(\delta^{-1/p}t^{-\alpha_p}) at each fixed time tt, or O~(δ−1t−αp)\widetilde{O}(\delta^{-1}t^{-\alpha_p}) without a confidence input (Theorem 5). For gradient-only rules and r∈(βp,αp]r \in(\beta_p,\alpha_p], we prove that a fixed-time bound O~(δ−ct−r)\widetilde{O}(\delta^{-c}t^{-r}) that holds for every δ\delta with constants independent of δ\delta requires c≥r−βpc \ge r-\beta_p, whereas c=(3p−1)(r−βp)/(p−1)c=(3p-1)(r-\beta_p)/(p-1) suffices (Theorems 5 and 6). With polylogarithmic dependence on 1/δ1/\delta, the exponent is again limited to βp\beta_p.

With a known horizon, Liu [35] and Jiang et al. [26] show that a fixed threshold and linearly decaying step sizes attain O(T−αp)O(T^{-\alpha_p}) at the last iterate, which matches the lower bound Ω(T−αp)\Omega(T^{-\alpha_p}) of Jiang et al. [26]; we restate their bound as Theorem 1. Our lower bounds allow adaptive, randomized scalar responses to the history and the current gradient, while our upper bounds use deterministic schedules.

Guarantee requiredGradient at the current iterateGradient at the running averageThm.
At a known horizon TTT−1/2T^{-1/2}T−1/2T^{-1/2}1
At one fixed time, confidence factor δ−1/2\delta^{-1/2}t−1/2t^{-1/2}t−1/2t^{-1/2}5
At one fixed time, confidence factor log⁡1δ\log\frac{1}{\delta}t−2/5t^{-2/5}t−1/2t^{-1/2}2, 6
At all times (any stopping time)t−1/3→t−2/5t^{-1/3} \to t^{-2/5}t−1/2t^{-1/2}2, 4, 9

Table 1. Best last-iterate error of clipped SGD under finite variance, up to constants and logarithmic factors. Shaded: new in this paper; the arrow starts from the previous rate of Chezhegov et al. [8], and the known-horizon rate is due to Liu [35] and Jiang et al. [26]. Down the first column, knowing less about when the run stops costs a polynomial factor; the second column shows that querying gradients at the running average removes this cost. The rates t−2/5t^{-2/5} are optimal for every rule that queries its current iterate, with any step sizes and thresholds, and also limit heavy-ball momentum with a fixed coefficient and polynomially bounded step sizes (Theorems 7 and 8). For 1<p≤21 < p \le2, replace 1/21/2 by αp=(p−1)/p\alpha_p = (p - 1)/p, 2/52/5 by βp=2(p−1)/(3p−1)\beta_p = 2(p - 1)/(3p - 1), and δ−1/2\delta^{-1/2} by δ−(p−1)/p\delta^{-(p-1)/p}.

What the Results Mean

We draw three lessons from these results.

Under heavy-tailed noise, a guarantee for clipped SGD that covers early stopping or checkpoint selection has a polynomial price, and tuning cannot remove it. When the model may be used at any time, the best error bound for clipped SGD under finite variance is O~(t−2/5)\widetilde{O}(t^{-2/5}) rather than O(T−1/2)O(T^{-1/2}), whereas under sub-Gaussian noise the same requirement costs only logarithmic factors (Li et al. (2026)). Our lower bound covers every rule that queries its current iterate and moves along the resulting stochastic gradient, with step sizes and thresholds that may adapt to all observed gradients. The reason is a counting argument (Proposition 17). On our hard instances the informative gradient observations are rare, and on each of them the iterate may move only a limited distance, since a longer move would violate the error bound on one of the instances that produce the same observations. Rare observations and limited moves cannot support any exponent above βp\beta_p.

What does help is to change where gradients are evaluated. If they are evaluated at the running average of the iterates and the average is kept as the model, the polynomial loss in the exponent disappears: the error is O~(t−αp)\widetilde{O}(t^{-\alpha_p}) at all times (Theorem 9). This connects our analysis to schedule-free SGD (Defazio et al. [13]), which evaluates gradients between this average and a base sequence; when it evaluates them at the average, its update with clipped gradients has the form (20), with decreasing instead of constant step sizes. Momentum helps in the same way only if its memory grows. With 1−βt1-\beta_t of order 1/t1/t, the heavy-ball method is this averaging update, whereas geometrically decaying memory, as with a fixed coefficient, keeps the exponent βp\beta_p when the step sizes are polynomially bounded (Theorem 7).

For theory, our results show that under heavy-tailed noise, time-uniform analyses of gradient-only rules cannot match known-horizon rates up to logarithmic factors. At a single fixed time the gap moves into the confidence factor: O~(t−αp)\widetilde{O}(t^{-\alpha_p}) is attainable there only with a factor polynomial in 1/δ1/\delta (Theorems 5 and 6). Two of our tools may be useful beyond this paper: a last-iterate potential whose weights stay bounded without a horizon, so that one concentration event covers all times (Lemma 11), and the counting argument above, which applies to every such rule. Appendix C lists open problems, including adaptation to unknown problem parameters, lower bounds for more general updates, and the optimal confidence factor at a fixed time.

Techniques and Organization

References

  1. [1]Anonymous. The cube-root barrier for almost-sure last-iterate convergence of SGD. Submission to the International Conference on Learning Representations 2027, https://openreview.net/forum?id=PsmfXqmgZI, 2026.
  2. [2]L. Aolaritei and M. I. Jordan. Stopping rules for stochastic gradient descent via anytime-valid confidence sequences. arXiv:2512.13123v5, 2026.arxiv.org/abs/2512.13123
  3. [3]A. Armacki, H. Cai, and A. H. Sayed. Decentralized SGD under heavy-tailed noise: Optimal convergence rates and the role of gradient clipping. arXiv:2610.10527v1, 2026. URL https://arxiv.org/abs/2610.10527v1.
  4. [4]G. Beretta, T. Cesari, R. Colomboni, and A. Paudice. New bounds for the last iterate of the stochastic subGradient method. arXiv:2606.24879v1, 2026.arxiv.org/abs/2606.24879
  5. [5]O. Catoni. Challenging the empirical mean and empirical variance: A deviation study. Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 48(4):1148–1185, 2012.arxiv.org/abs/1009.2048
  6. [6]N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, Cambridge, 2006.
  7. [7]N. Cesa-Bianchi, A. Conconi, and C. Gentile. On the generalization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 50(9):2050–2057, 2004.
  8. [8]S. Chezhegov, D. A. Parletta, A. Paudice, and E. Gorbunov. High-probability bounds for the last iterate of clipped SGD. In International Conference on Learning Representations, 2026.
  9. [9]A. Cutkosky. Anytime online-to-batch, optimism and acceleration. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1446–1454, 2019.
  10. [10]A. Cutkosky and H. Mehta. High-probability bounds for non-convex stochastic optimization with heavy tails. In Advances in Neural Information Processing Systems, volume 34, pages 4883–4895, 2021.arxiv.org/abs/2106.14343
  11. [11]A. Defazio. Momentum via primal averaging: Theoretical insights and learning rate schedules for non-convex optimization. arXiv:2010.00406v4, 2021. URL https://arxiv.org/abs/2010.00406v4.
  12. [12]A. Defazio, A. Cutkosky, H. Mehta, and K. Mishchenko. Optimal linear decay learning rate schedules and further refinements. arXiv:2310.07831v2, 2024a.arxiv.org/abs/2310.07831
  13. [13]A. Defazio, X. Yang, H. Mehta, K. Mishchenko, A. Khaled, and A. Cutkosky. The road less scheduled. In Advances in Neural Information Processing Systems, volume 37, pages 9974–10007, 2024b.arxiv.org/abs/2405.15682
  14. [14]L. Devroye, M. Lerasle, G. Lugosi, and R. I. Oliveira. Sub-Gaussian mean estimators. The Annals of Statistics, 44(6):2695–2725, 2016.arxiv.org/abs/1509.05845
  15. [15]Y. Drori and O. Shamir. The complexity of finding stationary points with stochastic gradient descent. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 2658–2667, 2020. URL https://proceedings.mlr.press/v119/drori20a.html.arxiv.org/abs/1910.01845
  16. [16]J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(61):2121–2159, 2011.
  17. [17]T. El Bakkali El Kadi, S. Chezhегov, A. Beznosikov, S. Horváth, and E. Gorbunov. High-probability convergence of clipped SGD under heavy-tailed noise and (L₀, L₁)-smoothness. arXiv:2505.20817v3, 2026.arxiv.org/abs/2505.20817
  18. [18]D. A. Freedman. On tail probabilities for martingales. The Annals of Probability, 3(1):100–118, 1975.DOI
  19. [19]S. Ganesh, R. Deb, G. Thoppe, and A. Budhiraja. Does momentum help in stochastic optimization? A sample complexity analysis. In Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, volume 216 of Proceedings of Machine Learning Research, pages 602–612, 2023. URL https://proceedings.mlr.press/v216/ganesh23a.html.
  20. [20]E. Gorbunov, M. Danilova, and A. Gasnikov. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. In Advances in Neural Information Processing Systems, volume 33, pages 15042–15053, 2020.arxiv.org/abs/2005.10785
  21. [21]A. Hägele, E. Bakouch, A. Kosson, L. Ben Allal, L. Von Werra, and M. Jaggi. Scaling laws and compute-optimal training beyond fixed training durations. In Advances in Neural Information Processing Systems, volume 37, pages 76232–76264, 2024.
  22. [22]N. J. A. Harvey, C. Liaw, Y. Plan, and S. Randhawa. Tight analyses for non-smooth stochastic gradient descent. In Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1579–1613, 2019.arxiv.org/abs/1812.05217
  23. [23]S. R. Howard, A. Ramdas, J. McAuliffe, and J. Sekhon. Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2):1055–1080, 2021.DOI
  24. [24]P. J. Huber. Robust estimation of a location parameter. The Annals of Mathematical Statistics, 35(1):73–101, 1964.
  25. [25]P. Jain, D. M. Nagaraj, and P. Netrapalli. Making the last iterate of SGD information theoretically optimal. SIAM Journal on Optimization, 31(2):1108–1130, 2021.arxiv.org/abs/1904.12443
  26. [26]W. Jiang, H. Bai, and Z. Li. Last-iterate convergence of clipped SGD with linear decay. arXiv:2610.18555v1, 2026. URL https://arxiv.org/abs/2610.18555v1.
  27. [27]A. Khaled and P. Richtárik. Better theory for SGD in the nonconvex world. Transactions on Machine Learning Research, 2023. URL https://openreview.net/forum?id=AU4qHN2VkS.
  28. [28]G. Kornowski and O. Shamir. Open problem: Anytime convergence rate of gradient descent. In Proceedings of the Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 5335–5339, 2024.arxiv.org/abs/2406.13888
  29. [29]G. Kornowski and O. Shamir. Gradient descent’s last iterate is often (slightly) suboptimal. arXiv:2604.13870v2, 2026.arxiv.org/abs/2604.13870
  30. [30]G. Lan. An optimal method for stochastic composite optimization. Mathematical Programming, 133 (1–2):365–397, 2012.
  31. [31]L. Le Cam. Convergence of estimates under dimensionality restrictions. The Annals of Statistics, 1 (1):38–53, 1973.
  32. [33]J. Liu and Y. Yuan. On almost sure convergence rates of stochastic gradient methods. In Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 2963–2983, 2022. URL https://proceedings.mlr.press/v178/liu22d.html.arxiv.org/abs/2202.04295
  33. [35]Z. Liu. On the last-iterate convergence of clipped gradient methods. In Advances in Neural Information Processing Systems, 2026a. URL https://arxiv.org/abs/2610.21026v1. To appear.
  34. [36]Z. Liu. Clipped gradient methods for nonsmooth convex optimization under heavy-tailed noise: A refined analysis. In International Conference on Learning Representations, 2026b. Extended version: arXiv:2512.23178v3.arxiv.org/abs/2512.23178
  35. [37]Z. Liu and Z. Zhou. Revisiting the last-iterate convergence of stochastic gradient methods. In International Conference on Learning Representations, 2024.arxiv.org/abs/2312.08531
  36. [39]G. Lugosi and S. Mendelson. Mean estimation and regression under heavy-tailed distributions: A survey. Foundations of Computational Mathematics, 19(5):1145–1190, 2019.arxiv.org/abs/1906.04280
  37. [40]A. V. Nazin, A. S. Nemirovsky, A. B. Tsybakov, and A. B. Juditsky. Algorithms of robust stochastic optimization based on mirror descent method. Automation and Remote Control, 80(9):1607–1627, 2019.arxiv.org/abs/1907.02707
  38. [41]A. S. Nemirovsky and D. B. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, New York, 1983.DOI
  39. [42]Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course, volume 87 of Applied Optimization. Kluwer Academic Publishers, Boston, MA, 2004.
  40. [43]Y. E. Nesterov. A method of solving a convex programming problem with convergence rate O(1/k²). Doklady Akademii Nauk SSSR, 269(3):543–547, 1983.
  41. [44]T. D. Nguyen, T. H. Nguyen, A. Ene, and H. L. Nguyen. Improved convergence in high probability of clipped gradient methods with heavy tailed noise. In Advances in Neural Information Processing Systems, volume 36, pages 24191–24222, 2023. URL https://proceedings.neurips.cc/paper_files/paper/2023/hash/4c454d34f3a4c8d6b4ca85a918e5d7ba-Abstract-Conference.html.DOI
  42. [45]W. Ou and X. Wang. Revisiting AdaGrad in stochastic convex optimization: Last iterates, high probability, and lower bounds. arXiv:2609.32729v1, 2026.arxiv.org/abs/2609.32729
  43. [46]D. A. Parletta, A. Paudice, M. Pontil, and S. Salzo. High probability bounds for stochastic subgradient schemes with heavy tailed noise. SIAM Journal on Mathematics of Data Science, 6 (4):953–977, 2024.arxiv.org/abs/2208.08567
  44. [47]D. A. Parletta, A. Paudice, and S. Salzo. An improved analysis of the clipped stochastic subGradient method under heavy-tailed noise. arXiv:2410.00573v2, 2025.arxiv.org/abs/2410.00573
  45. [48]R. Pascanu, T. Mikolov, and Y. Bengio. On the difficulty of training recurrent neural networks. In Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 1310–1318, 2013.arxiv.org/abs/1211.5063
  46. [49]B. T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1–17, 1964.DOI
  47. [50]B. T. Polyak and A. B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4):838–855, 1992.DOI
  48. [51]H. Robbins and S. Monro. A stochastic approximation method. The Annals of Mathematical Statistics, 22(3):400–407, 1951.
  49. [52]D. Ruppert. Efficient estimations from a slowly convergent Robbins–Monro process. Technical Report 781, School of Operations Research and Industrial Engineering, Cornell University, 1988.
  50. [53]A. Sadiev, M. Danilova, E. Gorbunov, S. Horváth, G. Gidel, P. Dvurechensky, A. Gasnikov, and P. Richtárik. High-probability bounds for stochastic optimization and variational inequalities: The case of unbounded variance. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 29563–29648, 2023.arxiv.org/abs/2302.00999
  51. [54]O. Sebbouh, R. M. Gower, and A. Defazio. Almost sure convergence rates for stochastic gradient descent and stochastic heavy ball. In Proceedings of the 34th Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 3935–3971, 2021. URL https://proceedings.mlr.press/v134/sebbouh21a.html.
  52. [55]O. Shamir and T. Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 71–79, 2013.arxiv.org/abs/1212.1824
  53. [56]U. Şimşekli, L. Sagun, and M. Gürbüzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 5827–5837, 2019.arxiv.org/abs/1901.06053
  54. [57]M. Streeter and H. B. McMahan. Less regret via online conditioning. arXiv:1002.4862v1, 2010. URL https://arxiv.org/abs/1002.4862v1.
  55. [58]A. Suvorikova, E. Gladin, D. Dvinskikh, A. Agafonov, M. Alkousa, Y. Dorn, V. Matyukhin, and A. Gasnikov. Clipped or unclipped? Finite-sample trade-offs for averaged SGD under heavy-tailed noise. arXiv:2609.32962v1, 2026.arxiv.org/abs/2609.32962
  56. [59]A. Taylor and F. Bach. Stochastic first-order methods: Non-asymptotic and computer-aided analyses via potential functions. In Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, 2019.
  57. [60]X. Tian, J. Fan, R. H. L. Sim, and B. K. H. Low. INO-SGD: Addressing utility imbalance under individualized differential privacy. In International Conference on Learning Representations, 2026. URL https://arxiv.org/abs/2605.07930v1.
  58. [61]H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozière, N. Goyal, E. Hambro, F. Azhar, A. Rodriguez, A. Joulin, E. Grave, and G. Lample. LLaMA: Open and efficient foundation language models. arXiv:2302.13971v1, 2023. URL https://arxiv.org/abs/2302.13971v1.
  59. [62]C.-E. Tsai, I. Fatkhullin, L. Zhang, and N. He. Lower bounds for anytime acceleration of gradient descent. arXiv:2607.02053v1, 2026.arxiv.org/abs/2607.02053
  60. [63]A. B. Tsybakov. Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer, New York, 2009.
  61. [64]N. M. Vural, L. Yu, K. Balasubramanian, S. Volgushev, and M. A. Erdogdu. Mirror descent strikes again: Optimal stochastic convex optimization under infinite noise variance. In Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 65–102, 2022.arxiv.org/abs/2202.11632
  62. [65]R. Ward, X. Wu, and L. Bottou. AdaGrad stepsizes: Sharp convergence over nonconvex landscapes. Journal of Machine Learning Research, 21(219):1–30, 2020.
  63. [66]M. Zamani and F. Glineur. Exact convergence rate of the last iterate in subgradient methods. SIAM Journal on Optimization, 35(3):2182–2201, 2025.arxiv.org/abs/2307.11134
  64. [67]H. Zhang, W. Wu, C. Zhang, Y. Li, C. Zheng, C. Fang, H. Li, and Z. Lin. Sharp high-probability statistical rates for heavy-tailed nonsmooth convex optimization. arXiv:2610.00260v1, 2026.arxiv.org/abs/2610.00260
  65. [68]J. Zhang and A. Cutkosky. Parameter-free regret in high probability with heavy tails. In Advances in Neural Information Processing Systems, volume 35, pages 8000–8012, 2022.arxiv.org/abs/2210.14355
  66. [69]J. Zhang, S. P. Karimireddy, A. Veit, S. Kim, S. J. Reddi, S. Kumar, and S. Sra. Why are adaptive methods good for attention models? In Advances in Neural Information Processing Systems, volume 33, pages 15383–15393, 2020.arxiv.org/abs/1912.03194

Paper details

vlnc:W_vm22jteh
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
  • Computer Science

GPT (multiple versions), Anthropic’s Claude

View statement
Looking for related papers…
Contents