The limits of min-max optimization algorithms: convergence to spurious
  non-critical sets
  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.
