IC Colloquium: Improving prophet inequalities: going beyond worst-case and the impact of weaker benchmark
By: Vianney Perchet - CREST at ENSAE
Video of the talk
Abstract
Prophet inequalities is a standard stopping time question where a decision maker observes sequentially random variables and decides when to stop, in the hope of maximizing the value of the selected variable. There is an extensive literature on the subject, proving some "optimality" of different procedures in the worst-case scenario. We claim, and prove, that those results can be strikingly improved when considering non-pathological distributions. This is illustrated in two directions: by introducing a parameter that characterizes the complexity of an instance or by looking at some slightly weaker benchmarks that strongly impact the performances of the oracle that knows in advance all the realized values.
Bio
Vianney Perchet is a professor at the Centre de recherche en économie et statistique (CREST) at the ENSAE since october 2019. Mainly focusing on the interplay between machine learning and game theory, his research themes are at the intersection 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 part-time distinguished researcher in the Criteo AI Lab, in Paris, working on efficient exploration in recommender systems.
More information
Video of the talk
Abstract
Prophet inequalities is a standard stopping time question where a decision maker observes sequentially random variables and decides when to stop, in the hope of maximizing the value of the selected variable. There is an extensive literature on the subject, proving some "optimality" of different procedures in the worst-case scenario. We claim, and prove, that those results can be strikingly improved when considering non-pathological distributions. This is illustrated in two directions: by introducing a parameter that characterizes the complexity of an instance or by looking at some slightly weaker benchmarks that strongly impact the performances of the oracle that knows in advance all the realized values.
Bio
Vianney Perchet is a professor at the Centre de recherche en économie et statistique (CREST) at the ENSAE since october 2019. Mainly focusing on the interplay between machine learning and game theory, his research themes are at the intersection 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 part-time distinguished researcher in the Criteo AI Lab, in Paris, working on efficient exploration in recommender systems.
More information
Practical information
- General public
- Free
Contact
- Host: Nicolas Flammarion