# Low-Degree Method Fails to Predict Robust Subspace Recovery

arXiv: https://arxiv.org/abs/2603.02594 · HTML: https://mlsanity.com/paper/2603.02594/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 38 references that are in the map.
- First posted on arXiv 3 Mar 2026.

## Builds on (most cited first, 23 of 23)

- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017)
- [Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent](https://mlsanity.com/paper/2009.06107/) (2020)
- [Continuous LWE](https://mlsanity.com/paper/2005.09595/) (2020)
- [Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure](https://mlsanity.com/paper/1806.07508/) (2018)
- [An Overview of Robust Subspace Recovery](https://mlsanity.com/paper/1803.01013/) (2018)
- [Bayesian estimation from few samples: community detection and related problems](https://mlsanity.com/paper/1710.00264/) (2017)
- [Lattice-Based Methods Surpass Sum-of-Squares in Clustering](https://mlsanity.com/paper/2112.03898/) (2021)
- [Computational Complexity of Statistics: New Insights from Low-Degree Polynomials](https://mlsanity.com/paper/2506.10748/) (2025)
- [Non-Gaussian Component Analysis via Lattice Basis Reduction](https://mlsanity.com/paper/2112.09104/) (2021)
- [Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness](https://mlsanity.com/paper/1902.07380/) (2019)
- [SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions](https://mlsanity.com/paper/2403.04744/) (2024)
- [Counterexamples to the Low-Degree Conjecture](https://mlsanity.com/paper/2004.08454/) (2020)
- [Computational Lower Bounds for Sparse PCA](https://mlsanity.com/paper/1304.0828/) (2013)
- [Smoothed Analysis in Unsupervised Learning via Decoupling](https://mlsanity.com/paper/1811.12361/) (2018)
- [The Average-Case Time Complexity of Certifying the Restricted Isometry Property](https://mlsanity.com/paper/2005.11270/) (2020)
- [Algorithms approaching the threshold for semi-random planted clique](https://mlsanity.com/paper/2212.05619/) (2022)
- [Precise Error Rates for Computationally Efficient Testing](https://mlsanity.com/paper/2311.00289/) (2023)
- [Efficient Certificates of Anti-Concentration Beyond Gaussians](https://mlsanity.com/paper/2405.15084/) (2024)
- [Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing](https://mlsanity.com/paper/2403.07862/) (2024)
- [The Quasi-Polynomial Low-Degree Conjecture is False](https://mlsanity.com/paper/2505.17360/) (2025)
- [Learning Confidence Ellipsoids and Applications to Robust Subspace Recovery](https://mlsanity.com/paper/2512.16875/) (2025)

## Built on by (most cited first, 2 of 2)

- [Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps](https://mlsanity.com/paper/2604.17410/) (2026)
- [Detection of local geometry in random graphs: information-theoretic and computational limits](https://mlsanity.com/paper/2603.24545/) (2026)

## Abstract (arXiv)

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 ℝ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=nOmega(1). Moreover, the low-degree moments match exactly up to degree k=O(√log n/loglog 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.