Search Mailing List Archives


Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory seminar tomorrow with Tengyu Ma!

Moses Charikar moses at cs.stanford.edu
Thu Sep 1 01:11:01 PDT 2016


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

--Moses

On Wed, Aug 31, 2016 at 2:31 PM, Gregory Valiant <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
> 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/62f7921e/attachment.html>


More information about the theory-seminar mailing list