← All setups

Constrained Minimax Cubic — Constrained Second-Order Minimax Optimization

Descriptions may be stale. Consult the linked Lean sources.

Constrained Second-Order Minimax Optimization · Lean proof

Constrained Second-Order Minimax Optimization

We consider minimizing ϕ(x)=supy∈Yf(x,y), where f:E×F→R, E and F are finite-dimensional real inner product spaces, and Y⊆F is nonempty, closed, and convex. The function f has a globally Lipschitz gradient and Hessian and is strongly concave in its second variable. Given initial points have bounded value gap and gradient norm. The oracle returns the value, gradient, and Hessian of f at any queried point. For ε>0, the goal is differentiability of ϕ and an output x¯∈E satisfying ∥∇ϕ(x¯)∥≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is infx∈Esupy∈Yf(x,y). Equip E×F with the product inner product and norm ∥(x,y)∥=(∥x∥2+∥y∥2)1/2. Write ∇yf(x,y) for the F component of ∇f(x,y). The Hessian ∇2f(z) is the derivative of the gradient, viewed as a linear operator from E×F to itself; ∥⋅∥op denotes its induced operator norm.

The parameters satisfy 0<μ≤L,ρ>0,Δ≥0,B≥0,ε>0. The given initial points are x0∈E and y0∈Y. The algorithm receives E, F, Y, L, μ, ρ, Δ, B, ε, x0, and y0.

Our assumptions:

Assumption 1 (Second-order regularity). The function f is Fréchet differentiable everywhere, its gradient is Fréchet differentiable everywhere, and, for all z,w∈E×F, ∥∇f(z)−∇f(w)∥≤L∥z−w∥,∥∇2f(z)−∇2f(w)∥op≤ρ∥z−w∥.

Assumption 2 (Strong concavity). For every x∈E and y,y′∈F, f(x,y′)≤f(x,y)+⟨∇yf(x,y),y′−y⟩−μ2∥y′−y∥2.

Assumption 3 (Initial bounds). The initial value gap and full gradient satisfy ϕ(x0)−ϕ(x)≤Δfor every x∈E,∥∇f(x0,y0)∥≤B.

Queries may be made at any z∈E×F, including points whose second component lies outside Y. The exact second-order oracle returns (f(z),∇f(z),∇2f(z)). The output requirement is that ϕ be differentiable everywhere on E and that, after the allotted oracle calls, x¯∈E satisfy ∥∇ϕ(x¯)∥≤εP-a.s.

Proved result

4⋅(1+⌈16⋅Lμ⋅log⁡(1+32⋅ρ⋅Bμ2)⌉++(2+⌈384⋅Δ⋅ρ⋅(Lμ)34ε⋅ε⌉++⌈2048⋅ρ⋅Lμ⋅Δμ⋅ε+8⋅ρ⋅εμ⌉+)⋅(2+⌈2⋅log⁡(33+512⋅L⋅μρ⋅ε)⌉+))

OracleTemplate.Convergence LongTails.Setups.ConstrainedMinimaxSecondOrder.spec
  LongTails.Theorems.ConstrainedMinimaxCubic.budget

Relevant previous results

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