Newton-Raphson Meets Sparsity: Sparse Learning Via a Novel Penalty and a Fast Solver.

Abstract

In machine learning and statistics, the penalized regression methods are the main tools for variable selection (or feature selection) in high-dimensional sparse data analysis. Due to the nonsmoothness of the associated thresholding operators of commonly used penalties such as the least absolute shrinkage and selection operator (LASSO), the smoothly clipped absolute deviation (SCAD), and the minimax concave penalty (MCP), the classical Newton-Raphson algorithm cannot be used. In this article, we propose a cubic Hermite interpolation penalty (CHIP) with a smoothing thresholding operator. Theoretically, we establish the nonasymptotic estimation error bounds for the global minimizer of the CHIP penalized high-dimensional linear regression. Moreover, we show that the estimated support coincides with the target support with a high probability. We derive the Karush-Kuhn-Tucker (KKT) condition for the CHIP penalized estimator and then develop a support detection-based Newton-Raphson (SDNR) algorithm to solve it. Simulation studies demonstrate that the proposed method performs well in a wide range of finite sample situations. We also illustrate the application of our method with a real data example.