Descriptions may be stale. Consult the linked Lean sources.
Stochastic
Inequalities with Surjective Jacobians
We consider minimizing a differentiable function subject to , where is a finite-dimensional real inner
product space and , , are differentiable
constraints. Gradients are bounded and Lipschitz, the constraint
Jacobian is uniformly surjective, and the initial penalty gap is
bounded. Each oracle call returns unbiased estimates of the objective
gradient, constraint values, and constraint gradients at two points
using a shared sample; samples across calls are independent, with
bounded variance and mean-square smoothness. Given and , the goal is a pair satisfying , ,
and
simultaneously with probability at least .
The optimization problem is Write and
The norm on is induced by its inner product; , , and their products carry Euclidean
product norms. In particular, . The
parameters satisfy The algorithm receives , a measurable sample space , , , , , , , and a given starting point .
Our assumptions:
Assumption 1 (Regularity and surjectivity). The
functions and are Fréchet differentiable
everywhere. For every and
,
Assumption 2 (Initial penalty gap). Define the
penalty function
The given point satisfies
Assumption 3 (Stochastic estimates). There is a
probability law on and jointly measurable maps Set For every fixed , the three components of are Bochner integrable under
, and
For every , the random
variables and
are
integrable and satisfy
A query is any pair . At call , the oracle
returns The
samples are
measurable, mutually independent, and each has law . They are independent of the
algorithm’s randomness. Thus one call provides both triples using the
same sample, including when the query points are chosen adaptively.
After the allotted calls, the algorithm must return a measurable pair
. Define . The
required accuracy is where is the joint law of the algorithm’s
randomness and the oracle samples.