Pure Entropic Regularization for Metrical Task Systems

by Christian Coester and James R. Lee

Theory of Computing, Volume 18(23), pp. 1-24, 2022

Bibliography with links to cited articles

[1]   Jacob Abernethy, Peter Bartlett, Niv Buchbinder, and Isabelle Stanton: A regularization approach to metrical task systems. In Proc. 21st Internat. Conf. Algorithmic Learning Theory (ALT’10), pp. 270–284. Springer, 2010. [doi:10.1007/978-3-642-16108-7_23]

[2]   Jean-Pierre Aubin and Arrigo Cellina: Differential Inclusions: Set-Valued Maps and Viability Theory. Springer, 1984. [doi:10.1007/978-3-642-69512-4]

[3]   Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Joseph Naor: A polylogarithmic-competitive algorithm for the k-server problem. J. ACM, 62(5):40:1–49, 2015. Preliminary version in FOCS’11. [doi:10.1145/2783434, arXiv:1110.1580]

[4]   Nikhil Bansal, Niv Buchbinder, and Joseph Naor: Metrical task systems and the k-server problem on HSTs. In Proc. 37th Internat. Colloq. on Automata, Languages, and Programming (ICALP’10), pp. 287–298. Springer, 2010. [doi:10.1007/978-3-642-14165-2_25]

[5]   Nikhil Bansal, Niv Buchbinder, and Joseph Naor: A primal-dual randomized algorithm for weighted paging. J. ACM, 59(4):19:1–24, 2012. Preliminary version in FOCS’07. [doi:10.1145/2339123.2339126]

[6]   Yair Bartal: Probabilistic approximations of metric spaces and its algorithmic applications. In Proc. 37th FOCS, pp. 184–193. IEEE Comp. Soc., 1996. [doi:10.1109/SFCS.1996.548477]

[7]   Yair Bartal, Avrim Blum, Carl Burch, and Andrew Tomkins: A polylog(n)-competitive algorithm for metrical task systems. In Proc. 29th STOC, pp. 711–719. ACM Press, 1997. [doi:10.1145/258533.258667]

[8]   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. [doi:10.1016/j.jcss.2005.05.008, arXiv:cs/0406028]

[9]   Yair Bartal, Nathan Linial, Manor Mendel, and Assaf Naor: On metric Ramsey-type phenomena. Ann. Math., 162(2):643–709, 2005. Preliminary version in STOC’03. [doi:10.4007/annals.2005.162.643, arXiv:math/0406353]

[10]   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. [doi:10.1137/S0097539799351882]

[11]   Allan Borodin, Nathan Linial, and Michael E. Saks: An optimal on-line algorithm for metrical task system. J. ACM, 39(4):745–763, 1992. [doi:10.1145/146585.146588]

[12]   Sébastien Bubeck and Nicolò Cesa-Bianchi: Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Found. Trends Mach. Learning, 5(1):1–122, 2012. [doi:10.1561/2200000024, arXiv:1204.5721]

[13]   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. Preliminary version in SODA’19. [doi:10.1137/19M1237879, arXiv:1807.04404]

[14]   Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and Aleksander Madry: k-server via multiscale entropic regularization. In Proc. 50th STOC, pp. 3–16. ACM Press, 2018. [doi:10.1145/3188745.3188798, arXiv:1711.01085]

[15]   Niv Buchbinder, Shahar Chen, and Joseph (Seffi) Naor: Competitive analysis via regularization. In Proc. 25th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’14), pp. 436–444. SIAM, 2014. [doi:10.1137/1.9781611973402.32]

[16]   Niv Buchbinder and Joseph Naor: The design of competitive online algorithms via a primal-dual approach. Found. Trends Theor. Comp. Sci., 3(2–3):93–263, 2009. [doi:10.1561/0400000024]

[17]   Christian Coester and James R. Lee: Pure entropic regularization for metrical task systems. In Proc. 32nd Ann. Conf. on Learning Theory (COLT’19), pp. 835–848. MLR Press, 2019. PMLR.

[18]   Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. System Sci., 69(3):485–497, 2004. Preliminary version in STOC’03. [doi:10.1016/j.jcss.2004.04.011]

[19]   Amos Fiat and Manor Mendel: Better algorithms for unfair metrical task systems and applications. SIAM J. Comput., 32(6):1403–1422, 2003. Preliminary version in STOC’00. [doi:10.1137/S0097539700376159, arXiv:cs/0406034]

[20]   Steve Seiden: Unfair problems and randomized algorithms for metrical task systems. Inform. Comput., 148(2):219–240, 1999. [doi:10.1006/inco.1998.2744]