Statistical-Computational Tradeoff in Single Index Models

Lingxiao Wang, Zhuoran Yang, Zhaoran WangNeurIPS 2019 · OpenReview

Introduction

In high-dimensional statistics, there is often a distinct "gap" between what is mathematically possible to solve given infinite computing power and what is practically feasible with efficient algorithms. This paper maps out that gap for Single Index Models (SIMs), proving that when the relationship between variables is non-linear and symmetric (such as in phase retrieval), practitioners must pay a "computational tax" in the form of significantly more data to make the problem tractable.

Single Index Models are a class of models where a response variable $Y$ depends on a high-dimensional, sparse vector $X$ through an unknown "link function" $f$, formulated as $Y = f(X^\top \beta^*) + \epsilon$.

When $f$ is roughly linear, powerful tools like the Lasso can recover the important features ($\beta^*$) using very few samples—roughly proportional to the sparsity $s$. However, when $f$ is symmetric (e.g., $f(x) = x^2$), the linear correlation between $Y$ and $X$ vanishes, causing standard methods like Lasso to fail.

Previous research identified a strange phenomenon in these symmetric cases: while information theory dictates that we should be able to recover $\beta^*$ with $O(s \log d)$ samples, all known efficient algorithms require $O(s^2 \log d)$ samples. This paper investigates whether this gap is a fundamental mathematical barrier and explores how it evolves as the link function transitions from "easy" (linear) to "hard" (symmetric).

Methodology: Proving Computational Hardness

To rigorously answer these questions, the authors employ several sophisticated theoretical frameworks, relying on mathematical proofs rather than empirical datasets:

  • Stein’s Associations: The authors use first- and second-order Stein’s identities to categorize link functions. "First-order" captures the linear correlation, while "second-order" captures quadratic-like dependencies.
  • Statistical Query (SQ) Model: Instead of attempting to prove hardness based on $P \neq NP$, they utilize the SQ model. This framework treats algorithms as entities that can only interact with data by asking for the expected value of a function. It is a standard method to prove that no "efficient" algorithm (using a polynomial number of queries) can solve a specific problem.
  • Mixture Interpolation: They construct a model that mixes a "linear-friendly" function and a "symmetric" function, controlled by a parameter $\alpha$. This allows them to study the "phase transition" as the problem shifts from easy to hard.
  • Signal Detection Framework: The problem is framed as a hypothesis test: can an algorithm distinguish between pure noise and a signal hidden in a Single Index Model?

The Linearity Dial and Regimes of Difficulty

The mixture probability $\alpha$ acts as a dial for the problem's difficulty. When $\alpha$ is large, the first-order correlation is strong, and the problem is computationally easy. As $\alpha$ drops, the linear signal disappears, and the computational cost skyrockets.

3D surface plot illustrating the computational gap as a function of the mixture parameter alpha and sample size n.

The paper confirms that the jump from $s$ to $s^2$ sample complexity is a fundamental computational barrier in the SQ model. Even an optimal polynomial-time algorithm cannot bypass this "tax." The authors identify three distinct phases of difficulty:

  1. Regime 1 (Hard): The linear signal is so weak that the computational gap is at its maximum and stays constant.
  2. Regime 2 (Transition): As the linear signal grows, the computational gap begins to shrink.
  3. Regime 3 (Easy): The linear signal is strong enough that the statistical and computational limits coincide, and the gap vanishes entirely.

Key Findings

  • Minimax Rates: The authors provide explicit formulas for the minimum signal-to-noise ratio (SNR) required for detection.
  • Computational Lower Bounds: They prove that for "hard" link functions, any algorithm using a polynomial number of queries must have a higher SNR (requiring more data) than what is theoretically required by an unbounded, all-powerful computer.
  • Parameter Estimation: These detection results are extended to show that the same barriers apply to estimating the vector $\beta^*$. Specifically, they confirm a long-standing conjecture in "sparse phase retrieval" regarding the $s^2$ sample complexity requirement for efficient algorithms.

Limitations and Future Work

The theoretical proofs rely heavily on the covariates $X$ being Gaussian to utilize Stein’s identities. Extending this framework to broader distributions (like sub-Gaussian) remains an open challenge. Additionally, while the SQ model covers a vast array of algorithms (including gradient descent and most convex optimization), it does not encompass every possible computational approach, such as certain parity-based algorithms. Finally, the current framework assumes some prior knowledge of the transformation applied to the response; future work could explore "blind" settings where the non-linearity is entirely unknown.

Summary updated

Abstract

We study the statistical-computational tradeoffs in a high dimensional single index model $Y=f(X^\top\beta^*) +\epsilon$, where $f$ is unknown, $X$ is a Gaussian vector and $\beta^*$ is $s$-sparse with unit norm. When $\cov(Y,X^\top\beta^*)\neq 0$, \cite{plan2016generalized} shows that the direction and support of $\beta^*$ can be recovered using a generalized version of Lasso. In this paper, we investigate the case when this critical assumption fails to hold, where the problem becomes considerably harder. Using the statistical query model to characterize the computational cost of an algorithm, we show that when $\cov(Y,X^\top\beta^*)=0$ and $\cov(Y,(X^\top\beta^*)^2)>0$, no computationally tractable algorithms can achieve the information-theoretic limit of the minimax risk. This implies that one must pay an extra computational cost for the nonlinearity involved in the model.
BibTeX
@inproceedings{wang2019statistical,
  author = {Lingxiao Wang and Zhuoran Yang and Zhaoran Wang},
  title = {{Statistical-Computational Tradeoff in Single Index Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=PVsrLF19BM},
}
Figure