A Complete Characterization of Optimal Subgradient Methods for Lipschitz Convex Minimization

We consider the design of optimal fixed-step first-order methods for $M$-Lipschitz convex optimization given $\mathrm{\parallel }{x}_0-x_{\star }\mathrm{\parallel }\le D$. Prior works have identified several distinct fixed-step methods, parameterized by a matrix of stepsizes $W$, with the (information-theoretic) minimax optimal rate $MD\mathrm{/}\sqrt{N+1}$ of objective gap convergence. We provide a complete characterization of every optimal fixed-step method. Moreover, we show every optimal fixed-step method can be derived from the constructive approach of~\cite{constructive_approach} and provide a polyhedral representation of the set of optimal methods through proof multipliers. From this characterization, we show that no anytime optimal fixed-step subgradient methods exist.