Descriptions may be stale. Consult the linked Lean sources.
Stochastic Nonconvex
Strongly Concave Minimax
We consider a possibly nonconvex minimax objective on
finite-dimensional real inner product spaces and . The function is strongly concave in
its second argument, with a Lipschitz gradient and Lipschitz Hessian.
Given points and satisfy bounds on the initial
value gap and dual gradient. Each oracle call returns unbiased estimates
of both partial gradients using one shared sample, independently across
calls, with bounded joint variance. For , the goal is a
measurable output
satisfying ,
where
and expectation includes sampling and independent algorithm
randomness.
The optimization problem is We equip with the product inner product
and norm All
operator norms below are induced by these norms. The parameters satisfy
The
algorithm receives , , the measurable sample space , all seven scalar parameters, and
the given points .
Our assumptions:
Assumption 1 (Gradient and Hessian regularity). Both
partial gradients of exist
everywhere and are Fréchet differentiable as functions on . Writing and , we require, for every , Here is the linear operator from to obtained by differentiating the
two partial gradients.
Assumption 2 (Strong concavity). For every and ,
Assumption 3 (Initial bounds). The given points
satisfy
Assumption 4 (Stochastic partial gradients). There
is a probability measure on
and jointly measurable maps
For each fixed , both replies are Bochner
integrable under , and The sum of squared errors is integrable and
satisfies The samples are measurable,
independent, and identically distributed with law , and are independent of algorithm
randomness. At query , call returns the pair
using the same sample for both components.
Queries may be made anywhere in . The output requirement includes the existence of a
maximizing selection
satisfying For every such
selection, the value function is . The output must be measurable, its gradient
norm must
be integrable, and it must satisfy
where is the joint law of the
oracle samples and the independent algorithm randomness.