Sharp Dimension Dependence for the Last Iterate of the SubGradient Method

Abstract

We study the last iterate of the projected subGradient Method (sGM) for convex Lipschitz objectives defined on ${\mathbb{R}}^d$. We prove that, for a finite horizon $n$ and a constant stepsize $\hat{I}\cdot =\hat{I}˜(1/\sqrt{n})$, the last iterate achieves an optimization error of order $d/\sqrt{n}$, showing that the extra $\log n$ factor appearing in high dimensions is unnecessary in every fixed dimension. We complement this result with a matching linear-in-$d$ lower bound and show that the sharp worst-case dimension-horizon dependence is of order $\min \{d,\log n\}/\sqrt{n}$. This solves, in particular, a COLT open problem posed by Koren and Segal in 2020 and shows that the correct dependence on the dimension is linear rather than logarithmic.