What is a Good Metric to Study Generalization of Minimax Learners?

Asuman E. Ozdaglar, Sarath Pattathil, Jiawei Zhang, Kaiqing Zhang

Abstract

Minimax optimization has served as the backbone of many machine learning (ML) problems. Although the convergence behavior of optimization algorithms has been extensively studied in the minimax settings, their generalization guarantees in stochastic minimax optimization problems, i.e., how the solution trained on empirical data performs on unseen testing data, have been relatively underexplored. A fundamental question remains elusive: What is a good metric to study generalization of minimax learners? In this paper, we aim to answer this question by first showing that primal risk, a universal metric to study generalization in minimization problems, which has also been adopted recently to study generalization in minimax ones, fails in simple examples. We thus propose a new metric to study generalization of minimax learners: the primal gap, defined as the difference between the primal risk and its minimum over all models, to circumvent the issues. Next, we derive generalization error bounds for the primal gap in nonconvex-concave settings. As byproducts of our analysis, we also solve two open questions: establishing generalization error bounds for primal risk and primal-dual risk, another existing metric that is only well-defined when the global saddle-point exists, in the strong sense, i.e., without strong concavity or assuming that the maximization and expectation can be interchanged, while either of these assumptions was needed in the literature. Finally, we leverage this new metric to compare the generalization behavior of two popular algorithms -- gradient descent-ascent (GDA) and gradient descent-max (GDMax) in stochastic minimax optimization.

Introduction

In standard machine learning (minimization), generalization is straightforward: we want the model's performance on training data to match its performance on unseen data. We usually measure this using "Primal Risk." However, many modern AI problems—like Generative Adversarial Networks (GANs) and adversarial robustness—are minimax problems. They are a "game" between two players: one trying to minimize a loss and another trying to maximize it.

The authors point out a major gap: the standard metric used for minimization (Primal Risk) fails in minimax settings. Specifically, a model can show "good generalization" according to Primal Risk while actually being a terrible model that performs poorly on the real-world population. This happens because the "max-player" (e.g., the discriminator in a GAN) can overfit the training data so severely that the "min-player" (the generator) is led astray.

The Primal Gap: A Robust Metric for Minimax Generalization

To address these shortcomings, the authors introduce the Primal Gap. Unlike Primal Risk, the Primal Gap measures the difference between the current model's risk and the best possible risk across all models. This metric captures the "shift" between the empirical minimizer and the population minimizer, which Primal Risk often misses.

Theoretical Generalization Bounds

The researchers utilize the algorithmic stability framework to derive generalization error bounds. This approach measures how much an algorithm's output changes if you change exactly one data point in the training set. If the output doesn't change much, the algorithm is "stable" and likely to generalize well.

The paper provides concrete mathematical rates for generalization in nonconvex-concave settings (where the minimization part is complex, but the maximization part is well-behaved). For example, they show the Primal Gap bound includes a term $O(1/\sqrt{n})$, where $n$ is the number of samples, scaled by the "empirical capacity" ($C_p$ and $C_e$) of the maximizer.

Comparison of generalization error rates across different metrics and assumptions.

As shown in the table above, this work establishes bounds for the Primal Gap (PG) and improves upon existing bounds for Primal Risk (PR) and Primal-Dual (PD) risk without requiring strong concavity or the interchangeability of maximization and expectation.

Comparing GDA and GDMax

The authors use the Primal Gap to compare two common strategies:

  • GDA (Gradient Descent-Ascent): Both players update simultaneously.
  • GDMax (Gradient Descent-Max): The min-player updates only after the max-player has reached an optimal (or near-optimal) state for the current iteration.

A surprising "aha moment" is that GDMax often generalizes worse than GDA. Because GDMax tries to find the absolute best response for the max-player at every step, it overfits the discriminator to the specific training samples. In GAN experiments on MNIST, GDA produced visually superior images compared to GDMax. They found that the weights (norms) of the discriminator in GDMax exploded to very high values, creating a "steep" discriminator that perfectly distinguishes training points but fails to provide a useful gradient for the generator to learn the general distribution.

Conclusion

This paper identifies a critical flaw in how we measure generalization in minimax optimization and proposes the Primal Gap as a more robust alternative. By leveraging algorithmic stability, the authors provide new theoretical bounds and empirical evidence showing that simultaneous updates (GDA) can act as a form of regularization, leading to better generalization than full maximization (GDMax). Future work could extend this analysis to nonconvex-nonconcave settings and other popular solvers like Extra-Gradient.

Summary updated

Abstract

Minimax optimization has served as the backbone of many machine learning (ML) problems. Although the convergence behavior of optimization algorithms has been extensively studied in the minimax settings, their generalization guarantees in stochastic minimax optimization problems, i.e., how the solution trained on empirical data performs on unseen testing data, have been relatively underexplored. A fundamental question remains elusive: What is a good metric to study generalization of minimax learners? In this paper, we aim to answer this question by first showing that primal risk, a universal metric to study generalization in minimization problems, which has also been adopted recently to study generalization in minimax ones, fails in simple examples. We thus propose a new metric to study generalization of minimax learners: the primal gap, defined as the difference between the primal risk and its minimum over all models, to circumvent the issues. Next, we derive generalization error bounds for the primal gap in nonconvex-concave settings. As byproducts of our analysis, we also solve two open questions: establishing generalization error bounds for primal risk and primal-dual risk, another existing metric that is only well-defined when the global saddle-point exists, in the strong sense, i.e., without strong concavity or assuming that the maximization and expectation can be interchanged, while either of these assumptions was needed in the literature. Finally, we leverage this new metric to compare the generalization behavior of two popular algorithms -- gradient descent-ascent (GDA) and gradient descent-max (GDMax) in stochastic minimax optimization.
BibTeX
@inproceedings{ozdaglar2022what,
  author = {Asuman E. Ozdaglar and Sarath Pattathil and Jiawei Zhang and Kaiqing Zhang},
  title = {{What is a Good Metric to Study Generalization of Minimax Learners?}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=eJiZIS9IMO},
}
Figure