Abstract: We consider the resolution of learning problems involving $\ell_0$-regularization via BnB algorithms. These methods explore the feasible space of the problem through a decision tree where each node is checked against a ``pruning test''. In standard BnB implementations, evaluating a pruning test requires to solve some convex optimization problem, which may result in computational bottlenecks. In this paper, we present an alternative manner to implement pruning tests for some generic family of $\ell_0$-regularized problems. Our proposed procedure does not require to solve any optimization problem and can be embedded in standard BnB implementations with a negligible computational overhead. We show through numerical simulations that our pruning strategy can improve the solving time of BnB procedures by several orders of magnitude for typical problems encountered in machine learning applications.