← All setups

Coupled Strongly Concave Minimax

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Consider minx∈Xmaxy∈Y,c(x,y)≤0f(x,y) on nonempty compact convex Euclidean sets, with supplied starts in X×Y. The gradient of f is Lf-Lipschitz, f(x,⋅) is μ-strongly concave, and each ci(x,⋅) is convex. The constraint Jacobian is LJ-Lipschitz; ∥Jc∥≤J, ∥∇xf∥≤Gx, ∥∇yf∥≤Gy, ∥c∥≤C; diameters are bounded by DX,DY. At every (x,y), some d∈NY(y)∘ satisfies ∥d∥≤Z and ⟨∇yci,d⟩≤−δ for every violated constraint. Here μ,δ,Z,ε>0. Target: deterministic ε-KKT, with λ≥0, ∥[c]+∥≤ε, ∑i|λici|≤ε, and normal-cone stationarity residuals at most ε for x and y. One complete oracle call returns (f,∇f,c,Jc).

Sufficient oracle budgets for CoupledStronglyConcaveMinimax.
Result Oracle complexity Novelty Limitations
(1) CoupledMinimaxCappedKkt (Ours) (⋆⋆⋆) (review) O([1+B/μlog(2+BDYS(1+ε)ε)]×[1+B2ΔS2(1+ε)2με2])
(2) ALDER (Zhang et al. 2026, Theorem 16) O(1+ℓε3/2Hμε2) complete calls; 0<ε≤1, given a feasible start. Its construction cost is excluded. (1): ε−2log⁡(1/ε) instead of ε−7/2 for fixed remaining data and small ε; roughly ε≪μ2/3, up to logarithms. Fixed-cap stationarity transfers to KKT. (1): leading μ−3/2 instead of μ−1/2; can lose at moderate accuracy with small μ. Nested inner solves replace a single loop.
(3) FAL (Lu and Mei 2026, Theorem 2, Remark 6(ii)); specialization: no outer constraints, indicator composite terms, uniform inner Slater O(ε−7/2[1+log⁡(1/ε)]) gradient/Jacobian and projection operations, with remaining problem data fixed and sufficiently small ε; aggregate complementarity |λ⊤c|≤ε after rescaling the tolerance. (1): Scope: violated-only qualification replaces uniform inner Slater; permits paired equality constraints. The aggregate complementarity target in (3) prevents an identical-criterion rate comparison. (1) does not cover the outer nonlinear constraints or general proximal composite terms handled by (3).

Abbr: m is the number of coupled constraints; [c]+ is the componentwise positive part; NX,NY are outward normal cones and ∘ denotes the polar cone. Stationarity uses L=f−λ⊤c: ∥∇xL+nx∥,∥∇yL−ny∥≤ε for nx∈NX(x),ny∈NY(y). M=1+Z(Gy+1)/δ, B=1+μ+Lf+MLJ+J, Δ=GxDX+GyDY+MC, S=1+m+M. In (2), Ma=mC+Z(1+Gy+DY+JC)/δ, A=max{1,Ma,Ma(Ma+C)}, ℓε=1+μ+Lf+LJC+(LJC+J2)A/ε, and H=1+GxDX+GyDY+Gx2+Gy2+(1+μ)DY2+C2. Bounds suppress universal factors; the fixed-data order in (3) suppresses dependence on its other parameters. Uniform inner Slater means ci(x,y^x)≤−δd<0 uniformly in x,i.

Lu, Zhaosong, and Sanyou Mei. 2026. A First-Order Method for Nonconvex-Strongly-Concave Constrained Minimax Optimization. https://doi.org/10.48550/arXiv.2512.22909.
Zhang, Huiling, Minhao Zhang, Zi Xu, and Yu-Hong Dai. 2026. ALDER: A Single-Loop Augmented-Lagrangian Damped Extragradient Method for Nonconvex–Concave Minimax Problems with Nonlinear Coupled Constraints. https://doi.org/10.48550/arXiv.2611.00691.

Lean setup