Chasing Convex Bodies

Speaker

Mark Sellke
Stanford

Host

Quanquan Liu, Sitan Chen, Nikhil Vyas
CSAIL MIT
Abstract: I will explain our recent understanding of the chasing convex bodies problem posed by Friedman and Linial in 1993. In this problem, a player receives a request sequence K_1,...,K_T of convex sets in d dimensional space and moves online into each requested set. The player's movement cost is the length of the resulting path. Chasing convex bodies asks to find an online algorithm with cost competitive against the offline (in hindsight) optimal path. This is both an challenging metrical task system and (equivalent to) a competitive analysis view on online convex optimization.

This problem was open for d>2 until recently but has since been solved twice. The first solution gives a 2^{O(d)} competitive algorithm while the second gives a nearly optimal min(d,sqrt(d*log(T))) competitive algorithm for T requests. The latter result is based on the Steiner point, which is the exact optimal solution to a related geometric problem called Lipschitz selection and dates from 1840. I will briefly outline the first solution and fully explain the second.

Partially based on joint work with S├ębastien Bubeck, Bo'az Klartag, Yin Tat Lee, and Yuanzhi Li.