Best-first Search Algorithm for Non-convex Sparse Minimization

Abstract

Non-convex sparse minimization (NSM), or ${\ell }_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 ${\ell }_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 \ge 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.

References in corpus (16)

• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Anytime Heuristic Search
• A first-order primal-dual algorithm with linesearch
• Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization
• A* Orthogonal Matching Pursuit: Best-First Search for Compressed Sensing Signal Recovery
• On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
• Dual Iterative Hard Thresholding: From Non-convex Sparse Minimization to Non-smooth Concave Maximization