Low-Degree Method Fails to Predict Robust Subspace Recovery

He Jia, Aravindan Vijayaraghavan

TL;DR

The "low-degree polynomial method" is a popular tool used to predict whether a high-dimensional statistical problem is computationally hard. This paper provides a "natural" counterexample—a specific case of robust subspace recovery—where the method predicts the problem is impossible to solve efficiently, yet a simple, robust algorithm exists that solves it in polynomial time.

What Problem Does This Paper Address?

In high-dimensional statistics, researchers often encounter "statistical-computational gaps": settings where a signal is mathematically present in the data, but no known algorithm can find it in a reasonable amount of time. To understand these gaps, the community relies on the Low-Degree Conjecture. This conjecture posits that if a problem cannot be solved by a low-degree polynomial of the input data, it is likely hard for all efficient algorithms.

The authors investigate whether this conjecture is truly universal. They focus on Robust Subspace Recovery (RSR), where the goal is to identify a low-dimensional subspace $S$ when a fraction of the data points lie exactly on $S$, while the rest are "outliers" drawn from a background distribution.

Methods

The paper approaches the problem from two sides: proving a theoretical "hardness" according to the low-degree method, and then providing an algorithm that proves the problem is actually "easy."

  1. Lower Bound Construction: The authors construct a "null" distribution (noise) and a "planted" distribution (signal + noise). The null distribution is a scale mixture of Gaussians—essentially a Gaussian where the variance (scale) is itself a random variable. They prove that the moments of these two distributions match exactly up to a certain degree, making them indistinguishable to any low-degree polynomial.
  2. The Algorithm: They present a "Noise Tolerant Algorithm" that leverages anti-concentration. Instead of looking at aggregate statistics (like moments), the algorithm samples small subsets of points ($d+1$ points for a $d$-dimensional subspace) and checks if they are nearly linearly dependent.
  3. Geometric Analysis: To prove the existence of their "moment-matching" distributions, they use tools from convex geometry, specifically Tukey depth, to show that their target moment vector lies within the "convex hull" of all possible valid distributions.

Datasets

Not discussed in the paper. As a theoretical work in computer science and statistics, the authors use synthetic, mathematically defined probability distributions (scale mixtures of Gaussians and planted subspaces) rather than empirical datasets.

Key Insights and Ideas

  • The Blind Spot of Moments: The most significant insight is that low-degree moments are excellent at capturing where data concentrates, but they are poor at capturing anti-concentration (the property that data points are "well-spread" and unlikely to cluster in specific ways).
  • Scale Mixtures as a "Cloaking Device": By using a scale mixture of Gaussians for the null model, the authors created a distribution that is rotationally invariant (looks the same from all angles) but has enough "spread" in its scale to fool polynomial-based tests.
  • Challenging Universality: The paper suggests that the Low-Degree Conjecture might only apply to problems where the "noise" is very well-behaved (like a standard Gaussian). For problems involving robust estimation or heavy-tailed noise, the conjecture may fail to predict tractability.

Key Results

  • Exact Moment Matching: The authors show that for a natural RSR problem, the first $k$ moments match exactly for $k = O(\sqrt{\log n / \log \log n})$.
  • High-Degree Failure: They prove that the "Low-Degree Advantage" (a measure of how well polynomials can distinguish signal from noise) remains small even for polynomials of very high degree ($k = n^{\Omega(1)}$). Under the standard conjecture, this should imply the problem requires exponential time.
  • Polynomial Time Success: Despite the predicted hardness, the authors provide a simple algorithm that runs in $O(mn)$ or $O(\binom{m}{d+1})$ time.
  • Robustness: The algorithm is shown to be robust against both relative error perturbations (where points are moved by a fraction of their distance from the origin) and additive noise.

Limitations and Future Work

  • Dimension Dependence: The proposed algorithm's complexity is exponential in the dimension of the hidden subspace ($d$). While $d$ is assumed to be a small constant in this paper, the algorithm becomes inefficient as $d$ grows.
  • Other Frameworks: The authors conjecture that their problem might also "fool" other popular hardness frameworks, such as the Statistical Query (SQ) model or the Sum-of-Squares (SoS) hierarchy. Proving this would further cement this problem as a fundamental challenge to our understanding of computational complexity in statistics.
  • Defining "Natural": The Low-Degree Conjecture is often caveated to apply to "natural" problems. This paper argues that RSR is a very natural problem, pushing the community to more precisely define what kinds of problems the conjecture actually covers.

Summary updated

Abstract

The low-degree polynomial framework has been highly successful in predicting computational versus statistical gaps for high-dimensional problems in average-case analysis and machine learning. This success has led to the low-degree conjecture, which posits that this method captures the power and limitations of efficient algorithms for a wide class of high-dimensional statistical problems. We identify a natural and basic hypothesis testing problem in $\mathbb{R}^n$ which is polynomial time solvable, but for which the low-degree polynomial method fails to predict its computational tractability even up to degree $k=n^{Ω(1)}$. Moreover, the low-degree moments match exactly up to degree $k=O(\sqrt{\log n/\log\log n})$. Our problem is a special case of the well-studied robust subspace recovery problem. The lower bounds suggest that there is no polynomial time algorithm for this problem. In contrast, we give a simple and robust polynomial time algorithm that solves the problem (and noisy variants of it), leveraging anti-concentration properties of the distribution. Our results suggest that the low-degree method and low-degree moments fail to capture algorithms based on anti-concentration, challenging their universality as a predictor of computational barriers.
BibTeX
@misc{jia2026low,
  author = {He Jia and Aravindan Vijayaraghavan},
  title = {{Low-Degree Method Fails to Predict Robust Subspace Recovery}},
  year = {2026},
  eprint = {2603.02594},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.02594},
}
Figure