# On the One-sided Convergence of Adam-type Algorithms in Non-convex Non-concave Min-max Optimization

arXiv: https://arxiv.org/abs/2109.14213 · HTML: https://mlsanity.com/paper/2109.14213/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 49 references that are in the map.
- First posted on arXiv 29 Sep 2021.

## Builds on (most cited first, 24 of 24)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks](https://mlsanity.com/paper/1511.06434/) (2015)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning](https://mlsanity.com/paper/2012.09816/) (2020)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Adaptive Gradient Methods with Dynamic Bound of Learning Rate](https://mlsanity.com/paper/1902.09843/) (2019)
- [On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization](https://mlsanity.com/paper/1808.02941/) (2018)
- [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [Convergence Analysis of Two-layer Neural Networks with ReLU Activation](https://mlsanity.com/paper/1705.09886/) (2017)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [An Alternative View: When Does SGD Escape Local Minima?](https://mlsanity.com/paper/1802.06175/) (2018)
- [Feature Purification: How Adversarial Training Performs Robust Deep Learning](https://mlsanity.com/paper/2005.10190/) (2020)
- [On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization](https://mlsanity.com/paper/1808.05671/) (2018)
- [What Can ResNet Learn Efficiently, Going Beyond Kernels?](https://mlsanity.com/paper/1905.10337/) (2019)
- [Negative Momentum for Improved Game Dynamics](https://mlsanity.com/paper/1807.04740/) (2018)
- [Variants of RMSProp and Adagrad with Logarithmic Regret Bounds](https://mlsanity.com/paper/1706.05507/) (2017)
- [The limits of min-max optimization algorithms: convergence to spurious non-critical sets](https://mlsanity.com/paper/2006.09065/) (2020)
- [Understanding the Generalization of Adam in Learning Neural Networks with Proper Regularization](https://mlsanity.com/paper/2108.11371/) (2021)
- [Extragradient method with variance reduction for stochastic variational inequalities](https://mlsanity.com/paper/1703.00260/) (2017)
- [On the Convergence Properties of Non-Euclidean Extragradient Methods for Variational Inequalities with Generalized Monotone Operators](https://mlsanity.com/paper/1311.2776/) (2013)
- [Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets](https://mlsanity.com/paper/1912.11940/) (2019)
- [Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions](https://mlsanity.com/paper/2106.02619/) (2021)

## Built on by (most cited first, 9 of 9)

- [Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization](https://mlsanity.com/paper/2206.00743/) (2022)
- [Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guarantees](https://mlsanity.com/paper/2110.03313/) (2021)
- [Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave Minimax Optimization](https://mlsanity.com/paper/2212.12978/) (2022)
- [Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey](https://mlsanity.com/paper/2208.13592/) (2022)
- [Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities](https://mlsanity.com/paper/2302.07615/) (2023)
- [On Scaled Methods for Saddle Point Problems](https://mlsanity.com/paper/2206.08303/) (2022)
- [Regularized Gradient Clipping Provably Trains Wide and Deep Neural Networks](https://mlsanity.com/paper/2404.08624/) (2024)
- [Diffusion Stochastic Optimization for Min-Max Problems](https://mlsanity.com/paper/2401.14585/) (2024)
- [Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum](https://mlsanity.com/paper/2406.13041/) (2024)

## Abstract (arXiv)

Adam-type methods, the extension of adaptive gradient methods, have shown great performance in the training of both supervised and unsupervised machine learning models. In particular, Adam-type optimizers have been widely used empirically as the default tool for training generative adversarial networks (GANs). On the theory side, however, despite the existence of theoretical results showing the efficiency of Adam-type methods in minimization problems, the reason of their wonderful performance still remains absent in GAN's training. In existing works, the fast convergence has long been considered as one of the most important reasons and multiple works have been proposed to give a theoretical guarantee of the convergence to a critical point of min-max optimization algorithms under certain assumptions. In this paper, we firstly argue empirically that in GAN's training, Adam does not converge to a critical point even upon successful training: Only the generator is converging while the discriminator's gradient norm remains high throughout the training. We name this one-sided convergence. Then we bridge the gap between experiments and theory by showing that Adam-type algorithms provably converge to a one-sided first order stationary points in min-max optimization problems under the one-sided MVI condition. We also empirically verify that such one-sided MVI condition is satisfied for standard GANs after trained over standard data sets. To the best of our knowledge, this is the very first result which provides an empirical observation and a strict theoretical guarantee on the one-sided convergence of Adam-type algorithms in min-max optimization.