Minibatch forward-backward-forward methods for solving stochastic variational inequalities

DOI10.1287/STSY.2019.0064zbMATH Open1489.90195arXiv1902.03355OpenAlexW3122435563MaRDI QIDQ5084485FDOQ5084485

Authors: Radu I. Boţ, Panayotis Mertikopoulos, Mathias Staudigl, Phan Tu Vuong 

Publication date: 24 June 2022

Published in: Stochastic Systems (Search for Journal in Brave)

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 (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..

Full work available at URL: https://arxiv.org/abs/1902.03355

Recommendations

• scientific article; zbMATH DE number 7652675
• A fast stochastic approximation-based subgradient extragradient algorithm with variance reduction for solving stochastic variational inequality problems
• New first-order algorithms for stochastic variational inequalities
• Stochastic projection gradient algorithm for stochastic variational inequalities
• Solving variational inequalities with stochastic mirror-prox algorithm

zbMATH Keywords

stochastic approximationvariational inequalitiesforward-backward-forward algorithmminibatch

Mathematics Subject Classification ID

Stochastic approximation (62L20) Stochastic programming (90C15) Strong limit theorems (60F15) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Variational inequalities (49J40)

Cites Work

• Title not available (Why is that?)
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• Finite-Dimensional Variational Inequalities and Complementarity Problems
• Pseudo-monotone complementarity problems in Hilbert space
• Lectures on Stochastic Programming
• Title not available (Why is that?)
• A New Projection Method for Variational Inequality Problems
• A Modified Forward-Backward Splitting Method for Maximal Monotone Mappings
• Stochastic Approximation Approaches to the Stochastic Variational Inequality Problem
• Stochastic forward-backward splitting for monotone inclusions
• Title not available (Why is that?)
• Solving variational inequalities with Stochastic Mirror-Prox algorithm
• Stochastic Quasi-Fejér Block-Coordinate Fixed Point Iterations with Random Sweeping
• Asymptotic Theory for Solutions in Statistical Estimation and Stochastic Programming
• On perturbed proximal gradient algorithms
• Stochastic algorithms
• On the characterization of solution sets of smooth and nonsmooth convex stochastic Nash games
• Probability theory. An analytic view.
• Stochastic mirror descent dynamics and their convergence in monotone variational inequalities
• Distributed computation of equilibria in monotone Nash games via iterative regularization techniques
• Optimization Methods for Large-Scale Machine Learning
• Learning in games with continuous action sets and unknown payoff functions
• On the convergence properties of non-Euclidean extragradient methods for variational inequalities with generalized monotone operators
• Stochastic accelerated alternating direction method of multipliers with importance sampling
• On smoothing, regularization, and averaging in stochastic approximation methods for stochastic variational inequality problems
• Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants
• Extragradient Method with Variance Reduction for Stochastic Variational Inequalities
• On variance reduction for stochastic smooth convex optimization with multiplicative noise
• Fractional Programming for Communication Systems—Part I: Power Control and Beamforming

Cited In (14)

• Two Steps at a Time---Taking GAN Training in Stride with Tseng's Method
• Title not available (Why is that?)
• Stochastic projective splitting
• Smooth monotone stochastic variational inequalities and saddle point problems: a survey
• Improved variance reduction extragradient method with line search for stochastic variational inequalities
• A stochastic projection and contraction algorithm with inertial effects for stochastic variational inequalities
• Modified Stochastic Extragradient Methods for Stochastic Variational Inequality
• Two fast variance-reduced proximal gradient algorithms for SMVIPs -- stochastic mixed variational inequality problems with suitable applications to stochastic network games and traffic assignment problems
• A fast stochastic approximation-based subgradient extragradient algorithm with variance reduction for solving stochastic variational inequality problems
• Stochastic relaxed inertial forward-backward-forward splitting for monotone inclusions in Hilbert spaces
• Variable sample-size optimistic mirror descent algorithm for stochastic mixed variational inequalities
• A stochastic Bregman golden ratio algorithm for non-Lipschitz stochastic mixed variational inequalities with application to resource share problems
• An accelerated stochastic extragradient-like algorithm with new stepsize rules for stochastic variational inequalities
• Variable sample-size operator extrapolation algorithm for stochastic mixed variational inequalities

This page was built for publication: Minibatch forward-backward-forward methods for solving stochastic variational inequalities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5084485)