Title: A New Look of Best Subset Selection for Sparse Ridge Regression from Chance-Constrained Programming
Abstract:
Sparse regression and variable selection for large-scale data have been rapidly developed in the past decades. This work focuses on considering the exact L0 norm to pursue sparse regression. We pave out a theoretical foundation to understand why many existing approaches may not work well for this problem, in particular on largescale datasets. Inspired by reformulating the problem as a chance-constrained program, we derive a novel mixed-integer second-order conic (MISOC) reformulation. Based on the reformulation, we develop new scalable algorithms for sparse ridge regression with desirable theoretical properties. The proposed algorithms are proved to yield near-optimal solutions under mild conditions. The merits of the proposed methods are elaborated through a set of numerical examples in comparison with several existing ones.