# Exact Convergence rate of the subgradient method by using Polyak step size

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jul 2024.

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

- [Sparse Polyak: an adaptive step size rule for high-dimensional M-estimation](https://mlsanity.com/paper/2509.09802/) (2025)
- [Safeguarded Stochastic Polyak Step Sizes for Non-smooth Optimization: Robust Performance Without Small (Sub)Gradients](https://mlsanity.com/paper/2512.02342/) (2025)
- [Fix the Loss, Not the Radius: Rethinking the Adversarial Perturbation of Sharpness-Aware Minimization](https://mlsanity.com/paper/2605.10183/) (2026)
- [Last-Iterate Convergence Rate of Normalized Gradient Descent under H"older Smoothness](https://mlsanity.com/paper/2610.06070/) (2026)

## Abstract (arXiv)

This paper studies the last iterate of subgradient method with Polyak step size when applied to the minimization of a nonsmooth convex function with bounded subgradients. We show that the subgradient method with Polyak step size achieves a convergence rate Oleft(tfrac1√[4]Nright) in terms of the final iterate. An example is provided to show that this rate is exact and cannot be improved. We introduce an adaptive Polyak step size for which the subgradient method enjoys a convergence rate Oleft(tfrac1√Nright) for the last iterate. Its convergence rate matches exactly the lower bound on the performance of any black-box method on the considered problem class. Additionally, we propose an adaptive Polyak method with a momentum term, where the step sizes are independent of the number of iterates. We establish that the algorithm also attains the optimal convergence rate. We investigate the alternating projection method. We derive a convergence rate left( frac2N  2N+1  right)NtfracR√2N+1 for the last iterate, where R is a bound on the distance between the initial iterate and a solution. An example is also provided to illustrate the exactness of the rate.