On the convergence of stochastic forward-backward-forward algorithms with variance reduction in pseudo-monotone variational inequalities

Radu Bot (1) , Panayotis Mertikopoulos (2, 3) , Mathias Staudigl (4) , Phan Tu Vuong (1)

1 University of Vienna [Vienna]
2 LIG - Laboratoire d'Informatique de Grenoble
3 POLARIS - Performance analysis and optimization of LARge Infrastructures and Systems
4 Maastricht University [Maastricht]

We develop a new stochastic algorithm with variance reduction for solving pseudo-monotone stochastic variational inequalities. Our method builds on Tseng's forward-backward-forward algorithm, which is known in the deterministic literature to be a valuable alternative to Korpelevich's extragradient method when solving variational inequalities over a convex and closed set governed with pseudo-monotone and Lipschitz continuous operators. The main computational advantage of Tseng's algorithm is that it relies only on a single projection step, and two independent queries of a stochastic oracle. Our algorithm incorporates a variance reduction mechanism, and leads to a.s. convergence to solutions of a merely pseudo-monotone stochastic variational inequality problem. To the best of our knowledge, this is the first stochastic algorithm achieving this by using only a single projection at each iteration.

Domaines: Optimisation et contrôle [math.OC]

Radu Bot, Panayotis Mertikopoulos, Mathias Staudigl, Phan Tu Vuong. On the convergence of stochastic forward-backward-forward algorithms with variance reduction in pseudo-monotone variational inequalities. NIPS 2018 - Workshop on Smooth Games, Optimization and Machine Learning, Dec 2018, Montréal, Canada. pp.1-5. ⟨hal-01949361⟩