← All setups

Second-Order Stationarity in PL Minimax Problems

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

On finite-dimensional real inner-product spaces, f has an L-Lipschitz gradient and differentiable gradient with ρ-Lipschitz Hessian. Inner maxima are attained and 2μ(Φ(x)−f(x,y))≤∥∇yf(x,y)∥2 uniformly. Assume 0<μ≤L, ρ,ε>0, Φ(x0)−infΦ≤Δ and Φ(x0)−f(x0,y0)≤D, with Δ,D≥0. Exact queries return (f,∇f,∇2f). The target is ∥∇Φ(x)∥≤ε and ∇2Φ(x)⪰−100ρκ(4+κ)εI; the constructed output is deterministic.

Second-order nonconvex–PL minimax optimization: NonconvexPLSecondOrder.
Result Oracle complexity Novelty Limitations
(1) EnvelopeCubicNonconvexPL (Ours) (⋆⋆⋆) (review) O([1+κ+Δρκ3/4ε3/2+Δρ2μ3]ℓ2) joint calls.
(2) ECRN (Zhou et al. 2026), Thm. 11. Strongly concave inner subclass. O(κℓ+[1+Δρκ3/4ε3/2](1+log⁡ℓ)) gradient and Hessian calls; ε≤L2/[ρ(4+κ)3/2]. (1): Scope: PL permits nonconcave inner objectives and nonunique maximizers. Matches the leading polynomial rate on the strongly concave overlap. (1): κ initialization instead of κ; larger logarithmic overhead, function values required, curvature constant up to 10× looser. Retuning (2) removes its accuracy restriction.
(3) MCN (Luo et al. 2022), Cor. 1. Strongly concave inner subclass. O([κ+Δρκ2ε3/2]ℓ) total gradient/Hessian calls; Hessians: O(1+Δρκ3/2ε−3/2). (1): Scope: strong concavity to PL. On the overlap, for ε≤L2/(ρκ3/2), leading cost replaces κ2 by κ3/4, up to logarithms; curvature scaling improves by κ3/4. (1) requires values and has larger initialization/logarithmic overhead. Leading-term improvement need not dominate total cost.
(4) Smoothed-AGDA (Yang et al. 2022), Thm. 4.1, Cor. 4.1. Full inner-PL class. O(1+κL(Δ+b0)ε2+κ(1+log⁡κ)) gradient calls, including translation to ∥∇Φ∥≤ε. (1) adds second-order stationarity. Costs are not directly comparable: different oracle access and accuracy guarantees. (1) requires a Lipschitz Hessian and full-Hessian queries; (4) requires only gradient smoothness.

Abbr: Φ(x)=maxyf(x,y); κ=L/μ; ℓ=log⁡(2+κ+ρ2(Δ+D)/μ3+ρε/μ2+μ2/(ρε)). PL: Polyak–Łojasiewicz inequality. b0=2[maxyf^(x0,y)−minxf^(x,y0)], where f^(x,y)=f(x,y)+L∥x−x0∥2, is the initial auxiliary primal–dual gap. Curvature tolerances in (2) and (3) are respectively ρ(4+κ)3/2ε and κ3/2ρε.

Luo, Luo, Yujun Li, and Cheng Chen. 2022. Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization. https://doi.org/10.48550/arXiv.2110.04814.
Yang, Junchi, Antonio Orvieto, Aurelien Lucchi, and Niao He. 2022. “Faster Single-Loop Algorithms for Minimax Optimization Without Strong Concavity.” Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, Proceedings of machine learning research, vol. 151: 5485–517. https://proceedings.mlr.press/v151/yang22b.html.
Zhou, Qihao, Lesi Chen, Luo Luo, and Chengchang Liu. 2026. Envelope Cubic Regularized Newton Method for Nonconvex-Strongly-Concave Minimax Optimization. https://doi.org/10.48550/arXiv.2610.20345.

Lean setup