Search Mailing List Archives
[theory-seminar] Theory Lunch 10/10 - Mark Sellke
Neha Gupta
nehgupta at stanford.edu
Wed Oct 9 10:21:05 PDT 2019
Hi everyone,
This Thursday at theory lunch, Mark will tell us about chasing convex bodies problem (title and abstract below). As usual, please join us from noon - 1pm in Gates 463A.
-----------------------------
Title:
Chasing Convex Bodies
Abstract:
I will explain our recent understanding of the chasing convex bodies problem posed by Friedman and Linial in 1991. In this problem, an online player receives a request sequence K_1,...,K_T of convex sets in d dimensional space and moves his position online into each requested set. The player's movement cost is the total length of the resulting path. The question: is there an online algorithm with cost competitive against the offline 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 last year but has recently 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. In the talk, I will briefly outline the first solution and fully explain the second.
Partially based on joint works with Sébastien Bubeck, Bo'az Klartag, Yin Tat Lee, and Yuanzhi Li.
-------------------------------
Thanks,
Neha
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20191009/26f83430/attachment-0003.html>
More information about the theory-seminar
mailing list