Signed Support Recovery for Single Index Models in High-Dimensions

2015/11/07 by Neykov, Matey, Lin, Qian, Liu, Jun S.
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.1511.02270

Abstract

In this paper we study the support recovery problem for single index models Y=f(\boldsymbolX^\intercal \boldsymbolβ,ε), where f is an unknown link function, \boldsymbolX∼ N_p(0,\mathbbI_p) and \boldsymbolβ is an s-sparse unit vector such that \boldsymbolβ_i∈ \±(1)/(√(s)),0\. In particular, we look into the performance of two computationally inexpensive algorithms: (a) the diagonal thresholding sliced inverse regression (DT-SIR) introduced by Lin et al. (2015); and (b) a semi-definite programming (SDP) approach inspired by Amini & Wainwright (2008). When s=O(p^1-δ) for some δ>0, we demonstrate that both procedures can succeed in recovering the support of \boldsymbolβ as long as the rescaled sample size κ=(n)/(slog(p-s)) is larger than a certain critical threshold. On the other hand, when κ is smaller than a critical value, any algorithm fails to recover the support with probability at least (1)/(2) asymptotically. In other words, we demonstrate that both DT-SIR and the SDP approach are optimal (up to a scalar) for recovering the support of \boldsymbolβ in terms of sample size. We provide extensive simulations, as well as a real dataset application to help verify our theoretical observations.

Related

• L1-Regularized Least Squares for Support Recovery of High Dimensional Single Index Models with Gaussian Designs
• Convergence guarantee for the sparse monotone single index model
• Exact recovery in the double sparse model: sufficient and necessary signal conditions
• On the Structural Dimension of Sliced Inverse Regression
• On the optimality of sliced inverse regression in high dimensions