Geometry Seminar

---

Chasing Convex Functions and Bodies

Speaker: Anupam Gupta, Courant Institute, NYU

Location: Warren Weaver Hall 1314 in person and on Zoom

Date: Tuesday, April 15, 2025, 6 p.m.

Synopsis:

At each timestep \(t\) you are given a convex function \(f_t\) over \(\mathbb{R}^d\), and need to immediately output a point \(x_t\).  Your total cost incurred is \(f_t(x_t)\) plus the distance between \(x_t\) and \(x_{t-1}\), summed over all time. In 1994, Friedman and Linial introduced this question (chasing convex functions) as a very general question in online algorithms. They asked: can we give an algorithm whose cost is only \(f(d)\) times the optimal cost in hindsight? This problem also became known as “smoothed online convex optimization,” and gained interest in the online learning community as well.

The problem was finally resolved in 2019-20, in several works by authors including Argue, Bubeck, Cohen, Klartag, Lee, Li, Sellke, and myself. In this talk I will survey the algorithms behind this resolution, and highlight some techniques and open questions.

Notes:

In person and simultaneously Zoom-broadcast at the usual place; sent via the mailing list.  Contact Boris Aronov to be put on the mailing list and/or get access to the physical location if you are not NYU-affiliated.