Train simultaneously, generalize better: Stability of gradient-based minimax learners

Abstract

The success of minimax learning problems of generative adversarial networks (GANs) has been observed to depend on the minimax optimization algorithm used for their training. This dependence is commonly attributed to the convergence speed and robustness properties of the underlying optimization algorithm. In this paper, we show that the optimization algorithm also plays a key role in the generalization performance of the trained minimax model. To this end, we analyze the generalization properties of standard gradient descent ascent (GDA) and proximal point method (PPM) algorithms through the lens of algorithmic stability under both convex concave and non-convex non-concave minimax settings. While the GDA algorithm is not guaranteed to have a vanishing excess risk in convex concave problems, we show the PPM algorithm enjoys a bounded excess risk in the same setup. For non-convex non-concave problems, we compare the generalization performance of stochastic GDA and GDmax algorithms where the latter fully solves the maximization subproblem at every iteration. Our generalization analysis suggests the superiority of GDA provided that the minimization and maximization subproblems are solved simultaneously with similar learning rates. We discuss several numerical results indicating the role of optimization algorithms in the generalization of the learned minimax models.

References in corpus (38)

• Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks
• GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium
• Spectral Normalization for Generative Adversarial Networks
• Reconciling modern machine learning practice and the bias-variance trade-off
• Which Training Methods for GANs do actually Converge?
• Adversarially Robust Generalization Requires More Data
• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• The generalization error of random features regression: Precise asymptotics and double descent curve
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• The Numerics of GANs
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• A Variational Inequality Perspective on Generative Adversarial Networks
• A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• Do GANs actually learn the distribution? An empirical study
• Rademacher Complexity for Adversarially Robust Generalization
• Uniform convergence may be unable to explain generalization in deep learning
• Adversarially Robust Generalization Just Requires More Unlabeled Data
• Improving Generalization and Stability of Generative Adversarial Networks
• On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games
• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• Generalizable Adversarial Training via Spectral Normalization
• On the Convergence and Robustness of Training GANs with Regularized Optimal Transport
• On the Discrimination-Generalization Tradeoff in GANs
• Overfitting in adversarially robust deep learning
• High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
• Convergence of Learning Dynamics in Stackelberg Games
• Approximability of Discriminators Implies Diversity in GANs
• Generalization Bounds for Uniformly Stable Algorithms
• Efficient Algorithms for Smooth Minimax Optimization
• Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin
• GANs May Have No Nash Equilibria
• Adversarial Risk Bounds via Function Transformation
• Coherent Gradients: An Approach to Understanding Generalization in Gradient Descent-based Optimization
• Implicit competitive regularization in GANs
• Newton-type Methods for Minimax Optimization

Cited by in corpus (1)

• Stability and Generalization of Stochastic Gradient Methods for Minimax Problems