Descending Everest, Part I: Oracle Complexity of Convex Optimization under (L 0,L 1) -Smoothness
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: I'm Ada.
Emmy: And I'm Emmy, here with Kolya.
Ada: We're looking at the paper: "Descending Everest, Part I".
Emmy: Here's the gist of the paper. Descending Everest with First-Order Oracles determines that for convex (L0, L1)-smooth functions, even when a bound R on the distance to a minimizer is known, the oracle complexity is bounded by L0R2/ε + L1R up to logarithmic factors <ref:2610.21461#pg6>.
Ada: Problem Setting and Function Class The paper considers unconstrained convex optimization problems where the function f: R d → R is a convex differentiable (L0, L1)-smooth function attaining its minimum at x∗ <ref:2610.21461#pg4>.
Emmy: The (L0, L1)-smoothness condition is defined by ∇f(x) - ∇f(y)k ≤ lsup u∈
x,y: k∇f(u)k for a continuous nondecreasing function l:
0, ∞) → (0, ∞), specifically Fd L0,L1 <ref:2610.21461#pg6>. [Ada: The class PR consists of functions in Fd L0,L1 that have a minimizer x∗ with kx∗k ≤ R the radius-only class <ref:2610.21461#pg6>.
Paper summary: Ada: We've covered the main points of "Descending Everest, Part I: Oracle Complexity of Convex Optimization under (L 0,L one)-Smoothness", focusing on how the complexity changes with those L zero and L one parameters <ref:2610.21461#pg1,Oracle Complexity of Convex Optimization under>. The paper really establishes a concrete bound for this class of functions.
Emmy: So the authors are essentially saying that even when you know where the minimum is relatively close—within distance R —the complexity isn't just a simple function of the smoothness constants; it has to explicitly track how much L one influences things <ref:2610.21461#pg1>.
Kolya: I think what this means for the broader research area is that we need to be more precise when we talk about deterministic optimization methods in non-standard settings, especially where local properties like smoothness are not just simple constants but depend on the gradient itself.
Ada: Precisely. And they provide a concrete upper bound on oracle complexity that matches their lower bound, which means this result is robust for this class of problems and it's the best we can expect with deterministic first-order methods.
Emmy: The authors are focused on showing that the cost of passing through those regions of large gradients—that L one term—is real and cannot be ignored in the final complexity analysis <ref:2610.21461#pg1>.
Kolya: And if you look at the context, they also point out a limitation: their lower bound might not fully capture everything because of how they chose certain chains and shifts in their proof. That's a necessary caveat to keep in mind when applying this result to specific scenarios.
Ada: So to wrap up, the complexity is L zero times R squared divided by epsilon plus that term involving L one and that part involving L one comes from the difficulty of handling those steep gradient regions <ref:2610.21461#pg1>.
Emmy: It’s a reminder that in these settings, you can't rely on simpler bounds; you have to account for the specific way curvature and gradient norm interact. That's what "Descending Everest, Part I: Oracle Complexity of Convex Optimization under (L 0,L one)-Smoothness" is about <ref:2610.21461#pg1,Oracle Complexity of Convex Optimization under>.
Conclusion: Ada: So we’ve gone through how the authors built up this new complexity bound for convex optimization problems where you know where your minimum is located, but that location is only within a certain distance R of it.
Emmy: Yeah, they're tackling these functions that have a specific kind of smoothness called L zero L one smoothness, which involves how the gradient changes between different points.
Kolya: And the main point they’re driving home is that even when you have this radius R bound, the cost of finding the solution isn't just about R squared times something simple; it has this extra term tied to L one.
Ada: Right. The authors show that for deterministic first-order methods, they managed to match their upper and lower bounds exactly up to some logarithmic factors.
Emmy: That matching is significant because it suggests that the structure of these problems dictates a certain complexity, and they've found the right tools to prove that structure holds true.
Kolya: I’m interested in what this means for real-world applications; if you’re dealing with optimization where you can estimate how far from the solution you are, this bound gives us a concrete idea of the cost of finding it.
Ada: It tells us that the cost scales like L zero times R squared divided by epsilon plus that L one term, which is essentially accounting for those steep gradient regions they mentioned earlier.
Emmy: And honestly, if you look at how they handled those first stage methods—SHERPA and ICEPICK—it shows how important it is to design a sequence of steps that deals with the worst parts of the problem first.
Kolya: The fact that this complexity involves L one, which measures how fast the gradient itself is changing, suggests that the sensitivity of these optimization problems to small changes in function behavior is a key factor in their difficulty.
Ada: It’s a lot to take in, but it boils down to this: for these specific smooth functions, you get this complexity bound that seems tight.
Emmy: And because they matched the lower bound so well, we can trust that this L zero R squared over epsilon plus L one term is really what it takes for deterministic methods here.
Kolya: It sets a benchmark, though I’m still wondering if the constant hidden inside those logarithmic factors is actually going to be manageable when you try to put this into a real solver.
Ada: That’s the next thing we need to look at, figuring out exactly what those hidden constants turn out to be in practice.
MIRIAI Moscow Independent Research Institute of Artificial Intelligence · Yandex
math.OC
Submitted: 2026-10-15
Updated: 2026-11-05
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
Code: https://github.com/chitoraphelion/descending-everest-with-first-order-oracles
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 81/100
The gist: Descending Everest with First-Order Oracles determines that for convex (L0, L1)-smooth functions, even when a bound R on the distance to a minimizer is known…
Key concepts
- (L0,L1)-smoothness
- This condition describes how much the gradient of a function can change between two points. It involves a continuous nondecreasing function 'l' that bounds the difference between gradients, ensuring the function has controlled curvature across its domain.
- Radius-only class (PR)
- This class consists of convex functions where you only know that the distance from any point to the minimum is less than or equal to a fixed radius R. The complexity analysis focuses on finding the minimum within this bounded region.
- Upper and Lower Bounds
- The paper establishes an upper bound by constructing a specific algorithm (two-stage method) and a lower bound using geometric principles like chains and orthogonal invariance. Matching these bounds proves the optimal complexity is asymptotically L0R^2/epsilon + L1R.
Terminology
Summary
Descending Everest with First-Order Oracles determines that for convex (L0, L1)-smooth functions, even when a bound R on the distance to a minimizer is known, the oracle complexity is bounded by L0R2/ε + L1R up to logarithmic factors <ref:2610. p. 1 How many oracle calls does this cost the best
first-order method if only an upper bound R on the distance from the starting point to a
minimizer is known? In this paper we answer this question: up to logarithmic factors, the
cost is L1R.Where the paper says it
Problem Setting and Function Class
The paper considers unconstrained convex optimization problems where the function f: R d → R is a convex differentiable (L0, L1)-smooth function attaining its minimum at x∗ <ref:2610.21461#pg4>. The (L0, L1)-smoothness condition is defined by ∇f(x) - ∇f(y)k ≤ lsup u∈[x,y] k∇f(u)k for a continuous nondecreasing function l: [0, ∞) → (0, ∞), specifically Fd L0,L1 <ref:2610. p. 3 1 (Function class). Let ℓ : [0, ∞) → (0, ∞) be a continuous nondecreasing function. Two problem classes are
considered. ▷ PR consists of all functions f ∈ Fd
L0,L1
, d ≥ 1, that have a minimizer x
∗ with kx
∗k ≤ R
(the radius-only class).Where the paper says it
Where the paper says it
Upper Bound Construction
The optimal complexity for arbitrary deterministic first-order methods is determined by a two-stage method designed to pass through the large-gradient regime and then use a standard accelerated method <ref:2610.21461#pg8>. The first stage, SHERPA, passes through the large-gradient regime in O(1 + L1R) iterations with an inexact line search ICEPICK <ref:2610. p. 2 At the
first stage, the method SHERPA passes through the large-gradient regime in O(1 + L1R)
iterations. This is an accelerated method with the inexact line search ICEPICK, based on
Nesterov’s framework of estimating sequences (Nesterov, 2018). ▷ The second stage (the method CRUISE) is started from x
′
. In a neighborhood of such
a point, a function of the class behaves like a function with 2L0-Lipschitz gradient, and
we run the standard accelerated method with a constant stepsize 1/(2L0), using the
analysis of Tyurin (2026).Where the paper says it
Where the paper says it
Lower Bound Derivation
The lower bound is established using chains and the orthogonal invariance principle on functions conjugate to strongly convex functions on a polytope <ref:2610.21461#pg10>. The main result shows that for arbitrary deterministic first-order methods, the smallest number of calls N satisfies 1 + N ≥ 1/29 h 1 + r L0R2/ε + L1R p log(2 + L1R) <ref:2610. p. 1 We consider arbitrary deterministic first-order methods: a method may query
the gradient at any points and output any point, and every oracle call is counted. We prove
that the smallest number of calls N for which there exists a deterministic first-order method
solving the problem for all functions of the class in all dimensions satisfies2
1 + N ≥
1
29
h
1 + r
L0R2
ε
+
L1R
p
log(2 + L1R)
i
,
1 + N ≤ 5
r
L0R2
ε
+ C (1 + L1R)log(2 + L1R)
with an absolute constant
p
C (Theorems 3.Where the paper says it
Comparison and Final Complexity
The optimal complexity is found to be L0R2/ε + L1R up to logarithmic factors, as the upper and lower bounds match asymptotically <ref:2610.21461#pg10>. If the initial optimality gap is at most 4ε, the complexity drops to 1 + N = Θe r L0R2/ε + (L1R) 2/3 <ref:2610. p. 2 Bounded initial optimality gap. If it is additionally known that f(x
0
) − f
∗ ≤ 4ε, the
complexity drops to
1 + N = Θe
r
L0R2
ε
+ (L1R)
2/3
(Appendix B).Where the paper says it
Comparison with Known Results
Known bounds for deterministic methods without a bound on the initial optimality gap contain either a term (L1R) 2 or higher, or a factor equal to the logarithm of the ratio of the initial gap f(x0)-f∗ to ε or to L0/L2 1 (Table 2 <ref:2610.21461#pg5>. On the radius-only class, this factor may be of order L1R <ref:2610. p. 2 Known bounds for the convex deterministic case that
do not use a bound on the initial optimality gap contain either a term (L1R)
2 or higher, or a
factor equal to the logarithm of the ratio of the initial gap f(x
0
)−f
∗
to ε or to L0/L
2
1
(Table 2). On the radius-only class, this factor may be of order L1R. We prove
that the smallest number of calls N for which there exists a deterministic first-order method
solving the problem for all functions of the class in all dimensions satisfies2
1 + N ≥
1
29
h
1 + r
L0R2
ε
+
L1R
p
log(2 + L1R)
i
,
1 + N ≤ 5
r
L0R2
ε
+ C (1 + L1R)log(2 + L1R)
with an absolute constant
p
C (Theorems 3. Thus, the optimal complexity is
L0R2/ε + L1R up to logarithmic factors, and the logarithmic factors affect only the L1R
2Here and below, the lower bounds are proved for L0R
2 ≥ ε.Where the paper says it
Where the paper says it
Conclusion and Open Questions
The cost of passing through the region of large gradients is L1R up to logarithmic factors <ref:2610. p. 1 Therefore, before the method reaches the region of small
gradients, where the familiar theory for problems with Lipschitz gradient applies, it has to
pass through the region of large gradients. How many oracle calls does this cost the best
first-order method if only an upper bound R on the distance from the starting point to a
minimizer is known? Bounded initial optimality gap. If it is additionally known that f(x
0
) − f
∗ ≤ 4ε, the
complexity drops to
1 + N = Θe
r
L0R2
ε
+ (L1R)
2/3
(Appendix B). How many oracle calls does this cost the best
first-order method if only an upper bound R on the distance from the starting point to a
minimizer is known? In this paper we answer this question: up to logarithmic factors, the
cost is L1R. We call the variant of this method that we use CRUISE. The lower bound follows
the classical scheme: a chain and the orthogonal invariance principle (Nemirovsky and Yudin,
1983, Nesterov, 2018, Carmon et al.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Fixed Dimension Analysis
For fixed dimension d, the center-of-gravity method solves the problem with fixed normalized accuracy L2 1ε/L0 in a number of calls logarithmic in L1R. This shows that a linear lower bound in L1R up to logarithms cannot be realized by a family of fixed dimension. p. 2 2) gives the bound O
1 + p
L0R2/ε
without logarithms, and we use it at
the second stage. Lower bounds in the generalized setting were previously known only for
specific methods, for example, for gradient descent with a constant stepsize (Zhang et al.Where the paper says it
Summary Table
Table 2 collects known upper bounds for the convex deterministic case, showing complexities like sym accelerated method with inexact line search O q L0R2ε + O(1 + L1R)log(2 + L1R). The paper's result is sym accelerated method with inexact line search O q L0R2ε + O(1 + L1R)log(2 + L1R) <ref:2610.21461#pg6>.
Auxiliary Inequalities
Lemma A.3 proves that the step length of the descent lemma is at most 1/(4L1) <ref:2610. p. 5 The length of such a step is at most
1/(4L1). Over this distance, the local smoothness constant changes by a factor of at most
e
1/4 (Lemma A. 3 is given in Appendix A. The number of steps m depends
logarithmically on L0r
2/δ and L1r. The following lemma shows that it suffices
to check it along lines, and that for twice continuously differentiable functions it is equivalent
to the familiar Hessian bound. Its proof is given in Appendix A. Therefore, even when kx
0−x
∗k ≤ R, the gradient and the optimality gap at the starting point may be exponentially large in L1R, and the bound p
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 = Θe
p
L0R2/ε + L1R
.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Bounded Initial Optimality Gap Case
In the class P∆ with ∆ greater than 4ε but smaller than the right-hand side of (A.3), only the upper bound of Theorem B. p. 2 After that, the accelerated method of Tyurin
(2026, Theorem 3. 2) gives the bound O
1 + p
L0R2/ε
without logarithms, and we use it at
the second stage. The set X
∗ = arg min f is convex and closed, so the condition below
is equivalent to dist(x
0
, X∗
) ≤ R, and x
∗ may be taken to be the minimizer closest to x
0
. 1
arXiv:2610. 6 Number of first-stage iterations
The initial optimality gap is unknown and may be exponentially large in L1R, so a bound in
terms of this gap does not give the desired guarantee in terms of the radius. Instead, we use
the two quantities bounded by Lemma 3. The (L0, L1)-smoothness condition was proposed on the basis of empirical observations
in neural network training. Experiments with an LSTM language model revealed a positive
correlation between the local smoothness constant and the gradient norm, which motivated
the model with the dependence L0 + L1k∇f(x)k (Zhang et al.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Conclusion
If the initial optimality gap is at most 4ε, the optimal complexity is L0R2/ε + (L1R) 2/3 <ref:2610.21461#pg6>. The cost of passing through the region of large gradients is L1R up to logarithmic factors <ref:2610.21461#pg6>. The authors conclude that for L0R2 ≥ ε the optimal complexity is 1 + N = Θe 1 + r L0R2/ε + L1R <ref:2610. p. 0 Therefore, even when kx
0−x
∗k ≤ R, the gradient and the optimality gap at the starting point may be exponentially large in L1R, and the bound p
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 = Θe
p
L0R2/ε + L1R
.Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Optimization of First-Order Methods for (L0, L1)-Smooth Functions: The improved system can determine that for convex (L0, L1)-smooth functions, even when the initial distance to a minimizer is bounded by R (kx 0 - x∗k ≤ R), the gradient and optimality gap may be exponentially large in L1R.
-
Complexity Bounds for Deterministic First-Order Methods: The system can calculate the optimal number of oracle calls N for arbitrary deterministic first-order methods, which satisfies 1 + N = Theta e(p L0R2/ε + L1R) up to logarithmic factors, and provides a specific upper bound O p L0R2/ε + (1 + L1R)log(2 + L1R).
-
Accelerated Method Design for Large Gradients: The system can construct a two-stage method SHERPA that first passes through the large-gradient regime in O(1 + L1R) iterations using an inexact line search, followed by a standard accelerated method with a constant stepsize to achieve the overall upper bound.
-
Handling Bounded Initial Optimality Gaps: When the initial optimality gap is known and bounded (f(x 0) - f∗ ≤ 4ε), the system can use Algorithm 4 with an appropriate positive initial weight to reduce the complexity to 1 + N = Theta e(r L0R2/ε + (L1R)2/3).
-
Lower Bound Verification for Generalized Smoothness: The system can verify lower bounds for arbitrary deterministic methods by constructing chains conjugate to strongly convex functions on a polytope, which captures the growth of curvature together with the gradient norm.
-
Dimension-Dependent Complexity Analysis: For fixed dimension d, the system can solve the problem using the center-of-gravity method with O(d log2 sqrt(d R/min[R, ρε]) - log(1 - 1/e) k oracle calls.
Abstract
For convex (L 0,L 1) -smooth functions, the curvature may grow together with the gradient norm. Therefore, even when |x 0-x*| at most 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/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 0R 2/epsilon at least1, the optimal number of oracle calls N satisfies 1+N= Θ(sqrt L 0R 2/epsilon +L 1R). The upper bound reads O(sqrt L 0R 2/epsilon +(1+L 1R) (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 epsilon, the optimal bound becomes 1+N= Θ(sqrt L 0R 2/epsilon +(L 1R) 2/3).
Sources
- Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimization
- Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness
- Robustness to Unbounded Smoothness of Generalized SignSGD
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity
- On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization
- Parameter-Agnostic Optimization under Relaxed Smoothness
- Normalized First-Order Methods for Convex (L0, L1)-Smooth Optimization with Inexact Gradients
- A Few Accelerated Algorithms for Convex Optimization under $(H_0,H_1)$-Smoothness
- Linear Convergence Rate in Convex Setup is Possible! Gradient Descent Method Variants under $(L_0,L_1)$-Smoothness
- Nonlinearly Preconditioned Gradient Methods under Generalized Smoothness
- Parameter-free Clipped Gradient Descent Meets Polyak
- Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods
- Why gradient clipping accelerates training: A theoretical justification for adaptivity
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise