TY - JOUR
T1 - Convergent Noisy forward-backward-forward algorithms in non-monotone variational inequalities
AU - Staudigl, Mathias
AU - Mertikopoulos, Panayotis
N1 - data source:
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
KW - Stochastic approximation
KW - Variational inequalities
KW - forward-backward-forward algorithm
KW - variance reduction
KW - Variational inequalites
KW - Variance Reduction
KW - Stochastic Approximation
KW - Forward-Backward-Forward Algorithm
U2 - 10.1016/j.ifacol.2019.06.021
DO - 10.1016/j.ifacol.2019.06.021
M3 - Conference article in journal
SN - 2405-8963
VL - 52
SP - 120
EP - 125
JO - IFAC-PapersOnLine
JF - IFAC-PapersOnLine
IS - 3
ER -