Descending Everest, Part I: Oracle Complexity of Convex Optimization under (L 0,L 1) -Smoothness

arXiv:2610.21461 · math.OC · Submitted 2026-10-15 · Read on arXiv

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

Where the paper says it

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.

21461#pg6>.

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

Where the paper says it

1 (Function class). Let ℓ : [0, ∞) → (0, ∞) be a continuous nondecreasing function.

21461#pg6>. 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. p. 4
Where the paper says it

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

21461#pg6>.

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

Where the paper says it

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

21461#pg9>. The second stage uses the standard accelerated method CRUISE with a constant stepsize 1/(2L0) starting from the point found in the first stage <ref:2610. p. 4
Where the paper says it

▷ 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).

21461#pg9>.

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

Where the paper says it

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.

21461#pg10>.

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

Where the paper says it

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

21461#pg4>.

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

Where the paper says it

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.

21461#pg10>. The lower bound for the radius-only class is shown to be 1 + N (PR) ≥ 1/29 h 1 + r L0R2/ε + L1R p log(2 + L1R) <ref:2610. p. 1
Where the paper says it

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 ≥ ε.

21461#pg10>.

Conclusion and Open Questions

The cost of passing through the region of large gradients is L1R up to logarithmic factors <ref:2610. p. 1

Where the paper says it

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?

21461#pg6>. If the initial optimality gap is at most 4ε, this cost drops to (L1R) 2/3 <ref:2610. p. 2
Where the paper says it

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

21461#pg4>. The authors note that the logarithmic factors in the upper bound come from the line search at the first stage <ref:2610. p. 1
Where the paper says it

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.

21461#pg9>. The lower bound is lost because of the choice of slopes and shifts of the chain <ref:2610. p. 2
Where the paper says it

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.

21461#pg10>.

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

Where the paper says it

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.

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

Where the paper says it

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.

21461#pg9>. Lemma A.4 shows that for x 6= 0 its curvature along the radius equals L0e L1x = L0 + L1k∇f(x)k, and in the tangential directions the curvature equals k∇f(x)k xk k ≤ L0e L1x, since e s − 1 ≤ ses <ref:2610.21461#pg9>. Lemma A.5 proves that the number of steps m depends logarithmically on L0r2/δ and L1r <ref:2610. p. 6
Where the paper says it

3 is given in Appendix A. The number of steps m depends logarithmically on L0r 2/δ and L1r.

21461#pg9>. The proof of Lemma 3. p. 3
Where the paper says it

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.

3 shows that the number of calls is at most m + 2 oracle calls <ref:2610. p. 0
Where the paper says it

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 .

21461#pg9>.

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

Where the paper says it

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.

7(b) is proved <ref:2610. p. 0
Where the paper says it

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.

21461#pg41>. A matching lower bound in terms of the dependence on ∆ is unknown <ref:2610. p. 9
Where the paper says it

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.

21461#pg41>. The exact dependence of the complexity on ∆/ε for ε. p. 1
Where the paper says it

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.

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

Where the paper says it

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 .

21461#pg6>.

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

  1. 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.

  2. 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).

  3. 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.

  4. 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).

  5. 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.

  6. 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

Related papers