An efficient method for the support vector machine with minimax concave penalty in high dimensions

Abstract Support vector machines (SVMs) are powerful approaches for achieving accurate and well-generalized classification on high-dimensional datasets. However, considering all dimensions will lead to computational difficulties and overfitting. In this study, our focus lies in establishing the numerical theory for solving minimax concave penalty penalized SVMs, with the aim of providing sparse optimization and statistical guarantees. We develop a novel convergence theory proving that the difference-of-convex algorithm (DCA), without any proximal regularization, achieves linear convergence to directional-stationary points. More strikingly, in high-dimensional regimes, the DCA provably achieves convergence to the oracle estimator with high probability after a single iteration. To overcome computational bottlenecks inherent in existing algorithms, we propose a highly efficient second-order information-based algorithm for solving the subproblems of DCA. Numerical experiments substantiate computational efficiency and model accuracy of the proposed approach.