Statistical-ComputationalTradeoffs inHigh-DimensionalSingleIndex Models

We study the statistical-computational tradeoffs in a high dimensional single index modelY = f(X>β)+, where f is unknown,X is a Gaussian vector and β is s-sparse with unit norm. WhenCov(Y,X>β) 6= 0, [43] shows that the direction and support ofβ can be recovered using a generalized version of Lasso.