{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-21","reactions":{}}