Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems

By Arkadi Nemirovski. 2004

1,109 citations recorded by the source corpus.

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

In Computational Theory and Mathematics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, methodology): “In contrast, for the stochastic setting, guarantees on the classic extragradient method and its variants rely on iterate averaging over compact domains (Nemirovski, 2004).”
A Tight and Unified Analysis of Extragradient for a Whole Spectrum of Differentiable Games (2019, methodology): “Indeed Nemirovski (2004) shown a rate of O (1 /t ) for extragradient by treating it as a "good enough" approximation of the proximal point method.”
Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “Moving beyond SGD, in Section 5 we consider the stochastic extra-gradient (SEG) method [42, 57, 37, 32, 25] used to solve general variational inequalities [28].”
A Variational Inequality Perspective on Generative Adversarial Networks (2018, methodology): “A similar one is used in (Nemirovski, 2004; Juditsky et al., 2011).”
How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD (2018, background): “ AGD. Recall that starting from a point x 0 , if we perform T steps of gradient descent (GD) x t+1 = x t 1 L r f (x t), then it satises P T 1 t=0 kr f (x t)k2 L (f (x 0 ) f (x )) (see for instance [7, 22]). In addition, if this x 0 is already the output of AGD for another T iterations, then it sati”
Solving variational inequalities with Stochastic Mirror-Prox algorithm (2008, methodology): “We are about to present the stochastic version of the deterministic Mirror-Prox algorithm proposed in [9].”
Revisiting Stochastic Extragradient (2019, methodology): “A stochastic version of the Mirror-Prox method (Nemirovski, 2004) was analyzed in (Juditsky et al.”
Predictor-Corrector Policy Optimization (2018, background): “• Extragradient descent (Korpelevich, 1976), mirror-prox (Nemirovski, 2004; Juditsky et al., 2011) or optimistic mirror descent (Chiang et al.”
Solving variational inequalities with monotone operators on domains given by Linear Minimization Oracles (2013, methodology): “Below we discuss in details the situation when the latter algorithm is either MD [18, Chapter 5], or MP ([25], see also [18, Chapter 6] and [27]).”
A Theory of Regularized Markov Decision Processes (2019, methodology): “It would be interesting to take inspiration from proximal convex optimization to derive new dynamic programming approaches, for example based on Dual Averaging [Nesterov, 2009] or Mirror Prox [Nemirovski, 2004].”
On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach (2019, background): “The vast majority of this line of research focus on convex-concave setting (Kinderlehrer and Stampacchia, 1980; Nemirovski and Yudin, 1978; Nemirovski, 2004; Mokhtari et al., 2019b;a).”
Model-Agnostic Linear Competitors - When Interpretable Models Compete and Collaborate with Black-Box Models (2019, methodology): “iques are available in literature including subgradient methods (Nemirovski et al. 2009, Duchi et al. 2011), accelerated gradient methods (Nesterov 2013, Beck and Teboulle 2009), primal-dual methods (Nemirovski 2004, Chambolle and Pock 2011) and many stochastic rst-order methods based on randomly sa”
Dual extrapolation and its applications to solving variational inequalities and related problems (2007, methodology): “The method proposed in [ 3 ] can be seen as a two-level scheme, which implements in a smart way a standard prox-type algorithm.”
Extremely Low Bit Neural Network: Squeeze the Last Bit Out with ADMM (2017, background): “Particularly, this additional iteration allows to foresee the geometry of the problem and take the curvature information into account, which leads to a better convergency than standard gradient descent (Nemirovski 2004).”
A Direct Formulation for Sparse PCA Using Semidefinite Programming (2004, positive): “Of special interest are the recent ly-developed algorithms due to [8, 9].”
Proximal Reinforcement Learning: A New Theory of Sequential Decision Making in Primal-Dual Spaces (2014, methodology): “The framework of mirror descent [5, 6] plays a central role in our framework, which includes not just the original mirror descent method, but also the mirror-prox method [7], which generalizes the extragradient method to non-Euclidean geometries [8].”
Multiple Kernel Learning from Noisy Labels by Stochastic Programming (2012, background): “…(Lawrence & Schölkopf, 2001; Pal et al., 2007; Yang et al., 2010) on learning with noisy labeled data that make strong assumptions about the noise model (e.g. conditional independence assumption between noisy label and the data given the true label), our framework depends only on a mild…”