Tensor Prediction, Rademacher Complexity and Random 3-XOR

Boaz Barak, Ankur Moitra

Published 2015-01-26Version 1

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 $m = \tilde{O}(n^{3/2})$ observations, and we complement our result by showing that any attempt to solve tensor prediction with $m = O(n^{3/2 - \epsilon})$ observations through the sum-of-squares hierarchy needs $\Omega(n^{2 \epsilon})$ rounds and consequently would run in moderately exponential time. In contrast, information theoretically $m = \tilde{O}(n)$ observations suffice. Our approach is to characterize the Rademacher complexity of the sequence of norms that arise from the sum-of-squares hierarchy, and both our upper and lower bounds are based on establishing connections between tensor prediction and the task of strongly refuting random $3$-XOR formulas, and the resolution proof system.