Pure entropic regularization for metrical task systems
share
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( n)-competitive for movement costs. In general, these refined guarantees are optimal up to the implicit constant. While an O( n)-competitive algorithm for MTS on HST metrics was developed by Bubeck et al., that approach could only establish an O(( 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(( n)^2)-competitive for movement costs.
READ FULL TEXT