Statistical-Computational Tradeoff in Single Index Models

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.