Id: arxiv/2607.19240 Url: https://arxiv.org/abs/2607.19240 Tags: math.OC Score: 0 Title: A Complete Characterization of Optimal Subgradient Methods for Lipschitz Convex Minimization Domain: math.OC Source: arxiv Authors: Aaron Zoll, Benjamin Grimmer Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-21 Page: https://delphi.science/r/arxiv/2607.19240 We consider the design of optimal fixed-step first-order methods for $M$-Lipschitz convex optimization given $\|x_0-x_\star\|\leq 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/\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…