Statistical-computational tradeoffs in high-dimensional single index models

We study the statistical-computational tradeoffs in a high dimensional single index model Y = f(X^>ß^*) + e, where f is unknown, X is a Gaussian vector and ß^* is s-sparse with unit norm. When Cov(Y, X^>ß^*) 6= 0, [43] shows that the direction and support of ß^* 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^>ß^*) = 0 and Cov(Y, (X^>ß^*)²) > 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.