Paperlane

no. 11 · Monday 9 November 2026

Descending Everest, Part I: Oracle Complexity of Convex Optimization under $(L_0,L_1)$-Smoothness

Mikhail Rudomanov, Ivan Fomin, Alexander V. Gasnikov and Fedor S. Stonyakin

math.OC · v2 · code · 43 pp

Abstract

For convex $(L_0,L_1)$-smooth functions, the curvature may grow together with the gradient norm. Therefore, even when $\|x^0-x^*\|\le R$, the gradient and the optimality gap at the starting point may be exponentially large in $L_1R$, and the bound $\sqrt{L_0R^2/\varepsilon}$, 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_0R^2/\varepsilon\ge1$, the optimal number of oracle calls $N$ satisfies $1+N=\widetildeΘ(\sqrt{L_0R^2/\varepsilon}+L_1R)$. The upper bound reads $O(\sqrt{L_0R^2/\varepsilon}+(1+L_1R)\log(2+L_1R))$: the method first passes through the large-gradient regime in $O(1+L_1R)$ 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\varepsilon$, the optimal bound becomes $1+N=\widetildeΘ(\sqrt{L_0R^2/\varepsilon}+(L_1R)^{2/3})$.

code
github.com/chitoraphelion/descending-everest-with-first-order-oracles
comments
43 pages, 4 algorithms, 2 tables. A Russian version of the paper is available at https://github.com/chitoraphelion/descending-everest-with-first-order-oracles
fields
Optimization and Control
pdf ↗ page arXiv:2610.21461 ↗