On the One-sided Convergence of Adam-type Algorithms in Non-convex Non-concave Min-max Optimization
arXiv:2109.14213
Abstract
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.
arXiv comment44 pages
References in corpus (16)
- Decoupled Weight Decay Regularization
- Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks
- Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
- ADADELTA: An Adaptive Learning Rate Method
- On the Convergence of Adam and Beyond
- Adaptive Gradient Methods with Dynamic Bound of Learning Rate
- Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning
- Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
- What Can ResNet Learn Efficiently, Going Beyond Kernels?
- On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
- An Alternative View: When Does SGD Escape Local Minima?
- Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets
- Solving Non-Convex Non-Concave Min-Max Games Under Polyak-Łojasiewicz Condition
- The limits of min-max optimization algorithms: convergence to spurious non-critical sets
- Understanding the Generalization of Adam in Learning Neural Networks with Proper Regularization
- Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions