← All papers

Anytime Last Iterates in Fixed Dimension

Abstract

The standard horizon-free subgradient schedules, $\eta_t\asymp t^{-1/2}$ for convex objectives and $\eta_t\asymp t^{-1}$ under strong convexity, have last-iterate guarantees worse than the optimal rates by a logarithmic factor. Known matching examples use dimension growing with the horizon. We prove that this loss disappears in every fixed dimension for deterministic projected subgradient descent. The key is a pathwise conversion theorem for arbitrary positive and adaptive steps. On any suffix, the terminal objective can exceed the best suffix value by at most twice the suffix trajectory rank times the Lipschitz constant times the largest realized step length. The proof combines last exits from consecutive objective levels with a rank bound for obtuse vectors in a common open halfspace. Combining this conversion with suffix regret yields $O(dDL/\sqrt n)$ for $\eta_t=D/(L\sqrt t)$ on a domain of diameter $D$, and $O(dL^2/(\mu n))$ for both standard strongly convex schedules. Thus their horizon dependence is minimax optimal for every fixed dimension. The result complements recent dimension-free anytime impossibility and sharp horizon-tuned constant-step theory. It also gives data-dependent bounds in terms of trajectory rank and realized, rather than worst-case, step lengths.

Keywords: last-iterate convergence, anytime guarantees, subgradient method, convex optimization, step-size schedules, suffix bounds

Full text (PDF) · source repository