Chasing Nested Convex Bodies Nearly Optimally

The convex body chasing problem, introduced by Friedman and Linial [FL93], is a competitive analysis problem on any normed vector space. In convex body chasing, for each timestep t ∈ N, a convex body K t ⊆ R d is given as a request, and the player picks a point x t ∈ K t . The player aims to ensure that the total distance moved

|| is within a bounded ratio of the smallest possible offline solution.

In this work, we consider the nested version of the problem, in which the sequence (K t ) must be decreasing. For Euclidean spaces, we consider a memoryless algorithm which moves to the so-called Steiner point, and show that in an appropriate sense it is exactly optimal among memoryless algorithms. For general finite dimensional normed spaces, we combine the Steiner point and our recent algorithm in [ABC + 18] to obtain a new algorithm which is nearly optimal for all ℓ p d spaces with p ≥ 1, closing a polynomial gap.

• This work was done while M. Sellke and Y. Li were at Microsoft Research.