License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.60
URN: urn:nbn:de:0030-drops-156568
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15656/
Go to the corresponding LIPIcs Volume Portal

Ebrahimnejad, Farzam ; Lee, James R.

Multiscale Entropic Regularization for MTS on General Metric Spaces

pdf-format:
LIPIcs-ITCS-2022-60.pdf (1 MB)

Abstract

We present an O((log n)²)-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).

BibTeX - Entry

@InProceedings{ebrahimnejad_et_al:LIPIcs.ITCS.2022.60,
  author =	{Ebrahimnejad, Farzam and Lee, James R.},
  title =	{{Multiscale Entropic Regularization for MTS on General Metric Spaces}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{60:1--60:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15656},
  URN =		{urn:nbn:de:0030-drops-156568},
  doi =		{10.4230/LIPIcs.ITCS.2022.60},
  annote =	{Keywords: Metrical task systems, online algorithms, metric embeddings, convex optimization}
}

Keywords: Metrical task systems, online algorithms, metric embeddings, convex optimization
Collection: 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Issue Date: 2022
Date of publication: 25.01.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI