Extragradient method with variance reduction for pseudo-monotone stochastic variational inequalities

Resumen:

We propose an extragradient method with stepsizes bounded away from zero for stochastic variational inequalities requiring only pseudo-monotonicity. We provide convergence and complexity analysis, allowing for an unbounded feasible set, unbounded operator, non-uniform variance of the oracle and, also, we do not require any regularization.

Alongside the stochastic approximation procedure, we iteratively reduce the variance of the stochastic error. Our method attains the optimal oracle complexity O(1/epsilon^2) (up to a logarithmic term) and an accelerated rate O(1/K) in terms of the mean (quadratic) natural residual and the D-gap function, where K is the number of iterations required for a given tolerance epsilon > 0. The generated sequence also enjoys a new feature: the sequence is bounded in Lp if the stochastic error has finite p-moment.Explicit estimates for the convergence rate, the complexity and the p-moments are given depending on problem parameters and distance of the initial iterate to the solution set. Moreover, sharper constants are possible if the variance is uniform over the solution set or the feasible set. Our results provide new classes of stochastic variational inequalities for which a convergence rate of O(1/K) holds in terms of the mean-squared distance to the solution set. Our analysis includes the distributed solution of pseudo-monotone Cartesian variational inequalities under partial coordination of parameters between users of a network. Joint work with A. Iusem (IMPA), A. Jofré (CMM-DIM) and R. Oliveira (IMPA).

Posted on Sep 1, 2015 in Optimization and Equilibrium, Seminars