Optimal Subgradient Methods for Lipschitz Convex Optimization with Error Bounds

Abstract

We study the iteration complexity of Lipschitz convex optimization problems satisfying a general error bound. We show that for this class of problems, subgradient descent with either Polyak stepsizes or decaying stepsizes achieves minimax optimal convergence guarantees for decreasing distance-to-optimality. The main contribution is a novel lower-bounding argument that produces hard functions simultaneously satisfying zero-chain conditions and global error bounds.