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

Abstract

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 starting point may be exponentially large in $L_{1}R$, and the bound $\sqrt{L_0{R}^2/\epsilon }$, known for the accelerated method on functions with Lipschitz gradient, no longer describes the complexity of the problem. We determine the oracle complexity of this class for arbitrary deterministic first-order methods: for $L_0{R}^2/\epsilon \ge 1$, the optimal number of oracle calls $N$ satisfies $1+N=\tilde{\Theta }(\sqrt{L_0{R}^2/\epsilon }+L_{1}R)$. The upper bound reads $O(\sqrt{L_0{R}^2/\epsilon }+(1+L_{1}R)\log (2+L_{1}R))$: the method first passes through the large-gradient regime in $O(1+L_{1}R)$ iterations with an inexact line search, and then the standard accelerated method with a constant stepsize takes over. The lower bound is obtained by means of chains and the orthogonal invariance principle on functions conjugate to strongly convex functions on a polytope. If the initial optimality gap is at most $4\epsilon$, the optimal bound becomes $1+N=\tilde{\Theta }(\sqrt{L_0{R}^2/\epsilon }+(L_{1}R{)}^{2/3})$.

arXiv comment43 pages, 4 algorithms, 2 tables. A Russian version of the paper is available at https://github.com/chitoraphelion/descending-everest-with-first-order-oracles