Nonconvex optimization problems are ubiquitous in a wide range of areas of science and engineering — from representation learning for visual classification, to signal/image reconstruction in medical systems, physics and astronomy. The worst case theory for nonconvex optimization is dismal: in general, even guaranteeing a local minimum is NP hard. However, heuristic algorithms are often surprisingly effective in practice. The ability of nonconvex heuristics to find high-quality solutions remains largely mysterious. In this talk, I will present examples of nonconvex problems that can be provably and efficiently solved to global optimum, using simple numerical optimization methods. These include variants of problems of learning sparsifying basis for subspaces (a.k.a. sparse dictionary learning), and image reconstruction from certain types of phaseless measurements (a.k.a. phase retrieval). Those problems possess characteristic structures, in which (i) all local minima are global, (ii) the energy landscape does not have any ``flat’’ saddle points. For each of the aforementioned problems, the benign geometric structure allows us to obtain novel performance guarantees. To enrich the framework is an ongoing research effort, I will discuss several open problems and future directions.
Qing Qu is a Ph.D candidate in Electrical Engineering, Columbia University, working with Prof. John Wright. He received his B.Eng. from Tsinghua University in Jul. 2011, and a M.Sc.from the Johns Hopkins University in Dec. 2012, both in Electrical Engineering. He interned at U.S. Army Research Laboratory in 2012 and Microsoft Research in 2016, respectively. His research interest lies at the intersection of signal/image processing, machine learning, numerical optimization, information theory and compressed sensing, with focus on developing practical algorithms and provable guarantees for many nonconvex problems with low intrinsic structure. He is the recipient of Best Student Paper Award at SPARS’15 (with Ju Sun, John Wright), and the recipient of 2016-18 Microsoft Research Fellowship in North America.