We consider a regularized version of the canonical best subset estimator, which is given by the following optimization problem
minimize 0.5*\| y - X \beta \|_2^2 + \lambda \|\beta\|_{q}^q
subject to \| \beta \|_0 <= K,
where \lambda and K are two regularization parameters, and q is either 1 or 2. We call this the L0-LQ estimator where L0 corresponds to the cardinality constraint and LQ the penalty function that is meant to impart shrinkage. Above, we estimate the regression coefficients (\beta); where \lambda, K and q are provided by the user.
The optimization problem above can be expressed as a Mixed Integer Optimization (MIO) formulation. To obtain good upper bounds, we use low complexity Discrete First Order (DFO) methods. A neighborhood continuation heuristic using warm-starts across the tuning parameters (\lambda, K) is also proposed. The solutions obtained from the above methods serve as warm-starts for our MIO-based framework. For additional details on the algorithm and statistical properties of the L0-LQ estimator, please see our manuscript Subset selection with shrinkage: Sparse linear modeling when the SNR is low (link)
The Discrete First Order (DFO) algorithm written in Python can be used as a standalone algorithm. The MIO formulation is solved with Gurobi's mixed integer programming solver.
To see a demo example on how to use our algorithm, please refer to example.py file located at
python/example/example.py (link)