← All setups

Coupled Minimax Capped Kkt — Coupled Strongly Concave Minimax

Descriptions may be stale. Consult the linked Lean sources.

Coupled Strongly Concave Minimax · Lean proof

Coupled Strongly Concave Minimax

We consider minimizing over x∈X⊂Rnx the maximum of f(x,y) over y∈Y⊂Rny subject to c(x,y)≤0, where c has m components and nx,ny,m are nonnegative integers. The sets are compact and convex; f is strongly concave in y, potentially nonconvex in x, and each constraint is convex in y. Gradients and constraint Jacobians satisfy Lipschitz and boundedness conditions, together with a uniform constraint qualification. On X×Y, the oracle returns f, ∇f, c, and its Jacobian. For ε>0, the goal is an output in X×Y with nonnegative multipliers whose Euclidean constraint violation, absolute complementarity sum, and two normal-cone stationarity residuals are each at most ε, almost surely.

The optimization problem is minx∈X maxy∈Yc(x,y)≤0f(x,y). Write E=Rnx×Rny, D=X×Y, and let f:E→R and c:E→Rm. All vector norms are Euclidean, with the product norm ∥(x,y)∥=(∥x∥2+∥y∥2)1/2. Operator norms ∥⋅∥op are induced by these norms. The parameters satisfy Lf,LJ,J,Gx,Gy,C,DX,DY≥0,μ,δ,Z,ε>0. The algorithm receives the dimensions, sets X,Y, given points x0,y0, and all the displayed scalar parameters.

Our assumptions:

Assumption 1 (Domain and starting points). The sets X and Y are compact and convex, with x0∈X and y0∈Y. Their diameters satisfy ∥x−x′∥≤DX(x,x′∈X),∥y−y′∥≤DY(y,y′∈Y).

Assumption 2 (Differentiability and uniform bounds). The functions f and c are Fréchet differentiable at every point of D. Write A(z):E→Rm for the Jacobian of c at z. For all z,w∈D, ∥∇f(z)−∇f(w)∥≤Lf∥z−w∥,∥A(z)−A(w)∥op≤LJ∥z−w∥. For every z∈D, ∥A(z)∥op≤J,∥c(z)∥≤C,∥∇xf(z)∥≤Gx,∥∇yf(z)∥≤Gy.

Assumption 3 (Strong concavity and constraint convexity). For every x∈X and i∈{1,…,m}, the function y↦ci(x,y) is convex on Y. For every x∈X and y,y′∈Y, f(x,y′)≤f(x,y)+⟨∇yf(x,y),y′−y⟩−μ2∥y′−y∥2.

For a convex set S and u∈S, define its normal cone by NS(u)={n:⟨n,v−u⟩≤0 for every v∈S}.

Assumption 4 (Uniform constraint qualification). For every (x,y)∈D, there exists d∈Rny such that ∥d∥≤Z,⟨n,d⟩≤0for every n∈NY(y),[A(x,y)(0,d)]i≤−δwhenever ci(x,y)>0.

At a query z∈D, the oracle returns the exact tuple (f(z),∇f(z),c(z),A(z)). Queries take values in E; replies outside D are unspecified.

The output is a triple (x¯,y¯,λ¯)∈Rnx×Rny×Rm. Set z¯=(x¯,y¯) and r=∇f(z¯)−A(z¯)∗λ¯=(rx,ry), where A(z¯)∗ denotes the Euclidean adjoint. Define [c(z¯)]+ componentwise by [c(z¯)]+,i=max{ci(z¯),0}. The required accuracy is x¯∈X,y¯∈Y,λ¯≥0,∥[c(z¯)]+∥≤ε,∑i=1m|λ¯ici(z¯)|≤ε,∃nx∈NX(x¯), ny∈NY(y¯):∥rx+nx∥≤ε,∥ry−ny∥≤ε,P-a.s. Here P is the law of the algorithm and oracle randomness, taken independently, and the almost-sure requirement applies to all the displayed output conditions jointly.

Proved result

(2+⌈4⋅1+μ+Lf+(1+2⋅Z⋅(Gy+1)δ)⋅LJ+2⋅Jμ⌉+⋅⌈log⁡(2+24⋅(1+μ+Lf+(1+2⋅Z⋅(Gy+1)δ)⋅LJ+2⋅J)⋅DY⋅(1+ε)⋅(2+constraints+2⋅Z⋅(Gy+1)δ)ε)log⁡(2)⌉+)⋅(1+⌈576⋅(1+μ+Lf+(1+2⋅Z⋅(Gy+1)δ)⋅LJ+2⋅J)2⋅(Gx⋅DX+Gy⋅DY+(1+2⋅Z⋅(Gy+1)δ)⋅C)⋅(1+ε)2⋅(2+constraints+2⋅Z⋅(Gy+1)δ)2μ⋅ε2⌉+)

OracleTemplate.Convergence LongTails.Setups.CoupledStronglyConcaveMinimax.spec
  OracleTemplate.CoupledMinimaxCappedKkt.budget

Relevant previous results

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