Volume 18 (2022) Article 23 pp. 1-24
Pure Entropic Regularization for Metrical Task Systems
Revised: October 8, 2020
Published: December 29, 2022
[PDF (363K)] [PS (1600K)] [Source ZIP]
Keywords: online algorithms, competitive analysis, mirror descent, metrical task systems, decision making under uncertainty
ACM Classification: F.2.0
AMS Classification: 68W27

Abstract: [Plain Text Version]

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).