David Steurer, Cornell University

Tensor Decomposition, Sum-of-Squares Proofs, and Spectral Algorithms
Date
Nov 17, 2016, 4:30 pm5:30 pm
Location
101 - Sherrerd Hall

Details

Event Description

Abstract: The problem of finding low-rank decompositions of tensors has a wide-range applications, e.g., for learning various mixture models. In the overcomplete regime---when the rank is superlinear in the dimension---most known provable decomposition methods for third-order tensors break down.

We describe a polynomial-time algorithm based on the sum-of-squares method that is able to approximately decompose random n-dimensional third-order tensors of rank up to n^{3/2}/polylog n. The previous best algorithm by Ge and Ma also used sum-of-squares but required quasi-polynomial time to achieve such decompositions.

Finally, we demonstrate how to reap the benefits of the sum-of-squares method without solving large semidefinite programs: Using the sum-of-squares toolkit, we devise new kinds of spectral algorithms that achieve similar decomposition guarantees as sum-of-squares but with running times that are close to linear in the size of the input (exponent 1.125 using fast matrix-multiplication).

Based on joint works with Sam Hopkins, Tengyu Ma, Tselil Schramm, and Jonathan Shi.

BIO: David Steurer is an assistant professor in the department of computer science at Cornell University and a visiting assistant professor at the Institute for Advanced Study. He obtained his PhD at Princeton University in 2010 and was a postdoctoral researcher at Microsoft Research New England for two years. He investigates the power and limitations of efficient algorithms for discrete and non-convex optimization problems. His work has made major contributions to the Unique Games Conjecture and the sum-of-squares method, two central developments toward the effort of uncovering a unified theory for efficient optimization. He has received the 2010 FOCS best paper award, the 2011 ACM Doctoral Dissertation Award Honorable Mention, an NSF CAREER Award, an Alfred P. Sloan Research Fellowship, the 2014 Microsoft Research Faculty Fellowship, and the 2015 STOC best paper award.

Event Category
Optimization Seminar