Learning learning-augmented algorithms. The example of stochastic scheduling

Abstract:
In this talk, I will argue that it is sometimes possible to learn, with techniques originated from bandits, the “hints” on which learning-augmented algorithms rely to improve worst-case performances. We will describe this phenomenon, the combination of online learning with competitive analysis, on the example of stochastic online scheduling. We shall quantify the merits of this approach by computing and comparing non-asymptotic expected competitive ratios (the standard performance measure of algorithms)

Bio:
Vianney Perchet is a professor at the Centre de recherche en économie et statistique (CREST) at the ENSAE. Mainly focusing on the interplay between machine learning and game theory, his themes of research are at the junction of mathematics, computer science and economics. The spectrum of his interest ranges from pure theory  (say, optimal rates of convergence of algorithms) to pure applications (modeling user behavior, optimisation of recommender systems, etc.) He is also a part-time principal researcher in the Criteo AI Lab, in Paris, working on efficient exploration in recommender systems.