More Web Proxy on the site http://driver.im/

research-article

Open access

Optimistic No-regret Algorithms for Discrete Caching

Authors:

Abhishek Sinha,

Georgios Paschos,

George IosifidisAuthors Info & Claims

Proceedings of the ACM on Measurement and Analysis of Computing Systems, Volume 6, Issue 3

Article No.: 48, Pages 1 - 28

https://doi.org/10.1145/3570608

Published: 08 December 2022 Publication History

Abstract

We take a systematic look at the problem of storing whole files in a cache with limited capacity in the context of optimistic learning, where the caching policy has access to a prediction oracle (provided by, e.g., a Neural Network). The successive file requests are assumed to be generated by an adversary, and no assumption is made on the accuracy of the oracle. In this setting, we provide a universal lower bound for prediction-assisted online caching and proceed to design a suite of policies with a range of performance-complexity trade-offs. All proposed policies offer sublinear regret bounds commensurate with the accuracy of the oracle. Our results substantially improve upon all recently-proposed online caching policies, which, being unable to exploit the oracle predictions, offer only O(√T) regret. In this pursuit, we design, to the best of our knowledge, the first comprehensive optimistic Follow-the-Perturbed leader policy, which generalizes beyond the caching problem. We also study the problem of caching files with different sizes and the bipartite network caching problem. Finally, we evaluate the efficacy of the proposed policies through extensive numerical experiments using real-world traces.

References

[1]

A. Giovanidis, and A. Avranas. 2016. Spatial Multi-LRU: Distributed Caching for Wireless Networks with Coverage Overlaps. arXiv:1612.04363 (2016).

[2]

Jacob Abernethy, Chansoo Lee, Abhinav Sinha, and Ambuj Tewari. 2014. Online Linear Optimization via Smoothing. In Proc. of COLT.

[3]

Noga Alon and Joel H Spencer. 2016. The probabilistic method. John Wiley & Sons.

[4]

Xavier Amatriain. 2012. Building Industrial-Scale Real-World Recommender Systems. In Proc. of RecSys.

Digital Library

[5]

Daron Anderson, George Iosifidis, and Douglas Leith. 2022. Lazy Lagrangians with Predictions for Online Learning. arXiv preprint arXiv:2201.02890 (2022).

[6]

Lachlan Andrew, Siddharth Barman, Katrina Ligett, Minghong Lin, Adam Meyerson, Alan Roytman, and Adam Wierman. 2013. A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret. In Proc. of COLT.

Digital Library

[7]

Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Bertrand Simon. 2020. Online Metric Algorithms with Untrusted Predictions. In Proc. of ICML.

[8]

T Bektas, O Oguz, and Ouveysi I. 2007. Designing Cost-effective Content Distribution Networks. Computers & Operations Research, Vol. 34 (2007), 2436--2449.

Digital Library

[9]

Dimitri P Bertsekas. 1973. Stochastic optimization problems with nondifferentiable cost functionals. Journal of Optimization Theory and Applications, Vol. 12, 2 (1973), 218--231.

[10]

Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. 2020a. Online Learning with Imperfect Hints. In Proc. of ICML.

[11]

A. Bhaskara, A. Cutkosky, R. Kumar, and M. Purohit. 2020b. Online Learning with Many Hints. In Proc. of NeurIPS.

[12]

Rajarshi Bhattacharjee, Subhankar Banerjee, and Abhishek Sinha. 2020. Fundamental Limits on the Regret of Online Network-Caching. Proc. ACM Meas. Anal. Comput. Syst., Vol. 4, 2 (2020), 31 pages.

Digital Library

[13]

Jarosław Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. 2017. An Improved Approximation for K-Median and Positive Correlation in Budgeted Optimization. ACM Trans. Algorithms, Vol. 13, 2 (2017).

Digital Library

[14]

Livia Elena Chatzieleftheriou, Merkouris Karaliopoulos, and Iordanis Koutsopoulos. 2019. Jointly Optimizing Content Caching and Recommendations in Small Cell Networks. IEEE Trans. Mobile Comput., Vol. 18, 1 (2019), 125--138.

Digital Library

[15]

Alon Cohen and Tamir Hazan. 2015. Following the Perturbed Leader for Online Structured Learning. In Proc. of the ICML.

[16]

J. Comden, S. Yao, N. Chen, H. Xing, and Z. Liu. 2019. Online Optimization in Cloud Resource Provisioning: Predictions, Regrets and Algorithms. Proc. ACM Meas. Anal. Comput. Syst., Vol. 1, 3 (2019), 30 pages.

[17]

Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2022. Introduction to algorithms. MIT press.

[18]

D. Chatzopoulos, C. Bermejo, Z. Huang, and P. Hui. 2017. Mobile Augmented Reality Survey: From Where We Are to Where We Go. IEEE Access, Vol. 5 (2017), 6917--950.

[19]

George B. Dantzig. 1957. Discrete-Variable Extremum Problems. Operations Research, Vol. 5, 2 (1957), 266--277.

Digital Library

[20]

Steven De Rooij, Tim Van Erven, Peter D. Grünwald, and Wouter M. Koolen. 2014. Follow the Leader If You Can, Hedge If You Must. J. Mach. Learn. Res., Vol. 15, 1 (2014), 1281--1316.

[21]

E. Leonardi, and G. Neglia. 2018. Implicit Coordination of Caches in Small-cell Networks Under Unknown Popularity Profiles. IEEE J. Sel. Areas Commun., Vol. 36, 6 (2018), 1276--1285.

Digital Library

[22]

Yaru Fu, Yue Zhang, Angus Wong, and Tony Q.S. Quek. 2022. Revenue Maximization: The Interplay Between Personalized Bundle Recommendation and Wireless Content Caching. IEEE Trans. on Mobile Comput. (2022). https://doi.org/10.1109/TMC.2022.3142809

Digital Library

[23]

G. Gracioli, A. Alhammad, R. Mancuso, A. A. Frohlich, R. Pellizzoni. 2015. A Survey on Cache Management Mechanisms for Real-Time Embedded Systems. ACM Comput. Surv., Vol. 48, 2 (2015), 37 pages.

Digital Library

[24]

Theodoros Giannakas, Pavlos Sermpezis, and Thrasyvoulos Spyropoulos. 2021. Network Friendly Recommendations: Optimizing for Long Viewing Sessions. IEEE Trans. on Mobile Comput. (2021). https://doi.org/10.1109/TMC.2021.3109727

[25]

Carlos A. Gomez-Uribe and Neil Hunt. 2016. The Netflix Recommender System: Algorithms, Business Value, and Innovation. ACM Trans. Manage. Inf. Syst., Vol. 6, 4 (2016), 19 pages.

Digital Library

[26]

Geoffrey J Gordon, Amy Greenwald, and Casey Marks. 2008. No-regret learning in convex games. In Proceedings of the 25th international conference on Machine learning. 360--367.

Digital Library

[27]

Robert Gramacy, Manfred Warmuth, Scott Brandt, and Ismail Ari. 2002. Adaptive Caching by Refetching. In Proc. of NIPS.

[28]

Fabrice Guillemin, Thierry Houdoin, and Stéphanie Moteau. 2013. Volatility of YouTube content in Orange networks and consequences. In Proc. of ICC.

[29]

F. Maxwell Harper and Joseph A. Konstan. 2015. The MovieLens Datasets: History and Context. ACM Trans. Interact. Intell. Syst., Vol. 5, 4 (2015), 19 pages.

Digital Library

[30]

Elad Hazan. 2019. Introduction to Online Convex Optimization. https://arxiv.org/abs/1909.05207

[31]

Marcus Hutter and Jan Poland. 2005. Adaptive Online Prediction by Following the Perturbed Leader. Journal of Machine Learning Research, Vol. 6, 22 (2005), 639--660.

Digital Library

[32]

Predrag R. Jelenković and Xiaozhu Kang. 2008. Characterizing the Miss Sequence of the LRU Cache. SIGMETRICS Perform. Eval. Rev., Vol. 36, 2 (2008), 119--121.

Digital Library

[33]

Ativ Joshi and Abhishek Sinha. 2022. Universal Caching. arXiv preprint arXiv:2205.04860 (2022).

[34]

K. Chen, and L. Huang. 2018. Timely-Throughput Optimal Scheduling With Prediction. IEEE/ACM Tran. on Networking, Vol. 26, 6 (2018), 2457--2470.

Digital Library

[35]

Adam Kalai and Santosh Vempala. 2005. Efficient algorithms for online decision problems. J. Comput. System Sci., Vol. 71, 3 (2005), 291--307.

Digital Library

[36]

Mathieu Leconte, Georgios Paschos, Lazaros Gkatzikis, Moez Draief, Spyridon Vassilaras, and Symeon Chouvardas. 2016. Placing Dynamic Content in Caches with Small Population. In Proc. of IEEE INFOCOM.

Digital Library

[37]

Donghee Lee, Jongmoo Choi, Jong-Hun Kim, Sam H. Noh, Sang Lyul Min, Yookun Cho, and Chong Sang Kim. 1999. On the Existence of a Spectrum of Policies That Subsumes the Least Recently Used (LRU) and Least Frequently Used (LFU) Policies. SIGMETRICS Perform. Eval. Rev., Vol. 27, 1 (1999), 134--143.

Digital Library

[38]

Yuanyuan Li, Tareq Si Salem, Giovanni Neglia, and Stratis Ioannidis. 2021. Online Caching Networks with Adversarial Guarantees. Proc. ACM Meas. Anal. Comput. Syst., Vol. 5, 3 (2021), 39 pages.

Digital Library

[39]

Thodoris Lykouris and Sergei Vassilvtiskii. 2018. Competitive Caching with Machine Learned Advice. In Proc. of ICML.

[40]

M. A. Maddah-Ali, and U. Niesen. 2014. Fundamental Limits of Caching. IEEE Trans. Inf. Theory, Vol. 60, 5 (2014), 2856--2867.

[41]

William G. Madow. 1949. On the Theory of Systematic Sampling. The Annals of Mathematical Statistics, Vol. 20, 3 (1949), 333--354.

[42]

Silvano Martello and Paolo Toth. 1990. Knapsack Problems: Algorithms and Computer Implementations. J. Willey & Sons.

Digital Library

[43]

H. Brendan McMahan. 2017. A Survey of Algorithms and Analysis for Adaptive Online Learning. J. Mach. Learn. Res., Vol. 18, 1 (2017), 3117--3166.

Digital Library

[44]

Naram Mhaisen, George Iosifidis, and Douglas Leith. 2022a. Online Caching with no Regret: Optimistic Learning via Recommendations. https://arxiv.org/abs/2204.09345

[45]

Naram Mhaisen, George Iosifidis, and Douglas Leith. 2022b. Online Caching with Optimistic Learning. In Proc. of IFIP Networking.

[46]

Mehryar Mohri and Scott Yang. 2016. Accelerating Online Convex Optimization via Adaptive Prediction. In Proc. of AISTATS.

[47]

Samrat Mukhopadhyay, Sourav Sahoo, and Abhishek Sinha. 2022. k-experts-Online Policies and Fundamental Limits. In International Conference on Artificial Intelligence and Statistics. PMLR, 342--365.

[48]

et al. O. Dekel. 2017. Online Learning with a Hint. In Proc. of NeurIPS.

[49]

Felipe Olmos, Bruno Kauffmann, Alain Simonian, and Yannick Carlinet. 2014. Catalog dynamics: Impact of content publishing and perishing on the performance of a LRU cache. In Proc. of ITC.

[50]

Francesco Orabona. 2019. A Modern Introduction to Online Learning. https://arxiv.org/abs/1912.13213

[51]

Debjit Paria and Abhishek Sinha. 2021. LeadCache: Regret-Optimal Caching in Networks. In Proc. of NeurIPS.

[52]

Georgios Paschos, George Iosifidis, and Giuseppe Caire. 2020b. Cache Optimization Models and Algorithms. FnT in Communications and Information Theory, Vol. 16, 3--4 (2020), 156--345.

Digital Library

[53]

Georgios S. Paschos, Apostolos Destounis, and George Iosifidis. 2020a. Online Convex Optimization for Caching Networks. IEEE/ACM Trans. Networking, Vol. 28, 2 (2020), 625--638.

Digital Library

[54]

Georgios S. Paschos, George Iosifidis, Meixia Tao, Don Towsley, and Giuseppe Caire. 2018. The Role of Caching in Future Communication Systems and Networks. IEEE J. Select. Areas Commun., Vol. 36, 6 (2018), 1111--1125.

Digital Library

[55]

Konstantinos Poularakis, George Iosifidis, and Leandros Tassiulas. 2014. Approximation Algorithms for Mobile Data Caching in Small Cell Networks. IEEE Trans. Commun., Vol. 62, 10 (2014), 3665--3677.

[56]

Alexander Rakhlin and Karthik Sridharan. 2013. Optimization, Learning, and Games with Predictable Sequences. In Proc. of NeurIPS.

[57]

Liana Rodriguez, Farzana Yusuf, Steven Lyons, Eysler Paz, and Raju Rangaswami. 2021. Learning Cache Replacement with Cacheus. In Proc. of USENIX Conferecne on File and Storage Technologies.

[58]

Dhruv Rohatgi. 2020. Near-Optimal Bounds for Online Caching with Machine Learned Advice. In Proc. of ACM-SIAM SODA.

[59]

Daan Rutten, Nico Christianson, Debankur Mukherjee, and Adam Wierman. 2022. Online Optimization with Untrusted Predictions. https://arxiv.org/abs/2202.03519

[60]

Sarah Sachs, Hédi Hadiji, Tim van Erven, and Cristóbal Guzmán. 2022. Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness. https://arxiv.org/abs/2202.07554

[61]

Alireza Sadeghi, Fatemeh Sheikholeslami, and Georgios B. Giannakis. 2018. Optimal and Scalable Caching for 5G Using Reinforcement Learning of Space-Time Popularities. IEEE J. Select. Areas Commun., Vol. 12, 1 (2018), 180--190.

[62]

Alireza Sadeghi, Fatemeh Sheikholeslami, Antonio G. Marques, and Georgios B. Giannakis. 2019. Reinforcement Learning for Adaptive Caching With Dynamic Storage Pricing. IEEE J. Select. Areas Commun, Vol. 37, 10 (2019), 2267--2281.

[63]

Karthikeyan Shanmugam, Negin Golrezaei, Alexandros G Dimakis, Andreas F Molisch, and Giuseppe Caire. 2013. Femtocaching: Wireless Content Delivery Through Distributed Caching Helpers. IEEE Trans. Inform. Theory, Vol. 59, 12 (2013), 8402--8413.

Digital Library

[64]

T. Si Salem, G. Neglia, and S. Ioannidis. 2021a. No-Regret Caching via Online Mirror Descent. https://arxiv.org/abs/2101.12588

[65]

Tareq Si Salem, Giovanni Neglia, and Stratis Ioannidis. 2021b. No-Regret Caching via Online Mirror Descent. In Proc. of ICC.

[66]

Samuel O. Somuyiwa, András György, and Deniz Gündüz. 2018. A Reinforcement-Learning Approach to Proactive Caching in Wireless Networks. IEEE J. Select. Areas Commun., Vol. 36, 6 (2018), 1331--1344.

Digital Library

[67]

Arun Suggala and Praneeth Netrapalli. 2020a. Follow the Perturbed Leader: Optimism and Fast Parallel Algorithms for Smooth Minimax Games. In Proc. of NeurIPS.

[68]

Arun Sai Suggala and Praneeth Netrapalli. 2020b. Online Non-Convex Learning: Following the Perturbed Leader is Optimal. In Proc. of ALT.

[69]

Stefano Traverso, Mohamed Ahmed, Michele Garetto, Paolo Giaccone, Emilio Leonardi, and Saverio Niccolini. 2013. Temporal Locality in Today's Content Caching: Why It Matters and How to Model It. SIGCOMM Comput. Commun. Rev., Vol. 43, 5 (2013), 5--12.

Digital Library

[70]

Vijay V Vazirani. 2001. Approximation algorithms. Vol. 1. Springer.

Digital Library

[71]

W. Wang, and C. Lu. 2015. Projection onto the Capped Simplex. arXiv preprint arXiv:1503.01002 (2015).

[72]

X. Huang, S. Bian, X. Gao, W. Wu, Z. Shao, Y. Yang, J. C.S. Lui. 2021. Online VNF Chaining and Predictive Scheduling: Optimality and Trade-Offs. IEEE/ACM Tran. on Networking, Vol. 29, 4 (2021), 1867--1880.

Digital Library

[73]

Z. Zhou, X. Chen, W. Wu, D. Wu, and J. Zhang. 2019. Predictive Online Server Provisioning for Cost-Efficient IoT Data Streaming Across Collaborative Edges. In Proc. of ACM Mobihoc.

[74]

Michael Zink, Kyoungwon Suh, Yu Gu, and Jim Kurose. 2009. Characteristics of YouTube Network Traffic at a Campus Network - Measurements, Models, and Implications. Comput. Netw., Vol. 53, 4 (2009), 501--514. io

Digital Library

Cited By

Aslan FIosifidis GAyala-Romero JGarcia-Saavedra ACosta-Perez X(2024)Fair Resource Allocation in Virtualized O-RAN PlatformsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/36390438:1(1-34)Online publication date: 21-Feb-2024
https://dl.acm.org/doi/10.1145/3639043
Faticanti FNeglia G(2024)Optimistic online caching for batched requestsComputer Networks10.1016/j.comnet.2024.110341244(110341)Online publication date: May-2024
https://doi.org/10.1016/j.comnet.2024.110341
Mhaisen NSinha APaschos GIosifidis G(2023)Optimistic No-regret Algorithms for Discrete CachingACM SIGMETRICS Performance Evaluation Review10.1145/3606376.359356151:1(69-70)Online publication date: 27-Jun-2023
https://dl.acm.org/doi/10.1145/3606376.3593561
Show More Cited By

Index Terms

Optimistic No-regret Algorithms for Discrete Caching
1. Networks
  1. Network performance evaluation
    1. Network performance analysis

Recommendations

Optimistic No-regret Algorithms for Discrete Caching
SIGMETRICS '23: Abstract Proceedings of the 2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems

We take a systematic look at the problem of storing whole files in a cache with limited capacity in the context of optimistic learning, where the caching policy has access to a prediction oracle. The successive file requests are assumed to be generated ...
Optimistic No-regret Algorithms for Discrete Caching
SIGMETRICS '23

We take a systematic look at the problem of storing whole files in a cache with limited capacity in the context of optimistic learning, where the caching policy has access to a prediction oracle. The successive file requests are assumed to be generated ...
On-line restricted caching
Special issue: On-line algorithm part I

We study the on-line caching problem in a restricted cache where each memory item can be placed in only a restricted subset of cache locations. Examples of restricted caches in practice include victim caches, assist caches, and skew caches. To the best ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Measurement and Analysis of Computing Systems

Proceedings of the ACM on Measurement and Analysis of Computing Systems Volume 6, Issue 3

POMACS

December 2022

534 pages

EISSN:2476-1249

DOI:10.1145/3576048

Editors:
Augustin Chaintreau
Columbia University
,
Leana Golubchik
University of Southern California, United States
,
Zhi-Li Zhang
University of Minnesota, United States

Issue’s Table of Contents

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 December 2022

Published in POMACS Volume 6, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

US-India NSF-DST collaborative research
European Commission

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
442
Total Downloads

Downloads (Last 12 months)277
Downloads (Last 6 weeks)18

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Aslan FIosifidis GAyala-Romero JGarcia-Saavedra ACosta-Perez X(2024)Fair Resource Allocation in Virtualized O-RAN PlatformsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/36390438:1(1-34)Online publication date: 21-Feb-2024
https://dl.acm.org/doi/10.1145/3639043
Faticanti FNeglia G(2024)Optimistic online caching for batched requestsComputer Networks10.1016/j.comnet.2024.110341244(110341)Online publication date: May-2024
https://doi.org/10.1016/j.comnet.2024.110341
Mhaisen NSinha APaschos GIosifidis G(2023)Optimistic No-regret Algorithms for Discrete CachingACM SIGMETRICS Performance Evaluation Review10.1145/3606376.359356151:1(69-70)Online publication date: 27-Jun-2023
https://dl.acm.org/doi/10.1145/3606376.3593561
Mazziane YFaticanti FNeglia GAlouf S(2023)No- Regret Caching with Noisy Request Estimates2023 IEEE Virtual Conference on Communications (VCC)10.1109/VCC60689.2023.10474978(341-346)Online publication date: 28-Nov-2023
https://doi.org/10.1109/VCC60689.2023.10474978

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents