Variance-Reduced Splitting Schemes for Monotone Stochastic Generalized
  Equations
  We consider monotone inclusion problems where the operators may be
expectation-valued, a class of problems that subsumes convex stochastic
optimization problems as well as subclasses of stochastic variational
inequality and equilibrium problems. A direct application of splitting schemes
is complicated by the need to resolve problems with expectation-valued maps at
each step, a concern that is addressed by using sampling. Accordingly, we
propose an avenue for addressing uncertainty in the mapping: Variance-reduced
stochastic modified forward-backward splitting scheme (vr-SMFBS). In
constrained settings, we consider structured settings when the map can be
decomposed into an expectation-valued map A and a maximal monotone map B with a
tractable resolvent. We show that the proposed schemes are equipped with a.s.
convergence guarantees, linear (strongly monotone A) and O(1/k) (monotone A)
rates of convergence while achieving optimal oracle complexity bounds. The rate
statements in monotone regimes appear to be amongst the first and rely on
leveraging the Fitzpatrick gap function for monotone inclusions. Furthermore,
the schemes rely on weaker moment requirements on noise and allow for weakening
unbiasedness requirements on oracles in strongly monotone regimes. Preliminary
numerics on a class of two-stage stochastic variational inequality problems
reflect these findings and show that the variance-reduced schemes outperform
stochastic approximation schemes and sample-average approximation approaches.
The benefits of attaining deterministic rates of convergence become even more
salient when resolvent computation is expensive.
