OpenAlex ·
Descending Everest, Part I: Oracle Complexity of Convex Optimization under $(L_0,L_1)$-Smoothness
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.21461
- Original
- Read it at the publisher
- Topics
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.
More in Artificial Intelligence
Parallel Repetition for Entangled Games via Conditional Relative Entropy
Concrete Functions in Private Simultaneous Quantum Messages: Quantum Advantages and Structural Limitations
Parameterized Complexity of Isometric Path Cover: Treewidth and Diameter
Unconditional Quantum PAC Learning Advantage in the Large Error Regime
Electrostatic Limits on Quantum Spatial Search
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.