- Chasing Convex Bodies
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in February 2020

## 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:**

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