Scalable Algorithms for the Sparse Ridge Regression
arXiv:1806.03756
Abstract
Sparse regression and variable selection for large-scale data have been rapidly developed in the past decades. This work focuses on sparse ridge regression, which enforces the sparsity by use of the L0 norm. We first prove that the continuous relaxation of the mixed integer second order conic (MISOC) reformulation using perspective formulation is equivalent to that of the convex integer formulation proposed in recent work. We also show that the convex hull of the constraint system of MISOC formulation is equal to its continuous relaxation. Based upon these two formulations (i.e., the MISOC formulation and convex integer formulation), we analyze two scalable algorithms, the greedy and randomized algorithms, for sparse ridge regression with desirable theoretical properties. The proposed algorithms are proved to yield near-optimal solutions under mild conditions. We further propose to integrate the greedy algorithm with the randomized algorithm, which can greedily search the features from the nonzero subset identified by the continuous relaxation of the MISOC formulation. The merits of the proposed methods are illustrated through numerical examples in comparison with several existing ones.
arXiv comment31 pages
References in corpus (10)
- Nearly unbiased variable selection under minimax concave penalty
- Asymptotic properties of bridge estimators in sparse high-dimensional regression models
- Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
- Robust Wasserstein Profile Inference and Applications to Machine Learning
- Extended Comparisons of Best Subset Selection, Forward Stepwise Selection, and the Lasso
- Computing exact -optimal designs by mixed integer second-order cone programming
- Scalable Greedy Feature Selection via Weak Submodularity
- Regularization vs. Relaxation: A conic optimization perspective of statistical variable selection
- Rank-one Convexification for Sparse Regression
- On the exact recovery of sparse signals via conic relaxations