  Best subset selection is considered the `gold standard' for many sparse
learning problems. A variety of optimization techniques have been proposed to
attack this non-convex and NP-hard problem. In this paper, we investigate the
dual forms of a family of $\ell_0$-regularized problems. An efficient
primal-dual method has been developed based on the primal and dual problem
structures. By leveraging the dual range estimation along with the incremental
strategy, our algorithm potentially reduces redundant computation and improves
the solutions of best subset selection. Theoretical analysis and experiments on
synthetic and real-world datasets validate the efficiency and statistical
properties of the proposed solutions.
