On linear convergence of iterative methods for the variational inequality problem

By Paul Tseng. 1995

How researchers see this paper

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

In Optimization & Training

Citations in the corpus

A Tight and Unified Analysis of Extragradient for a Whole Spectrum of Differentiable Games (2019, methodology): “On the other hand, Tseng (1995) proved linear convergence results for extragra-dient by using the projection-type error bound Tseng (1995, Eq.”
Reducing Noise in GAN Training with Variance Reduced Extragradient (2019, methodology): “This strategy has been first introduced for variance reduced methods by Xiao and Zhang (2014) for SVRG and has been discussed for saddle point optimization by Palaniappan and Bach (2016).”
A Variational Inequality Perspective on Generative Adversarial Networks (2018, methodology): “However, since Tseng (1995) works in a very general setting, the bound are not as tight as ours and his proof technique is a bit more technical.”
Revisiting Stochastic Extragradient (2019, background): “In the case where at the optimum the noise is zero, we recover a slight generalization of linear convergence of extragradient (Tseng, 1995).”
Some developments in general variational inequalities (2004, background): “Such type of the proximal methods have been studied extensively in recent years, see for example [25,43,53,62,87,94,107, 126,137] and the reference therein.”
A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Differentiable Games (2020, methodology): “First, taking inspiration from the analysis of GD by Gidel et al. (2019b), we aim at providing a single precise analysis of EG which covers both the bilinear and the strongly monotone settings and their intermediate cases.”
Projected Reflected Gradient Methods for Monotone Variational Inequalities (2015, methodology): “It is well-known (see [19]) that under some suitable conditions the extragradient method has R-linear rate of convergence.”
Tight last-iterate convergence rates for no-regret learning in multi-player games (2020, background): “Moreover, linear last-iterate rates have been long known for smooth strongly-monotone games ([Tse95, GBV + 18, LS18, MOP19b, AMLJG19, ZMM + 20]), a sub-class of λ -cocoercive games.”
On the convergence of single-call stochastic extra-gradient methods (2019, methodology): “…with Lipschitz continuous operators, the last iterate of the method was shown to exhibit a geometric convergence rate [18, 25, 31, 42]; similar geometric convergence results also extend to bilinear saddle-point problems [18, 36, 42], even though the operator involved is not strongly monotone.”