Efficient Regularized Regression with 𝐿0 Penalty for Variable Selection and Network Construction

Variable selections for regression with high-dimensional big data have found many applications in bioinformatics and computational biology. One appealing approach is the 𝐿0 regularized regression which penalizes the number of nonzero features in the model directly. However, it is well known that 𝐿0 optimization is NP-hard and computationally challenging. In this paper, we propose efficient EM (𝐿0EM) and dual 𝐿0EM (D𝐿0EM) algorithms that directly approximate the 𝐿0 optimization problem. While 𝐿0EM is efficient with large sample size, D𝐿0EM is efficient with high-dimensional (𝑛≪𝑚) data. They also provide a natural solution to all 𝐿𝑝 𝑝 ∈ [0, 2] problems, including lasso with 𝑝=1 and elastic net with 𝑝 ∈ [1, 2]. The regularized parameter 𝜆 can be determined through cross validation or AIC and BIC. We demonstrate our methods through simulation and high-dimensional genomic data. The results indicate that 𝐿0 has better performance than lasso, SCAD, and MC+, and 𝐿0 with AIC or BIC has similar performance as computationally intensive cross validation. The proposed algorithms are efficient in identifying the nonzero variables with less bias and constructing biologically important networks with high-dimensional big data.