Adaptive Algorithms for Optimization Beyond Lipschitz Requirements
Algorithmes adaptatifs pour l'optimisation au-delà des conditions de Lipschitz
Résumé
Several important problems in learning theory and data science involve high-dimensional optimization objectives that transcend the standard Lipschitz regularity conditions. The absence of Lipschitz regularity - smoothness or continuity - poses significant challenges to the convergence analysis of most optimization algorithms and, in many cases, it requires novel analytical and algorithmic tools to be treated efficiently. In this thesis, we aim to partially fill this gap via the design and analysis of universal first-order methods for two general optimization frameworks: (a) online convex optimization (which contains as special cases deterministic and stochastic convex optimization problems); and (b) abstract variational inequalities (which contain as special cases min-max problems and games), both without global Lipschitz continuity/smoothness assumptions. In this "NoLips" setting, we take a geometric approach - Riemannian or Bregman-based - that allows us to handle vector fields and functions whose norm or variation becomes infinite at the boundary of the problem's domain. Using these non-Euclidean surrogates for Lipschitz continuity and smoothness, we propose a range of novel adaptive first-order methods that concurrently achieve order-optimal convergence rates in different problem classes, without any prior knowledge of the specific class or the problem's (relative) smoothness parameters. Our methods are based on a suitable mirror descent or mirror-prox template (for convex minimization and monotone variational inequalities respectively), and they revolve around adaptive step-size policies that exploit the geometry of the gradient data observed at earlier iterations to perform more informative (extra-)gradient steps in later ones. Our results do not always coincide with what one would expect in standard Lipschitz problems, and serve to further highlight the differences between the "Lispschitz" and "NoLips" frameworks.
Plusieurs problèmes importants issus de l'apprentissage statistique et de la science des données impliquent des objectifs d'optimisation à très haute dimension qui vont au delà des hypothèses standard de régularité de Lipschitz. L'absence de régularité de Lipschitz - lissage ou continuité - pose des défis importants à l'analyse de convergence de la plupart des algorithmes existants d'optimisation et, dans de nombreux cas, elle nécessite de nouveaux outils analytiques et algorithmiques pour être traitée efficacement. Dans cette thèse, nous visons à combler partiellement cette lacune par la conception et l'analyse de nouvelles méthodes universelles du premier ordre pour deux cadres d'optimisation généraux : (a) l'optimisation convexe en ligne (qui contient comme cas particuliers des problèmes d'optimisation convexe déterministes et stochastiques) ; et (b) les inégalités variationnelles abstraites (qui contiennent comme cas particuliers des problèmes min-max et des jeux), tous deux sans hypothèses globales de continuité/lissage de Lipschitz. Dans ce cadre "NoLips", nous adoptons une approche géométrique - Riemannienne ou Bregmaniene - qui nous permet de traiter les champs de vecteurs et les fonctions dont la norme ou la variation devient infinie sur le bord du domaine du problème. En utilisant ces substituts non-euclidiens pour la continuité et le lissage de Lipschitz, nous proposons une gamme de nouvelles méthodes adaptatives du premier ordre qui atteignent simultanément des taux de convergence optimaux dans différentes classes de problèmes, sans aucune connaissance préalable de la classe spécifique ou des paramètres de régularité (spécifiques) du problème. Nos méthodes sont basées sur un modèle approprié de descente en miroir ou de prox miroir (pour la minimisation convexe et les inégalités variationnelles monotones respectivement), et elles se basent sur politiques adaptatives de taille de pas qui exploitent la géométrie des données de gradient observées aux itérations précédentes afin d'effectuer des pas de gradient (supplémentaires) plus informatifs aux itérations suivantes. Nos résultats ne coïncident pas toujours avec ce que l'on attendrait dans des problèmes standard de Lipschitz, et servent à souligner davantage les différences entre les cadres "Lispschitz" et "NoLips".
Domaines
Optimisation et contrôle [math.OC]
Origine : Version validée par le jury (STAR)