{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T14:12:43Z","timestamp":1766067163346,"version":"3.41.0"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,6,9]],"date-time":"2020-06-09T00:00:00Z","timestamp":1591660800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100005144","name":"Qualcomm","doi-asserted-by":"publisher","award":["IND-417880"],"award-info":[{"award-number":["IND-417880"]}],"id":[{"id":"10.13039\/100005144","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2020,6,9]]},"abstract":"<jats:p>Optimal caching of files in a content distribution network (CDN) is a problem of fundamental and growing commercial interest. Although many different caching algorithms are in use today, the fundamental performance limits of network caching algorithms from an online learning point-of-view remain poorly understood to date. In this paper, we resolve this question in the following two settings: (1) a single user connected to a single cache, and (2) a set of users and a set of caches interconnected through a bipartite network. Recently, an online gradient-based coded caching policy was shown to enjoy sub-linear regret. However, due to the lack of known regret lower bounds, the question of the optimality of the proposed policy was left open. In this paper, we settle this question by deriving tight non-asymptotic regret lower bounds in both of the above settings. In addition to that, we propose a new Follow-the-Perturbed-Leader-based uncoded caching policy with near-optimal regret. Technically, the lower-bounds are obtained by relating the online caching problem to the classic probabilistic paradigm of balls-into-bins. Our proofs make extensive use of a new result on the expected load in the most populated half of the bins, which might also be of independent interest. We evaluate the performance of the caching policies by experimenting with the popular MovieLens dataset and conclude the paper with design recommendations and a list of open problems.<\/jats:p>","DOI":"10.1145\/3392143","type":"journal-article","created":{"date-parts":[[2020,6,9]],"date-time":"2020-06-09T22:10:12Z","timestamp":1591740612000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["Fundamental Limits on the Regret of Online Network-Caching"],"prefix":"10.1145","volume":"4","author":[{"given":"Rajarshi","family":"Bhattacharjee","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Madras, Chennai, India"}]},{"given":"Subhankar","family":"Banerjee","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Madras, Chennai, India"}]},{"given":"Abhishek","family":"Sinha","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Madras, Chennai, India"}]}],"member":"320","published-online":{"date-parts":[[2020,6,12]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. MovieLens 25M Dataset. https:\/\/grouplens.org\/datasets\/movielens\/. Accessed: 01--19--2019.  [n.d.]. MovieLens 25M Dataset. https:\/\/grouplens.org\/datasets\/movielens\/. Accessed: 01--19--2019."},{"volume-title":"Conference on Learning Theory. 807--823","year":"2014","author":"Abernethy Jacob","key":"e_1_2_1_2_1"},{"volume-title":"In Proceedings of the Nineteenth Annual Conference on Computational Learning Theory.","year":"2008","author":"Abernethy Jacob","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.755618"},{"key":"e_1_2_1_5_1","unstructured":"Shipra Agrawal and Navin Goyal. 2013. Further optimal regret bounds for thompson sampling. In Artificial intelligence and statistics. 99--107.  Shipra Agrawal and Navin Goyal. 2013. Further optimal regret bounds for thompson sampling. In Artificial intelligence and statistics. 99--107."},{"key":"e_1_2_1_6_1","unstructured":"Susanne Albers. 1996. Competitive online algorithms. Citeseer.  Susanne Albers. 1996. Competitive online algorithms. Citeseer."},{"key":"e_1_2_1_7_1","unstructured":"Noga Alon and Joel H Spencer. 2004. The probabilistic method. John Wiley & Sons.  Noga Alon and Joel H Spencer. 2004. The probabilistic method. John Wiley & Sons."},{"key":"e_1_2_1_8_1","unstructured":"EC Amazon. 2015. Amazon web services. Available in: http:\/\/aws. amazon. com\/es\/ec2\/(November 2012) (2015).  EC Amazon. 2015. Amazon web services. Available in: http:\/\/aws. amazon. com\/es\/ec2\/(November 2012) (2015)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.spl.2013.01.023"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219617.3219627"},{"key":"e_1_2_1_11_1","unstructured":"Dimitri P Bertsekas and Athena Scientific. 2015. Convex optimization algorithms. Athena Scientific Belmont.  Dimitri P Bertsekas and Athena Scientific. 2015. Convex optimization algorithms. Athena Scientific Belmont."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3211852.3211857"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.1999.749260"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Nicolo Cesa-Bianchi and G\u00e1bor Lugosi. 2006. Prediction learning and games. Cambridge university press.  Nicolo Cesa-Bianchi and G\u00e1bor Lugosi. 2006. Prediction learning and games. Cambridge university press.","DOI":"10.1017\/CBO9780511546921"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097895.3097902"},{"key":"e_1_2_1_16_1","unstructured":"David Chappell et al. 2010. Introducing the windows azure platform. David Chappell & Associates White Paper (2010).  David Chappell et al. 2010. Introducing the windows azure platform. David Chappell & Associates White Paper (2010)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48228-8_12"},{"volume-title":"International Conference on Machine Learning. 1034--1042","year":"2015","author":"Cohen Alon","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2796314.2745852"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Asit Dan and Don Towsley. 1990. An approximate analysis of the LRU and FIFO buffer replacement schemes. Vol. 18. ACM.  Asit Dan and Don Towsley. 1990. An approximate analysis of the LRU and FIFO buffer replacement schemes. Vol. 18. ACM.","DOI":"10.1145\/98457.98525"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Alexandros G Dimakis P Brighten Godfrey Yunnan Wu Martin J Wainwright and Kannan Ramchandran. 2010. Network coding for distributed storage systems. IEEE transactions on information theory 56 9 (2010) 4539--4551.  Alexandros G Dimakis P Brighten Godfrey Yunnan Wu Martin J Wainwright and Kannan Ramchandran. 2010. Network coding for distributed storage systems. IEEE transactions on information theory 56 9 (2010) 4539--4551.","DOI":"10.1109\/TIT.2010.2054295"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149371"},{"volume-title":"Improved Multi-Rate Video Encoding. In 2011 IEEE International Symposium on Multimedia. 293--300","year":"2011","author":"Finstad D. H.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90177-C"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/322248.322254"},{"volume-title":"Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics. 273--280","year":"2010","author":"Gr\u00fcnew\u00e4lder Steffen","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","first-page":"396","article-title":"Multiple bit rate video encoding using variable bit rate and dynamic resolution for adaptive video streaming","volume":"8","author":"Gu Chuang","year":"2013","journal-title":"US Patent"},{"key":"e_1_2_1_28_1","unstructured":"Ori Gurel-Gurevich. [n.d.]. Expectation of square root of binomial r.v. MathOverflow. arXiv:https:\/\/mathoverflow.net\/q\/121424 https:\/\/mathoverflow.net\/q\/121424 URL:https:\/\/mathoverflow.net\/q\/121424 (version: 2013-02--10).  Ori Gurel-Gurevich. [n.d.]. Expectation of square root of binomial r.v. MathOverflow. arXiv:https:\/\/mathoverflow.net\/q\/121424 https:\/\/mathoverflow.net\/q\/121424 URL:https:\/\/mathoverflow.net\/q\/121424 (version: 2013-02--10)."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"F Maxwell Harper and Joseph A Konstan. 2015. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis) 5 4 (2015) 1--19.  F Maxwell Harper and Joseph A Konstan. 2015. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis) 5 4 (2015) 1--19.","DOI":"10.1145\/2827872"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-007-5016-8"},{"key":"e_1_2_1_31_1","unstructured":"Elad Hazan and Sanjeev Arora. 2006. Efficient algorithms for online convex optimization and their applications. Princeton University Princeton.  Elad Hazan and Sanjeev Arora. 2006. Efficient algorithms for online convex optimization and their applications. Princeton University Princeton."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2670328"},{"key":"e_1_2_1_33_1","first-page":"379","article-title":"Multi-resolution video coding and decoding","volume":"7","author":"Holcomb Thomas W","year":"2008","journal-title":"US Patent"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1453175.1453203"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2504556"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/SPAWC.2015.7227127"},{"key":"e_1_2_1_37_1","volume-title":"Proc. ACM Meas. Anal. Comput. Syst.","volume":"4","author":"Kolchin Valentin Fedorovich","year":"1978"},{"key":"e_1_2_1_38_1","unstructured":"Branislav Kveton Zheng Wen Azin Ashkan and Csaba Szepesvari. 2015. Tight regret bounds for stochastic combinatorial semi-bandits. In Artificial Intelligence and Statistics. 535--543.  Branislav Kveton Zheng Wen Azin Ashkan and Csaba Szepesvari. 2015. Tight regret bounds for stochastic combinatorial semi-bandits. In Artificial Intelligence and Statistics. 535--543."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/301453.301487"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Boxi Liu Konstantinos Poularakis Leandros Tassiulas and Tao Jiang. 2019. Joint Caching and Routing in Congestible Networks of Arbitrary Topology. IEEE Internet of Things Journal (2019).  Boxi Liu Konstantinos Poularakis Leandros Tassiulas and Tao Jiang. 2019. Joint Caching and Routing in Congestible Networks of Arbitrary Topology. IEEE Internet of Things Journal (2019).","DOI":"10.1109\/JIOT.2019.2935742"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"M Luby A Shokrollahi M Watson T Stockhammer and L Minder. 2011. RaptorQ forward error correction scheme for object delivery?rfc 6330. IETF Request For Comments (2011).  M Luby A Shokrollahi M Watson T Stockhammer and L Minder. 2011. RaptorQ forward error correction scheme for object delivery?rfc 6330. IETF Request For Comments (2011).","DOI":"10.17487\/rfc6330"},{"key":"e_1_2_1_42_1","unstructured":"Thodoris Lykouris and Sergei Vassilvitskii. 2018. Competitive caching with machine learned advice. arXiv preprint arXiv:1802.05399 (2018).  Thodoris Lykouris and Sergei Vassilvitskii. 2018. Competitive caching with machine learned advice. arXiv preprint arXiv:1802.05399 (2018)."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2306938"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCOM.2016.7537173"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2805789.2805800"},{"volume-title":"Proceedings of The 27th Conference on Learning Theory, COLT 2014","year":"2014","author":"Magureanu Stefan","key":"e_1_2_1_46_1"},{"key":"e_1_2_1_47_1","unstructured":"Michael Mitzenmacher and Eli Upfal. 2017. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press.  Michael Mitzenmacher and Eli Upfal. 2017. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press."},{"key":"e_1_2_1_48_1","unstructured":"Michael David Mitzenmacher. 1996. The Power of Two Choices in Randomized Load Balancing. Ph.D. Dissertation. UNIVERSITY of CALIFORNIA at BERKELEY.  Michael David Mitzenmacher. 1996. The Power of Two Choices in Randomized Load Balancing. Ph.D. Dissertation. UNIVERSITY of CALIFORNIA at BERKELEY."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1842733.1842736"},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","unstructured":"Georgios Paschos George Iosifidis and Giuseppe Caire. 2019. Cache Optimization Models and Algorithms. arXiv preprint arXiv:1912.12339 (2019).  Georgios Paschos George Iosifidis and Giuseppe Caire. 2019. Cache Optimization Models and Algorithms. arXiv preprint arXiv:1912.12339 (2019).","DOI":"10.1561\/9781680837032"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2019.8737446"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/3001647.3001661"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49543-6_13"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.23919\/IFIPNetworking.2017.8264840"},{"key":"e_1_2_1_55_1","doi-asserted-by":"crossref","unstructured":"Herbert Robbins. 1955. A remark on Stirling's formula. The American mathematical monthly 62 1 (1955) 26--29.  Herbert Robbins. 1955. A remark on Stirling's formula. The American mathematical monthly 62 1 (1955) 26--29.","DOI":"10.2307\/2308012"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2013.6566874"},{"key":"e_1_2_1_57_1","unstructured":"Walter Rudin et al. 1964. Principles of mathematical analysis. Vol. 3. McGraw-hill New York.  Walter Rudin et al. 1964. Principles of mathematical analysis. Vol. 3. McGraw-hill New York."},{"key":"e_1_2_1_58_1","volume-title":"2000 IEEE International Conference on Multimedia and Expo. ICME2000","volume":"2","author":"Serpanos D. N.","year":"2000"},{"key":"e_1_2_1_59_1","doi-asserted-by":"crossref","unstructured":"Shai Shalev-Shwartz etal 2012. Online learning and online convex optimization. Foundations and Trends\u00ae in Machine Learning 4 2 (2012) 107--194.  Shai Shalev-Shwartz et al. 2012. Online learning and online convex optimization. Foundations and Trends\u00ae in Machine Learning 4 2 (2012) 107--194.","DOI":"10.1561\/2200000018"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2281606"},{"key":"e_1_2_1_61_1","doi-asserted-by":"crossref","unstructured":"Amin Shokrollahi. 2006. Raptor codes. IEEE\/ACM Transactions on Networking (TON) 14 SI (2006) 2551--2567.  Amin Shokrollahi. 2006. Raptor codes. IEEE\/ACM Transactions on Networking (TON) 14 SI (2006) 2551--2567.","DOI":"10.1109\/TIT.2006.874390"},{"key":"e_1_2_1_62_1","first-page":"1","article-title":"The hadoop distributed file system","volume":"10","author":"Shvachko Konstantin","year":"2010","journal-title":"MSST"},{"key":"e_1_2_1_63_1","unstructured":"Abraham Silberschatz Peter Baer Galvin and Greg Gagne. 2006. Operating system principles. John Wiley & Sons.  Abraham Silberschatz Peter Baer Galvin and Greg Gagne. 2006. Operating system principles. John Wiley & Sons."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMM.2015.2458043"},{"key":"e_1_2_1_65_1","volume-title":"Proc. ACM Meas. Anal. Comput. Syst.","volume":"4","author":"Roy Benjamin Van","year":"2007"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1005686.1005722"},{"key":"e_1_2_1_67_1","unstructured":"Jinesh Varia Sajee Mathew etal 2014. Overview of amazon web services. Amazon Web Services (2014) 1--22.  Jinesh Varia Sajee Mathew et al. 2014. Overview of amazon web services. Amazon Web Services (2014) 1--22."},{"key":"e_1_2_1_68_1","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1109\/TPDS.2007.1119","article-title":"rStream: resilient and optimal peer-to-peer streaming with rateless codes","volume":"19","author":"Wu Chuan","year":"2007","journal-title":"IEEE Transactions on Parallel and Distributed Systems"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3392143","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3392143","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:48Z","timestamp":1750199928000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3392143"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,9]]},"references-count":68,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,6,9]]}},"alternative-id":["10.1145\/3392143"],"URL":"https:\/\/doi.org\/10.1145\/3392143","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2020,6,9]]},"assertion":[{"value":"2020-06-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}