Document Open Access Logo

Multiscale Entropic Regularization for MTS on General Metric Spaces

Authors Farzam Ebrahimnejad, James R. Lee

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.60.pdf
  • Filesize: 1.03 MB
  • 21 pages

Document Identifiers

Author Details

Farzam Ebrahimnejad
  • University of Washington, Seattle, WA, USA
James R. Lee
  • University of Washington, Seattle, WA, USA

Funding

This research was partially supported by NSF CCF-2007079 and a Simons Investigator Award.

Cite As Get BibTex

Farzam Ebrahimnejad and James R. Lee. Multiscale Entropic Regularization for MTS on General Metric Spaces. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 60:1-60:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITCS.2022.60

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

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
  • Theory of computation → Mathematical optimization
  • Theory of computation → Random projections and metric embeddings
Keywords
  • Metrical task systems
  • online algorithms
  • metric embeddings
  • convex optimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Jacob Abernethy, Peter Bartlett, Niv Buchbinder, and Isabelle Stanton. A regularization approach to metrical task systems. In Algorithmic Learning Theory, ALT 2010. Springer, 2010. Google Scholar
  2. Yair Bartal. Probabilistic approximations of metric spaces and its algorithmic applications. In 37th Annual Symposium on Foundations of Computer Science, FOCS '96, Burlington, Vermont, USA, 14-16 October, 1996, pages 184-193, 1996. URL: https://doi.org/10.1109/SFCS.1996.548477.
  3. Yair Bartal, Avrim Blum, Carl Burch, and Andrew Tomkins. A polylog(n)-competitive algorithm for metrical task systems. In Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, STOC '97, pages 711-719, New York, NY, USA, 1997. ACM. URL: https://doi.org/10.1145/258533.258667.
  4. Yair Bartal, Béla Bollobás, and Manor Mendel. Ramsey-type theorems for metric spaces with applications to online problems. J. Comput. System Sci., 72(5):890-921, 2006. URL: https://doi.org/10.1016/j.jcss.2005.05.008.
  5. Yair Bartal, Nathan Linial, Manor Mendel, and Assaf Naor. On metric Ramsey-type phenomena. Ann. of Math. (2), 162(2):643-709, 2005. URL: https://doi.org/10.4007/annals.2005.162.643.
  6. Avrim Blum, Howard Karloff, Yuval Rabani, and Michael Saks. A decomposition theorem for task systems and bounds for randomized server problems. SIAM J. Comput., 30(5):1624-1661, 2000. URL: https://doi-org.offcampus.lib.washington.edu/10.1137/S0097539799351882.
  7. Allan Borodin, Nathan Linial, and Michael E. Saks. An optimal on-line algorithm for metrical task system. J. ACM, 39(4):745-763, October 1992. URL: https://doi.org/10.1145/146585.146588.
  8. Sébastien Bubeck, Michael B. Cohen, James R. Lee, and Yin Tat Lee. Metrical task systems on trees via mirror descent and unfair gluing. SIAM J. Comput., 50(3):909-923, 2021. URL: https://doi.org/10.1137/19M1237879.
  9. Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and Aleksander Madry. k-server via multiscale entropic regularization. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 3-16, 2018. URL: https://doi.org/10.1145/3188745.3188798.
  10. Niv Buchbinder, Shahar Chen, and Joseph (Seffi) Naor. Competitive analysis via regularization. In Proceedings of the Twenty-fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '14, pages 436-444, Philadelphia, PA, USA, 2014. Society for Industrial and Applied Mathematics. Google Scholar
  11. Gruia Calinescu, Howard Karloff, and Yuval Rabani. Approximation algorithms for the 0-extension problem. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 8-16, 2001. Google Scholar
  12. Christian Coester and James R. Lee. Pure entropic regularization for metrical task systems. In Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, pages 835-848, 2019. Google Scholar
  13. Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci., 69(3):485-497, 2004. Google Scholar
  14. Amos Fiat and Manor Mendel. Better algorithms for unfair metrical task systems and applications. SIAM Journal on Computing, 32(6):1403-1422, 2003. URL: https://doi.org/10.1137/S0097539700376159.
  15. Steve Seiden. Unfair problems and randomized algorithms for metrical task systems. Inf. Comput., 148(2):219-240, February 1999. URL: https://doi.org/10.1006/inco.1998.2744.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact