← All setups

Alex-GDA for Block-Smooth Saddle Problems

Descriptions may be stale. Consult the linked Lean sources.

Alex-GDA for Block-Smooth Saddle Problems

We consider minx∈Emaxy∈Ff(x,y) on real Hilbert spaces E and F, where f:E×F→R is convex in x, concave in y, and has globally Lipschitz partial gradients in each variable. A given starting pair (x0,y0) lies within distance R≥0 of a saddle point in the Hilbert product norm. Each oracle query returns either ∇xf(x,y) or ∇yf(x,y). For ε>0, Alex-GDA must return (x¯,y¯) satisfying ∥∇xf(x¯,y¯)∥2+∥∇yf(x¯,y¯)∥2≤ε2 almost surely.

The saddle-point problem is minx∈Emaxy∈Ff(x,y). Norms on E and F are induced by their inner products, and we use the product norm ∥(x,y)∥=(∥x∥2+∥y∥2)1/2. The block constants satisfy Lx,Ly,Lxy≥0,Lx+Lxy>0,Ly+Lxy>0. The algorithm receives E,F,Lx,Ly,Lxy, the starting pair (x0,y0), and parameters γ,δ satisfying 1<γ≤2 and δ≥1; the radius R and tolerance ε may enter only the oracle-call budget.

Our assumptions:

Assumption 1 (Convexity and concavity). For every y∈F, the function f(⋅,y) is convex on E. For every x∈E, the function f(x,⋅) is concave on F.

Assumption 2 (Block smoothness). Both partial functions are Fréchet differentiable everywhere. For all x,x′∈E and y,y′∈F, their gradients satisfy ∥∇xf(x,y)−∇xf(x′,y)∥≤Lx∥x−x′∥,∥∇xf(x,y)−∇xf(x,y′)∥≤Lxy∥y−y′∥,∥∇yf(x,y)−∇yf(x,y′)∥≤Ly∥y−y′∥,∥∇yf(x,y)−∇yf(x′,y)∥≤Lxy∥x−x′∥.

Assumption 3 (Saddle point and initial distance). There exists (x⋆,y⋆)∈E×F such that, for every x∈E and y∈F, f(x⋆,y)≤f(x⋆,y⋆)≤f(x,y⋆), and ∥x0−x⋆∥2+∥y0−y⋆∥2≤R2.

Queries may be made at any pair in E×F. The oracle returns the requested exact partial gradient, with each partial-gradient evaluation counted as one call.

Our result is algorithm-specific: we analyze Alex-GDA. The method chooses fixed step sizes α,β>0 from its available inputs and initializes v0=0. Starting from the given pair, each iteration k≥0 makes two successive oracle calls and updates according to gk=∇xf(xk,yk+(δ−1)βvk),hk=∇yf(xk−γαgk,yk),xk+1=xk−αgk,yk+1=yk+βhk,vk+1=hk. For each completed iteration, define sk=∥gk∥2+∥hk∥2+∥vk∥2. Given a total budget of B≥0 oracle calls, let N=⌊B/2⌋. If N≥1, the output is the pre-update pair with the smallest score, with ties resolved by the earliest index: k⋆=minargmin0≤k<N⁡sk,(x¯,y¯)=(xk⋆,yk⋆). If N=0, the output is (x0,y0). An unpaired final partial-gradient call does not change the output.

The required accuracy is the squared gradient-residual bound ∥∇xf(x¯,y¯)∥2+∥∇yf(x¯,y¯)∥2≤ε2P-a.s., where P is the law of the algorithm’s randomness; the specified method and exact replies are deterministic.

Results

On real Hilbert spaces E×F, f is differentiable and convex–concave. Its partial gradients have within-block Lipschitz bounds Lx,Ly≥0 and cross-block bound Lxy≥0, with Lx+Lxy,Ly+Lxy>0. A saddle z⋆ satisfies ∥z0−z⋆∥≤R, where R≥0. Exact partial-gradient queries are available. The setup requires constant-step Alex-GDA with 1<γ≤2, δ≥1. The target is ∥∇xf(z^)∥2+∥∇yf(z^)∥2≤ε2, ε>0; (1) achieves it deterministically at a selected iterate. Other algorithm families below compare the underlying problem and oracle on the stated restrictions.

Comparison for BlockSmoothConvexConcave.
Result Oracle complexity Novelty Limitations
(1) AlexGdaConvexConcave (Ours) (review) O(1+γ4δ4Λ2R2(γ−1)3ε2)
(2) EAG-V (Yoon and Ryu 2021, Cor. 2) O(1+ΛR/ε); four block calls per iteration. Finite-dimensional statement; last-iterate accuracy. (1): No established improvement on the finite-dimensional overlap. (1): For fixed γ,δ and ΛR/ε>1, quadratic rather than linear cost; selected rather than last iterate; needs separate block bounds instead of Λ.
(3) Optimistic gradient / PEG (Gorbunov et al. 2022, Thm. 1) O(1+Λ2R2/ε2); two block calls per iteration, including initialization. Finite-dimensional unconstrained specialization; last-iterate accuracy. (1): Matches known rate for fixed γ,δ on the finite-dimensional overlap, with the same oracle access. (1): Selected rather than last iterate; at least tenfold larger leading constant; deteriorates as γ↓1 or δ grows.
(4) Alternating GDA, momentum −12 (Shugart et al. 2026, Thm. 3.1) O(1+Λ2R2/ε2); two block calls per iteration. Finite dimensions; E∥∇f(zτ)∥2≤ε2 for uniform τ. (1): Deterministic selected output instead of expected random-iterate accuracy; matches the rate for fixed γ,δ on the finite-dimensional overlap.
(5) Derived bound (Shugart et al. 2026, Thm. 3.1) O(1+Λ2R2/ε2); three block calls per iteration including residual selection. Finite dimensions; deterministic minimum-residual iterate. (1): No extra selection queries; two rather than three calls per iteration. Matched total-cost order for fixed γ,δ, not a proved total-cost saving.
(6) Alex-GDA (Lee et al. 2024, Thm. 5.1; Conj. 8.2) No general convex–concave bound in Thm. 5.1: requires twice-differentiable, finite-dimensional, strongly convex–strongly concave objectives and γ,δ>1. (1): Method-specific scope extension to mere convexity–concavity, including δ=1; selected-iterate stationarity partially addresses Conj. 8.2, without establishing its last-iterate convergence claim.

Abbr: Λ=max{Lx,Ly}+Lxy; z0=(x0,y0); ∥∇f(z)∥2=∥∇xf(z)∥2+∥∇yf(z)∥2. Costs count individual partial-gradient calls. EAG: extra anchored gradient; PEG: past extragradient; GDA: gradient descent–ascent.

Gorbunov, Eduard, Adrien Taylor, and Gauthier Gidel. 2022. Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalities. https://arxiv.org/abs/2205.08446v2.
Lee, Jaewook, Hanseul Cho, and Chulhee Yun. 2024. Fundamental Benefit of Alternating Updates in Minimax Optimization. https://arxiv.org/abs/2402.10475v2.
Shugart, Henry, Shuyi Wang, and Jason M. Altschuler. 2026. Negative Momentum for Convex-Concave Optimization. https://arxiv.org/abs/2604.17145v1.
Yoon, Taeho, and Ernest K. Ryu. 2021. “Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm.” In Proceedings of the 38th International Conference on Machine Learning, edited by Marina Meila and Tong Zhang, vol. 139. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v139/yoon21d.html.

Lean setup