Solving variational inequalities with Stochastic Mirror-Prox algorithm

By Anatoli B. Juditsky, A. Nemirovskii, Claire Tauvel. 2008

489 citations recorded by the source corpus.

In this paper we consider iterative methods for stochastic variational inequalities (s.v.i.) with monotone operators. Our basic assumption is that the operator possesses both smooth and nonsmooth components. Further, only noisy observations of the problem data are available. We develop a novel Stochastic Mirror-Prox (SMP) algorithm for solving s.v.i. and show that with the convenient stepsize strategy it attains the optimal rates of convergence with respect to the problem parameters. We apply the SMP algorithm to Stochastic composite minimization and describe particular applications to Stochastic Semidefinite Feasability problem and Eigenvalue minimization.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics, Optimization & Training

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 Mechanics

In Computational Theory and Mathematics

In Optimization & Training

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, background): “…for the analysis of stochastic algorithms, papers assume either bounded operators [Nemirovski et al., 2009, Abernethy et al., 2021] or bounded variance [Juditsky et al., 2011, Yang et al., 2020, Lin et al., 2020a, Luo et al., 2020, Tran Dinh et al., 2020] and growth condition [Lin et al., 2020b].”
Reducing Noise in GAN Training with Variance Reduced Extragradient (2019, background): “Note that constraining the optimization problem (23) to bounded domains ⇥ and , would make the finite variance assumption from Juditsky et al. (2011) holds.”
A Variational Inequality Perspective on Generative Adversarial Networks (2018, methodology): “(Juditsky et al., 2011, Thm. 1) Under Assump.”
First Analysis of Local GD on Heterogeneous Data (2019, methodology): “Second, there exists at least one method, whose convergence is guaranteed under bounded gradients [6], but in practice the method diverges [3, 12].”
Agnostic Federated Learning (2019, background): “Juditsky, Nemirovski, and Tauvel (2011) proposed a stochastic Mirror-Prox algorithm for solving stochastic variational inequalities, which would be applicable in our context.”
Distributed delayed stochastic optimization (2011, methodology): “For the remainder of the paper, we will use the following three essentially standard assumptions [8, 9, 20] about the stochastic optimization problem (1).”
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 .”
Tighter Theory for Local SGD on Identical and Heterogeneous Data (2019, methodology): “Second, there exists at least one method, whose convergence is guaranteed under bounded variance (Juditsky et al., 2011), but in practice the method diverges (Chavdarova et al.”
Revisiting Stochastic Extragradient (2019, methodology): “Since the existing stochastic extragradient algorithm, called Mirror-Prox, of (Juditsky et al., 2011) diverges on a simple bilinear problem when the domain is not bounded, we prove guarantees for solving variational inequality that go beyond existing settings.”
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 .”
Randomized Smoothing for Stochastic Optimization (2011, methodology): “Although such methods are classical [30, 11, 28], recent work by Juditsky et al. [15] and Lan [18, 19] has shown that if f is smooth—its gradients are Lipschitz continuous—convergence rates dependent on the variance of the stochastic gradient estimator are achievable.”
Convex optimization under inexact first-order information (2009, methodology): “34) also exhibits the best known so far rate of convergence guaranteed by a more involved stochastic mirror-prox algorithm [25].”
Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems (2017, methodology): “Our proposed algorithm and analysis was partly motivated by the stochastic mirror-prox meth-ods for solving convex-concave saddle point problems [20] and variational inequalities [13].”
ODE Analysis of Stochastic Gradient Methods with Optimism and Anchoring for Minimax Problems and GANs (2019, unknown): “Classical literature analyze convergence of the Polyak-averaged iterates (which assigns less weight to newer iterates) when solving convex-concave saddle point problems using stochastic subgradients [47, 46, 24, 17].”