Preprint C1455/2019
Algorithms for stochastic variational inequalities: convergence and complexity analysis
Philip Thompson
Keywords: stochastic approximation | randomized algorithms | stochastic variational inequalities | incremental methods | extragradient method | variance-reduction | weak-sharpness | Tykhonov regularization

Stochastic approximation methods are well established for optimization problems.
The appeal of these methods is due largely to their ability to cope efficiently and robustly
with inexact information about the underlying optimization problem. This
thesis proposes stochastic approximation methods for the solution of stochastic
variational inequalities, paying attention to asymptotic convergence (stability),
convergence rate, oracle complexity, knowledge of problem parameters, data availability
and distributed solution. In chapter 3, we propose a method that combines
stochastic approximation with incremental constraint projections, meaning that, at
each iteration, the random operator is sampled and a component of the intersection
defining the feasible set is chosen at random. Our method allows the distributed
solution of Cartesian stochastic variational inequalities with partial coordination
between users of a network. Such sequential scheme is well suited for applications
involving large data sets, online optimization and distributed learning. We analyse
this method for the class of weak-sharp monotone operators (without regularization)
and for the class of plain monotone operators with regularization. In chapter
4, we propose a stochastic extragradient method for pseudo-monotone operators
with a novel iterative variance reduction procedure. We present convergence and
complexity analysis relaxing previous assumptions used for stochastic approximation
and accelerating the convergence rate while maintaining a near-optimal oracle
complexity. Our extragradient method is also suitable for the distributed case. In
chapter 5, we propose two stochastic extragradient methods with linear search
with the same set of assumptions as in chapter 4, except that we do not require
the knowledge of the Lipschitz constant or Lipschitz continuity.