Date(s) - 28 Jul 2017
2:00 PM - 4:00 PM
3043 ECpE Building Addition
Title: “When Are Nonconvex Optimization Problems Not Scary?”
Abstract: Nonconvex optimization plays an important role in problem solving across science and engineering. In theory, even guaranteeing a local minimizer is NP-hard. In practice, more often than not, simple iterative methods work surprisingly well in specific applications. In this talk, I will describe a family of nonconvex problems that can be solved to global optimality using simple iterative methods, which are “initialization-free.” This family has the characteristic structure that (1) all local minimizers are global, and (2) all saddle points have non-degenerate Hessians. Examples lying in this family arise from applications such as learning sparsifying basis for signals (aka sparse dictionary learning), and recovery of images from phaseless measurements (aka generalized phase retrieval). In both examples, the benign global structure allows us to derive novel performance guarantees. Completing and enriching this framework is an active research endeavor undertaken by several research communities. The ultimate goal is to enable practitioners to deploy the theory and computational tools with a minimal amount of efforts, paralleling convex analysis and optimization. I will highlight open problems to be tackled to move forward. Joint work with Qing Qu (Columbia) and John Wright (Columbia).
Bio: Ju Sun is a postdoctoral scholar at Stanford University, working with Professor Emmanuel Candes. He received his B. Eng. degree in computer engineering (with a minor in Mathematics) from the National University of Singapore in 2008 (2004-08), and Ph. D. degree from Electrical Engineering of Columbia University in 2016 (2011-16). 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 high-dimensional 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.