Descriptions may be stale. Consult the linked Lean sources.
Stochastic
Inequality-Constrained Optimization
We consider minimizing a possibly nonconvex differentiable function
subject to
differentiable inequalities , , on a finite-dimensional
real inner product space .
Gradients are globally Lipschitz and bounded on the feasible set, which
satisfies a uniform constraint qualification near active constraints; a
given feasible starting point has bounded objective gap. Each oracle
call returns stochastic objective gradients, constraint values, and
constraint gradients at two points using a shared sample, with
independent samples across calls, unbiasedness, bounded variance, and
mean-square Lipschitz continuity on feasible points. For and , the goal is a feasible
output with multipliers
satisfying and
with probability at least .
Write and
define the feasible set . The problem is Let , with
transpose action The norm on is
induced by its inner product; and carry their Euclidean product norms.
For triples in , use The parameters satisfy
The algorithm receives , the measurable sample space , , , , , , , , , , and the starting point .
Our assumptions:
Assumption 1 (Differentiability and gradient
bounds). The functions and , , are Fréchet differentiable
everywhere. For every and every , For every and every ,
Assumption 2 (Uniform band constraint
qualification). For every , there exists
with such that,
simultaneously for all ,
Assumption 3 (Initial feasibility and objective
gap). The given point belongs
to , and
Assumption 4 (Stochastic primitive estimates). There
is a probability measure on
and jointly measurable maps
Define and
. For
every , the three
components of are
Bochner integrable under , and
The squared error is integrable and satisfies
For every , the squared difference
below is integrable, and
At call , a query is any pair
. The oracle
returns using
the same sample for both points and all components. The measurable
samples are
mutually independent with common distribution , and are independent of the
algorithm’s randomness. One such paired reply counts as one oracle call.
The moment conditions above apply to feasible query points.
After the allotted calls, the algorithm must return a measurable pair
satisfying where is the joint law of the oracle samples
and the algorithm’s randomness.