Descriptions may be stale. Consult the linked Lean sources.
Arrow–Hurwicz for
Bounded Composite Saddles
We consider the saddle objective
on convex sets and , where are real inner product spaces. Both
sets lie in balls of radius
about zero; and
are convex and
-Lipschitz on their respective
sets, with , and is bounded linear with operator
norm at most . The oracle
returns exact linear-map, adjoint, and constrained proximal evaluations.
From given feasible points, Arrow–Hurwicz must return a feasible pair
satisfying
for every ,
almost surely, where is the tolerance.
The optimization problem is The norms on and are induced by their inner products,
and we use the product norm . Operator
norms are the induced operator norms. The algorithm receives and the
starting points ; access to
is through the oracle.
Our assumptions:
Assumption 1 (Bounded feasible sets). The sets and are convex, , , and
Assumption 2 (Convex composite objective). The
functions and are convex on and , respectively, and satisfy The map is bounded linear with . There exists a
map satisfying
Assumption 3 (Exact proximal access). For every
, , and , the oracle provides points The oracle also returns for any and for any . Each linear-map, adjoint, or
proximal evaluation counts as one call to the same oracle. Proximal
queries accept arbitrary real ,
with the stated minimization requirement applying when .
Our result is algorithm-specific: we analyze Arrow–Hurwicz with a
constant step size chosen
from the available inputs. Starting from the given pair , the updates are Each iteration makes four calls, in the order
, the primal proximal
evaluation, , and the dual
proximal evaluation. After
complete iterations, the output is 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: after zero
or one call, and after
two or three calls.
The required accuracy is feasibility together with a uniform
primal–dual gap bound: where is
the law of the algorithm’s randomness; the specified Arrow–Hurwicz
method and its oracle replies are deterministic.