Les thèmes abordés dans cette thèse visent à caractériser les compromis à réaliser entre confidentialité et utilité dans la prise de décision séquentielle dans l'incertain. Le principal cadre adopté pour définir la confidentialité est la protection différentielle, et le principal cadre d'utilité est le problème de bandit stochastique à plusieurs bras. Tout d'abord, nous proposons différentes définitions qui étendent la définition de confidentialité à l'environnement des bandits à plusieurs bras. Ensuite, nous quantifions la difficulté des bandits avec protection différentielle en prouvant des bornes inférieures sur la performance des algorithmes de bandits confidentielles. Ces bornes suggèrent l'existence de deux régimes de difficulté en fonction du budget de confidentialité et des distributions de récompenses. Nous proposons également un plan générique pour concevoir des versions confidentielles quasi-optimales des algorithmes de bandits. Nous instancions ce schéma directeur pour concevoir des versions confidentielles de différents algorithmes de bandits dans différents contextes: bandits à bras finis, linéaires et contextuels avec le regret comme mesure d'utilité, et bandits à bras finis avec la complexité d'échantillonnage comme mesure d'utilité. L'analyse théorique et expérimentale des algorithmes proposés valide aussi l'existence de deux régimes de difficulté en fonction du budget de confidentialité. Dans la deuxième partie de cette thèse, nous passons des défenses de la confidentialité aux attaques. Plus précisément, nous étudions les attaques par inférence d'appartenance où un adversaire cherche à savoir si un point cible a été inclus ou pas dans l'ensemble de données d'entrée d'un algorithme. Nous définissons la fuite d'information sur un point comme l'avantage de l'adversaire optimal essayant de déduire l'appartenance de ce point. Nous quantifions ensuite cette fuite d'information pour la moyenne empirique et d'autres variantes en termes de la distance de Mahalanobis entre le point cible et la distribution génératrice des données. Notre analyse asymptotique repose sur une nouvelle technique de preuve qui combine une expansion de Edgeworth du test de vraisemblance et un théorème central limite de Lindeberg-Feller. Notre analyse montre que le test de vraisemblance pour la moyenne empirique est une attaque par produit scalaire mais corrigé pour la géométrie des données en utilisant l'inverse de la matrice de covariance. Enfin, comme conséquences de notre analyse, nous proposons un nouveau score de covariance et une nouvelle stratégie de sélection des points cible pour l'audit des algorithmes de descente de gradient dans le cadre de l'apprentissage fédéré en white-box.
M. Philippe PREUX Université de Lille Directeur de thèse, M. Debabrota BASU Inria Lille Co-directeur de thèse, Mme Catuscia PALAMIDESSI Inria Saclay et LIX Examinatrice, M. Adam SMITH Boston University Rapporteur, M. Aurélien GARIVIER Ecole Normale Supérieure de Lyon Rapporteur, M. Christos DIMITRAKAKIS University of Neuchâtel Examinateur, M. Aurélien BELLET Inria Montpellier Invité.
Thèse de l'équipe SCOOL soutenue le 26/11/2024
français
English