“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:
https://arxiv.org/pdf/2006.11144.pdf
https://arxiv.org/pdf/2006.09065.pdf
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
2011.