Exact continuous relaxations of $$\ell _0$$ ℓ 0 -regularized criteria with non-quadratic data terms

Mhamed Essafri (), Luca Calatroni () and Emmanuel Soubies ()
Additional contact information
Mhamed Essafri: IRIT, Université de Toulouse, CNRS
Luca Calatroni: Università degli studi di Genova & MMS, Istituto Italiano di Tecnologia, MaLGa Center, DIBRIS
Emmanuel Soubies: IRIT, Université de Toulouse, CNRS

Journal of Global Optimization, 2025, vol. 93, issue 3, No 2, 699 pages

Abstract: Abstract We consider the minimization of $$\ell _0$$ ℓ 0 -regularized criteria involving non-quadratic data terms such as the Kullback-Leibler divergence and the logistic regression, possibly combined with an $$\ell _2$$ ℓ 2 regularization. We first prove the existence of global minimizers for such problems and characterize their local minimizers. Then, we propose a new class of continuous relaxations of the $$\ell _0$$ ℓ 0 pseudo-norm, termed as $$\ell _0$$ ℓ 0 Bregman Relaxations (B-rex). They are defined in terms of suitable Bregman distances and lead to exact continuous relaxations of the original $$\ell _0$$ ℓ 0 -regularized problem in the sense that they do not alter its set of global minimizers and reduce its non-convexity by eliminating certain local minimizers. Both features make such relaxed problems more amenable to be solved by standard non-convex optimization algorithms. In this spirit, we consider the proximal gradient algorithm and provide explicit computation of proximal points for the B-rex penalty in several cases. Finally, we report a set of numerical results illustrating the geometrical behavior of the proposed B-rex penalty for different choices of the underlying Bregman distance, its relation with convex envelopes, as well as its exact relaxation properties in 1D/2D and higher dimensions.

Keywords: $$\ell _0$$ ℓ 0 regularization; Non-convex/non-smooth optimization; Bregman distances; Proximal gradient algorithm; Exact relaxations; Convex envelopes (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-025-01527-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:93:y:2025:i:3:d:10.1007_s10898-025-01527-z

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-025-01527-z

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().