Adaptive Algorithms for Optimization Beyond Lipschitz Requirements

Algorithmes adaptatifs pour l'optimisation au-delà des conditions de Lipschitz 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".