Dual extrapolation and its applications to solving variational inequalities and related problems

By Yurii E. Nesterov. 2007

434 citations recorded by the source corpus.

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

In Computational Theory and Mathematics

In Mathematical Optimization

Citations in the corpus

A Variational Inequality Perspective on Generative Adversarial Networks (2018, methodology): “…with unbounded constraint sets (leading to a potentially inﬁnite valued function outside of the optimal set), we use the restricted merit function (Nesterov, 2007): This function acts as merit function for (VIP) on the interior of the open ball of radius R around ω 0 , as shown in Lemma 1 of…”
Solving variational inequalities with Stochastic Mirror-Prox algorithm (2008, methodology): “The goal of this paper is to demonstrate that a speciﬁc Mirror-Prox algorithm [6] for solving monotone v.i.’s with Lipschitz continuous operators can be extended onto monotone s.v.i.’s to yield, uniformly in the dimension, the optimal rate of convergence O (1) + M + N √ t . h i We present the…”
Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming (2010, methodology): “ows us to implement the estimator using eﬃcient algorithmic methods, such as interior-point methods, which provide polynomial-time bounds on computational time [16, 17], and modern ﬁrst-order methods [14, 15, 11, 1]. In what follows, all true parameter values, such as β0, σ, F0, are implicitly index”
Revisiting Stochastic Extragradient (2019, methodology): “The left-hand side in the bound above is a merit function that has been used in variational inequality literature (Nesterov, 2007).”
Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile (2018, methodology): “3 By that token, we will make the following standard assumptions for the gradient feedback sequence ĝn [Nesterov, 2007; Nemirovski et al., 2009; Juditsky et al., 2011]: a) Unbiasedness: [ĝn |Fn] = g(Xn).”
A Variational Inequality Perspective on Generative Adversarial Nets (2018, methodology): “This algorithm has been originally introduced by Korpelevich (1976) and extended by Nesterov (2007) and Nemirovski (2004).”
On the convergence of single-call stochastic extra-gradient methods (2019, background): “Lemma 1 (Nesterov, 2007) .”
A General Framework for a Class of First Order Primal-Dual Algorithms for Convex Optimization in Imaging Science (2010, methodology): “This kind of averaging of previous iterates suggests a connection to Nesterov’s method [36].”
Pivotal estimation via square-root Lasso in nonparametric regression (2011, background): “h-dimensional data. AnnalsofStatistics, 37(1):2246–2270, 2009. [19] Y. Nesterov. Smooth minimization of non-smooth functions, mathematical programming. Mathematical Programming, 103(1):127–152, 2005. [20] Y. Nesterov. Dual extrapolation and its applications to solving variational inequalities and re”
Variance Reduction for Matrix Games (2019, methodology): “In comparison, accelerated linear-time methods run in time Õ (nnz(A)Lexact/ ) [24, 25]; in `1-`1 and `2-`1 games we have Lrow-col = Lexact and the guarantee (9) is at least as good.”
Stochastic Mirror Descent in Variationally Coherent Optimization Problems (2017, background): “These results were further boosted by recent work on extra-gradient variants of the algorithm [11, 17], and the ergodic relaxation of [8] where the independence assumption on the gradient samples is relaxed and is replaced by a mixing distribution that converges in probability to a well-defined limi”
Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling (2020, background): “[11], Nemirovski [26], Nesterov [27], and references therein.”
Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities (2021, methodology): “Another important non-Euclidean extension is Nesterov’s dual extrapolation [31] from the perspective of dual averaging, which also has the optimal O(1/✏) convergence rate.”
Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence (2020, methodology): “For any ﬁxed positive value D , we deﬁne If X is a bounded domain, we deﬁne The following lemma, shown in (Nesterov 2007), justiﬁes the use of the error function to analyze convergence.”