Paperlane

no. 8 · Wednesday 4 November 2026

A Minimax Analysis of the Last Iterate of the SubGradient Method in Finite Dimension

Guglielmo Beretta, Tommaso Cesari, Roberto Colomboni and Andrea Paudice

math.OC · v3 · 25 pp

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
pdf ↗ page arXiv:2607.15980 ↗