OpenAlex ·

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

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

Published
Source
OpenAlex
Published in
arXiv (Cornell University)
DOI
10.48550/arxiv.2610.21461
Original
Read it at the publisher
Topics
Artificial IntelligenceComputational ComplexityNumerical Analysis

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})$.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

Read it on ReadSearch

Each opens after you create an account, and brings you back to this paper.

Already a reader? Sign in

All new papers in Artificial Intelligence

Get the few papers worth your time in Artificial Intelligence every morning.

ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.

Papers belong to their authors and publishers; every page here links to the original. All research topics