[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

The University of Chicago
Joint Computer Science & Mathematics
Seminar Presents:
 
Tuesday, March 3, 2014
Ryerson 251@ 3:00 pm
 
Ankur Moitra
M.I.T.
 
Title: “ Tensor Prediction, Rademacher Complexity and Random 3-XOR”
 
Abstract: Here we study the tensor prediction problem, where the goal is to accurately predict the entries of a low rank, third-order tensor (with noise) given as few observations as possible. We give algorithms based on the sixth level of the sum-of-squares hierarchy that work with roughly m = n^3/2 observations, and we complement our result by showing that any attempt to solve tensor prediction with fewer observations through the sum-of-squares hierarchy would run in moderately exponential time. In contrast, information theoretically roughly m = n observations suffice.
 
This work is part of a broader agenda of studying computational vs. statistical tradeoffs through the sum-of-squares hierarchy. In particular, for linear inverse problems (such as tensor prediction) the natural sum-of-squares relaxation gives rise to a sequence of norms. Our approach is to characterize their Rademacher complexity.  Moreover, both our upper and lower bounds are based on connections between this, and the task of strongly refuting random 3-XOR formulas, and the resolution proof system.
 
This talk is based on joint work with Boaz Barak
 
Host by Prof. Madhur Tulsiani
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20150225/81996bcb/attachment-0002.htm 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Ankur.docx
Type: application/vnd.openxmlformats-officedocument.wordprocessingml.document
Size: 202591 bytes
Desc: not available
Url : http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20150225/81996bcb/attachment-0001.bin 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20150225/81996bcb/attachment-0003.htm