Optimal first-order methods for convex functions with a quadratic upper bound

arXiv2205.15033MaRDI QIDQ6400539FDOQ6400539

Aymeric Dieuleveut, Baptiste Goujaud, Adrien B. Taylor

Publication date: 30 May 2022

Abstract: We analyze worst-case convergence guarantees of first-order optimization methods over a function class extending that of smooth and convex functions. This class contains convex functions that admit a simple quadratic upper bound. Its study is motivated by its stability under minor perturbations. We provide a thorough analysis of first-order methods, including worst-case convergence guarantees for several algorithms, and demonstrate that some of them achieve the optimal worst-case guarantee over the class. We support our analysis by numerical validation of worst-case guarantees using performance estimation problems. A few observations can be drawn from this analysis, particularly regarding the optimality (resp. and adaptivity) of the heavy-ball method (resp. heavy-ball with line-search). Finally, we show how our analysis can be leveraged to obtain convergence guarantees over more complex classes of functions. Overall, this study brings insights on the choice of function classes over which standard first-order methods have working worst-case guarantees.

This page was built for publication: Optimal first-order methods for convex functions with a quadratic upper bound

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6400539)