# Sum-of-Squares Lower Bounds for Sparse PCA

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jul 2015.

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

- [Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors](https://mlsanity.com/paper/2106.15358/) (2021)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps](https://mlsanity.com/paper/2402.15409/) (2024)
- [Inferring Hidden Structures in Random Graphs](https://mlsanity.com/paper/2110.01901/) (2021)
- [Coordinate Descent Methods for Fractional Minimization](https://mlsanity.com/paper/2201.12691/) (2022)
- [Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs](https://mlsanity.com/paper/2203.02824/) (2022)
- [Planted Bipartite Graph Detection](https://mlsanity.com/paper/2302.03658/) (2023)
- [Sparse PCA Beyond Covariance Thresholding](https://mlsanity.com/paper/2302.10158/) (2023)
- [Sharp Analysis of Power Iteration for Tensor PCA](https://mlsanity.com/paper/2401.01047/) (2024)
- [Do algorithms and barriers for sparse principal component analysis extend to other structured settings?](https://mlsanity.com/paper/2307.13535/) (2023)

## Abstract (arXiv)

This paper establishes a statistical versus computational trade-off for solving a basic high-dimensional machine learning problem via a basic convex relaxation method. Specifically, we consider the em Sparse Principal Component Analysis (Sparse PCA) problem, and the family of em Sum-of-Squares (SoS, aka Lasserre/Parillo) convex relaxations. It was well known that in large dimension p, a planted k-sparse unit vector can be em in principle detected using only n ≈ klog p (Gaussian or Bernoulli) samples, but all em efficient (polynomial time) algorithms known require n ≈ k2 samples. It was also known that this quadratic gap cannot be improved by the the most basic em semi-definite (SDP, aka spectral) relaxation, equivalent to a degree-2 SoS algorithms. Here we prove that also degree-4 SoS algorithms cannot improve this quadratic gap. This average-case lower bound adds to the small collection of hardness results in machine learning for this powerful family of convex relaxation algorithms. Moreover, our design of moments (or "pseudo-expectations") for this lower bound is quite different than previous lower bounds. Establishing lower bounds for higher degree SoS algorithms for remains a challenging problem.