betaFeedback

WorksComputer Science

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

Abstract

When training stops at a data-dependent time, a guarantee for the returned model must hold at all times simultaneously. We study the last iterate of clipped SGD on smooth convex objectives under heavy-tailed stochastic gradients with a bounded central ppth moment, 1<p≤21<p\le2. With a known horizon TT, clipped SGD reaches the optimal last-iterate rate O(T−αp)O(T^{-α_p}), where αp=(p−1)/pα_p=(p-1)/p (Liu, 2026; Jiang et al., 2026). Without a known horizon, Chezhegov et al. (ICLR 2026) obtained the time-uniform rate O~(t−2(p−1)/(3p))\tilde O(t^{-2(p-1)/(3p)}) and conjectured that a better schedule reaches the optimal rate. We show that for clipped SGD, and more generally for every rule whose iterate does not advance on rounds without new gradient information, the optimal time-uniform rate is O~(t−βp)\tilde O(t^{-β_p}), where βp=2(p−1)/(3p−1)β_p=2(p-1)/(3p-1). Our deterministic schedule for clipped SGD uses neither a horizon nor a confidence input and attains O~(t−βp)\tilde O(t^{-β_p}) at all times simultaneously, and hence almost surely. Conversely, no such rule attains O~(t−r)\tilde O(t^{-r}) at all times for any r>βpr>β_p; for clipped SGD, this holds even with adaptive, randomized step sizes and clipping thresholds. Under finite variance, the known-horizon, optimal time-uniform, and previous time-uniform exponents are 1/21/2, 2/52/5, and 1/31/3. Since βp<αpβ_p<α_p, the conjecture, which holds with a known horizon, fails without one. By contrast, an update that queries gradients at the running average can advance the iterate on rounds without new gradient information and attains O~(t−αp)\tilde O(t^{-α_p}) at all times. Memory alone does not suffice: heavy-ball momentum with geometric forgetting and polynomially bounded step sizes cannot improve on the exponent βpβ_p.

Introduction

The length of a training run is rarely fixed before optimization begins. Early stopping (Aolaritei and Jordan, [2]) and checkpoint selection pick a stopping point from the observed trajectory, large-scale runs increasingly avoid committing to a fixed duration (Hägele et al., [23]), and schedule-free methods are designed so that no stopping time has to be specified (Defazio et al., [13]). The model that is kept is the state of the run at the chosen time rather than an average of past iterates. In such runs, the stochastic gradients are often heavy-tailed ([61] (Zhang et al. 2020)), and gradient clipping (Pascanu et al., [53]) is a standard remedy used routinely in training large language models (Touvron et al., [66]). We ask what an unknown horizon costs: how fast can the last iterate of clipped stochastic gradient descent (SGD; Robbins and Monro [56]) converge with high probability when the run may stop at a data-dependent time?

Fixed-time guarantees do not answer this question. A bound that holds with probability at least 1−δ1-\delta at each deterministic step tt relies on an event that may change with tt, so the bound can fail when the stopping time is chosen from the observed trajectory, just as continuously monitoring an A/B test with a fixed-sample rule inflates Type I error [25]. A guarantee holds at every bounded stopping time if and only if it is time-uniform, meaning that a single event of probability at least 1−δ1-\delta covers all steps t≥1t \ge1 simultaneously (Section 2). Under sub-Gaussian noise, time-uniform guarantees pay only logarithmic factors beyond the fixed-horizon exponent 1/21/2 (Li et al., 2026).

To study heavy-tailed noise, we consider a differentiable 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 conditionally unbiased stochastic gradients gtg_t queried at xtx_t that satisfy

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

Clipped SGD updates its iterate according to

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\left\{1,\frac{\lambda}{\lVert g\rVert}\right\}g, \tag*{(1)} \end{aligned}

where ηt\eta_t is the step size and λt\lambda_t is the clipping threshold. Without clipping, SGD with predefined step sizes attains the minimax optimal rate in expectation on convex problems whose stochastic gradients have bounded ppth moments [18], but its high-probability guarantees can require polynomial dependence on 1/δ1/\delta [58, 18]. Clipping achieves logarithmic dependence on 1/δ1/\delta [43, 21, 10, 58, 48], as in robust mean estimation [5, 14, 41]. Most of these high-probability guarantees apply to an averaged or auxiliary output rather than the last iterate. For an averaged output of clipped stochastic mirror descent, Nguyen et al. [48] proved that TT oracle calls suffice to reach, with probability at least 1−δ1-\delta, the statistical 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. We write αp=(p−1)/p\alpha_p=(p-1)/p for the statistical exponent in (2). For δ≤1/8\delta\le1/8 and T≥log⁡(1/δ)T\ge\log(1/\delta), Jiang et al. [28] proved that no algorithm using TT stochastic gradients improves on the minimum of LR2LR^2 and the scale (2) by more than a constant factor.

For the last iterate xT+1x_{T+1} itself, existing bounds depend on whether the horizon is given in advance. With a known horizon TT, Liu [37] and Jiang et al. [28] proved that clipped SGD with linearly decaying step sizes attains the optimal scale (2) at xT+1x_{T+1}; we restate the explicit bound of Jiang et al. [28] as Theorem 1. Without a known horizon, Chezhegov et al. [8] obtained the slower rate O~(t−2(p−1)/(3p))\widetilde{O}(t^{-2(p-1)/(3p)}) using a schedule that takes δ\delta as input; because their proof controls nested events across all steps, their guarantee is time-uniform. Guided by numerical experiments, Chezhegov et al. [8] conjectured that a better schedule reaches the optimal rate, while Liu [37] left the unknown-horizon case open. Since linear decay closes the last-iterate gap for a known horizon and time uniformity costs only logarithmic factors under sub-Gaussian noise, one would expect the gap between the exponents 2(p−1)/(3p)2(p-1)/(3p) and αp\alpha_p to be an artifact of the analysis.

Main Results

We show that under heavy-tailed noise, part of this gap is inherent. Across the two regimes, clipped SGD attains its optimal last-iterate errors

O~(T−αp)\widetilde{O}(T^{-\alpha_p})

with a known horizon TT,

O~(t−βp)\widetilde{O}(t^{-\beta_p})

at all times tt simultaneously,

where βp=2(p−1)/(3p−1)\beta_p = 2(p-1)/(3p-1) lies strictly between the exponents 2(p−1)/(3p)2(p-1)/(3p) and αp\alpha_p, and O~(⋅)\widetilde{O}(\cdot) hides constants and factors polylogarithmic in t/δt/\delta. Under finite variance (p=2p = 2), the known-horizon, optimal time-uniform, and previous time-uniform exponents are 1/21/2, 2/52/5, and 1/31/3. The conjecture of Chezhegov et al. [8] holds with a known horizon, as the results of Liu [37] and Jiang et al. [28] show, but fails without one, because βp<αp\beta_p < \alpha_p. On the upper-bound side, we give a deterministic schedule with ηt∝t−(p+1)/(3p−1)/log⁡2(100t)\eta_t \propto t^{-(p+1)/(3p-1)}/\log^2(100t) and λt∝t2/(3p−1)\lambda_t \propto t^{2/(3p-1)} that uses neither the horizon nor the confidence level, and we prove that clipped SGD with this schedule attains error O~(t−βp)\widetilde{O}(t^{-\beta_p}) at all times simultaneously (Theorem 2). Because a single trajectory serves every δ∈(0,1)\delta\in(0,1), the rate O~(t−βp)\widetilde{O}(t^{-\beta_p}) also holds almost surely. At p=2p = 2, this upper bound separates clipped SGD from unclipped SGD with deterministic step sizes: in concurrent work, Anonymous [1] prove that deterministic unclipped schedules attain no almost sure rate O~(t−r)\widetilde{O}(t^{-r}) for r>1/3r > 1/3, and we show that their construction also excludes time-uniform exponents above 1/31/3 on our problem class (Appendix § 15, Remark 16).

A lower bound with exponent rr takes the following form: for every r′>rr' > r, any claimed guarantee O~(t−r′)\widetilde{O}(t^{-r'}) fails on some instance with probability greater than δ\delta, so no exponent above rr is attainable. We begin with horizon-free gradient-only rules (Definition 3), which at each round tt query one fresh stochastic gradient gtg_t at the current iterate xtx_t and update xt+1=xt−ctgtx_{t+1} = x_t - c_tg_t with a scalar ct≥0c_t \ge0 that may depend on the observed history, on gtg_t, and on independent randomness. Every clipped SGD method with adaptive, randomized step sizes and thresholds belongs to this class. Even on one-dimensional instances with i.i.d. noise, we prove that no gradient-only rule attains a time-uniform guarantee O~(t−r)\widetilde{O}(t^{-r}) for any r>βpr > \beta_p (Theorem 4). We then extend this lower bound to every horizon-free rule whose iterate does not advance on rounds that bring no new gradient information, meaning that on one-dimensional instances a round with gt=0g_t = 0 does not move the iterate past its earlier maximum in a direction fixed before the run (Proposition 21). This broader class includes updates with fixed anchors, contracting weight decay toward the initialization, clipped KT coin betting (Orabona and Pál [49]), and the conic-lifting methods CBA, CBA+^+, and conic FTRL of Grand-Clément et al. [22] in one dimension (Appendix § 17).

Why can these rules not reach the exponent αp\alpha_p without a known horizon? Our hard instances are translated one-dimensional smooth convex objectives whose stochastic gradients contain rare Bernoulli spikes; we index them by their population minimizers, or targets, y∈[μ,1]y \in[\mu,1], where μ∈(0,1/2]\mu\in(0,1/2] is a parameter. Before the iterate crosses y−μy-\mu, the oracle of every target in this family returns zero gradient on quiet rounds and the same negative spike on rare rounds, which occur with probability π≍μp/(p−1)\pi\asymp\mu^{p/(p-1)}. Because the oracles of all uncrossed targets produce the same observation transcript, any rule whose iterate does not advance on zero gradients can move forward toward distant targets only on the rare spike rounds. Suppose that the rule promises an objective gap below an envelope btb_t at every round tt. If the iterate first crosses y−μy-\mu at round tt and lands more than μ+2bt\mu+\sqrt{2b_t} beyond this boundary, it overshoots yy and violates that target’s envelope. When we integrate the probabilities of failing at the first crossing over the targets yy, we find that if a rule keeps the gap below btb_t at all rounds t≤Nt \le N with probability at least 1−ε1-\varepsilon on every target, then the envelope values satisfy the progress budget π∑t=1N(μ+2bt)≥(1−2ε)/2\pi\sum_{t=1}^{N}(\mu+\sqrt{2b_t}) \ge(1-2\varepsilon)/2 for every μ∈(4θN,1/2)\mu\in(4\theta_N,1/2) (Proposition 17). For an envelope that decays like t−ut^{-u} with u>βpu > \beta_p and μ\mu of order bNb_N, the left-hand side tends to zero as N→∞N \to\infty (§ 4.2), a contradiction when ε<1/2\varepsilon< 1/2. A method that queries stochastic gradients at the running average is not bound by this budget: even on rounds with zero gradient, its iterate keeps moving toward a base sequence that accumulates past clipped gradient steps. Using a δ\delta-dependent schedule, we prove that a clipped running-average update attains O~(t−αp)\widetilde{O}(t^{-\alpha_p}) at all times simultaneously (Theorem 9). The three-sequence accelerated clipped method of Nguyen et al. [48] also attains αp\alpha_p without a known horizon; their theorem is stated at each fixed time, and their proof gives the time-uniform form (Appendix § 21). Reaching αp\alpha_p without a known horizon therefore requires an output that can advance without new gradient information; rescaling individual gradients is not enough.

When a guarantee is required only at one deterministic time tt rather than at all times simultaneously, the cost of an unknown horizon moves from the time exponent into the confidence factor (§ 5). For every r∈(βp,αp]r \in(\beta_p, \alpha_p], we give horizon-free clipped SGD schedules that attain the fixed-time error O~(δ−ct−r)\widetilde{O}(\delta^{-c}t^{-r}) with c=(3p−1)(r−βp)/(p−1)c = (3p-1)(r-\beta_p)/(p-1) when δ\delta is supplied as input, and with a larger exponent cc without a confidence input; at r=αpr = \alpha_p, the confidence factors are δ−αp\delta^{-\alpha_p} with a confidence input and δ−1\delta^{-1} without one (Theorem 5). Conversely, by applying our progress budget across finite prefixes via a union bound, we prove that any family of gradient-only rules attaining O~(δ−ct−r)\widetilde{O}(\delta^{-c}t^{-r}) at each fixed time with δ\delta-independent constants must satisfy c≥r−βpc \ge r-\beta_p (Theorem 6). Thus the optimal fixed-time confidence exponent c∗(r)c^*(r) satisfies r−βp≤c∗(r)≤(3p−1)(r−βp)/(p−1)r-\beta_p \le c^*(r) \le(3p-1)(r-\beta_p)/(p-1); its exact value remains open (Appendix § 11). With polylogarithmic dependence on 1/δ1/\delta, gradient-only rules are again limited to the rate O~(t−βp)\widetilde{O}(t^{-\beta_p}).

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. Chezhegov, 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]I. Fatkhullin, F. Hübler, and G. Lan. Can SGD handle heavy-tailed noise? arXiv:2508.04860v2, 2026. URL https://arxiv.org/abs/2508.04860v2.
  19. [19]D. A. Freedman. On tail probabilities for martingales. The Annals of Probability, 3(1):100–118, 1975.DOI
  20. [20]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.
  21. [21]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
  22. [22]J. Grand-Clément, J. Kwon, and F. Orabona. Conic-lifting for learning-rate-free convex optimization. arXiv:2610.39531v1, 2026. URL https://arxiv.org/abs/2610.39531v1.
  23. [23]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.arxiv.org/abs/2405.18392
  24. [24]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
  25. [25]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
  26. [26]P. J. Huber. Robust estimation of a location parameter. The Annals of Mathematical Statistics, 35 (1):73–101, 1964.
  27. [27]P. Jain, D. M. Nagaraj, and P. Netrपalli. Making the last iterate of SGD information theoretically optimal. SIAM Journal on Optimization, 31(2):1108–1130, 2021.arxiv.org/abs/1904.12443
  28. [28]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.
  29. [29]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.
  30. [30]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.
  31. [31]G. Kornowski and O. Shamir. Gradient descent’s last iterate is often (slightly) suboptimal. arXiv:2604.13870v2, 2026.
  32. [32]G. Lan. An optimal method for stochastic composite optimization. Mathematical Programming, 133 (1–2):365–397, 2012.
  33. [33]L. Le Cam. Convergence of estimates under dimensionality restrictions. The Annals of Statistics, 1 (1):38–53, 1973.
  34. [35]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.
  35. [37]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.
  36. [38]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.
  37. [39]Z. Liu and Z. Zhou. Revisiting the last-iterate convergence of stochastic gradient methods. In International Conference on Learning Representations, 2024.
  38. [41]G. Lugosi and S. Mendelson. Mean estimation and regression under heavy-tailed distributions: A survey. Foundations of Computational Mathematics, 19(5):1145–1190, 2019.
  39. [42]A. Meterez, P. A. Nair, D. Morwani, C. Pehelvan, and S. Kakade. Anytime pretraining: Horizon-free learning-rate schedules with weight averaging. arXiv:2602.03702v2, 2026. URL https://arxiv.org/abs/2602.03702v2.
  40. [43]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
  41. [44]A. Nekrasova, M. Sidorov, S. Chezhegov, A. Gasnikov, M. Preobrazhenskaia, I. Preobrazhensky, and E. Gorbunov. Weak-Lᵅ noise, strong guarantees: Gradient clipping under affine heavy tails. arXiv:2610.28107v1, 2026. URL https://arxiv.org/abs/2610.28107v1.
  42. [45]A. S. Nemirovsky and D. B. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, New York, 1983.
  43. [46]Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course, volume 87 of Applied Optimization. Kluwer Academic Publishers, Boston, MA, 2004.
  44. [47]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.
  45. [48]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
  46. [49]F. Orabona and D. Pál. Coin betting and parameter-free online learning. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016. URL https://proceedings.neurips.cc/paper_files/paper/2016/file/320722549d1751cf3f247855f937b982-Paper.pdf.arxiv.org/abs/1602.04128
  47. [50]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
  48. [51]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
  49. [52]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
  50. [53]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
  51. [54]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
  52. [55]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
  53. [56]H. Robbins and S. Monro. A stochastic approximation method. The Annals of Mathematical Statistics, 22(3):400–407, 1951.
  54. [57]D. Ruppert. Efficient estimations from a slowly convergent Robbins–Monro process. Technical Report 781, School of Operations Research and Industrial Engineering, Cornell University, 1988.
  55. [58]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
  56. [59]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.
  57. [60]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
  58. [61]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
  59. [62]M. Streeter and H. B. McMahan. Less regret via online conditioning. arXiv:1002.4862v1, 2010. URL https://arxiv.org/abs/1002.4862v1.
  60. [63]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
  61. [64]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.arxiv.org/abs/1902.00947
  62. [65]X. Tian, J. Fan, R. H. L. Sim, and B. K. H. Low. INO-SGD: Addressing utility imbalance under individualised differential privacy. In International Conference on Learning Representations, 2026. URL https://arxiv.org/abs/2605.07930v1.
  63. [66]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.
  64. [67]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
  65. [68]A. B. Tsybakov. Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer, New York, 2009.
  66. [69]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
  67. [70]R. Ward, X. Wu, and L. Bottou. AdaGrad stepsizes: Sharp convergence over nonconvex landscapes. Journal of Machine Learning Research, 21(219):1–30, 2020.

Paper details

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

views · 0

downloads · 0

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

  • Computer Science

GPT (multiple versions), Anthropic’s Claude

View statement
Looking for related papers…
Contents