Computational Lower Bounds for Sparse PCA

Abstract

In the context of sparse principal component detection, we bring evidence towards the existence of a statistical price to pay for computational efficiency. We measure the performance of a test by the smallest signal strength that it can detect and we propose a computationally efficient method based on semidefinite programming. We also prove that the statistical performance of this test cannot be strictly improved by any computationally efficient method. Our results can be viewed as complexity theoretic lower bounds conditionally on the assumptions that some instances of the planted clique problem cannot be solved in randomized polynomial time.

Alternate title: "Complexity Theoretic Lower Bounds for Sparse Principal Component Detection"

References in corpus (7)

• Sparse principal component analysis and iterative thresholding
• Sparse PCA: Optimal rates and adaptive estimation
• Optimal detection of sparse principal components in high dimension
• Global testing under sparse alternatives: ANOVA, multiple comparisons and the higher criticism
• Detection of an anomalous cluster in a network
• Computational and Statistical Tradeoffs via Convex Relaxation
• On combinatorial testing problems

Cited by in corpus (24)

• Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula
• Lower bounds on the performance of polynomial-time algorithms for sparse linear regression
• Statistical analysis of latent generalized correlation matrix estimation in transelliptical distribution
• Sparse PCA via Covariance Thresholding
• Sparse PCA through Low-rank Approximations
• Finding Hidden Cliques of Size \sqrt{N/e} in Nearly Linear Time
• Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix
• Sparse PCA with Oracle Property
• Subexponential-Time Algorithms for Sparse PCA
• Error regions in quantum state tomography: computational complexity caused by geometry of quantum states
• Parallel Tempering for the planted clique problem
• On the optimality of sliced inverse regression in high dimensions
• Computationally Efficient Robust Estimation of Sparse Functionals
• Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrieval
• Counterexamples to the Low-Degree Conjecture
• Sharp Computational-Statistical Phase Transitions via Oracle Computational Model
• From average case complexity to improper learning complexity
• Tensor SVD: Statistical and Computational Limits
• Sparse GCA and Thresholded Gradient Descent
• Statistical Limits of Convex Relaxations
• Nonasymptotic Guarantees for Spiked Matrix Recovery with Generative Priors
• Analyzing statistical and computational tradeoffs of estimation procedures
• ReFACTor: Practical Low-Rank Matrix Estimation Under Column-Sparsity
• An M* Proxy for Sparse Recovery Performance