General Holder Smooth Convergence Rates Follow From Specialized Rates Assuming Growth Bounds
From MaRDI portal
Publication:6365762
DOI10.1007/S10957-023-02178-4arXiv2104.10196MaRDI QIDQ6365762
Publication date: 20 April 2021
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.
Numerical mathematical programming methods (65K05) Convex programming (90C25) Nonlinear programming (90C30)
This page was built for publication: General Holder Smooth Convergence Rates Follow From Specialized Rates Assuming Growth Bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6365762)
