Chasing Nested Convex Bodies Nearly Optimally

Abstract

The convex body chasing problem, introduced by Friedman and Linial, is a competitive analysis problem on any normed vector space. In convex body chasing, for each timestep $t\in \mathbb{N}$, a convex body $K_t\subseteq {\mathbb{R}}^d$ is given as a request, and the player picks a point $x_t\in K_t$. The player aims to ensure that the total distance ${\sum }_{t=0}^{T-1}||x_t-x_{t+1}||$ 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 a certain sense it is exactly optimal among memoryless algorithms. For general finite dimensional normed spaces, we combine the Steiner point and our recent previous algorithm to obtain a new algorithm which is nearly optimal for all ${\ell }_d^p$ spaces with $p\ge 1$, closing a polynomial gap.