# Exact convergence rate of the last iterate in subgradient methods

arXiv: https://arxiv.org/abs/2307.11134 · HTML: https://mlsanity.com/paper/2307.11134/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jul 2023.

## Built on by (most cited first, 25 of 25)

- [Training Deep Learning Models with Norm-Constrained LMOs](https://mlsanity.com/paper/2502.07529/) (2025)
- [The Road Less Scheduled](https://mlsanity.com/paper/2405.15682/) (2024)
- [Optimal Linear Decay Learning Rate Schedules and Further Refinements](https://mlsanity.com/paper/2310.07831/) (2023)
- [The Surprising Agreement Between Convex Optimization Theory and Learning-Rate Scheduling for Large Model Training](https://mlsanity.com/paper/2501.18965/) (2025)
- [Can SGD Handle Heavy-Tailed Noise?](https://mlsanity.com/paper/2508.04860/) (2025)
- [Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications](https://mlsanity.com/paper/2508.07473/) (2025)
- [From Continual Learning to SGD and Back: Better Rates for Continual Linear Models](https://mlsanity.com/paper/2504.04579/) (2025)
- [Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime](https://mlsanity.com/paper/2507.11274/) (2025)
- [On the Last-Iterate Convergence of Shuffling Gradient Methods](https://mlsanity.com/paper/2403.07723/) (2024)
- [Last Iterate Convergence of Incremental Methods and Applications in Continual Learning](https://mlsanity.com/paper/2403.06873/) (2024)
- [An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizes](https://mlsanity.com/paper/2407.04358/) (2024)
- [Optimal Rates in Continual Linear Regression via Increasing Regularization](https://mlsanity.com/paper/2506.06501/) (2025)
- [Gradient Descent's Last Iterate is Often (slightly) Suboptimal](https://mlsanity.com/paper/2604.13870/) (2026)
- [Primal Methods for Variational Inequality Problems with Functional Constraints](https://mlsanity.com/paper/2403.12859/) (2024)
- [In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise](https://mlsanity.com/paper/2606.00520/) (2026)
- [Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size](https://mlsanity.com/paper/2604.09909/) (2026)
- [MARINA-P: Superior Performance in Non-smooth Federated Optimization with Adaptive Stepsizes](https://mlsanity.com/paper/2412.17082/) (2024)
- [Scaling and Transferability of Annealing Strategies in Large Language Model Training](https://mlsanity.com/paper/2512.13705/) (2025)
- [The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives](https://mlsanity.com/paper/2609.08537/) (2026)
- [Learning Rate Annealing Improves Tuning Robustness in Stochastic Optimization](https://mlsanity.com/paper/2503.09411/) (2025)
- [Convergence Rate of the Last Iterate of Stochastic Proximal Algorithms](https://mlsanity.com/paper/2602.05489/) (2026)
- [New Bounds for the Last Iterate of the Stochastic subGradient Method](https://mlsanity.com/paper/2606.24879/) (2026)
- [Dangerous Liaisons of Convex Learning and Non-Affine Aggregation](https://mlsanity.com/paper/2606.28123/) (2026)
- [How AI settled the complexity of the oldest SGD algorithm](https://mlsanity.com/paper/2606.29593/) (2026)
- [Last-Iterate Convergence Rate of Normalized Gradient Descent under H"older Smoothness](https://mlsanity.com/paper/2610.06070/) (2026)

## Abstract (arXiv)

We study the convergence of the last iterate in subgradient methods applied to the minimization of a nonsmooth convex function with bounded subgradients. We first introduce a proof technique that generalizes the standard analysis of subgradient methods. It is based on tracking the distance between the current iterate and a different reference point at each iteration. Using this technique, we obtain the exact worst-case convergence rate for the objective accuracy of the last iterate of the projected subgradient method with either constant step sizes or constant step lengths. Tightness is shown with a worst-case instance matching the established convergence rate. We also derive the value of the optimal constant step size when performing N iterations, for which we find that the last iterate accuracy is smaller than B R √1+log(N)/4/√N+1 %fracB R log N√N+1 , where B is a bound on the subgradient norm and R is a bound on the distance between the initial iterate and a minimizer. Finally, we introduce a new optimal subgradient method that achieves the best possible last-iterate accuracy after a given number N of iterations. Its convergence rate B R/√N+1 matches exactly the lower bound on the performance of any black-box method on the considered problem class. We also show that there is no universal sequence of step sizes that simultaneously achieves this optimal rate at each iteration, meaning that the dependence of the step size sequence in N is unavoidable.