Worst-case analysis of efficient first-order methods
Analyse de pire cas des méthodes du premier ordre efficaces
Résumé
Many modern applications rely on solving optimization problems (e.g., computational biology, mechanics, finance), establishing optimization methods as crucial tools in many scientific fields. Providing guarantees on the (hopefully good) behaviors of these methods is therefore of significant interest. A standard way of analyzing optimization algorithms consists in worst-case reasoning. That is, providing guarantees on the behavior of an algorithm (e.g. its convergence speed), that are independent of the function on which the algorithm is applied and true for every function in a particular class. This thesis aims at providing worst-case analyses of a few efficient first-order optimization methods. We start by the study of Anderson acceleration methods, for which we provide new explicit worst-case bounds guaranteeing precisely when acceleration occurs. We obtained these guarantees by providing upper bounds on a variation of the classical Chebyshev optimization problem on polynomials, that we believe of independent interest. Then, we extend the Performance Estimation Problem (PEP) framework, that was originally designed for principled analyses of fixed-step algorithms, to study first-order methods with adaptive parameters. This is illustrated in particular through the worst-case analyses of the canonical gradient method with Polyak step sizes that use gradient norms and function values information, and of an accelerated version of it. The approach is also presented on other standard adaptive algorithms. Finally, the last contribution of this thesis is to further develop the PEP methodology for analyzing first-order methods relying on inexact proximal computations. Using this framework, we produce algorithms with optimized worst-case guarantees and provide (numerical and analytical) worst-case bounds for some standard algorithms in the literature.
De nombreuses applications modernes reposent sur la résolution de problèmes d’optimisations (par exemple, en biologie numérique, en mécanique, en finance), faisant des méthodes d’optimisation des outils essentiels dans de nombreux domaines scientifiques. Apporter des garanties sur le comportement de ces méthodes constitue donc un axe de recherche important. Une façon classique d’analyser un algorithme d’optimisation consiste à étudier son comportement dans le pire cas. C'est-à-dire, donner des garanties sur son comportement (par exemple sa vitesse de convergence) qui soient indépendantes de la fonction en entrée de l’algorithme et vraies pour toutes les fonctions dans une classe donnée. Cette thèse se concentre sur l’analyse en pire cas de quelques méthodes du premier ordre réputées pour leur efficacité. Nous commençons par étudier les méthodes d’accélération d’Anderson, pour lesquelles nous donnons de nouvelles bornes de pire cas qui permettent de garantir précisément et explicitement quand l’accélération a lieu. Pour obtenir ces garanties, nous fournissons des majorations sur une variation du problème d’optimisation polynomiale de Tchebychev, dont nous pensons qu’elles constituent un résultat indépendant. Ensuite, nous prolongeons l’étude des Problèmes d’Estimation de Performances (PEP), développés à l’origine pour analyser les algorithmes d’optimisation à pas fixes, à l’analyse des méthodes adaptatives. En particulier, nous illustrons ces développements à travers l’étude des comportements en pire cas de la descente de gradient avec pas de Polyak, qui utilise la norme des gradients et les valeurs prises par la fonction objectif, ainsi que d’une nouvelle version accélérée. Nous détaillons aussi cette approche sur d’autres algorithmes adaptatifs standards. Enfin, la dernière contribution de cette thèse est de développer plus avant la méthodologie PEP pour l’analyse des méthodes du premier ordre se basant sur des opérations proximales inexactes. En utilisant cette approche, nous définissons des algorithmes dont les garanties en pire cas ont été optimisées et nous fournissons des analyses de pire cas pour quelques méthodes présentes dans la littérature.
Origine : Version validée par le jury (STAR)