Principled algorithms for finding local minima
Convex optimization is the cornerstone of continuous optimization, but many real problems are nonconvex: deep learning, optimizing drinking water networks, etc. This two part talk explores my work developing efficient algorithms for finding local minima of nonconvex functions.
The first part discusses my work with Yair Carmon, John Duchi and Aaron Sidford, characterizing the computational time required to find approximate local minima. The complexity of minimizing unconstrained convex functions was first characterized by Yudin and Nemirovski, who together proved lower bounds, and Nesterov, who proved upper bounds. Our work is the analog for finding local minima; we give the first 'accelerated' gradient-based methods and almost tight lower bounds for finding approximate local minima.
The second part of this talk focuses on my work with my advisor Yinyu Ye, developing an interior point method (IPM) for optimization problems with nonconvex constraints. We develop an IPM that, by careful initialization and updates of the slack variables, is guaranteed to find a first-order certificate of local infeasibility, local optimality or unboundedness of the (shifted) feasible region. It has the desirable property of avoiding a typical two-phase or penalty method. Comparison on test sets with a state-of-the-art IPM (IPOPT) indicates similar overall performance but much better infeasibility detection.