Search Mailing List Archives
[theory-seminar] Theory seminar tomorrow with Tengyu Ma!
Weihao Kong
whkong at stanford.edu
Thu Sep 1 15:11:50 PDT 2016
In 1 hour!
On Sep 1, 2016, at 1:11 AM, Moses Charikar <moses at cs.stanford.edu<mailto:moses at cs.stanford.edu>> wrote:
Tengyu will be around most of the day. If you would like to meet with him,
send him email to coordinate: tengyu at cs.princeton.edu<mailto:tengyu at cs.princeton.edu>
--Moses
On Wed, Aug 31, 2016 at 2:31 PM, Gregory Valiant <gvaliant at cs.stanford.edu<mailto:gvaliant at cs.stanford.edu>> wrote:
Hi Friends,
Tomorrow will be our first theory seminar of the year, with Tengyu Ma
from Princeton.
Time/Location: THursday 9/1, 4pm Gates 463a.
Title: Polynomial-time tensor decompositions with sum-of-squares
Abstract:
Tensor decompositions have been the key algorithmic components in
provable learning of a wide range of hidden variable models such as
topic models, Gaussian mixture models, independent component analysis,
dictionary learning. One of the challenges in this area is to
decompose over-complete low-order tensors robustly.
In this talk I will present new algorithms based on the sum-of-squares
method for tensor decomposition. Our results improve the best known
running times from quasi-polynomial to polynomial for several
problems, including decomposing random overcomplete 3-tensors and
learning overcomplete dictionaries with constant relative sparsity. We
also give the first robust analysis for decomposing overcomplete
4-tensors in the smoothed analysis model.
A key ingredient of our analysis is to establish small spectral gaps
in moment matrices derived from solutions to sum-of-squares
relaxations. To enable this analysis we augment sum-of-squares
relaxations with spectral analogs of maximum entropy constraints.
Based on joint work with Jonathan Shi and David Steurer.
--------
Theory seminar calendar here: http://theory.stanford.edu/~aflb/2015-16.html
_______________________________________________
theory-seminar mailing list
theory-seminar at lists.stanford.edu<mailto:theory-seminar at lists.stanford.edu>
https://mailman.stanford.edu/mailman/listinfo/theory-seminar
_______________________________________________
theory-seminar mailing list
theory-seminar at lists.stanford.edu<mailto:theory-seminar at lists.stanford.edu>
https://mailman.stanford.edu/mailman/listinfo/theory-seminar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20160901/80c4f631/attachment.html>
More information about the theory-seminar
mailing list