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!

Gregory Valiant gvaliant at
Wed Aug 31 14:31:38 PDT 2016

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


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:

More information about the theory-seminar mailing list