  Classical extragradient schemes and their stochastic counterpart represent a
cornerstone for resolving monotone variational inequality problems. Yet, such
schemes have a per-iteration complexity of two projections onto a convex set
and require two evaluations of the map, the former of which could be relatively
expensive if $X$ is a complicated set. We consider two related avenues where
the per-iteration complexity is significantly reduced: (i) A stochastic
projected reflected gradient method requiring a single evaluation of the map
and a single projection; and (ii) A stochastic subgradient extragradient method
that requires two evaluations of the map, a single projection onto $X$, and a
significantly cheaper projection (onto a halfspace) computable in closed form.
Under a variance-reduced framework reliant on a sample-average of the map based
on an increasing batch-size, we prove almost sure (a.s.) convergence of the
iterates to a random point in the solution set for both schemes. Additionally,
both schemes display a non-asymptotic rate of $\mathcal{O}(1/K)$ where $K$
denotes the number of iterations; notably, both rates match those obtained in
deterministic regimes. To address feasibility sets given by the intersection of
a large number of convex constraints, we adapt both of the aforementioned
schemes to a random projection framework. We then show that the random
projection analogs of both schemes also display a.s. convergence under a
weak-sharpness requirement; furthermore, without imposing the weak-sharpness
requirement, both schemes are characterized by a provable rate of
$\mathcal{O}(1/\sqrt{K})$ in terms of the gap function of the projection of the
averaged sequence onto $X$ as well as the infeasibility of this sequence.
Preliminary numerics support theoretical findings and the schemes outperform
standard extragradient schemes in terms of the per-iteration complexity.
