The limits of min-max optimization algorithms: convergence to spurious non-critical sets

Ya-Ping Hsieh, Panayotis Mertikopoulos, Volkan Cevher

TL;DR

This paper reveals a fundamental limitation of many popular min-max optimization algorithms: they can converge to "spurious attractors" that are not optimal or even stationary points of the problem. This means that even with high probability, these algorithms might get stuck in suboptimal solutions, a phenomenon not seen in standard function minimization.

What Problem Does This Paper Address?

Min-max optimization problems, common in areas like generative adversarial networks (GANs) and robust reinforcement learning, are notoriously difficult. Unlike standard function minimization where algorithms typically converge to critical points (like minima), min-max problems can exhibit complex behaviors like periodic cycles. While these issues are somewhat understood in simpler, convex settings, the authors tackle the much harder problem of understanding convergence in general non-convex and non-concave min-max scenarios. They aim to answer: "Where do these algorithms actually end up?"

Methods

The authors introduce a unified framework based on the Robbins-Monro (RM) template, a general form for iterative algorithms. They then leverage the Ordinary Differential Equation (ODE) method from stochastic approximation to analyze the "mean dynamics" of these algorithms. This allows them to prove that:

  1. Algorithms converge to "internally chain-transitive" (ICT) sets of the mean dynamics.
  2. They converge with high probability to attractors of these dynamics.
  3. They avoid unstable invariant sets with probability 1.

Crucially, they then show that for min-max problems, these ICT sets and attractors can be "spurious," meaning they don't contain any stationary points of the original min-max problem.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and illustrative examples rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Spurious Attractors are Inescapable: The most striking finding is that many min-max algorithms can get trapped in limit cycles or other non-critical sets, even when better solutions exist. This is a fundamental difference from standard minimization.
  • Min-Max Dynamics are Richer (and Trickier): The "mean dynamics" of min-max problems can be far more complex than those of minimization problems. They can exhibit periodic orbits and other behaviors that don't have direct counterparts in minimization.
  • "Avoiding Unstable Points" Isn't Enough: In minimization, avoiding unstable critical points often implies convergence to stable ones. In min-max, an algorithm might avoid an unstable point but still get stuck in a stable, but spurious, attractor.
  • Bilinear Games Aren't Always Representative: The paper suggests that simple bilinear games, often used as testbeds, might not fully capture the complexities of more general min-max problems, as some mitigation strategies that work for bilinear games might fail in broader settings.

Key Results

  • Generality of Convergence: The paper establishes that a broad class of first- and zeroth-order min-max optimization algorithms (including SGDA, proximal point methods, extra-gradient schemes, and their variants) converge to internally chain-transitive (ICT) sets of the underlying mean dynamics.
  • High-Probability Attraction: These algorithms are shown to converge with high probability to attractors of the mean dynamics.
  • Avoidance of Unstable Sets: With probability 1, these algorithms avoid the unstable invariant sets of the mean dynamics.
  • Demonstration of Spurious Attractors: The authors provide concrete, simple examples (almost bilinear problems) where these algorithms demonstrably converge to spurious attractors that do not contain any stationary points of the min-max problem.

Limitations and Future Work

  • Theoretical Focus: The paper is primarily theoretical, providing a framework and proofs for convergence properties. While illustrative examples are given, extensive empirical validation on large-scale problems like GANs is left for future work.
  • Hyperparameter Sensitivity: The analysis often relies on specific step-size schedules (e.g., diminishing step-sizes). The behavior of algorithms with constant or adaptive step-sizes is discussed but not fully analyzed within the main theoretical framework.
  • Practical Implications for GANs: The authors acknowledge that their findings are a "cautionary tale" and don't definitively explain all failures in GAN training, but they suggest that these convergence issues are an important factor to consider.
  • Future Directions: The paper implicitly suggests exploring new algorithmic designs that can reliably escape spurious attractors or guarantee convergence to desirable solutions in non-convex min-max settings. Investigating the behavior of adaptive methods and second-order methods in more detail is also highlighted.

Summary updated

Abstract

Compared to ordinary function minimization problems, min-max optimization algorithms encounter far greater challenges because of the existence of periodic cycles and similar phenomena. Even though some of these behaviors can be overcome in the convex-concave regime, the general case is considerably more difficult. On that account, we take an in-depth look at a comprehensive class of state-of-the art algorithms and prevalent heuristics in non-convex / non-concave problems, and we establish the following general results: a) generically, the algorithms' limit points are contained in the ICT sets of a common, mean-field system; b) the attractors of this system also attract the algorithms in question with arbitrarily high probability; and c) all algorithms avoid the system's unstable sets with probability 1. On the surface, this provides a highly optimistic outlook for min-max algorithms; however, we show that there exist spurious attractors that do not contain any stationary points of the problem under study. In this regard, our work suggests that existing min-max algorithms may be subject to inescapable convergence failures. We complement our theoretical analysis by illustrating such attractors in simple, two-dimensional, almost bilinear problems.
BibTeX
@inproceedings{hsieh2021limits,
  author = {Ya-Ping Hsieh and Panayotis Mertikopoulos and Volkan Cevher},
  title = {{The limits of min-max optimization algorithms: convergence to spurious non-critical sets}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=ybSptmjUYBa},
}
Figure