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 (11)

• GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Do GANs actually learn the distribution? An empirical study
• Improving Generalization and Stability of Generative Adversarial Networks
• On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games
• Overfitting in adversarially robust deep learning
• High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
• Efficient Algorithms for Smooth Minimax Optimization
• GANs May Have No Nash Equilibria
• Coherent Gradients: An Approach to Understanding Generalization in Gradient Descent-based Optimization
• Newton-type Methods for Minimax Optimization

Cited by in corpus (1)

• Stability and Generalization of Stochastic Gradient Methods for Minimax Problems