ED Mathématiques et Informatique
Étude d'algorithmes inertiels type Nesterov pour l'optimisation accélérée non convexe et stochastique
par Julien HERMANT (IMB - Institut de Mathématiques de Bordeaux)
Cette soutenance a lieu à 14h00 - Salle de conférence Université de Bordeaux, 351 cours de la Libération, Bâtiment A33, 33400, Talence
devant le jury composé de
- Jean-François AUJOL - Professeur des universités - Université de Bordeaux - Directeur de these
- Aude RONDEPIERRE - Professeure des universités - INSA Toulouse - CoDirecteur de these
- Aris DANIILIDIS - Professor - TU Wien - Rapporteur
- Adrien TAYLOR - Chargé de recherche - Centre de Recherche INRIA de Paris - Rapporteur
- Antonin CHAMBOLLE - Directeur de recherche - Université Paris Dauphine-PSL - Examinateur
- Jalal FADILI - Professeur des universités - Université Caen Normandie - Examinateur
- Edouard PAUWELS - Professeur des universités - Toulouse School of Economics - Examinateur
Les algorithmes d'optimisation jouent un rôle important dans beaucoup d'applications. L'un des critères essentiels d'un bon algorithme est de converger rapidement vers une solution, ce qui peut s'avérer difficile en raison de la grande échelle des problèmes modernes. Parmi les mécanismes qui permettent de concevoir des algorithmes rapides, un d'importance est l'inertie. Il est largement observé qu'ajouter à la descente de gradient un tel mécanisme d'inertie accélère sa convergence. Si ce phénomène d'accélération est bien compris dans le cadre de la minimisation convexe lisse avec des gradients exacts, de nombreux problèmes sont non convexes et reposent sur des estimateurs stochastiques du gradient. Cette thèse propose une étude théorique de l'accélération induite par l'inertie de Nesterov dans de tels cadres. Notre première contribution est motivée par l'observation que, dans plusieurs cadres naturels non convexes ou stochastiques, de nombreuses analyses existantes n'établissent aucune propriété d'accélération de l'inertie. Nous identifions des conditions géométriques sous lesquelles l'inertie produit effectivement une accélération démontrable. Pour les fonctions non convexes satisfaisant une condition de Polyak–Łojasiewicz, nous montrons que la possibilité d'accélération dépend de l'angle entre la direction de descente et la direction vers les minimiseurs. Dans le cadre convexe stochastique en somme finie, nous montrons que l'accélération est gouvernée par la corrélation moyenne entre les gradients qui composent la somme. Notre seconde contribution s'appuie sur le système Nesterov continuisé récemment proposé. Celui-ci peut être compris comme un algorithme de Nesterov analysable par une approche de Lyapunov stochastique en temps continu. Nous étendons son cadre d'application, et l'utilisons pour améliorer les garanties de convergence existantes pour l'optimisation fortement quasar-convexe, en affinant le taux de convergence et en affaiblissant les hypothèses sur l'ensemble des minimiseurs. On montre aussi que l'inertie de Nesterov, sous une paramétrisation stochastique appropriée, atteint le meilleur taux connu parmi les méthodes de premier ordre pour approximer un point critique de fonctions à gradient et Hessienne Lipschitz, sans recourir aux mécanismes de réinitialisation d'inertie nécessaires dans les travaux existants.