Algorithmes exploratoires pour la frugalité par la parcimonie
Date(s) : 31/03/2025 iCal
13h30 - 18h00
- Mme Laure BLANC-FÉRAUD, CNRS, Rapporteure
- M. Gilles GASSO, INSA Rouen Normandie, Rapporteur
- Mme Marianne CLAUSEL, Université de Lorraine , Examinatrice
- M. Rémi GRIBONVAL, Inria, Examinateur
- M. Hachem KADRI, Aix-Marseille Université, Examinateur
- M. Vincent FRÉOUR, Yamaha Music Europe, Invité
- M. François MALGOUYRES, Université de Toulouse, Invité
- M. Valentin EMIYA, Aix Marseille Université, Directeur de thèse
- Mme Caroline CHAUX, CNRS, Co-directrice de thèse
Résumé:
La parcimonie, qui se caractérise par un faible nombre de composantes non nulles, est une propriété essentielle dans des domaines tels que le traitement du signal, l’apprentissage automatique, les statistiques et la compression de données. En effet, elle est souvent utilisée pour réduire la complexité des modèles, améliorer la généralisation et faciliter l’interprétation des résultats. Cependant, elle est généralement difficile à obtenir en pratique, car il est complexe de déterminer quelles composantes doivent être nulles. Cela est dû à la non-convexité et non-différentiabilité des problèmes de parcimonie en norme L0, ce qui rend difficile la recherche de solutions exactes.
Pour contourner cette difficulté, il est courant d’utiliser une relaxation convexe de la norme L0 en norme L1 ou de faire appel à des algorithmes gloutons. La première approche permet d’obtenir un problème avec un unique minimum, permettant ainsi l’utilisation d’algorithmes ayant des garanties de convergence. Tandis que la seconde approche converge rapidement, mais vers des minima locaux.
Dans cette thèse, nous avons cherché à développer une méthode offrant des capacités d’exploration plus étendues que celles des méthodes précédemment évoquées, afin de sortir des minima locaux sans recourir à une relaxation. La méthode proposée repose sur l’utilisation de l’estimateur direct (de l’anglais « Straight-Through Estimator » ou « STE »). Elle présente deux avantages. Tout d’abord, elle permet de rendre différentiables les fonctions faisant appel à la norme L0, sans relaxation, en proposant une approximation du gradient des parties non-différentiables. Cela rend possible l’utilisation de toutes les techniques de descente de gradient. Ensuite, elle permet d’explorer les minima locaux, améliorant ainsi la qualité des objets parcimonieux reconstruits.
Cette nouvelle stratégie d’exploration a été exploitée dans le cadre de la reconstruction de supports parcimonieux dans le cas linéaire (MOHAMED, MALGOUYRES et al. 2024), ainsi que sur une extension de cette approche dans le cadre de la factorisation de matrices en produit de matrices creuses (MOHAMED, EMIYA et al. 2025). Dans le premier contexte, nous avons construit un algorithme surpassant l’état de l’art pour le cas difficile des dictionnaires redondants, avec des garanties théoriques reposant sur la propriété d’isométrie restreinte du dictionnaire. Dans le second contexte, nous avons conçu un algorithme capable d’estimer un modèle plus expressif que celui des matrices de type « Monarch ». Ce modèle peut être utilisé pour remplacer les matrices denses dans les réseaux de neurones, réduisant ainsi les complexités spatiale et temporelle.Cette propriété de parcimonie est finalement exploitée dans une dernière étude effectuée dans le cadre d’une mission de doctorant expert (FRÉOUR, MOHAMED et al. 2023 ; MOHAMED, FRÉOUR et al. 2024) pour la résolution d’un problème industriel (pour Yamaha).
Mots-clés : Estimateur direct, Parcimonie, Reconstruction de supports, Apprentissage automatique, Factorisation de matrices, Trompette
Abstract:
Sparsity, characterized by a small number of non-zero components, is an essential property in fields such as signal processing, machine learning, statistics, and data compression. Indeed, it is often used to reduce model complexity, improve generalization, and facilitate the interpretation of results. However, it is generally difficult to achieve in practice, as determining which components should be null is complex. This is due to the non-convexity and non-differentiability of sparse problems in L0, making it difficult to find exact solutions.
To overcome this challenge, it is common to use a convex relaxation of the L0-norm into the L1-norm or employ greedy algorithms. The first approach leads to a problem with a unique minimum, enabling the use of algorithms with convergence guarantees. In contrast, the second approach converges quickly but to local minima.
In this thesis, we sought to develop a method offering broader exploration capabilities than those of the previously mentioned methods, to escape local minima without relying on relaxation. The proposed method is based on the use of the Straight-Through Estimator (STE). It has two advantages. First, it allows for differentiability of functions involving the L0-norm, without relaxation, by approximating the gradient of the non-differentiable parts. This makes it possible to use all gradient descent techniques. Second, it enables the exploration of local minima, thereby improving the quality of the reconstructed sparse objects.
This new exploration strategy has been applied in the context of reconstructing sparse supports in the linear case (MOHAMED, MALGOUYRES et al. 2024) as well as an extension of this approach in the context of matrix factorization as a product of sparse matrices (MOHAMED, EMIYA et al. 2025). In the first context, we developed an algorithm surpassing the state-of-the-art for the challenging case of redundant dictionaries, with theoretical guarantees based on the restricted isometry property (RIP) of the dictionary. In the second context, we designed an algorithm capable of estimating a more expressive model than that of « Monarch » matrices. This model can be used to replace dense matrices in neural networks, thus reducing spatial and temporal complexities. Finally, sparsity is exploited in a final study carried out within the framework of a french expert doctoral mission (FRÉOUR, MOHAMED et al. 2023 ; MOHAMED, FRÉOUR et al. 2024) to solve an industrial problem (for Yamaha).
Keywords: straight-through estimator, sparsity, support reconstruction, machine learning, matrix factorization, trumpet
Emplacement
Saint-Charles - FRUMAM (2ème étage)
Catégories
