De Montbrun, Etienne (2023) Théorie des jeux et apprentissage séquentiel : montée-descente de gradient, optimisation, approximation et certification. École doctorale Mathématiques, Informatique et Télécommunications (Toulouse).

Preview

Text Download (5MB) | Preview

Abstract

Cette thèse se situe dans les domaines de la théorie des jeux et de l'apprentissage séquentiel, en abordant trois problèmes distincts par l'étude de trois algorithmes optimistes différents.Tout d'abord, nous approfondissons l'étude d'OGDA, une variante de l'algorithme de montée-descente de gradient, dans le cadre des jeux bilinéaires sans contraintes. OGDA améliore ses performances grâce à un terme de gradient supplémentaire dans la mise à jour.Notre deuxième domaine de recherche est l'optimisation multi-fidélité pour les fonctions lipschitziennes, où nous nous intéressons plus particulièrement à la notion de certificat.Nous introduisons c.MF-DOO, un algorithme certifié s'appuyant sur la maximisation de bornes supérieures de la fonction à optimiser.Enfin, nous examinons GreedyBox, un algorithme qui minimise les erreurs d'approximation Lp des fonctions monotones grâce à une approche dite ``gourmande''.Notre étude examine les dynamiques, les vitesses de convergence, les limites ainsi que certaines améliorations de ces trois algorithmes, et conduit à de nouvelles perspectives sur les avantages de la certification et de l'optimisme.

This thesis delves into the topics of game theory and online learning, addressing three distinct problems, with the study of three different optimistic algorithms.Firstly, we strengthen the study of OGDA, a variant of the gradient descent ascent algorithm, in the framework of unconstrained bilinear games. It improves its performance thanks to an extra gradient update at each time step.Our second focus is multi-fidelity zeroth-order optimization of Lipschitz functions, where we emphasize on certification.We introduce c.MF-DOO, a certified algorithm built on the maximization of a surrogate function.Finally, we consider GreedyBox, which minimizes Lp approximation errors of monotone functions through a greedy approach.Our study scrutinizes the mechanics, convergence rates, limitations and some improvements of these algorithms, and leads to new insights on the benefit of certification and optimism.