Description

Cette proposition de thèse porte sur les algorithmes augmentés par l’apprentissage, un domaine émergent à l’intersection de l’informatique théorique, du machine learning et de l’intelligence artificielle. Contrairement aux algorithmes classiques qui reposent sur des scénarios pessimistes, ces nouveaux algorithmes exploitent des prédictions fournies par des oracles d’apprentissage pour améliorer leurs performances.

L’objectif du projet est de développer de nouvelles approches stochastiques pour la modélisation et l’analyse de ces algorithmes. Il met en avant les limites des méthodes actuelles, qui utilisent souvent des prédictions déterministes et sont sensibles aux erreurs. À la place, la thèse propose des modèles de prédiction distributionnelle, où les oracles fournissent des distributions de probabilité plutôt que des valeurs fixes.

Deux outils mathématiques clés seront explorés :

L’analyse basée sur le risque, via la Valeur en Risque Conditionnelle (CVaR), afin d’équilibrer performance et risque.
La théorie du transport optimal, permettant de mesurer l’écart entre la prédiction et la réalité pour garantir des performances robustes.
Ces méthodes seront appliquées à divers problèmes d’optimisation en ligne, comme l’arrêt optimal, le sac à dos, la recherche et l’ordonnancement, avec un fort potentiel d’applications pratiques.

Compétences requises

Connaissances en apprentissage et algorithmique

Bibliographie

[1] Carlo Acerbi, and Dirk Tasche. On the coherence of expected shortfall. Journal of Banking and Finance 26, no. 7 (2002): 1487-1503.
[2] Spyros Angelopoulos, Marcin Bienkowski, Christoph Dürr, Bertrand Simon. Contract scheduling with distributional and multiple advice. Proceedings of IJCAI 2024: 3652-3660.
[3] Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, Marc P. Renault. Online computation with untrusted advice. J. Comput. Syst. Sci. 144: 103545 (2024).
[4] Spyros Angelopoulos and Shahin Kamali. Contract Scheduling with Predictions. J. of Artificial Intelligence Research 77 (2023), pp. 395–426.
[5] Spyros Angelopoulos. Online search with a hint. Information and Computation. 295.Part B (2023), p.105091.
[6] Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press 1998.
[7] Sinho Chewi, Jonathan Niles-Weed, and Philippe Rigollet. Statistical optimal transport. arXiv preprint arXiv:2407.18163 (2024).
[8] Nicolas Christianson, Bo Sun, Steven Low, and Adam Wierman. Risk-sensitive online algorithms. ACM SIGMETRICS Performance Evaluation Review 52, no. 2 (2024): 6-8.
[9] Nicolas Christianson, Junxuan Shen, and Adam Wierman. Optimal robustness-consistency tradeoffs for learning-augmented metrical task systems. In: AISTATS. Vol. 206. Proceedings of Machine Learning Research. PMLR, 2023, pp. 9377–9399.
[10] Jose Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld. Recent developments in prophet inequalities. ACM SIGecom Exchanges 17, no. 1 (2019): 61-70.
[11] Romain Cosson, and Laurent Massoulié. Barely Random Algorithms and Collective Metrical Task Systems. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024
[12] Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, and Nikos Zarifis. Learning online algorithms with distributional advice. In International Conference on Machine Learning (ICML), pp. 2687-2696. PMLR, 2021.
[13] Mohammadreza Daneshvaramoli, Helia Karisani, Adam Lechowicz, Bo Sun, Cameron Musco, and Mohammad Hajiesmaili. Competitive Algorithms for Online Knapsack with Succinct Predictions. arXiv preprint arXiv:2406.18752 (2024).
[14] Ryan Donnelly. Optimal execution: A review. Applied Mathematical Finance 29, no. 3 (2022): 181-212.
[15] Alex Elenter, Spyros Angelopoulos, Christoph Dürr, and Yanni Lefki. Overcoming Brittleness in Pareto-Optimal Learning Augmented Algorithms. The Thirty-eighth Annual Conference on Neural Information Processing Systems (NeurIPS) 2024.
[16] Ran El-Yaniv, Amos Fiat, Richard M. Karp, and Gordon Turpin. 'Optimal search and one-way trading online algorithms.' Algorithmica 30 (2001): 101-139.
[17] Thomas Lavastida, Benjamin Moseley, R. Ravi, and Chenyang Xu. Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing. Proceedings of the European Symposium on Algorithms (ESA) 2021: 59:1-59:17
[18] Russell Lee, Bo Sun, Mohammad Hajiesmaili, and John CS Lui. Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Markets. In Proceedings of the 15th ACM International Conference on Future and Sustainable Energy Systems, pp. 386-407. 2024.
[19] Thodoris Lykouris, and Sergei Vassilvitskii. 'Competitive caching with machine learned advice.' Journal of the ACM (JACM) 68, no. 4 (2021): 1-25.
[20] Nicole Megow and Alexander Lindermayr. Algorithms with Predictions. Online repository: https://algorithms-with-predictions.github.io/
[21] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with Predictions. In: Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, 2020, pp. 646–662.
[22] Sergey Sarykalin, Gaia Serraino, and Stan Uryasev. Value-at-risk vs. conditional value-at-risk in risk management and optimization. In State-of-the-art decision-making tools in the information-intensive age, pp. 270-294. Informs, 2008.
[23] Bo Sun, Russell Lee, Mohammad Hajiesmaili, Adam Wierman, and Danny Tsang. Pareto-optimal learning-augmented algorithms for online conversion problems. Advances in Neural Information Processing Systems 34 (2021): 10339-10350.
[24] Alexander Wei and Fred Zhang. Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms. In: Proceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS) 2020.

Mots clés

Algorithmes avec prédiction, Apprentissage