L1-Regularized Least Squares for Support Recovery of High Dimensional Single Index Models with Gaussian Designs

It is known that for a certain class of single index models (SIMs) Y = f(boldsymbolXp × 1^intercalboldsymbolβ0, varepsilon), support recovery is impossible when boldsymbolX ~ N(0, mathbbIp × p) and a model complexity adjusted sample size is below a critical threshold. Recently, optimal algorithms based on Sliced Inverse Regression (SIR) were suggested. These algorithms work provably under the assumption that the design boldsymbolX comes from an i.i.d. Gaussian distribution. In the present paper we analyze algorithms based on covariance screening and least squares with L1 penalization (i.e. LASSO) and demonstrate that they can also enjoy optimal (up to a scalar) rescaled sample size in terms of support recovery, albeit under slightly different assumptions on f and varepsilon compared to the SIR based algorithms. Furthermore, we show more generally, that LASSO succeeds in recovering the signed support of boldsymbolβ0 if boldsymbolX ~ N(0, boldsymbolSigma), and the covariance boldsymbolSigma satisfies the irrepresentable condition. Our work extends existing results on the support recovery of LASSO for the linear model, to a more general class of SIMs.