Efficient ADMM Algorithms for approximating Best Subset Selection via Sequential lp Regularisation

Best Subset Selection (BSS) is the gold standard for sparse linear regression, but its cardinality constraint renders it NP-hard and intractable at scale. In this paper, we introduce three novel variations of the Alternating Direction Method of Multipliers (ADMM) for approximating BSS. Instead of solving the BSS problem directly, we approach it through a series of bridge regressions, regularised by the lp penalty with continuation in the order of the quasi-norm. We start at p=1, therefore solving the convex LASSO problem, and gradually decrease the order of the quasi-norm towards zero, therefore closely approximating the l0 penalty. We analyse the computational performance of our proposed solvers and compare them to state-of-the-art benchmarks. Furthermore, we analyse how the number of nonzero entries in the beta vector evolves as we decrease p.