“Online Lipschitz Selection”

Speaker: SÉBASTIEN BUBECK
Microsoft Research, Redmond
Website

Abstract: Since the late 19^th 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. The presentation will be centered around the *convex* aspects of the problem. On the way we will discuss state of the art results on k-server, metrical task systems, and chasing convex bodies.

Based on joint works with Michael B. Cohen, James R. Lee, Yin Tat Lee, Yuanzhi Li, Aleksander Madry, and Mark Sellke.