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
The optimization problem is
Our assumptions:
Assumption 1 (Bounded feasible sets). The sets
Assumption 2 (Convex composite objective). The
functions
Assumption 3 (Exact proximal access). For every
Our result is algorithm-specific: we analyze Arrow–Hurwicz with a
constant step size
The required accuracy is feasibility together with a uniform
primal–dual gap bound:
Proved result
OracleTemplate.Convergence LongTails.Setups.BoundedCompositeSaddle.spec
OracleTemplate.ArrowHurwicz.ArrowHurwiczUniformRate.budgetRelevant previous results
- Antonin Chambolle and Thomas Pock. A
First-Order Primal-Dual Algorithm for Convex Problems with Applications
to Imaging. 2011 (May 2010 preprint used). Complexity:
total exact proximal and oracle calls for uniform saddle gap at most , using their extrapolated primal-dual algorithm; fixed cost, two proximal calls and two operator applications per iteration. - Antonin Chambolle and Thomas Pock. On
the ergodic convergence rates of a first-order primal-dual
algorithm. 2016 (October 30, 2014 preprint used). Complexity:
total exact proximal and oracle calls for uniform saddle gap at most , using their primal-dual algorithm with squared-norm proximity; fixed cost, two proximal calls and two operator applications per iteration.