Imprimer |
Some contributions on safe regions and safe screening in convex optimization (Quelques contributions dans la conception de “régions sûres” et “tests d’élagages sûrs” en optimisation convexe) Tran, Thu le - (2023-12-14) / Université de Rennes - Some contributions on safe regions and safe screening in convex optimization
| |||
Langue : Anglais Directeur(s) de thèse: Herzet, Cédric; Fercoq, Vincent Discipline : Mathématiques et leurs interactions Laboratoire : IRMAR Ecole Doctorale : MATISSE Classification : Mathématiques Mots-clés : Optimisation convexe
| |||
Résumé : L’optimisation convexe est fréquente en apprentissage automatique, statistiques, signal et image. La résolution de problèmes d'optimisation en grande dimension reste difficile en raison de contraintes calculatoires et de stockage. La dernière décennie, les méthodes de ''safe screening'' sont devenues un outil puissant pour réduire la dimension de ces problèmes en se basant sur la connaissance d'une ''safe region'' contenant la solution optimale duale. La première contribution de cette thèse est un cadre mathématique pour créer de nouvelles ''safe region'' tout en démontrant leur supériorité par rapport à l'état de l'art. Notre cadre offre également une manière élégante d’unifier les ''safe regions'' existantes. Cette contribution établit en particulier une base théorique pour les futures avancées dans l’étude des ''safe region''. La seconde contribution est une extension de la méthodologie de ''safe screening'' à des problèmes en dimension infinie. Nous montrons notamment que l’intégration de cette méthode dans un algorithme de l'état de l'art permet de réduire significativement sa complexité numérique tout en préservant sa propriété de convergence. Cette contribution met en évidence le potentiel du ''safe screening'' pour résoudre efficacement les défis calculatoires dans des contextes de dimension infinie. Abstract : Convex optimization is common in machine learning, statistics, signal, and image processing. Solving high-dimensional optimization problems remains challenging due to computational and storage constraints. In the last decade, the ''safe screening'' methods have become a powerful tool to reduce the dimension of these problems based on the knowledge of a ''safe region'' containing the dual optimal solution. The first contribution of this thesis is a mathematical framework for creating new safe regions while demonstrating their superiority over the state-of-the-art. Our framework also provides an elegant way to unify existing safe regions. This contribution establishes a theoretical foundation for future advances in the study of safe regions. The second contribution is an extension of the safe screening methodology to problems in infinite dimensions. We show, in particular, that integrating this method into a state-of-the-art algorithm can significantly reduce its numerical complexity while preserving its convergence property. This contribution highlights the potential of safe screening to effectively address computational challenges in infinite-dimensional contexts. |