Noisy Tensor Completion via the Sum-of-Squares Hierarchy

Introduction

Matrix completion is one of the cornerstone problems in machine learning and has a diverse range of applications. One of the original motivations for it comes from the Netflix Problem where the goal is to predict user-movie ratings based on all the ratings we have observed so far, from across many different users. We can organize this data into a large, partially observed matrix where each row represents a user and each column represents a movie. The goal is to fill in the missing entries. The usual assumptions are that the ratings depend on only a few hidden characteristics of each user and movie and that the underlying matrix is approximately low rank. Another standard assumption is that it is incoherent, which we elaborate on later. How many entries of $M$ do we need to observe in order to fill in its missing entries? And are there efficient algorithms for this task?

There have been thousands of papers on this topic and by now we have a relatively complete set of answers. A representative result (building on earlier works by Fazel , Recht, Fazel and Parrilo , Srebro and Shraibman , Candes and Recht , Candes and Tao ) due to Keshavan, Montanari and Oh can be phrased as follows: Suppose $M$ is an unknown $n_{1}\times n_{2}$ matrix that has rank $r$ but each of its entries has been corrupted by independent Gaussian noise with standard deviation $\delta$. Then if we observe roughly

of its entries, the locations of which are chosen uniformly at random, there is an algorithm that outputs a matrix $X$ that with high probability satisfies

There are extensions to non-uniform sampling models , as well as various efficiency improvements . What is particularly remarkable about these guarantees is that the number of observations needed is within a logarithmic factor of the number of parameters — $(n_{1}+n_{2})r$ — that define the model.

In fact, there are benefits to working with even higher-order structure but so far there has been little progress on natural extensions to the tensor setting. To motivate this problem, consider the Groupon Problem (which we introduce here to illustrate this point) where the goal is to predict user-activity ratings. The challenge is that which activities we should recommend (and how much a user liked a given activity) depends on time as well — weekday/weekend, day/night, summer/fall/winter/spring, etc. or even some combination of these. As above, we can cast this problem as a large, partially observed tensor where the first index represents a user, the second index represents an activity and the third index represents the time period. It is again natural to model it as being close to low rank, under the assumption that a much smaller number of (latent) factors about the interests of the user, the type of activity and the time period should contribute to the rating. How many entries of the tensor do we need to observe in order to fill in its missing entries? This problem is emblematic of a larger issue: Can we always solve linear inverse problems when the number of observations is comparable to the number of parameters in the mode, or is computational intractability an obstacle?

In fact, one of the advantages of working with tensors is that their decompositions are unique in important ways that matrix decompositions are not. There has been a groundswell of recent work that uses tensor decompositions for exactly this reason for parameter learning in phylogenetic trees , HMMs , mixture models , topic models and to solve community detection . In these applications, one assumes access to the entire tensor (up to some sampling noise). But given that the underlying tensors are low-rank, can we observe fewer of their entries and still utilize tensor methods?

A wide range of approaches to solving tensor completion have been proposed . However, in terms of provable guarantees noneMost of the existing approaches rely on computing the tensor nuclear norm, which is hard to compute . The only other algorithms we are aware of require that the factors be orthogonal. This is a rather strong assumption. First, orthogonality requires the rank to be at most $n$. Second, even when $r\leq n$, most tensors need to be “whitened” to be put in this form and then a random sample from the “whitened” tensor would correspond to a (dense) linear combination of the entries of the original tensor, which would be quite a different sampling model. of them improve upon the following näive algorithm. If the unknown tensor $T$ is $n_{1}\times n_{2}\times n_{3}$ we can treat it as a collection of $n_{1}$ matrices each of size $n_{2}\times n_{3}$. It is easy to see that if $T$ has rank at most $r$ then each of these slices also has rank at most $r$ (and they inherit incoherence properties as well). By treating a third-order tensor as nothing more than an unrelated collection of $n_{1}$ low-rank matrices, we can complete each slice separately using roughly $m=n_{1}(n_{2}+n_{3})r\log(n_{2}+n_{3})$ observations in total. When the rank is constant, this is a quadratic number of observations even though the number of parameters in the model is linear.

Here we show how to solve the (noisy) tensor completion problem with many fewer observations. Let $n_{1}\leq n_{2}\leq n_{3}$. We give an algorithm based on the sixth level of the sum-of-squares hierarchy that can accurately fill in the missing entries of an unknown, incoherent $n_{1}\times n_{2}\times n_{3}$ tensor $T$ that is entry-wise close to being rank $r$ with roughly

observations. Moreover, our algorithm works even when the observations are corrupted by noise. When $n=n_{1}=n_{2}=n_{3}$, this amounts to about $n^{1/2}r$ observations per slice which is much smaller than what we would need to apply matrix completion on each slice separately. Our algorithm needs to leverage the structure between the various slices.

We give an algorithm for noisy tensor completion that works for third-order tensors. Let $T$ be a third-order $n_{1}\times n_{2}\times n_{3}$ tensor that is entry-wise close to being low rank. In particular let

Let $\Omega$ represent the locations of the entries that we observe, which (as is standard) are chosen uniformly at random and without replacement. Set $|\Omega|=m$. Our goal is to output a hypothesis $X$ that has small entry-wise error, defined as:

This measures the error on both the observed and unobserved entries of $T$. Our goal is to give algorithms that achieve vanishing error, as the size of the problem increases. Moreover we will want algorithms that need as few observations as possible. Here and throughout let $n_{1}\leq n_{2}\leq n_{3}$ and $n=\max\{n_{1},n_{2},n_{3}\}$. Our main result is:

provided that $\max_{i,j,k}|\Delta_{i,j,k}|\leq\sqrt{\frac{m}{\log 2/\epsilon}}\delta$.

Further, suppose that for a $1-o(1)$ fraction of the entries of $T$, we have $\operatorname{var}(T_{i,j,k})\geq r/\operatorname{polylog}(n)=V$ and that $\Delta$ is a tensor where each entry is a Gaussian with mean zero and variance $o(V)$. Then there is a polynomial time algorithm that outputs a hypothesis $X$ that satisfies

We believe that this work is a natural first step in designing practically efficient algorithms for tensor completion. Our algorithms manage to leverage the structure across the slices through the tensor, instead of treating each slice as an independent matrix completion problem. Now that we know this is possible, a natural follow-up question is to get more efficient algorithms. Our algorithms are based on the sixth level of the sum-of-squares hierarchy and run in polynomial time, but are quite far from being practically efficient as stated. Recent work of Hopkins et al. shows how to speed up sum-of-squares and obtain nearly linear time algorithms for a number of problems where the only previously known algorithms ran in a prohibitively large degree polynomial running time. Another approach would be to obtain similar guarantees for alternating minimization. Currently, the only known approaches require that the factors are orthonormal and only work in the undercomplete case. Finally, it would be interesting to get algorithms that recover a low rank tensor exactly when there is no noise.

2 Our approach

All of our algorithms are based on solving the following optimization problem:

and outputting the minimizer $X$, where $\|\cdot\|_{\mathcal{K}}$ is some norm that can be computed in polynomial time. It will be clear from the way we define the norm that the low rank part of $T$ will itself be a good candidate solution. But this is not necessarily the solution that the convex program finds. How do we know that whatever it finds not only has low entry-wise error on the observed entries of $T$, but also on the unobserved entries too?

This is a well-studied topic in statistical learning theory, and as is standard we can use the notion of Rademacher complexity as a tool to bound the error. The Rademacher complexity is a property of the norm we choose, and our main innovation is to use the sum-of-squares hierarchy to suggest a suitable norm. Our results are based on establishing a connection between noisy tensor completion and refuting random constraint satisfaction problems. Moreover, our analysis follows by embedding algorithms for refutation within the sum-of-squares hierarchy as a method to bound the Rademacher complexity.

A natural question to ask is: Are there other norms that have even better Rademacher complexity than the ones we use here, and that are still computable in polynomial time? It turns out that any such norm would immediately lead to much better algorithms for refuting random constraint satisfaction problems than we currently know. We have not yet introduced Rademacher complexity yet, so we state our lower bounds informally:

For any $\epsilon>0$, if there is a polynomial time algorithm that achieves error

through the framework of Rademacher complexity then there is an efficient algorithm for refuting a random $3$-SAT formula on $n$ variables with $m=n^{3/2-\epsilon}$ clauses. Moreover the natural sum-of-squares relaxation requires at least $n^{2\epsilon}$-levels in order to achieve the above error (again through the framework of Rademacher complexity).

These results follow directly from the works of Grigoriev , Schoenebeck and Feige . There are similar connections between our upper bounds and the work of Coja-Oghlan, Goerdt and Lanka who give an algorithm for strongly refuting random $3$-SAT. In Section 2 we explain some preliminary connections between these fields, at which point we will be in a better position to explain how we can borrow tools from one area to address open questions in another. We state this theorem more precisely in Corollary 2.13 and Corollary 5.6, which provide both conditional and unconditional lower bounds that match our upper bounds.

3 Computational vs. Sample Complexity Tradeoffs

It is interesting to compare the story of matrix completion and tensor completion. In matrix completion, we have the best of both worlds: There are efficient algorithms which work when the number of observations is close to the information theoretic minimum. In tensor completion, we gave algorithms that improve upon the number of observations needed by a polynomial factor but still require a polynomial factor more observations than can be achieved if we ignore computational considerations. We believe that for many other linear inverse problems (e.g. sparse phase retrieval), there may well be gaps between what can be achieved information theoretically and what can be achieved with computationally efficient estimators. Moreover, proving lower bounds against the sum-of-squares hierarchy offers a new type of evidence that problems are hard, that does not rely on reductions from other average-case hard problems which seem (in general) to be brittle and difficult to execute while preserving the naturalness of the input distribution. In fact, even when there are such reductions , the sum-of-squares hierarchy offers a methodology to make sharper predictions for questions like: Is there a quasi-polynomial time algorithm for sparse PCA, or does it require exponential time?

Organization

In Section 2 we introduce Rademacher complexity, the tensor nuclear norm and strong refutation. We connect these concepts by showing that any norm that can be computed in polynomial time and has good Rademacher complexity yields an algorithm for strongly refuting random $3$-SAT. In Section 3 we show how a particular algorithm for strong refutation can be embedded into the sum-of-squares hierarchy and directly leads to a norm that can be computed in polynomial time and has good Rademacher complexity. In Section 4 we establish certain spectral bounds that we need, and prove our main upper bounds. In Section 5 we prove lower bounds on the Rademacher complexity of the sequence of norms arising from the sum-of-squares hierarchy by a direct reduction to lower bounds for refuting random $3$-XOR. In Appendix A we give a reduction from noisy tensor completion on asymmetric tensors to symmetric tensors. This is what allows us to extend our analysis to arbitrary order $d$ tensors, but the proofs are essentially identical to those in the $d=3$ case but more notationally involved so we omit them.

Noisy Tensor Completion and Refutation

Here we make the connection between noisy tensor completion and strong refutation explicit. Our first step is to formulate a problem that is a special case of both, and studying it will help us clarify how notions from one problem translate to the other.

Here we introduce a problem that we call the distinguishing problem. We are given random observations from a tensor and promised that the underlying tensor fits into one of the two following categories. We want an algorithm that can tell which case the samples came from, and succeeds using as few observations as possible. The two cases are:

Each observation is chosen uniformly at random (and without replacement) from a tensor $T$ where independently for each entry we set

where $a$ is a vector whose entries are $\pm 1$.

Alternatively, each observation is chosen uniformly at random (and without replacement) from a tensor $T$ each of whose entries is independently set to either $+1$ or $-1$ and with equal probability.

In the first case, the entries of the underlying tensor $T$ are predictable. It is possible to guess a $15/16$ fraction of them correctly, once we have observed enough of its entries to be able to deduce $a$. And in the second case, the entries of $T$ are completely unpredictable because no matter how many entries we have observed, the remaining entries are still random. Thus we cannot predict any of the unobserved entries better than random guessing.

Now we will explain how the distinguishing problem can be equivalently reformulated in the language of refutation. We give a formal definition for strong refutation later (Definition 2.10), but for the time being we can think of it as the task of (given an instance of a constraint satisfaction problem) certifying that there is no assignment that satisfies many of the clauses. We will be interested in $3$-XOR formulas, where there are $n$ variables $v_{1},v_{2},...,v_{n}$ that are constrained to take on values $+1$ or $-1$. Each clause takes the form

Each clause in the formula is generated by choosing an ordered triple of variables $(v_{i},v_{j},v_{k})$ uniformly at random (and without replacement) and we set

where $a$ is a vector whose entries are $\pm 1$. Now $a$ represents a planted solution and by design our sampling procedure guarantees that many of the clauses that are generated are consistent with it.

Alternatively, each clause in the formula is generated by choosing an ordered triple of variables $(v_{i},v_{j},v_{k})$ uniformly at random (and without replacement) and we set $v_{i}\cdot v_{j}\cdot v_{k}=z_{i,j,k}$ where $z_{i,j,k}$ is a random variable that takes on values $+1$ and $-1$.

In the first case, the $3$-XOR formula has an assignment that satisfies a $15/16$ fraction of the clauses in expectation by setting $v_{i}=a_{i}$. In the second case, any fixed assignment satisfies at most half of the clauses in expectation. Moreover if we are given $\Omega(n\log n)$ clauses, it is easy to see by applying the Chernoff bound and taking a union bound over all possible assignments that with high probability there is no assignment that satisfies more than a $1/2+o(1)$ fraction of the clauses.

This will be the starting point for the connections we establish between noisy tensor completion and refutation. Even in the matrix case these connections seem to have gone unnoticed, and the same spectral bounds that are used to analyze the Rademacher complexity of the nuclear norm are also used to refute random $2$-SAT formulas , but this is no accident.

2 Rademacher Complexity

Ultimately our goal is to show that the hypothesis $X$ that our convex program finds is entry-wise close to the unknown tensor $T$. By virtue of the fact that $X$ is a feasible solution to (2) we know that it is entry-wise close to $T$ on the observed entries. This is often called the empirical error:

For a hypothesis $X$, the empirical error is

Recall that $\mbox{err}(X)$ is the average entry-wise error between $X$ and $T$, over all (observed and unobserved) entries. Also recall that among the candidate $X$’s that have low empirical error, the convex program finds the one that minimizes $\|X\|_{\mathcal{K}}$ for some polynomial time computable norm. The way we will choose the norm $\|\cdot\|_{\mathcal{K}}$ and our bound on the maximum magnitude of an entry of $\Delta$ will guarantee that the low rank part of $T$ will with high probability be a feasible solution. This ensures that $\|X\|_{\mathcal{K}}$ for the $X$ we find is not too large either. One way to bound $\mbox{err}(X)$ is to show that no hypothesis in the unit norm ball can have too large a gap between its error and its empirical error (and then dilate the unit norm ball so that it contains $X$). With this in mind, we define:

For a norm $\|\cdot\|_{\mathcal{K}}$ and a set $\Omega$ of observations, the generalization error is

It turns out that one can bound the generalization error via the Rademacher complexity.

It follows from a standard symmetrization argument from empirical process theory that the Rademacher complexity does indeed bound the generalization error.

Let $\epsilon\in(0,1)$ and suppose each $X$ with $\|X\|_{\mathcal{K}}\leq 1$ has bounded loss — i.e. $|X_{i,j,k}-T_{i,j,k}|\leq a$ and that locations $(i,j,k)$ are chosen uniformly at random and without replacement. Then with probability at least $1-\epsilon$, for every $X$ with $\|X\|_{\mathcal{K}}\leq 1$, we have

We repeat the proof here following for the sake of completeness but readers familiar with Rademacher complexity can feel free to skip ahead to Definition 2.5. The main idea is to let $\Omega^{\prime}$ be an independent set of $m$ samples from the same distribution, again without replacement. The expected generalization error is:

Let $Z$ be an $n_{1}\times n_{2}\times n_{3}$ tensor such that

This definition greatly simplifies our notation. In particular we have

where we have introduced the notation $\langle\mbox{ }\cdot\mbox{ },\mbox{ }\cdot\mbox{ }\rangle$ to denote the natural inner-product between tensors. Our main technical goal in this paper will be to analyze the Rademacher complexity of a sequence of successively tighter norms that we get from the sum-of-squares hierarchy, and to derive implications for noisy tensor completion and for refutation from these bounds.

3 The Tensor Nuclear Norm

A length $n_{i}$ vector $a$ is $C$-incoherent if $\|a\|=\sqrt{n_{i}}$ and $\|a\|_{\infty}\leq C$.

Recall that we chose to work with vectors whose typical entry is a constant so that the entries in $T$ do not become vanishingly small as the dimensions of the tensor increase. We can now define the tensor nuclear normThe usual definition of the tensor nuclear norm has no constraints that the vectors $a$, $b$ and $c$ be $C$-incoherent. However, adding this additional requirement only serves to further restrict the unit norm ball, while ensuring that the low rank part of $T$ (when scaled down) is still in it, since the factors of $T$ are anyways assumed to be $C$-incoherent. This makes it easier to prove recovery guarantees because we do not need to worry about sparse vectors behaving very differently than incoherent ones, and since we are not going to compute this norm anyways this modification will make our analysis easier.:

The tensor nuclear norm of $X$ which is denoted by $\|X\|_{{\mathcal{A}}}$ is the infimum over $\alpha$ such that $X/\alpha\in{\mathcal{A}}$.

In particular $\|T-\Delta\|_{{\mathcal{A}}}\leq r^{*}$. Finally we give an elementary bound on the Rademacher complexity of the tensor nuclear norm. Recall that $n=\max(n_{1},n_{2},n_{3})$.

$R^{m}(\|\cdot\|_{\mathcal{A}})=O(C^{3}\sqrt{\frac{n}{m}})$

Recall the definition of $Z$ given in Definition 2.5. With this we can write

We can now adapt the discretization approach in , although our task is considerably simpler because we are constrained to $C$-incoherent $a$’s. In particular, let

By standard bounds on the size of an $\epsilon$-net , we get that $|S|\leq O(C/\epsilon)^{n}$. Suppose that $|\langle Z,a\otimes b\otimes c\rangle|\leq M$ for all $a,b,c\in S$. Then for an arbitrary, but $C$-incoherent $a$ we can expand it as $a=\sum_{i}\epsilon^{i}a^{i}$ where each $a^{i}\in S$ and similarly for $b$ and $c$. And now

Moreover since each entry in $a\otimes b\otimes c$ has magnitude at most $C^{3}$ we can apply a Chernoff bound to conclude that for any particular $a,b,c\in S$ we have

with probability at least $1-\gamma$. Finally, if we set $\gamma=(\frac{\epsilon}{C})^{-n}$ and we set $\epsilon=1/2$ we get that

The important point is that the Rademacher complexity of the tensor nuclear norm is $o(1)$ whenever $m=\omega(n)$. In the next subsection we will connect this to refutation in a way that allows us to strengthen known hardness results for computing the tensor nuclear norm and show that it is even hard to compute in an average-case sense based on some standard conjectures about the difficulty of refuting random $3$-SAT.

4 From Rademacher Complexity to Refutation

Here we show the first implication of the connection we have established. Any norm that can be computed in polynomial time and has good Rademacher complexity immediately yields an algorithm for strongly refuting random $3$-SAT and $3$-XOR formulas. Next let us finally define strong refutation.

For a formula $\phi$, let $\operatorname{opt}(\phi)$ be the largest fraction of clauses that can be satisfied by any assignment.

In what follows, we will use the term random $3$-XOR formula to refer to a formula where each clause is generated by choosing an ordered triple of variables $(v_{i},v_{j},v_{k})$ uniformly at random (and without replacement) and setting $v_{i}\cdot v_{j}\cdot v_{k}=z$ where $z$ is a random variable that takes on values $+1$ and $-1$.

An algorithm for strongly refuting random $3$-XOR takes as input a $3$-XOR formula $\phi$ and outputs a quantity $\mbox{alg}(\phi)$ that satisfies

For any $3$-XOR formula $\phi$, $\operatorname{opt}(\phi)\leq\mbox{alg}(\phi)$

If $\phi$ is a random $3$-XOR formula with $m$ clauses, then with high probability $\mbox{alg}(\phi)=1/2+o(1)$

This definition only makes sense when $m$ is large enough so that $\mbox{opt}(\phi)=1/2+o(1)$ holds with high probability, which happens when $m=\omega(n)$. The goal is to design algorithms that use as few clauses as possible, and are able to certify that a random formula is indeed far from satisfiable (without underestimating the fraction of clauses that can be satisfied) and to do so as close as possible to the information theoretic threshold.

Now let us use a polynomial time computable norm $\|\cdot\|_{\mathcal{K}}$ that has good Rademacher complexity to give an algorithm for strongly refuting random $3$-XOR. As in Section 2.1, given a formula $\phi$ we map its $m$ clauses to a collection of $m$ observations according to the usual rule: If there are $n$ variables, we construct an $n\times n\times n$ tensor $Z$ where for each clause of the form $v_{i}\cdot v_{j}\cdot v_{k}=z_{i,j,k}$ we put the entry $z_{i,j,k}$ at location $(i,j,k)$. All the rest of the entries in $Z$ are set to zero. We solve the following optimization problem:

Let $\eta^{*}$ be the optimum value. We set $\mbox{alg}(\phi)=1/2+\eta^{*}$. What remains is to prove that the output of this algorithm solves the strong refutation problem for $3$-XOR.

Suppose that $\|\cdot\|_{\mathcal{K}}$ is computable in polynomial time and satisfies $\|X\|_{\mathcal{K}}\leq 1$ whenever $X=a\otimes a\otimes a$ and $a$ is a vector with $\pm 1$ entries. Further suppose that for any $X$ with $\|X\|_{\mathcal{K}}\leq 1$ its entries are bounded by $C^{3}$ in absolute value. Then (3) can be solved in polynomial time and if $R^{m}(\|\cdot\|_{\mathcal{K}})=o(1)$ then setting $\mbox{alg}(\phi)=1/2+\eta^{*}$ solves strong refutation for $3$-XOR with $O(C^{6}m\log n)$ clauses.

The key observation is the following inequality which relates (3) to $\operatorname{opt}(\phi)$.

To establish this inequality, let $v_{1},v_{2},...,v_{n}$ be the assignment that maximizes the fraction of clauses satisfied. If we set $a_{i}=v_{i}$ and $X=a\otimes a\otimes a$ we have that $\|X\|_{\mathcal{K}}\leq 1$ by assumption. Thus $X$ is a feasible solution. Now with this choice of $X$ for the right hand side, every term in the sum that corresponds to a satisfied clause contributes $+1$ and every term that corresponds to an unsatisfied clause contributes $-1$. We get $2\operatorname{opt}(\phi)-1$ for this choice of $X$, and this completes the proof of the inequality above.

The crucial point is that the expectation of the right hand side over $\Omega$ and $\sigma$ is exactly the Rademacher complexity. However we want a bound that holds with high probability instead of just in expectation. It follows from McDiarmid’s inequality and the fact that the entries of $Z$ and of $X$ are bounded by $1$ and by $C^{3}$ in absolute value respectively that if we take $O(C^{6}m\log n)$ observations the right hand side will be $o(1)$ with high probability. In this case, rearranging the inequality we have

The right hand side is exactly $\mbox{alg}(\phi)$ and is $1/2+o(1)$ with high probability, which implies that both conditions in the definition for strong refutation hold and this completes the proof. ∎

We can now combine Theorem 2.11 with the bound on the Rademacher complexity of the tensor nuclear norm given in Lemma 2.8 to conclude that if we could compute the tensor nuclear norm we would also obtain an algorithm for strongly refuting random $3$-XOR with only $m=\Omega(n\log n)$ clauses. It is not obvious but it turns out that any algorithm for strongly refuting random $3$-XOR implies one for $3$-SAT. Let us define strong refutation for $3$-SAT. We will refer to any variable $v_{i}$ or its negation $\bar{v}_{i}$ as a literal. We will use the term random $3$-SAT formula to refer to a formula where each clause is generated by choosing an ordered triple of literals $(y_{i},y_{j},y_{k})$ uniformly at random (and without replacement) and setting $y_{i}\vee y_{j}\vee y_{k}=1$.

An algorithm for strongly refuting random $3$-SAT takes as input a $3$-SAT formula $\phi$ and outputs a quantity $\mbox{alg}(\phi)$ that satisfies

For any $3$-SAT formula $\phi$, $\operatorname{opt}(\phi)\leq\mbox{alg}(\phi)$

If $\phi$ is a random $3$-SAT formula with $m$ clauses, then with high probability $\mbox{alg}(\phi)=7/8+o(1)$

The only change from Definition 2.10 comes from the fact that for $3$-SAT a random assignment satisfies a $7/8$ fraction of the clauses in expectation. Our goal here is to certify that the largest fraction of clauses that can be satisfied is $7/8+o(1)$. The connection between refuting random $3$-XOR and $3$-SAT is often called “Feige’s XOR Trick” . The first version of it was used to show that an algorithm for $\epsilon$-refuting $3$-XOR can be turned into an algorithm for $\epsilon$-refuting $3$-SAT. However we will not use this notion of refutation so for further details we refer the reader to . The reduction was extended later by Coja-Oghlan, Goerdt and Lanka to strong refutation, which for us yields the following corollary:

Suppose that $\|\cdot\|_{\mathcal{K}}$ is computable in polynomial time and satisfies $\|X\|_{\mathcal{K}}\leq 1$ whenever $X=a\otimes a\otimes a$ and $a$ is a vector with $\pm 1$ entries. Suppose further that for any $X$ with $\|X\|_{\mathcal{K}}\leq 1$ its entries are bounded by $C^{3}$ in absolute value and that $R^{m}(\|\cdot\|_{\mathcal{K}})=o(1)$. Then there is a polynomial time algorithm for strongly refuting a random $3$-SAT formula with $O(C^{6}m\log n)$ clauses.

Now we can get a better understanding of the obstacles to noisy tensor completion by connecting it to the literature on refuting random $3$-SAT. Despite a long line of work on refuting random $3$-SAT , there is no known polynomial time algorithm that works with $m=n^{3/2-\epsilon}$ clauses for any $\epsilon>0$. Feige conjectured that for any constant $C$, there is no polynomial time algorithm for refuting random $3$-SAT with $m=Cn$ clausesIn Feige’s paper there was no need to make the conjecture any stronger because it was already strong enough for all of the applications in inapproximability.. Daniely et al. conjectured that there is no polynomial time algorithm for $m=n^{3/2-\epsilon}$ for any $\epsilon>0$. What we have shown above is that any norm that is a relaxation to the tensor nuclear norm and can be computed in polynomial time but has Rademacher complexity is $R^{m}(\|\cdot\|_{\mathcal{K}})=o(1)$ for $m=n^{3/2-\epsilon}$ would disprove the conjecture of Daniely et al. and would yield much better algorithms for refuting random $3$-SAT than we currently know, despite fifteen years of work on the subject.

This leaves open an important question. While there are no known algorithms for strongly refuting random $3$-SAT with $m=n^{3/2-\epsilon}$ clauses, there are algorithms that work with roughly $m=n^{3/2}$ clauses . Do these algorithms have any implications for noisy tensor completion? We will adapt the algorithm of Coja-Oghlan, Goerdt and Lanka and embed it within the sum-of-squares hierarchy. In turn, this will give us a norm that we can use to solve noisy tensor completion which uses a polynomial factor fewer observations than known algorithms.

Using Resolution to Bound the Rademacher Complexity

Here we introduce the sum-of-squares hierarchy and will use it (at level six) to give a relaxation to the tensor nuclear norm. This will be the norm that we will use in proving our main upper bounds. First we introduce the notion of a pseudo-expectation operator from :

(1) $\widetilde{\mathop{\bf E\/}}=1$ (normalization)

(2) $\widetilde{\mathop{\bf E\/}}[P^{2}]\geq 0$, for any degree at most $k/2$ polynomial $P$ (nonnegativity)

Moreover suppose that $p\in P_{k}^{n^{\prime}}$ with $\mbox{deg}(p)=k^{\prime}$. We say that $\widetilde{\mathop{\bf E\/}}$ satisfies the constraint $\{p=0\}$ if $\widetilde{\mathop{\bf E\/}}[pq]=0$ for every $q\in P_{k-k^{\prime}}^{n^{\prime}}$. And we say that $\widetilde{\mathop{\bf E\/}}$ satisfies the constraint $\{p\geq 0\}$ if $\widetilde{\mathop{\bf E\/}}[pq^{2}]\geq 0$ for every $q\in P_{\lfloor(k-k^{\prime})/2\rfloor}^{n^{\prime}}$.

$\{\sum_{i=1}^{n_{1}}(Y^{(1)}_{i})^{2}=n_{1}\}$, $\{\sum_{i=1}^{n_{2}}(Y^{(2)}_{i})^{2}=n_{2}\}$ and $\{\sum_{i=1}^{n_{3}}(Y^{(3)}_{i})^{2}=n_{3}\}$

$\{(Y^{(1)}_{i})^{2}\leq C^{2}\}$, $\{(Y^{(2)}_{i})^{2}\leq C^{2}\}$ and $\{(Y^{(3)}_{i})^{2}\leq C^{2}\}$ for all $i$ and

$X_{i,j,k}=\widetilde{\mathop{\bf E\/}}[Y^{(1)}_{i}Y^{(2)}_{j}Y^{(3)}_{k}]$ for all $i,j$ and $k$.

The constraints in Definition 3.1 can be expressed as an $O(n^{k})$-sized semidefinite program. This implies that given any set of polynomial constraints of the form $\{p=0\}$, $\{p\geq 0\}$, one can efficiently find a degree $k$ pseudo-distribution satisfying those constraints if one exists. This is often called the degree $k$ Sum-of-Squares algorithm . Hence we can compute the norm $\|X\|_{\mathcal{K}_{k}}$ of any tensor $X$ to within arbitrary accuracy in polynomial time. And because it is a relaxation to the tensor nuclear norm which is defined analogously but over a distribution on $C$-incoherent vectors instead of a pseudo-distribution over them, we have that $\|X\|_{\mathcal{K}_{k}}\leq\|X\|_{{\mathcal{A}}}$ for every tensor $X$. Throughout most of this paper, we will be interested in the case $k=6$.

Recall that any polynomial time computable norm with good Rademacher complexity with $m$ observations yields an algorithm for strong refutation with roughly $m$ clauses too. Here we will use an algorithm for strongly refuting random $3$-SAT to guide our search for an appropriate norm. We will adapt an algorithm due to Coja-Oghlan, Goerdt and Lanka that strongly refutes random $3$-SAT, and will instead give an algorithm that strongly refutes random $3$-XOR. Moreover each of the steps in the algorithm embeds into the sixth level of the sum-of-squares hierarchy by mapping resolution operations to applications of Cauchy-Schwartz, that ultimately show how the inequalities that define the norm (Definition 3.2) can be manipulated to give bounds on its own Rademacher complexity.

Let’s return to the task of bounding the Rademacher complexity of $\|\cdot\|_{\mathcal{K}_{6}}$. Let $X$ be arbitrary but satisfy $\|X\|_{\mathcal{K}_{6}}\leq 1$. Then there is a degree six pseudo-expectation meeting the conditions of Definition 3.2. Using Cauchy-Schwartz we have:

To simplify our notation, we will define the following polynomial

which we will use repeatedly. If $d$ is even then any degree $d$ pseudo-expectation operator satisfies the constraint $(\widetilde{\mathop{\bf E\/}}[p])^{2}\leq\widetilde{\mathop{\bf E\/}}[p^{2}]$ for every polynomial $p$ of degree at most $d/2$ (e.g., see Lemma $A.4$ in ). Hence the right hand side of (4) can be bounded as:

It turns out that bounding the right-hand side of (5) boils down to bounding the spectral norm of the following matrix.

Let $A$ be the $n_{2}n_{3}\times n_{2}n_{3}$ matrix whose rows and columns are indexed over ordered pairs $(j,k^{\prime})$ and $(j^{\prime},k)$ respectively, defined as

We can now make the connection to resolution more explicit: We can think of a pair of observations $Z_{i,j,k},Z_{i,j^{\prime},k^{\prime}}$ as a pair of $3$-XOR constraints, as usual. Resolving them (i.e. multiplying them) we obtain a $4$-XOR constraint

$A$ captures the effect of resolving certain pairs of $3$-XOR constraints into $4$-XOR constraints. The challenge is that the entries in $A$ are not independent, so bounding its maximum singular value will require some care. It is important that the rows of $A$ are indexed by $(j,k^{\prime})$ and the columns are indexed by $(j^{\prime},k)$, so that $j$ and $j^{\prime}$ come from different $3$-XOR clauses, as do $k$ and $k^{\prime}$, and otherwise the spectral bounds that we will want to prove about $A$ would simply not be true! This is perhaps the key insight in .

It will be more convenient to decompose $A$ and reason about its two types of contributions separately. To that end, we let $R$ be the $n_{2}n_{3}\times n_{2}n_{3}$ matrix whose non-zero entries are of the form

and all of its other entries are set to zero. Then let $B$ be the $n_{2}n_{3}\times n_{2}n_{3}$ matrix whose entries are of the form

By construction we have $A=B+R$. Finally:

The pseudo-expectation operator satisfies $\{(Y^{(1)}_{i})^{2}\leq C^{2}\}$ for all $i$, and hence we have

We will now bound the contribution of $B$ and $R$ separately.

$\widetilde{\mathop{\bf E\/}}[(Y^{(2)}\otimes Y^{(3)})(Y^{(2)}\otimes Y^{(3)})^{T}]$ is positive semidefinite and has trace at most $n_{2}n_{3}$

It is easy to see that a quadratic form on $\widetilde{\mathop{\bf E\/}}[(Y^{(2)}\otimes Y^{(3)})(Y^{(2)}\otimes Y^{(3)})^{T}]$ corresponds to $\widetilde{\mathop{\bf E\/}}[p^{2}]$ for some $p\in P_{2}^{n_{2}+n_{3}}$ and this implies the first part of the claim. Finally

where the last equality follows because the pseudo-expectation operator satisfies the constraints $\{\sum_{i=1}^{n_{2}}(Y^{(2)}_{i})^{2}=n_{2}\}$ and $\{\sum_{i=1}^{n_{3}}(Y^{(3)}_{i})^{2}=n_{3}\}$. ∎

Hence we can bound the contribution of the first term as $C^{2}\langle B,\widetilde{\mathop{\bf E\/}}[(Y^{(2)}\otimes Y^{(3)})(Y^{(2)}\otimes Y^{(3)})^{T}]]\rangle\leq C^{2}n_{2}n_{3}\|B\|$. Now we proceed to bound the contribution of the second term:

$\widetilde{\mathop{\bf E\/}}[(Y^{(2)}_{j})^{2}(Y^{(3)}_{k})^{2}]\leq C^{4}$

It is easy to verify by direct computation that the following equality holds:

Moreover the pseudo-expectation of each of the three terms above is nonnegative, by construction. This implies the claim. ∎

Moreover each entry in $Z$ is in the set $\{-1,0,+1\}$ and there are precisely $m$ non-zeros. Thus the sum of the absolute values of all entries in $R$ is at most $m$. Now we have:

And this completes the proof of the lemma. ∎

Spectral Bounds

Recall the definition of $B$ given in the previous section. In fact, for our spectral bounds it will be more convenient to relabel the variables (but keeping the definition intact):

Let us consider the following random process: For $r=1,2,...,O(\log n)$ partition the set of all ordered triples $(i,j,k)$ into two sets $S_{r}$ and $T_{r}$. We will use this ensemble of partitions to define an ensemble of matrices $\{\mathsf{B}^{r}\}_{r=1}^{O(\log n)}$: Set $U_{i,j,k^{\prime}}^{r}$ as equal to $Z_{i,j,k^{\prime}}$ if $(i,j,k^{\prime})\in S_{r}$ and zero otherwise. Similarly set $V_{i,j^{\prime},k}^{r}$ equal to $Z_{i,j^{\prime},k}$ if $(i,j^{\prime},k)\in T_{r}$ and zero otherwise. Also let $E_{i,j,j^{\prime},k,k^{\prime},r}$ be the event that there is no $r^{\prime}<r$ where $(i,j,k^{\prime})\in S_{r^{\prime}}$ and $(i,j^{\prime},k)\in T_{r^{\prime}}$ or vice-versa. Now let

As is standard, we are interested in bounding $\mathop{\bf E\/}[\operatorname{Tr}(\mathsf{B}\mathsf{B}^{T}\mathsf{B}\mathsf{B}^{T}...\mathsf{B}\mathsf{B}^{T})]$ in order to bound $\|\mathsf{B}\|$. But note that $\mathsf{B}$ is not symmetric. Also note that the random variables $U$ and $V$ are not independent, however whether or not they are non-zero is non-positively correlated and their signs are mutually independent. Expanding the trace above we have

Fix a particular term in the above sum where each random variable appears an even number of times. Let $s$ be the number of distinct values for $i$. Moreover let $i_{1},i_{2},...,i_{s}$ be the order that these indices first appear. Now let $r^{j}_{1}$ denote the number of distinct values for $j$ that appear with $i_{1}$ in $U$ terms — i.e. $r^{j}_{1}$ is the number of distinct $j$’s that appear as $U_{i_{1},j,*}$. Let $r^{k}_{1}$ denote the number of distinct values for $k$ that appear with $i_{1}$ in $U$ terms — i.e. $r^{k}_{1}$ is the number of distinct $k$’s that appear as or $U_{i_{1},*,k}$. Similarly let $q^{j}_{1}$ denote the number of distinct values for $j$ that appear with $i_{1}$ in $V$ terms — i.e. $q^{j}_{1}$ is the number of distinct $j$’s that appear as $V_{i_{1},j,*}$. And finally let $q^{k}_{1}$ denote the number of distinct values for $k$ that appear with $i_{1}$ in $V$ terms — i.e. $q^{k}_{1}$ is the number of distinct $k$’s that appear as $V_{i_{1},*,k}$.

We give our encoding below. It is more convenient to think of the encoding as any way to answer the following questions about the term.

What is the order $i_{1},i_{2},...,i_{s}$ of the first appearance of each distinct value of $i$?

For each $i$ that appears, what is the order of each of the distinct values of $j$’s and $k$’s that appear along with it in $U$? Similarly, what is the order of each of the distinct values of $j$’s and $k$’s that appear along with it in $V$?

For each step (i.e. a new variable in the term when reading from left to right), has the value of $i$ been visited already? Also, has the value for $j$ or $k$ that appears along with $U$ been visited? Has the value for $j$ or $k$ that appears along with $V$ been visited? Note that whether or not $j$ or $k$ has been visited (together in $U$) depends on what the value of $i$ is, and if $i$ is a new value then the $j$ or $k$ value must be new too, by definition. Finally, if any value has already been visited, which earlier value is it?

It is easy to see that this encoding is injective, since given the answers to the above questions one can simulate each step and recover the sequence of random variables. Next we establish some easy facts that allow us to bound $\mathop{\bf E\/}[\operatorname{Tr}(\mathsf{B}\mathsf{B}^{T}\mathsf{B}\mathsf{B}^{T}...\mathsf{B}\mathsf{B}^{T})]$.

For any valid encoding, $s\leq r_{j}+q_{j}$ and $s\leq r_{k}+q_{k}$.

This holds because in each step where the $i$ variable is new and has not been visited before, by definition the $j$ variable is new too (for the current $i$) and similarly for the $k$ variable. ∎

Finally, if $s,r_{j},q_{j},r_{k}$ and $q_{k}$ are defined as above then for any contributing term

its expectation is at most $p^{r_{j}+r_{k}}p^{q_{j}+q_{k}}$ where $p=m/n_{1}n_{2}n_{3}$ because there are exactly $r_{j}+r_{k}$ distinct $U$ variables and $q_{j}+q_{k}$ distinct $V$ variables whose values are in the set $\{-1,0,+1\}$ and whether or not a variable is non-zero is non-positively correlated and the signs are mutually independent.

Note that the indicator variables only have the effect of zeroing out some terms that could otherwise contribute to $\mathop{\bf E\/}[\operatorname{Tr}(\mathsf{B}\mathsf{B}^{T}\mathsf{B}\mathsf{B}^{T}...\mathsf{B}\mathsf{B}^{T})]$. Returning to the task at hand, we have

Now if $p\max(n_{2},n_{3})\leq 1$ then using Claim 4.2 followed by the first half of Claim 4.1 we have:

where the last inequality follows because $pn_{1}^{1/2}\max(n_{2},n_{3})>1$. Alternatively if $p\max(n_{2},n_{3})>1$ then we can directly invoke the second half of Claim 4.1 and get:

As before, let $n=\max(n_{1},n_{2},n_{3})$. Then the last piece we need to bound the Rademacher complexity is the following spectral bound:

With high probability, \|B\|\leq O\Big{(}\frac{m\log^{4}n}{n_{1}^{1/2}\min(n_{2},n_{3})}\Big{)}

where we have used the fact that $p=m/n_{1}n_{2}n_{3}$. This completes the proof of the theorem. ∎

We can now bound the Rademacher complexity of the norm that we get from the six level sum-of-squares relaxation to the tensor nuclear norm:

R^{m}(\|\cdot\|_{\mathcal{K}_{6}})\leq O\Big{(}\sqrt{\frac{(n_{1})^{1/2}(n_{2}+n_{3})\log^{4}n}{m}}\Big{)}

Consider any $X$ with $\|X\|_{\mathcal{K}_{6}}\leq 1$. Then using Lemma 3.4 and Theorem 4.4 we have

Recall that $Z$ was defined in Definition 2.5. The Rademacher complexity can now be bounded as

which completes the proof of the theorem. ∎

Recall that bounds on the Rademacher complexity readily imply bounds on the generalization error (see Theorem 2.4). We can now prove Theorem 1.1:

We solve (2) using the norm $\|\cdot\|_{\mathcal{K}_{6}}$. Since this norm comes from the sixth level of the sum-of-squares hierarchy, it follows that (2) is an $n^{6}$-sized semidefinite program and there is an efficient algorithm to solve it to arbitrary accuracy. Moreover we can always plug in $X=T-\Delta$ and the bounds on the maximum magnitude of an entry in $\Delta$ together with the Chernoff bound imply that with high probability $X=T-\Delta$ is a feasible solution. Moreover $\|T-\Delta\|_{\mathcal{K}_{6}}\leq r^{*}$. Hence with high probability, the minimizer $X$ satisfies $\|X\|_{\mathcal{K}_{6}}\leq r^{*}$. Now if we take any such $X$ returned by the convex program, because it is feasible its empirical error is at most $2\delta$. And since $\|X\|_{\mathcal{K}_{6}}\leq r^{*}$ the bounds on the Rademacher complexity (Theorem 4.5) together with Theorem 2.4 give the desired bounds on $\mbox{err}(X)$ and complete the proof of our main theorem. ∎

Our goal is to lower bound the absolute value of a typical entry in $T$. To be concrete, suppose that $\operatorname{var}(T_{i,j,k})\geq f(r,n)$ for a $1-o(1)$ fraction of the entries where $f(r,n)=r^{1/2}/\log^{D}n$. Consider $T_{i,j,k}$, which we will view as a degree three polynomial in Gaussian random variables. Then the anti-concentration bounds of Carbery and Wright now imply that $|T_{i,j,k}|\geq f(r,n)/\log n$ with probability $1-o(1)$. With this in mind, we define

and it follows form Markov’s bound that that $|\mathcal{R}|\geq(1-o(1))n_{1}n_{2}n_{3}$. Now consider just those entries in $\mathcal{R}$ which we get substantially wrong:

We can now invoke Theorem 1.1 which guarantees that the hypothesis $X$ that results from solving (2) satisfies $\mbox{err}(X)=o(1/\log n)$ with probability $1-o(1)$ provided that $m=\widetilde{\Omega}(n^{3/2}r)$. This bound on the error immediately implies that $|\mathcal{R}^{\prime}|=o(n_{1}n_{2}n_{3})$ and so $|\mathcal{R}\setminus\mathcal{R}^{\prime}|=(1-o(1))n_{1}n_{2}n_{3}$. This completes the proof of the corollary. ∎

Sum-of-Squares Lower Bounds

Here we will show strong lower bounds on the Rademacher complexity of the sequence of relaxations to the tensor nuclear norm that we get from the sum-of-squares hierarchy. Our lower bounds follow as a corollary from known lower bounds for refuting random instances of $3$-XOR . First we need to introduce the formulation of the sum-of-squares hierarchy used in : We will call a Boolean function $f$ a $k$-junta if there is set $S\subseteq[n]$ of at most $k$ variables so that $f$ is determined by the values in $S$.

The $k$-round Lasserre hierarchy is the following relaxation:

$\|v_{0}\|^{2}=1$, $\|v_{C}\|^{2}=1$ for all $C\in{\mathcal{C}}$

$\langle v_{f},v_{g}\rangle=\langle v_{f^{\prime}},v_{g^{\prime}}\rangle$ for all $f,g,f^{\prime},g^{\prime}$ that are $k$-juntas and $f\cdot g\equiv f^{\prime}\cdot g^{\prime}$

$v_{f}+v_{g}=v_{f+g}$ for all $f,g$ that are $k$-juntas and satisfy $f\cdot g\equiv 0$

Here we define a vector $v_{f}$ for each $k$-junta, and ${\mathcal{C}}$ is a class of constraints that must be satisfied by any Boolean solution (and are necessarily $k$-juntas themselves). See for more background, but it is easy to construct a feasible solution to the above convex program given a distribution on feasible solutions for some constraint satisfaction problem. In the above relaxation, we think of functions $f$ as being $\{0,1\}$-valued. It will be more convenient to work with an intermediate relaxation where functions are $\{-1,1\}$-valued and the intuition is that $u_{S}$ for some set $S\subseteq[n]$ should correspond to the vector for the character $\chi_{S}$.

Alternatively, the $k$-round Lasserre hierarchy is the following relaxation:

$\|u_{\emptyset}\|^{2}=1$, $\langle u_{\emptyset},u_{S}\rangle=(-1)^{Z_{S}}$ for all $(\oplus_{S},Z_{S})\in{\mathcal{C}}$

$\langle u_{S},u_{T}\rangle=\langle u_{S^{\prime}},u_{T^{\prime}}\rangle$ for sets $S,T,S^{\prime},T^{\prime}$ that are size at most $k$ and satisfy $S\Delta T=S^{\prime}\Delta T^{\prime}$, where $\Delta$ is the symmetric difference.

Here we have explicitly made the switch to XOR-constraints — namely $(\oplus_{S},Z_{S})$ has $Z_{S}\in\{0,1\}$ and correspond to the constraint that the parity on the set $S$ is equal to $Z_{S}$. Now if we have a feasible solution to the constraints in Definition 5.1 where all the clauses are XOR-constraints, we can construct a feasible solution to the constraints in Definition 5.2 as follows. If $S$ is a set of size at most $k$, we define

where $f$ is the parity function on $S$ and $g=1-f$ is its complement. Moreover let $u_{\emptyset}=v_{0}$.

$\{u_{S}\}$ is a feasible solution to the constraints in Definition 5.2

Consider Constraint $(b)$ in Definition 5.2, and let $S,T,S^{\prime},T^{\prime}$ be sets of size at most $k$ that satisfy $S\oplus T=S^{\prime}\oplus T^{\prime}$. Then our goal is to show that

where $f_{S}$ is the parity function on $S$, and similarly for the other functions. Then we have $f_{S}\cdot f_{T}\equiv f_{S^{\prime}}\cdot f_{T^{\prime}}$ because $S\oplus T=S^{\prime}\oplus T^{\prime}$, and this implies that $\langle v_{f_{S}},v_{f_{T}}\rangle=\langle v_{f_{S^{\prime}}},v_{f_{T^{\prime}}}\rangle$. An identical argument holds for the other terms. This implies that all the Constraints $(b)$ hold. Similarly suppose $(\oplus_{S},Z_{S})\in{\mathcal{C}}$. Since $f_{S}\cdot g_{S}\equiv 0$ and $f_{S}+g_{S}\equiv 1$ it is well-known that $(1)$ $v_{f_{S}}$ and $v_{g_{S}}$ are orthogonal $(2)$ $v_{f_{S}}+v_{g_{S}}=v_{0}$ and $(3)$ since $f_{S}\in{\mathcal{C}}$ in Definition 5.1, we have $v_{g_{S}}=0$ (see ). Thus

Now following Barak et al. we can use the constraints in Definition 5.2 to define the operator $\widetilde{\mathop{\bf E\/}}[\cdot]$. In particular, given $p\in P_{k}^{n}$ where $p\equiv\sum_{S}c_{S}\prod_{i\in S}Y_{i}$ and $p$ is multilinear, we set

Here we will also need to define $\widetilde{\mathop{\bf E\/}}[p]$ when $p$ is not multilinear, and in that case if $Y_{i}$ appears an even number of times we replace it with $1$ and if it appears an odd number of times we replace it by $Y_{i}$ to get a multilinear polynomial $q$ and then set $\widetilde{\mathop{\bf E\/}}[p]=\widetilde{\mathop{\bf E\/}}[q]$.

$\widetilde{\mathop{\bf E\/}}[\cdot]$ is a feasible solution to the constraints in Definition 3.2, and for any $(\oplus_{S},Z_{S})\in{\mathcal{C}}$ we have $\widetilde{\mathop{\bf E\/}}[\prod_{i\in S}Y_{i}]=(-1)^{Z_{S}}$.

Then by construction $\widetilde{\mathop{\bf E\/}}=1$, and the proof that $\widetilde{\mathop{\bf E\/}}[p^{2}]\geq 0$ is given in , but we repeat it here for completeness. Let $p=\sum_{S}c_{S}\prod_{i\in S}Y_{i}$ be multilinear where we follow the above recipe and replace terms of the form $Y_{i}^{2}$ with $(1/n)$ as needed. Then $p^{2}=\sum_{S,T}c_{S}c_{T}\prod_{i\in S}Y_{i}\prod_{i\in T}Y_{i}$ and moreover

as desired. Next we must verify that $\widetilde{\mathop{\bf E\/}}[\cdot]$ satisfies the constraints $\{\sum_{i=1}^{n}Y_{i}^{2}=n\}$ and $\{Y_{i}^{2}\leq C^{2}\}$ for all $i\in\{1,2,...,n\}$, in accordance with Definition 3.1. To that end, observe that

which holds for any polynomial $q\in P_{k-2}^{n}$. Finally consider

which follows because $C^{2}\geq 1$ and holds for any polynomial $q\in P_{\lfloor(d-d^{\prime})/2\rfloor}^{n}$. This completes the proof. ∎

Let $\phi$ be a random $3$-XOR formula on $n$ variables with $m=n^{3/2-\epsilon}$ clauses. Then for any $\epsilon>0$ and any $c<2$, the $k=\Omega(n^{c\epsilon})$ round Lasserre hierarchy given in Definition 5.1 permits a feasible solution, with probability $1-o(1)$.

Note that the constant in the $\Omega(\cdot)$ depends on $\epsilon$ and $c$. Then using the above reductions, we have the following as an immediate corollary:

For any $\epsilon>0$ and any $c<2$ and $k=\Omega(n^{c\epsilon})$, if $m=n^{3/2-\epsilon}$ the Rademacher complexity $R^{m}(\|\cdot\|_{\mathcal{K}_{k}})=1-o(1)$.

Thus there is a sharp phase transition (as a function of the number of observations) in the Rademacher complexity of the norms derived from the sum-of-squares hierarchy. At level six, $R^{m}(\|\cdot\|_{\mathcal{K}_{6}})=o(1)$ whenever $m=\omega(n^{3/2}\log^{4}n)$. In contrast, $R^{m}(\|\cdot\|_{\mathcal{K}_{k}})=1-o(1)$ when $m=n^{3/2-\epsilon}$ even for very strong relaxations derived from $n^{2\epsilon}$ rounds of the sum-of-squares hierarchy. These norms require time $2^{n^{2\epsilon}}$ to compute but still achieve essentially no better bounds on their Rademacher complexity.

We would like to thank Aram Harrow for many helpful discussions.

References

Appendix A Reduction from Asymmetric to Symmetric Tensors

Here we give a general reduction, and show that any algorithm for tensor prediction that works for symmetric tensors can be used to predict the entries of an asymmetric tensor too. Hardt gave a related reduction for the cases of matrices and it is instructive to first understand this reduction, before proceeding to the tensor case. Suppose we are given a matrix $M$ that is not necessarily symmetric. Then the approach of is to construct the following symmetric matrix:

We have not precisely defined the notion of incoherence that is used in the matrix completion literature, but it turns out to be easy to see that $S$ is low rank and incoherent as well.

Now let us proceed to the tensor case. Let us introduce the following definition, for ease of notation:

Let $m(n,r,\epsilon,\mathpzc{f},C)$ be such that, there is an algorithm that on a rank $r$, order $d$, size $n\times n\times...\times n$ symmetric tensor where each factor has norm at most $C$, the algorithm returns an estimate $X$ with $\mbox{err}(X)=\mathpzc{f}$ with probability $1-\epsilon$ when it is given $m(n,r,\epsilon,\mathpzc{f})$ samples chosen uniformly at random (and without replacement).

For any odd $d$, suppose we are given $m(\sum_{j=1}^{d}n_{j},r2^{d-1},\epsilon,\mathpzc{f},\sqrt{d})$ samples chosen uniformly at random (and without replacement) from an $n_{1}\times n_{2}\times...\times n_{d}$ tensor

where each factor is unit norm. There is an algorithm that with probability at least $1-\epsilon$ returns an estimate $Y$ with