Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oracles

AI summary

Overview

Research area: Optimization theory and machine learning — specifically, the computational complexity of bilevel optimization under first-order oracle models.

Technical level: Advanced. The paper is a theoretical worst-case complexity analysis that relies on constructions from zero-chain lower-bound theory, and it assumes familiarity with smooth optimization, condition numbers, and oracle-based complexity.

Scope: This paper constructs new hard instances that establish lower bounds on the number of first-order oracle calls needed to solve smooth nonconvex-strongly-convex bilevel optimization problems in both deterministic and stochastic settings.

What This Paper Is About

Bilevel optimization solves a problem of the form min over x of H(x) = f(x, y*(x)), where y*(x) = argmin over y of g(x, y). In the setting studied here, the lower-level function g is smooth and strongly convex in y, while the upper-level function f is smooth but potentially nonconvex, and κ = L_g/μ denotes the condition number of the lower-level function. While upper-bound convergence guarantees for such problems are widely studied, lower bounds have lagged behind because the bilevel structure makes it hard to construct meaningful hard instances. The goal of this paper is to produce nontrivial lower bounds under standard deterministic and stochastic first-order oracles.

Key Contributions

1. Deterministic lower bound. The paper constructs a hard instance on which no first-order zero-respecting algorithm can find an ε-stationary solution using fewer than Ω(κ^{3/2} ε^{-2}) first-order oracle calls for smooth nonconvex-strongly-convex bilevel problems. This improves on the optimal lower bounds for general smooth nonconvex single-level optimization, Ω(ε^{-2}) (Carmon et al., 2020), and for smooth nonconvex-strongly-convex min-max optimization, Ω(√κ ε^{-2}) (Li et al., 2021), by factors of κ^{3/2} and κ, respectively.

2. Stochastic lower bound. The paper constructs an instance showing that no first-order zero-respecting algorithm can achieve an ε-stationary solution with fewer than Ω(κ^{5/2} ε^{-4}) stochastic oracle calls under bounded variance assumptions. This compares to Ω(ε^{-4}) for standard smooth nonconvex single-level stochastic optimization (Arjevani et al., 2023) and Ω(κ^{1/3} ε^{-2}) for smooth nonconvex-strongly-convex min-max optimization (Li et al., 2021), improving on these by factors of κ^{5/2} and κ^{13/6}, respectively.

3. An explicit, verifiable hard instance. The paper gives a concrete construction in which the upper-level function f depends only on the lower-level block variable, and it works through the validation that the pair {f, g} belongs to the assumed function class F(L_f, L_g, μ, Δ), including strong convexity, L_f/L_g smoothness, and bounded y-gradient.

4. Exposure of remaining gaps and a suggested direction. The paper documents that substantial gaps persist between current upper and lower bounds, and suggests that closing them may require first understanding the simpler case in which the lower-level function is quadratic.

Main Findings

• Deterministic result: Any first-order zero-respecting bilevel algorithm requires at least C_0 Δ L_f κ^{3/2} / ε^2 oracle calls to find x with ‖∇H(x)‖_2 < ε, where H(x) = f(x, y*(x)), y*(x) = argmin_y g(x, y), κ = L_g/μ ≥ 1, Δ/L_f = O(1), and C_0 is a numerical constant.

• Stochastic result: At least Ω(κ^{5/2} ε^{-4}) stochastic first-order oracle calls are necessary under bounded variance assumptions, where the paper assumes for simplicity that the variances of the stochastic first-order oracles are identical, i.e., σ_f = σ_g = σ.

• Bilevel is provably harder than min-max: The deterministic Ω(κ^{3/2} ε^{-2}) bound is larger than the Ω(√κ ε^{-2}) min-max bound by a factor of κ. The paper states this is consistent with the fundamental hardness comparison for smooth strongly-convex–strongly-convex bilevel problems established in Ji and Liang (2023).

• Upper-bound side (deterministic): Chen et al. (2025) propose a first-order penalty method achieving a convergence rate of order κ^4 ε^{-2}, which can be reduced to κ^{3.5} ε^{-2} through a naive application of Nesterov acceleration. Even compared to the new lower bound, a gap of order κ^2 remains.

• Upper-bound side (stochastic): Compared with the Ω(ε^{-6}) upper bound established by Kwon et al. (2024), a gap still remains.

• Quadratic lower level: The paper's lower bounds continue to apply in the regime where the lower-level function is quadratic, but obtaining tighter upper bounds there remains largely unexplored and not yet well understood.

• Comparison with prior bilevel lower bounds: Ji and Liang (2023) gave bounds for strongly-convex–strongly-convex and convex–strongly-convex bilevel problems under second-order oracles, assuming the hyper-objective H(x) is convex or strongly convex, and revealed a gap of a factor √κ compared to min-max lower bounds; that analysis is limited to the deterministic setting and to convexity assumptions on the hyper-objective. Dagréou et al. (2024) derived a lower bound of Ω(n + √n ε^{-2}) for finite-sum nonconvex-strongly-convex bilevel problems that does not reflect condition-number dependence. Kwon et al. (2024) established lower bounds under a y*-aware stochastic first-order oracle returning an estimate ŷ that is ε-close to the exact lower-level solution, effectively reducing the problem to one resembling single-level optimization.

• Concurrent work noted: While preparing the final draft, the author became aware of concurrent work by Chen and Zhang (2025), which also establishes lower bounds for nonconvex-strongly-convex bilevel optimization under (stochastic) first-order oracle access, showing a larger dependence on the condition number than min-max and single-level minimization of the same type. The constructions differ: Chen and Zhang (2025) introduce an additional auxiliary variable z, whereas this paper's construction is simpler without such a variable; in the stochastic setting, Chen and Zhang (2025) eliminate the coupling variable y to reduce dimensionality, while this paper instead uses two bounded hypercubes to control noise variances.

Methodology in Plain English

The paper uses the standard "hard instance" or worst-case construction approach to lower bounds: rather than analyzing a specific algorithm, it builds a specific, legitimate problem instance that is provably difficult for any algorithm in a broad class.

The key tool is the idea of a zero-chain. A function is a zero-chain if, whenever a vector has nonzero entries only in coordinates 1 through i−1, its gradient is nonzero only in coordinates 1 through i. Starting from an initialization at zero, this means each iteration of a first-order algorithm can "activate" at most one new coordinate. If a good solution requires discovering at least T coordinates, then any deterministic first-order method must take at least T iterations.

The construction builds three ingredients:

1. A tri-diagonal 1-D discrete Laplacian matrix A (of size n×n), which is positive semidefinite with spectral norm at most 4. Because it is tri-diagonal, multiplying a vector supported on coordinates 1 through i−1 produces a vector supported on at most coordinates 1 through i — preserving the one-coordinate-per-step property. This matrix is used to build the strongly-convex lower-level instance.

2. Two "hardness" scalar functions Ψ(·) and Φ(·) borrowed from Carmon et al. (2020). Ψ is identically zero (with all derivatives zero) for x ≤ 1/2, and both Ψ and Φ are infinitely differentiable and bounded, with bounded derivatives. These boundedness properties are what make it possible to fit the constructed instance inside the bilevel function class and keep the y-gradient of the upper-level function bounded by a numerical constant.

3. A coupled construction linking the upper variable to lower-level blocks. The upper-level variable is x = [x_1, …, x_T], and the lower-level variable is a collection of blocks ỹ = [y^(0), y^(1), …, y^(T)], each y^(i) in R^n. The dimension of each lower block is set as n = ⌊√((L_g − μ)/(4μ))⌋. The coupling vector b_x^(i) = x_i e_n is described by the author as the most critical design element.

The proof approach then:

• Validates the instance by showing g(x,·) is μ-strongly convex, that f and g are L_f- and L_g-smooth, and that the y-gradient of f has norm bounded by a numerical constant independent of T and n. This last step is singled out as particularly challenging; the paper notes that prior work (Ji and Liang, 2023) sidestepped it using strong convexity of the hyper-objective, and Kwon et al. (2024) sidestepped it by making the upper-level function a scalar y.

• Analyzes activation order to show that the iterates obey a specific support structure at iteration Kn + k (for K = 0, …, T−1 and k = 1, …, n), so that activating all coordinates of x requires at least T·n iterations in total.

• Translates iteration count into an oracle-call lower bound by specifying the constants and parameters so the resulting bound takes the form Ω(κ^{3/2} ε^{-2}) in the deterministic case and Ω(κ^{5/2} ε^{-4}) in the stochastic case.

Notably, the paper reports no experimental or numerical results; the contribution is entirely theoretical.

Why This Matters

Impact on research. The paper shows that nontrivial lower bounds for nonconvex-strongly-convex bilevel optimization are indeed possible, and that they are significantly stronger than known lower bounds for single-level and min-max problems. It establishes that bilevel optimization is provably more difficult than min-max optimization under comparable conditions, and it sharply quantifies how much room remains between the current upper bounds (κ^{3.5} ε^{-2} deterministic and Ω(ε^{-6}) stochastic, as cited from prior work) and the new lower bounds (κ^{3/2} ε^{-2} deterministic and κ^{5/2} ε^{-4} stochastic). It also addresses an open problem the paper identifies: lower bounds for standard (stochastic) first-order oracles that directly access f and g, as opposed to the y*-aware oracle assumed by Kwon et al. (2024).

Real-world applications. The paper frames the smooth nonconvex-strongly-convex bilevel formulation as capturing a variety of modern applications, specifically:

• Meta-learning (Rajeswaran et al., 2019)
• Reinforcement learning (Konda and Tsitsiklis, 2000; Hong et al., 2023)
• Robotics (Wang et al., 2024)
• Communication networks and federated learning (Ji and Ying, 2023; Tarzanagh et al., 2022; Huang et al., 2023)

Industry relevance. The algorithm class studied is deliberately broad: the definition of the update subspaces permits both simultaneous and alternating updates of x and y, thereby covering single-loop and double-loop bilevel optimization algorithms. The paper states that this class covers all existing first-order bilevel optimization methods, including penalty-based approaches (Shen and Chen, 2023; Lu and Mei, 2024), primal–dual methods (Sow et al., 2022), finite-difference Hessian–vector-approximation methods (Yang et al., 2023), value-function-based approaches (Liu et al., 2020; Liu et al., 2021c; Liu et al., 2021b), and barrier-based methods (Liu et al., 2022). The lower bounds therefore apply across the full spectrum of first-order bilevel methods that practitioners use when avoiding second-order Hessian-vector or Jacobian-vector products.

Future Directions

1. Close the deterministic gap. A gap of order κ^2 persists between the lower bound κ^{3/2} ε^{-2} and the best upper bound κ^{3.5} ε^{-2} (from Chen et al. (2025) with naive Nesterov acceleration). The paper explicitly calls this "substantial room for future improvements."

2. Close the stochastic gap. A gap remains between the Ω(κ^{5/2} ε^{-4}) lower bound and the Ω(ε^{-6}) upper bound established by Kwon et al. (2024).

3. Study the quadratic lower-level case. The paper suggests that closing these gaps may require first studying the simpler yet meaningful case in which the lower-level function is quadratic. The paper's lower bounds continue to apply in that regime, but tighter upper bounds there remain largely unexplored and not yet well understood.

4. Extend lower-bound constructions beyond the current assumptions. The paper notes that the lower-bound literature has largely been limited to deterministic settings, convexity assumptions on the hyper-objective (Ji and Liang, 2023), or y*-aware oracles (Kwon et al., 2024). Its own contribution is restricted to the smooth nonconvex-strongly-convex regime with standard first-order oracles, so the boundaries of what is provable in other bilevel regimes remain to be mapped.

Target Audience

This paper is intended for optimization theorists and machine learning researchers working on complexity theory, particularly those studying lower bounds, oracle complexity, and the foundations of bilevel and min-max optimization. It is also relevant to researchers developing first-order bilevel algorithms who want to know how far current methods are from optimal in terms of condition-number and accuracy dependence. Readers without a background in zero-chain lower-bound techniques and smooth nonconvex optimization will find the constructions difficult; the paper is advanced and theoretical, and it reports no experiments.

Authors’ abstract

Although upper bound guarantees for bilevel optimization have been widely studied, progress on lower bounds has been limited due to the complexity of the bilevel structure. In this work, we focus on the smooth nonconvex-strongly-convex setting and develop new hard instances that yield nontrivial lower bounds under deterministic and stochastic first-order oracle models. In the deterministic case, we prove that any first-order zero-respecting algorithm requires at least $Ω(κ^{3/2}ε^{-2})$ oracle calls to find an $ε$-accurate stationary point, improving the optimal lower bounds known for single-level nonconvex optimization and for nonconvex-strongly-convex min-max problems. In the stochastic case, we show that at least $Ω(κ^{5/2}ε^{-4})$ stochastic oracle calls are necessary, again strengthening the best known bounds in related settings. Our results expose substantial gaps between current upper and lower bounds for bilevel optimization and suggest that even simplified regimes, such as those with quadratic lower-level objectives, warrant further investigation toward understanding the optimal complexity of bilevel optimization under standard first-order oracles.