Étude de méthodes inertielles en optimisation et leur comportement sous conditions de géométrie

par Hippolyte Labarrière (INSA Toulouse)

mercredi 20 sept. 2023, 14:00 → 17:30 Europe/Paris

Amphithéâtre Sophie Germain (Institut de Mathématiques de Toulouse)

Cette thèse est consacrée à l'optimisation de fonctions convexes composites dans un cadre déterministe. Dans ce contexte, je me suis concentré sur l'analyse de convergence d'algorithmes d'optimisation sous des hypothèses de croissance. 

Lorsque l'on s'intéresse à la minimisation de telles fonctions, les méthodes de premier ordre les plus efficaces sont dites inertielles car elles font apparaître une notion d'élan. Si l'introduction de cette inertie est généralement bénéfique, il est nécessaire de bien paramétrer ce type de méthodes pour obtenir une solution rapidement et éviter des comportements pathologiques. Par exemple, certaines méthodes dites Heavy-Ball nécessitent de connaître la valeur du conditionnement de la fonction à minimiser pour être utilisées. 

La question à laquelle cherche à répondre cette thèse est : quelle méthode appliquer en fonction des hypothèses de géométrie vérifiées par $F$? Comme les méthodes étudiées sont inertielles, on peut reformuler cette problématique de la manière suivante : comment maîtriser l'inertie lorsque $F$ vérifie une hypothèse de croissance plus forte que la convexité? Plusieurs stratégies sont proposées, basées sur des procédés algorithmiques ou sur le parallèle entre schémas numériques et systèmes dynamiques. 

Une première partie est consacrée aux méthodes de restart. Les travaux qui y sont présentés font suite au constat suivant : lorsque la fonction à minimiser vérifie une hypothèse de croissance (forte convexité par exemple), les méthodes les plus rapides doivent être calibrées en fonction du paramètre de croissance (ou de manière équivalente en fonction du conditionnement) qui peut être difficile à estimer. Les stratégies de restart visent à répondre à la question : comment profiter des hypothèses de croissance d'une fonction lorsque le paramètre de croissance n'est pas connu? Je propose deux schémas de restart de FISTA permettant d'obtenir des garanties théoriques de convergence rapide en s'affranchissant de la connaissance de certains paramètres de géométrie. 

Dans un deuxième temps, on étudie un moyen alternatif permettant de maîtriser l'inertie et atténuer les comportements oscillatoires. Cette analyse porte sur un système dynamique introduit par Attouch, Peypouquet et Redont qui est proche de celui proposé par Su, Boyd et Candès et fait intervenir un terme de friction lié à la hessienne de $F$. L'introduction de ce terme de friction permet d'atténuer les oscillations des trajectoires et des schémas numériques de premier ordre peuvent être dérivés de ce système. On se concentre ici sur les propriétés de convergence des trajectoires de ce système lorsque $F$ vérifie des hypothèses de croissance. Dans ce contexte, on montre que l'introduction du terme lié à la hessienne permet d'obtenir des propriétés d'intégrabilité sur le gradient de la fonction $F$ qui sont de plus en plus fortes à mesure que les hypothèses de croissance sont renforcées. Comme les hypothèses considérées sont liées à l'inégalité de Lojasiewicsz, ces propriétés donnent des garanties sur la décroissance de l'erreur. 

La dernière partie est dédiée à l'hypothèse d'unicité du minimiseur dans l'analyse de convergence de méthodes inertielles. Dans la littérature, les résultats de convergence les plus forts pour des systèmes dynamiques et des schémas numériques lorsque $F$ vérifie une condition de croissance s'appuient, sauf exception, sur l'hypothèse que $F$ a un unique minimiseur. Les questions posées dans ce chapitre sont : à quoi est due cette hypothèse? Est-il possible d'obtenir des résultats de convergence rapide en s'en affranchissant? On montre que cette hypothèse est principalement liée aux techniques de preuves et qu'elle n'est pas nécessaire à l'obtention de vitesses rapides. Dans le cadre continu, une hypothèse de géométrie sur $X^{\ast }$ est proposée pour étendre plusieurs résultats connus. On donne enfin des résultats de convergence pour V-FISTA et FISTA sans hypothèse d'unicité du minimiseur.