Theory of Computing
-------------------
Title     : Pure Entropic Regularization for Metrical Task Systems
Authors   : Christian Coester and James R. Lee
Volume    : 18
Number    : 23
Pages     : 1-24
URL       : https://theoryofcomputing.org/articles/v018a023

Abstract
--------

We show that on every $n$-point HST metric, there is a randomized
online algorithm for metrical task systems (MTS) that is
$1$-competitive for service costs and $O(\log n)$-competitive for
movement costs. In general, these refined guarantees are optimal up to
the implicit constant. While an $O(\log n)$-competitive algorithm for
MTS on HST metrics was developed by Bubeck et al. (SODA'19), that
approach could only establish an $O((\log n)^2)$-competitive ratio
when the service costs are required to be $O(1)$-competitive. Our
algorithm can be viewed as an instantiation of online mirror descent
with the regularizer derived from a multiscale conditional entropy.

In fact, our algorithm satisfies a set of even more refined
guarantees; we are able to exploit this property to combine it with
known random embedding theorems and obtain, for _any_ $n$-point metric
space, a randomized algorithm that is $1$-competitive for service
costs and $O((\log n)^2)$-competitive for movement costs.


----------------

An extended abstract of this paper appeared in the Proceedings 
of the 32nd Ann. Conference on Learning Theory (COLT 2019).