Wednesday May 11th 2022 — Sébastien Bubeck from Microsoft Research

The next Foundations of Data Science virtual talk of this year will take place on Wednesday, March 11th at 1:00 PM Pacific Time (16:00 Eastern Time, 22:00 Central European Time, 20:00 UTC). Sébastien Bubeck from Microsoft Research will speak about “Set Chasing, with an application to online shortest path.

Please register here to join the virtual 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).

 The series is supported by the NSF HDR TRIPODS Grant 1934846.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Create your website with
Get started
%d bloggers like this: