The power of sum-of-squares for detecting hidden structures

Introduction

Recent years have seen a surge of progress in algorithm design via the sum-of-squares (SoS) semidefinite programming hierarchy. Initiated by the work of [BBH+12], who showed that polynomial time algorithms in the hierarchy solve all known integrality gap instances for Unique Games and related problems, a steady stream of works have developed efficient algorithms for both worst-case [BKS14, BKS15, BKS17, BGG+16] and average-case problems [HSS15, GM15, BM16, RRS16, BGL16, MSS16a, PS17]. The insights from these works extend beyond individual algorithms to characterizations of broad classes of algorithmic techniques. In addition, for a large class of problems (including constraint satisfaction), the family of SoS semidefinite programs is now known to be as powerful as any semidefinite program (SDP) [LRS15].

In this paper we focus on recent progress in using Sum of Squares algorithms to solve average-case, and especially planted problems—problems that ask for the recovery of a planted signal perturbed by random noise. Key examples are finding solutions of random constraint satisfaction problems (CSPs) with planted assignments [RRS16] and finding planted optima of random polynomials over the $n$-dimensional unit sphere [RRS16, BGL16]. The latter formulation captures a wide range of unsupervised learning problems, and has led to many unsupervised learning algorithms with the best-known polynomial time guarantees [BKS15, BKS14, MSS16b, HSS15, PS17, BGG+16].

In many cases, classical algorithms for such planted problems are spectral algorithms—i.e., using the top eigenvector of a natural matrix associated with the problem input to recover a planted solution. The canonical algorithms for the planted clique [AKS98], principal components analysis (PCA) [Pea01], and tensor decomposition (which is intimately connected to optimizaton of polynomials on the unit sphere) [Har70] are all based on this general scheme. In all of these cases, the algorithm employs the top eigenvector of a matrix which is either given as input (the adjacency matrix, for planted clique), or is a simple function of the input (the empirical covariance, for PCA).

Recent works have shown that one can often improve upon these basic spectral methods using SoS, yielding better accuracy and robustness guarantees against noise in recovering planted solutions. Furthermore, for worst case problems—as opposed to the average-case planted problems we consider here—semidefinite programs are strictly more powerful than spectral algorithms.For example, consider the contrast between the SDP algorithm for Max-Cut of Goemans and Williamson, [GW94], and the spectral algorithm of Trevisan [Tre09]; or the SDP-based algorithms for coloring worst-case 3-colorable graphs [KT17] relative to the best spectral methods [AK97] which only work for random inputs. A priori one might therefore expect that these new SoS guarantees for planted problems would not be achievable via spectral algorithms. But curiously enough, in numerous cases these stronger guarantees for planted problems can be achieved by spectral methods! The twist is that the entries of these matrices are low-degree polynomials in the input to the algorithm . The result is a new family of low-degree spectral algorithms with guarantees matching SoS but requriring only eigenvector computations instead of general semidefinite programming [HSSS16, RRS16, AOW15a].

This leads to the following question which is the main focus of this work.

Are SoS algorithms equivalent to low-degree spectral methods for planted problems?

We answer this question affirmatively for a wide class of distinguishing problems which includes refuting random CSPs, tensor and sparse PCA, densest-$k$-subgraph, community detection in stochastic block models, planted clique, and more. Our positive answer to this question implies that a light-weight algorithm—computing the top eigenvalue of a single matrix whose entries are low-degree polynomials in the input—can recover the performance guarantees of an often bulky semidefinite programming relaxation.

To complement this picture, we prove two new SoS lower bounds for particular planted problems, both variants of component analysis: sparse principal component analysis and tensor principal component analysis (henceforth sparse PCA and tensor PCA, respectively) [ZHT06, RM14]. For both problems there are nontrivial low-degree spectral algorithms, which have better noise tolerance than naive spectral methods [HSSS16, DM14b, RRS16, BGL16]. Sparse PCA, which is used in machine learning and statistics to find important coordinates in high-dimensional data sets, has attracted much attention in recent years for being apparently computationally intractable to solve with a number of samples which is more than sufficient for brute-force algorithms [KNV+15, BR13b, MW15a]. Tensor PCA appears to exhibit similar behavior [HSS15]. That is, both problems exhibit information-computation gaps.

Our lower bounds for sparse and tensor PCA are closely connected to the failure of low-degree spectral methods in high noise regimes of both problems. We prove them both by showing that with noise beyond what known low-degree spectral algorithms can tolerate, even low-degree scalar algorithms (the result of restricting low-degree spectral algorithms to $1\times 1$ matrices) would require subexponential time to detect and recover planted signals. We then show that in the restricted settings of tensor and sparse PCA, ruling out these weakened low-degree spectral algorithms is enough to imply a strong SoS lower bound.

We turn to our characterization of SoS algorithms for planted problems in terms of low-degree spectral algorithms. First, a word on planted problems. Many planted problems have several formulations: search, in which the goal is to recover a planted solution, refutation, in which the goal is to certify that no planted solution is present, and distinguishing, where the goal is to determine with good probability whether an instance contains a planted solution or not. Often an algorithm for one version can be parlayed into algorithms for the others, but distinguishing problems are often the easiest, and we focus on them here.

A distinguishing problem is specified by two distributions on instances: a planted distribution supported on instances with a hidden structure, and a uniform distribution, where samples w.h.p. contain no hidden structure. Given an instance drawn with equal probability from the planted or the uniform distribution, the goal is to determine with probability greater than $\tfrac{1}{2}$ whether or not the instance comes from the planted distribution. For example:

Planted clique Uniform distribution: $G(n,\tfrac{1}{2})$, the Erdős-Renyi distribution, which w.h.p. contains no clique of size $\omega(\log n)$. Planted distribution: The uniform distribution on graphs containing a $n^{\varepsilon}$-size clique, for some $\varepsilon>0$. (The problem gets harder as $\varepsilon$ gets smaller, since the distance between the distributions shrinks.)

Planted $3$xor Uniform distribution: a $3$xor instance on $n$ variables and $m>n$ equations $x_{i}x_{j}x_{k}=a_{ijk}$, where all the triples $(i,j,k)$ and the signs $a_{ijk}\in\{\pm 1\}$ are sampled uniformly and independently. No assignment to $x$ will satisfy more than a $0.51$-fraction of the equations, w.h.p. Planted distribution: The same, except the signs $a_{ijk}$ are sampled to correlate with $b_{i}b_{j}b_{k}$ for a randomly chosen $b_{i}\in\{\pm 1\}$, so that the assignment $x=b$ satisfies a $0.9$-fraction of the equations. (The problem gets easier as $m/n$ gets larger, and the contradictions in the uniform case become more locally apparent.)

We now formally define a family of distinguishing problems, in order to give our main theorem. Let $\mathscr{I}$ be a set of instances corresponding to a product space (for concreteness one may think of $\mathscr{I}$ to be the set of graphs on $n$ vertices, indexed by $\{0,1\}^{\binom{n}{2}}$, although the theorem applies more broadly). Let $\nu$, our uniform distrbution, be a product distribution on $\mathscr{I}$.

With some decision problem $\mathcal{P}$ in mind (e.g. does $G$ contain a clique of size $\geqslant n^{\varepsilon}$?), let $\mathcal{X}$ be a set of solutions to $\mathcal{P}$; again for concreteness one may think of $\mathcal{X}$ as being associated with cliques in a graph, so that $\mathcal{X}\subset\{0,1\}^{n}$ is the set of all indicator vectors on at least $n^{\varepsilon}$ vertices.

For each solution $x\in\mathcal{X}$, let $\mu_{|_{x}}$ be the uniform distribution over instances $I\in\mathscr{I}$ that contain $x$. For example, in the context of planted clique, if $x$ is a clique on vertices $1,\ldots,n^{\varepsilon}$, then $\mu_{|_{x}}$ would be the uniform distribution on graphs containing the clique $1,\ldots,n^{\varepsilon}$. We define the planted distribution $\mu$ to be the uniform mixture over $\mu_{x}$, $\mu=U_{x\sim\mathcal{X}}\mu_{|_{x}}$.

The following is our main theorem on the equivalence of sum of squares algorithms for distinguishing problems and spectral algorithms employing low-degree matrix polynomials.

Let $N,n\in\mathcal{N}$, and let $\mathcal{A},\mathcal{B}$ be sets of real numbers. Let $\mathscr{I}$ be a family of instances over $\mathcal{A}^{N}$, and let $\mathcal{P}$ be a decision problem over $\mathscr{I}$ with $\mathcal{X}=\mathcal{B}^{n}$ the set of possible solutions to $\mathcal{P}$ over $\mathscr{I}$. Let $\{g_{j}(x,I)\}$ be a system of $n^{O(d)}$ polynomials of degree at most $d$ in the variables $x$ and constant degree in the variables $\mathcal{I}$ that encodes $\mathcal{P}$, so that

for $I\sim_{\nu}\mathscr{I}$, with high probability the system is unsatisfiable and admits a degree-$d$ SoS refutation, and

for $I\sim_{\mu}\mathscr{I}$, with high probability the system is satisfiable by some solution $x\in X$, and $x$ remains feasible even if all but an $n^{-0.01}$-fraction of the coordinates of $\mathcal{I}$ are re-randomized according to $\nu$.

where $\lambda^{+}_{\max}$ denotes the maximum non-negative eigenvalue.

The condition that a solution $x$ remain feasible if all but a fraction of the coordinates of $I\sim\mu_{|_{x}}$ are re-randomized should be interpreted as a noise-robustness condition. To see an example, in the context of planted clique, suppose we start with a planted distribution over graphs with a clique $x$ of size $n^{\varepsilon+0.01}$. If a random subset of $n^{0.99}$ vertices are chosen, and all edges not entirely contained in that subset are re-randomized according to the $G(n,1/2)$ distribution, then with high probability at least $n^{\varepsilon}$ of the vertices in $x$ remain in a clique, and so $x$ remains feasible for the problem $\mathcal{P}$: $G$ has a clique of size $\geqslant n^{\varepsilon}$?

2 SoS and information-computation gaps

Computational complexity of planted problems has become a rich area of study. The goal is to understand which planted problems admit efficient (polynomial time) algorithms, and to study the information-computation gap phenomenon: many problems have noisy regimes in which planted structures can be found by inefficient algorithms, but (conjecturally) not by polynomial time algorithms. One example is the planted clique problem, where the goal find a large clique in a sample from the uniform distribution over graphs containing a clique of size $n^{\varepsilon}$ for a small constant $\varepsilon>0$. While the problem is solvable for any $\varepsilon>0$ by a brute-force algorithm requiring $n^{\Omega(\log n)}$ time, polynomial time algorithms are conjectured to require $\varepsilon\geqslant\tfrac{1}{2}$.

A common strategy to provide evidence for such a gap is to prove that powerful classes of efficient algorithms are unable to solve the planted problem in the (conjecturally) hard regime. SoS algorithms are particularly attractive targets for such lower bounds because of their broad applicability and strong guarantees.

That is, such a polynomial $p$ has much larger expectation in under the planted distribution than its standard deviation in uniform distribution. (The choice of $n^{\Omega(1)}$ is somewhat arbitrary, and could be replaced with $\Omega(1)$ or $n^{\Omega(d)}$ with small changes in the parameters.) By showing that as long as $\varepsilon<\frac{1}{2}$ any such polynomial $p$ must have degree $\Omega(\log n)^{2}$, they rule out efficient SoS algorithms when $\varepsilon<\frac{1}{2}$. Interestingly, this matches the spectral distinguishing threshold—the spectral algorithm of [AKS98] is known to work when $\varepsilon\geqslant\frac{1}{2}$.

This stronger characterization of SoS for the planted clique problem, in terms of scalar distinguishing algorithms rather than spectral distinguishing algorihtms, may at first seem insignificant. To see why the scalar characterization is more powerful, we point out that if the degree-$d$ moments of the planted and uniform distributions are known, determining the optimal scalar distinguishing polynomial is easy: given a planted distribution $\mu$ and a random distribution $\nu$ over instances $\mathcal{I}$, one just solves a linear algebra problem in the $n^{d\log n}$ coefficients of $p$ to maximize the expectation over $\mu$ relative to $\nu$:

It is not difficult to show that the optimal solution to the above program has a simple form: it is the projection of the relative density of $\nu$ with respect to $\mu$ projected to the degree-$d\log n$ polynomials. So given a pair of distributions $\mu,\nu$, in $n^{O(d\log n)}$ time, it is possible to determine whether there exists a degree-$d\log n$ scalar distinguishing polynomial. Answering the same question about the existence of a spectral distinguisher is more complex, and to the best of our knowledge cannot be done efficiently.

Given this powerful theorem for the case of the planted clique problem, one may be tempted to conjecture that this stronger, scalar distinguisher characterization of the SoS algorithm applies more broadly than just to the planted clique problem, and perhaps as broadly as Theorem 1.1. If this conjecture is true, given a pair of distributions $\nu$ and $\mu$ with known moments, it would be possible in many cases to efficiently and mechanically determine whether polynomial-time SoS distinguishing algorithms exist!

To illustrate the power of this conjecture, in the beginning of Section 6 we give a short and self-contained explanation of how this predicts, via simple linear algebra, our $n^{\Omega(1)}$-degree SoS lower bound for tensor PCA. As evidence for the conjecture, we verify this prediction by proving such a lower bound unconditionally.

We also note why Theorem 1.1 does not imply Conjecture 1.2. While, in the notation of that theorem, the entries of $Q(I)$ are low-degree polynomials in $I$, the function $M\mapsto\lambda^{+}_{\max}(M)$ is not (to the best of our knowledge) a low-degree polynomial in the entries of $M$ (even approximately). (This stands in contrast to, say the operator norm or Frobenious norm of $M$, both of which are exactly or approximately low-degree polynomials in the entries of $M$.) This means that the final output of the spectral distinguishing algorithm offered by Theorem 1.1 is not a low-degree polynomial in the instance $I$.

3 Exponential lower bounds for sparse PCA and tensor PCA

Our other main results are strong exponential lower bound on the sum-of-squares method (specifically, against $2^{n^{\Omega(1)}}$ time or $n^{\Omega(1)}$ degree algorithms) for the tensor and sparse principal component analysis (PCA). We prove the lower bounds by extending the techniques pioneered in [BHK+16]. In the present work we describe the proofs informally, leaving full details to a forthcoming full version.

We start with the simpler case of tensor PCA, introduced by [RM14].

Uniform Distribution: each entry of the tensor sampled independently from $\mathcal{N}(0,1)$.

Here, we think of $v$ as a signal hidden by Gaussian noise. The parameter $\lambda$ is a signal-to-noise ratio. In particular, as $\lambda$ grows, we expect the distinguishing problem above to get easier.

Tensor PCA is a natural generalization of the PCA problem in machine learning and statistics. Tensor methods in general are useful when data naturally has more than two modalities: for example, one might consider a recommender system which factors in not only people and movies but also time of day. Many natural tensor problems are NP hard in the worst-case. Though this is not necessarily an obstacle to machine learning applications, it is important to have average-case models to in which to study algorithms for tensor problems. The spiked tensor setting we consider here is one such simple model.

A natural generalization of this algorithm to the tensor PCA setting (restricting for simplicity $k=3$ for this discussion) is the maximum of the degree-three polynomial $\langle T,x^{\otimes 3}\rangle$ over the unit sphere—equivalently, the (symmetric) injective tensor norm of $T$. This maximum can be shown to be much larger in case of the planted distribution so long as $\lambda\gg\sqrt{n}$. Indeed, this approach to distinguishing between planted and uniform distributions is information-theoretically optimal [PWB16, BMVX16]. Since recovering the spike $v$ and optimizing the polynomial $\langle T,x^{\otimes 3}\rangle$ on the sphere are equivalent, tensor PCA can be thought of as an average-case version of the problem of optimizing a degree-$3$ polynomial on the unit sphere (this problem is NP hard in the worst case, even to approximate [HL09, BBH+12]).

Even in this average-case model, it is believed that there is a gap between which signal strengths $\lambda$ allow recovery of $v$ by brute-force methods and which permit polynomial time algorithms. This is quite distinct from the vanilla PCA setting, where eigenvector algorithms solve the spike-recovery problem to information-theoretic optimality. Nevertheless, the best-known algorithms for tensor PCA arise from computing convex relaxations of this degree-$3$ polynomial optimization problem. Specifically, the SoS method captures the state of the art algorithms for the problem; it is known to recover the vector $v$ to $o(1)$ error in polynomial time whenever $\lambda\gg n^{3/4}$ [HSS15]. A major open question in this direction is to understand the complexity of the problem for $\lambda\leqslant n^{3/4-\varepsilon}$. Algorithms (again captured by SoS) are known which run in $2^{n^{O(\varepsilon)}}$ time [RRS16, BGG+16]. We show the following theorem which shows that the sub-exponential algorithm above is in fact nearly optimal for SoS algorithm.

In particular for third order tensors (i.e $k=3$), since degree $n^{\Omega(\varepsilon)}$ SoS is unable to certify that a random $3$-tensor has maximum value much less than $n^{3/4-\varepsilon}$, this SoS relaxation cannot be used to distinguish the planted and random distributions above when $\lambda\ll n^{3/4-\varepsilon}$.In fact, our proof for this theorem will show somewhat more: that a large family of constraints—any valid constraint which is itself a low-degree polynomial of $T$—could be added to this convex relaxation and the lower bound would still obtain.

We turn to sparse PCA, which we formalize as the following planted distinguishing problem.

Given an $n\times n$ symmetric real matrix $A$, determine whether $A$ comes from:

Uniform Distribution: each upper-triangular entry of the matrix $A$ is sampled iid from $\mathcal{N}(0,1)$; other entries are filled in to preserve symmetry.

Planted Distribution: a random $k$-sparse unit vector $v$ with entries $\{\pm 1/\sqrt{k},0\}$ is sampled, and $B$ is sampled from the uniform distribution above; then $A=B+\lambda\cdot vv{}^{\mkern-4.0mu\intercal}$.

We generally think of $k,\lambda$ as small powers of $n$; i.e. $n^{\rho}$ for some $\rho\in(0,1)$; this allows us to generally ignore logarithmic factors in our arguments. As in the tensor PCA setting, a natural and information-theoretically optimal algorithm for sparse PCA is to maximize the quadratic form $\langle x,Ax\rangle$, this time over $k$-sparse unit vectors. For $A$ from the uniform distribution standard techniques ($\varepsilon$-nets and union bounds) show that the maximum value achievable is $O(\sqrt{k}\log n)$ with high probability, while for $A$ from the planted model of course $\langle v,Av\rangle\approx\lambda$. So, when $\lambda\gg\sqrt{k}$ one may distinguish the two models by this maximum value.

However, this maximization problem is NP hard for general quadratic forms $A$ [CPR16]. So, efficient algorithms must use some other distinguisher which leverages the randomness in the instances. Essentially only two polynomial-time-computable distinguishers are known.If one studies the problem at much finer granularity than we do here, in particular studying $\lambda$ up to low-order additive terms and how precisely it is possible to estimate the planted signal $v$, then the situation is more subtle [DM14a]. If $\lambda\gg\sqrt{n}$ then the maximum eigenvalue of $A$ distinguishes the models. If $\lambda\gg k$ then the planted model can be distinguished by the presence of large diagonal entries of $A$. Notice both of these distinguishers fail for some choices of $\lambda$ (that is, $\sqrt{k}\ll\lambda\ll\sqrt{n},k$) for which brute-force methods (optimizing $\langle x,Ax\rangle$ over sparse $x$) could successfully distinguish planted from uniform $A$’s. The theorem below should be interpreted as an impossibility result for SoS algorithms in the $\sqrt{k}\ll\lambda\ll\sqrt{n},k$ regime. This is the strongest known impossibility result for sparse PCA among those ruling out classes of efficient algorithms (one reduction-based result is also know, which shows sparse PCA is at least as hard as the planted clique problem [BR13a]. It is also the first evidence that the problem may require subexponential (as opposed to merely quasi-polynomial) time.

There are absolute constants $c,\varepsilon^{*}>0$ so that for every $\rho\in(0,1)$ and $\varepsilon\in(0,\varepsilon^{*})$, if $k=n^{\rho}$, then for $d\leqslant n^{c\cdot\varepsilon}$,

For more thorough discussion of the theorem, see Section 6.3.

4 Related work

As we have already alluded to, many prior works explore the connection between SoS relaxations and spectral algorithms, beginning with the work of [BBH+12] and including the followup works [HSS15, AOW15b, BM16] (plus many more). Of particular interest are the papers [HSSS16, MS16b], which use the SoS algorithms to obtain fast spectral algorithms, in some cases running in time linear in the input size (smaller even than the number of variables in the associated SoS SDP).

In light of our Theorem 1.1, it is particularly interesting to note cases in which the known SoS lower bounds matching the known spectral algorithms—these problems include planted clique (upper bound: [AKS98], lower bound:SDP lower bounds for the planted clique problem were known for smaller degrees of sum-of-squares relaxations and for other SDP relaxations before; see the references therein for details. [BHK+16]), strong refutations for random CSPs (upper bound:There is a long line of work on algorithms for refuting random CSPs, and 3SAT in particular; the listed papers contain additional references. [AOW15b, RRS16], lower bounds: [Gri01b, Sch08, KMOW17]), and tensor principal components analysis (upper bound: [HSS15, RRS16, BGG+16], lower bound: this paper).

We also remark that our work applies to several previously-considered distinguishing and average-case problems within the sum-of-squares algorithmic framework: block models [MS16a] , densest-$k$-subgraph [BCC+10]; for each of these problems, we have by Theorem 1.1 an equivalence between efficient sum-of-squares algorithms and efficient spectral algorithms, and it remains to establish exactly what the tradeoff is between efficiency of the algorithm and the difficulty of distinguishing, or the strength of the noise.

To the best of knowledge, no previous work has attempted to characterize SoS relaxations for planted problems by simpler algorithms in the generality we do here. Some works have considered characterizing degree-$2$ SoS relaxations (i.e. basic semidefinie programs) in terms of simpler algorithms. One such example is recent work of Fan and Montanari [FM16] who showed that for some planted problems on sparse random graphs, a class of simple procedures called local algorithms performs as well as semidefinite programming relaxations.

By now, there’s a large body of work that establishes lower bounds on SoS SDP for various average case problems. Beginning with the work of Grigoriev [Gri01a], a long line work have established tight lower bounds for random constraint satisfaction problems [Sch08, BCK15, KMOW17] and planted clique [MPW15, DM15, HKP15, RS15, BHK+16]. The recent SoS lower bound for planted clique of [BHK+16] was particularly influential to this work, setting the stage for our main line of inquiry. We also draw attention to previous work on lower bounds for the tensor PCA and sparse PCA problems in the degree-$4$ SoS relaxation [HSS15, MW15b]—our paper improves on this and extends our understanding of lower bounds for tensor and sparse PCA to any degree.

5 Organization

In Section 2 we set up and state our main theorem on SoS algorithms versus low-degree spectral algorithms. In Section 5 we show that the main theorem applies to numerous planted problems—we emphasize that checking each problem is very simple (and barely requires more than a careful definition of the planted and uniform distributions). In Section 3 and Section 4 we prove the main theorerm on SoS algorithms versus low-degree spectral algorithms.

In section 7 we get prepared to prove our lower bound for tensor PCA by proving a structural theorem on factorizations of low-degree matrix polynomials with well-behaved Fourier transforms. In section 8 we prove our lower bound for tensor PCA, using some tools proved in section 9.

Distinguishing Problems and Robust Inference

In this section, we set up the formal framework within which we will prove our main result.

Suppose that $\mathscr{I}$ is the space of all instances, and suppose we have two distributions over $\mathscr{I}$, a product distribution $\nu$ (the “uniform” distribution), and an arbitrary distribution $\mu$ (the “planted” distribution).

In a uniform distinguishing problem, we are given an instance $\mathcal{I}\in\mathscr{I}$ which is sampled with probability $\frac{1}{2}$ from $\nu$ and with probability $\frac{1}{2}$ from $\mu$, and the goal is to determine with probability greater than $\frac{1}{2}+\varepsilon$ which distribution $\mathcal{I}$ was sampled from, for any constant $\varepsilon>0$.

Polynomial Systems

In the uniform distinguishing problems that we are interested in, the planted distribution $\mu$ will be a distribution over instances that obtain a large value for some optimization problem of interest (i.e. the max clique problem). We define polynomial systems in order to formally capture optimization problems.

For the sake of simplicity, the polynomial system Program 2.2 has no inequalities. Inequalities can be incorporated in to the program by converting each inequality in to an equality with an additional slack variable. Our main theorem still holds, but for some minor modifications of the proof, as outlined in Section 4.

Planted Distributions

We will be concerned with planted distributions of a particular form; first, we fix a polynomial system of interest $\mathcal{S}=\{g_{j}(x,\mathcal{I})\}_{j\in[m]}$ and some set $\mathcal{X}\subseteq\mathcal{B}^{n}$ of feasible solutions for $\mathcal{S}$, so that the program variables $x$ represent elements of $\mathcal{X}$. Again, for concreteness, if $\mathscr{I}$ is the set of graphs on $n$ vertices, we can take $\mathcal{X}\subseteq\{0,1\}^{n}$ to be the set of indicators for subsets of at least $n^{\varepsilon}$ vertices.

For each fixed $x\in\mathcal{X}$, let $\mu_{|x}$ denote the uniform distribution over $\mathcal{I}\in\mathscr{I}$ for which the polynomial system $\{g_{j}(x,\mathcal{I})\}_{j\in[m]}$ is feasible. The planted distribution $\mu$ is given by taking the uniform mixture over the $\mu_{|x}$, i.e., $\mu\sim U_{x\sim\mathcal{X}}[\mu_{|x}]$.

SoS Relaxations

Sub-instances

Suppose that $\mathscr{I}=\mathcal{A}^{N}$ is a family of instances; then given an instance $\mathcal{I}\in\mathscr{I}$ and a subset $S\subseteq[N]$, let $\mathcal{I}_{S}$ denote the sub-instance consisting of coordinates within $S$. Further, for a distribution $\Theta$ over subsets of $[N]$, let $\mathcal{I}_{S}\sim_{\Theta}\mathcal{I}$ denote a subinstance generated by sampling $S\sim\Theta$. Let $\mathcal{I}_{\downarrow}$ denote the set of all sub-instances of an instance $\mathcal{I}$, and let $\mathscr{I}_{\downarrow}$ denote the set of all sub-instances of all instances.

Robust Inference

Our result will pertain to polynomial systems that define planted distributions whose solutions to sub-instances generalize to feasible solutions over the entire instance. We call this property “robust inference.”

Let $\mathscr{I}=\mathcal{A}^{N}$ be a family of instances, let $\Theta$ be a distribution over subsets of $[N]$, let $\mathcal{S}$ be a polynomial system as in Program 2.2, and let $\mu$ be a planted distribution over instances feasible for $\mathcal{S}$. Then the polynomial system $\mathcal{S}$ is said to satisfy the robust inference property for probability distribution $\mu$ on $\mathscr{I}$ and subsampling distribution $\Theta$, if given a subsampling $\mathcal{I}_{S}$ of an instance $\mathcal{I}$ from $\mu$, one can infer a setting of the program variables $x^{*}$ that remains feasible to $\mathcal{S}$ for most settings of $\mathcal{I}_{\overline{S}}$.

for some negligible function $\varepsilon(n,d)$. To specify the error probability, we will say that polynomial system is $\varepsilon(n,d)$-robustly inferable.

Main Theorem

We are now ready to state our main theorem.

The polynpomial system $\mathcal{S}$ is $\frac{1}{n^{8B}}$-robustly inferable with respect to the planted distribution $\mu$ and the sub-sampling distribution $\Theta$.

For $\mathcal{I}\sim\nu$, the polynomial system $\mathcal{S}$ admits a degree-$d$ SoS refutation with numbers bounded by $n^{B}$ with probability at least $1-\frac{1}{n^{8B}}$.

Our argument implies a stronger result that can be stated in terms of the eigenspaces of the subsampling operator. Specifically, suppose we define

Then, the distinguishing polynomial exhibited by Theorem 2.6 satisfies $Q\in\operatorname{span}\{\text{ monomials }\mathcal{I}_{\alpha}|\alpha\in\mathcal{S}_{\varepsilon}\}$. This refinement can yield tighter bounds in cases where all monomials of a certain degree are not equivalent to each other. For example, in the Planted Clique problem, each monomial consists of a subgraph and the right measure of the degree of a sub-graph is the number of vertices in it, as opposed to the number of edges in it.

In Section 5, we will make the routine verifications that the conditions of this theorem hold for a variety of distinguishing problems: planted clique (Lemma 5.2), refuting random CSPs (Lemma 5.4, stochastic block models (Lemma 5.6), densest-$k$-subgraph (Lemma 5.8), tensor PCA (Lemma 5.10), and sparse PCA (Lemma 5.12). Now we will proceed to prove the theorem.

Moment-Matching Pseudodistributions

We assume the setup from Section 2: we have a family of instances $\mathscr{I}=\mathcal{A}^{N}$, a polynomial system $\mathcal{S}=\{g_{j}(x,\mathcal{I})\}_{j\in[m]}$ with a family of solutions $\mathcal{X}=\mathcal{B}^{n}$, a “uniform” distribution $\nu$ which is a product distribution over $\mathscr{I}$, and a “planted” distribution $\mu$ over $\mathscr{I}$ defied by the polynomial system $\mathcal{S}$ as described in Section 2.

The contrapositive of Theorem 2.6 is that if $\mathcal{S}$ is robustly inferable with respect to $\mu$ and a distribution over sub-instances $\Theta$, and if there is no spectral algorithm for distinguishing $\mu$ and $\nu$, then with high probability there is no degree-$d$ SoS refutation for the polynomial system $\mathcal{S}$ (as defined in Program 2.4). To prove the theorem, we will use duality to argue that if no spectral algorithm exists, then there must exist an object which is in some sense close to a feasible solution to the SoS SDP relaxation.

where $\hat{\mu}$ is the relative density of $\mu$ with respect to $\nu$, so that $\hat{\mu}(\mathcal{I})=\mu(\mathcal{I})/\nu(\mathcal{I})$, and $M$ is some matrix valued function such that $M(\mathcal{I})\succeq 0$ and $\lVert M(\mathcal{I})\rVert\leqslant B$ for all $\mathcal{I}\in\mathscr{I}$. Our goal is to find a PSD matrix-valued function $P$ that matches the low-degree moments of $\Lambda$ in the variables $\mathcal{I}$, while being supported over most of $\mathscr{I}$ (rather than just over the support of $\mu$).

We have perturbed $\Lambda$ in (3.3) so that we can easily show that strong duality holds in the proof of Claim 3.4. For the remainder of the paper we ignore this perturbation, as we can accumulate the resulting error terms and set $\eta$ to be small enough so that they can be neglected.

The dual of the above program will allow us to relate the existence of an SoS refutation to the existence of a spectral algorithm.

where $Q_{+}$ is the projection of $Q$ to the PSD cone.

Program 3.3 is a manipulation of the dual of Program 3.1, so that if Program 3.1 has optimum $c>1$, Program 3.3 as optimum at least $\Omega(\sqrt{c})$.

Before we present the proof of the claim, we summarize its central consequence in the following theorem: if Program 3.1 has a large objective value (and therefore does not provide a feasible SoS solution), then there is a spectral algorithm.

By Claim 3.4, if the value of Program 3.1 is $\operatorname{opt}>1$, then there is a polynomial $Q$ achieves a value of $\Omega(\sqrt{\operatorname{opt}})$ for the dual. It follows that

It is interesting to note that the specific structure of the PSD matrix valued function $M$ plays no role in the above argument—since $M$ serves as a proxy for monomials in the solution as represented by the program variables $x^{\otimes d}$, it follows that the choice of how to represent the planted solution is not critical. Although seemingly counterintuitive, this is natural because the property of being distinguishable by low-degre distinguishers or by SoS SDP relaxations is a property of $\nu$ and $\mu$.

We wrap up the section by presenting a proof of the Claim 3.4.

We take the Lagrangian dual of Program 3.1. Our dual variables will be some combination of low-degree matrix polynomials, $Q$, and a PSD matrix $A$:

It is easy to verify that if $P$ is not PSD, then $A$ can be chosen so that the value of $\mathcal{L}$ is $\infty$. Similarly if there exists a low-degree polynomial upon which $P$ and $\Lambda$ differ in expectation, $Q$ can be chosen as a multiple of that polynomial so that the value of $\mathcal{L}$ is $\infty$.

Now, we argue that Slater’s conditions are met for Program 3.1, as $P=\Lambda^{\prime}$ is strictly feasible. Thus strong duality holds, and therefore

Taking the partial derivative of $\mathcal{L}(P,Q,A)$ with respect to $P$, we have

Now it is clear that the maximizing choice of $A$ is to set $A=-Q_{-}$, the negation of the negative-semi-definite projection of $Q$. Thus (3.4) simplifies to

Consider $Q^{\prime}=Q^{*}/\|Q^{*}_{+}\|_{Fr,\nu}$. Clearly $\|Q^{\prime}_{+}\|_{Fr,\nu}=1$. Now, multiplying the above inequality through by the scalar $1/\|Q^{*}_{+}\|_{Fr,\nu}$, we have that

Therefore $\langle Q^{\prime},\Lambda\rangle_{\nu}$ is at least $\Omega(c^{1/2})$, as if $\|Q^{*}_{+}\|_{Fr,\nu}\geqslant\sqrt{c}$ then the third term gives the lower bound, and otherwise the first term gives the lower bound.

Thus by substituting $Q^{\prime}$, the square root of the maximum of (3.5) within an additive $\eta n^{d}$ lower-bounds the maximum of the program

Proof of Theorem 2.6

We will prove Theorem 2.6 by contradiction. Let us assume that there exists no degree-$2D$ matrix polynomial that distinguishes $\nu$ from $\mu$. First, the lack of distinguishers implies the following fact about scalar polynomials.

Under the assumption that there are no degree-$2D$ distinguishers, for every degree-$D$ scalar polynomial $Q$,

Suppose not, then the degree-$2D$ $1\times 1$ matrix polynomial $\operatorname{Tr}(Q(\mathcal{I})^{2})$ will be a distinguisher between $\mu$ and $\nu$. ∎

Since $\Lambda(\mathcal{I})$ is an average over $\Lambda_{S}(\mathcal{I})$, each of which is a feasible solution with high probability, $\Lambda(\mathcal{I})$ is close to a feasible solution to the SDP relaxation for $\mathcal{I}$. The following Lemma formalizes this intuition.

Suppose Program 2.2 satisfies the $\varepsilon$-robust inference property with respect to planted distribution $\mu$ and subsampling distribution $\Theta$ and if $\lVert x(\mathcal{I}_{S})^{\leqslant d}\rVert_{2}^{2}\leqslant K$ for all $\mathcal{I}_{S}$ then for every $G\in\mathcal{G}$, we have

We begin by expanding the left-hand side by substituting the definition of $\Lambda$. We have

The lemma follows by observing that the first term in the product above is exactly the non-robustness of inference probability $\varepsilon$. ∎

If $G\in\mathcal{G}$ is a degree-$D$ polynomial in $\mathcal{I}$, then under the assumption that there are no degree-$2D$ distinguishers for $\nu,\mu$,

Substituting back in the bound in Lemma 4.2 the corollary follows. ∎

Now, since there are no degree-$D$ matrix distinguishers $Q$, for each $S$ in the support of $\Theta$ we can apply reasoning similar to Theorem 3.5 to conclude that there is a high-entropy PSD matrix-valued function $P_{S}$ that matches the degree-$D$ moments of $\Lambda_{S}$.

If there are no degree-$D$ matrix distinguishers $Q$ for $\mu,\nu$, then for each $S\sim\Theta$, there exists a solution $P_{S}$ to Program 3.1 (with the variable $\Lambda:=\Lambda_{S}$) and

This does not follow directly from Theorem 3.5, because a priori a distinguisher for some specific $S$ may only apply to a small fraction of the support of $\mu$. However, we can show that Program 3.1 has large value for $\Lambda_{S}$ only if there is a distinguisher for $\mu,\nu$.

By Claim 3.4, it suffices for us to argue that there is no degree-$D$ matrix polynomial $Q$ which has large inner product with $\Lambda_{S}$ relative to its Frobenius norm. So, suppose by way of contradiction that $Q$ is a degree-$D$ matrix that distinguishes $\Lambda_{S}$, so that $\langle Q,\Lambda_{S}\rangle_{\nu}\geqslant n^{B+d}$ but $\|Q\|_{Fr,\nu}\leqslant 1$.

It follows by definition of $\Lambda_{S}$ that

where the inequality is the definition of convexity. Taking the expectation over $\mathcal{I}\sim\nu$ gives us that $\|(Q_{S})_{+}\|_{Fr,\nu}^{2}\leqslant\|Q_{+}\|_{Fr,\nu}^{2}\leqslant 1$, which gives us our contradiciton. ∎

We will exploit the crucial property that $\Lambda$ and $P$ are averages over functions that depend on subsets of variables. This has the same effect as a random restriction, in that $\langle P,R\rangle_{\nu}$ essentially depends on the low-degree part of $R$. Formally, we will show the following lemma.

We first re-express the left-hand side as

Expressing $R^{\geqslant D}(\mathcal{I})$ in the Fourier basis, we have that over a random choice of $S\sim\Theta$,

Substituting into the above inequality, the conclusion follows. ∎

Since $\Lambda$ is close to satisfying all the equality constraints $\mathcal{G}$ of the SDP, the function $P$ approximately satisfies the low-degree part of $\mathcal{G}$. Specifically, we can prove the following.

Now we make the following claim regarding the effect of projection on to the ideal $\mathcal{G}$, on the degree of a polynomial.

For every polynomial $Q$, $\deg(\Pi_{\mathcal{G}}Q)\leqslant\deg(Q)+2k$. Furthermore for all $\alpha$, $\Pi_{\mathcal{G}}Q^{>\alpha}$ has no monomials of degree $\leqslant\alpha-k$

where the final equality is because $\deg(\chi_{S})>\deg(G_{j})+\deg(Q)$. On the other hand, for every subset $S$ with $\deg(\chi_{S})\leqslant\alpha-k$,

Incorporating the above claim into (4.3), we have that

where we have used the fact that $(\Pi_{\mathcal{G}}G^{\geqslant D-2k})^{[D-3k,D]}$ is high degree. By property of orthogonal projections, $\|\Pi_{\mathcal{G}}G^{\geqslant D-2k}\|_{Fr,\nu}\leqslant\|G^{\geqslant D-2k}\|_{Fr,\nu}\leqslant\|G\|_{Fr,\nu}$. Along with the bound on $\lVert P_{S}\rVert_{Fr,\nu}$ from (4.2), this implies the claim of the lemma. ∎

Finally, we have all the ingredients to complete the proof of Theorem 2.6.

Suppose we sample an instance $\mathcal{I}\sim\nu$, and suppose by way of contradiction this implies that with high probability the SoS SDP relaxation is infeasible. In particular, this implies that there is a degree-$d$ sum-of-squares refutation of the form,

where $G^{\mathcal{I}}\in\mathcal{G}$, the span of the equality constraints of the SDP.

With this notation, we can rewrite the sos-refutation identity as a polynomial identity in $X$ and $\mathcal{I}$,

Let $\mathbf{e}_{\emptyset,\emptyset}$ denote the $[n]^{\leqslant d}\times[n]^{\leqslant d}$ matrix with the entry corresponding to $(\emptyset,\emptyset)$ equal to $1$, while the remaining entries are zero. We can rewrite the above equality as,

for all $\mathcal{I}$ and formal variables $X$.

where the inequality follows because $A,P\succeq 0$. We will show that the above equation is a contradiction by proving that LHS is less than $-0.9$, while the right hand side is at least $-0.5$. First, the right hand side of (4.4) can be bounded by Lemma 4.7

where the last step used the bounds on $\lVert P_{S}\rVert_{Fr,\nu}$ from (4.2) and on $\lVert G\rVert_{Fr,\nu}$ from the $n^{B}$ bound assumed on the SoS proofs in Theorem 2.6.

Now the negation of the left hand side of (4.4) is

We have the desired contradiction in (4.4). ∎

1 Handling Inequalities

Suppose the polynomial system Program 2.2 includes inequalities of the form $h(\mathcal{I},x)\geqslant 0$, then a natural approach would be to introduce a slack variable $z$ and set $h(\mathcal{I},x)-z^{2}=0$. Now, we can view the vector $(x,z)$ consisting of the original variables along with the slack variables as the hidden planted solution. The proof of Theorem 2.6 can be carried out as described earlier in this section, with this setup. However, in many cases of interest, the inclusion of slack variables invalidates the robust inference property. This is because, although a feasible solution $x$ can be recovered from a subinstance $\mathcal{I}_{S}$, the value of the corresponding slack variables could potentially depend on $\mathcal{I}_{\overline{S}}$. For instance, in a random CSP, the value of the objective function on the assignment $x$ generated from $\mathcal{I}_{S}$ depends on all the constraints outside of $S$ too.

The proof we described is to be modified as follows.

As earlier, construct $\Lambda_{S}$ using only the robust inference property of original variables $x$, and the corresponding matrix functions $P_{S}$.

Convert each inequality of the form $h_{i}(\mathcal{I},x)\geqslant 0$, in to an equality by setting $h_{i}(\mathcal{I},x)=z_{i}^{2}$.

Intuitively, the pseudo-distribution picks the sign for each $z_{i}$ uniformly at random, independent of all other variables. Therefore, all moments involving an odd power of $z_{i}$ are zero. On the other hand, the moments of even powers of $z_{i}$ are picked so that the equalities $h_{i}(\mathcal{I},x)=z_{i}$ are satisfied.

The main ingredient of the proof that is different from the case of equalities is the random restriction lemma which we outline below. The error in the random restriction is multiplied by $D^{dk/2}\leqslant n^{B/2}$; however this does not substantially change our results, since Theorem 2.6 requires $\rho(D,\Theta)<n^{-8B}$, which leaves us enough slack to absorb this factor (and in every application $\rho(D,\Theta)=p^{O(D)}$for some $p<1$ sufficiently small that we meet the requirement that $D^{dk}\rho(D-dk,\Theta)$ is monotone non-increasing in $D$).

and the additional requirement that $D^{dk}\cdot\rho(D-dk,\Theta)$ is monotone non-increasing in $D$, then

where we have used that $D^{dk}\rho(D-dk,\Theta)$ is a monotone non-increasing function of $D$. Substituting this in the earlier inequality the Lemma follows. ∎

Applications to Classical Distinguishing Problems

In this section, we verify that the conditions of Theorem 2.6 hold for a variety of canonical distinguishing problems. We’ll rely upon the (simple) proofs in Appendix A, which show that the ideal term of the SoS proof is well-conditioned.

Given a graph $G=(V,E)$ on $n$ vertices, determine whether it comes from:

Uniform Distribution: the uniform distribution over graphs on $n$ vertices ($G(n,\tfrac{1}{2})$).

Planted Distribution: the uniform distribution over $n$-vertex graphs with a clique of size at least $n^{\delta}$

The usual polynomial program for planted clique in variables $x_{1},\ldots,x_{n}$ is:

Theorem 2.6 applies to the above planted clique program, so long as $\operatorname{obj}\leqslant n^{\delta-\varepsilon}$ for any $\varepsilon\geqslant\frac{c\cdot d}{D-6d}$ for a fixed constant $c$.

For planted clique, for our notion of “instance degree”, rather than the multiplicity of instance variables, the “degree” of $\mathcal{I}_{\alpha}$ will be the number of distinct vertices incident on the edges in $\alpha$. The proof of Theorem 2.6 proceeds identically with this notion of degree, but we will be able to achieve better bounds on $D$ relative to $d$.

In this case, the instance degree of the SoS relaxation is $k=2$. We have from Corollary A.3 that the degree-$d$ SoS refutation is well-conditioned, with numbers bounded by $n^{c_{1}\cdot d}$ for some constant $c_{1}/2$. Define $B=c_{1}d\geqslant dk$.

Our subsampling distribution $\Theta$ is the distribution given by including every vertex with probability $\rho$, producing an induced subgraph of $\approx\rho n$ vertices. For any set of edges $\alpha$ of instance degree at most $D-6d$,

since the instance degree corresponds to the number of vertices incident on $\alpha$.

This subsampling operation satisfies the subsample inference condition for the clique constraints with probability $1$, since a clique in any subgraph of $G$ is also a clique in $G$. Also, if there is a clique of size $n^{\delta}$ in $G$, then by a Chernoff bound

Choosing $\beta=\sqrt{\frac{10B\log n}{\rho n^{\delta}}}$, this gives us that $\Theta$ gives $n^{-10B}$-robust inference for the planted clique problem, so long as $\operatorname{obj}\leqslant\rho n/2$. Choosing $\rho=n^{-\varepsilon}$ for $\varepsilon$ so that

for some constant $c_{2}$, all of the conditions required by Theorem 2.6 now hold. ∎

Given an instance of a Boolean $k$-CSP with predicate $P:\{\pm 1\}^{k}\to\{\pm 1\}$ on $n$ variables with clause set $C$, determine whether it comes from:

Uniform Distribution: $m\approx\alpha n$ constraints are generated as follows. Each $k$-tuple of variables $S\in[n]^{k}$ is independently with probability $p=\alpha n^{-k+1}$ given the constraint $P(x_{S}\circ z_{S})=b_{S}$ (where $\circ$ is the entry-wise multiplication operation) for a uniformly random $z_{S}\in\{\pm 1\}^{k}$ and $b_{S}\in\{\pm 1\}$.

Planted Distribution: a planted solution $y\in\{\pm 1\}^{n}$ is chosen, and then $m\approx\alpha n$ constraints are generated as follows. Each $k$-tuple of variables $S\in[n]^{k}$ is independently with probability $p=\alpha n^{-k+1}$ given the constraint $P(x_{S}\circ z_{S})=b_{S}$ for a uniformly random $z_{S}\in\{\pm 1\}^{k}$, but $b_{S}=P(y_{S}\circ z_{S})$ with probability $1-\delta$ and $b_{S}$ is uniformly random otherwise.

The usual polynomial program for random CSP refutation in variables $x_{1},\ldots,x_{n}$ is:

If $\alpha\geqslant 1$, then Theorem 2.6 applies to the above random $k$-CSP refutation problem, so long as $\operatorname{obj}\leqslant(1-\delta-\varepsilon)m$ for any $\varepsilon\geqslant\frac{c\cdot d\log n}{D-3d}$, where $c$ is a fixed constant.

In this case, the instance degree of the SoS relaxation $k=1$. We have from Corollary A.3 that the degree-$d$ SoS refutation is well-conditioned, with numbers bounded by $n^{c_{1}d}$ for some constant $c_{1}$. Define $B=c_{1}d$.

Our subsampling distribution $\Theta$ is the distribution given by including each constraint independently with probability $\rho$, producing an induced CSP instance on $n$ variables with approximately $\rho m$ constraints. Since each constraint survives the subsampling with probability $\rho$, for any $\alpha\in\binom{C}{D-3d}$,

The subsample inference property clearly holds for the boolean constraints $\{x_{i}^{2}=1\}_{i\in[n]}$, as a Boolean assignment to the variables is valid regardless of the number of constraints. Before subsampling there are at least $(1-\delta)m$ satisfied constraints, and so letting $O_{S}$ be the number of constraints satisfied in sub-instance $S$, we have by a Chernoff bound

for some constant $c_{2}$. The conclusion follows (after making appropriate adjustments to the constant). ∎

Given a graph $G=(V,E)$ on $n$ vertices, determine whether it comes from:

Uniform Distribution: $G(n,b/n)$, the distribution over graphs in which each edge is included independently with probability $b/n$.

Planted Distribution: the stochastic block model—there is a partition of the vertices into two equally-sized sets, $Y$ and $Z$, and the edge $(u,v)$ is present with probability $a/n$ if $u,v\in Y$ or $u,v\in Z$, and with probability $(b-a)/n$ otherwise.

Letting $x_{1},\ldots,x_{n}$ be variables corresponding to the membership of each vertex’s membership, and let $A$ be the adjacency of the graph. The canonical polynomial optimization problem is

Theorem 2.6 applies to the community detection problem so long as $\operatorname{obj}\leqslant(1-\varepsilon)\frac{(2a-b)}{4}n$, for $\varepsilon>\frac{c\cdot d\log n}{D-3d}$ where $c$ is a fixed constant.

The degree of the SoS relaxation in the instance is $k=1$. Since we have only hypercube and balancedness constraints, we have from Corollary A.3 that the SoS ideal matrix is well-conditioned, with no number in the SoS refutation larger than $n^{c_{1}d}$ for some constant $c_{1}$. Let $B=c_{1}d$.

Consider the solution $x$ which assigns $x_{i}=1$ to $i\in Y$ and $x_{i}=-1$ to $i\in Z$. Our subsampling operation is to remove every edge independently with probability $1-\rho$. The resulting distribution $\Theta$ and the corresponding restriction of $x$ clearly satisfies the Booleanity and balancedness constraints with probability $1$. Since each edge is included independently with probability $\rho$, for any $\alpha\in\binom{E}{D-3d}$,

In the sub-instance, the expected value (over the choice of planted instance and over the choice of sub-instance) of the restricted solution $x$ is

and by a Chernoff bound, the value in the sub instance is within a $(1-\beta)$-factor with probability $1-n^{-10B}$ for $\beta=\sqrt{\frac{10B\log n}{n}}$. On resampling the edges outside the sub-instance from the uniform distribution, this value can only decrease by at most $(1-\rho)(1+\beta)nb/2$ w.h.p over the choice of the outside edges.

If we set $\rho=(1-\varepsilon(2a-b)/10b)$, then $\rho^{D-3d}\leqslant n^{-8B}$ for $\varepsilon\geqslant\frac{c_{2}(2a-b)\log n}{D-3d}$. for some constant $c_{2}$, while the objective value is at least $(1-\varepsilon)\frac{(2a-b)n}{4}$. The conclusion follows (after making appropriate adjustments to the constant). ∎

Given a graph $G=(V,E)$ on $n$ vertices, determine whether it comes from:

Planted Distribution: A graph from $G(n,p)$ with an instance of $G(k,q)$ planted on a random subset of $k$ vertices, $p<q$.

Letting $A$ be the adjacency matrix, the usual polynomial program for densest-$k$-subgraph in variables $x_{1},\ldots,x_{n}$ is:

When $k^{2}(p+q)\gg d\log n$, Theorem 2.6 applies to the densest-k-subgraph problem with $\operatorname{obj}\leqslant(1-\varepsilon)(p+q)\binom{k}{2}$ for any $\varepsilon>\frac{c\cdot d\log n}{D-3d}$ for a fixed constant $c$.

The degree of the SoS relaxation in the instance is $k=1$. We have from Corollary A.3 that the SoS proof has no values larger than $n^{c_{1}d}$ for a constant $c_{1}$; fix $B=c_{1}d$.

Our subsampling operation is to include each edge independently with probability $\rho$, and take the subgraph induced by the included edges. Clearly, the Booleanity and sparsity constraints are preserved by this subsampling distribution $\Theta$. Since each edge is included independently with probability $\rho$, for any $\alpha\in\binom{E}{D-3d}$,

Now, the expected objective value (over the instance and the sub-sampling) is at least $\rho(p+q)\binom{k}{2}$, and applying a Chernoff bound, we hace that the probability the sub-sampled instance has value less than $(1-\beta)\rho(p+q)\binom{k}{2}$ is at most $n^{-10B}$ if we choose $\beta=\sqrt{\frac{10B\log n}{\rho(p+q)\binom{k}{2}}}$ (which is valid since we assumed that $d\log n\ll(p+q)k^{2}$). Further, a dense subgraph on a subset of the edges is still dense when more edges are added back, so we have the $n^{-10B}$-robust inference property.

Thus, choosing $\rho=(1-\varepsilon)$ and setting

for some constant $c_{2}$, which concludes the proof (after making appropriate adjustments to the constant). ∎

Uniform Distribution: each entry of the tensor sampled independently from $\mathcal{N}(0,1)$.

Planted Distribution: a spiked tensor, $\mathbf{T}=\lambda\cdot v^{\otimes k}+G$ where $v$ is sampled uniformly from $\{\pm\frac{1}{\sqrt{n}}\}^{n}$, and where $G$ is a random tensor with each entry sampled independently from $\mathcal{N}(0,1)$.

Given the tensor $\mathbf{T}$, the canonical program for the tensor PCA problem in variables $x_{1},\ldots,x_{n}$ is:

For $\lambda n^{-\varepsilon}\gg\log n$, Theorem 2.6 applies to the tensor PCA problem with $\operatorname{obj}\leqslant\lambda n^{-\varepsilon}$ for any $\varepsilon\geqslant\frac{c\cdot d}{D-3d}$ for a fixed constant $c$.

The degree of the SoS relaxation in the instance is $k=1$. Since the entries of the noise component of the tensor are standard normal variables, with exponentially good probability over the input tensor $\mathbf{T}$ we will have no entry of magnitude greater than $n^{d}$. This, together with Corollary A.3, gives us that except with exponentially small probability the SoS proof will have no values exceeding $n^{c_{1}d}$ for a fixed constant $c_{1}$.

Our subsampling operation is to set to zero every entry of $\mathbf{T}$ independently with probability $1-\rho$, obtaining a sub-instance $\mathbf{T}^{\prime}$ on the nonzero entries. Also, for any $\alpha\in\binom{[n]^{k}}{D-3d}$,

This subsampling operation clearly preserves the planted solution unit sphere constraint. Additionally, let $\mathcal{R}$ be the operator that restricts a tensor to the nonzero entries. We have that $\langle\mathcal{R}(\lambda\cdot v^{\otimes k}),v^{\otimes k}\rangle$ has expectation $\lambda\cdot\rho$, since every entry of $v^{\otimes k}$ has magnitude $n^{-k/2}$. Applying a Chernoff bound, we have that this quantity will be at least $(1-\beta)\lambda\rho$ with probability at least $n^{-10B}$ if we choose $\beta=\sqrt{\frac{10B\log n}{\lambda\rho}}$.

Now, we set $\rho=n^{-\varepsilon}$ so that

which concludes the proof (after making appropriate adjustments to the constant $c_{1}$). ∎

Uniform Distribution: each entry of the matrix sampled independently from $\mathcal{N}(0,1)$.

The canonical program for the sparse PCA problem in variables $x_{1},\ldots,x_{n}$ is:

For $kn^{-\varepsilon/2}\gg\log n$, Theorem 2.6 applies to the sparse PCA problem with $\operatorname{obj}\leqslant k^{2-\varepsilon}m$ for any $\varepsilon>\frac{c\cdot d}{D-6d}$ for a fixed constant $c$.

The degree of the SoS relaxation in the instance is $2$. Since the entries of the noise are standard normal variables, with exponentially good probability over the input matrix $M$ we will have no entry of magnitude greater than $n^{d}$. This, together with Corollary A.3, gives us that except with exponentially small probability the SoS proof will have no values exceeding $n^{c_{1}d}$ for a fixed constant $c_{1}$.

Our subsampling operation is to set to zero every entry of $M$ independently with probability $1-\rho$, obtaining a sub-instance $M$ on the nonzero entries. Also, for any $\alpha\in\binom{M}{D-6d}$,

This subsampling operation clearly preserves the constraints on the solution variables.

where $G^{T}$ is a random Gaussian matrix. Therefore, the objective value obtained by the solution $y=\sqrt{k}v$ is

The first term is a vector $u_{signal}$ with $m$ entries, each of which is a sum of $k$ Bernoulli random variables, all of the same sign, with probability $\rho$ of being nonzero. The second term is a vector $u_{noise}$ with $m$ entries, each of them an independent Gaussian variable with variance bounded by $k$. We have that

and by Chernoff bounds we have that this concentrates within a $(1-\beta)$ factor with probability $1-n^{-10B}$ if we take $\beta=\sqrt{\frac{10B\log n}{(\rho k)^{2}m}}$.

The expectation of $\langle u_{signal},u_{noise}\rangle$ is zero, and applying similar concentration arguments we have that with probability $1-n^{10B}$, $|\langle u_{signal},u_{noise}\rangle|\leqslant(1+\beta)\rho k$. Taking the union bound over these events and applying Cauchy-Schwarz, we have that

so long as $\rho k\gg 1$, the first term dominates.

Now, we set $\rho=n^{-\varepsilon}$ for $\varepsilon<1$ so that

for some constant $c_{2}$, which concludes the proof. ∎

For tensor PCA and sparse PCA, the underlying distributions were Gaussian. Applying Theorem 2.6 in these contexts yields the existence of distinguishers that are low-degree in a non-standard sense. Specifically, the degree of a monomial will be the number of distinct variables in it, irrespective of the powers to which they are raised.

Exponential lower bounds for PCA problems

In this section we give an overview of the proofs of our SoS lower bounds for the tensor and sparse PCA problems. We begin by showing how Conjecture 1.2 predicts such a lower bound in the tensor PCA setting. Following this we state the key lemmas to prove the exponential lower bounds; since these lemmas can be proved largely by techniques present in the work of Barak et al. on planted clique [BHK+16], we leave the details to a forthcoming full version of the present paper.

In this section we demonstrate how to predict using Conjecture 1.2 that when $\lambda\ll n^{3/4-\varepsilon}$ for $\varepsilon>0$, SoS algorithms cannot solve Tensor PCA. This prediction is borne out in Theorem 1.4.

We sketch the proof of this theorem. The theorem follows from two claims.

where $\nu^{\leqslant d}$ is the orthogonal projection (with respect to $\mu$) of the density $\nu$ to the degree-$d$ polynomials. Note that the last quantity is just the $2$ norm, or the variance, of the truncation to low-degree polynomials of the density $\nu$ of the planted distribution.

The theorem follows immediately. We sketch proofs of the claims in order.

Then the best $p$ (ignoring normalization momentarily) will be the function

The following fact, used to prove Claim 6.3, is an elementary computation with Hermite polynomials.

Let $W\subseteq[n]^{3}$. Then $\widehat{\nu}(W)=\lambda^{|W|}n^{-3|W|/2}$ if $W$, thought of as a $3$-uniform hypergraph, has all even degrees, and is otherwise.

What is the contribution to $\sum_{1\leqslant|W|\leqslant d}\widehat{\nu}(W)^{2}$ of terms $W$ with $|W|=t$? By the fact above, to contribute a nonzero term to the sum, $W$,considered as a $3$-uniform hypergraph must have even degrees. So, if it has $t$ hyperedges, it contains at most $3t/2$ nodes. There are $n^{3t/2}$ choices for these nodes, and having chosen them, at most $t^{O(t)}$ $3$-uniform hypergraphs on those nodes. Hence,

So long as $\lambda^{2}\leqslant n^{3/2-\varepsilon}$ for some $\varepsilon=\Omega(1)$ and $t\leqslant d\leqslant n^{O(\varepsilon)}$, this is $o(1)$. ∎

2 Main theorem and proof overview for Tensor PCA

In this section we give an overview of the proof of Theorem 1.4. The techniques involved in proving the main lemmas are technical refinements of techniques used in the work of Barak et al. on SoS lower bounds for planted clique [BHK+16]; we therefore leave full proofs to a forthcoming full version of this paper.

To state and prove our main theorem on tensor PCA it is useful to define a Boolean version of the problem. For technical convenience we actually prove an SoS lower bound for this problem; then standard techniques (see Section C) allow us to prove the main theorem for Gaussian tensors.

the uniform distribution: $A\sim\Omega$ chosen uniformly at random.

the planted distribution: Choose $v\sim\{\pm 1\}^{n}$ and let $B=v^{\otimes k}$. Sample $A$ by rerandomizing every coordinate of $B$ with probability $1-\lambda n^{-k/2}$.

We show that the natural SoS relaxation of this problem suffers from a large integrality gap, when $\lambda$ is slightly less than $n^{k/4}$, even when the degree of the SoS relaxation is $n^{\Omega(1)}$. (When $\lambda\gg n^{k/4-\varepsilon}$, algorithms with running time $2^{n^{O(\varepsilon)}}$ are known for $k=O(1)$ [RM14, HSS15, HSSS16, BGL16, RRS16].)

There is a constant $c$ so that for every small enough $\varepsilon>0$, if $d\leqslant n^{c\cdot\varepsilon}$, then for large enough $n$,

Moreover, the latter also holds for $A$ with iid entries from $\mathcal{N}(0,1)$.For technical reasons we do not prove a tail bound type statement for Gaussian $A$, but we conjecture that this is also true.

The Planted Distribution: Choose $v\sim\{\pm 1\}^{n}$ uniformly. Let $B=v^{\otimes k}$. Sample $A$ by

replacing every coordinate of $B$ with a random draw from $\{\pm 1\}$ independently with probability $1-\lambda n^{-k/2}$,

then choosing a subset $S\subseteq[n]$ by including every coordinate with probability $n^{-\varepsilon}$,

then replacing every entry of $B$ with some index outside $S$ independently with a uniform draw from $\{\pm 1\}$.

For a tensor $A$, the moment matrix of the pseudodistribution we exhibit will be $\Lambda^{\leqslant D}(A)$. We will need it to satisfy the constraint $\{\|x\|^{2}=1\}$. This follows from the following general lemma. (The lemma is much more general than what we state here, and uses only the vector space structures of space of real matrices and matrix-valued functions.)

Last, we will require a couple of scalar functions of $\Lambda^{\leqslant D}$ to be well concentrated.

Let $\Lambda,d,\varepsilon,D$ be as in Lemma 6.7. The function $\Lambda^{\leqslant D}$ satisfies