Chasing Convex Bodies

Speaker: Mark Sellke , Stanford

Date: Wednesday, February 12, 2020

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type: Seminar

Room Description:

Host: Quanquan Liu, Sitan Chen, Nikhil Vyas, CSAIL MIT

Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: Mark Sellke: Chasing Convex Bodies

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.

Research Areas:
Algorithms & Theory

Impact Areas:

See other events that are part of the Algorithms and Complexity Seminar 2019-2020 .

Created by Rebecca Yadegar Email at Wednesday, January 08, 2020 at 7:44 PM.