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

Matthew Brennan, Guy Bresler
Proceedings of the Thirty-Second Conference on Learning Theory, PMLR 99:469-470, 2019.

Abstract

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 ($\textsc{pc}$) conjecture. All previous reductions 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 given weak forms of the $\textsc{pc}$ conjecture. We give a reduction from $\textsc{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 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 $\textsc{pc}$ is $\text{polylog}(N)$, rather than on the order $N^{1/2}$ as is widely conjectured. This is the first instance of a suboptimal hardness assumption implying optimal lower bounds for another problem in unsupervised learning.

Cite this Paper

BibTeX
@InProceedings{pmlr-v99-brennan19b, title = {Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness}, author = {Brennan, Matthew and Bresler, Guy}, booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory}, pages = {469--470}, year = {2019}, editor = {Beygelzimer, Alina and Hsu, Daniel}, volume = {99}, series = {Proceedings of Machine Learning Research}, month = {25--28 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v99/brennan19b/brennan19b.pdf}, url = {https://proceedings.mlr.press/v99/brennan19b.html}, abstract = {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 ($\textsc{pc}$) conjecture. All previous reductions 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 given weak forms of the $\textsc{pc}$ conjecture. We give a reduction from $\textsc{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 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 $\textsc{pc}$ is $\text{polylog}(N)$, rather than on the order $N^{1/2}$ as is widely conjectured. This is the first instance of a suboptimal hardness assumption implying optimal lower bounds for another problem in unsupervised learning.} }
Endnote
%0 Conference Paper %T Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness %A Matthew Brennan %A Guy Bresler %B Proceedings of the Thirty-Second Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2019 %E Alina Beygelzimer %E Daniel Hsu %F pmlr-v99-brennan19b %I PMLR %P 469--470 %U https://proceedings.mlr.press/v99/brennan19b.html %V 99 %X 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 ($\textsc{pc}$) conjecture. All previous reductions 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 given weak forms of the $\textsc{pc}$ conjecture. We give a reduction from $\textsc{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 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 $\textsc{pc}$ is $\text{polylog}(N)$, rather than on the order $N^{1/2}$ as is widely conjectured. This is the first instance of a suboptimal hardness assumption implying optimal lower bounds for another problem in unsupervised learning.
APA
Brennan, M. & Bresler, G.. (2019). Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness. Proceedings of the Thirty-Second Conference on Learning Theory, in Proceedings of Machine Learning Research 99:469-470 Available from https://proceedings.mlr.press/v99/brennan19b.html.

Related Material