Arrow Hurwicz Bounded Saddle — 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.ArrowHurwiczBoundedSaddle.budgetRelevant previous results
- Antonin Chambolle, Thomas Pock. A First-Order
Primal-Dual Algorithm for Convex Problems with Applications to
Imaging. 2011 (online publication 2010). Complexity:
fixed exact operator and proximal oracle calls for a feasible averaged pair with uniform saddle gap at most , using primal–dual hybrid gradient; one call each to , , and the two proximal maps per iteration, with no initialization calls. - Antonin Chambolle, Thomas Pock. On the ergodic
convergence rates of a first-order primal–dual algorithm. 2016
(online publication 2015; author manuscript HAL v2, September 28, 2015,
used). Complexity:
fixed exact operator and proximal oracle calls for a feasible averaged pair with uniform saddle gap at most , using their primal–dual algorithm with squared-norm proximity; one call each to , , and the two proximal maps per iteration, with no initialization calls.