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

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01949361
Contributor : Panayotis Mertikopoulos <>
Submitted on : Monday, December 10, 2018 - 9:05:02 AM
Last modification on : Thursday, February 7, 2019 - 3:38:28 PM
Long-term archiving on : Monday, March 11, 2019 - 12:51:34 PM

File

FBF_NIPS2018.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01949361, version 1

Citation

Radu Bot, Panayotis Mertikopoulos, Mathias Staudigl, Phan 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⟩

Share

Metrics

Record views

77

Files downloads

112