%0 Journal Article %1 hsieh2020limits %A Hsieh, Ya-Ping %A Mertikopoulos, Panayotis %A Cevher, Volkan %D 2020 %K convergence game-theory optimization readings %T The limits of min-max optimization algorithms: convergence to spurious non-critical sets %U http://arxiv.org/abs/2006.09065 %X Compared to minimization problems, the min-max landscape in machine learning applications is considerably more convoluted because of the existence of cycles and similar phenomena. Such oscillatory behaviors are well-understood in the convex-concave regime, and many algorithms are known to overcome them. In this paper, we go beyond the convex-concave setting and we characterize the convergence properties of a wide class of zeroth-, first-, and (scalable) second-order methods in non-convex/non-concave problems. In particular, we show that these state-of-the-art min-max optimization algorithms may converge with arbitrarily high probability to attractors that are in no way min-max optimal or even stationary. Spurious convergence phenomena of this type can arise even in two-dimensional problems, a fact which corroborates the empirical evidence surrounding the formidable difficulty of training GANs.

@article{hsieh2020limits, abstract = {Compared to minimization problems, the min-max landscape in machine learning applications is considerably more convoluted because of the existence of cycles and similar phenomena. Such oscillatory behaviors are well-understood in the convex-concave regime, and many algorithms are known to overcome them. In this paper, we go beyond the convex-concave setting and we characterize the convergence properties of a wide class of zeroth-, first-, and (scalable) second-order methods in non-convex/non-concave problems. In particular, we show that these state-of-the-art min-max optimization algorithms may converge with arbitrarily high probability to attractors that are in no way min-max optimal or even stationary. Spurious convergence phenomena of this type can arise even in two-dimensional problems, a fact which corroborates the empirical evidence surrounding the formidable difficulty of training GANs.}, added-at = {2020-07-16T13:27:58.000+0200}, author = {Hsieh, Ya-Ping and Mertikopoulos, Panayotis and Cevher, Volkan}, biburl = {https://www.bibsonomy.org/bibtex/223ba493c75f73387b1dd5df393d049e4/kirk86}, description = {[2006.09065] The limits of min-max optimization algorithms: convergence to spurious non-critical sets}, interhash = {df7e46f564564ca025c4b3d1c0cad681}, intrahash = {23ba493c75f73387b1dd5df393d049e4}, keywords = {convergence game-theory optimization readings}, note = {cite arxiv:2006.09065}, timestamp = {2020-07-16T13:27:58.000+0200}, title = {The limits of min-max optimization algorithms: convergence to spurious non-critical sets}, url = {http://arxiv.org/abs/2006.09065}, year = 2020 }