Descriptions may be stale. Consult the linked Lean sources.
Constrained Monotone
Operators with Gap Noise
We consider a variational inequality for a continuous monotone
operator on a convex set
in a finite-dimensional real
Hilbert space . The operator
satisfies a generalized Lipschitz bound, and a given point lies near a solution. Two
oracles return independent-sample unbiased estimates of on , with variance controlled by an
operator gap, and exact projections onto . For and , the goal is a measurable
output admitting with for every
and , with
probability at least .
The underlying variational inequality is to find such that The norm is induced by the inner
product on . The parameters
satisfy The algorithm receives , a measurable sample space , , and all parameters ;
it accesses and through the two oracles.
Our assumptions:
Assumption 1 (Feasibility and reference solution).
The set is convex and
contains . There exists a
solution of the variational
inequality satisfying An exact projection map is available and satisfies,
for every ,
Assumption 2 (Monotonicity and generalized Lipschitz
bound). The operator is
continuous on , and for all , For
every and , the segment bound implies
Assumption 3 (Gap-dependent stochastic noise). There
is a probability measure on
and a jointly measurable map
. For every
, the random vector is Bochner integrable and is integrable for , with The reference solution is the same as above. The oracle
samples are
measurable, mutually independent, and each has law . This sequence is independent of the
algorithm’s randomness.
Both oracles accept queries in . At the th oracle call, a stochastic query at
returns , whereas a projection query at
returns . The stochastic moment
conditions apply to queries in .
Stochastic-operator calls and projection calls are counted
separately.
Define the normal cone at
by After the allotted calls, the
output must be measurable
and satisfy where is the
joint law of the oracle samples and the independent algorithm
randomness.