The Limits of Min-Max Optimization Algorithms: Convergence to Spurious Non-Critical Sets

Ya-Ping Hsieh, Panayotis Mertikopoulos, Volkan Cevher
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:4337-4348, 2021.

Abstract

Compared to minimization, the min-max optimization 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 this basic setting and characterize the convergence properties of many popular methods in solving non-convex/non-concave problems. In particular, we show that a wide class of state-of-the-art schemes and heuristics may converge with arbitrarily high probability to attractors that are in no way min-max optimal or even stationary. Our work thus points out a potential pitfall among many existing theoretical frameworks, and we corroborate our theoretical claims by explicitly showcasing spurious attractors in simple two-dimensional problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-hsieh21a, title = {The Limits of Min-Max Optimization Algorithms: Convergence to Spurious Non-Critical Sets}, author = {Hsieh, Ya-Ping and Mertikopoulos, Panayotis and Cevher, Volkan}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {4337--4348}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/hsieh21a/hsieh21a.pdf}, url = {https://proceedings.mlr.press/v139/hsieh21a.html}, abstract = {Compared to minimization, the min-max optimization 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 this basic setting and characterize the convergence properties of many popular methods in solving non-convex/non-concave problems. In particular, we show that a wide class of state-of-the-art schemes and heuristics may converge with arbitrarily high probability to attractors that are in no way min-max optimal or even stationary. Our work thus points out a potential pitfall among many existing theoretical frameworks, and we corroborate our theoretical claims by explicitly showcasing spurious attractors in simple two-dimensional problems.} }
Endnote
%0 Conference Paper %T The Limits of Min-Max Optimization Algorithms: Convergence to Spurious Non-Critical Sets %A Ya-Ping Hsieh %A Panayotis Mertikopoulos %A Volkan Cevher %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-hsieh21a %I PMLR %P 4337--4348 %U https://proceedings.mlr.press/v139/hsieh21a.html %V 139 %X Compared to minimization, the min-max optimization 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 this basic setting and characterize the convergence properties of many popular methods in solving non-convex/non-concave problems. In particular, we show that a wide class of state-of-the-art schemes and heuristics may converge with arbitrarily high probability to attractors that are in no way min-max optimal or even stationary. Our work thus points out a potential pitfall among many existing theoretical frameworks, and we corroborate our theoretical claims by explicitly showcasing spurious attractors in simple two-dimensional problems.
APA
Hsieh, Y., Mertikopoulos, P. & Cevher, V.. (2021). The Limits of Min-Max Optimization Algorithms: Convergence to Spurious Non-Critical Sets. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:4337-4348 Available from https://proceedings.mlr.press/v139/hsieh21a.html.

Related Material