A Complete Characterization of Optimal Subgradient Methods for Lipschitz Convex Minimization

2026/07/21 by Aaron Zoll, Benjamin Grimmer · 1 citation
#math.OC

paper · pdf

Abstract

We consider the design of optimal fixed-step first-order methods for M-Lipschitz convex optimization given ‖x₀-x_⋆‖≤ 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/√(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~\citeconstructive_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.

Cited by

• Implicit Primal-Dual Guarantees in Unconstrained First-Order Minimization

Related

• Optimal Subgradient Methods for Lipschitz Convex Optimization with Error Bounds
• Accelerated first-order methods for large-scale convex minimization
• "Efficient" Subgradient Methods for General Convex Optimization
• Subgradient methods with variants of Polyak step-size for quasi-convex optimization with inequality constraints for analogues of sharp minima
• Primal subgradient methods with predefined stepsizes