Accelerated schemes for a class of variational inequalities

By Yunmei Chen, Guanghui Lan, Yuyuan Ouyang. 2014

138 citations recorded by the source corpus.

We propose a novel stochastic method, namely the stochastic accelerated mirror-prox (SAMP) method, for solving a class of monotone stochastic variational inequalities (SVI). The main idea of the proposed algorithm is to incorporate a multi-step acceleration scheme into the stochastic mirror-prox method. The developed SAMP method computes weak solutions with the optimal iteration complexity for SVIs. In particular, if the operator in SVI consists of the stochastic gradient of a smooth function, the iteration complexity of the SAMP method can be accelerated in terms of their dependence on the Lipschitz constant of the smooth function. For SVIs with bounded feasible sets, the bound of the iteration complexity of the SAMP method depends on the diameter of the feasible set. For unbounded SVIs, we adopt the modified gap function introduced by Monteiro and Svaiter for solving monotone inclusion, and show that the iteration complexity of the SAMP method depends on the distance from the initial point to the set of strong solutions. It is worth noting that our study also significantly improves a few existing complexity results for solving deterministic variational inequality problems. We demonstrate the advantages of the SAMP method over some existing algorithms through our preliminary numerical experiments.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis, 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 Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

In Mathematical Optimization

Citations in the corpus

Certifying Some Distributional Robustness with Principled Adversarial Training (2017, background): “When ` is convex in θ and γ is large enough that z 7→ (`(θ; z) − γc(z, z0)) is concave for all (θ, z0) ∈ Θ × Z , we have a stochastic monotone variational inequality, which is efficiently solvable (Juditsky et al., 2011; Chen et al., 2014) with convergence rate 1/ √ T .”
Extragradient Method with Variance Reduction for Stochastic Variational Inequalities (2017, methodology): “…order to analyze the monotone case, SA methodologies based on the extragradient method of Korpelevich [25] and the mirror-prox algorithm of Nemiroviski [31] were used in [19, 7, 44, 21, 22], and iterative Tykhonov and proximal regularization procedures (see [20, 24]), were used in [43, 26, 17, 45].”
Accelerating Smooth Games by Manipulating Spectral Shapes (2020, methodology): “Some old papers (Korpelevich, 1976; Tseng, 1995) and many recent ones (Nemirovski, 2004; Chen et al., 2014; Palaniappan and Bach, 2016; Mescheder et al., 2017; Gidel et al., 2019a,b; Daskalakis et al., 2018; Mokhtari et al., 2019; Azizian et al., 2019) suggest new methods and provide better upper…”
A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Differentiable Games (2020, methodology): “It was initially introduced for online learning (Chiang et al., 2012; Rakhlin and Sridharan, 2013) and subsequently studied in the context of games by Daskalakis et al. (2018), who proved that this method converges on bilinear games. Gidel et al. (2019a) interpreted GANs as a variational inequality ”
Certifiable Distributional Robustness with Principled Adversarial Training (2017, background): “When l is convex in θ and γ is large enough that z 7→ (l(θ; z) − γc(z, z0)) is concave for all (θ, z0) ∈ Θ × Z, we have a stochastic monotone variational inequality, which is efficiently solvable [23, 13] with convergence rate 1/ √ T .”
Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants (2014, background): “s for monotone SVIs in non-Lipshitzian regimes. Noteworthy amongst past eorts is the development of a class of accelerated techniques for deterministic and stochastic variational inequality problems [44]. We summarize much of the prior results in Table1. We believe that this is amongst the rst eorts”