Statistical-Computational Tradeoff in Single Index Models
Authors: Lingxiao Wang, Zhuoran Yang, Zhaoran Wang
NeurIPS 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the statistical-computational tradeoffs in a high dimensional single index model Y = f(X β ) + ϵ, where f is unknown, X is a Gaussian vector and β is s-sparse with unit norm. ... Using the statistical query model to characterize the computational cost of an algorithm, we show that when Cov(Y, X β ) = 0 and Cov(Y, (X β )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. |
| Researcher Affiliation | Academia | Northwestern University; lingxiaowang2022@u.northwestern.edu Princeton University; zy6@princeton.edu Northwestern University; zhaoranwang@gmail.com |
| Pseudocode | No | The paper does not include any pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access to source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not describe experiments with datasets, thus no training data information is provided. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments with datasets, thus no validation split information is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe any software implementation details or dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details such as hyperparameters or training settings. |