{"ID":2829163,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.13863","arxiv_id":"2512.13863","title":"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.","short_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 co...","url_abs":"https://arxiv.org/abs/2512.13863","url_pdf":"https://arxiv.org/pdf/2512.13863v1","authors":"[\"Alex L. Wang\"]","published":"2025-12-15T19:51:20Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}