← All setups

Arrow–Hurwicz for Bounded Composite Saddles

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Convex sets X⊂E, Y⊂F in real inner-product spaces satisfy ∥x∥,∥y∥≤R, with (x0,y0)∈X×Y. The objective is Φ(x,y)=g(x)+⟨y,Kx⟩−h(y), where K is continuous linear, ∥K∥≤L, and g,h are convex and M-Lipschitz on their respective domains; R,L,ε>0, M≥0. Exact K,K∗ and constrained proximal maps are available. The setup restricts algorithms to constant-step Arrow–Hurwicz. The target is a feasible pair (x¯,y¯) with Φ(x¯,y)−Φ(x,y¯)≤ε for every (x,y)∈X×Y, deterministically.

Bounded composite saddle problems: BoundedCompositeSaddle.
Result Oracle complexity Novelty Limitations
(1) ArrowHurwiczUniformRate (Ours) (review) O(1+LR2+MRε)
(2) ArrowHurwiczBoundedSaddle (Ours) (review) O(1+(R(LR+M)ε)4/3)
(3) PDHG (Chambolle and Pock 2010, Thm. 1(b), Eq. (16)); θ=1. Derived bound. O(1+LR2ε) (1): Matches known rate when M≤LR, with an Arrow–Hurwicz guarantee. (2): No established improvement. (1): extra MR/ε. (2): worse accuracy exponent. (1), (2): require Lipschitz terms; (3) needs only bounded comparator sets.
(4) Arrow–Hurwicz (Chambolle and Pock 2010, sec. 3.2, Eq. (20)). Derived bound. O(1+L2R4ε2) For M≤LR, ε≤LR2, method-specific costs: (1) O(1+LR2/ε); (2) O(1+(LR2/ε)4/3), versus (4)’s quadratic dependence. (1): step independent of accuracy. (1), (2): add bounded primal domain and Lipschitz terms. (2) is worse when M≫L3/2R2/ε.
(5) AltGDA (Nan et al. 2026, Thm. 1, v1). Special case: simplices, g=h=0, R=1. O(1+Lδε); η=δ/(22L). (1): O(1+L/ε) removes 1/δ and knowledge of δ in the step. (1), (2): extend to bounded convex domains and Lipschitz composites. (2) gains when δ≪(ε/L)1/3, ε≤L. (1): larger leading constant for large δ. (2): worse when δ≫(ε/L)1/3.

Abbr: R bounds domain norms; L bounds ∥K∥; M bounds the Lipschitz constants; ε is the full saddle-gap tolerance. Costs count each K, K∗ and proximal evaluation separately (four calls per iteration, including two simplex projections in (5)). δ∈(0,1] is the minimum positive support probability and off-support payoff slack divided by L at a selected strictly complementary equilibrium, omitting absent off-support terms. Derived bounds specialize the cited comparator inequalities to radius R and the stated exact proximal oracles.

Chambolle, Antonin, and Thomas Pock. 2010. A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging. No. 685. Centre de Mathématiques Appliquées, École Polytechnique. https://optimization-online.org/wp-content/uploads/2010/06/2646.pdf.
Nan, Tianlong, Garud Iyengar, Christian Kroer, and Shuvomoy Das Gupta. 2026. AltGDA Achieves Global O(1/T) Ergodic Convergence in Matrix Games. https://doi.org/10.48550/arXiv.2609.32995.

Lean setup