ORIE Colloquium: Volkan Cevher (Swiss Federal Institute of Technology Lausanne), April 20, 2021
From Henry Lam
“Limits of Robbins-Monro-type algorithms: From minimization to minimax optimization”
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 1.
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:
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 Atlanta, GA in
2005. He was a research scientist with the University of Maryland, College Park
from 2006-2007 and also with Rice University in Houston, TX, 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