Train simultaneously, generalize better: Stability of gradient-based minimax learners
This addresses the challenge of improving generalization in minimax optimization for machine learning practitioners, though it is incremental as it builds on existing algorithmic stability analysis.
The paper tackles the problem of how optimization algorithms affect the generalization performance of minimax learners, such as GANs, by analyzing gradient descent ascent (GDA) and proximal point method (PPM) algorithms. It shows that PPM enjoys bounded excess risk in convex-concave settings, and in non-convex non-concave problems, GDA generalizes better when subproblems are solved simultaneously with similar learning rates.
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.