Golden ratio algorithms for variational inequalities

By Yura Malitsky. Mathematical programming, 2018

299 citations recorded by the source corpus.

The paper presents a fully adaptive algorithm for monotone variational inequalities. In each iteration the method uses two previous iterates for an approximation of the local Lipschitz constant without running a linesearch. Thus, every iteration of the method requires only one evaluation of a monotone operator F and a proximal mapping g. The operator F need not be Lipschitz continuous, which also makes the algorithm interesting in the area of composite minimization. The method exhibits an ergodic O(1 / k) convergence rate and R-linear rate under an error bound condition. We discuss possible applications of the method to fixed point problems as well as its different generalizations.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/6196c19d536b616d0d246d0597dba0b3a2785bd1

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

Citations in the corpus

ODE Analysis of Stochastic Gradient Methods with Optimism and Anchoring for Minimax Problems and GANs (2019, unknown): “Although the recent name ‘optimism’ originates from its use in online optimization [6, 55, 56, 62], the idea dates back to Popov’s work in the 1980s [53] and has been studied independently in the mathematical programming community [35, 32, 34, 33, 7].”
Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling (2020, background): “For some τ > 0 and all x ∈ R d , we have This kind of error bound is standard in the literature on variational inequalities for deriving last iterate convergence rates [see e.g., 7, 19, 20, 37, 38].”
On the convergence of single-call stochastic extra-gradient methods (2019, background): “First, given the extensive literature on the subject, this list is not exhaustive; see e.g., [30, 31, 36] for a generalization of (OG), [26] for a variant that employs averaging to update the algorithm’s base state X t , and [19] for a proxy deﬁned via “negative momentum”.”
Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization (2020, methodology): “The condition that we impose on F that enables our convergence results differs from the strong assumption that a solution to ( MVI ) exists [32, 36, 44, 49], an assumption which is satisﬁed by several interesting families, including quasiconvex-concave families or starconvex-concave families.”