# Best-first Search Algorithm for Non-convex Sparse Minimization

arXiv: https://arxiv.org/abs/1910.01296 · HTML: https://mlsanity.com/paper/1910.01296/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Oct 2019.

## Built on by (most cited first, 1 of 1)

- [Fast Sparse Classification for Generalized Linear and Additive Models](https://mlsanity.com/paper/2202.11389/) (2022)

## Abstract (arXiv)

Non-convex sparse minimization (NSM), or ℓ0-constrained minimization of convex loss functions, is an important optimization problem that has many machine learning applications. NSM is generally NP-hard, and so to exactly solve NSM is almost impossible in polynomial time. As regards the case of quadratic objective functions, exact algorithms based on quadratic mixed-integer programming (MIP) have been studied, but no existing exact methods can handle more general objective functions including Huber and logistic losses; this is unfortunate since those functions are prevalent in practice. In this paper, we consider NSM with ℓ2-regularized convex objective functions and develop an algorithm by leveraging the efficiency of best-first search (BFS). Our BFS can compute solutions with objective errors at most Delta≥0, where Delta is a controllable hyper-parameter that balances the trade-off between the guarantee of objective errors and computation cost. Experiments demonstrate that our BFS is useful for solving moderate-size NSM instances with non-quadratic objectives and that BFS is also faster than the MIP-based method when applied to quadratic objectives.