Relax and Follow: L0-Path Computation with L0-Bregman Relaxations

This work introduces L0PathBrex, a novel method for estimating the solution path of L0-regularized problems through the use of L0 Bregman relaxations (B-rex). Recently introduced and analyzed in the literature, these relaxations provide continuous reformulations of the original objective, are applicable to possibly non-quadratic data fidelity terms, and depend on a family of functions designed to preserve the global minimizers while eliminating part of the undesirable local minima. Given any numerical solver for the relaxation, the proposed approach dynamically constructs a collection of local minimizers that are candidates for the L0-solution path. It exploits warm-start strategies and identifies ranges of the regularization parameter for which each minimizer remains valid under the corresponding relaxation. Experiments on sparse least-squares and logistic regression problems demonstrate that L0PathBrex systematically outperforms state-of-the-art baselines across both synthetic and real-world datasets in terms of various evaluation metrics; additionally, the study investigates how the choice of the B-rex affects the quality of the estimated path in the sparse Poisson regression setting.