Descriptions may be stale. Consult the linked Lean sources.
Constrained
Second-Order Minimax Optimization
We consider minimizing , where , and
are finite-dimensional real inner
product spaces, and is
nonempty, closed, and convex. The function has a globally Lipschitz gradient and
Hessian and is strongly concave in its second variable. Given initial
points have bounded value gap and gradient norm. The oracle returns the
value, gradient, and Hessian of
at any queried point. For , the goal is
differentiability of and an
output satisfying
almost surely under , the law of
the algorithm’s randomness.
The optimization problem is Equip with the product inner product
and norm
Write for the component of . The Hessian is the derivative of the
gradient, viewed as a linear operator from to itself; denotes its
induced operator norm.
The parameters satisfy The given
initial points are and
. The algorithm receives
, , , , , , , , , , and .
Our assumptions:
Assumption 1 (Second-order regularity). The function
is Fréchet differentiable
everywhere, its gradient is Fréchet differentiable everywhere, and, for
all ,
Assumption 2 (Strong concavity). For every and ,
Assumption 3 (Initial bounds). The initial value gap
and full gradient satisfy
Queries may be made at any , including points whose second component lies outside . The exact second-order oracle returns
The output requirement is that be differentiable everywhere on
and that, after the allotted
oracle calls, satisfy