Search Mailing List Archives


Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[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