← All setups

Envelope Cubic Nonconvex PL — Second-Order Stationarity in PL Minimax Problems

Descriptions may be stale. Consult the linked Lean sources.

Second-Order Stationarity in PL Minimax Problems · Lean proof

Second-Order Stationarity in PL Minimax Problems

We consider minimizing Φ(x)=maxy∈Ff(x,y) for a possibly nonconvex function f:E×F→R on finite-dimensional real inner product spaces E,F. The gradient and Hessian of f are Lipschitz with constants L and ρ>0, respectively; every inner maximum is attained and satisfies a maximization Polyak–Łojasiewicz condition with 0<μ≤L. Initial value and maximization gaps are bounded. The oracle returns f(z), ∇f(z), and ∇2f(z) at z∈E×F. For ε>0, the goal is twice differentiable Φ and an output x¯∈E satisfying ∥∇Φ(x¯)∥≤ε and ∇2Φ(x¯)⪰−100ρL/μ(4+L/μ)εIE almost surely, where IE is the identity and the probability concerns algorithm randomness.

The optimization problem is infx∈EΦ(x),Φ(x)=maxy∈Ff(x,y). Equip E×F with the product inner product and norm ∥(x,y)∥=∥x∥2+∥y∥2. All operator norms below are the induced operator norms. The Hessian ∇2f(z) acts on E×F, and ∇yf(x,y) denotes the F component of ∇f(x,y). The algorithm receives E,F,L,μ,ρ,Δ,D,ε and the given points x0∈E, y0∈F, with parameter ranges 0<μ≤L,ρ>0,Δ≥0,D≥0,ε>0.

Our assumptions:

Assumption 1 (Smoothness). 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 (Attainment and maximization PL condition). For every x∈E, there exists yx∈F such that f(x,y)≤f(x,yx)for every y∈F. For all x∈E and y∈F, 2μ(Φ(x)−f(x,y))≤∥∇yf(x,y)∥2.

Assumption 3 (Initial gaps). The given points satisfy Φ(x0)−Φ(x)≤Δfor every x∈E,Φ(x0)−f(x0,y0)≤D.

Queries may be made at any point z∈E×F. Each oracle call returns the exact triple (f(z),∇f(z),∇2f(z)). The required success condition includes Fréchet differentiability of both Φ and ∇Φ everywhere on E. After the allotted oracle calls, the output x¯∈E must satisfy ∥∇Φ(x¯)∥≤ε,⟨v,∇2Φ(x¯)v⟩≥−100ρL/μ(4+L/μ)ε∥v∥2for every v∈E,P-a.s., where P is the law of the algorithm’s randomness.

Proved result

⌈10000000000⋅(1+Lμ+Δ⋅ρ⋅(Lμ)34ε32+Δ⋅ρ2μ3)⋅(log⁡(2+Lμ+ρ2⋅(Δ+D)μ3+ρ⋅εμ2+μ2ρ⋅ε))2⌉+

OracleTemplate.Convergence LongTails.Setups.NonconvexPLSecondOrder.spec
  OracleTemplate.PLMinimax.EnvelopeCubicNonconvexPL.budget

Relevant previous results

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