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

arXiv:1710.05017v1 [] 13 Oct 2017

Samuel B. Hopkins∗
Prasad Raghavendra

Pravesh K. Kothari †
Tselil Schramm‡

Aaron Potechin
David Steurer§

October 31, 2017

Abstract
We study planted problems—ﬁnding hidden structures in random noisy inputs—through
the lens of the sum-of-squares semideﬁnite programming hierarchy (SoS). This family of powerful semideﬁnite programs has recently yielded many new algorithms for planted problems,
often achieving the best known polynomial-time guarantees in terms of accuracy of recovered
solutions and robustness to noise. One theme in recent work is the design of spectral algorithms which match the guarantees of SoS algorithms for planted problems. Classical spectral
algorithms are often unable to accomplish this: the twist in these new spectral algorithms is
the use of spectral structure of matrices whose entries are low-degree polynomials of the input
variables.
We prove that for a wide class of planted problems, including refuting random constraint
satisfaction problems, tensor and sparse PCA, densest-k-subgraph, community detection in
stochastic block models, planted clique, and others, eigenvalues of degree-d matrix polynomials
are as powerful as SoS semideﬁnite programs of size roughly n d . For such problems it is
therefore always possible to match the guarantees of SoS without solving a large semideﬁnite
program.
Using related ideas on SoS algorithms and low-degree matrix polynomials (and inspired
by recent work on SoS and the planted clique problem [BHK+ 16]), we prove new nearly-tight
SoS lower bounds for the tensor and sparse principal component analysis problems. Our
lower bounds are the ﬁrst to suggest that improving upon the signal-to-noise ratios handled by
existing polynomial-time algorithms for these problems may require subexponential time.

∗ Cornell

University, samhop@cs.cornell.edu Partially supported by an NSF GRFP under grant no. 1144153, by a
Microsoft Research Graduate Fellowship, and by David Steurer’s NSF CAREER award.
† Princeton University and IAS, kothari@cs.princeton.edu
‡ UC Berkeley, tscrhamm@cs.berkeley.edu. Supported by an NSF Graduate Research Fellowship (1106400).
§ Cornell University, dsteurer@cs.cornell.edu. Supported by a Microsoft Research Fellowship, a Alfred P. Sloan
Fellowship, an NSF CAREER award, and the Simons Collaboration for Algorithms and Geometry.

Contents
1 Introduction
1.1 SoS and spectral algorithms for robust inference . . . . . .
1.2 SoS and information-computation gaps . . . . . . . . . . .
1.3 Exponential lower bounds for sparse PCA and tensor PCA
1.4 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

2 Distinguishing Problems and Robust Inference
3 Moment-Matching Pseudodistributions

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

1
2
4
5
8
9
9
12

4 Proof of Theorem 2.6
15
4.1 Handling Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5 Applications to Classical Distinguishing Problems

23

6 Exponential lower bounds for PCA problems
29
6.1 Predicting sos lower bounds from low-degree distinguishers for Tensor PCA . . . . . 29
6.2 Main theorem and proof overview for Tensor PCA . . . . . . . . . . . . . . . . . . . . 31
6.3 Main theorem and proof overview for sparse PCA . . . . . . . . . . . . . . . . . . . . 33
References

35

A Bounding the sum-of-squares proof ideal term

40

B Lower bounds on the nonzero eigenvalues of some moment matrices

43

C From Boolean to Gaussian lower bounds

45

1 Introduction
Recent years have seen a surge of progress in algorithm design via the sum-of-squares (SoS)
semideﬁnite 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 eﬃcient 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 semideﬁnite program (SDP) [LRS15].
In this paper we focus on recent progress in using Sum of Squares algorithms to solve averagecase, and especially planted problems—problems that ask for the recovery of a planted signal
perturbed by random noise. Key examples are ﬁnding solutions of random constraint satisfaction
problems (CSPs) with planted assignments [RRS16] and ﬁnding 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—semideﬁnite programs are strictly more powerful than spectral algorithms.1 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 semideﬁnite 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 aﬃrmatively 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
1For 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.

1

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
semideﬁnite 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 ﬁnd 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 suﬃcient 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 SoS lower bounds for both problems are the strongest yet formal evidence for informationcomputation gaps for these problems. We rule out the possibility of subexponential-time SoS
algorithms which improve by polynomial factors on the signal-to-noise ratios tolerated by the
known low degree spectral methods. In particular, in the case of sparse PCA, it appeared possible
prior to this work that it might be possible in quasipolynomial time to recover a k-sparse unit vector
v in p dimensions from O(k log p) samples from the distribution N(0, Id +vv ⊤ ). Our lower bounds
suggest that this is extremely unlikely; in fact this task probably requires polynomial SoS degree
and hence exp(n Ω(1) ) time for SoS algorithms. This demonstrates that (at least with regard to SoS
algorithms) both problems are much harder than the planted clique problem, previously used as a
basis for reductions in the setting of sparse PCA [BR13b].
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 × 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.

1.1 SoS and spectral algorithms for robust inference
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 speciﬁed 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 12 whether or not
2

the instance comes from the planted distribution. For example:
Planted clique Uniform distribution:
G(n, 12 ), the Erdős-Renyi distribution, which w.h.p.
contains no clique of size ω(log n). Planted distribution: The uniform distribution on graphs
containing a n ε -size clique, for some ε > 0. (The problem gets harder as ε gets smaller, since the
distance between the distributions shrinks.)
Planted 3xor Uniform distribution: a 3xor instance on n variables and m > n equations
x i x j x k  a i jk , where all the triples (i, j, k) and the signs a i jk ∈ {±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 i jk are sampled to correlate with b i b j b k for a
randomly chosen b i ∈ {±1}, so that the assignment x  b satisﬁes 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 deﬁne a family of distinguishing problems, in order to give our main theorem.
Let I be a set of instances corresponding to a product space (for concreteness one may think of
n
I to be the set of graphs on n vertices, indexed by {0, 1}( 2 ) , although the theorem applies more
broadly). Let ν, our uniform distrbution, be a product distribution on I.
With some decision problem P in mind (e.g. does G contain a clique of size > n ε ?), let X be a
set of solutions to P; again for concreteness one may think of X as being associated with cliques
in a graph, so that X ⊂ {0, 1} n is the set of all indicator vectors on at least n ε vertices.
For each solution x ∈ X, let µ |x be the uniform distribution over instances I ∈ I that contain x.
For example, in the context of planted clique, if x is a clique on vertices 1, . . . , n ε , then µ |x would
be the uniform distribution on graphs containing the clique 1, . . . , n ε . We deﬁne the planted
distribution µ to be the uniform mixture over µ x , µ  U x∼X µ |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.
Theorem 1.1 (Informal). Let N, n ∈ N, and let A, B be sets of real numbers. Let I be a family of
instances over A N , and let P be a decision problem over I with X  B n the set of possible solutions to P
over I. Let {1 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 I that encodes P, so that
• for I ∼ν I, with high probability the system is unsatisﬁable and admits a degree-d SoS refutation, and
• for I ∼µ I, with high probability the system is satisﬁable by some solution x ∈ X, and x remains
feasible even if all but an n −0.01 -fraction of the coordinates of I are re-randomized according to ν.
n
n
Then there exists a matrix whose entries are degree-O(d) polynomials Q : I → (6 d)×(6 d) such that

I∼ν





λ +max (Q(I)) 6 1,

while

I∼µ

where λ +max denotes the maximum non-negative eigenvalue.





λ +max (Q(I)) > n 10d ,

The condition that a solution x remain feasible if all but a fraction of the coordinates of I ∼ µ |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 ε+0.01 . If a random subset of n 0.99 vertices are chosen, and all edges not entirely
3

contained in that subset are re-randomized according to the G(n, 1/2) distribution, then with high
probability at least n ε of the vertices in x remain in a clique, and so x remains feasible for the
problem P: G has a clique of size > n ε ?

1.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 eﬃcient (polynomial time) algorithms, and to study the
information-computation gap phenomenon: many problems have noisy regimes in which planted
structures can be found by ineﬃcient algorithms, but (conjecturally) not by polynomial time
algorithms. One example is the planted clique problem, where the goal ﬁnd a large clique in
a sample from the uniform distribution over graphs containing a clique of size n ε for a small
constant ε > 0. While the problem is solvable for any ε > 0 by a brute-force algorithm requiring
n Ω(log n) time, polynomial time algorithms are conjectured to require ε > 21 .
A common strategy to provide evidence for such a gap is to prove that powerful classes of
eﬃcient 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.
In a recent work, Barak et al. [BHK+ 16] show an SoS lower bound for the planted clique
problem, demonstrating that when ε < 12 , SoS algorithms require n Ω(log n) time to solve planted
clique. Intriguingly, they show that in the case of planted clique that SoS algorithms requiring
≈ n d time can distinguish planted from random graphs only when there is a scalar-valued degree
≈ d · log n polynomial p(A) : n×n →  (here A is the adjacency matrix of a graph) with
G(n,1/2)

p(A)  0,

planted

p(A) > n

Ω(1)

·




G(n,1/2)

p(A)

 1/2

.

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 Ω(1) is somewhat arbitrary, and
could be replaced with Ω(1) or n Ω(d) with small changes in the parameters.) By showing that
as long as ε < 21 any such polynomial p must have degree Ω(log n)2 , they rule out eﬃcient SoS
algorithms when ε < 12 . Interestingly, this matches the spectral distinguishing threshold—the
spectral algorithm of [AKS98] is known to work when ε > 21 .
This stronger characterization of SoS for the planted clique problem, in terms of scalar distinguishing algorithms rather than spectral distinguishing algorihtms, may at ﬁrst seem insigniﬁcant.
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 µ and a random distribution ν over instances I,
one just solves a linear algebra problem in the n d log n coeﬃcients of p to maximize the expectation
over µ relative to ν:
max
[p 2 (I)] s.t.
[p 2 (I)]  1 .
p

I∼µ

I∼ν

It is not diﬃcult to show that the optimal solution to the above program has a simple form: it is
the projection of the relative density of ν with respect to µ projected to the degree-d log n polynomials.
So given a pair of distributions µ, ν, in n O(d log n) time, it is possible to determine whether there
4

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 eﬃciently.
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 ν and µ with known moments, it would be
possible in many cases to eﬃciently and mechanically determine whether polynomial-time SoS
distinguishing algorithms exist!
Conjecture 1.2. In the setting of Theorem 1.1, the conclusion may be replaced with the conclusion that
there exists a scalar-valued polynomial p : I →  of degree O(d · log n) so that
uniform

p(I)  0 and

planted

p(I) > n

Ω(1)



2

uniform

p(I)

 1/2

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 Ω(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 7→ λ +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 ﬁnal output
of the spectral distinguishing algorithm oﬀered by Theorem 1.1 is not a low-degree polynomial in
the instance I.

1.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 (specifΩ(1)
ically, against 2n time or n Ω(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.
Tensor PCA. We start with the simpler case of tensor PCA, introduced by [RM14].
Problem 1.3 (Tensor PCA). Given an order-k tensor in (n )⊗k , determine whether it comes from:
• Uniform Distribution: each entry of the tensor sampled independently from N(0, 1).
• Planted Distribution: a spiked tensor, T  λ · v ⊗k + G where v is sampled uniformly from
n−1 , and where G is a random tensor with each entry sampled independently from N(0, 1).
Here, we think of v as a signal hidden by Gaussian noise. The parameter λ is a signal-to-noise
ratio. In particular, as λ grows, we expect the distinguishing problem above to get easier.

5

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.
Turning to algorithms: consider ﬁrst the ordinary PCA problem in a spiked-matrix model.
Given an n × n matrix M, the problem is to distinguish between the case where every entry of M
is independently drawn from the standard Gaussian distribution N(0, 1) and the case when M is
drawn from a distribution as above with an added rank one shift λvv ⊤ in a uniformly random
direction v. A natural and well-studied algorithm, which solves this problem to informationtheoretic optimality is to threshold on the largest singular value/spectral norm of the input matrix.
Equivalently, one thresholds on the maximizer of the degree two polynomial hx, Mxi in x ∈ n−1 .
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 hT, x ⊗3i 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 λ ≫ 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 hT, x ⊗3 i 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
λ 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.
Speciﬁcally, 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 λ ≫ n 3/4 [HSS15]. A major
open question in this direction is to understand the complexity of the problem for λ 6 n 3/4−ε .
O(ε)
Algorithms (again captured by SoS) are known which run in 2n
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.
Theorem 1.4. For a tensor T, let
SoS d (T)  max ˜ [hT, x ⊗k i] such that ˜ is a degree d pseudoexpectation and satisﬁes {kx k 2  1}2
˜

For every small enough constant ε > 0, if T ∈ n×n×n has iid Gaussian or {±1} entries,
n k/4−ε , for every d 6 n c·ε for some universal c > 0.

T

SoS d (T) >

In particular for third order tensors (i.e k  3), since degree n Ω(ε) SoS is unable to certify that a
2For deﬁnitions of pseudoexpectations and related matters, see the survey [BS14].

6

random 3-tensor has maximum value much less than n 3/4−ε , this SoS relaxation cannot be used to
distinguish the planted and random distributions above when λ ≪ n 3/4−ε .3
Sparse PCA. We turn to sparse PCA, which we formalize as the following planted distinguishing
problem.
Problem 1.5 (Sparse PCA (λ, k)). Given an n × n symmetric real matrix A, determine whether A
comes from:
• Uniform Distribution: each upper-triangular entry of the matrix A is sampled iid from
N(0, 1); other entries are ﬁlled in to preserve symmetry.
√
• Planted Distribution: a random k-sparse unit vector v with entries {±1/ k, 0} is sampled,
and B is sampled from the uniform distribution above; then A  B + λ · vv⊺ .
We defer signiﬁcant discussion to Section 6, noting just a few things before stating our main
theorem on sparse PCA. First, the planted model above is sometimes called the spiked Wigner
model—this refers to the independence of the entries of the matrix B. An alternative model for
Í
sparse PCA is the spiked Wishart model: A is replaced by i 6 m x i x i⊺ , where each x i ∼ N(0, Id +βvv⊺ ),
for some number m ∈  of samples and some signal-strength β ∈ . Though there are technical
diﬀerences between the models, to the best of our knowledge all known algorithms with provable
guarantees are equally applicable to either model; we expect that our SoS lower bounds also apply
in the spiked Wishart model.
We generally think of k, λ as small powers of n; i.e. n ρ for some ρ ∈ (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 hx, Axi, this time over k-sparse unit vectors. For A from the uniform distribution √
standard
techniques (ε-nets and union bounds) show that the maximum value achievable is O( k log√n)
with high probability, while for A from the planted model of course hv, Avi ≈ λ. So, when λ ≫ 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,
eﬃcient algorithms must use some other distinguisher which leverages the randomness in the
instances. Essentially only two polynomial-time-computable distinguishers are known.4 If λ ≫
√
n then the maximum eigenvalue of A distinguishes the models. If λ ≫ 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 λ (that is, k ≪ λ ≪ n, k) for which brute-force methods
(optimizing hx, Axi 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 k ≪
√
λ ≪ n, k regime. This is the strongest known impossibility result for sparse PCA among those
ruling out classes of eﬃcient 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 ﬁrst evidence
that the problem may require subexponential (as opposed to merely quasi-polynomial) time.
3In 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.
4If one studies the problem at much ﬁner granularity than we do here, in particular studying λ 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].

7

Theorem 1.6. If A ∈ n×n , let



SoS d,k (A)  max ˜ hx, Axi s.t. ˜ is degree d and satisﬁes x 3i  x i , kx k 2  k .
˜

There are absolute constants c, ε ∗ > 0 so that for every ρ ∈ (0, 1) and ε ∈ (0, ε ∗ ), if k  n ρ , then for
d 6 n c·ε ,
SoS d,k (A) > min(n 1/2−ε k, n ρ−ε k) .
n
A∼{±1} ( 2 )

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

1.4 Related work
On interplay of SoS relaxations and spectral methods. 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:5 [BHK+ 16]), strong refutations for random CSPs (upper
bound:6 [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 eﬃcient sum-of-squares algorithms and eﬃcient spectral algorithms, and it remains to
establish exactly what the tradeoﬀ is between eﬃciency of the algorithm and the diﬃculty 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 semideﬁnie 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 semideﬁnite programming relaxations.
On strong SoS lower bounds for planted problems. 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,
5SDP 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.
6There is a long line of work on algorithms for refuting random CSPs, and 3SAT in particular; the listed papers
contain additional references.

8

BHK+ 16]. The recent SoS lower bound for planted clique of [BHK+ 16] was particularly inﬂuential
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.
Tensor principle component analysis was introduced by Montanari and Richard [RM14] who
indentiﬁed information theoretic threshold for recovery of the planted component and analyzed the
maximum likelihood estimator for the problem. The work of [HSS15] began the eﬀort to analyze
the sum of squares method for the problem and showed that it yields an eﬃcient algorithm
for recovering the planted component with strength ω̃(n 3/4 ). They also established that this
threshold is tight for the sum of squares relaxation of degree 4. Following this, Hopkins et al.
[HSSS16] showed how to extract a linear time spectral algorithm from the above analysis. Tomioka
and Suzuki derived tight information theoretic thresholds for detecting planted components by
establishing tight bounds on the injective tensor norm of random tensors [TS14]. Finally, very
recently, Raghavendra et. al. and Bhattiprolu et. al. independently showed sub-exponential time
algorithms for tensor pca [RRS16, BGL16]. Their algorithms are spectral and are captured by the
sum of squares method.

1.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
deﬁnition 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.
def

Notation. For two matrices A, B, let hA, Bi  Tr(AB). Let kAkFr denote the Frobenius norm, and
kAk its spectral norm. For matrix valued functions A, B over I and a distribution ν over I ∼ I,
def

we will denote hA, Biν  I∼ν hA(I), B(I)i and by kAkFr,ν  ( I∼ν hA(I), A(I)i)1/2 .
For a vector of formal variables x  (x1 , . . . , x n ), we use x 6 d to denote the vector consisting of all
def

monomials of degree at most d in these variables. Furthermore, let us denote X 6 d  (x 6 d )(x 6 d )T .

2 Distinguishing Problems and Robust Inference
In this section, we set up the formal framework within which we will prove our main result.
Uniform vs. Planted Distinguishing Problems
We begin by describing a class of distinguishing problems. For A a set of real numbers, we will
use I  A N denote a space of instances indexed by N variables—for the sake of concreteness, it
9



will be useful to think of I as {0, 1} N ; for example, we could have N  n2 and I as the set of
all graphs on n vertices. However, the results that we will show here continue to hold in other
contexts, where the space of all instances is N or [q]N .
Definition 2.1 (Uniform Distinguishing Problem). Suppose that I is the space of all instances, and
suppose we have two distributions over I, a product distribution ν (the “uniform” distribution),
and an arbitrary distribution µ (the “planted” distribution).
In a uniform distinguishing problem, we are given an instance I ∈ I which is sampled with
probability 21 from ν and with probability 12 from µ, and the goal is to determine with probability
greater than 21 + ε which distribution I was sampled from, for any constant ε > 0.
Polynomial Systems
In the uniform distinguishing problems that we are interested in, the planted distribution µ will be
a distribution over instances that obtain a large value for some optimization problem of interest (i.e.
the max clique problem). We deﬁne polynomial systems in order to formally capture optimization
problems.
Program 2.2 (Polynomial System). Let A, B be sets of real numbers, let n, N ∈ , and let I  A N
be a space of instances and X ⊆ B n be a space of solutions. A polynomial system is a set of polynomial
equalities
1 j (x, I)  0 ∀ j ∈ [m],
where {1 j } m
are polynomials in the program variables {x i }i∈[n] , representing x ∈ X, and in the
j1
instance variables {Ij } j∈[N] , representing I ∈ I. We deﬁne degprog (1 j ) to be the degree of 1 j in the
program variables, and deginst (1 j ) to be the degree of 1 j in the instance variables.
Remark 2.3. 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 modiﬁcations
of the proof, as outlined in Section 4.
A polynomial system allows us to capture problem-speciﬁc objective functions as well as
problem-speciﬁc constraints. For concreteness, consider a quadtratic program which checks if a
graph on n vertices contains a clique of size k. We can express this with the polynomial system
n
over program variables x ∈ n and instance variables I ∈ {0, 1}( 2 ) , where Ii j  1 iﬀ there is an
edge from i to j, as follows:

nÕ

i∈[n]

o

x i − k  0 ∪ {x i (x i − 1)  0}i∈[n] ∪ {(1 − Ii j )x i x j  0}i, j∈( [n]) .
2

Planted Distributions
We will be concerned with planted distributions of a particular form; ﬁrst, we ﬁx a polynomial
system of interest S  {1 j (x, I)} j∈[m] and some set X ⊆ B n of feasible solutions for S, so that the
10

program variables x represent elements of X. Again, for concreteness, if I is the set of graphs on
n vertices, we can take X ⊆ {0, 1} n to be the set of indicators for subsets of at least n ε vertices.
For each ﬁxed x ∈ X, let µ |x denote the uniform distribution over I ∈ I for which the
polynomial system {1 j (x, I)} j∈[m] is feasible. The planted distribution µ is given by taking the
uniform mixture over the µ |x , i.e., µ ∼ U x∼X [µ |x ].
SoS Relaxations
If we have a polynomial system {1 j } j∈[m] where degprog (1 j ) 6 2d for every j ∈ [m], then the
degree-2d sum-of-squares SDP relaxation for the polynomial system Program 2.2 can be written
as,
Program 2.4 (SoS Relaxation for Polynomial System). Let S  {1 j (x, I)} j∈[m] be a polynomial
system in instance variables I ∈ I and program variables x ∈ X. If degprog (1 j ) 6 2d for all j ∈ [m],
then an SoS relaxation for S is
hG j (I), Xi  0 ∀ j ∈ [m]

X0

6d

6d

where X is an [n]6 d ×[n]6 d matrix containing the variables of the SDP and G j : I → [n] ×[n] are
matrices containing the coeﬃcients of 1 j (x, I) in x, so that the constraint hG j (I), Xi  0 encodes
the constraint 1 j (x, I)  0 in the SDP variables. Note that the entries of G j are polynomials of
degree at most deginst (1 j ) in the instance variables.
Sub-instances
Suppose that I  A N is a family of instances; then given an instance I ∈ I and a subset S ⊆ [N],
let IS denote the sub-instance consisting of coordinates within S. Further, for a distribution Θ over
subsets of [N], let IS ∼Θ I denote a subinstance generated by sampling S ∼ Θ. Let I↓ denote
the set of all sub-instances of an instance I, and let I↓ denote the set of all sub-instances of all
instances.
Robust Inference
Our result will pertain to polynomial systems that deﬁne planted distributions whose solutions to
sub-instances generalize to feasible solutions over the entire instance. We call this property “robust
inference.”
Definition 2.5. Let I  A N be a family of instances, let Θ be a distribution over subsets of [N], let S
be a polynomial system as in Program 2.2, and let µ be a planted distribution over instances feasible
for S. Then the polynomial system S is said to satisfy the robust inference property for probability
distribution µ on I and subsampling distribution Θ, if given a subsampling IS of an instance I from
µ, one can infer a setting of the program variables x ∗ that remains feasible to S for most settings of
IS .
Formally, there exists a map x : I↓ → n such that


I∼µ,S∼Θ,Ĩ∼ν|IS

[x(IS ) is a feasible for S on IS ◦ Ĩ] > 1 − ε(n, d)
11

for some negligible function ε(n, d). To specify the error probability, we will say that polynomial
system is ε(n, d)-robustly inferable.
Main Theorem
We are now ready to state our main theorem.
Theorem 2.6. Suppose that S is a polynomial system as deﬁned in Program 2.2, of degree at most 2d in the
program variables and degree at most k in the instance variables. Let B > d · k ∈  such that
1. The polynpomial system S is n18B -robustly inferable with respect to the planted distribution µ and the
sub-sampling distribution Θ.
2. For I ∼ ν, the polynomial system S admits a degree-d SoS refutation with numbers bounded by n B
with probability at least 1 − n18B .
Let D ∈  be such that for any subset α ⊆ [N] with |α| > D − 2dk,

 [α ⊆ S] 6

S∼Θ

1
n 8B

There exists a degree 2D matrix polynomial Q : I → [n]
+
I∼µ [λ max (Q(I))]
+
I∼ν [λ max (Q(I))]

6 d ×[n] 6 d

such that,

> n B/2

Remark 2.7. Our argument implies a stronger result that can be stated in terms of the eigenspaces
of the subsampling operator. Speciﬁcally, suppose we deﬁne
def

Sε 



α |  {α ⊆ S} 6 ε
S∼Θ



Then, the distinguishing polynomial exhibited by Theorem 2.6 satisﬁes Q
∈
span{ monomials Iα |α ∈ Sε }. This reﬁnement 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 veriﬁcations 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.

3 Moment-Matching Pseudodistributions
We assume the setup from Section 2: we have a family of instances I  A N , a polynomial system
S  {1 j (x, I)} j∈[m] with a family of solutions X  B n , a “uniform” distribution ν which is a product
distribution over I, and a “planted” distribution µ over I deﬁed by the polynomial system S as
described in Section 2.
12

The contrapositive of Theorem 2.6 is that if S is robustly inferable with respect to µ and a
distribution over sub-instances Θ, and if there is no spectral algorithm for distinguishing µ and
ν, then with high probability there is no degree-d SoS refutation for the polynomial system S (as
deﬁned 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.
Since each I in the support of µ is feasible for S by deﬁnition, a natural starting point is the
6d
6d
SoS SDP solution for instances I ∼µ I. With this in mind, we let Λ : I → ([n] ×[n] )+ be an
arbitrary function from the support of µ over I to PSD matrices. In other words, we take
Λ(I)  µ̂(I) · M(I)
where µ̂ is the relative density of µ with respect to ν, so that µ̂(I)  µ(I)/ν(I), and M is some
matrix valued function such that M(I)  0 and kM(I)k 6 B for all I ∈ I. Our goal is to ﬁnd a
PSD matrix-valued function P that matches the low-degree moments of Λ in the variables I, while
being supported over most of I (rather than just over the support of µ).
6d
6d
The function P : I → ([n] ×[n] )+ is given by the following exponentially large convex
program over matrix-valued functions,
Program 3.1 (Pseudodistribution Program).
min
s.t.

2
kP kFr,ν

(3.1)

hQ, Piν  hQ, Λ′iν

P0

Λ′  Λ + η · Id,

[n]6 d ×[n]6 d

∀Q : I → 
2n

2−2

, deginst (Q) 6 D

>η>0

(3.2)

(3.3)

The constraint (3.2) ﬁxes Tr(P), and so the objective function (3.1) can be viewied as minimizing Tr(P 2 ), a proxy for the collision probability of the distribution, which is a measure of
entropy.
Remark 3.2. We have perturbed Λ 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 η 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.
Program 3.3 (Low-Degree Distinguisher).
max
s.t.

hΛ, Qiν

Q : I → [n]

6 d ×[n] 6 d

2
kQ + kFr,ν
6 1,

, deginst (Q) 6 D

where Q + is the projection of Q to the PSD cone.
Claim 3.4. 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 Ω( c).
13

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.
[n]6 d ×[n]6 d

be such that Id  M  0. Let λ +max (·) be the
Theorem 3.5. Fix a function M : I → +
function that gives the largest non-negative eigenvalue of a matrix. Suppose Λ  µ · M then the optimum
of Program 3.1 is equal to opt > 1 only if there exists a low-degree matrix polynomial Q such that,
I∼µ

p

[λ+max (Q(I))] > Ω( opt/n d )

while,
I∼ν

[λ +max (Q(I))] 6 1 .

Proof. By Claim 3.4, if the value of Program 3.1 is opt > 1, then there is a polynomial Q achieves a
√
value of Ω( opt) for the dual. It follows that

I∼µ

1
nd

[λ +max (Q(I))] >

while
I∼ν

[λ+max (Q(I))]

6

I∼µ

q

[hId, Q(I))i] >

I∼ν

[λ +max (Q(I))2 ]

p
1
hΛ,
Qi

Ω(
opt/n d ),
ν
nd
6

r

I∼ν

2
6 1.
kQ + (I)kFr



It is interesting to note that the speciﬁc 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 ⊗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 ν and µ.
We wrap up the section by presenting a proof of the Claim 3.4.
Proof of 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:
2
L(P, Q, A)  kP kFr,ν
− hQ, P − Λ′iν − hA, Piν

s.t.

A  0.

It is easy to verify that if P is not PSD, then A can be chosen so that the value of L is ∞. Similarly if
there exists a low-degree polynomial upon which P and Λ diﬀer in expectation, Q can be chosen
as a multiple of that polynomial so that the value of L is ∞.
Now, we argue that Slater’s conditions are met for Program 3.1, as P  Λ′ is strictly feasible.
Thus strong duality holds, and therefore
min max L(P, Q, A) 6 max min L(P, Q, A).
P

A0,Q

A0,Q

P

Taking the partial derivative of L(P, Q, A) with respect to P, we have
∂
L(P, Q, A)  2 · P − Q − A.
∂P
14

6d

6d

where the ﬁrst derivative is in the space of functions from I → [n] ×[n] . By the convexity of
∂
L as a function of P, it follows that if we set ∂P
L  0, we will have the minimizer. Substituting, it
follows that
1
1
1
2
kA + Q kFr,ν
− hQ, A + Q − Λ′iν − hA, A + Qiν
4
2
2
1
2
 max hQ, Λ′iν − kA + Q kFr,ν
4
A0,Q

min max L(P, Q, A) 6 max
P

A0,Q

A0,Q

(3.4)

Now it is clear that the maximizing choice of A is to set A  −Q − , the negation of the negativesemi-deﬁnite projection of Q. Thus (3.4) simpliﬁes to
min max L(P, Q, A) 6 max hQ, Λ′iν −
P

A0,Q

Q

1
2
kQ + kFr,ν
4
1
4

2
,
6 max hQ, Λiν + η Trν (Q + ) − kQ + kFr,ν
Q

(3.5)

def

where we have used the shorthand Trν (Q + )  I∼ν Tr(Q(I)+ ). Now suppose that the low-degree
matrix polynomial Q ∗ achieves a right-hand-side value of
1
2
> c.
hQ ∗ , Λiν + η · Trν (Q +∗ ) − kQ +∗ kFr,ν
4
Consider Q ′  Q ∗ /kQ +∗ kFr,ν . Clearly kQ +′ kFr,ν  1. Now, multiplying the above inequality through
by the scalar 1/kQ +∗ kFr,ν , we have that
Trν (Q +∗ )
1
c
−
η
·
+ kQ +∗ kFr,ν
∗
∗
kQ + kFr,ν
kQ + kFr,ν 4
1
c
− η · n d + kQ +∗ kFr,ν .
>
∗
kQ + kFr,ν
4

hQ ′ , Λiν >

√
Therefore hQ ′ , Λiν is at least Ω(c 1/2 ), as if kQ +∗ kFr,ν > c then the third term gives the lower bound,
and otherwise the ﬁrst term gives the lower bound.
Thus by substituting Q ′, the square root of the maximum of (3.5) within an additive ηn d
lower-bounds the maximum of the program
max
s.t.

hQ, Λiν

Q : I → [n]
2
kQ + kFr,ν

6 d ×[n] 6 d

6 1.

This concludes the proof.

,

deginst (Q) 6 D



4 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 ν from µ. First, the lack of distinguishers implies the following fact
about scalar polynomials.
15

Lemma 4.1. Under the assumption that there are no degree-2D distinguishers, for every degree-D scalar
polynomial Q,
2
2
kQ kFr,µ
6 n B kQ kFr,ν
Proof. Suppose not, then the degree-2D 1 × 1 matrix polynomial Tr(Q(I)2 ) will be a distinguisher
between µ and ν.

Constructing Λ. First, we will use the robust inference property of µ to construct a pseudodistribution Λ. Recall again that we have deﬁned µ̂ to be the relative density of µ with respect
to ν, so that µ̂(I)  µ(I)/ν(I). For each subset S ⊆ [N], deﬁne a PSD matrix-valued function
6d
6d
ΛS : I → ([n] ×[n] )+ as,
ΛS (I) 

I′
S

[ µ̂(IS ◦ I ′)] · x(IS )6 d (x(IS )6 d )T
S

where we use IS to denote the restriction of I to S ⊂ [N], and IS ◦ I ′ to denote the instance given by
S
completing the sub-instance IS with the setting I ′. Notice that ΛS is a function depending only on
S
def

IS —this fact will be important to us. Deﬁne Λ 
function that satisﬁes
hΛ∅,∅ , 1iν 

I∼ν S∼Θ I ′ ∼ν
S

S∼Θ ΛS .

[ µ̂(IS ◦ I ′)] 
S

Observe that Λ is a PSD matrix-valued

S IS IS ◦I ′ ∼ν
S

[ µ̂(IS ◦ I ′)]  1
S

(4.1)

Since Λ(I) is an average over ΛS (I), each of which is a feasible solution with high probability,
Λ(I) is close to a feasible solution to the SDP relaxation for I. The following Lemma formalizes
this intuition.
def
Deﬁne G  span{χS · G j | j ∈ [m], S ⊆ [N]}, and use ΠG to denote the orthogonal projection
into G.
Lemma 4.2. Suppose Program 2.2 satisfies the ε-robust inference property with respect to planted distribution µ and subsampling distribution Θ and if kx(IS )6 d k22 6 K for all IS then for every G ∈ G, we
have
! 1/2
√
hΛ, Giν 6 ε · K ·
kG(IS ◦ IS )k22
S∼Θ Ĩ ∼ν I∼µ
S

Proof. We begin by expanding the left-hand side by substituting the deﬁnition of Λ. We have
hΛ, Giν 

S∼Θ I∼ν

hΛS (IS ), G(I)i


S∼Θ I∼ν I ′ ∼ν
S

µ̂(IS ◦ I ′) · hx(IS )6 d (x(IS )6 d )T , G(I)i
S

And because the inner product is zero if x(IS ) is a feasible solution,

6
6

S∼Θ I∼ν

I ′ ∼ν
S

S∼Θ I∼ν I ′ ∼ν
S

µ̂(IS ◦ I ′) · [x(IS ) is infeasible for S(I)] · x(IS )6 d
S

2
2

· kG(I)kFr

µ̂(IS ◦ I ′) · [x(IS ) is infeasible for S(I)] · K · kG(I)kFr
S

16

And now letting ĨS denote the completion of IS to I, so that IS ◦ ĨS  I, we note that the above
is like sampling I ′ , ĨS independently from ν and then reweighting by µ̂(IS ◦ I ′ ), or equivalently
S

S

taking the expectation over IS ◦ I ′  I ′ ∼ µ and ĨS ∼ ν:
S


S∼Θ I ′ ∼µ Ĩ ∼ν
S

· [x(IS ) is infeasible for S(IS ◦ ĨS )] · K · kG(IS ◦ ĨS )kFr

and by Cauchy-Schwarz,

6K·

S∼Θ I ′ ∼µ Ĩ ∼ν
S

· [x(IS ) is infeasible for S(IS ◦ ĨS )]

! 1/2

·

S∼Θ I ′ ∼µ Ĩ ∼ν
S

2
kG(IS ◦ ĨS )kFr

! 1/2

The lemma follows by observing that the ﬁrst term in the product above is exactly the nonrobustness of inference probability ε.

Corollary 4.3. If G ∈ G is a degree-D polynomial in I, then under the assumption that there are no
degree-2D distinguishers for ν, µ,
hΛ, Giν 6

√

ε · K · n B · kGkFr,ν

Proof. For each ﬁxing of ĨS , kG(IS ◦ ĨS )k22 is a degree-2D-scalar polynomial in I. Therefore by
Lemma 4.1 we have that,
I∼µ

2
kG(IS ◦ ĨS )kFr
6 nB ·

I∼ν

2
kG(IS ◦ ĨS )kFr
.

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 Θ we can
apply reasoning similar to Theorem 3.5 to conclude that there is a high-entropy PSD matrix-valued
function PS that matches the degree-D moments of ΛS .
Lemma 4.4. If there are no degree-D matrix distinguishers Q for µ, ν, then for each S ∼ Θ, there exists a
solution PS to Program 3.1 (with the variable Λ : ΛS ) and
kPS kFr,ν 6 n

(B+d)/4

6 n B/2

(4.2)

This does not follow directly from Theorem 3.5, because a priori a distinguisher for some
speciﬁc S may only apply to a small fraction of the support of µ. However, we can show that
Program 3.1 has large value for ΛS only if there is a distinguisher for µ, ν.
Proof. By Claim 3.4, it suﬃces for us to argue that there is no degree-D matrix polynomial Q which
has large inner product with ΛS relative to its Frobenius norm. So, suppose by way of contradiction
that Q is a degree-D matrix that distinguishes ΛS , so that hQ, ΛS iν > n B+d but kQ kFr,ν 6 1.
It follows by deﬁnition of ΛS that
n B+d 6 hQ, ΛS iν 

I∼ν I ′ ∼ν
S

µ̂(IS ◦ I ′) · hQ(I), x(IS )6 d (x(IS )6 d )⊤ i
S

17





IS ◦I ′ ∼µ IS ∼ν

6

µ



S

λ +max



Q(IS ◦ IS ), x(IS )

IS ∼ν

Q(IS ◦ IS )



6d

(x(IS )

6d ⊤

· x(IS )6 d

)

2
2



.

So, we will show that Q S (I)  I ′∼ν Q(IS ◦ I ′) is a degree-D distinguisher for µ. The degree of Q S
S
S
is at most D, since averaging over settings of the variables cannot increase the degree. Applying
our assumption that kx(IS )6 d k22 6 K 6 n d , we already have µ λ +max (Q S ) > n B . It remains to show
that ν λ +max (Q S ) is bounded. For this, we use the following fact about the trace.
Fact 4.5 (See e.g. Theorem 2.10 in [CC09]). For a function f :  →  and a symmetric matrix A with
Í
Í
eigendecomposition λ · vv ⊤ , define f (A)  f (λ) · vv ⊤ . If f :  →  is continuous and convex, then
the map A → Tr( f (A)) is convex for symmetric A.

The function f (t)  (max{0, t})2 is continuous and convex over , so the fact above implies
2
is convex for symmetric A. We can take Q S to be symmetric without loss
that the map A → kA+ kFr
of generality, as in the argument above we only consider the inner product of Q S with symmetric
matrices. Now we have that
k(Q S (I))+ k 2Fr



I′
S

h

Q(IS ◦

I ′)
S

i

!

2

6

I′
S

+ Fr



Q(IS ◦ I ′)
S



2
+ Fr

,

where the inequality is the deﬁnition of convexity. Taking the expectation over I ∼ ν gives us that
2
2
k(Q S )+ kFr,ν
6 kQ + kFr,ν
6 1, which gives us our contradiciton.

def

Now, analogous to Λ, set P 

S∼Θ

PS .

Random Restriction. We will exploit the crucial property that Λ and P are averages over functions
that depend on subsets of variables. This has the same eﬀect as a random restriction, in that hP, Riν
essentially depends on the low-degree part of R. Formally, we will show the following lemma.
Lemma 4.6. (Random Restriction) Fix D, ℓ ∈ . For matrix-valued functions R : I → ℓ×ℓ and a family
of functions {PS : IS → ℓ×ℓ }S⊆[N] , and a distribution Θ over subsets of [N],

I∼ν S∼Θ

hPS (IS ), R(I)i >

S∼Θ I∼ν

hPS (IS ), R <D
S (IS )i

1/2

− ρ(D, Θ)

·



2
kPS kFr,ν
S∼Θ

where
ρ(D, Θ)  max

 [α ⊆ S].

α,|α| > D S∼Θ

Proof. We ﬁrst re-express the left-hand side as
I∼ν S∼Θ

hPS (IS ), R(I)i 

S∼Θ I∼ν

18

hPS (IS ), R S (IS )i

 12

kRkFr,ν

def

where R S (IS )  IS [R(I)] obtained by averaging out all coordinates outside S. Splitting the
function R S into its low-degree and high-degree parts, R S  R S6D + R >D
, then applying a CauchyS
Schwartz inequality we get

S∼Θ I∼ν

hPS (IS ), R S (IS )i >

S∼Θ I∼ν

hPS (IS ), R <D
S (IS )i

−



2
kPS kFr,ν
S∼Θ

 1/2 
·

>D 2

S∼Θ

kR S kFr,ν

 1/2

.

Expressing R >D (I) in the Fourier basis, we have that over a random choice of S ∼ Θ,
S∼Θ

2
kR S>D kFr,ν


Õ

α,|α| > D

2
 [α ⊆ S] · R̂ 2α 6 ρ(D, Θ) · kRkFr

S∼Θ

Substituting into the above inequality, the conclusion follows.



Equality Constraints. Since Λ is close to satisfying all the equality constraints G of the SDP,
the function P approximately satisﬁes the low-degree part of G. Speciﬁcally, we can prove the
following.
Lemma 4.7. Let k > deginst (G j ) for all G j ∈ S. With P defined as above and under the conditions of
Theorem 2.6 for any function G ∈ G,
hP, G 6D iν 6

2
kGkFr,ν
n 2B

Proof. Recall that G  span{χS · G j | j ∈ [m], S ⊆ [N]} and let ΠG be the orthogonal projection into
G. Now, since G ∈ G,
G 6D  (ΠG G)6D  (ΠG G 6D−2k )6D + (ΠG G >D−2k )6D .

(4.3)

Now we make the following claim regarding the eﬀect of projection on to the ideal G, on the
degree of a polynomial.
Claim 4.8. For every polynomial Q, deg(ΠG Q) 6 deg(Q) + 2k. Furthermore for all α, ΠG Q >α has
no monomials of degree 6 α − k
Proof. To establish the ﬁrst part of the claim it suﬃces to show that ΠG Q ∈ span{χS · G j | |S| 6
deg(Q) + k}, since deg(G j ) 6 k for all j ∈ [m]. To see this, observe that ΠG Q ∈ span{χS · G j | |S| 6
deg(Q) + k} and is orthogonal to every χS · G j with |S| > deg(Q) + k:
hΠG Q, χS · G j iν  hQ, ΠG χS · G j iν  hQ, χS · G j iν  hQG j , χS iν  0,
where the ﬁnal equality is because deg(χS ) > deg(G j ) + deg(Q). On the other hand, for every
subset S with deg(χS ) 6 α − k,
hΠG Q >α , χS · G j i  hQ >α , ΠG χS · G j i  hQ >α , χS · G j i  0, since α > deg(G j ) + deg(χS )
This implies that ΠG Q >α ∈ span{χS · G j | |S| > α − k} which implies that ΠG Q >α has no monomials
of degree 6 α − k.

19

Incorporating the above claim into (4.3), we have that
G 6D  ΠG G 6D−2k + (ΠG G >D−2k )[D−3k,D] ,
where the superscript [D − 3k, D] denotes the degree range. Now,
hP, G 6D iν  hP, ΠG G 6D−2k iν + hP, (ΠG G >D−2k )[D−3k,D] iν
And since ΠG G 6D−2k is of degree at most D we can replace P by Λ,
 hΛ, ΠG G 6D−2k iν + hP, (ΠG G >D−2k )[D−3k,D] iν
Now bounding the ﬁrst term using Corollary 4.3 with a n B bound on K,



1
6 8B
n

 1/2

6 D−2k
· n B · (n B · kΠG G∅,∅
kFr,ν ) + hP, (ΠG G >D−2k )[D−3k,D] i

And for the latter term we use Lemma 4.6,
1
1
6 D−2k
6 2B kΠG G∅,∅
kFr,ν + 4B
n
n



2
kPS kFr,ν
S

 1/2

kGkFr,ν ,

where we have used the fact that (ΠG G >D−2k )[D−3k,D] is high degree. By property of orthogonal
projections, kΠG G >D−2k kFr,ν 6 kG >D−2k kFr,ν 6 kGkFr,ν . Along with the bound on kPS kFr,ν from
(4.2), this implies the claim of the lemma.

Finally, we have all the ingredients to complete the proof of Theorem 2.6.
Proof of Theorem 2.6. Suppose we sample an instance I ∼ ν, 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,
−1  a I (x) +

Õ

j∈[m]

1 Ij (x) · q Ij (x),

where a I is a sum-of-squares of polynomials of degree at most 2d in x, and deg(q Ij ) + deg(1 Ij ) 6 2d.
6d

6d

Let AI ∈ [n] ×[n] be the matrix of coeﬃcients for a I (c) on input I, and let G I be deﬁned similarly
Í
for j∈[m] 1 j (x) · q j (x). We can rewrite the sum-of-squares refutation as a matrix equality,
−1  hX 6 d , AI i + hX 6 d , G I i,

where G I ∈ G, the span of the equality constraints of the SDP.
Deﬁne s : I → {0, 1} as
def

s(I)  [∃ a degree-2d sos-refutation for S(I)]
By assumption,
setting,

I∼ν [s(I)]

 1−

1
.
n 8B

Deﬁne matrix valued functions A, G : I → [n]
def

A(I)  s(I) · AI
20

6 d ×[n] 6 d

by

def

G(I)  s(I) · G I
With this notation, we can rewrite the sos-refutation identity as a polynomial identity in X and I,
−s(I)  hX 6 d , A(I)i + hX 6 d , G(I)i .
Let e∅,∅ denote the [n]6 d × [n]6 d matrix with the entry corresponding to (∅, ∅) equal to 1, while the
remaining entries are zero. We can rewrite the above equality as,
−hX 6 d , s(I) · e∅,∅ i  hX 6 d , A(I)i + hX 6 d , G(I)i .
for all I and formal variables X.
Now, let P  S∼Θ PS where each PS is obtained by from the Program 3.1 with ΛS . Substituting
6
d
X with P(I) and taking an expectation over I,
hP, s(I) · e∅,∅ iν  hP, Aiν + hP, Giν

(4.4)

> hP, Giν

(4.5)

where the inequality follows because A, P  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
hP, Giν 

>

I∼ν S∼Θ

hPS (IS ), G(I)i

I∼ν S∼Θ

hPS (IS ), G

6D

1
(I)i − 4B ·
n

1
2
> − 2B · kGkFr,ν − 4B
n
n
1
>−
2



2
kPS kFr,ν
S



2
kPS kFr,ν
S

 1/2

kGkFr,ν

 1/2

· kGkFr,ν

(random restriction Lemma 4.6)

(using Lemma 4.7)

where the last step used the bounds on kPS kFr,ν from (4.2) and on kGkFr,ν 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
I∼ν

hP(I), s(I) · e∅,∅ i >

I∼ν

[P∅,∅ (I) · 1] − [(s − 1)2 ]1/2 · kP kFr,ν

The latter term can be simpliﬁed by noticing that the expectation of the square of a 0,1 indicator is
equal to the expectation of the indicator, which is in this case n18B by assumption. Also, since 1 is a
constant, P∅,∅ and Λ∅,∅ are equivalent:

I∼ν

[Λ∅,∅ (I) · 1] −

1
· kP kFr,ν
n 4B

1
· kP kFr,ν
( using (4.1))
n 4B
1
(using (4.2))
 1 − 3B
n

 1−

We have the desired contradiction in (4.4).


21

4.1 Handling Inequalities
Suppose the polynomial system Program 2.2 includes inequalities of the form h(I, x) > 0, then
a natural approach would be to introduce a slack variable z and set h(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 IS , the value of the corresponding slack variables could potentially
depend on IS . For instance, in a random CSP, the value of the objective function on the assignment
x generated from IS depends on all the constraints outside of S too.
The proof we described is to be modiﬁed as follows.
• As earlier, construct ΛS using only the robust inference property of original variables x, and
the corresponding matrix functions PS .
• Convert each inequality of the form h i (I, x) > 0, in to an equality by setting h i (I, x)  z 2i .
• Now we deﬁne a pseudo-distribution Λ̃S (IS ) over original variables x and slack variables z
as follows. It is convenient to describe the pseudo-distribution in terms of the corresponding
pseudo-expectation operator. Speciﬁcally, if x(IS ) is a feasible solution for Program 2.2 then
deﬁne
(
if σi odd for some i
def 0
Ẽ[z σ x α ]  Î
σ i /2 · x(I )
otherwise
S α
i∈σ (h i (I, x(IS )))

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 (I, x)  z i are satisﬁed.

It is easy to check that Λ̃ is psd matrix valued, satisﬁes (4.1) and all the equalities.

• While ΛS in the original proof was a function of IS , Λ̃S is not. However, the key observation
is that, Λ̃S is degree at most k · d in the variables outside of S. Each function h i (I, x(IS ))
is degree at most k in IS , and the entries of Λ̃S (IS ) are a product of at most d of these
polynomials.
• The main ingredient of the proof that is diﬀerent 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 6 n B/2 ; however this does not substantially change our results, since Theorem 2.6
requires ρ(D, Θ) < n −8B , which leaves us enough slack to absorb this factor (and in every
application ρ(D, Θ)  p O(D) for some p < 1 suﬃciently small that we meet the requirement
that D dk ρ(D − dk, Θ) is monotone non-increasing in D).
Lemma 4.9. [Random Restriction for Inequalities] Fix D, ℓ ∈ . Consider a matrix-valued function
R : I → ℓ×ℓ and a family of functions {PS : I → ℓ×ℓ }S⊆[N] such that each PS has degree at most dk
in IS . If Θ is a distribution over subsets of [N] with
ρ(D, Θ)  max

 [α ⊆ S],

α,|α| > D S∼Θ

22

and the additional requirement that D dk · ρ(D − dk, Θ) is monotone non-increasing in D, then
I∼ν S∼Θ

hPS (IS ), R(I)i >

S∼Θ I∼ν

hPS (IS ), R̃ <D
S (IS )i

−D

1/2

dk/2

· ρ(D − dk, Θ)

·



2
kPS k2,ν
S∼Θ

 12

kRkFr,ν

Proof.
I∼ν S∼Θ

hPS (IS ), R(I)i 

S∼Θ I∼ν

hPS (IS ), R̃ S (I)i

where R̃ S (I) is now obtained by averaging out the values for all monomials whose degree in S is
> dk. Writing R̃ S  R̃ S6D + R̃ >D
and applying a Cauchy-Schwartz inequality we get,
S

S∼Θ I∼ν

hPS (IS ), R̃ S (I)i >

S∼Θ I∼ν

hPS (IS ), R̃ <D
S (I)i

−



2
kPS kFr,ν
S∼Θ

 1/2 
·

>D

S∼Θ

k R̃ S kFr,ν

 1/2

Over a random choice of S,
S∼Θ

2

k R̃ S>D kFr,ν

Õ

α,|α| > D

2
 [|α ∩ S| 6 dk] · R̂ 2α 6 D dk · ρ(D − dk, Θ) · kRkFr
,

S∼Θ

where we have used that D dk ρ(D − dk, Θ) is a monotone non-increasing function of D. Substituting
this in the earlier inequality the Lemma follows.


5 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.
Problem 5.1 (Planted clique with clique of size n δ ). 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, 21 )).
• Planted Distribution: the uniform distribution over n-vertex graphs with a clique of size at
least n δ
The usual polynomial program for planted clique in variables x1 , . . . , x n is:
obj 6

Õ

xi

i

x 2i  x i

∀i ∈ [n]

x i x j  0 ∀(i, j) ∈ E
Lemma 5.2. Theorem 2.6 applies to the above planted clique program, so long as obj 6 n δ−ε for any
c·d
ε > D−6d
for a fixed constant c.
Proof. For planted clique, for our notion of “instance degree”, rather than the multiplicity of
instance variables, the “degree” of Iα will be the number of distinct vertices incident on the edges
23

in α. 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 c1 ·d for some constant
c 1 /2. Deﬁne B  c 1 d > dk.
Our subsampling distribution Θ is the distribution given by including every vertex with probability ρ, producing an induced subgraph of ≈ ρn vertices. For any set of edges α of instance
degree at most D − 6d,
 [α ⊆ S] 6 ρ D−6d ,
S∼Θ

since the instance degree corresponds to the number of vertices incident on α.
This subsampling operation satisﬁes 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 δ in G, then by a Chernoﬀ bound
β 2 ρn δ
 [∃ clique of size > (1 − β)ρn ∈ S] > 1 − exp(−
).
S∼Θ
2
δ

q

10B log n

, this gives us that Θ gives n −10B -robust inference for the planted clique
Choosing β 
ρn δ
problem, so long as obj 6 ρn/2. Choosing ρ  n −ε for ε so that
ρ D−6d 6 n −8B ⇒ ε >

c2 d
,
D − 6d

for some constant c 2 , all of the conditions required by Theorem 2.6 now hold.



Problem 5.3 (Random CSP Refutation at clause density α). Given an instance of a Boolean k-CSP
with predicate P : {±1} k → {±1} on n variables with clause set C, determine whether it comes
from:
• Uniform Distribution: m ≈ αn constraints are generated as follows. Each k-tuple of variables
S ∈ [n]k is independently with probability p  αn −k+1 given the constraint P(x S ◦ z S )  b S
(where ◦ is the entry-wise multiplication operation) for a uniformly random z S ∈ {±1} k and
b S ∈ {±1}.
• Planted Distribution: a planted solution y ∈ {±1} n is chosen, and then m ≈ αn constraints
are generated as follows. Each k-tuple of variables S ∈ [n]k is independently with probability
p  αn −k+1 given the constraint P(x S ◦ z S )  b S for a uniformly random z S ∈ {±1} k , but
b S  P(yS ◦ z S ) with probability 1 − δ and b S is uniformly random otherwise.
The usual polynomial program for random CSP refutation in variables x1 , . . . , x n is:
obj 6

Õ

S∈[n]



1 + P(x S ◦ z S ) · b S
[∃ constraint on S] ·
2
k



x 2i  1 ∀ i ∈ [n]
Lemma 5.4. If α > 1, then Theorem 2.6 applies to the above random k-CSP refutation problem, so long
c·d log n
as obj 6 (1 − δ − ε)m for any ε > D−3d , where c is a fixed constant.
24

Proof. 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 c1 d for some constant
c 1 . Deﬁne B  c 1 d.
Our subsampling distribution Θ is the distribution given by including each constraint independently with probability ρ, producing an induced CSP instance on n variables with approximately ρm constraints. Since each constraint survives the subsampling with probability ρ, for any
C 
,
α ∈ D−3d
 [α ⊆ S] 6 ρ D−3d .
S∼Θ

The subsample inference property clearly holds for the boolean constraints {x 2i  1}i∈[n] , as
a Boolean assignment to the variables is valid regardless of the number of constraints. Before
subsampling there are at least (1 − δ)m satisﬁed constraints, and so letting OS be the number of
constraints satisﬁed in sub-instance S, we have by a Chernoﬀ bound





β 2 ρ(1 − δ)m
.
 [OS > (1 − β) · ρ(1 − δ)m] > 1 − exp −
2
S∼Θ
Choosing β 

q

10B log n
ρ(1−δ)m

 o(1) (with overwhelming probability since we have α > 1 ⇒
n −10B -robust inference

[m] >

n), we have that Θ gives us
for the random CSP refutation problem, so long
as obj 6 (1 − o(1))ρ(1 − δ)m. Choosing ρ  (1 − ε) so that
ρ D−3d 6 n −8B ⇒ ε >

c 2 d log n
,
D − 3d

for some constant c 2 . The conclusion follows (after making appropriate adjustments to the constant).

Problem 5.5 (Community detection with average degree d (stochastic block model)). 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 ∈ Y or
u, v ∈ Z, and with probability (b − a)/n otherwise.
Letting x1 , . . . , 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
obj 6 x ⊤ Ax

Õ

x 2i  1

∀i ∈ [n]

x i  0.

i

Lemma 5.6. Theorem 2.6 applies to the community detection problem so long as obj 6 (1 − ε)
for ε >

c·d log n
D−3d

where c is a fixed constant.

25

(2a−b)
4 n,

Proof. 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 c1 d for some constant c 1 . Let B  c 1 d.
Consider the solution x which assigns x i  1 to i ∈ Y and x i  −1 to i ∈ Z. Our subsampling
operation is to remove every edge independently with probability 1−ρ. The resulting distribution Θ
and the corresponding restriction of x clearly satisﬁes the Booleanity and balancedness constraints
with probability 1. Since each edge is included independently with probability ρ, for any α ∈
E 
D−3d ,
 [α ⊆ S] 6 ρ D−3d .
S∼Θ

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
ρa
·
n







|Z|
|Y|
+
2
2



−ρ

(2a − b)ρn
b−a
· |Y| · |Z| 
− ρa,
n
4

and by a Chernoﬀqbound, the value in the sub instance is within a (1 − β)-factor with probability
10B log n

1 − n −10B for β 
. On resampling the edges outside the sub-instance from the uniform
n
distribution, this value can only decrease by at most (1 − ρ)(1 + β)nb/2 w.h.p over the choice of the
outside edges.
c (2a−b) log n
If we set ρ  (1 − ε(2a − b)/10b), then ρ D−3d 6 n −8B for ε > 2 D−3d . for some constant c 2 ,

while the objective value is at least (1 − ε)
adjustments to the constant).

(2a−b)n
.
4

The conclusion follows (after making appropriate



Problem 5.7 (Densest-k-subgraph). Given a graph G  (V, E) on n vertices, determine whether it
comes from:
• Uniform Distribution: G(n, p).
• 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 x1 , . . . , x n is:
obj 6 x ⊤ Ax

Õ

x 2i  x i

∀i ∈ [n]

xi  k

i

Lemma 5.8. When k 2 (p + q) ≫ d log n, Theorem 2.6 applies to the densest-k-subgraph problem with

c·d log n
obj 6 (1 − ε)(p + q) 2k for any ε > D−3d for a fixed constant c.

Proof. 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 c1 d for a constant c 1 ; ﬁx B  c 1 d.
Our subsampling operation is to include each edge independently with probability ρ, and take
the subgraph induced by the included edges. Clearly, the Booleanity and sparsity constraints are

26

preserved by this subsampling distribution Θ. Since each edge is included independently with
E 
,
probability ρ, for any α ∈ D−3d
 [α ⊆ S] 6 ρ D−3d .
S∼Θ



Now, the expected objective value (over the instance and the sub-sampling) is at least ρ(p + q) 2k ,
and applying a Chernoﬀ bound, we hace that the probability the
r sub-sampled instance has value
less than (1 − β)ρ(p + q)

k
2

is at most n −10B if we choose β 

10B log n

ρ(p+q)(2k)

(which is valid since we

assumed that d log n ≪ (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 ρ  (1 − ε) and setting
ρ D−3d 6 n −8B ⇒ ε >

c 2 d log n
,
D − 3d

for some constant c 2 , which concludes the proof (after making appropriate adjustments to the
constant).

Problem 5.9 (Tensor PCA). Given an order-k tensor in (n )⊗k , determine whether it comes from:
• Uniform Distribution: each entry of the tensor sampled independently from N(0, 1).
• Planted Distribution: a spiked tensor, T  λ · v ⊗k + G where v is sampled uniformly from
{± √1n } n , and where G is a random tensor with each entry sampled independently from
N(0, 1).
Given the tensor T, the canonical program for the tensor PCA problem in variables x1 , . . . , x n is:
obj 6 hx ⊗k , Ti

kx k22  1

Lemma 5.10. For λn −ε ≫ log n, Theorem 2.6 applies to the tensor PCA problem with obj 6 λn −ε for
c·d
for a fixed constant c.
any ε > D−3d
Proof. 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 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 c1 d for a ﬁxed constant c 1 .
Our subsampling operation is to set to zero every entry of T independently with probability
1 − ρ, obtaining a sub-instance T′ on the nonzero entries. Also, for any α ∈

 [α ∈ S] 6 ρ D−3d .

[n]k 
,
D−3d

S∼Θ

This subsampling operation clearly preserves the planted solution unit sphere constraint. Additionally, let R be the operator that restricts a tensor to the nonzero entries. We have that
hR(λ · v ⊗k ), v ⊗k i has expectation λ · ρ, since every entry of v ⊗k has magnitude n −k/2 . Applying a
Chernoﬀ bound, q
we have that this quantity will be at least (1 − β)λρ with probability at least n −10B

if we choose β 

10B log n
.
λρ

27

It remains to address the noise introduced by GT′ and resampling all the entries outside of the
subinstance T′. Each of these entries is a standard normal entry. The quantity h(Id −R)(N), v ⊗k i
is a sum over at most n k i.i.d. Gaussian entries each with standard deviation n −k/2 (since that is
the magnitude of (v ⊗k )α . The entire quantity is thus a Gaussian random variable with mean
0 and
p
−10B
variance 1, and therefore with probability at least n
this quantity will not exceed 10B log n.
p
So long as 10B log n ≪ λρ, the signal term will dominate, and the solution will have value at
least λρ/2.
Now, we set ρ  n −ε so that
ρ D−3d 6 n −8B ⇒ ε >

2c 1 d
,
D − 3d

which concludes the proof (after making appropriate adjustments to the constant c 1 ).



Problem 5.11 (Sparse PCA). Given an n × m matrix M in n , determine whether it comes from:
• Uniform Distribution: each entry of the matrix sampled independently from
√ N(0, 1).
• Planted Distribution: a random vector with k non-zero entries v ∈ {0, ±1/ k} n is chosen,
and then the ith column of the matrix is sampled independently by taking s i v + γi for a
uniformly random sign s i ∈ {±1} and a standard gaussian vector γi ∼ N(0, Id).
The canonical program for the sparse PCA problem in variables x1 , . . . , x n is:
obj 6 kM ⊤ x k22
x 2i  x i

kx k22

k

∀i ∈ [n]

Lemma 5.12. For kn −ε/2 ≫ log n, Theorem 2.6 applies to the sparse PCA problem with obj 6 k 2−ε m for
c·d
any ε > D−6d
for a fixed constant c.
Proof. 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 c1 d for a ﬁxed
constant c 1 .
Our subsampling operation is to set to zero every entry of M independently with probability
M 
,
1 − ρ, obtaining a sub-instance M on the nonzero entries. Also, for any α ∈ D−6d

 [α ∈ S] 6 ρ D−6d .

S∼Θ

This subsampling operation clearly preserves
the constraints on the solution variables.
√
We take our subinstance solution y  kv, which is feasible. Let R be the subsampling operator
that zeros out a set of columns. On subsampling, and then resampling the zeroed out columns
from the uniform distribution, we can write the resulting M̃ as
M̃ ⊤  R(sv T ) + G ⊤
T
where
√ G is a random Gaussian matrix. Therefore, the objective value obtained by the solution
y  kv is

28

M̃ ⊤ y 

√

√
k · R(sv ⊤ )v + k · G ⊤ v

The ﬁrst term is a vector u si1nal with m entries, each of which is a sum of k Bernoulli random
variables, all of the same sign, with probability ρ 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
[ku si1nal k22 ]  (ρk)2 m,
Θ

and by Chernoﬀ bounds
qwe have that this concentrates within a (1 − β) factor with probability
10B log n

.
1 − n −10B if we take β 
(ρk)2 m
The expectation of hu si1nal , u noise i is zero, and applying similar concentration arguments we
have that with probability 1 − n 10B , |hu si1nal , u noise i| 6 (1 + β)ρk. Taking the union bound over
these events and applying Cauchy-Schwarz, we have that
kR(M)y k22 > (ρk)2 m − 2km  ρ 2 k 2 m − 2km.
so long as ρk ≫ 1, the ﬁrst term dominates.
Now, we set ρ  n −ε for ε < 1 so that
ρ D−6d 6 n −8B ⇒ ε >

c2 d
,
D − 6d

for some constant c 2 , which concludes the proof.



Remark 5.13. 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. Speciﬁcally, the degree of a monomial will be the number of distinct variables
in it, irrespective of the powers to which they are raised.

6 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.

6.1 Predicting sos lower bounds from low-degree distinguishers for Tensor PCA
In this section we demonstrate how to predict using Conjecture 1.2 that when λ ≪ n 3/4−ε for ε > 0,
SoS algorithms cannot solve Tensor PCA. This prediction is borne out in Theorem 1.4.
Theorem 6.1. Let µ be the distribution on n⊗n⊗n which places a standard Gaussian in each entry. Let ν
be the density of the Tensor PCA planted distribution with respect to µ, where we take the planted vector v

29

to have each entry uniformly chosen from {± √1n }.7 If λ 6 n 3/4−ε , there is no degree n o(1) polynomial p with
p(A)  0,

µ

p(A) > n

planted

Ω(1)



·  p(A)
µ

 1/2

.

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

max

deg p 6 n o(1)
,

µ

p(T)0

µ

p(T)

 ( (ν 6 d (T) − 1)2 )1/2

1/2
µ
2

(6.1)

p(T)

where ν 6 d is the orthogonal projection (with respect to µ) of the density ν 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 ν of the planted distribution.
Claim 6.3. (

µ (v

6 d (T) −

1)2 )1/2 ≪ 1 when λ 6 n 3/4−ε for ε > Ω(1) and d  n o(1) .

The theorem follows immediately. We sketch proofs of the claims in order.
Sketch of proof for Claim 6.2. By deﬁnition of ν, the maximization is equivalent to maximizing
o(1) and with
2
µ ν(T) · p(T) among all p of degree d  n
µ p(T)  1 and
µ p(T)  0. Standard Fourier analysis shows that this maximum is achieved by the orthogonal projection of ν − 1
into the span of degree d polynomials.
To make this more precise, recall that the Hermite polynomials provide an orthonormal basis
for real-valued polynomials under the multivariate Gaussian distribution. (For an introduction
to Hermite polynomials, see the book [O’D14].) The tensor T ∼ µ is an n 3 -dimensional multivariate Gaussian. For a (multi)-set W ⊆ [n]3 , let HW be the W-th Hermite polynomial, so that
µ HW (T)HW ′ (T)  WW ′ .
Then the best p (ignoring normalization momentarily) will be the function
p(A)  ν 6 d (A) − 1 

Õ

16 |W | 6 d

(

T∼µ

ν(T)HW (T)) · HW (A)

Here µ ν(T)HW (T)  b
ν (W) is the W-th Fourier coeﬃcient of ν. What value for (6.1) is achieved
by this p? Again by standard Fourier analysis, in the numerator we have,
ν

p(T) 

ν

(ν 6D (T) − 1) 

µ

ν(T) · (ν 6D (T) − 1) 

µ

(ν 6 d (T) − 1)2

Comparing this to the denominator, the maximum value of (6.1) is ( µ (v 6 d (T) − 1)2 )1/2 . This is
nothing more than the 2-norm of the projection of ν − 1 to degree-d polynomials!

The following fact, used to prove Claim 6.3, is an elementary computation with Hermite
polynomials.
Fact 6.4. Let W ⊆ [n]3 . Then b
ν (W)  λ |W | n −3|W |/2 if W, thought of as a 3-uniform hypergraph, has all
even degrees, and is 0 otherwise.
7This does not substantially modify the problem but it will make calculations in this proof sketch more convenient.

30

  µ ν(T)HW (T)  ν HW (T),
To see that this calculation is straightforward, note that ν(W)
so it is enough to understand the expectations of the Hermite polynomials under the planted
distribution.
Sketch of proof for Claim 6.3. Working in the Hermite basis (as described above), we get µ (v 6 d (T) −
Í
1)2  16 |W | 6 d b
ν (W)2 . For the sake of exposition, we will restrict attention in the sum to W in
which no element appears with multiplicity larger than 1 (other terms can be treated similarly).
Í
What is the contribution to 16 |W | 6 d b
ν (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,

Õ

16 |W | 6 d

2

b
ν (W) 6

d
Õ

n 3t/2 t O(t) λ 2t n −3t .

t1

So long as λ 2 6 n 3/2−ε for some ε  Ω(1) and t 6 d 6 n O(ε) , this is o(1).



6.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 reﬁnements 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 deﬁne 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.
Problem 6.5 (k-Tensor PCA, signal-strength λ, boolean version). Distinguish the following two
n
def
distributions on Ωk  {±1}( k ) .
• the uniform distribution: A ∼ Ω chosen uniformly at random.
• the planted distribution: Choose v ∼ {±1} n and let B  v ⊗k . Sample A by rerandomizing
every coordinate of B with probability 1 − λn −k/2 .
We show that the natural SoS relaxation of this problem suﬀers from a large integrality gap,
when λ is slightly less than n k/4 , even when the degree of the SoS relaxation is n Ω(1) . (When
O(ε)
are known for k  O(1) [RM14, HSS15, HSSS16,
λ ≫ n k/4−ε , algorithms with running time 2n
BGL16, RRS16].)
Theorem 6.6. Let k  O(1). For A ∈ Ωk , let
def
SoS d (A)  max ˜ hx ⊗k , Ai s.t. ˜ is a degree-d pseudoexpectation satisfying {kx k 2  1} .
˜

There is a constant c so that for every small enough ε > 0, if d 6 n c·ε , then for large enough n,

 {SoS d (A) > n k/4−ε } > 1 − o(1)

A∼Ω

31

and
A∼Ω

SoS d (A) > n k/4−ε .

Moreover, the latter also holds for A with iid entries from N(0, 1).8
To prove the theorem we will exhibit for a typical sample A from the uniform distribution a
degree n Ω(ε) pseudodistribution ˜ which satisﬁes {kx k 2  1} and has ˜ hx ⊗k , Ai > n k/4−ε . The
following lemma ensures that the pseudo-distribution we exhibit will be PSD.

Í

Lemma 6.7. Let d ∈  and let Nd  s 6 d n(n − 1) · · · (n − (s − 1)) be the number of 6 d-tuples with
unique entries from [n]. There is a constant ε ∗ independent of n such that for any ε < ε ∗ also independent of
n, the following is true. Let λ  n k/4−ε . Let µ(A) be the density of the following distribution (with respect
n
to the uniform distribution on Ω  {±1}( k ) ).
The Planted Distribution: Choose v ∼ {±1} n uniformly. Let B  v ⊗k . Sample A by
• replacing every coordinate of B with a random draw from {±1} independently with probability
1 − λn −k/2 ,
• then choosing a subset S ⊆ [n] by including every coordinate with probability n −ε ,
• then replacing every entry of B with some index outside S independently with a uniform draw from
{±1}.
Let Λ : Ω → Nd ×Nd be the following function
Λ(A)  µ(A) ·

v|A

v ⊗ 62d

Here we abuse notation and denote by x 6 ⊗2d the matrix indexed by tuples of length 6 d with unique
entries from [n]. For D ∈ , let Λ6D be the projection of Λ into the degree-D real-valued polynomials on
n
{±1}( k ) . There is a universal constant C so that if Cd/ε < D < n ε/C , then for large enough n

 {Λ6D (A)  0} > 1 − o(1) .

A∼Ω

For a tensor A, the moment matrix of the pseudodistribution we exhibit will be Λ6D (A). We will
need it to satisfy the constraint {kx k 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.)
n
Lemma 6.8. Let k ∈ . Let V be a linear subspace of N×M . Let Ω  {±1}( k ) . Let Λ : Ω → V. Let Λ6D
be the entrywise orthogonal projection of Λ to polynomials of degree at most D. Then for every A ∈ Ω, the
matrix Λ6D (A) ∈ V.

Proof. The function Λ is an element of the vector space N×M ⊗ Ω . The projection ΠV : N×M →
V and the projection Π6D from Ω to the degree-D polynomials commute as projections on
N×M ⊗ Ω , since they act on separate tensor coordinates. It follows that Λ6D ∈ V ⊗ (Ω )6D takes
values in V.

8For technical reasons we do not prove a tail bound type statement for Gaussian A, but we conjecture that this is also
true.

32

Last, we will require a couple of scalar functions of Λ6D to be well concentrated.
Lemma 6.9. Let Λ, d, ε, D be as in Lemma 6.7. The function Λ6D satisfies
6D
• A∼Ω {Λ∅,∅
(A)  1 ± o(1)} > 1 − o(1) (Here Λ∅,∅  1 is the upper-left-most entry of Λ.)

• A∼Ω {hΛ6D (A), Ai  (1 ± o(1)) · n 3k/4−ε } > 1 − o(1) (Here we are abusing notation to write
hΛ6D (A), Ai for the inner product of the part of Λ6D indexed by monomials of degree k and A.)
The Boolean case of Theorem 6.6 follows from combining the lemmas. The Gaussian case can
be proved in a black-box fashion from the Boolean case following the argument in Section C.
The proofs of all the lemmas in this section follow analogous lemmas in the work of Barak et
al. on planted clique [BHK+ 16]; we defer them to the full version of the present work.

6.3 Main theorem and proof overview for sparse PCA
In this section we prove the following main theorem. Formally, the theorem shows that with high
probability for a random n × n matrix A, even high-degree SoS relaxations are unable to certify
that no sparse vector v has large quadratic form hv, Avi.
Theorem 6.10 (Restatement of Theorem 1.6). If A ∈ n×n , let



SoS d,k (A)  max ˜ hx, Axi s.t. ˜ is degree d and satisfies x 3i  x i , kx k 2  k .
˜

There are absolute constants c, ε ∗ > 0 so that for every ρ ∈ (0, 1) and ε ∈ (0, ε ∗ ), if k  n ρ , then for
d 6 n c·ε ,
 n {SoS d,k (A) > min(n 1/2−ε k, n ρ−ε k)} > 1 − o(1)
A∼{±1} ( 2 )

and
n
A∼{±1} ( 2 )

SoS d,k (A) > min(n 1/2−ε k, n ρ−ε k) .

Furthermore, the latter is true also if A is symmetric with iid entries from N(0, 1).9
We turn to some discussion of the theorem statement. First of all, though it is technically
convenient for A in the theorem statement above to be a ±1 matrix, the entries may be replaced by
standard Gaussians (see Section C).
Remark 6.11 (Relation to the spiked-Wigner model of sparse principal component analysis). To get
some intuition for the theorem statement, it is useful to return to a familiar planted problem: the
spiked-Wigner model of sparse principal component analysis. Let W be a symmetric matrix
with
√
iid entries from N(0, 1), and let v be a random k-sparse unit vector with entries {±1/ k, 0}. Let
B  W + λvv⊺ . The problem is to distinguish between a single sample from B and a sample from
W. There are two main algorithms for this problem, both captured by the SoS hierarchy. The
√
ﬁrst, applicable when λ ≫ n, is vanilla PCA: the top eigenvalue of B will be larger than the top
eigenvalue of W. The second, applicable when λ ≫ k, is diagonal thresholding: the diagonal
9For technical reasons we do not prove a tail bound type statement for Gaussian A, but we conjecture that this is also
true.

33

entries of B which corresponds to nonzero coordinates will be noticeably large. The theorem
statement above (transferred to the Gaussian setting, though this has little eﬀect) shows that once
λ is well outside these parameter regimes, i.e. when λ < n 1/2−ε , k 1−ε for arbitrarily small ε > 0,
even degree n Ω(ε) SoS programs do not distinguish between B and W.
Remark 6.12 (Interpretation as an integrality gap). A second interpretation of the theorem statement,
independent of any planted problem, is as a strong integrality gap for random instances for the
problem of maximizing a quadratic form over k-sparse vectors. Consider the actual maximum of
hx, Axi for random ({±1} or Gaussian) A over k-sparse unit vectors x. There are roughly 2k log n
points in a 21 -net for such vectors, meaning that by standard arguments,
max

kxk1,x is k-sparse

√
hx, Axi 6 O( k log n) .

With the parameters of the theorem, this means that the integrality gap of the degree n Ω(ε) SoS
relaxation is at least min(n ρ/2−ε , n 1/2−ρ/2−ε ) when k  n ρ .
Remark 6.13 (Relation to spiked-Wishart model). Theorem 1.6 most closely concerns the spikedWigner model of sparse PCA; this refers to independence of the entries of the matrix A. Often,
sparse PCA is instead studied in the (perhaps more realistic) spiked-Wishart model, where the input
is m samples x1 , . . . , x m from an n-dimensional Gaussian vector N(0, Id +λ · vv ⊤ ), where v is
a unit-norm k-sparse vector. Here the question is: as a function of the sparsity k, the ambient
dimension n, and the signal strength λ, how many samples m are needed to recover the vector v?
The natural approach to recovering v in this setting is to solve a convex relaxation of the problem
Í
of maximizing he quadratic form of the empirical covariance M  i 6 m x i x i⊺ over k-sparse unit
vectors (the maximization problem itself is NP-hard even to approximate [CPR16]).
Theoretically, one may apply our proof technique for Theorem 1.6 directly to the spiked-Wishart
model, but this carries the expense of substantial technical complication. We may however make
intelligent guesses about the behavior of SoS relaxations for the spiked-Wishart model on the basis
of Theorem 1.6 alone. As in the spiked Wigner model, there are essentially two known algorithms
to recover a planted sparse vector v in the spiked Wishart model: vanilla PCA and diagonal
thresholding [DM14b]. We conjecture that, as in the spiked Wigner model, the SoS hierarchy
requires n Ω(1) degree to improve the number of samples required by these algorithms by any
polynomial factor. Concretely, considering the case λ  1 for simplicity, we conjecture that there
are constants c, ε ∗ such that for every ε ∈ (0, ε ∗ ) if m 6 min(k 2−ε , n 1−ε ) and x1 , . . . , x m ∼ N(0, Id)
are iid, then with high probability for every ρ ∈ (0, 1) if k  n ρ ,
SoS d,k

Õ
i6m

!

x i x i⊺ > min(n 1−ε k, k 2−ε )

for all d 6 n c·ε .
Lemmas for Theorem 1.6. Our proof of Theorem 1.6 is very similar to the analogous proof for
Tensor PCA, Theorem 6.6. We state the analogues of Lemma 6.7 and Lemma 6.9. Lemma 6.8 can
be used unchanged in the sparse PCA setting.
The main lemma, analogous to Lemma 6.7 is as follows.
34

Í

Lemma 6.14. Let d ∈  and let Nd  s 6 d n(n − 1) · · · (n − (s − 1)) be the number of 6 d-tuples with
unique entries from [n]. Let µ(A) be the density of the following distribution on n × n matrices A with
n
respect to the uniform distribution on {±1}( 2) .
Planted distribution: Let k  k(n) ∈  and λ  λ(n) ∈ , and γ > 0, and assume λ 6 k. Sample
a uniformly random k-sparse vector v ∈ n with entries ±1, 0. Form the matrix B  vv ⊤ . For each nonzero
entry of B independently, replace it with a uniform draw from {±1} with probability 1 − λ/k (maintaining
the symmetry B  B ⊤ ). For each zero entry of B, replace it with a uniform draw from {±1} (maintaining
the same symmetry). Finally, choose every i ∈ [n] with probability n −γ independently; for those indices that
were not chosen, replace every entry in the corresponding row and column of B with random ±1 entries.10
Output the resulting matrix A. (We remark that this matrix is a Boolean version of the more standard
spiked-Wigner model B + λvv√⊤ where B has iid standard normal entries and v is a random k-sparse unit
vector with entries from {±1/ k, 0}.)
n
Let Λ : {±1}( 2) → Nd ×Nd be the following function
Λ(A)  µ(A) ·

v|A

v ⊗ 62d

where the expectation is with respect to the planted distribution above. For D  D(n) ∈ , let Λ6D be the
entrywise projection of Λ into the Boolean functions of degree at most D.
There are constants C, ε ∗ > 0 such that for every γ > 0 and ρ ∈ (0, 1) and every ε ∈ (0, ε ∗ ) (all
independent of n), if k  n ρ and λ 6 min{n ρ−ε , n 1/2−ε }, and if Cd/ε < D < n ε/C , then for large enough
n
 n {Λ6D (A)  0} > 1 − o(1) .
A∼{±1} ( 2 )

Remark 6.15. We make a few remarks about the necessity of some of the assumptions above.
A useful intuition is that the function Λ6D (A) is (with high probability) positive-valued when
the parameters ρ, ε, γ of the planted distribution are such that there is no degree-D polynomial
n
f : {±1}( 2) →  whose values distinguish a typical sample from the planted distribution from a
null model: a random symmetric matrix with iid entries.
At this point it is useful to consider a more familiar planted model, which the lemma above
n
mimics. Let W be a n × n symmetric
√ matrix with iid entries from N(0, 1). Let v ∈  be a k-sparse
⊺
unit vector, with entries in {±1/ k, 0}. Let A  W + λvv . Notice that if λ ≫ k, then diagonal
thresholding on the matrix W identiﬁes the nonzero coordinates of v. (This is the analogue of
the covariance-thresholding algorithm in the spiked-Wishart version of sparse PCA.) On the other
√
√
hand, if λ ≫ n then (since typically kW k ≈ n), ordinary PCA identiﬁes v. The lemma captures
computational hardness for the problem of distinguishing a single sample from A from a sample
from the null model W both diagonal thresholding and ordinary PCA fail.
Next we state the analogue of Lemma 6.9.
Lemma 6.16. Let Λ, d, k, λ, γ, D be as in Lemma 6.14. The function Λ6D satisfies
6D
• A∼{±1}(nk) {Λ∅,∅
(A)  1 ± o(1)} > 1 − o(1).

• A∼{±1}(nk) {hΛ6D (A), Ai  (1 ± o(1)) · λn Θ(−γ) } > 1 − o(1).
10This additional n −γ noising step is a technical convenience which has the eﬀect of somewhat decreasing the number
of nonzero entries of v and decreasing the signal-strength λ.

35

References
[AK97]

Noga Alon and Nabil Kahale, A spectral technique for coloring random 3-colorable graphs,
SIAM J. Comput. 26 (1997), no. 6, 1733–1748. 1

[AKS98]

Noga Alon, Michael Krivelevich, and Benny Sudakov, Finding a large hidden clique in a
random graph, Random Struct. Algorithms 13 (1998), no. 3-4, 457–466. 1, 4, 8

[AOW15a] Sarah R. Allen, Ryan O’Donnell, and David Witmer, How to refute a random CSP, 2015
IEEE 56th Annual Symposium on Foundations of Computer Science—FOCS 2015,
IEEE Computer Soc., Los Alamitos, CA, 2015, pp. 689–708. MR 3473335 1
[AOW15b] Sarah R. Allen, Ryan O’Donnell, and David Witmer, How to refute a random CSP, FOCS,
IEEE Computer Society, 2015, pp. 689–708. 8
[BBH+ 12]

Boaz Barak, Fernando G. S. L. Brandão, Aram Wettroth Harrow, Jonathan A. Kelner, David Steurer, and Yuan Zhou, Hypercontractivity, sum-of-squares proofs, and their
applications, STOC, ACM, 2012, pp. 307–326. 1, 6, 8

[BCC+ 10]

Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vĳayaraghavan, Detecting high log-densities—an O(n 1/4 ) approximation for densest k-subgraph,
STOC’10—Proceedings of the 2010 ACM International Symposium on Theory of Computing, ACM, New York, 2010, pp. 201–210. MR 2743268 8

[BCK15]

Boaz Barak, Siu On Chan, and Pravesh K. Kothari, Sum of squares lower bounds from
pairwise independence [extended abstract], STOC’15—Proceedings of the 2015 ACM Symposium on Theory of Computing, ACM, New York, 2015, pp. 97–106. MR 3388187
8

[BGG+ 16]

Vĳay V. S. P. Bhattiprolu, Mrinal Kanti Ghosh, Venkatesan Guruswami, Euiwoong Lee,
and Madhur Tulsiani, Multiplicative approximations for polynomial optimization over the
unit sphere, Electronic Colloquium on Computational Complexity (ECCC) 23 (2016),
185. 1, 6, 8

[BGL16]

Vĳay V. S. P. Bhattiprolu, Venkatesan Guruswami, and Euiwoong Lee, Certifying
random polynomials over the unit sphere via sum of squares hierarchy, CoRR abs/1605.00903
(2016). 1, 2, 9, 31

[BHK+ 16]

Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra,
and Aaron Potechin, A nearly tight sum-of-squares lower bound for the planted clique
problem, FOCS, IEEE Computer Society, 2016, pp. 428–437. 1, 4, 5, 8, 9, 29, 31, 33

[BKS14]

Boaz Barak, Jonathan A. Kelner, and David Steurer, Rounding sum-of-squares relaxations,
STOC, ACM, 2014, pp. 31–40. 1

[BKS15]

, Dictionary learning and tensor decomposition via the sum-of-squares method, STOC,
ACM, 2015, pp. 143–151. 1

36

[BKS17]

Boaz Barak, Pravesh Kothari, and David Steurer, Quantum entanglement, sum of squares,
and the log rank conjecture, CoRR abs/1701.06321 (2017). 1

[BM16]

Boaz Barak and Ankur Moitra, Noisy tensor completion via the sum-of-squares hierarchy,
COLT, JMLR Workshop and Conference Proceedings, vol. 49, JMLR.org, 2016, pp. 417–
445. 1, 8

[BMVX16] Jess Banks, Cristopher Moore, Roman Vershynin, and Jiaming Xu, Information-theoretic
bounds and phase transitions in clustering, sparse pca, and submatrix localization, CoRR
abs/1607.05222 (2016). 6
[BR13a]

Quentin Berthet and Philippe Rigollet, Complexity theoretic lower bounds for sparse principal component detection, COLT, JMLR Workshop and Conference Proceedings, vol. 30,
JMLR.org, 2013, pp. 1046–1066. 7

[BR13b]

Quentin Berthet and Philippe Rigollet, Computational lower bounds for sparse pca, COLT
(2013). 2

[BS14]

Boaz Barak and David Steurer, Sum-of-squares proofs and the quest toward optimal algorithms, CoRR abs/1404.5236 (2014). 6

[CC09]

Eric Carlen and ERIC CARLEN, Trace inequalities and quantum entropy: An introductory
course, 2009. 18

[CPR16]

Siu On Chan, Dimitris Papailliopoulos, and Aviad Rubinstein, On the approximability
of sparse PCA, COLT, JMLR Workshop and Conference Proceedings, vol. 49, JMLR.org,
2016, pp. 623–646. 7, 34

[DM14a]

Yash Deshpande and Andrea Montanari, Information-theoretically optimal sparse PCA,
ISIT, IEEE, 2014, pp. 2197–2201. 7

[DM14b]

, Sparse PCA via covariance thresholding, NIPS, 2014, pp. 334–342. 2, 34

[DM15]

, Improved sum-of-squares lower bounds for hidden clique and hidden submatrix
problems, COLT, JMLR Workshop and Conference Proceedings, vol. 40, JMLR.org,
2015, pp. 523–562. 9

[DX13]

Feng Dai and Yuan Xi, Spherical harmonics, arXiv preprint arXiv:1304.2585 (2013). 44

[Fil16]

Yuval Filmus, An orthogonal basis for functions over a slice of the boolean hypercube, Electr.
J. Comb. 23 (2016), no. 1, P1.23. 44

[FM16]

Zhou Fan and Andrea Montanari, How well do local algorithms solve semidefinite programs?, CoRR abs/1610.05350 (2016). 8

[GM15]

Rong Ge and Tengyu Ma, Decomposing overcomplete 3rd order tensors using sum-of-squares
algorithms, APPROX-RANDOM, LIPIcs, vol. 40, Schloss Dagstuhl - Leibniz-Zentrum
fuer Informatik, 2015, pp. 829–849. 1

37

[Gri01a]

Dima Grigoriev, Complexity of positivstellensatz proofs for the knapsack, Computational
Complexity 10 (2001), no. 2, 139–154. 8

[Gri01b]

, Linear lower bound on degrees of positivstellensatz calculus proofs for the parity,
Theor. Comput. Sci. 259 (2001), no. 1-2, 613–622. 8

[GW94]

Michel X. Goemans and David P. Williamson, .879-approximation algorithms for MAX
CUT and MAX 2sat, STOC, ACM, 1994, pp. 422–431. 1

[Har70]

Richard A Harshman, Foundations of the parafac procedure: Models and conditions for an"
explanatory" multi-modal factor analysis. 1

[HKP15]

Samuel B. Hopkins, Pravesh K. Kothari, and Aaron Potechin, Sos and planted clique:
Tight analysis of MPW moments at all degrees and an optimal lower bound at degree four,
CoRR abs/1507.05230 (2015). 9

[HL09]

Christopher J. Hillar and Lek-Heng Lim, Most tensor problems are NP hard, CoRR
abs/0911.1393 (2009). 6

[HSS15]

Samuel B. Hopkins, Jonathan Shi, and David Steurer, Tensor principal component analysis
via sum-of-square proofs, COLT, JMLR Workshop and Conference Proceedings, vol. 40,
JMLR.org, 2015, pp. 956–1006. 1, 2, 6, 8, 9, 31

[HSSS16]

Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer, Fast spectral
algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors,
STOC, ACM, 2016, pp. 178–191. 1, 2, 8, 9, 31

[KMOW17] Pravesh K. Kothari, Ryuhei Mori, Ryan O’Donnell, and David Witmer, Sum of squares
lower bounds for refuting any CSP, CoRR abs/1701.04521 (2017). 8
[KNV+ 15]

Robert Krauthgamer, Boaz Nadler, Dan Vilenchik, et al., Do semidefinite relaxations solve
sparse pca up to the information limit?, The Annals of Statistics 43 (2015), no. 3, 1300–1322.
2

[KT17]

Ken-ichi Kawarabayashi and Mikkel Thorup, Coloring 3-colorable graphs with less than
n1/5 colors, J. ACM 64 (2017), no. 1, 4:1–4:23. 1

[LRS15]

James R. Lee, Prasad Raghavendra, and David Steurer, Lower bounds on the size of
semidefinite programming relaxations, STOC, ACM, 2015, pp. 567–576. 1

[MPW15]

Raghu Meka, Aaron Potechin, and Avi Wigderson, Sum-of-squares lower bounds for
planted clique [extended abstract], STOC’15—Proceedings of the 2015 ACM Symposium
on Theory of Computing, ACM, New York, 2015, pp. 87–96. MR 3388186 9

[MS16a]

Andrea Montanari and Subhabrata Sen, Semidefinite programs on sparse random graphs
and their application to community detection, STOC, ACM, 2016, pp. 814–827. 8

[MS16b]

Andrea Montanari and Nike Sun, Spectral algorithms for tensor completion, CoRR
abs/1612.07866 (2016). 8
38

[MSS16a]

Tengyu Ma, Jonathan Shi, and David Steurer, Polynomial-time tensor decompositions with
sum-of-squares, CoRR abs/1610.01980 (2016). 1

[MSS16b]

, Polynomial-time tensor decompositions with sum-of-squares, FOCS, IEEE Computer Society, 2016, pp. 438–446. 1

[MW15a]

Tengyu Ma and Avi Wigderson, Sum-of-squares lower bounds for sparse PCA, NIPS, 2015,
pp. 1612–1620. 2

[MW15b]

, Sum-of-squares lower bounds for sparse PCA, CoRR abs/1507.06370 (2015). 9

[O’D14]

Ryan O’Donnell, Analysis of boolean functions, Cambridge University Press, 2014. 30

[Pea01]

Karl Pearson, On lines and planes of closes fit to systems of points in space, Philosophical
Magazine 2 (1901), 559–572. 1

[PS17]

Aaron Potechin and David Steurer, Exact tensor completion with sum-of-squares, CoRR
abs/1702.06237 (2017). 1

[PWB16]

Amelia Perry, Alexander S. Wein, and Afonso S. Bandeira, Statistical limits of spiked
tensor models, CoRR abs/1612.07728 (2016). 6

[RM14]

Emile Richard and Andrea Montanari, A statistical model for tensor PCA, NIPS, 2014,
pp. 2897–2905. 2, 5, 9, 31

[RRS16]

Prasad Raghavendra, Satish Rao, and Tselil Schramm, Strongly refuting random csps
below the spectral threshold, CoRR abs/1605.00058 (2016). 1, 2, 6, 8, 9, 31

[RS15]

Prasad Raghavendra and Tselil Schramm, Tight lower bounds for planted clique in the
degree-4 SOS program, CoRR abs/1507.05136 (2015). 9

[RW17]

Prasad Raghavendra and Benjamin Weitz, On the bit complexity of sum-of-squares proofs,
CoRR abs/1702.05139 (2017). 40, 42

[Sch08]

Grant Schoenebeck, Linear level lasserre lower bounds for certain k-csps, FOCS, IEEE
Computer Society, 2008, pp. 593–602. 8

[Tre09]

Luca Trevisan, Max cut and the smallest eigenvalue, STOC, ACM, 2009, pp. 263–272. 1

[TS14]

Ryota Tomioka and Taĳi Suzuki, Spectral norm of random tensors, arXiv preprint
arXiv:1407.1870 (2014). 9

[Wei17]

Benjamin Weitz, Polynomial proof systems, effective derivations, and their applications in the
sum-of-squares hierarchy, Ph.D. thesis, UC Berkeley, 2017. 42

[ZHT06]

Hui Zou, Trevor Hastie, and Robert Tibshirani, Sparse principal component analysis,
Journal of Computational and Graphical Statistics 15 (2006), no. 2, 265–286. 2

39

A

Bounding the sum-of-squares proof ideal term

We give conditions under which sum-of-squares proofs are well-conditioned, using techniques
similar to those that appear in [RW17] for bounding the bit complexity of SoS proofs. We begin
with some deﬁnitions.
Definition A.1. Let P be a polynomial optimization problem and let D be the uniform distribution
over the set of feasible solutions S for P. Deﬁne the degree-2d moment matrix of D to be
X D  s∼D [ ŝ ⊗2d ], where ŝ  [1 s]⊤ .
• We say that P is k-complete on up to degree 2d if every zero eigenvector of X D has a degree-k
derivation from the ideal constraints of P.
Theorem A.2. Let P be a polynomial optimization problem over variables x ∈ n of degree at most 2d,
with objective function f (x) and ideal constraints {1 j (x)  0} j∈[m] . Suppose also that P is 2d-complete up
to degree 2d. Let G be the matrix of ideal constraints in the degree-2d SoS proof for P. Then if
• the SDP optimum value is bounded by n O(d)
• the coefficients of the objective function are bounded by n O(d) ,
• there is a set of feasible solutions S ⊆ n with the property that for each α ⊆ [n]d , |α| 6 d for
which χα is not identically zero over the solution space, there exists some s ∈ S such that the square
monomial χα (s)2 > n −O(d) ,
it follows that the SoS certificate for the problem is well-conditioned, with no value larger than n O(d).
To prove this, we essentially reproduce the proof of the main theorem of [RW17], up to the very
end of the proof at which point we slightly deviate to draw a diﬀerent conclusion.
Proof. Following our previous convention, the degree-2d sum-of-squares proof for P is of the form
sdpOpt − f (x)  a(x) + 1(x),
where the 1(x) is a polynomial in the span of the ideal constraints, and A is a sum of squares of
polynomials. Alternatively, we have the matrix characterization,
sdpOpt −hF, x̂ ⊗2d i  hA, x̂ ⊗2d i + hG, x̂ ⊗2d i,
where x̂  [1 x]⊤ , F, A, and G are matrix polynomials corresponding to f , a, and 1 respectively,
and with A  0.
Now let s ∈ S be a feasible solution. Then we have that
sdpOpt −hF, s ⊗2d i  hA, s ⊗2d i + hG, s ⊗2d i  hA, s ⊗2d i,
where the second equality follows because each s ∈ S is feasible. By assumption the left-hand-side
is bounded by n O(d).
We will now argue that the diagonal entries of A cannot be too large. Our ﬁrst step is to argue
that A cannot have nonzero diagonal entries unless there is a solution element in the solution
Let X D  [x ⊗2d ] be the 2d-moment matrix of the uniform distribution of feasible solutions to

40

P. Deﬁne Π to be the orthogonal projection into the zero eigenspace of X D . By linearity and
orthonormality, we have that
hX D , Ai  X D , (Π + Π⊥ )A(Π + Π⊥ )

 X D , Π⊥ AΠ⊥ + X D , ΠAΠ⊥ + X D , Π⊥ AΠ + hX D , ΠAΠi .

By assumption P is 2d-complete on D up to degree 2d, and therefore Π is derivable in degree 2d
from the ideal constraints {1 j } j∈[m] . Therefore, the latter three terms may be absorbed into G, or
more formally, we can set A′  Π⊥ AΠ⊥ , G′  G + (Π + Π⊥ )A(Π + Π⊥ ) − Π⊥ AΠ⊥ , and re-write the
original proof
sdpOpt −hF, x̂ ⊗2d i  hA′ , x̂ ⊗2d i + hG′ , x̂ ⊗2d i.

(A.1)

The left-hand-side remains unchanged, so we still have that it is bounded by n O(d) for any feasible
solution s ∈ S. Furthermore, the nonzero eigenspaces of X D and A′ are identical, and so A′ cannot
be nonzero on any diagonal entry which is orthogonal to the space of feasible solutions.
Now, we argue that every diagonal entry of A′ is at most n O(d) . To see this, for each diagonal
term χ2α , we choose the solution s ∈ S for which χα (s)2 > n −O(d) . We then have by the PSDness of
A′ that
A′α,α · χα (s)2 6 hs ⊗2d , A′i 6 n O(d) ,
which then implies that A′α,α 6 n O(d) . It follows that Tr(A′) 6 n O(d) , and again since A′ is PSD,
kA′ kF 6

p

Tr(A′) 6 n O(d) .

(A.2)

Putting things together, we have from our original matrix identity (A.1) that
kG′ kF  k sdpOpt −A′ − F kF

6 k sdpOpt kF + kA′ kF + kF kF
6 k sdpOpt kF + n O(d) + kF kF

(triangle inequality)

(from (A.2)).

Therefore by our assumptions that k sdpOpt k, kF kF  n O(d) , the conclusion follows.



We now argue that the conditions of this theorem are met by several general families of
problems.
Corollary A.3. The following problems have degree-2d SoS proofs with all coefficients bounded by n O(d) :
1. The hypercube: Any polynomial optimization problem with the only constraints being {x 2i  x i }i∈[n]
or {x 2i  1}i∈[n] and objective value at most n O(d) over the set of integer feasible solutions. (Including
max k-csp).
2. The hypercube with balancedness constraints: Any polynomial optimization problem with the only
Í
constraints being {x 2i − 1}i∈[n] ∪ { i x i  0}. (Including community detection).

Í

3. The unit sphere: Any polynomial optimization problem with the only constraints being { i∈[n] x 2i  1}
and objective value at most n O(d) over the set of integer feasible solutions. (Including tensor PCA).

41

4. The sparse hypercube: As long as 2d 6 k, any polynomial optimization problem with the only
Í
Í
constraints being {x 2i  x i }i∈[n] ∪ { i∈[n] x i  k}, or {x 3i  x i }i∈[n] ∪ { i∈[n] x 2i  k}, and objective
value at most n O(d) over the set of integer feasible solutions. (Including densest k-subgraph and the
Boolean version of sparse PCA).
5. The max clique problem.
We prove this corollary below. For each of the above problems, it is clear that the objective value
is bounded and the objective function has no large coeﬃcients. To prove this corollary, we need to
verify the completeness of the constraint sets, and then demonstrate a set of feasible solutions so
that each square term receives non-negligible mass from some solution.
A large family of completeness conditions were already veriﬁed by [RW17] and others (see the
references therein):
Proposition A.4 (Completeness of canonical polynomial optimization problems (from Corollary
3.5 of [RW17])). The following pairs of polynomial optimization problems P and distributions over solutions
D are complete:
1. If the feasible set is x ∈ n with {x 2i  1}i∈[n] or {x 2i  x i }i∈[n] , P is d-complete up to degree d
Í
(e.g. if P is a CSP). This is still true of the constraints {x 2i  1}i∈[n] ∪ { i x i  0} (e.g. if P is a
community detection problem).
2. If the feasible set is x ∈ n with
is the tensor PCA problem).

Í

i∈[n]

x 2i  α, then P is d-complete on D up to degree d (e.g. if P

3. If P is the max clique problem with feasible set x ∈ n with {x 2i  x i }i∈[n] ∪ {x i x j  0}(i, j)∈E , then
P is d-complete on D up to degree d.
A couple of additional examples can be found in the upcoming thesis of Benjamin Weitz
[Wei17]:
Proposition A.5 (Completeness of additional polynomial optimization problems) [Wei17]). The
following pairs of polynomial optimization problems P and distributions over solutions D are complete:
1. If P is the densest k-subgraph relaxation, with feasible set x ∈ n with {x 2i  x i }i∈[n] ∪ {
k}, P is d-complete on D up to degree d 6 k.

Í

i∈[n]

xi 

2. If P is the sparse PCA relaxation with sparsity k, with feasible set x ∈ n with {x 3i  x i }i∈[n] ∪
Í
{ i∈[n] x 2i  k}, P is d-complete up to degree d 6 k/2.

Proof of Corollary A.3. We verify the conditions of Theorem A.2 separately for each case.

1. The hypercube: the completeness conditions are satisﬁed by Proposition A.4. We choose the
® for which χ2α (s)  1 always.
set of feasible solutions to contain a single point, s  1,
2. The hypercube with balancedness constraints: the completeness conditions are satisﬁed by
Proposition A.4. We choose the set of feasible solutions to contain a single point, s, some
perfectly balanced vector, for which χ2α (s)  1 always.
42

3. The unit sphere: the completeness conditions are satisﬁed by Proposition A.4. We choose
the set of feasible solutions to contain a single point, s  √1n · ®1, for which χ2α (s) > n −d as long
as |α| 6 d, which meets the conditions of Theorem A.2.
4. The sparse hypercube: the completeness conditions are satisﬁed by Proposition A.5. Here,
Í
we choose the set of solutions S  {x ∈ {0, 1} n | i x i  k}. as long as k > d, for any |α| 6 d
we have that χS (x)2  1 when s is 1 on α.
5. The max clique problem: the completeness conditions are satisﬁed by Proposition A.4. We
choose the solution set S to be the set of 0, 1 indicators for cliques in the graph. Any α
that corresponds to a non-clique in the graph has χα identically zero in the solution space.
Otherwise, χα (s)2  1 when s ∈ S is the indicator vector for the clique on α.
This concludes the proof.



B Lower bounds on the nonzero eigenvalues of some moment matrices
In this appendix, we prove lower bounds on the magnitude of nonzero eigenvalues of covariance
matrices for certain distributions over solutions. Many of these bounds are well-known, but we
re-state and re-prove them here for completeness. We ﬁrst deﬁne the property we want:
Definition B.1. Let P be a polynomial optimization problem and let D be the uniform distribution
over the set of feasible solutions S for P. Deﬁne the degree-2d moment matrix of D to be
X D  x∼D [ x̂ ⊗2d ], where x̂  [1 x]⊤ .
• We say that D is δ-spectrally rich up to degree 2d if every nonzero eigenvalue of X D is at least
δ.
Proposition B.2 (Spectral richness of polynomial optimization problems). The following distributions
over solutions D are polynomially spectrally rich:
1. If D is the uniform distribution over {±1} n , then D is polynomially spectrally rich up to degree
d 6 n.
2. If D is the uniform distribution over α · Sn−1 , then D is polynomially spectrally rich up to degree
d 6 n.
3. If D is the uniform distribution over x ∈ {1, 0} n with kx k0  k, then if 2d 6 k, D is polynomially
spectrally rich up to degree d.
4. If D is the uniform distribution over x ∈ {±1, 0} n with kx k0  k, then if 2d 6 k, D is polynomially
spectrally rich up to degree d.
def

Proof. In the proof of each statement, denote the 2dth moment matrix of D by X D  x∼D [x ⊗2d ].
Because X D is a sum of rank-1 outer-products, an eigenvector of X D has eigenvalue 0 if and only if it
is orthogonal to every solution in the support of D, and therefore the zero eigenvectors correspond
exactly to the degree at most d constraints that can be derived from the ideal constraints.

43

Now, let p1 (x), . . . , p r (x) be a basis for polynomials of degree at most 2d in x which is orthonormal with respect to D, so that
x∼D

[p i (x)p j (x)] 

(

1

ij

0 otherwise

If p̂ i is the representation of p i in the monomial basis, we have that
(p̂ i )⊤ X D p̂ j 
Therefore, the matrix R 

Í

⊤
i e i ( p̂ i )

x∼D

[p i (x)p j (x)].

diagonalizes X D ,
RX D R ⊤  Id .

It follows that the minimum non-zero eigenvalue of X D is equal to the smallest eigenvalue of
(RR ⊤ )−1 , which is in turn equal to σ 1(R)2 where σmax (R) is the largest singular value of R. Therefore,
max
for each of these cases it suﬃces to bound the singular values of the change-of-basis matrix
between the monomial basis and an orthogonal basis over D. We now proceed to handle each
case separately.
1. D uniform over hypercube: In this case, the monomial basis is an orthogonal basis, so R is the
identity on the space orthogonal to the ideal constraints, and σmax (R)  1, which completes
the proof.
2. D uniform over sphere: Here, the canonical orthonormal basis the spherical harmonic
polynomials. Examining an explicit characterization of the spherical harmonic polynomials
(given for example in [DX13], Theorem 5.1), we have that when expressing p i in the monomial
basis, no coeﬃcient of a monomial (and thus no entry of p̂ i ) exceeds n O(d) , and since there

Í
are at most n d polynomials each with di0 nd 6 n d coeﬃcients, employing the triangle
inequality we have that σmax (R) 6 n O(d) , which completes the proof.
3. D uniform over {x ∈ {0, 1} k | kx k0  k}: In this case, the canonical orthonormal basis is
the correctly normalized Young’s basis (see e.g. [Fil16] Theorems 3.1,3.2 and 5.1), and agan
we have that when expressing an orthonormal basis polynomial p i in the monomial basis,
no coeﬃcient exceeds n O(d) . As in the above case, this implies that σmax (R) 6 n O(d) and
completes the proof.
4. D uniform over {x ∈ {±1, 0} k | kx k0  k}: Again the canonical orthonormal basis is Young’s
basis with a correct normalization. We again apply [Fil16] Theorems 3.1,3.2, but this time we
calculate the normalization by hand: we have that in expressing each p i , no element of the
monomial basis has coeﬃcient larger than n O(d) multiplied by the quantity

x∼D

"

d
Ö
i1

2

(x2i−1 − x2i )

#

 O(1).

This gives the desired conclusion.


44

C

From Boolean to Gaussian lower bounds

In this section we show how to prove our SoS lower bounds for Gaussian PCA problems using the
lower bounds for Boolean problems in a black-box fashion. The techniques are standard and more
broadly applicable than the exposition here but we prove only what we need.
The following proposition captures what is needed for tensor PCA; the argument for sparse
PCA is entirely analogous so we leave it to the reader.
n
Proposition C.1. Let k ∈  and let A ∼ {±1}( k ) be a symmetric random Boolean tensor. Suppose that for
n
every A ∈ {±1}( k ) there is a degree-d pseudodistribution ˜ satisfying {kx k 2  1} such that

A

˜ hx ⊗k , Ai  C .

n
Let T ∼ N(0, 1)( k ) be a Gaussian random tensor. Then

T

max ˜ hx ⊗k , Ti > Ω(C)
˜

where the maximization is over pseudodistributions of degree d which satisfy {kx k 2  1}.
Proof. For a tensor T ∈ (n )⊗k , let A(T) have entries A(T)α  sign(Tα ). Now consider
T

˜ A(T) hx ⊗k , Ti 

Õ
α

T

˜ A(T) x α Tα

where α ranges over multi-indices of size k over [n]. We rearrange each term above to
A(T)

where 1 ∼ N(0, 1). Since

( ˜ A(T) x α ) ·

Tα | A(T)

Tα 

( ˜ A(T) x α ) · A(T)α ·

A(T)

|1 |

|1 | is a constant independent of n, all of this is
Ω(1) ·

Õ
α

A

˜ A x α · Aα  C .

45



