Title: Chasing sets, with an application to online shortest path
Abstract: Since the late 19th century, mathematicians have realized the importance and generality of selection problems: given a collection of sets, select an element in each set, possibly in a “nice” way. Of particular importance in computer science is the scenario where the ground set is a metric space, in which case it is natural to ask for *Lipschitz* selection. In this talk I will describe a far-reaching extension of this classical Lipschitz selection problem to an *online* setting. I will show how mirror descent can be used to approach this type of problems, and I will illustrate the power of the framework by solving a long-standing problem in online shortest path known as layered graph traversal.
Bio: Sebastien Bubeck leads the Machine Learning Foundations group at Microsoft Research Redmond. He joined MSR in 2014, after three years as an assistant professor at Princeton University. He received several best paper awards at machine learning conferences for his work on online decision making, convex optimization, and adversarial robustness (NeurIPS 2021, NeurIPS 2018, ALT 2018, COLT 2016, COLT 2009). He also wrote two monographs, “Regret Analysis of Stochastic and Non-Stochastic Multi-Armed Bandit Problems” (2012) and “Convex Optimization: Algorithms and Complexity” (2014).