Forward-backward-forward methods with variance reduction for stochastic variational inequalities

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

1 University of Vienna [Vienna]
2 POLARIS - Performance analysis and optimization of LARge Infrastructures and Systems
3 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 (FBF) 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 by pseudo-monotone, 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 almost sure (a.s.) convergence to an optimal solution. To the best of our knowledge, this is the first stochastic look-ahead algorithm achieving this by using only a single projection at each iteration.

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

Radu Ioan Bot, Panayotis Mertikopoulos, Mathias Staudigl, Phan Tu Vuong. Forward-backward-forward methods with variance reduction for stochastic variational inequalities. 2019. ⟨hal-02405776v1⟩