Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets

Abstract

Adaptive gradient algorithms perform gradient-based updates using the history of gradients and are ubiquitous in training deep neural networks. While adaptive gradient methods theory is well understood for minimization problems, the underlying factors driving their empirical success in min-max problems such as GANs remain unclear. In this paper, we aim at bridging this gap from both theoretical and empirical perspectives. First, we analyze a variant of Optimistic Stochastic Gradient (OSG) proposed in~\citep{daskalakis2017training} for solving a class of non-convex non-concave min-max problem and establish $O({\epsilon }^{-4})$ complexity for finding $\epsilon$-first-order stationary point, in which the algorithm only requires invoking one stochastic first-order oracle while enjoying state-of-the-art iteration complexity achieved by stochastic extragradient method by~\citep{iusem2017extragradient}. Then we propose an adaptive variant of OSG named Optimistic Adagrad (OAdagrad) and reveal an \emph{improved} adaptive complexity $O\left({\epsilon }^{-\frac{2}{1-\alpha }}\right)$, where $\alpha$ characterizes the growth rate of the cumulative stochastic gradient and $0\le \alpha \le 1/2$. To the best of our knowledge, this is the first work for establishing adaptive complexity in non-convex non-concave min-max optimization. Empirically, our experiments show that indeed adaptive gradient algorithms outperform their non-adaptive counterparts in GAN training. Moreover, this observation can be explained by the slow growth rate of the cumulative stochastic gradient, as observed empirically.

arXiv commentAccepted by ICLR 2020

References in corpus (16)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium
• Large Scale GAN Training for High Fidelity Natural Image Synthesis
• Spectral Normalization for Generative Adversarial Networks
• Self-Attention Generative Adversarial Networks
• On the Convergence of Adam and Beyond
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• The Numerics of GANs
• A Variational Inequality Perspective on Generative Adversarial Networks
• Optimization, Learning, and Games with Predictable Sequences
• On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games
• Reducing Noise in GAN Training with Variance Reduced Extragradient
• Stochastic AUC Maximization with Deep Neural Networks
• A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise
• Solving Non-Convex Non-Concave Min-Max Games Under Polyak-Łojasiewicz Condition
• On the Convergence of (Stochastic) Gradient Descent with Extrapolation for Non-Convex Optimization

Cited by in corpus (11)

• On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization
• Adaptive Temporal Difference Learning with Linear Function Approximation
• A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems
• Minimax Problems with Coupled Linear Constraints: Computational Complexity, Duality and Solution Methods
• On the One-sided Convergence of Adam-type Algorithms in Non-convex Non-concave Min-max Optimization
• Complex Momentum for Optimization in Games
• Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Optimization