Description
Date depot: 11 avril 2022
Titre: Online Computation with Machine-Learned Advice
Directeur de thèse:
Spyros ANGELOPOULOS (LIP6)
Directeur de thèse:
Christoph DURR (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Algorithmique, combinatoire
Resumé: A recent, and fast-growing trend in Machine Learning and Theoretical Computer Science has focused on enhancing online algorithms with machine-learned predictions. Here, the online algorithm (i.e., an algorithm that does not know the entire input ahead of time) must leverage some additional information on the input so as to boost its performance. This project proposes several research directions towards the efficient design and analysis of algorithms with predictions. Our main objective is to expand and combine the known approaches so as to better study the power, but also the limitations of this class of algorithms. The end goal is to obtain online algorithms that are proven to be theoretically efficient, but also perform well in practice.
Résumé dans une autre langue: Une tendance récente en Apprentissage Automatique et en Informatique Théorique s'est concentrée sur l'amélioration d'algorithmes en ligne avec des prédictions liées à l'apprentissage automatique. Ici, l'algorithme en ligne (c'est-à-dire un algorithme qui ne connaît pas à l'avance l'intégralité des données) doit tirer parti d'informations supplémentaires sur les données pour accroître ses performances. Ce projet propose plusieurs axes de recherche convergeant vers la conception efficace et l'analyse d'algorithmes avec prédictions. Notre objectif principal est d'étendre et de combiner les approches connues pour mieux étudier tant la puissance que les limites de cette classe d'algorithmes. Le but ultime est de développer des algorithmes en ligne dont non seulement l'efficacité théorique est prouvée, mais aussi dont les performances sont avérées dans la pratique.
Doctorant.e: Melidi Georgii