← All setups

Constrained Second-Order Minimax Optimization

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Finite-dimensional real inner-product spaces E,F; nonempty closed convex Y⊆F, possibly unbounded. On all of E×F, ∇f is differentiable and L-Lipschitz, ∇2f is ρ-Lipschitz, and f(x,⋅) is μ-strongly concave. Assume 0<μ≤L, ρ,ε>0, Δ,B≥0, y0∈Y, Φ(x0)−infxΦ(x)≤Δ, and ∥∇f(x0,y0)∥≤B, where Φ(x)=maxy∈Yf(x,y). Exact queries return (f,∇f,∇2f). Target: Φ differentiable and ∥∇Φ(x^)∥≤ε for every seed.

Comparison for ConstrainedMinimaxSecondOrder.
Result Oracle complexity Novelty Limitations
(1) ConstrainedMinimaxCubic (Ours) (⋆⋆⋆) (review) O(κlog⁡(1+ρB/μ2)+[1+A(1+r)+ρε/μ]ℓ) bundled calls.
(2) Minimax-PPA (Lin et al. 2020, Theorem 20) O((1+κLΔ/ε2)ℓD2) gradient calls; bounded Y, diameter Dy; success probability 2/3. (1): Scope: unbounded closed convex Y. On bounded Y, leading accuracy exponent ε−3/2 instead of ε−2 when r<1; deterministic accuracy. (1) needs full Hessians, ambient Hessian Lipschitzness and B; pays κlog⁡(1+ρB/μ2) startup.
(3) (Zhang et al. 2026, Theorem 4.1, v2) O~(1+min{κ,(ρD0/μ)2/7}+min{A(1+r1/7),LΔε−2(1+r2/7),κLΔε−2}) bundled calls; Y=F. (1): Scope: closed convex dual constraints, including changing active constraints. Matches leading A for Y=F, r≤1, up to logarithms. (1) has κ rather than at most κ startup dependence; for r>1, tracking Ar versus regime-adaptive branches.
(4) ECRN (Zhou et al. 2026, Theorem 11, v1) O~(1+A) gradient/Hessian evaluations; Y=F, ε≤L2/[ρ(4+κ)3/2]; (ε,ρ(4+κ)3/2ε)-SOSP. (1): Scope: closed convex dual constraints. Matches leading A on the unconstrained overlap in the stated accuracy range, up to logarithms. (1) guarantees only first-order stationarity; retains explicit initialization and tracking costs.

Abbr: κ=L/μ, r=ρε/(Lμ3/2), A=Δρκ3/4ε−3/2, ℓ=1+log⁡(1+Lμ/(ρε)), ℓD=1+log+⁡(κL(D~x2+Dy2)/ε); log+⁡t=max{0,log⁡t}. D~x is the distance from x0 to the minimizer of f(x,y0)+L∥x−x0∥2. D0=Ry+κΔ/L, with Ry=B/μ a valid bound on ∥y0−y∗(x0)∥ when Y=F. O~ suppresses the cited results’ logarithmic factors; SOSP additionally requires ∇2Φ(x^)⪰−ηI for the displayed second tolerance η.

Lin, Tianyi, Chi Jin, and Michael I. Jordan. 2020. “Near-Optimal Algorithms for Minimax Optimization.” In Proceedings of Thirty Third Conference on Learning Theory, edited by Jacob Abernethy and Shivani Agarwal, vol. 125. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v125/lin20a.html.
Zhang, Fangqing, Haihan Zhang, Wendao Wu, et al. 2026. Matching Full-Hessian Oracle Complexity for Nonconvex–Strongly-Concave Minimax Optimization. https://doi.org/10.48550/arXiv.2610.16771.
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