← All setups

Smooth Convex Concave — Smooth Convex–Concave Saddle Problems

Descriptions may be stale. Consult the linked Lean sources.

Smooth Convex–Concave Saddle Problems · Lean proof

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¯)]≤ε.

Proved result

2⋅max{1,⌈2⋅L⋅D2ε⌉+}

OracleTemplate.Convergence LongTails.Setups.SmoothConvexConcave.spec OracleTemplate.SaddlePoint.budget

Relevant previous results