Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods

We study gradient methods for optimizing $(L_0, L_1)$-smooth functions, aclass that generalizes Lipschitz-smooth functions and has gained attention forits relevance in machine learning.We provide new insights into the structure of this function class and developa principled framework for analyzing optimization methods in this setting.While our convergence rate estimates recover existing results for minimizingthe gradient norm in nonconvex problems, our approach significantly improvesthe best-known complexity bounds for convex objectives.Moreover, we show that the gradient method with Polyak stepsizes and thenormalized gradient method achieve nearly the same complexity guarantees asmethods that rely on explicit knowledge of $(L_0, L_1)$.Finally, we demonstrate that a carefully designed accelerated gradientmethod can be applied to $(L_0, L_1)$-smooth functions, further improving allprevious results.