← All setups

Alex Gda Convex Concave — Alex-GDA for Block-Smooth Saddle Problems

Descriptions may be stale. Consult the linked Lean sources.

Alex-GDA for Block-Smooth Saddle Problems · Lean proof

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.

Proved result

2⋅⌈180⋅γ4⋅δ4⋅(max{Lx,Ly}+Lxy)2⋅R2(γ−1)3⋅ε2⌉+

OracleTemplate.Convergence LongTails.Setups.BlockSmoothConvexConcave.spec OracleTemplate.BlockSaddle.budget

Relevant previous results