Chasing Convex Bodies Optimally
share
In the chasing convex bodies problem, an online player receives a request sequence of N convex sets K_1,..., K_N contained in a normed space R^d. The player starts at x_0∈ R^d, and after observing each K_n picks a new point x_n∈ K_n. At each step the player pays a movement cost of ||x_n-x_n-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 2^O(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 O(√(d N)), compared to a lower bound of √(d). Our approach extends another recent work 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.
READ FULL TEXT