La soutenance de thèse de Tareq Si Salem a eu lieu le 17 octobre 2022 à 15h, à l’amphitheatre Morgenstern, Bâtiment Kahn du centre Inria de Sophia Antipolis.
Titre: « Apprentissage Séquentiel pour l’Allocation de Ressources dans les Réseaux »
Composition du jury
Directeur de thèse :
- Giovanni Neglia, Directeur de Recherche, Inria, France
Rapporteurs :
- Douglas Leith, Professeur, Trinity College Dublin, Irlande
- Leandros Tassiulas, Professeur, Université Yale, États-Unis
Examinateurs :
- Edmund Yeh, Professeur, Université Northeastern, États-Unis
- György Dán, Professeur, École Royale Polytechnique, Suède
- Walid Dabbous, Directeur de Recherche, Inria, France
Résumé :
L’allocation de ressources dans les réseaux est un problème complexe et fondamental en informatique. Il s’agit d’un processus dans lequel les composants d’un système de réseau visent à fournir un service plus rapide aux demandes ou à réduire la charge de calcul ou de communication sur le système. Les principaux facteurs qui contribuent à la complexité de ce problème sont que les demandes arrivent au système de manière imprévisible et séquentielle et peuvent entrer en concurrence pour les différentes ressources du réseau. L’ubiquité des problèmes d’allocation de ressources dans les réseaux a motivé des recherches approfondies pour concevoir de nouveaux algorithmes avec des garanties prouvables. Cette thèse étudie plusieurs instances du problème d’allocation de ressources dans les réseaux et propose des algorithmes adaptatifs avec de fortes garanties de performances s’appuyant sur le cadre d’apprentissage séquentiel.
Premièrement, nous étudions le problème de mise en cache séquentiel, dans lequel les demandes de fichiers peuvent être servies par un cache local pour éviter les coûts de récupération à partir d’un serveur distant. Nous étudions des algorithmes avec des garanties de performance basés sur des stratégies de descente miroir (DM). Nous montrons que la stratégie DM optimale dépend de la diversité présente dans un lot de demandes. Nous prouvons également que, lorsque le cache doit stocker le fichier entier, plutôt qu’une fraction, les stratégies DM peuvent être couplées à un schéma d’arrondi aléatoire qui préserve garanties de performance. Nous présentons de plus une extension aux réseaux de caches, et nous proposons un algorithme adaptatif distribué.
Deuxièmement, nous étudions les caches de similarité qui peuvent répondre à une demande d’un objet avec des objets similaires stockés localement. Nous proposons un nouvel algorithme de mise en cache de similarité séquentiel qui utilise la descente de gradient pour naviguer dans l’espace de représentation continue des objets et trouver les objets appropriés à stocker dans le cache. Nous montrons que l’algorithme proposé réduit les coûts de service encourus par le système pour les systèmes de diffusion vidéo à 360° et les systèmes de recommandation. Par la suite, nous montrons que le problème de mise en cache de similarité peut être formulé dans le cadre d’apprentissage séquentiel en utilisant un algorithme MD associée à un arrondi aléatoire.
Troisièmement, nous présentons les réseaux de distribution d’inférence (RDI) émergents, des réseaux de nœuds informatiques qui se coordonnent pour satisfaire les demandes d’inférence d’apprentissage automatique (AA) en obtenant le meilleur compromis entre latence et précision. Nous proposons un algorithme adaptatif distribué pour l’allocation de modèles d’AA dans un RDI : chaque nœud met à jour dynamiquement son ensemble local de modèles d’inférence en fonction des demandes observées au cours du passé récent et d’un échange d’informations limité avec ses nœuds voisins.
Finalement, nous étudions l’équité du problème d’allocation des ressources réseau sous le critère d’α-fairness. Nous reconnaissons deux objectifs d’équité différents qui surgissent naturellement dans ce problème: l’objectif d’équité de tranche bien compris qui vise à assurer l’équité à chaque tranche de temps, et l’objectif d’équité d’horizon moins exploré qui vise à assurer l’équité entre les utilités accumulées sur un horizon temporel. Nous étudions l’équité de l’horizon avec le regret comme métrique de performance et montrons que la disparition du regret ne peut être atteinte en présence d’un adversaire sans restriction. Nous proposons des restrictions sur les capacités de l’adversaire correspondant à des scénarios réalistes et un algorithme adaptatif qui garantit en effet la disparition du regret sous ces restrictions.
