← All setups

Higher-Order Smooth Bilevel Optimization

Descriptions may be stale. Consult the linked Lean sources.

Higher-Order Smooth Bilevel Optimization

We consider minimizing F(x)=f(x,y⋆(x)) over a finite-dimensional real inner product space X, where y⋆(x) minimizes g(x,⋅) over another such space Y. The functions f,g:X×Y→R are respectively twice and three times continuously differentiable, with bounded first derivative of f, Lipschitz derivatives through these orders, and uniform strong convexity of the lower problem. Given initial points have bounded outer objective gap and lower gradient residual. The oracle returns both function values and first derivatives. For ε>0, the goal is an output x¯ where F is differentiable and ∥∇F(x¯)∥≤ε almost surely under P, the law of the algorithm’s randomness.

Write y⋆(x)=argminy∈Yg(x,y),F(x)=f(x,y⋆(x)). The lower minimizer exists and is unique by the assumptions below. The bilevel problem is minx∈XF(x). On X and Y, norms are induced by their inner products. On Z=X×Y, we use the product norm ∥(x,y)∥Z=max{∥x∥,∥y∥}. For a scalar function h on Z, write dh for its first derivative and ∇2h, ∇3h for its second and third derivatives, viewed as bilinear and trilinear forms on Z. Their norms ∥⋅∥op are the induced operator norms for this product norm. Gradients on X and Y use the respective inner products.

The algorithm receives X, Y, initial points x0∈X, y0∈Y, and all parameters L,μ,Δ,G,ε, whose ranges are 0<μ≤L,Δ>0,G≥0,ε>0.

Our assumptions:

Assumption 1 (Higher-order regularity). The functions satisfy f∈C2(Z;R) and g∈C3(Z;R). For every z,w∈Z, ∥df(z)∥op≤L,∥df(z)−df(w)∥op≤L∥z−w∥Z,∥∇2f(z)−∇2f(w)∥op≤L∥z−w∥Z,∥dg(z)−dg(w)∥op≤L∥z−w∥Z,∥∇2g(z)−∇2g(w)∥op≤L∥z−w∥Z,∥∇3g(z)−∇3g(w)∥op≤L∥z−w∥Z.

Assumption 2 (Lower-level strong convexity). For every x∈X and y,v∈Y, g(x,v)≥g(x,y)+⟨∇yg(x,y),v−y⟩+μ2∥v−y∥2.

Assumption 3 (Initial bounds). The given initial points satisfy F(x0)−F(x)≤Δfor every x∈X,∥∇yg(x0,y0)∥≤G.

Queries may be made at any z∈Z. A single oracle call returns the exact tuple (f(z),g(z),df(z),dg(z)). After the allotted oracle calls, the output x¯∈X must satisfy F is differentiable at x¯,∥∇F(x¯)∥≤εP-a.s.

Results

Finite-dimensional real inner-product spaces X,Y; f∈C2, g∈C3, ∥Df∥≤L, and Df,D2f,Dg,D2g,D3g are L-Lipschitz (max product norm). Each g(x,⋅) is μ-strongly convex, 0<μ≤L, F(x0)−infF≤Δ>0, and ∥∇yg(x0,y0)∥≤G. Exact joint (f,g,Df,Dg) queries are available. Target: ∥∇F(x^)∥≤ε, ε>0; (1) succeeds for every seed.

Comparison for HigherSmoothBilevel.
Result Oracle complexity Novelty Limitations
(1) BilevelFirstOrderCurvature (Ours) (⋆⋆⋆) (review) O(1+[(Lκ3/ε)1/4+ΔL3/4κ11/4ε−7/4]ℓ) joint calls, including inner solves.
(2) AccF2BA+ (Chen, Ji, et al. 2026), Thm. F.2 O(ΔL3/4κ13/4ε−7/4χ6P) first-order calls; ερF≤LF. (1): κ smaller leading cost when ΔLκ4/ε3≥1, up to logs; deterministic, dimension-free FOSP instead of probability 1−δ. (1) loses SOSP. With heterogeneous constants, gain requires L¯1/4μ1/2<L11/2L21/4.
(3) AccF2BA (Chen, Ma, et al. 2026), Thm. 5.2 O(ΔL3/4κ15/4ε−7/4χ6P) first-order calls; additionally f∈C3. (1): κ smaller leading cost when ΔLκ4/ε3≥1, up to logs; every-seed FOSP without dimension/confidence logs. (1) loses the probability-1−δ SOSP guarantee.
(4) RAHGD (Yang et al. 2023), Cor. 3.6 O(ΔL3/4κ13/4ε−7/4P) total gradient, Jacobian-vector and Hessian-vector calls. (1): κ smaller leading total cost when ΔLκ4/ε3≥1, up to logs; only first-order queries.
(5) Derived bound: FSBA/LFSBA (Yang et al. 2026), Thms. 3.4, 4.3; finite-difference Hessians O([κ+D+ΔL(κ3+Dκ11/4)ε−3/2]P) first-order calls. (1) is dimension-free; leading cost improves up to logs when ε≳L/(κ1/4+D)4 and startup is dominated. (1) loses SOSP; worse accuracy exponent (7/4 versus 3/2), losing at fixed dimension for sufficiently small ε.

Abbr: F(x)=f(x,arg⁡minyg(x,y)); κ=L/μ; D=dim⁡X+dim⁡Y; dx=dim⁡X; ℓ=1+log⁡[κ(1+L/ε)(1+Δ/ε)(1+G/ε)]; χ=1+log+⁡(dx/(δε)), log+⁡t=max{0,log⁡t}, 0<δ<1. P denotes the cited bounds’ additional polylogarithmic factors in smoothness, conditioning, accuracy and initialization (and confidence for (2), (3)). FOSP: first-order stationarity; SOSP additionally bounds λmin(∇2F). LF,ρF are the gradient and Hessian Lipschitz bounds for F. L1,L2 are separate derivative Lipschitz bounds, L¯=maxqLq.

Chen, Lesi, Kaiyi Ji, and Jingzhao Zhang. 2026. On the Condition Number Dependency in Bilevel Optimization. https://doi.org/10.48550/arXiv.2511.22331.
Chen, Lesi, Yaohua Ma, and Jingzhao Zhang. 2026. Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles. https://doi.org/10.48550/arXiv.2306.14853.
Yang, Haikuo, Luo Luo, Chris Junchi Li, and Michael I. Jordan. 2023. Accelerating Inexact HyperGradient Descent for Bilevel Optimization. https://doi.org/10.48550/arXiv.2307.00126.
Yang, Sheng, Chengchang Liu, Lesi Chen, and John C. S. Lui. 2026. Second-Order Bilevel Optimization with Accelerated Convergence Rates. https://doi.org/10.48550/arXiv.2605.06431.

Lean setup