Pure entropic regularization for metrical task systems

DOI10.4086/TOC.2022.V018A023MaRDI QIDQ6320275arXivFDO

Authors Christian Coester, James R. Lee

Publication date 10 June 2019

Published in arXiv

Full work available at URL https://doi.org/10.4086/TOC.2022.V018A023

Mathematics Subject Classification ID

Theory of computing (68Qxx) Online algorithms; streaming algorithms (68W27)

arXiv classification

cs.DSmath.MG

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(logn)$-competitive for movement costs. In general, these refined guarantees are optimal up to the implicit constant. While an $O(logn)$-competitive algorithm for MTS on HST metrics was developed by Bubeck et al. (SODA 2019), that approach could only establish an $O((logn{)}^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((logn{)}^2)$-competitive for movement costs.

This page was built for publication: Pure entropic regularization for metrical task systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6320275)