[theory-seminar] Theory Lunch 12/10: Tselil Schramm on Sum-of-Squares Algorithms

[Dan Michael Stubbs]

Tomorrow, Thursday December 10, we will have the last theory lunch of the quarter and year.  The speaker is Tselil Schramm from Berkeley.  Food around 12:15, talk begins at 12:30.


Be there!

-Dan


--------------------------------------------------------

Title:
Overcomplete Tensor Decomposition: Speeding up Sum-of-Squares Algorithms

Abstract:
Recently, there has been some success in using the sum-of-squares
hierarchy to solve classical problems in machine learning. However,
the sum-of-squares algorithms are very slow, making them impractical
for the machine learning setting. In this talk I will show that ideas
from sum-of-squares rounding schemes can be used to obtain fast,
spectral algorithms. I will focus on the problem of decomposing an
overcomplete low-rank random tensor into rank-1 components, showing
that ideas from the quasi-polynomial sum-of-squares algorithm can be
adapted to achieve similar performance in subquadratic time.

Based on joint work with Sam Hopkins, Jonathan Shi and David Steurer.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20151209/b333f5cb/attachment.html>