# Multiscale entropic regularization for MTS on general metric spaces

arXiv: https://arxiv.org/abs/2111.10908 · HTML: https://mlsanity.com/paper/2111.10908/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Nov 2021.

## Built on by (most cited first, 1 of 1)

- [Dynamic Data Layout Optimization with Worst-case Guarantees](https://mlsanity.com/paper/2405.04984/) (2024)

## Abstract (arXiv)

We present an O((log n)2)-competitive algorithm for metrical task systems (MTS) on any n-point metric space that is also 1-competitive for service costs. This matches the competitive ratio achieved by Bubeck, Cohen, Lee, and Lee (2019) and the refined competitive ratios obtained by Coester and Lee (2019). Those algorithms work by first randomly embedding the metric space into an ultrametric and then solving MTS there. In contrast, our algorithm is cast as regularized gradient descent where the regularizer is a multiscale metric entropy defined directly on the metric space. This answers an open question of Bubeck (Highlights of Algorithms, 2019).