Events Calendar

CS Colloquium: Rong Ge (Duke University) - Avoid Spurious Local Optima: Homotopy Method for Tensor PCA

Speaker: Rong Ge, Duke University

Talk Title: Avoid Spurious Local Optima: Homotopy Method for Tensor PCA

Series: Yahoo! Labs Machine Learning Seminar Series

Abstract: This lecture satisfies requirements for CSCI 591: Computer Science Research Colloquium. Part of Yahoo! Labs Machine Learning Seminar Series.

Recently, several non-convex problems such as tensor decomposition, phase retrieval and matrix completion are shown to have no spurious local minima, which allows them to be solved by very simple local search algorithms. However, more complicated non-convex problems such as the Tensor PCA do have local optima that are not global, and previous results rely on techniques inspired by Sum-of-Squares hierarchy. In this work we show the commonly applied homotopy method, which tries to solve the optimization problem by considering different levels of "smoothing", can be applied to tensor PCA and achieve similar guarantees as the best known Sum-of-Squares algorithms. This is one of the first settings where local search algorithms are guaranteed to avoid spurious local optima even in high dimensions.

This is based on joint work with Yuan Deng (Duke University).

Biography: Rong Ge is an assistant professor at Duke computer science department. He got his Ph.D. in Princeton University and was a post-doc at Microsoft Research New England before joining Duke. Rong Ge is broadly interested in theoretical computer science and machine learning. His research focuses on designing algorithms with provable guarantees for machine learning problems, with applications to topic models, sparse coding and computational biology.

Host: Yan Liu

Location: Henry Salvatori Computer Science Center (SAL) - 101

Audiences: Everyone Is Invited

Contact: Assistant to CS chair