Descending Everest with First-Order Oracles: Oracle Complexity of Convex Optimization under $(L_0,L_1)$-Smoothness

Mikhail Rudomanov, Ivan Fomin, Alexander V. Gasnikov +1

For convex $(L_0,L_1)$-smooth functions, the curvature may grow together with the gradient norm. Therefore, even when $\Vert x^0-x^{\ast }\Vert \le R$, the gradient and the optimality gap at the…