Sum-of-Squares Lower Bounds for Sparse PCA

Abstract

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\approx k\log p$ (Gaussian or Bernoulli) samples, but all {\em efficient} (polynomial time) algorithms known require $n\approx k^2$ 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.

to appear at NIPS 2015

References in corpus (3)

• Structured Sparse Principal Component Analysis
• Augmented sparse principal component analysis for high dimensional data
• Tight Lower Bounds for Planted Clique in the Degree-4 SOS Program

Cited by in corpus (10)

• Subexponential-Time Algorithms for Sparse PCA
• All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation
• The Overlap Gap Property in Principal Submatrix Recovery
• Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
• Sharp Computational-Statistical Phase Transitions via Oracle Computational Model
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• Distributed Estimation for Principal Component Analysis: an Enlarged Eigenspace Analysis
• Nonasymptotic Guarantees for Spiked Matrix Recovery with Generative Priors
• Sparse Phase Retrieval via Sparse PCA Despite Model Misspecification: A Simplified and Extended Analysis
• Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems