Chasing Convex Bodies Optimally

In the chasing convex bodies problem, an online player receives a request sequence of N convex sets K1,dots, KN contained in a normed space mathbb Rd. The player starts at x0∈ mathbb Rd, and after observing each Kn picks a new point xn∈ Kn. At each step the player pays a movement cost of ||xn-xn-1||. The player aims to maintain a constant competitive ratio against the minimum cost possible in hindsight, i.e. knowing all requests in advance. The existence of a finite competitive ratio for convex body chasing was first conjectured in 1991 by Friedman and Linial. This conjecture was recently resolved with an exponential 2O(d) upper bound on the competitive ratio. We give an improved algorithm achieving competitive ratio d in any normed space, which is exactly tight for ℓ∞. In Euclidean space, our algorithm also achieves competitive ratio O(√dlog N), nearly matching a √d lower bound when N is subexponential in d. The approach extends our prior work for nested convex bodies, which is based on the classical Steiner point of a convex body. We define the functional Steiner point of a convex function and apply it to the associated work function.