Chasing Convex Bodies with Linear Competitive Ratio

We study the problem of chasing convex bodies online: given a sequence of convex bodies K t ⊆ R d the algorithm must respond with points x t ∈ K t in an online fashion (i.e., x t is chosen before K t+1 is revealed). The objective is to minimize the sum of distances between successive points in this sequence. Bubeck et al. (STOC 2019) gave a 2 O(d) -competitive algorithm for this problem. We give an algorithm that is O(min(d, √ d log T ))-competitive for any sequence of length T .