Document Open Access Logo

Online Paging with a Vanishing Regret

Authors Yuval Emek, Shay Kutten, Yangguang Shi

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2021.67.pdf
  • Filesize: 0.6 MB
  • 20 pages

Document Identifiers

Author Details

Yuval Emek
  • Faculty of Industrial Engineering and Management, Technion - Israel Institute of Technology, Haifa, Israel
Shay Kutten
  • Faculty of Industrial Engineering and Management, Technion - Israel Institute of Technology, Haifa, Israel
Yangguang Shi
  • Faculty of Industrial Engineering and Management, Technion - Israel Institute of Technology, Haifa, Israel

Funding

  • Emek, Yuval: The work of Yuval Emek was supported in part by an Israeli Science Foundation grant number 1016/17.
  • Kutten, Shay: The work of Shay Kutten was supported in part by a grant from the ministry of science in the program that is joint with JSPS and in part by the BSF.
  • Shi, Yangguang: The work of Yangguang Shi was partially supported at the Technion by a fellowship of the Israel Council for Higher Education.

Cite AsGet BibTex

Yuval Emek, Shay Kutten, and Yangguang Shi. Online Paging with a Vanishing Regret. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 67:1-67:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITCS.2021.67

Abstract

This paper considers a variant of the online paging problem, where the online algorithm has access to multiple predictors, each producing a sequence of predictions for the page arrival times. The predictors may have occasional prediction errors and it is assumed that at least one of them makes a sublinear number of prediction errors in total. Our main result states that this assumption suffices for the design of a randomized online algorithm whose time-average regret with respect to the optimal offline algorithm tends to zero as the time tends to infinity. This holds (with different regret bounds) for both the full information access model, where in each round, the online algorithm gets the predictions of all predictors, and the bandit access model, where in each round, the online algorithm queries a single predictor. While online algorithms that exploit inaccurate predictions have been a topic of growing interest in the last few years, to the best of our knowledge, this is the first paper that studies this topic in the context of multiple predictors for an online problem with unbounded request sequences. Moreover, to the best of our knowledge, this is also the first paper that aims for (and achieves) online algorithms with a vanishing regret for a classic online problem under reasonable assumptions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online learning algorithms
  • Theory of computation → Caching and paging algorithms
Keywords
  • online paging
  • inaccurate predictions
  • multiple predictors
  • vanishing regret
  • full information vs. bandit access

Metrics

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

Related Versions

References

  1. Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. In Proceedings of Machine Learning and Systems, ICML '20, pages 11463-11473. PMLR, 2020. URL: https://proceedings.icml.cc/static/paper_files/icml/2020/6657-Paper.pdf.
  2. Jean-Yves Audibert and Sébastien Bubeck. Minimax policies for adversarial and stochastic bandits. In COLT '09 - The 22nd Conference on Learning Theory, Montreal, Quebec, Canada, June 2009. URL: http://www.cs.mcgill.ca/%7Ecolt2009/papers/022.pdf#page=1.
  3. Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-77, 2002. URL: https://doi.org/10.1137/S0097539701398375.
  4. Grant Ayers, Heiner Litz, Christos Kozyrakis, and Parthasarathy Ranganathan. Classifying memory access patterns for prefetching. In Architectural Support for Programming Languages and Operating Systems, ASPLOS '20, pages 513-526, Lausanne, Switzerland, March 2020. ACM. URL: https://doi.org/10.1145/3373376.3378498.
  5. Laszlo A. Belady. A study of replacement algorithms for virtual-storage computer. IBM Systems Journal, 5(2):78-101, 1966. URL: https://doi.org/10.1147/sj.52.0078.
  6. Avrim Blum and Carl Burch. On-line learning and the metrical task system problem. Machine Learning, 39(1):35-58, 2000. URL: https://doi.org/10.1023/A:1007621832648.
  7. Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press, 1998. Google Scholar
  8. Allan Borodin, Nathan Linial, and Michael E. Saks. An optimal on-line algorithm for metrical task system. J. ACM, 39(4):745-763, 1992. URL: https://doi.org/10.1145/146585.146588.
  9. Peter Braun and Heiner Litz. Understanding memory access patterns for prefetching. In International Workshop on AI-assisted Design for Architecture (AIDArc), held in conjunction with ISCA, 2019. URL: https://eecs.oregonstate.edu/aidarc/paper/MAP.pdf.
  10. Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University Press, USA, 2006. URL: https://doi.org/10.1017/CBO9780511546921.
  11. Yuval Emek, Shay Kutten, and Yangguang Shi. Online paging with a vanishing regret. arXiv preprint, 2020. URL: http://arxiv.org/abs/2011.09439.
  12. Yuval Emek, Ron Lavi, Rad Niazadeh, and Yangguang Shi. Stateful posted pricing with vanishing regret via dynamic deterministic markov decision processes. Advances in Neural Information Processing Systems (NeurIPS '20), 33, 2020. URL: https://papers.nips.cc/paper/2020/file/1f10c3650a3aa5912dccc5789fd515e8-Paper.pdf.
  13. Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel Dominic Sleator, and Neal E. Young. Competitive paging algorithms. Journal of Algorithms, 12(4):685-699, 1991. URL: https://doi.org/10.1016/0196-6774(91)90041-V.
  14. Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of ICML '19, pages 2319-2327, Long Beach, California, USA, June 2019. PMLR. URL: http://proceedings.mlr.press/v97/gollapudi19a.html.
  15. Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In 3rd International Conference on Learning Representations, ICLR '15, San Diego, CA, USA, May 2015. URL: http://arxiv.org/abs/1412.6572.
  16. Milad Hashemi, Kevin Swersky, Jamie A. Smith, Grant Ayers, Heiner Litz, Jichuan Chang, Christos Kozyrakis, and Parthasarathy Ranganathan. Learning memory access patterns. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of ICML '18, pages 1924-1933, Stockholmsmässan, Stockholm, Sweden, July 2018. PMLR. URL: http://proceedings.mlr.press/v80/hashemi18a.html.
  17. Evan Zheran Liu, Milad Hashemi, Kevin Swersky, Parthasarathy Ranganathan, and Junwhan Ahn. An imitation learning approach for cache replacement. In Proceedings of the 37th International Conference on Machine Learning, ICML '20, July 2020. URL: http://arxiv.org/abs/2006.16239.
  18. Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. In Proceedings of the 35th International Conference on Machine Learning, ICML '18, volume 80, pages 3302-3311, Stockholmsmässan, Stockholm, Sweden, July 2018. PMLR. URL: http://proceedings.mlr.press/v80/lykouris18a.html.
  19. Leeor Peled, Uri C. Weiser, and Yoav Etsion. A neural network prefetcher for arbitrary memory access patterns. ACM Transactions on Architecture and Code Optimization (TACO), 16(4):37:1-37:27, 2020. URL: https://doi.org/10.1145/3345000.
  20. Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA '20, pages 1834-1845, Salt Lake City, UT, USA, January 2020. SIAM. URL: https://doi.org/10.1137/1.9781611975994.112.
  21. Daniel D. Sleator and Robert E. Tarjan. Amortized efficiency of list update and paging rules. Commun. ACM, 28(2):202–208, 1985. URL: https://doi.org/10.1145/2786.2793.
  22. Ajitesh Srivastava, Angelos Lazaris, Benjamin Brooks, Rajgopal Kannan, and Viktor K. Prasanna. Predicting memory accesses: the road to compact ml-driven prefetcher. In Proceedings of the International Symposium on Memory Systems, MEMSYS '19, pages 461-470, Washington, DC, USA, September - October 2019. ACM. URL: https://doi.org/10.1145/3357526.3357549.
  23. Ajitesh Srivastava, Ta-Yang Wang, Pengmiao Zhang, César Augusto Fonticielha De Rose, Rajgopal Kannan, and Viktor K. Prasanna. Memmap: Compact and generalizable meta-lstm models for memory access prediction. In Advances in Knowledge Discovery and Data Mining - 24th Pacific-Asia Conference, volume 12085 of PAKDD '20, pages 57-68, Singapore, May 2020. Springer. URL: https://doi.org/10.1007/978-3-030-47436-2_5.
  24. Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In 2nd International Conference on Learning Representations, ICLR '14, Banff, AB, Canada, April 2014. URL: http://arxiv.org/abs/1312.6199.
  25. Alexander Wei. Better and simpler learning-augmented online caching. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, volume 176 of APPROX/RANDOM '20, pages 60:1-60:17, Virtual Conference, August 2020. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.60.
  26. William A. Wulf and Sally A. McKee. Hitting the memory wall: implications of the obvious. SIGARCH Computer Architecture News, 23(1):20-24, 1995. URL: https://doi.org/10.1145/216585.216588.
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 Imprint Privacy Contact