On the convergence of single-call stochastic extra-gradient methods

By Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, Panayotis Mertikopoulos. 2019

189 citations recorded by the source corpus.

Variational inequalities have recently attracted considerable interest in machine learning as a flexible paradigm for models that go beyond ordinary loss function minimization (such as generative adversarial networks and related deep learning systems). In this setting, the optimal $\mathcal{O}(1/t)$ convergence rate for solving smooth monotone variational inequalities is achieved by the Extra-Gradient (EG) algorithm and its variants. Aiming to alleviate the cost of an extra gradient step per iteration (which can become quite substantial in deep learning applications), several algorithms have been proposed as surrogates to Extra-Gradient with a \emph{single} oracle call per iteration. In this paper, we develop a synthetic view of such algorithms, and we complement the existing literature by showing that they retain a $\mathcal{O}(1/t)$ ergodic convergence rate in smooth, deterministic problems. Subsequently, beyond the monotone deterministic case, we also show that the last iterate of single-call, \emph{stochastic} extra-gradient methods still enjoys a $\mathcal{O}(1/t)$ local convergence rate to solutions of \emph{non-monotone} variational inequalities that satisfy a second-order sufficient condition.

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 Hamiltonian Gradient Methods for Smooth Games (2020, background): “It is only very recently that last-iterate convergence guarantees over a non-compact domain appeared in literature for the stochastic problem (Palaniappan & Bach, 2016; Chavdarova et al., 2019; Hsieh et al., 2019; Mishchenko et al., 2020) under the assumption of strong monotonicity.”
Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence (2020, methodology): “A different line of work focused on reducing the number of gradient computation to one per iteration (Popov 1980; Gidel et al. 2019; Hsieh et al. 2019; Chambolle and Pock 2011; Malit-sky 2015; Cui and Shanbhag 2016; Daskalakis et al. 2018; Mokhtari, Ozdaglar, and Pattathil 2020).”
Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities (2021, methodology): “Consequently, after the (twocall) extragradient method [22], several single-call extragradient methods [35, 3, 6, 27] have been analyzed under the monotone setting and share the same convergence rates with Mirror-Prox and dual extrapolation [17].”
Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling (2020, background): “Results for single-call [9, 16] and non-extragradient methods [14, 17, 30] are not included.”
Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems (2020, background): “Many existing work [8, 9, 12, 13, 18, 28, 33, 34, 41, 45, 48, 50, 52] focused on the convex-concave case of problem (1), where f is convex in x and concave in y.”
Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems (2020, methodology): “Hsieh et al. (2019) proved local linear convergence rates of OGDA to local saddle points in the neighborhood of which f is strongly convex-strongly concave.”