Foundations of Data Science - Virtual Talk Series

Wednesday May 11 - 1pm PT (4pm ET, 10pm CEST, 8pm UTC)

Sebastien Bubeck (Microsoft):

Sebastien Bubeck leads the Machine Learning Foundations group at Microsoft Research in Redmond. He likes to work on technical solutions to conceptual problems, like how to make decision under uncertainty, or how to learn from data.

Title: Set Chasing, with an application to online shortest path

Register to receive zoom link for the talk:

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, where sets are streaming to the selector. I will show how Riemannian gradient descent (aka mirror descent) can be used to approach this type of problems. I will illustrate the power of the framework by solving a long-standing problem in online shortest path known as layered graph traversal (introduced by Papadimitriou and Yannakakis in 1989).