Mineurs de graphes et apprentissage fédéré : deux thèses récompensées

Mathieu Even - Towards decentralization, asynchrony, privacy and personalization in federated learning

La thèse de Mathieu Even concerne l’apprentissage fédéré, un modèle d’apprentissage qui s’opère à partir de données décentralisées, c’est-à-dire qui ne sont pas réunies sur un seul gros serveur. « Cela arrive lorsqu’il y a une trop grande quantité de données, ou pour des raisons de coût ou de confidentialité, comme avec des données médicales qui ne pourraient être stockées ailleurs que dans un hôpital », explique Mathieu Even, qui a obtenu son doctorat au Département d'informatique de l'école normale supérieure (DI ENS - CNRS/ENS - PSL/Inria).

L’objectif est d’obtenir des algorithmes aussi efficaces que si tout était centralisé, malgré les contraintes. Mathieu Even a pour cela utilisé des graphes de communication, rendus robustes aux échecs. Il s’est aussi concentré sur l’utilisation de données privées, en faisant attention à ce que l’algorithme final ne soit pas révélateur des données sur lesquelles il s’est entraîné. On parle alors de confidentialité différentielle. Cela passe par exemple par l’ajout de bruit dans chaque centre de données confidentielles.

Mathieu Even est à présent en postdoctorat à l’Inria de Montpellier, où il étudie l’inférence causale et l’IA appliquées aux données médicales. Ces travaux sont financés pour moitié par le laboratoire, et par la startup parisienne Theremia spécialisée dans les données médicales. L’objectif est de rendre les essais randomisés plus efficaces. Même si ces recherches ne sont pas directement liées à son doctorat, il y utilise toujours des méthodes d’apprentissage fédéré et la confidentialité différentielle.

Giannos Stamoulis - Logics and algorithms for graph minors

Dans sa thèse « Logics and Algorithms for Graph Minors », Giannos Stamoulis étudie, sous l'angle de la logique, la question de l'efficacité algorithmique pour différents problèmes sur les graphes. Il s’appuie pour cela sur la théorie des mineurs de graphes due à Neil Robertson et Paul Seymour et sur les nombreux travaux qui ont suivi. Un mineur dans un graphe peut être vu comme un graphe motif obtenu à partir du graphe de départ en appliquant une suite d'opérations élémentaires (suppression de sommets ou d'arrêtes, contractions d'arrêtes). Ce doctorat a été préparé au Laboratoire d'informatique, de robotique et de microélectronique de Montpellier (LIRMM - CNRS/Université de Montpellier).

Il s’agit de comprendre quand, pourquoi et comment certains problèmes peuvent être résolus efficacement. « Mes travaux proposent des algorithmes pour résoudre des problèmes qui sont exprimables dans certaines logiques. Ces logiques capturent, par exemple, des problèmes de routage, comme le problème des chemins disjoints, un problème central aussi bien dans la théorie des mineurs de graphes que dans la théorie des graphes en général, » explique Giannos Stamoulis. « Dans cette approche logique, j’ai aussi étudié la résolution efficace de problème de modification de graphes, à savoir si un graphe modifié satisfait une propriété donnée. »  
Les résultats obtenus sont des méta-théorèmes algorithmiques : ces derniers énoncent que tout problème exprimable dans un cadre logique donné peut être algorithmiquement résolu de façon efficace pour tout graphe qui vérifie certaines propriétés structurelles (ici exprimées en termes de mineur exclu).

« Cet accessit est un grand honneur pour moi, s’enthousiasme Giannos Stamoulis. C’est aussi une bonne occasion de partager mes travaux avec un plus large public et d’avoir davantage de retours. » 

Après sa thèse, Giannos Stamoulis est parti pendant un an et demi en postdoctorat à l’université de Varsovie. Il a ensuite réussi le concours de chargé de recherche CNRS et travaille depuis février à l’Institut de recherche en informatique fondamentale (IRIF - CNRS/Université Paris Cité). Il continue d’y étudier les interactions entre logique, algorithmique et théorie des graphes, en s’intéressant cette fois-ci à de nouvelles familles de graphes.