English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In the past decade, sparse principal component analysis has emerged as anarchetypal problem for illustrating statistical-computational tradeoffs. Thistrend has largely been driven by a line of research aiming to characterize theaverage-case complexity of sparse PCA through reductions from the plantedclique (PC) conjecture - which conjectures that there is no polynomial-timealgorithm to detect a planted clique of size $K = o(N^{1/2})$ in$\mathcal{G}(N, \frac{1}{2})$. All previous reductions to sparse PCA eitherfail to show tight computational lower bounds matching existing algorithms orshow lower bounds for formulations of sparse PCA other than its canonicalgenerative model, the spiked covariance model. Also, these lower bounds allquickly degrade with the exponent in the PC conjecture. Specifically, when onlygiven the PC conjecture up to $K = o(N^\alpha)$ where $\alpha < 1/2$, there isno sparsity level $k$ at which these lower bounds remain tight. If $\alpha \le1/3$ these reductions fail to even show the existence of astatistical-computational tradeoff at any sparsity $k$. We give a reductionfrom PC that yields the first full characterization of the computationalbarrier in the spiked covariance model, providing tight lower bounds at allsparsities $k$. We also show the surprising result that weaker forms of the PCconjecture up to clique size $K = o(N^\alpha)$ for any given $\alpha \in (0,1/2]$ imply tight computational lower bounds for sparse PCA at sparsities $k =o(n^{\alpha/3})$. This shows that even a mild improvement in the signalstrength needed by the best known polynomial-time sparse PCA algorithms wouldimply that the hardness threshold for PC is subpolynomial. This is the firstinstance of a suboptimal hardness assumption implying optimal lower bounds foranother problem in unsupervised learning.

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