Descriptions may be stale. Consult the linked Lean sources.
Stochastic Constrained
Monotone Inclusions
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 segmentwise generalized Lipschitz bound with constants and . A given lies within distance of a solution with , where . Two oracles return independent
unbiased estimates of with
variance at most , where
, and exact projections
onto . For and , the goal is a feasible
output admitting a normal
vector , meaning for all
, with , with
probability at least .
The variational inequality is to find such that The norm is induced by the inner
product on . The algorithm
receives , the measurable sample
space , , and the parameters ; it
accesses and through the two oracles. Both oracles
accept queries at any point of ,
and their calls are counted separately.
Our assumptions:
Assumption 1 (Constraint set and nearby solution).
The set is convex and contains
. There exists a solution of the variational inequality
satisfying The projection oracle returns at , where
Assumption 2 (Monotonicity and generalized Lipschitz
continuity). The operator is
continuous on and satisfies For all and , the segment bound implies
Assumption 3 (Stochastic operator oracle). There is
a probability measure on and a jointly measurable map . For every , the map is Bochner integrable and
is integrable
under , with Let be measurable, mutually
independent samples with common law , independent of the algorithm’s
randomness. At the th call across
both oracles, a stochastic operator query at returns , while a projection query
returns .
The output must be
measurable. For , define the
normal cone The required accuracy is where is the joint law of the algorithm’s
randomness and the independent sample sequence.