Chasing Convex Bodies Optimally

In the chasing convex bodies problem, an online player receives a request sequence of N convex sets K1, . . . , KN contained in a normed space X of dimension d. The player starts at x0 = 0 ∈ X, and at time n observes the set Kn and then moves to a new point xn ∈ Kn, paying a cost ||xn -xn-1||. The player aims to ensure the total cost exceeds the minimum possible total cost by at most a bounded factor α d independent of N , despite xn being chosen without knowledge of the future sets Kn+1, . . . , KN . The best possible α d is called the competitive ratio. Finiteness of the competitive ratio for convex body chasing was proved for d = 2 in [FL93] and conjectured for all d. [BLLS19] recently resolved this conjecture, proving an exponential 2 O(d) upper bound on the competitive ratio.

We give an improved algorithm achieving competitive ratio d in any normed space, which is exactly tight for ℓ ∞ . In Euclidean space, our algorithm also achieves competitive ratio O( √ d log N ), nearly matching a √ d lower bound when N is subexponential in d. Our approach extends that of [BKL + 20] for nested convex bodies, which is based on the classical Steiner point of a convex body. We define the functional Steiner point of a convex function and apply it to the associated work function.