Descending Everest with First-Order Oracles: Oracle Complexity of Convex Optimization under (L0,L1)-Smoothness
Abstract
For convex (L0,L1)-smooth functions, the curvature may grow together with the gradient norm. Therefore, even when |x0−x*|≤ R, the gradient and the optimality gap at the starting point may be exponentially large in L1R, and the bound √(L0R2/ε), 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 L0R2/ε≥1, the optimal number of oracle calls N satisfies 1+N=Θ̃(√(L0R2/ε)+L1R). The upper bound reads O(√(L0R2/ε)+(1+L1R)log(2+L1R)): the method first passes through the large-gradient regime in O(1+L1R) 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ε, the optimal bound becomes 1+N=Θ̃(√(L0R2/ε)+(L1R)2/3).
Related
- Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex (L0,L1)-Smooth Functions
- Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness
- Tight Sampling Complexity with Stochastic Gradient Oracles in Fixed Dimensions
- Complexity analysis of trust-region methods under (α,L0,L1)-smoothness
- Near-Optimal Convex Optimization with Lazy Second-Order Oracles
BibTeX
@misc{rudomanov2026descending,
title = {{Descending Everest with First-Order Oracles: Oracle Complexity of Convex Optimization under $(L_0,L_1)$-Smoothness}},
author = {Mikhail Rudomanov and Ivan Fomin and Alexander V. Gasnikov and Fedor S. Stonyakin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.21461},
eprint = {2610.21461},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.21461},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Descending Everest with First-Order Oracles: Oracle Complexity of Convex Optimization under (L_0,L_1)-Smoothness
AU - Mikhail Rudomanov
AU - Ivan Fomin
AU - Alexander V. Gasnikov
AU - Fedor S. Stonyakin
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.21461
UR - https://arxiv.org/abs/2610.21461
AB - For convex (L_0,L_1)-smooth functions, the curvature may grow together with the gradient norm. Therefore, even when |x^0−x^*|≤ R, the gradient and the optimality gap at the starting point may be exponentially large in L_1R, and the bound √(L_0R^2/ε), 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/ε≥1, the optimal number of oracle calls N satisfies 1+N=Θ̃(√(L_0R^2/ε)+L_1R). The upper bound reads O(√(L_0R^2/ε)+(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ε, the optimal bound becomes 1+N=Θ̃(√(L_0R^2/ε)+(L_1R)^2/3).
ER -