← All setups

Stochastic Nonconvex Strongly Concave Minimax

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Nonconvex Strongly Concave Minimax

We consider a possibly nonconvex minimax objective f:E×F→R on finite-dimensional real inner product spaces E and F. The function is strongly concave in its second argument, with a Lipschitz gradient and Lipschitz Hessian. Given points x0∈E and y0∈F satisfy bounds on the initial value gap and dual gradient. Each oracle call returns unbiased estimates of both partial gradients using one shared sample, independently across calls, with bounded joint variance. For ε>0, the goal is a measurable output x¯∈E satisfying E[∥∇Φ(x¯)∥]≤ε, where Φ(x)=maxy∈Ff(x,y) and expectation includes sampling and independent algorithm randomness.

The optimization problem is minx∈Emaxy∈Ff(x,y). We equip E×F with the product inner product and norm ∥(u,v)∥2=∥u∥2+∥v∥2. All operator norms below are induced by these norms. The parameters satisfy 0<μ≤L,ρ>0,σ>0,Δ≥0,G≥0,ε>0. The algorithm receives E, F, the measurable sample space Ω, all seven scalar parameters, and the given points x0,y0.

Our assumptions:

Assumption 1 (Gradient and Hessian regularity). Both partial gradients of f exist everywhere and are Fréchet differentiable as functions on E×F. Writing z=(x,y) and ∇f(z)=(∇xf(x,y),∇yf(x,y)), we require, for every z,z′∈E×F, ∥∇f(z)−∇f(z′)∥≤L∥z−z′∥,∥∇2f(z)−∇2f(z′)∥op≤ρ∥z−z′∥. Here ∇2f(z) is the linear operator from E×F to E×F obtained by differentiating the two partial gradients.

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 given points satisfy ∀x∈E ∀y∈F ∃y′∈F:f(x0,y)−f(x,y′)≤Δ,∥∇yf(x0,y0)∥≤G.

Assumption 4 (Stochastic partial gradients). There is a probability measure ν on Ω and jointly measurable maps ox:(E×F)×Ω→E,oy:(E×F)×Ω→F. For each fixed z=(x,y), both replies are Bochner integrable under ν, and Eξ∼ν[ox(z,ξ)]=∇xf(x,y),Eξ∼ν[oy(z,ξ)]=∇yf(x,y). The sum of squared errors is integrable and satisfies Eξ∼ν[∥ox(z,ξ)−∇xf(x,y)∥2+∥oy(z,ξ)−∇yf(x,y)∥2]≤σ2. The samples (ξk)k≥0 are measurable, independent, and identically distributed with law ν, and are independent of algorithm randomness. At query zk∈E×F, call k returns the pair (ox(zk,ξk),oy(zk,ξk)) using the same sample for both components.

Queries may be made anywhere in E×F. The output requirement includes the existence of a maximizing selection y⋆:E→F satisfying f(x,y)≤f(x,y⋆(x))for every x∈E, y∈F. For every such selection, the value function is Φ(x)=f(x,y⋆(x)). The output x¯ must be measurable, its gradient norm ∥∇Φ(x¯)∥ must be integrable, and it must satisfy EP[∥∇Φ(x¯)∥]≤ε, where P is the joint law of the oracle samples and the independent algorithm randomness.

Results

On finite-dimensional real inner-product spaces, f(x,y) is jointly L-smooth, μ-strongly concave in y, and has ρ-Lipschitz Hessian ∇2f. Let Φ(x)=maxyf(x,y), Φ(x0)−infxΦ(x)≤Δ, and ∥∇yf(x0,y0)∥≤G. Here 0<μ≤L, ρ,σ,ε>0, and Δ,G≥0. Each call returns a jointly measurable, unbiased joint stochastic gradient with total variance at most σ2, using a fresh IID sample. The target is ∫∥∇Φ(x^(ω))∥dP(ω)≤ε, where P includes the sampling and algorithm randomness.

Stochastic minimax optimization with Lipschitz Hessians: StochasticHessianNcsc.
Result Oracle complexity Novelty Limitations
(1) HessianNcscImplicitTransport (Ours) (⋆⋆⋆) (review) O(K2(1+σ2/ε2)⋅(1+ρεK/L2)⋅[KΔQ/ε+1+σ/ε+log⁡(1+G2Q/μ2)]) joint-gradient calls, including initialization.
(2) (Wu et al. 2026, Thm. 3.4, v1) O(Λ10[κLΔ/ε2+κLΔσ2/ε4+κ2σ2/ε2+κ(1+log⁡(1+κ2(G2+LΔ)/ε2))]) joint-gradient calls; success probability 2/3. Applies for κ≥κ0, LΔ≥C0ε2 (universal thresholds). (1): ε−7/2 instead of ε−4 for fixed positive parameters as ε→0. More generally, gain up to logarithms when σ≥ε and ε≪min{L2/(ρκ5),σ/κ2,LΔ/(κσ)}. Expected stationarity implies the shared probability target by tuning to ε/3. (1) needs a known Hessian-Lipschitz bound; leading noise dependence κ7/2 instead of κ. Low-noise gap term worse by κ5/2 when ρεK≤L2; larger proved constants.
(3) HCMM-1 (Cai et al. 2026, Thm. 1, v3) O(ε−3) stochastic-gradient and stochastic Hessian–vector-product calls in total, for fixed remaining parameters and initialization; their dependence is unspecified. Requires bounded gradients and unbiased, bounded-variance stochastic Hessians. (1): no stochastic Hessian oracle or bounded-gradient assumption. Rates are not comparable under the supplied gradient-only oracle. (1) has exponent 7/2 instead of 3 with other parameters fixed, under the respective oracle models.
(4) NIGT (Cutkosky and Mehta 2020, Thm. 3) Derived bound: O(1+LΔ/ε2+Δσ2ρ/ε7/2+σ13/3Δ4/3ρ2/3ε7/3) gradient calls, Δ>0. Special case f(x,y)=F(x)−μ2∥y∥2; shift infF to zero. (1) extends single-level optimization to coupled minimax problems. Matches the leading ε−7/2 rate on the overlap (μ=L, fixed positive parameters). (1) retains extra LΔσ/ε3-type terms even at μ=L.

Abbr: κ=L/μ, K=1+κ, Q=ρK/ε+L2/(ε2+σ2); Λ=1+log⁡(1+κ)+log⁡(1+LΔ/ε2)+log⁡(1+κ2σ2/ε2). IID: independent, identically distributed. One joint-gradient call returns the x and y components together.

Cai, Haoyuan, Sulaiman A. Alghunaim, and Ali H. Sayed. 2026. Accelerated Stochastic Min-Max Optimization Based on Bias-Corrected Momentum. https://doi.org/10.48550/arXiv.2406.13041.
Cutkosky, Ashok, and Harsh Mehta. 2020. “Momentum Improves Normalized SGD.” Proceedings of the 37th International Conference on Machine Learning, Proceedings of machine learning research, vol. 119: 2260–68. https://proceedings.mlr.press/v119/cutkosky20b.html.
Wu, Wendao, Haihan Zhang, Chenheng Zhang, et al. 2026. Sharp Fresh-Gradient Complexity of Nonconvex-Strongly-Concave Minimax Optimization. https://doi.org/10.48550/arXiv.2610.00229.

Lean setup