Back to Search Start Over

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

Authors :
Bot, Radu
Mertikopoulos, Panayotis
Staudigl, Mathias
Vuong, Phan
University of Vienna [Vienna]
Laboratoire d'Informatique de Grenoble (LIG )
Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])
Performance analysis and optimization of LARge Infrastructures and Systems (POLARIS )
Inria Grenoble - Rhône-Alpes
Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG )
Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])
Maastricht University [Maastricht]
Source :
NIPS 2018-Workshop on Smooth Games, Optimization and Machine Learning, NIPS 2018-Workshop on Smooth Games, Optimization and Machine Learning, Dec 2018, Montréal, Canada. pp.1-5
Publication Year :
2018
Publisher :
HAL CCSD, 2018.

Abstract

International audience; 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.

Details

Language :
English
Database :
OpenAIRE
Journal :
NIPS 2018-Workshop on Smooth Games, Optimization and Machine Learning, NIPS 2018-Workshop on Smooth Games, Optimization and Machine Learning, Dec 2018, Montréal, Canada. pp.1-5
Accession number :
edsair.dedup.wf.001..ba11088abe307da5760d0e32e8fc608c