Descriptions may be stale. Consult the linked Lean sources.
Stochastic Surjective
Inequality Constraints
We study minimizing a differentiable function subject to
differentiable inequalities , , on a finite-dimensional
real inner-product space .
Objective and constraint gradients are bounded and Lipschitz, the
constraint derivative is uniformly surjective, and a given point has
bounded initial penalty gap. Each oracle call returns unbiased
stochastic objective gradients, constraint values, and constraint
gradients at two points using one shared sample; successive samples are
independent, with bounded variance and mean-square Lipschitz dependence
on the points. For , the goal is a
measurable pair satisfying , , ,
and
simultaneously with probability at least .
The optimization problem is Write and
We use the
inner-product norm on , the
Euclidean norm on , and
the product norm on . In particular, all norms of below are product norms. Fix and
a given point . The
algorithm receives , the
measurable sample space , and
.
Our assumptions:
Assumption 1 (Regularity and surjectivity). The
functions and , , are differentiable
everywhere. For every ,
Moreover, for every and ,
Assumption 2 (Initial penalty gap). Define the
penalty function
The given point satisfies
Assumption 3 (Stochastic primitive estimates). There
is a probability measure on
and jointly measurable maps
For each , these maps are Bochner integrable in their sample argument
and satisfy For every , the nonnegative random variables inside the following
expectations are integrable, and
A query is any pair . At call , the oracle
returns The measurable
samples are
mutually independent with common law , and are independent of the
algorithm’s randomness. Thus both points in one query share a sample,
and each paired reply counts as one oracle call.
After the allotted calls, the output must be
measurable. Under , the joint law
of the algorithm’s randomness and the sample sequence, the following
conditions must hold simultaneously with probability at least :