Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants

By Aswin Kannan, Uday V. Shanbhag. 2014

106 citations recorded by the source corpus.

We consider the stochastic variational inequality problem in which the map is expectation-valued in a component-wise sense. Much of the available convergence theory and rate statements for stochastic approximation schemes are limited to monotone maps. However, non-monotone stochastic variational inequality problems are not uncommon and are seen to arise from product pricing, fractional optimization problems, and subclasses of economic equilibrium problems. Motivated by the need to address a broader class of maps, we make the following contributions: (1) we present an extragradient-based stochastic approximation scheme and prove that the iterates converge to a solution of the original problem under either pseudomonotonicity requirements or a suitably defined acute angle condition. Such statements are shown to be generalizable to the stochastic mirror-prox framework; (2) under strong pseudomonotonicity, we show that the mean-squared error in the solution iterates produced by the extragradient SA scheme converges at the optimal rate of O1K\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal {O}}}\left( \frac{1}{{K}}\right) $$\end{document}, statements that were hitherto unavailable in this regime. Notably, we optimize the initial steplength by obtaining an ϵ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon $$\end{document}-infimum of a discontinuous nonconvex function. Similar statements are derived for mirror-prox generalizations and can accommodate monotone SVIs under a weak-sharpness requirement. Finally, both the asymptotics and the empirical rates of the schemes are studied on a set of variational problems where it is seen that the theoretically specified initial steplength leads to significant performance benefits.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Management Science and Operations Research, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Management Science and Operations Research

In Mathematical Optimization

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, background): “For example, Song et al. [2020] also focuses on quasi-strongly monotone VI but they called them strong coherent VI and show that quasi strong monotonicity is weaker than the strongly pseudo-monotone [Kannan and Shanbhag, 2019] and strongly monotone assumption.”
Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities (2021, methodology): “Last but not least, different from N-EG [7] and ESA [19], the proposed OptDE and SOptDE algorithms only need the norm square k · k2 being strongly convex but not necessarily globally Lipschitz continuous, which will be significant if k · k is a non-Euclidean norm: k · k2 can not be strongly convex a”
Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling (2020, background): “As far as we are aware, this is the first result of this type for stochastic first-order methods: almost sure convergence typically requires stronger hypotheses guaranteeing that 〈V (x), x− x〉 is uniformly positive when x / ∈ X ? [12, 21].”