Subexponential-Time Algorithms for Sparse PCA

Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira

Abstract

We study the computational cost of recovering a unit-norm sparse principal component $x \in \mathbb{R}^n$ planted in a random matrix, in either the Wigner or Wishart spiked model (observing either $W + \lambda xx^\top$ with $W$ drawn from the Gaussian orthogonal ensemble, or $N$ independent samples from $\mathcal{N}(0, I_n + \beta xx^\top)$, respectively). Prior work has shown that when the signal-to-noise ratio ($\lambda$ or $\beta\sqrt{N/n}$, respectively) is a small constant and the fraction of nonzero entries in the planted vector is $\|x\|_0 / n = \rho$, it is possible to recover $x$ in polynomial time if $\rho \lesssim 1/\sqrt{n}$. While it is possible to recover $x$ in exponential time under the weaker condition $\rho \ll 1$, it is believed that polynomial-time recovery is impossible unless $\rho \lesssim 1/\sqrt{n}$. We investigate the precise amount of time required for recovery in the "possible but hard" regime $1/\sqrt{n} \ll \rho \ll 1$ by exploring the power of subexponential-time algorithms, i.e., algorithms running in time $\exp(n^\delta)$ for some constant $\delta \in (0,1)$. For any $1/\sqrt{n} \ll \rho \ll 1$, we give a recovery algorithm with runtime roughly $\exp(\rho^2 n)$, demonstrating a smooth tradeoff between sparsity and runtime. Our family of algorithms interpolates smoothly between two existing algorithms: the polynomial-time diagonal thresholding algorithm and the $\exp(\rho n)$-time exhaustive search algorithm. Furthermore, by analyzing the low-degree likelihood ratio, we give rigorous evidence suggesting that the tradeoff achieved by our algorithms is optimal.

Introduction

Principal Component Analysis (PCA) is a fundamental tool in data science, used to identify the directions of greatest variance in high-dimensional datasets. In many modern applications, the underlying signal is expected to be sparse, meaning only a small subset of features contributes to the principal component. This variant, known as Sparse PCA, has long been characterized by a significant "statistical-to-computational gap."

In high-dimensional settings (dimension $n$), researchers have identified three distinct regimes based on the sparsity level $\rho$ (the fraction of non-zero entries):

  1. The Easy Regime: When the signal is highly sparse ($\rho \lesssim 1/\sqrt{n}$), simple polynomial-time algorithms like diagonal thresholding can recover the signal.
  2. The Impossible Regime: When the signal-to-noise ratio is too low, recovery is information-theoretically impossible.
  3. The "Possible but Hard" Regime: When $1/\sqrt{n} \ll \rho \ll 1$, recovery is mathematically possible (e.g., via exhaustive search), but it has long been conjectured that no polynomial-time algorithm can succeed.

This paper moves beyond the binary distinction of "fast" vs. "slow" by investigating subexponential-time algorithms. We ask: if we are willing to invest more than polynomial time, but less than full exponential time, how much more sparsity can we handle?

Methods and Algorithmic Framework

Mathematical Models

We analyze two standard benchmarks for Sparse PCA:

  • Spiked Wigner Model: We observe a matrix $Y = \lambda xx^\top + W$, where $W$ is a random matrix from the Gaussian Orthogonal Ensemble (GOE).
  • Spiked Wishart Model: We observe $N$ independent samples from a multivariate normal distribution $\mathcal{N}(0, I_n + \beta xx^\top)$.

The Subexponential Algorithm

We propose a two-step algorithmic framework that achieves a smooth tradeoff between runtime and recovery capability:

  1. Subexponential Partial Search: Instead of searching for the entire sparse support of size $k = \rho n$, which would require exponential time $\binom{n}{k}$, the algorithm searches over subsets of a much smaller size $\ell \approx n^\delta$ (where $0 < \delta < 1$). This step identifies a "partial" support in subexponential time, roughly $\exp(n^\delta)$.
  2. Refinement via Thresholding: Once a promising partial support is identified, the algorithm uses a thresholding technique to "clean up" the estimate, effectively expanding the partial support to recover the full support of the planted vector $x$.

Establishing Lower Bounds

To determine if our algorithms are optimal, we employ the Low-Degree Likelihood Ratio (LDLR) framework. This method predicts computational hardness by testing whether any polynomial of a certain degree can distinguish between the spiked model (data with a signal) and the null model (pure noise). If low-degree polynomials cannot distinguish the two, it provides strong evidence that no algorithm within a corresponding runtime class can succeed.

Key Insights and Results

The Smooth Tradeoff

Our primary contribution is the discovery of a continuous spectrum of complexity. We show that the runtime required to recover a signal with sparsity $\rho$ scales as $\exp(\rho^2 n)$. This result bridges the gap between existing methods:

  • When $\delta$ is small, the algorithm approaches the performance of diagonal thresholding (polynomial time).
  • When $\delta$ is large, it approaches the performance of exhaustive search (exponential time).

Algorithmic Guarantees

For any constant $\delta \in (0, 1)$, we provide an algorithm with runtime $\exp(n^{\delta+o(1)})$ that achieves exact support recovery, provided the sparsity $\rho$ satisfies $\rho \ll n^{(\delta-1)/2}$. This pins down the precise relationship between time and sparsity: to handle a sparsity $\rho$, one generally requires time $\exp(\lambda^{-2} \rho^2 n)$, where $\lambda$ is the signal-to-noise ratio.

Evidence of Optimality

By analyzing the LDLR, we prove that for the same regime where our algorithm fails, the norm of the low-degree likelihood ratio remains bounded. According to the "low-degree conjecture," this implies that the tradeoff achieved by our subexponential algorithms is the best possible. This suggests that the difficulty of the "hard" regime is not a result of algorithmic inefficiency but is rooted in the fundamental geometry of the Sparse PCA problem.

Conclusion and Future Work

This work provides a complete picture of the computational landscape of Sparse PCA, replacing the traditional "gap" with a smooth, predictable tradeoff. However, several avenues for future research remain:

  • Noise Robustness: Our results assume Gaussian noise. Future work should investigate whether these tradeoffs hold for heavy-tailed or non-Gaussian distributions.
  • Parameter Adaptivity: Current algorithms require prior knowledge of the sparsity level $\rho$ and the signal-to-noise ratio. Developing adaptive versions that succeed without these parameters is a key next step.
  • Formal Hardness Reductions: While the LDLR provides rigorous evidence, a formal reduction to a standard hard problem (like the Planted Clique conjecture) would further solidify the hardness results in the subexponential regime.

Summary updated

Abstract

We study the computational cost of recovering a unit-norm sparse principal component $x \in \mathbb{R}^n$ planted in a random matrix, in either the Wigner or Wishart spiked model (observing either $W + \lambda xx^\top$ with $W$ drawn from the Gaussian orthogonal ensemble, or $N$ independent samples from $\mathcal{N}(0, I_n + \beta xx^\top)$, respectively). Prior work has shown that when the signal-to-noise ratio ($\lambda$ or $\beta\sqrt{N/n}$, respectively) is a small constant and the fraction of nonzero entries in the planted vector is $\|x\|_0 / n = \rho$, it is possible to recover $x$ in polynomial time if $\rho \lesssim 1/\sqrt{n}$. While it is possible to recover $x$ in exponential time under the weaker condition $\rho \ll 1$, it is believed that polynomial-time recovery is impossible unless $\rho \lesssim 1/\sqrt{n}$. We investigate the precise amount of time required for recovery in the "possible but hard" regime $1/\sqrt{n} \ll \rho \ll 1$ by exploring the power of subexponential-time algorithms, i.e., algorithms running in time $\exp(n^\delta)$ for some constant $\delta \in (0,1)$. For any $1/\sqrt{n} \ll \rho \ll 1$, we give a recovery algorithm with runtime roughly $\exp(\rho^2 n)$, demonstrating a smooth tradeoff between sparsity and runtime. Our family of algorithms interpolates smoothly between two existing algorithms: the polynomial-time diagonal thresholding algorithm and the $\exp(\rho n)$-time exhaustive search algorithm. Furthermore, by analyzing the low-degree likelihood ratio, we give rigorous evidence suggesting that the tradeoff achieved by our algorithms is optimal.
BibTeX
@inproceedings{ding2024subexponential,
  author = {Yunzi Ding and Dmitriy Kunisky and Alexander S. Wein and Afonso S. Bandeira},
  title = {{Subexponential-Time Algorithms for Sparse PCA}},
  booktitle = {Found. Comput. Math},
  year = {2024},
  url = {https://openreview.net/forum?id=pkmiUvNZry},
}
Figure