← All setups

Hessian Ncsc Implicit Transport — Stochastic Nonconvex Strongly Concave Minimax

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Nonconvex Strongly Concave Minimax · Lean proof

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.

Proved result

⌈106⋅(1+Lμ)2⋅(1+σ2ε2)⋅(1+ρ⋅ε⋅(1+Lμ)L2)⋅((1+Lμ)⋅Δε⋅40⋅ρ⋅(1+Lμ)ε+L2ε2+20⋅σ2+1+σε+log⁡(1+G2μ2⋅(40⋅ρ⋅(1+Lμ)ε+L2ε2+20⋅σ2)))⌉+

OracleTemplate.Convergence LongTails.Setups.StochasticHessianNcsc.spec OracleTemplate.HessianNcsc.budget

Relevant previous results

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