Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities

By Chaobing Song, Zhengyuan Zhou, Yichao Zhou, Yong Jiang, Yi Ma. 2021

54 citations recorded by the source corpus.

The optimization problems associated with training generative adversarial neural networks can be largely reduced to certain {\em non-monotone} variational inequality problems (VIPs), whereas existing convergence results are mostly based on monotone or strongly monotone assumptions. In this paper, we propose {\em optimistic dual extrapolation (OptDE)}, a method that only performs {\em one} gradient evaluation per iteration. We show that OptDE is provably convergent to {\em a strong solution} under different coherent non-monotone assumptions. In particular, when a {\em weak solution} exists, the convergence rate of our method is $O(1/{\epsilon^{2}})$, which matches the best existing result of the methods with two gradient evaluations. Further, when a {\em $\sigma$-weak solution} exists, the convergence guarantee is improved to the linear rate $O(\log\frac{1}{\epsilon})$. Along the way--as a byproduct of our inquiries into non-monotone variational inequalities--we provide the near-optimal $O\big(\frac{1}{\epsilon}\log \frac{1}{\epsilon}\big)$ convergence guarantee in terms of restricted strong merit function for monotone variational inequalities. We also show how our results can be naturally generalized to the stochastic setting, and obtain corresponding new convergence results. Taken together, our results contribute to the broad landscape of variational inequality--both non-monotone and monotone alike--by providing a novel and more practical algorithm with the state-of-the-art convergence guarantees.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, 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 Computer Vision and Pattern Recognition

In Optimization & Training

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, background): “For example, Song et al. [2020] also focuses on quasi-strongly monotone VI but they called them strong coherent VI and show that quasi strong monotonicity is weaker than the strongly pseudo-monotone [Kannan and Shanbhag, 2019] and strongly monotone assumption.”
Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization (2020, methodology): “Very recent (and independent) work of [44] proposed an optimistic dual extrapolation method with linear convergence for a class of problems that have a “strong” ( MVI ) solution (namely, the assumption is that there exists u ∗ ∈ R d such that ∀ u ∈ R d : F ( u ) , u − u ∗ ≥ m u − u ∗ 2 for some…”