# Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2019.

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

- [Planting Undetectable Backdoors in Machine Learning Models](https://mlsanity.com/paper/2204.06974/) (2022)
- [Oja's Algorithm for Streaming Sparse PCA](https://mlsanity.com/paper/2402.07240/) (2024)
- [Higher degree sum-of-squares relaxations robust against oblivious outliers](https://mlsanity.com/paper/2211.07327/) (2022)
- [Lower Bounds on the Total Variation Distance Between Mixtures of Two Gaussians](https://mlsanity.com/paper/2109.01064/) (2021)
- [Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps](https://mlsanity.com/paper/2402.15409/) (2024)
- [On the Statistical Complexity of Sample Amplification](https://mlsanity.com/paper/2201.04315/) (2022)
- [Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing](https://mlsanity.com/paper/2403.07862/) (2024)
- [Sparse PCA Beyond Covariance Thresholding](https://mlsanity.com/paper/2302.10158/) (2023)
- [Low-Degree Method Fails to Predict Robust Subspace Recovery](https://mlsanity.com/paper/2603.02594/) (2026)
- [Do algorithms and barriers for sparse principal component analysis extend to other structured settings?](https://mlsanity.com/paper/2307.13535/) (2023)
- [Logspace Reducibility From Secret Leakage Planted Clique](https://mlsanity.com/paper/2107.11886/) (2021)
- [Computationally efficient reductions between some statistical models](https://mlsanity.com/paper/2402.07717/) (2024)
- [Backdoor Channels Hidden in Latent Space: Extending Cryptographic Undetectability to Modern Neural Networks](https://mlsanity.com/paper/2605.13214/) (2026)

## Abstract (arXiv)

In the past decade, sparse principal component analysis has emerged as an archetypal problem for illustrating statistical-computational tradeoffs. This trend has largely been driven by a line of research aiming to characterize the average-case complexity of sparse PCA through reductions from the planted clique (PC) conjecture - which conjectures that there is no polynomial-time algorithm to detect a planted clique of size K = o(N1/2) in G(N, frac12). All previous reductions to sparse PCA either fail to show tight computational lower bounds matching existing algorithms or show lower bounds for formulations of sparse PCA other than its canonical generative model, the spiked covariance model. Also, these lower bounds all quickly degrade with the exponent in the PC conjecture. Specifically, when only given the PC conjecture up to K = o(Nα) where α < 1/2, there is no sparsity level k at which these lower bounds remain tight. If α ≤ 1/3 these reductions fail to even show the existence of a statistical-computational tradeoff at any sparsity k. We give a reduction from PC that yields the first full characterization of the computational barrier in the spiked covariance model, providing tight lower bounds at all sparsities k. We also show the surprising result that weaker forms of the PC conjecture up to clique size K = o(Nα) for any given α ∈ (0, 1/2] imply tight computational lower bounds for sparse PCA at sparsities k = o(nα/3). This shows that even a mild improvement in the signal strength needed by the best known polynomial-time sparse PCA algorithms would imply that the hardness threshold for PC is subpolynomial. This is the first instance of a suboptimal hardness assumption implying optimal lower bounds for another problem in unsupervised learning.