Pure entropic regularization for metrical task systems

Journal article

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)²)-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)²)-competitive for movement costs.

Authors: Coester, C; Lee, JR

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Department of Computer Science, University of Chicago
• Journal: Theory of Computing
• Volume: 18
• Pages: 1-24
• Article number: 23
• Publication date: 2022-12-29
• Acceptance date: 2022-09-13
• DOI: 10.4086/toc.2022.v018a023
• ISSN: 1557-2862
• Language: English
• Keywords: decision making under uncertainty; competitive analysis; FFR; mirror descent; metrical task systems; online algorithms