Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems

Aaron Potechin, Goutham Rajendran

Abstract: In this paper, we construct general machinery for proving Sum-of-Squares lower bounds on certification problems by generalizing the techniques used by Barak et al. [FOCS 2016] to prove Sum-of-Squares lower bounds for planted clique. Using this machinery, we prove degree $n^{\epsilon}$ Sum-of-Squares lower bounds for tensor PCA, the Wishart model of sparse PCA, and a variant of planted clique which we call planted slightly denser subgraph.

Introduction

In computational complexity, understanding the fundamental limits of algorithms is as critical as developing new ones. The Sum-of-Squares (SoS) hierarchy represents one of the most powerful tools in this endeavor. As a massive, flexible optimization framework that generalizes many of the best-known algorithms, SoS serves as a benchmark for computational hardness: if the SoS hierarchy cannot solve a problem, it is a strong indication that the problem is intrinsically difficult.

However, establishing "lower bounds"—mathematical proof that SoS fails—has historically been a grueling, problem-specific process. Proving that the SoS hierarchy cannot find a solution requires demonstrating that a complex, high-dimensional "moment matrix" is Positive Semidefinite (PSD). In their recent work, Aaron Potechin and Goutham Rajendran introduce a generalized machinery that simplifies this process, transforming the bespoke craft of lower-bound proofs into a systematic framework applicable to a wide range of statistical certification problems.

The Challenge of Certification

The paper focuses on certification problems, which involve proving that a random input does not contain a specific hidden structure. For example, given a random graph, one might seek to certify that it does not contain a clique of a certain size. While such structures are statistically unlikely to exist in random data, providing a mathematical guarantee that holds for every possible input is significantly more difficult than average-case prediction.

To prove a lower bound in this context, researchers must construct a "pseudo-expectation"—a linear functional that mimics the properties of a true probability distribution. The primary hurdle is proving the PSDness of the resulting moment matrix. Previously, this required re-deriving complex "intersection tradeoff" logic for every new problem, often resulting in hundreds of pages of dense mathematical proof.

A Unified Machinery

The authors overcome these hurdles by generalizing the pseudo-calibration technique, a heuristic used to estimate the SoS hierarchy’s internal state when confronted with random noise. Their framework relies on three primary components:

  1. Graph Matrices and Shapes: The massive moment matrix is decomposed into a linear combination of "graph matrices." These matrices are defined by small subgraphs, or "shapes," which represent the interactions between variables.
  2. Canonical Decomposition: The authors demonstrate that every shape has a natural decomposition into left, middle, and right components. This allows the moment matrix to be treated as a product of simpler, more manageable matrices.
  3. The Three Conditions: The core of the machinery is a theorem stating that an SoS lower bound follows automatically if three spectral conditions are met:
  4. PSD Mass: The primary component of the matrix must be positive.
  5. Middle Shape Bounds: Terms representing complex subgraphs must be sufficiently small to avoid destabilizing the positivity.
  6. Intersection Term Bounds: Errors introduced when "gluing" subgraphs together must be strictly controlled.

By shifting the analytical burden to these three conditions, the framework removes the need for problem-specific derivations of intersection logic.

Theoretical Benchmarks and Results

As a theoretical contribution, the paper evaluates the machinery against standard random distributions used as benchmarks in statistics and computer science, including Erdős-Rényi graphs, Gaussian tensors, and the Wishart model for Sparse PCA. The authors achieved several state-of-the-art results:

  • Tensor PCA: They proved that SoS cannot solve Tensor PCA for signal-to-noise ratios below $n^{k/4}$, matching the performance of the best known algorithms and suggesting a fundamental limit.
  • Sparse PCA: The authors provided the first high-degree SoS lower bounds for the Wishart model, filling a long-standing gap in the understanding of this problem's hardness.
  • Planted Slightly Denser Subgraph: They demonstrated that even when a subgraph is only marginally denser than its surroundings, SoS cannot distinguish it from pure randomness, even with sub-exponential running time.

Conclusion and Future Directions

This machinery represents a significant step toward proving the Low-Degree Conjecture—the hypothesis that the SoS hierarchy is no more powerful than simple low-degree polynomials for a wide class of symmetric problems.

While powerful, the current framework is optimized for "dense" problems. Future work remains to extend these techniques to "sparse" regimes (such as the Densest $k$-Subgraph problem) where missing edge indicators introduce new complexities. Additionally, refining the machinery to handle exact constraints, rather than the approximate constraints currently used in planted distributions, remains an important open challenge in the field.

Summary updated

Abstract

In this paper, we construct general machinery for proving Sum-of-Squares lower bounds on certification problems by generalizing the techniques used by Barak et al. [FOCS 2016] to prove Sum-of-Squares lower bounds for planted clique. Using this machinery, we prove degree $n^{\epsilon}$ Sum-of-Squares lower bounds for tensor PCA, the Wishart model of sparse PCA, and a variant of planted clique which we call planted slightly denser subgraph.
BibTeX
@misc{potechin2020machinery,
  author = {Aaron Potechin and Goutham Rajendran},
  title = {{Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems}},
  year = {2020},
  eprint = {2011.04253},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2011.04253},
}
Figure