Chasing Convex Bodies Optimally
Mark Sellke · Society for Industrial and Applied Mathematics eBooks · 2019
In the chasing convex bodies problem, an online player receives a request sequence of N convex sets K1, …, Kn contained in a normed space ℝd. The player starts at x0 ϵ ℝd, 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 in [FL93]. This conjecture was recently resolved in [BLLS19] which proved an exponential 2O(d) upper bound on the competitive ratio. In this paper, we drastically improve the exponential upper bound. We give an algorithm achieving competitive ratio d for arbitrary normed spaces, which is exactly tight for ℓ∞ In Euclidean space, our algorithm achieves nearly optimal competitive ratio , compared to a lower bound of . Our approach extends the recent work [BKL +20] which chases nested convex bodies using the classical Steiner point of a convex body. We define the functional Steiner point of a convex function and apply it to the work function to obtain our algorithm.