Nonconvex Recovery of Low-Complexity Models in Data Science
|Event Date:||January 29, 2019|
|Speaker:||Dr. Qing Qu|
|Speaker Affiliation:||New York University|
|School or Program:||Electrical and Computer Engineering
Dr. Qing Qu
New York University
Nonconvex optimization problems are ubiquitous in a wide range of areas of science and engineering — from representation learning for visual classification, to signal reconstruction of computational imaging systems in biomedical engineering, physics and astronomy. The worst-case theory for nonconvex optimization is dismal: in general, even guaranteeing a local minimum is NP hard. However, in practice heuristic algorithms are often surprisingly effective. The ability of nonconvex heuristics to find high-quality solutions remains largely mysterious.
In this talk, I will present a few 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). These high dimensional problems possess intrinsic low-dimensional structures, in which (i) the energy landscape does not have any ``flat’’ saddle points, and (ii) all the local minima are equivalent “good” target solutions. For each of the aforementioned problems, the benign geometric structure allows us to obtain novel performance guarantees. In the end, I will discuss about implications and extensions of our theory for nonconvex optimization in computational imaging and computational neuroscience.
Qing Qu is a Moore-Sloan research fellow at Center for Data Science, New York University. He received his Ph.D in Oct. 2018 from Columbia University in Electrical Engineering. 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, with focus on developing efficient nonconvex methods and global optimality guarantees for solving engineering problems in signal processing, computational imaging, and machine learning. 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.
Prof. Borja Peleato-Inarrea, firstname.lastname@example.org