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 $\|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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.19240
curl -X POST /api/v1/records/arxiv/2607.19240/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.19240/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'