Les problèmes d'optimisation impliquant un terme de régularisation sous forme de pseudo-norme L0 apparaissent dans de nombreux domaines tels que l'apprentissage automatique, le traitement d'images ou de signaux et la recherche opérationnelle. Malgré leur grande applicabilité, ils sont difficiles à résoudre en raison de leur nature combinatoire et non convexe. Pour cette raison, les premières approches se sont largement appuyées sur des relaxations convexes ou continues, plus faciles à traiter sur le plan informatique, mais qui s'écartent souvent de la structure du problème initial et peuvent échouer à en préserver les solutions exactes.
Une approche consiste alors à développer des formulations alternatives permettant de mieux préserver la structure des problèmes régularisés par L0 tout en proposant des modèles plus accessibles sur le plan computationnel. Dans ce travail, nous nous concentrons sur la construction de relaxations continues exactes pour les problèmes d'optimisation régularisés par L0 impliquant des termes généraux d'attache aux données. Ces relaxations sont obtenues en remplaçant la pseudo-norme L0 par des pénalités continues, ce qui conduit à des problèmes qui restent non convexes mais sont exacts. Plus précisément, une relaxation continue est qualifiée d'exacte si elle préserve les minimiseurs globaux du problème initial, réduit la présence de nombreux minimiseurs locaux de la formulation initiale, et ne produit aucun nouveau minimiseur qui ne soit pas un minimiseur du problème d'origine. Cette propriété garantit que le problème relaxé préserve les minimisateurs globaux du problème initial tout en simplifiant le paysage d’optimisation en réduisant certains minimisateurs locaux.
Sur la base de ce cadre, nous introduisons une classe de relaxations construites sur les divergences de Bregman, appelées L0 Bregman relaxations (Brex). Cette construction étend les résultats précédents au-delà du cadre classique des moindres carrés et permet d’incorporer une large classe de termes d’attache aux données, incluant des modèles non quadratiques tels que la divergence de Kullback--Leibler et la perte logistique.
En nous appuyant sur ces développements théoriques, nous proposons de plus L0PathBrex, une méthode pour estimer le chemin de régularisation L0. L'algorithme exploite les propriétés structurelles des relaxations exactes ; en particulier, il bénéficie de propriétés avantageuses qui facilitent l'utilisation de stratégies de démarrage à chaud (warm-start) afin de construire progressivement des candidats de solutions le long du chemin.
Enfin, des expériences numériques sur la reconstruction parcimonieuse, la classification et les problèmes inverses de Poisson illustrent l'efficacité du cadre proposé et mettent en évidence les avantages des relaxations continues exactes tant sur le plan théorique que pratique. |
Optimization problems involving an L0 pseudo-norm as regularization term appear in many areas, such as machine learning, image/signal processing, and operations research. Despite their wide applicability, they are difficult to solve due to their combinatorial and non-convex nature. For this reason, early approaches largely relied on convex or continuous relaxations, which are easier to handle computationally but often deviate from the structure of the original problem and may fail to preserve its true solutions.
One direction of research consists in developing formulations that treat L0-regularized problems while retaining their exact solution structure and improving tractability. In this work, we focus on the construction of exact continuous relaxations for L0-regularized optimization problems involving general data fidelity terms. These relaxations are obtained by replacing the L0 pseudo-norm with continuous penalties, leading to problems that remain non-convex but preserve the exact solutions of the original formulation. Specifically, a continuous relaxation is termed exact if it preserves the global minimizers of the original L0-regularized problem, reduces the number of local minimizers of the original formulation, and does not introduce any additional minimizers that are not minimizers of the original problem.
Based on this framework, we introduce a class of relaxations built upon Bregman divergences, referred to as the L0 Bregman relaxations (Brex). This construction extends previous results beyond the classical least-squares setting and allows the incorporation of a broad class of data fidelity terms, including non-quadratic models such as the Kullback--Leibler divergence and logistic loss.
Building on these theoretical developments, we further propose L0PathBrex, a method for estimating the L0-regularization path. The algorithm exploits structural properties of the exact relaxations; in particular, it enjoys desirable properties that facilitate the use of warm-start strategies to progressively construct candidate solutions along the path.
Finally, numerical experiments on sparse recovery, classification, and Poisson inverse problems illustrate the effectiveness of the proposed framework and highlight the benefits of exact continuous relaxations in both theory and practice. |