IDeAS Seminar: The effectiveness of nonconvex optimization in two problems

Wed, Mar 8, 2017, 2:30 pm

Many information and data science applications involve computation of the maximum likelihood estimates (MLE) over a high-dimensional space. Unfortunately, most MLEs are solutions to non-convex problems, which are in general intractable. 

Fortunately, some of the problems are not as hard as they may seem, and can be solved by optimizing the nonconvex objectives directly.  This talk illustrates this observation through two problems: (1) solving a random quadratic system of equations, which spans many applications ranging from the century-old phase retrieval problem to various latent-variable models in machine learning;  (2) recovering a collection of discrete variables from noisy pairwise differences, which arises when one wishes to jointly align multiple images or to retrieve the genome phases from paired sequencing reads. In both cases, the proposed solutions can be accomplished within linear time, while achieving a statistical accuracy that is nearly un-improvable.

This is based on joint work with Emmanuel Candes.

Yuxin Chen is currently an assistant professor in the Department of Electrical Engineering at Princeton University. Prior to joining Princeton, he was a postdoctoral scholar in the Department of Statistics at Stanford University, and he completed his Ph.D. in Electrical Engineering at Stanford University. His research interests include high-dimensional structured estimation, convex and nonconvex optimization, statistical learning, and information theory.

Fine Hall 224
Event category: 

Upcoming Events

Prof. Afonso Bandeira, ETH Zurich

Mon, Sep 11, 2023, 4:30 pm
Location: 214 Fine Hall

Prof. Jonathan Pillow, Princeton University

Mon, Sep 18, 2023, 4:30 pm
Location: 214 Fine Hall

No PACM Colloquium scheduled on this day-Yom Kippur

Mon, Sep 25, 2023, 4:30 pm
Location: 214 Fine Hall