Source-linked AI summary
The power of sum-of-squares for detecting hidden structures
Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer
TL;DR
The paper asks whether SoS algorithms are equivalent to low-degree spectral methods for planted problems and whether strong SoS lower bounds hold for tensor and sparse PCA. It proves broad equivalence through low-degree matrix polynomials and establishes lower bounds suggesting that sparse PCA may require subexponential time to improve existing algorithms.
Problem
It was unclear whether SoS guarantees for planted problems could always be achieved by spectral methods and how computationally hard tensor and sparse PCA remain beyond known algorithms.
Method
The paper relates degree-d SoS relaxations to eigenvalue computations on matrices whose entries are low-degree polynomials of the input, and uses related techniques to construct SoS lower bounds.
Results
For a wide class of planted problems, degree-d matrix-polynomial eigenvalue methods are as powerful as roughly degree-d SoS programs, while tensor and sparse PCA admit strong SoS lower bounds.
Takeaways & Limitations
The guarantees of bulky SoS relaxations can be matched by lightweight eigenvalue computations, while improving known sparse PCA algorithms may require subexponential time.
Takeaways & Limitations
Handling polynomial inequalities with slack variables can invalidate the robust inference property, and one theorem assumes a specific instance-rerandomization condition.
Abstract
from arXiv · showhide
We study planted problems---finding hidden structures in random noisy inputs---through the lens of the sum-of-squares semidefinite programming hierarchy (SoS). This family of powerful semidefinite 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 semidefinite programs of roughly degree d. For such problems it is therefore always possible to match the guarantees of SoS without solving a large semidefinite program. Using related ideas on SoS algorithms and low-degree matrix polynomials (and inspired by recent work on SoS and the planted clique problem by Barak et al.), we prove new nearly-tight SoS lower bounds for the tensor and sparse principal component analysis problems. Our lower bounds for sparse principal component analysis are the first to suggest that going beyond existing algorithms for this problem may require sub-exponential time.
1 Introduction
The paper establishes an equivalence between SoS algorithms and low-degree spectral methods for a broad class of planted problems, while proving strong SoS lower bounds for tensor and sparse PCA. These results connect lightweight eigenvalue computations with SoS guarantees and provide evidence for information-computation gaps.
- SoS and spectral algorithms: Classical spectral algorithms use top eigenvectors of input-derived matrices, whereas newer methods use matrices whose entries are low-degree input polynomials.This construction can improve accuracy and robustness against noise while retaining eigenvector-based computation.
- SoS and spectral algorithms: Theorem 1.1 shows that low-degree matrix-polynomial spectral methods match roughly comparable-degree SoS guarantees for a wide class of planted distinguishing problems.The scope includes refuting random CSPs, tensor and sparse PCA, densest-k-subgraph, stochastic block models, and planted clique.
- SoS and spectral algorithms: A single top-eigenvalue computation can recover the performance guarantees of a substantially larger semidefinite-programming relaxation.The resulting algorithm requires eigenvector computations instead of general semidefinite programming.
- SoS lower bounds: The paper proves new strong exponential SoS lower bounds for tensor PCA and sparse PCA, extending techniques pioneered in prior work.The bounds target 2^n^Ω(1) time or n^Ω(1) degree algorithms.
- SoS lower bounds: For tensor PCA, degree-n^Ω(ε) SoS cannot distinguish planted and random distributions when λ ≪ n^3/4−ε.The result follows because the relaxation cannot certify that a random 3-tensor has maximum value much less than n^3/4−ε.
- SoS lower bounds: The sparse PCA lower bound is the strongest known efficient-algorithm impossibility result for that problem and the first evidence that subexponential time may be necessary.The paper also states that its lower bounds suggest quasipolynomial-time recovery from O(k log p) samples is extremely unlikely.
2 Distinguishing Problems and Robust Inference
The paper formalizes planted distinguishing problems using polynomial systems and introduces robust inference, requiring solutions inferred from subsamples to remain feasible on most full instances.
- Distinguishing Problems: Distinguishing problems separate a planted distribution from a product “uniform” distribution using an instance sampled from either source.The goal is to identify the source with probability greater than 1/2 by a constant margin.
- Polynomial Systems: Polynomial systems encode optimization problems through program variables for solutions and instance variables for input data.Their degrees are tracked separately in program and instance variables.
- Planted Distributions: The planted distribution is formed by uniformly mixing instance distributions conditioned on each feasible planted solution.For each fixed solution, the conditional distribution is uniform over instances satisfying the polynomial system.
- Robust Inference: Robust inference requires that a solution inferred from a sampled sub-instance remains feasible for most settings of the full instance.The property is quantified by an error probability that can be negligible in n and d.
- Main Theorem: The main theorem connects robustly inferable polynomial systems and bounded-degree SoS refutations to low-degree matrix-polynomial distinguishers.Its framework is verified for planted clique, random CSPs, stochastic block models, densest-k-subgraph, tensor PCA, and sparse PCA.
- Main Theorem: A refinement measures polynomial degree through the relevant substructure, such as vertices rather than edges in planted clique.The distinguisher lies in the span of monomials associated with subsampling-operator eigenspaces.
3 Moment-Matching Pseudodistributions
The paper constructs moment-matching pseudodistributions through an exponentially large PSD matrix-valued program, then uses duality to relate SoS feasibility to low-degree spectral distinguishers.
- SoS Lower Bounds: Conversely, if no such spectral algorithm exists and robust inference holds, then with high probability no corresponding bounded-degree SoS refutation exists.This contrapositive is the core route from spectral indistinguishability to SoS lower bounds.
- Moment-Matching Pseudodistributions: The pseudodistribution program searches for a PSD matrix-valued function matching low-degree moments of a planted reference solution.The candidate function is supported over most instances rather than only planted instances.
- Moment-Matching Pseudodistributions: Its objective minimizes Tr(P^2), which serves as a proxy for collision probability and distributional entropy once Tr(P) is fixed.The moment constraints fix Tr(P), leaving the squared-trace objective to control concentration.
- Duality: The dual formulation supplies low-degree matrix polynomials and PSD matrices that certify departures from feasible SoS solutions.The construction uses strong duality and PSD projection in the dual optimization.
- Duality: If the SoS program has a large objective value, a low-degree matrix polynomial provides a spectral distinguishing algorithm.The spectral score is obtained from the largest nonnegative eigenvalue of the matrix polynomial.
- SoS Lower Bounds: The argument depends on the distributional relationship between planted and uniform instances rather than the particular matrix representation of planted solutions.The PSD matrix-valued proxy represents solution monomials, but its specific structure does not affect the equivalence argument.
4 Proof of Theorem 2.6
The proof constructs a pseudodistribution that is nearly feasible for the SoS relaxation while showing that any sufficiently distinguishing spectral object would contradict the absence of low-degree distinguishers.
- The proof constructs PSD matrix-valued functions ΛS from robust inference and averages them into a global PSD function Λ.Each ΛS is feasible with high probability, so their average is close to feasible for the original instance.
- The contrapositive reduces the theorem to constructing an approximately feasible SoS solution when no suitable spectral distinguisher exists.Duality supplies an object close to a feasible SDP solution under the no-distinguisher assumption.
- If a low-degree matrix distinguisher existed for a subinstance, averaging it over omitted coordinates would produce a forbidden scalar distinguisher for the original distributions.The scalar reduction preserves degree because averaging settings of variables cannot increase polynomial degree.
- Random restriction shows that averaging over subinstances controls the low-degree part of matrix-valued functions while suppressing high-degree contributions.The argument decomposes restricted functions into low- and high-degree components and bounds the latter using orthogonality and Cauchy–Schwarz.
- Projection onto the ideal preserves approximate equality constraints with controlled degree growth, allowing the constructed object to satisfy the SoS constraints.The projection obeys deg(ΠGQ) ⩽ deg(Q) + 2k and removes sufficiently low-degree monomials from high-degree components.
- For polynomial inequalities, slack variables preserve the formal reduction but can invalidate robust inference because their values may depend on the full instance.A feasible solution on a subinstance may not determine compatible slack variables after the remaining instance coordinates are revealed.
5 Applications to Classical Distinguishing Problems
The theorem is instantiated across classical planted distinguishing problems by verifying robust inference and conditioning requirements for their SoS formulations. The resulting bounds cover clique, CSPs, community detection, densest-k-subgraph, tensor PCA, and sparse PCA.
- Planted clique: Theorem 2.6 applies to planted clique when the objective satisfies obj ⩽ n^{δ−ε} for ε ⩾ c·d.The proof uses vertex subsampling, which preserves clique feasibility and retains a planted clique with high probability.
- Random CSP refutation: For random k-CSP refutation, Theorem 2.6 applies when obj ⩽ (1 − δ − ε)m for ε ⩾ c·d log n.Constraint subsampling preserves Boolean feasibility and yields robust inference through concentration.
- Community detection: Community detection satisfies the theorem when obj ⩽ (1 − ε)(2a − b)^{D−3d} for ε at least c·d log n divided by a constant-scale signal term.The construction subsamples edges while preserving Booleanity and balancedness constraints.
- Densest-k-subgraph: Densest-k-subgraph satisfies the theorem when k^2(p + q) ≫ d log n and obj ⩽ (1 − ε)(p + q)k^{D−3d}.Independent edge subsampling preserves the Booleanity and sparsity constraints.
- Tensor PCA: For tensor PCA, Theorem 2.6 applies when λn^{−ε} ≫ log n and obj ⩽ λn^{−ε}.For Gaussian PCA models, degree counts distinct variables rather than powers, producing a non-standard low-degree notion.
- Sparse PCA: For sparse PCA, Theorem 2.6 applies when kn^{−ε/2} ≫ log n and obj ⩽ k^{2−ε}m.The Gaussian formulation likewise uses degree defined by the number of distinct variables in a monomial.
6 Exponential lower bounds for PCA problems
The paper derives exponential-time lower bounds for tensor and sparse PCA by analyzing low-degree polynomial distinguishers and constructing SoS integrality gaps. These results show that high-degree SoS relaxations can remain ineffective below the signal levels handled by known algorithms.
- Tensor PCA: When λ ≪ n^{3/4−ε}, degree n^{o(1)} polynomials cannot distinguish the planted and null tensor PCA distributions.The low-degree density projection has norm much smaller than one in this regime.
- Tensor PCA: The tensor PCA lower bound follows by expanding the planted density in the Hermite basis and bounding contributions from even-degree hypergraphs.For λ^2 ⩽ n^{3/2−ε} and d ⩽ n^{O(ε)}, the relevant sum is o(1).
- Tensor PCA: The natural tensor PCA SoS relaxation has a large integrality gap when λ is slightly below n^{k/4}, even at degree n^{Ω(1)}.The Boolean lower bound transfers to Gaussian tensors using standard techniques.
- Sparse PCA: For sparse PCA, even degree n^{Ω(ε)} SoS programs fail to distinguish planted and null matrices when λ < n^{1/2−ε} and k^{1−ε}.The hard regime lies outside the signal ranges where ordinary PCA and diagonal thresholding identify the planted coordinates.
- Sparse PCA: The sparse PCA theorem also yields an integrality gap of at least min(n^{ρ/2−ε}, n^{1/2−ρ/2−ε}) for k = n^ρ.This is interpreted as a gap for maximizing a quadratic form over k-sparse unit vectors.
- Sparse PCA: The paper conjectures that improving known sample-complexity algorithms for the spiked-Wishart sparse PCA model by polynomial factors requires n^{Ω(1)} SoS degree.Applying the proof directly to that model is technically complicated, so the statement remains a conjecture.
A Bounding the sum-of-squares proof ideal term
This section establishes conditions ensuring that degree-2d SoS certificates are well-conditioned, then verifies them for several canonical polynomial optimization problems. The resulting bound applies across hypercube, sphere, sparse, balanced, and clique settings.
- If the SDP optimum, objective coefficients, and solution-square masses are bounded by n^O(d), the degree-2d SoS certificate has no coefficient larger than n^O(d).Each nonzero square monomial must receive mass at least n^-O(d) from some feasible solution.
- The proof uses matrix representations of SoS certificates and projects away directions orthogonal to the feasible-solution space.The projected PSD matrix preserves the relevant identity while restricting nonzero eigenspaces to feasible directions.
- The argument bounds diagonal entries, trace, and PSD matrix magnitude by evaluating square terms on feasible solutions.For each nonzero diagonal term, a feasible solution supplies sufficiently large mass; PSDness then controls the trace and matrix norm.
- The framework applies to polynomial optimization on the hypercube, balanced hypercube, unit sphere, sparse hypercube, and max clique.The listed applications include max-k-CSP, community detection, tensor PCA, densest-k-subgraph, and Boolean sparse PCA.
- Completeness and feasible-solution constructions verify the theorem’s conditions for the canonical problems, including sparse PCA and densest-k-subgraph under degree restrictions.For sparse hypercube problems, the construction uses solutions with exactly k active coordinates; max clique uses clique indicator vectors.
B Lower bounds on the nonzero eigenvalues of some moment matrices
This section relates the smallest nonzero eigenvalue of a solution moment matrix to a change-of-basis matrix, then proves polynomial spectral richness for several solution distributions. These bounds support the conditioning analysis for SoS proofs.
- Uniform distributions on the Boolean hypercube, scaled sphere, k-sparse Boolean vectors, and k-sparse signed vectors are polynomially spectrally rich.For sparse distributions, the stated degree range requires 2d ≤ k.
- Zero eigenvectors of a moment matrix correspond exactly to low-degree constraints derivable from the ideal constraints.This identifies the nullspace algebraically through orthogonality to every feasible solution in the distribution’s support.
- The minimum nonzero eigenvalue of the moment matrix equals 1/σ_max(R)^2, where R changes from an orthonormal polynomial basis to the monomial basis.Thus, bounding the change-of-basis singular value proves lower bounds on nonzero moment-matrix eigenvalues.
- For the uniform hypercube, the monomial basis is already orthogonal, so the change-of-basis matrix has σ_max(R) = 1.This directly yields the required eigenvalue lower bound on the subspace orthogonal to ideal constraints.
- For the sphere and sparse Boolean distributions, orthonormal polynomial bases have coefficients bounded by n^O(d) in the monomial basis.The sphere uses spherical harmonics, while sparse distributions use normalized Young’s bases.
C From Boolean to Gaussian lower bounds
This section transfers SoS lower bounds from Boolean tensor problems to Gaussian tensor problems using a sign transformation and comparison of Gaussian and Boolean random inputs. The tensor PCA argument is stated as the template for sparse PCA.
- The Gaussian tensor lower bound is obtained from a corresponding lower bound for a symmetric random Boolean tensor.The proposition assumes a degree-d Boolean pseudodistribution satisfying the sphere constraint for every Boolean tensor input.
- The tensor PCA proposition provides the needed transfer, while the sparse PCA argument is described as entirely analogous.The section presents the Gaussian reduction as a black-box method for these PCA problems.
- For a tensor T, the reduction forms a Boolean tensor A(T) by taking the sign of each entry of T.The proof then rearranges the resulting expression and uses a standard Gaussian variable representation.