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

2019/02/19 by Matthew Brennan, Brennan, Matthew, Guy Bresler +1 · 4 citations
Computer Science · Engineering · Mathematics · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Fault Detection and Control Systems #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Probability (math.PR) #Statistical Methods and Inference #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.1902.07380

openalex publication_date 2019/02/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Citations

• Sparse Principal Component Analysis
• Optimal link prediction with matrix logistic regression
• Universality of Computational Lower Bounds for Submatrix Detection

Cited by

• Causal inference under interference: computational barriers and algorithmic solutions
• Subexponential-Time Algorithms for Sparse PCA
• Logspace Reducibility From Secret Leakage Planted Clique
• A greedy anytime algorithm for sparse PCA

Related

• Computational Lower Bounds for Sparse PCA
• Reducibility and Computational Lower Bounds for Problems with Planted\n Sparse Structure
• Do algorithms and barriers for sparse principal component analysis extend to other structured settings?
• On the Worst-Case Approximability of Sparse PCA
• NP-Hardness and Inapproximability of Sparse PCA