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

Understand

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.