ORIE Colloquium: Volkan Cevher (EPFL) - Limits of Robbins-Monro-type algorithms: From minimization to minimax optimization

Description

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.

To this end, 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:
(i) generically, the algorithms' limit points are contained in the internally chain transitive sets of a common, mean-field system;
(ii) the attractors of this system also attract the algorithms in question with arbitrarily high probability;
(iii) all algorithms avoid the system's unstable sets with probability

While our result provides a highly optimistic outlook for min-max algorithms, we also 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.

The talk will cover the following joint works with Panayotis Mertikopoulos, Ya-Ping Hsieh, Nadav Hallak, and Ali Kavis:
https://arxiv.org/pdf/2006.11144.pdf
https://arxiv.org/pdf/2006.09065.pdf

Bio:
Volkan Cevher received the B.Sc. (valedictorian) in electrical engineering from Bilkent University in Ankara, Turkey, in 1999 and the Ph.D. in electrical and computer engineering from the Georgia Institute of Technology in 2005. He was a research scientist with the University of Maryland, College Park from 2006-2007, and also with Rice University from 2008-2009. Currently, he is an Associate Professor at the Swiss Federal Institute of Technology Lausanne and a Faculty Fellow in the electrical and computer engineering department at Rice University. His research interests include machine learning, signal processing theory, optimization, and information theory. Dr. Cevher is an ELLIS fellow and was the recipient of the Google Faculty Research Award on Machine Learning in 2018, IEEE Signal Processing Society Best Paper Award in 2016, a Best Paper Award at CAMSAP in 2015, a Best Paper Award at SPARS in 2009, and an ERC CG in 2016 as well as an ERC StG in 2011.