Search Mailing List Archives
[theory-seminar] Theory Lunch 12/10: Tselil Schramm on Sum-of-Squares Algorithms
Dan Michael Stubbs
dstubbs at stanford.edu
Wed Dec 9 12:30:36 PST 2015
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>
More information about the theory-seminar
mailing list