by Y. P. Hsieh, P. Mertikopoulos, V. Cevher

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.

Reference:

The limits of min-max optimization algorithms: Convergence to spurious non-critical sets Y. P. Hsieh, P. Mertikopoulos, V. CevherIn Proc. of Thirty Eighth International Conference on Machine Learning (ICML), 2021

Bibtex Entry:

@inproceedings{hsieh2021limits, author = {Hsieh, Ya-Ping and Mertikopoulos, Panayotis and Cevher, Volkan}, booktitle = {Proc. of Thirty Eighth International Conference on Machine Learning (ICML)}, month = {July}, pages = {4337--4348}, title = {The limits of min-max optimization algorithms: Convergence to spurious non-critical sets}, year = {2021}}