← All setups

Smooth Convex–Concave Saddle Problems

Descriptions may be stale. Consult the linked Lean sources.

Smooth Convex–Concave Saddle Problems

We consider a convex–concave function φ:E×F→R on real Hilbert spaces E,F, with nonempty compact convex feasible sets X⊆E and Y⊆F. Their product has diameter at most D≥0 in the maximum product norm. The oracle returns G(x,y)=(∇xφ(x,y),−∇yφ(x,y)), which exists everywhere and is globally L-Lipschitz for L>0. For ε>0, the goal is a measurable output (x¯,y¯)∈X×Y almost surely with integrable primal–dual gap and EP[supy∈Yφ(x¯,y)−infx∈Xφ(x,y¯)]≤ε, where P is the law of the algorithm’s randomness.

The saddle-point problem is minx∈Xmaxy∈Yφ(x,y). We equip the product space with the norm ∥(x,y)∥=max{∥x∥E,∥y∥F}, where the component norms are induced by the Hilbert inner products. The algorithm receives E,F,X,Y,L,D, and ε.

Our assumptions:

Assumption 1 (Feasible geometry). The sets X and Y are nonempty, compact, and convex, and ∥z−w∥≤D,z,w∈X×Y.

Assumption 2 (Convexity and concavity). For every x,x′∈X, y,y′∈Y, and t∈[0,1], φ((1−t)x+tx′,y)≤(1−t)φ(x,y)+tφ(x′,y),φ(x,(1−t)y+ty′)≥(1−t)φ(x,y)+tφ(x,y′).

Assumption 3 (Global smoothness). For every (x,y)∈E×F, the functions φ(⋅,y) and φ(x,⋅) are Fréchet differentiable at x and y, respectively. Their signed gradient map satisfies ∥G(z)−G(w)∥≤L∥z−w∥,z,w∈E×F.

Queries may be made at any point of E×F, and each oracle reply is the exact signed gradient G(x,y). Define the primal–dual gap by Gap(x,y)=supv∈Yφ(x,v)−infu∈Xφ(u,y). After the allotted oracle calls, the output (x¯,y¯) must be measurable with respect to the given measurable structures on E and F, and must satisfy (x¯,y¯)∈X×YP-a.s.,EP[|Gap(x¯,y¯)|]<∞,EP[Gap(x¯,y¯)]≤ε.

Results

Nonempty compact convex sets X⊂E, Y⊂F in real Hilbert spaces have product diameter at most D≥0. The function φ:E×F→R is convex–concave on X×Y, with partial gradients everywhere; the exact oracle G=(∇xφ,−∇yφ) is globally L-Lipschitz, L>0. For ε>0, the target is a feasible output with ∫Gap(z(ω))dP(ω)≤ε. Result (1) constructs deterministic projected extragradient with step 1/(2L) and averages its extrapolated points; its gap is at most ε for every seed.

Smooth convex–concave saddle points: SmoothConvexConcave.
Result Oracle complexity Novelty Limitations
(1) SmoothConvexConcave (Ours) (review) O(1+LD2/ε) exact G calls; one product projection per call.
(2) Mirror-Prox (Nemirovski 2004, Thm. 3.2, (3.10)). Euclidean specialization; finite dimensions. O(1+LD2/ε) exact G calls; one product projection per call. (1): Matches known rate on finite-dimensional overlap; Lean formalization. Scope: compact subsets of Hilbert spaces instead of finite-dimensional spaces. (1) needs ambient differentiability and Lipschitz continuity; (2) needs them only on X×Y. No general Bregman-geometry guarantee in (1).
(3) Lower bound (Ouyang and Xu 2018, Thm. 9). Bilinearly coupled problems on Euclidean balls. Ω(LD2/ε) calls in the regime Lf=∥A∥≍L, RX≍RY≍D, LD2/ε≫1. Oracle: (∇f(x),Ax,A⊤y). (1) matches the worst-case order for deterministic first-order methods when 8<m≤n and the call horizon satisfies t<m/4−2.

Abbr: Gap(x,y)=supv∈Yφ(x,v)−infu∈Xφ(u,y); P is the execution probability law. L,D use the max product norm ∥(x,y)∥=max{∥x∥,∥y∥}. A product projection projects onto X and Y. In (3), φ(x,y)=f(x)+⟨Ax−b,y⟩, Lf is the Lipschitz constant of ∇f, RX,RY are ball radii, n,m their dimensions, and t the oracle-call horizon; Ω denotes a lower bound, ≍ equality up to universal factors.

Nemirovski, Arkadi. 2004. “Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems.” SIAM Journal on Optimization 15 (1): 229–51. https://doi.org/10.1137/S1052623403425629.
Ouyang, Yuyuan, and Yangyang Xu. 2018. Lower Complexity Bounds of First-Order Methods for Convex-Concave Bilinear Saddle-Point Problems. https://doi.org/10.48550/arXiv.1808.02901.

Lean setup