🔢 mathematics

On the Condition Number Dependency in Bilevel Optimization

This paper establishes new oracle complexity lower bounds for bilevel optimization with a nonconvex upper level and strongly convex lower level, demonstrating a provable gap in condition number dependency between bilevel and minimax problems and extending these results to various settings including high-order smooth, stochastic, and convex hyper-objective cases.

Original authors: Lesi Chen, Jingzhao Zhang

Published 2026-06-10

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: Lesi Chen, Jingzhao Zhang

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the perfect recipe for a cake. But there’s a catch: you can’t just mix ingredients and bake. First, you have to figure out the perfect temperature for your oven. And to know the perfect temperature, you have to understand how the humidity in the kitchen affects the batter.

This is what mathematicians call Bilevel Optimization. It’s a two-layer puzzle:

The Lower Level: You solve a specific sub-problem (like finding the best oven temperature).
The Upper Level: You use that answer to solve the main problem (baking the best cake).

The paper "On the Condition Number Dependency in Bilevel Optimization" by Lesi Chen and Jingzhao Zhang is essentially a report card on how hard this two-layer puzzle is to solve using computers.

The "Stiffness" Problem (Condition Number)

In math, there’s a concept called the Condition Number (let’s call it $\kappa$ ). Think of this as the "Stiffness" or "Sensitivity" of the problem.

Low Stiffness: The problem is smooth and easy to navigate. Like rolling a ball down a gentle hill.
High Stiffness: The problem is jagged, narrow, and tricky. Like trying to balance a pencil on its tip while an earthquake happens.

The bigger the Condition Number, the harder it is for a computer algorithm to find the answer. The paper asks: How much does the difficulty increase as the problem gets "stiffer"?

The Big Discovery: Bilevel is Harder Than It Looks

Previously, scientists knew that solving these two-layer puzzles was harder than solving single-layer puzzles. But they weren’t sure how much harder, specifically regarding that "Stiffness" factor.

The authors proved a new Lower Bound. In plain English, a "lower bound" is a proof that says, "No matter how smart your algorithm is, it cannot be faster than this." It’s the absolute minimum amount of work required.

Here is what they found, using simple analogies:

1. The "Chain Reaction" Analogy

Imagine the lower-level problem (the oven temperature) is a long chain of dominoes. To find the answer, the computer has to knock over dominoes one by one.

In simpler problems (like Minimax games, which are like two players competing), the chain is short.
In Bilevel problems, the authors showed that the structure of the problem forces the computer to deal with a much longer chain.

They proved that because the upper level depends on the lower level, the "Stiffness" ( $\kappa$ ) gets amplified. It’s not just a little harder; it’s significantly harder.

2. The Specific Results (The "Scorecard")

The paper compares their new "minimum difficulty" scores against previous estimates. Here is the breakdown in everyday terms:

For Standard Problems (Deterministic):
- Old View: People thought the difficulty grew with the square root of the stiffness ( $\sqrt{\kappa}$ ).
- New Proof: The authors proved the difficulty actually grows with $\kappa^{2.5}$ (or $\kappa^{5/2}$ ).
- Analogy: If the stiffness doubles, the old view said the work increases by about 1.4x. The new proof says the work actually increases by about 5.6x. It’s much tougher than we thought!
For Noisy/Random Problems (Stochastic):
- Sometimes, the data is noisy (like trying to bake while the recipe book is vibrating).
- Old View: The difficulty was thought to be related to $\kappa^{1/3}$ .
- New Proof: The authors proved it’s related to $\kappa^4$ .
- Analogy: Noise makes the problem explode in difficulty. If the stiffness doubles, the work doesn’t just double; it increases by 16x. The authors argue that noise (variance) is the real bottleneck here, not just the complexity of the calculation.
For "Nice" Problems (Convex):
- If the problem is well-behaved (convex), it’s easier.
- Old View: Difficulty grew with $\kappa$ .
- New Proof: Difficulty grows with $\kappa^{1.5}$ ( $\kappa^{3/2}$ ).
- Analogy: Even in the "nice" scenarios, the two-layer structure adds extra friction.

Why Does This Matter?

The paper doesn’t just say "it’s hard." It explains why.

They identified two sources of difficulty in Bilevel Optimization:

The Coupling Variable ( $y$ ): This represents the effort to solve the lower-level problem (finding the oven temp).
The Rescaling Variable ( $z$ ): This represents how sensitive the upper-level problem is to changes in the lower level.

In previous studies, people only looked at one of these. The authors showed that both contribute to the difficulty. In noisy environments, the "Rescaling" (sensitivity) is the main culprit that makes the problem so hard.

The Bottom Line

This paper is a mathematical "speed limit sign." It tells computer scientists:

"Stop trying to build an algorithm that solves this problem faster than $\kappa^{2.5}$ times. It’s mathematically impossible. Instead, focus on algorithms that get as close to this limit as possible."

They also showed that for some specific cases (where the lower level is a simple quadratic equation), current algorithms are already very close to this theoretical limit. This means we are nearing the "end of the road" for improving those specific methods—we can’t get much faster than we already are.

Technical Summary: On the Condition Number Dependency in Bilevel Optimization

Problem Statement
This paper investigates the oracle complexity of finding an $\epsilon$ -stationary point for nonconvex-strongly-convex (NC-SC) bilevel optimization problems. The problem is formulated as minimizing a hyper-objective $F(x) = f(x, y^*(x))$ , where $y^*(x) = \arg \min_y g(x, y)$ is the solution to a strongly convex lower-level problem. While recent works have established upper bounds of $\tilde{O}(\bar{\kappa}_y^4 \epsilon^{-2})$ for deterministic smooth NC-SC bilevel problems (where $\bar{\kappa}_y$ is the global condition number), the optimal dependency on the condition number remains unknown. Specifically, it is unclear whether NC-SC bilevel problems are provably more difficult than NC-SC minimax problems (a special case where $f = -g$ ), which have a known lower bound of $\Omega(\sqrt{\kappa}_y \epsilon^{-2})$ .

Methodology
The authors establish new lower bounds by constructing hard instances based on "zero-chain" functions. They modify the standard zero-chain constructions used for minimax problems to exploit the asymmetry between the upper-level objective $f$ and the lower-level objective $g$ .

The core of their construction involves two distinct mechanisms to amplify the condition number dependency:

Coupling Variable ( $y$ ): A variable $y$ is used to couple sub-chains into the zero-chain in $x$ , reflecting the complexity of computing the lower-level solution $y^*(x)$ .
Rescaling Variable ( $z$ ): A variable $z$ is introduced to rescale $x$ by a factor related to the condition number $\kappa_y$ . This captures the dependency of the smoothness constant of the hyper-objective $F(x)$ on $\kappa_y$ .

By combining these, the authors create a longer effective chain in the upper-level variable $x$ . For deterministic problems, they construct quadratic lower-level functions, which allows the lower bounds to apply to both gradient-based and Hessian-vector product (HVP)-based methods. For stochastic problems, they utilize randomized stochastic NC zero-chains, focusing on variance amplification via the rescaling variable.

Key Contributions and Results
The paper provides the following lower bounds, which improve upon prior results for minimax and bilevel problems:

Deterministic NC-SC Problems:
- First-order smooth: $\Omega(\kappa_y^{5/2} \epsilon^{-2})$ . This improves the minimax lower bound of $\Omega(\sqrt{\kappa}_y \epsilon^{-2})$ .
- Second-order smooth: $\Omega(\kappa_y^{31/14} \epsilon^{-12/7})$ .
- Arbitrarily smooth ( $p \ge 3$ ): $\Omega(\kappa_y^{21/10} \epsilon^{-8/5})$ .
Stochastic NC-SC Problems:
- Smooth stochastic: $\Omega(\kappa_y^4 \epsilon^{-4})$ . This significantly improves the minimax lower bound of $\Omega(\kappa_y^{1/3} \epsilon^{-4})$ and concurrent work on bilevel problems. The authors argue that variance, rather than bias, is the fundamental bottleneck in the stochastic setting.
Convex-Strongly-Convex (C-SC) and Strongly-Convex-Strongly-Convex (SC-SC) Problems:
- C-SC: $\Omega(\kappa_y^{3/2} / \sqrt{\epsilon})$ , improving the previous best lower bound of $\Omega(\kappa_y / \sqrt{\epsilon})$ .
- SC-SC: $\tilde{\Omega}(\kappa_y^{3/2} \sqrt{\kappa_x})$ , improving the previous bound of $\tilde{\Omega}(\kappa_y \sqrt{\kappa_x})$ .

Refined Upper Bounds
The authors also refine existing upper bounds by applying Nesterov acceleration to the inner loop of fully first-order methods. For deterministic NC-SC problems with quadratic lower-level functions, they show that the upper bound can be reduced to $\tilde{O}(\kappa_y^{5/2} \epsilon^{-2})$ for first-order smoothness and $\tilde{O}(\bar{\kappa}_y^{9/4} \epsilon^{-7/4})$ for second-order smoothness. These refined upper bounds are nearly tight with respect to the new lower bounds, with only small gaps remaining (e.g., polylogarithmic factors or small polynomial powers).

Significance
The primary significance of this work is establishing the first provable gap in condition number dependency between NC-SC bilevel problems and NC-SC minimax problems. The results demonstrate that NC-SC bilevel optimization is fundamentally more challenging than NC-SC minimax optimization due to the bilevel structure. The lower bounds highlight two distinct sources of complexity: the computational cost of solving the lower-level problem (captured by the coupling variable) and the smoothness properties of the hyper-objective (captured by the rescaling variable). This provides a clearer understanding of the inherent difficulties in bilevel optimization and sets a new benchmark for algorithm design.