no. 8 · Wednesday 4 November 2026
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 $\mathbb{R}^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\cdot R\cdot\sqrt{\min\{d,\log n\}/n}$. Notably, when the dimension is fixed, the minimax error decays as $1/\sqrt{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.
- comments
- 25 pages, 2 figures. Substantially revised and expanded; sharp minimax bounds after optimizing over constant stepsizes. Title and abstract updated
- fields
- Optimization and Control