Descriptions may be stale. Consult the linked Lean sources.
Higher-Order Smooth
Bilevel Optimization
We consider minimizing over a
finite-dimensional real inner product space , where minimizes over another such space . The functions are
respectively twice and three times continuously differentiable, with
bounded first derivative of ,
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 , the goal is an output
where is differentiable and
almost surely under , the law of
the algorithm’s randomness.
Write The lower minimizer exists and is unique by the
assumptions below. The bilevel problem is On and , norms are induced by their inner
products. On , we use
the product norm For a
scalar function on , write for its first derivative and
, for its second and third
derivatives, viewed as bilinear and trilinear forms on . Their norms are the induced
operator norms for this product norm. Gradients on and use the respective inner products.
The algorithm receives , , initial points , , and all parameters , whose ranges
are
Our assumptions:
Assumption 1 (Higher-order regularity). The
functions satisfy and . For every ,
Assumption 2 (Lower-level strong convexity). For
every and ,
Assumption 3 (Initial bounds). The given initial
points satisfy
Queries may be made at any . A single oracle call returns the exact tuple
After the allotted oracle calls, the output must satisfy