Florian Frommelt: A neutral comparison of algorithms to minimize L0 penalties for high-dimensional variable selection

Variable selection methods based on L₀ penalties have excellent theoretical properties to select sparse models in a high-dimensional setting. There exist modifications of BIC which either control the family wise error rate (mBIC) or the false discovery rate (mBIC2) in terms of which regressors are selected to enter a model. However, the minimization of L₀ penalties comprises a mixed integer problem which is known to be NP hard and therefore becomes computationally challenging with increasing numbers of regressor variables. This is one reason why alternatives like the LASSO have become so popular, which involve convex optimization problems which are easier to solve. The last few years have seen some real progress in developing new algorithms to minimize  L₀ penalties. We will compare the performance of these algorithms in terms of minimizing L₀ based selection criteria.
Simulation studies covering a wide range of scenarios which are inspired by genetic association studies are used to compare the values of selection criteria obtained with different algorithms. Additionally some statistical characteristics of the selected models and the runtime of algorithms are compared.