General Holder Smooth Convergence Rates Follow From Specialized Rates Assuming Growth Bounds
Author:
Preprint
Abstract
Often in the analysis of first-order methods for both smooth and nonsmooth optimization, assuming the existence of a growth/error bound or KL condition facilitates much stronger convergence analysis. Hence separate analysis is typically needed for the general case and for the growth bounded cases. We give meta-theorems for deriving general convergence rates from those assuming a growth lower bound. Applying this simple but conceptually powerful tool to the proximal point, subgradient, bundle, dual averaging, gradient descent, Frank-Wolfe, and universal accelerated methods immediately recovers their known convergence rates for general convex optimization problems from their specialized rates. New convergence results follow for bundle methods, dual averaging, and Frank-Wolfe. Our results can lift any rate based on H\"older continuous gradients and H\"older growth bounds. Moreover, our theory provides simple proofs of optimal convergence lower bounds under H\"older growth from textbook examples without growth bounds.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- A Simple Nearly Optimal Restart Scheme For Speeding Up First-Order MethodsFoundations of Computational Mathematics, 2021
- Linear convergence of first order methods for non-strongly convex optimizationMathematical Programming, 2018
- Rate of Convergence of the Bundle MethodJournal of Optimization Theory and Applications, 2017
- From error bounds to the complexity of first-order descent methods for convex functionsMathematical Programming, 2016
- New fractional error bounds for polynomial systems with applications to Hölderian stability in optimization and spectral theory of tensorsMathematical Programming, 2014
- Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimizationMathematical Programming, 2013
- Primal-dual subgradient methods for convex problemsMathematical Programming, 2007
- Weak Sharp Minima in Mathematical ProgrammingSIAM Journal on Control and Optimization, 1993
- Finite termination of the proximal point algorithmMathematical Programming, 1991
- Monotone Operators and the Proximal Point AlgorithmSIAM Journal on Control and Optimization, 1976