← All setups

Bilevel First Order Curvature — Higher-Order Smooth Bilevel Optimization

Descriptions may be stale. Consult the linked Lean sources.

Higher-Order Smooth Bilevel Optimization · Lean proof

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.

Proved result

⌈240⋅(L⋅(Lμ)3ε)14⋅(1+Δ⋅L⋅(Lμ)4ε3)⋅log⁡(2⋅Lμ⋅(1+Lε)⋅(1+Δε)⋅(1+Gε))⌉+

OracleTemplate.Convergence LongTails.Setups.HigherSmoothBilevel.spec OracleTemplate.BilevelFirstOrderCurvature.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.