[Ml-stat-talks] Fwd: Princeton Optimization Seminar: David Steurer, Cornell University/IAS, TODAY, 4:30PM, Sherrerd 101

Barbara Engelhardt bee at princeton.edu
Thu Nov 17 12:35:14 EST 2016

Talk of interest.

*From:* Optimization Seminar [opt-seminar at Princeton.EDU
<opt-seminar at princeton.edu>] on behalf of Amir Ali Ahmadi [
a_a_a at PRINCETON.EDU <a_a_a at princeton.edu>]
*Sent:* Thursday, November 17, 2016 12:07 PM
*To:* opt-seminar at Princeton.EDU <opt-seminar at princeton.edu>
*Subject:* Princeton Optimization Seminar: David Steurer, Cornell
University/IAS, TODAY, 4:30PM, Sherrerd 101

*-----   **Princeton Optimization Seminar**   -----*

*DATE: TODAY *Thursday, November 17, 2016

*TIME*:  4:30PM

*LOCATION: * Sherrerd Hall 101

*SPEAKER:* David Steurer, Cornell University/Institute for Advanced Study

*TITLE: *Tensor decomposition, sum-of-squares proofs, and spectral

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.

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.

*** If you would like to subscribe to the mailing list of the optimization
seminar series, please visit the link below or send an email with
SUBSCRIBE opt-seminar in the body to listserv at lists.princeton.edu.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/ml-stat-talks/attachments/20161117/2b2b4569/attachment.html>

More information about the Ml-stat-talks mailing list