Risk averse optimisation: Models, Algorithms and Applications in Machine Learning

English

Spécialité : Mathématiques Appliquées

30/11/2021 - 14:00 Yassine Laguel (Université Grenoble Alpes) Amphitheater, Maison Jean Kuntzmann

Cette thèse s’inscrit dans le cadre de l’optimisation sous incertitude, qui a une longue tradition en recherche opérationnelle et en optimisation mathématique. Ce domaine trouve aujourd’hui de nouvelles applications en intelligence artificielle et science des données, où la prise en compte du risque est devenu une question cruciale. Dans cette thèse, nous considérons des problèmes d’optimisation, issus d’applications en apprentissage statistique, mettant en jeu des mesures de risque. Nous accordons une attention particulière à la mesure de risque appelée superquantile (également connue sous le nom de "Conditional Value at Risk") et montrons comment, dans divers contextes, elle permet d’obtenir de la robustesse dans la prise de décision.

Dans un premier temps, nous nous intéressons aux mesures de risque convexes admettant une représentation en termes de superquantiles. Nous dérivons des oracles du premier ordre avec une complexité de calcul optimale. Ces oracles approchés font intervenir différentes techniques de lissage pour lesquelles nous proposons une analyse unifiée. Nous proposons aussi une implémentation efficace de ces oracles, couplée à une série de méthodes classiques d’optimisation, dans un logiciel open-source en Python. Nous montrons empiriquement, sur des problèmes de classifications et de régression, que les prédictions obtenues sont robustes aux perturbations des données.

Nous nous penchons ensuite sur les problèmes d’optimisation avec contraintes en probabilités. Nous proposons une reformulation de ces problèmes sous la forme de problèmes bi-niveaux qui font apparaître le superquantile. Nous proposons une pénalisation (semi-)exacte pour cette reformulation, que nous traitons avec une méthode de faisceaux. Nous implémentons notre approche bi-niveau, dans un logiciel open-source, que nous illustrons sur des problèmes non-convexes.

Enfin, nous nous penchons sur l’utilisation du superquantile dans le cadre de l’apprentissage fédéré. Nous considérons le cas d’utilisateurs aux distributions de données hétérogènes et montrons comment le superquantile permet d’obtenir de meilleurs performances sur les utilisateurs les moins privilégiés. Notre algorithme est adapté aux contraintes réelles, en terme de communications et de protection des données. Nous en démontrons la convergence théorique dans le cas convexe en contrôlant simultanément la dérive des modèles locaux induite par la méthode de descente du gradient stochastique locale, ainsi que la redistribution de poids induite par le superquantile. Nous proposons aussi une étude numérique approfondie de notre algorithme en le comparant à un ensemble d’algorithmes constituant l’état de l’art en apprentissage fédéré.

Président:

Nadia Brauner ()

Directeurs:

  • Jérôme Malick

Raporteurs:

  • Claudia Sagastizábal
  • Joseph Salmon

Examinateurs:

  • Alexandre d'Aspremont
  • Mert Gürbüzbalaban
  • Panayotis Mertikopoulos