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.

arXiv comment25 pages, 2 figures. Substantially revised and expanded; sharp minimax bounds after optimizing over constant stepsizes. Title and abstract updated