Descriptions may be stale. Consult the linked Lean sources.
Coupled
Strongly Concave Minimax
We consider minimizing over the maximum of over subject to
, where has components and are nonnegative integers. The
sets are compact and convex; is
strongly concave in , potentially
nonconvex in , and each constraint
is convex in . Gradients and
constraint Jacobians satisfy Lipschitz and boundedness conditions,
together with a uniform constraint qualification. On , the oracle returns , , , and its Jacobian.
For , the goal is
an output in with
nonnegative multipliers whose Euclidean constraint violation, absolute
complementarity sum, and two normal-cone stationarity residuals are each
at most , almost
surely.
The optimization problem is Write ,
, and let and . All vector norms
are Euclidean, with the product norm
Operator norms are induced by
these norms. The parameters satisfy The algorithm receives the dimensions, sets , given points , and all the displayed scalar
parameters.
Our assumptions:
Assumption 1 (Domain and starting points). The sets
and are compact and convex, with and . Their diameters satisfy
Assumption 2 (Differentiability and uniform bounds).
The functions and are Fréchet differentiable at every
point of . Write for the Jacobian
of at . For all , For every ,
Assumption 3 (Strong concavity and constraint
convexity). For every and
, the function
is convex on
. For every and ,
For a convex set and , define its normal cone by
Assumption 4 (Uniform constraint qualification). For
every , there exists
such that
At a query , the oracle
returns the exact tuple Queries take values in ; replies outside are unspecified.
The output is a triple .
Set and
where denotes the Euclidean
adjoint. Define
componentwise by .
The required accuracy is Here is
the law of the algorithm and oracle randomness, taken independently, and
the almost-sure requirement applies to all the displayed output
conditions jointly.