When Are Nonconvex Problems Not Scary?

Sun Ju - Columbia University
Dec 16 2015 - 2:30pm
Event type: 
224 Fine Hall

General nonconvex optimization problems are NP-hard. In applied disciplines, however, nonconvex problems abound, and heuristic algorithms are often surprisingly effective. The ability of nonconvex heuristics to find high-quality solutions remains largely mysterious.

In this talk, I will describe a family of nonconvex problems which can be solved efficiently. This family has the characteristic structure that every local minimizer recovers the object of interest, and all saddle points are second-order. Natural formulations of a number of important problems in signal processing and machine learning lie in this family, including the eigenvalue problem, complete dictionary learning (DL), generalized phase retrieval (PR), tensor decomposition, linear neural network training.  The nice structure allows design of second-order algorithms that exploits the geometry to escape saddle points and eventually returns a local minimizer. The combination of geometric description and second-order algorithm has lead to new computational guarantees for several practical problems, such as DL and PR.

To complete and enrich the framework is an ongoing research effort. I will highlight challenges from both theoretical and algorithmic sides.

Joint work with Qing Qu and John Wright. An overview article on this is available online:  http://arxiv.org/abs/1510.06096


Ju Sun received his B. Eng. degree in computer engineering (with a minor in Mathematics) from the National University of Singapore in 2008.  He has been working towards a PhD degree in Electrical Engineering of Columbia University since 2011. His research interests lie at the intersection of computer vision, machine learning, numerical optimization, signal/image processing, information theory, and compressive sensing, focused on modeling, harnessing, and computing with low-dimensional structures in massive data, with provable guarantees and practical algorithms. Recently, he is particularly interested in explaining the surprisingly effectiveness of nonconvex optimization heuristics arising in practical problems. He maintains a webpage dedicated to this topic: http://sunju.org/research/nonconvex/ . He won the best student paper award from SPARS'15.