PreprintarXiv licencearXiv
A Minimax Analysis of the Last Iterate of the SubGradient Method in Finite Dimension
Abstract
We study the last iterate of the projected subGradient Method with a constant stepsize for convex L-Lipschitz objectives in ℝd, minimized over closed convex sets. Assuming that the initial iterate x1 has distance at most R from a minimizer, we establish matching upper and lower bounds on the minimax optimization error at xn, where the infimum is taken over constant stepsizes. Specifically, this error is of order L· R·√(min{d,log n}/n). Notably, when the dimension is fixed, the minimax error decays as 1/√n, without the extra logarithmic factor intrinsic to dimension-free analyses. Our analysis exploits a combinatorial argument based on linear algebra and novel geometric constructions.
Related
- The Last Iterate of the Projected Stochastic Subgradient Method Pays a Logarithm, Even in Dimension One
- Sampled-Max Subgradient Method for Convex Finite-Max Optimization
- Weak and Error-Bound Linear Convergence of a Safeguarded Anderson-Accelerated Subgradient Extragradient Method
- A stochastic subgradient method with optimal failure exponent
- A Shadow Sequence Technique for Last-Iterate Convergence Analysis of the Random Reshuffling Method: Relaxed Stepsize Conditions and Beyond
BibTeX
@misc{beretta2026minimax,
title = {{A Minimax Analysis of the Last Iterate of the SubGradient Method in Finite Dimension}},
author = {Guglielmo Beretta and Tommaso Cesari and Roberto Colomboni and Andrea Paudice},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2607.15980},
eprint = {2607.15980},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.15980},
}
RIS
TY - UNPB
TI - A Minimax Analysis of the Last Iterate of the SubGradient Method in Finite Dimension
AU - Guglielmo Beretta
AU - Tommaso Cesari
AU - Roberto Colomboni
AU - Andrea Paudice
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2607.15980
UR - https://arxiv.org/abs/2607.15980
AB - We study the last iterate of the projected subGradient Method with a constant stepsize for convex L-Lipschitz objectives in ℝ^d, minimized over closed convex sets. Assuming that the initial iterate x_1 has distance at most R from a minimizer, we establish matching upper and lower bounds on the minimax optimization error at x_n, where the infimum is taken over constant stepsizes. Specifically, this error is of order L· R·√(min{d,log n}/n). Notably, when the dimension is fixed, the minimax error decays as 1/√n, without the extra logarithmic factor intrinsic to dimension-free analyses. Our analysis exploits a combinatorial argument based on linear algebra and novel geometric constructions.
ER -