← All setups

Arrow Hurwicz Uniform Rate — Arrow–Hurwicz for Bounded Composite Saddles

Descriptions may be stale. Consult the linked Lean sources.

Arrow–Hurwicz for Bounded Composite Saddles · Lean proof

Arrow–Hurwicz for Bounded Composite Saddles

We consider the saddle objective Φ(x,y)=g(x)+⟨y,Kx⟩−h(y) on convex sets X⊂E and Y⊂F, where E,F are real inner product spaces. Both sets lie in balls of radius R>0 about zero; g:E→R and h:F→R are convex and M-Lipschitz on their respective sets, with M≥0, and K:E→F is bounded linear with operator norm at most L>0. The oracle returns exact linear-map, adjoint, and constrained proximal evaluations. From given feasible points, Arrow–Hurwicz must return a feasible pair (x¯,y¯) satisfying Φ(x¯,y)−Φ(x,y¯)≤ε for every (x,y)∈X×Y, almost surely, where ε>0 is the tolerance.

The optimization problem is infx∈Xsupy∈YΦ(x,y). The norms on E and F are induced by their inner products, and we use the product norm ∥(x,y)∥=max{∥x∥,∥y∥}. Operator norms are the induced operator norms. The algorithm receives E,F,X,Y,R,L,M,ε and the starting points x0,y0; access to K,g,h is through the oracle.

Our assumptions:

Assumption 1 (Bounded feasible sets). The sets X and Y are convex, x0∈X, y0∈Y, and ∥x∥≤Rfor every x∈X,∥y∥≤Rfor every y∈Y.

Assumption 2 (Convex composite objective). The functions g and h are convex on X and Y, respectively, and satisfy |g(a)−g(b)|≤M∥a−b∥(a,b∈X),|h(a)−h(b)|≤M∥a−b∥(a,b∈Y). The map K:E→F is bounded linear with ∥K∥op≤L. There exists a map K∗:F→E satisfying ⟨K∗y,z⟩=⟨y,Kz⟩,y∈F, z∈E.

Assumption 3 (Exact proximal access). For every u∈E, v∈F, and t>0, the oracle provides points pX(u,t)∈argminx∈X{tg(x)+12∥x−u∥2},pY(v,t)∈argminy∈Y{th(y)+12∥y−v∥2}. The oracle also returns Kx for any x∈E and K∗y for any y∈F. Each linear-map, adjoint, or proximal evaluation counts as one call to the same oracle. Proximal queries accept arbitrary real t, with the stated minimization requirement applying when t>0.

Our result is algorithm-specific: we analyze Arrow–Hurwicz with a constant step size η>0 chosen from the available inputs. Starting from the given pair (x0,y0), the updates are xk+1=pX(xk−ηK∗yk,η),yk+1=pY(yk+ηKxk+1,η),k≥0. Each iteration makes four calls, in the order K∗yk, the primal proximal evaluation, Kxk+1, and the dual proximal evaluation. After N≥1 complete iterations, the output is x¯=1N∑k=1Nxk,y¯=1N∑k=1Nyk. If the call budget ends during a subsequent iteration, that incomplete iteration is excluded from the averages. If no iteration has been completed, the output is the current pair: (x0,y0) after zero or one call, and (x1,y0) after two or three calls.

The required accuracy is feasibility together with a uniform primal–dual gap bound: (x¯,y¯)∈X×Y,Φ(x¯,y)−Φ(x,y¯)≤εfor every x∈X, y∈Y,P-a.s., where P is the law of the algorithm’s randomness; the specified Arrow–Hurwicz method and its oracle replies are deterministic.

Proved result

4⋅⌈200⋅R⋅(L⋅R+M)ε⌉+

OracleTemplate.Convergence LongTails.Setups.BoundedCompositeSaddle.spec
  OracleTemplate.ArrowHurwicz.ArrowHurwiczUniformRate.budget

Relevant previous results