Timezone: »

 
Poster
The Limits of Min-Max Optimization Algorithms: Convergence to Spurious Non-Critical Sets
Ya-Ping Hsieh · Panayotis Mertikopoulos · Volkan Cevher

Wed Jul 21 09:00 AM -- 11:00 AM (PDT) @
in Poster Session 3 »

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.

Keywords: Theory

Author Information

Ya-Ping Hsieh (ETH)
Panayotis Mertikopoulos (CNRS and Criteo AI Lab)
Volkan Cevher (EPFL)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors