A Generic Branch-and-Bound Algorithm for ℓ 0 \ell_{0} -Penalized Problems with Supplementary Material
Clément Elvira, Théo Guyard, Cédric Herzet · 2025
Read A Generic Branch-and-Bound Algorithm for ℓ 0 \ell_{0} -Penalized Problems with Supplementary Material by Clément Elvira, Théo Guyard, Cédric Herzet (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-03974.txt.
Introduction
Elvira, Guyard, and Herzet present in 2025 a general solver for math problems that pay a cost for each term used. Such sparse problems show up in data fitting and signal work. Past solvers mostly fit square losses and leaned on fixed tricks to relax the hard count cost.
Their branch and bound method allows a wider set of losses and freer choice of the penalty used in relaxations. They prove that all key values the solver needs have closed forms under broad rules. A free Python solver built on the frame lets users plug in their own losses. Tests show top results on classic cases and reach on cases once out of range.
Catalog record
| CREATOR | Clément Elvira, Théo Guyard, Cédric Herzet |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 127 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-03974
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Generic Branch-and-Bound Algorithm for ℓ 0 \ell_{0} -Penalized Problems with Supplementary Material Clément Elvira, Théo Guyard, Cédric Herzet Abstract We present a generic Branch-and-Bound procedure designed to solve ℓ 0 \ell_{0} -penalized optimization problems. Existing approaches primarily focus on quadratic losses and construct relaxations using “Big-M” constraints and/or ℓ 2 \ell_{2} -norm penalties. In contrast, our method accommodates a broader class of loss functions and allows greater flexibility in relaxation design through a general penalty term, encompassing existing techniques as special cases. We establish theoretical results ensuring that all key quantities required for the Branch-and-Bound implementation admit closed-form expressions under the general blanket assumptions considered in our work. Leveraging this framework, we introduce El 0 ps , an open-source Python solver with a plug-and-play workflow that enables user-defined losses and penalties in ℓ 0 \ell_{0} -penalized problems. Through extensive numerical experiments, we demonstrate that El 0 ps achieves state-of-the-art performance on classical instances and extends computational feasibility to previously intractable ones. ∎ MSC 90C25 90C57 90C90 1 Introduction Over the past decades, significant attention has been devoted to solving problems of the form p^{\star}=\min_{\mathbf{x}\in\mathbf{R}^{n}}\ f(\mathbf{A}\mathbf{x})+\sum_{i=1}^{n}g(x_{i}) (1) where f:\mathbf{R}^{m}\to{\mathbf{R}\cup\{+\infty\}} is a data fitting term such that (H0) f is closed, convex, differentiable, lower-bounded and \mathbf{0}\in\interiorOp({\domFuncOp{f}}) , and \begin{array}[b]{@{\,}r@{}r@{}c@{}l@{\,}}{g}\colon&{\mathbf{R}}&{}\to&{{\mathbf{R}\cup\{+\infty\}}}\end{array} is a regularizer imposing some structure on the solutions. In this paper, we concentrate on sparsity-inducing regularizers expressed as g(x)=\lambda\|x\|_{0}+h(x) (2) where \displaystyle\|x\|_{0} \displaystyle=\begin{cases}0&\mbox{if $x=0$}\\ 1&\mbox{if $x\neq 0$}\end{cases} (3) is the so-called “ \ell_{0} -norm” and \begin{array}[b]{@{\,}r@{}r@{}c@{}l@{\,}}{h}\colon&{\mathbf{R}}&{}\to&{{\mathbf{R}\cup\{+\infty\}}}\end{array} is a function with some desirable properties, see hypotheses (H1) - (H5) below. Problem ( 1 ) has been of interest in many fields of applied mathematics in recent years, including machine learning bach2011convex , signal processing soussen2011bernoulli and inverse problems tropp2010computational . Unfortunately, minimization problems involving the \ell_{0} -norm are in general NP-hard chen2014complexity . Over the last decades, various research avenues have consequently focused on developing greedy heuristic procedures blumensath2009iterative ; chen1989orthogonal ; Herzet_eusipco10 ; needell2009cosamp or addressing convex bach2011convex ; tibshirani1996regression ; zou2005regularization and non-convex fan2009network ; soubies2015continuous ; zhang2010nearly approximations of this problem. Recently, the landmark paper bertsimas2016best underscored the possibility of developing tractable procedures to address non-trivial instances of ( 1 ) by using modern tools from discrete optimization. In particular, the authors showed that \ell_{0} -norm problems can be reformulated under the Mixed Integer Programming (MIP) framework and be addressed by off-the-shelf solvers kronqvist2019review . These solvers, however, are designed as general-purpose optimization tools capable of handling a broad range of MIP problems beyond ( 1 ). While they leverage sophisticated Branch-and-Bound (BnB) strategies and cutting-plane methods, their generic nature implies that they do not exploit the specific structure of ( 1 ). As a result, their computational efficiency can be severely hampered when applied to medium- to large-scale instances typically encountered in machine learning and signal processing applications. To overcome these limitations, researchers have developed problem-specific implementations tailored to ( 1 ), aiming for more efficient algorithms capable of handling larger problem instances, see e.g. , atamturk2020safe ; ben2021global ; guyard2022node ; hazimeh2021sparse ; mhenni2020sparse ; samain2022techniques . Rather than addressing the problem in full generality, these approaches leverage particular choices of the data fitting function f and the regularization term h to exploit the problem structure and design specialized BnB algorithmic strategies. More specifically, contributions atamturk2020safe ; ben2021global ; guyard2022node ; mhenni2020sparse ; samain2022techniques concentrated on data fitting terms of the form: f(\mathbf{w})=\tfrac{1}{2}\|\mathbf{y}-\mathbf{w}\|_{2}^{2}\qquad\forall\mathbf{w}\in\mathbf{R}^{m} (4) and considered one of the following regularizers: \displaystyle h(x) \displaystyle=\eta(|x|\leq M) \displaystyle\forall x\in\mathbf{R} (5a) \displaystyle h(x) \displaystyle=\tfrac{\sigma}{2}x^{2} \displaystyle\forall x\in\mathbf{R} (5b) where M , \sigma are positive parameters and \eta denotes the convex indicator, as defined in ( Bauschke2017 , Example 1.25) . A linear combination of ( 5a )-( 5b ) was also considered in hazimeh2021sparse . A central element in the success of these methods lies in the fact that several key quantities needed for the implementation of BnB algorithms admit simple analytical expressions in the particular setups considered in these papers. For example, the authors in ben2021global ; pilanci2015sparse showed that \displaystyle g^{\star\star}(x) \displaystyle=\begin{cases}\frac{\lambda}{M}|x|&\mbox{if $|x|\leq M$}\\ +\infty&\mbox{otherwise}\end{cases} (6a) \displaystyle g^{\star\star}(x) \displaystyle=\begin{cases}\sqrt{2\lambda\sigma}|x|&\mbox{if $x^{2}\leq\tfrac{2\lambda}{\sigma}$}\\ \frac{\sigma}{2}x^{2}+\lambda&\mbox{otherwise}\end{cases} (6b) are convex lower-bounds on g when h is defined by ( 5a ) and ( 5b ), respectively. In these works, the authors also derived closed-form expressions for other key quantities appearing in the efficient optimization of convex relaxations involving g^{\star\star} , namely its convex conjugate, subdifferential and/or proximal operator. 1 1 1 We refer the reader to Section 3 for a detailed discussion on the practical interest of these quantities in the implementation of BnB procedures. While these results have led to efficient solving procedures for specific instances of ( 1 ), they remain limited in scope. In practice, a broader range of data fitting terms f and regularization functions h arise in applications tillmann2024cardinality . To date, no general framework is available to systematically handle these diverse settings, restricting the applicability of existing methods to the few instances mentioned above. Contributions. In this paper, we consider a methodological framework allowing to derive fast numerical solution to instances of problem ( 1 ) involving functions f and h verifying a set of blanket assumptions. In particular, f is supposed to verify (H0) and h to satisfy the following hypotheses: 2 2 2 Assumption (H5) can be relaxed in our derivations, but is retained to enhance the readability of our exposition. (H1) h(x)\geq h(0)=0 and \domFuncOp{h}\cap\mathbf{R}_{+}\setminus\{0\}\neq\emptyset . (H2) h is closed . (H3) h is convex. (H4) h is coercive. (H5) h is even. Our contributions are twofold. First, we provide a systematic strategy to efficiently compute the largest proper, closed and convex function that lower-bound g , as well as its convex conjugate, subdifferential, and proximal operator. In particular, we show that under (H1) - (H2) - (H3) - (H4) - (H5) , all these quantities admit simple closed-form expressions only depending on three key parameters: \displaystyle\tau \displaystyle\triangleq\sup\left\{{{z\in\mathbf{R}_{+}}\mid{h^{\star}(z)\leq\lambda}}\right\} (7) \displaystyle\mu \displaystyle\triangleq\begin{cases}\sup\left\{{{z\in\mathbf{R}_{+}}\mid{z\in\partial h^{\star}(\tau)}}\right\}&\text{ if }\partial h^{\star}(\tau)\neq\emptyset\\ +\infty&\text{ otherwise}\end{cases} (8) \displaystyle\kappa \displaystyle\triangleq\begin{cases}\sup\left\{{{z\in\mathbf{R}_{+}}\mid{z\in\partial h(\mu)}}\right\}&\mbox{if $\mu<+\infty$}\\ +\infty&\mbox{otherwise,}\end{cases} (9) where \partial denotes the subdifferential operator. As outlined in Table 1 , the quantities \tau , \mu , and \kappa admit simple closed-form expressions for many choices of h of practical interest. Interestingly, the proposed characterization unifies and extends previous results in the literature. For instance, we show in Proposition 2 that the tightest proper, closed, and convex lower bound on g – namely, its biconjugate function – can be expressed as: \forall x\in\mathbf{R}:\ g^{\star\star}(x)=\begin{cases}\tau|x|&\text{if}\ |x|\leq\mu\\ h(x)+\lambda&\text{if}\ |x|\geq\mu.\end{cases} (10) In particular, this formulation directly recovers the previously known results ( 6a )-( 6b ) as special cases when h is defined according to ( 5a )-( 5b ). Given the generality of our assumptions on f and h , our framework thus enables the efficient implementation of BnB algorithms for a much wider range of problem instances than was previously feasible. Function \tau \mu \kappa h(x)=\eta(|x|\leq M) \tfrac{\lambda}{M} M +\infty h(x)=\sigma|x| \sigma +\infty +\infty h(x)=\tfrac{\sigma}{p}|x|^{p} with p>1 \sigma(\tfrac{p\lambda}{(p-1)\sigma})^{\tfrac{p-1}{p}} (\tfrac{p\lambda}{(p-1)\sigma})^{\tfrac{1}{p}} \sigma(\tfrac{p\lambda}{(p-1)\sigma})^{\tfrac{p-1}{p}} h(x)=\sigma|x|+\tfrac{\sigma^{\prime}}{2}x^{2} \sigma+\sqrt{2\lambda\sigma^{\prime}} \sqrt{\tfrac{2\lambda}{\sigma^{\prime}}} \sigma+\sqrt{2\lambda\sigma^{\prime}} h(x)=\sigma|x|+\eta(|x|\leq M) \sigma+\tfrac{\lambda}{M} M +\infty h(x)=\tfrac{\sigma}{2}x^{2}+\eta(|x|\leq M) with \lambda<\tfrac{\sigma}{2}M^{2} \sqrt{2\lambda\sigma} \sqrt{\tfrac{2\lambda}{\sigma}} \sqrt{2\lambda\sigma} h(x)=\tfrac{\sigma}{2}x^{2}+\eta(|x|\leq M) with \lambda\geq\tfrac{\sigma}{2}M^{2} \tfrac{\lambda}{M}+\tfrac{\sigma M}{2} M +\infty Table 1: Examples of expression of \tau , \mu , \kappa . The parameters M , \sigma and