TITLE: " Taming nonconvexity: from smooth to nonsmooth problems”
Abstract: Many problems arising from scientific and engineering applications can be naturally formulated as optimization problems, most of which are nonconvex. For nonconvex problems, obtaining a local minimizer is computationally hard in theory, never mind the global minimizer. In practice, however, simple numerical methods often work surprisingly well in finding high-quality solutions (e.g., training deep neural networks). In this talk, I will describe our recent effort in bridging the mysterious theory-practice gap for nonconvex optimization. I will highlight a family of smooth nonconvex problems that can be solved to global optimality using simple numerical methods, independent of initialization. This covers a number of central problems in signal processing, machine learning, and scientific imaging. However, the existing theory pertains only to smooth problems. In modern applications, nonsmooth functions or sets are frequently used to encode structural objects (e.g., sparsity) or achieve robustness. I will continue by introducing tools from nonsmooth analysis, and demonstrate that nonsmooth, nonconvex problems can be analyzed and solved in a provable manner, with little additional technicalities.
The talk is based on joint work with John Wright (Columbia), Qing Qu (NYU), Yu Bai (Stanford), Qijia Jiang (Stanford), Emmanuel Candes (Stanford).
Main References: When Are Nonconvex Problems Not Scary? https://arxiv.org/abs/1510.06096
Subgradient Descent Learns Orthogonal Dictionaries https://arxiv.org/abs/1810.10702
Biography: Ju Sun is a postdoctoral scholar at Stanford University, working with Professor Emmanuel Candѐs. Prior to this, he received his Ph.D. degree from Electrical Engineering of Columbia University in 2016 (2011--2016) and B.Eng. degree in computer engineering (with a minor in Mathematics) from the National University of Singapore in 2008 (2004--2008). His research interests span 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 high-dimensional data, with practical algorithms and correctness guarantees. Recently, he is particularly fascinated by why simple methods often work surprisingly well on solving nonconvex problems in practice, on which he maintains a bibliographic webpage: http://sunju.org/research/nonconvex/ . He won the best student paper award from SPARS'15 and honorable mention of doctoral thesis for the New World Mathematics Awards (NWMA) 2017. SINE Seminar for Monday, November 5, 4 p.m. in 141 CSL. Speaker is Ju Sun of Stanford University. Title, abstract and bio forthcoming. Watch here for future details.