{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,15]],"date-time":"2026-11-15T11:39:38Z","timestamp":1794742778686,"version":"4.9.1"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,7,14]],"date-time":"2021-07-14T00:00:00Z","timestamp":1626220800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"funder":[{"name":"NSF","award":["CCF-1563714"],"award-info":[{"award-number":["CCF-1563714"]}]},{"name":"Google Ph.D. Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:p>Traditional online algorithms encapsulate decision making under uncertainty, and give ways to hedge against all possible future events, while guaranteeing a nearly optimal solution, as compared to an offline optimum. On the other hand, machine learning algorithms are in the business of extrapolating patterns found in the data to predict the future, and usually come with strong guarantees on the expected generalization error.<\/jats:p>\n                  <jats:p>In this work, we develop a framework for augmenting online algorithms with a machine learned predictor to achieve competitive ratios that provably improve upon unconditional worst-case lower bounds when the predictor has low error. Our approach treats the predictor as a complete black box and is not dependent on its inner workings or the exact distribution of its errors.<\/jats:p>\n                  <jats:p>\n                    We apply this framework to the traditional caching problem\u2014creating an eviction strategy for a cache of size\n                    <jats:italic>k<\/jats:italic>\n                    . We demonstrate that naively following the oracle\u2019s recommendations may lead to very poor performance, even when the average error is quite low. Instead, we show how to modify the Marker algorithm to take into account the predictions and prove that this combined approach achieves a competitive ratio that both (i) decreases as the predictor\u2019s error decreases and (ii) is always capped by\n                    <jats:italic>O<\/jats:italic>\n                    (log\n                    <jats:italic>k<\/jats:italic>\n                    ), which can be achieved without any assistance from the predictor. We complement our results with an empirical evaluation of our algorithm on real-world datasets and show that it performs well empirically even when using simple off-the-shelf predictions.\n                  <\/jats:p>","DOI":"10.1145\/3447579","type":"journal-article","created":{"date-parts":[[2021,7,14]],"date-time":"2021-07-14T12:23:56Z","timestamp":1626265436000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":116,"title":["Competitive Caching with Machine Learned Advice"],"prefix":"10.1145","volume":"68","author":[{"given":"Thodoris","family":"Lykouris","sequence":"first","affiliation":[{"name":"Microsoft Research New York City"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sergei","family":"Vassilvitskii","sequence":"additional","affiliation":[{"name":"Google Research New York City"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,7,14]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"[n.d.]. Brightkite data. http:\/\/snap.stanford.edu\/data\/loc-brightkite.html.  [n.d.]. Brightkite data. http:\/\/snap.stanford.edu\/data\/loc-brightkite.html."},{"key":"e_1_2_2_2_1","unstructured":"[n.d.]. Citibike System Data. http:\/\/https:\/\/www.citibikenyc.com\/system-data.  [n.d.]. Citibike System Data. http:\/\/https:\/\/www.citibikenyc.com\/system-data."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00116-9"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/090766437"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509949"},{"key":"e_1_2_2_6_1","volume-title":"Proceedings of the 37th International Conference on Machine Learning (ICML).","author":"Anand Keerti","year":"2020","unstructured":"Keerti Anand , Rong Ge , and Debmalya Panigrahi . 2020 . Customizing ML predictions for online algorithms . In Proceedings of the 37th International Conference on Machine Learning (ICML). Keerti Anand, Rong Ge, and Debmalya Panigrahi. 2020. Customizing ML predictions for online algorithms. In Proceedings of the 37th International Conference on Machine Learning (ICML)."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566486.2568018"},{"key":"e_1_2_2_8_1","volume-title":"Online computation with untrusted advice. arXiv preprint arXiv:1905.05655","author":"Angelopoulos Spyros","year":"2019","unstructured":"Spyros Angelopoulos , Christoph D\u00fcrr , Shendan Jin , Shahin Kamali , and Marc Renault . 2019. Online computation with untrusted advice. arXiv preprint arXiv:1905.05655 ( 2019 ). Spyros Angelopoulos, Christoph D\u00fcrr, Shendan Jin, Shahin Kamali, and Marc Renault. 2019. Online computation with untrusted advice. arXiv preprint arXiv:1905.05655 (2019)."},{"key":"e_1_2_2_9_1","volume-title":"Proceedings of the 37th International Conference on Machine Learning (ICML).","author":"Antoniadis Antonios","year":"2020","unstructured":"Antonios Antoniadis , Christian Coester , Marek Elias , Adam Polak , and Simon Betrand . 2020 . Online metric algorithms with untrusted predictions . In Proceedings of the 37th International Conference on Machine Learning (ICML). Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Simon Betrand. 2020. Online metric algorithms with untrusted predictions. In Proceedings of the 37th International Conference on Machine Learning (ICML)."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027217"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.79"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055406"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.52.0078"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/290169"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2993749.2993766"},{"key":"e_1_2_2_16_1","volume-title":"COLT 2012 - The 25th Annual Conference on Learning Theory","author":"Bubeck S\u00e9bastien","year":"2012","unstructured":"S\u00e9bastien Bubeck and Aleksandrs Slivkins . 2012 . The best of both worlds: Stochastic and adversarial bandits . In COLT 2012 - The 25th Annual Conference on Learning Theory , June 25-27, 2012, Edinburgh, Scotland. 42.1\u201342.23. http:\/\/www.jmlr.org\/proceedings\/papers\/v23\/bubeck12b\/bubeck12b.pdf. S\u00e9bastien Bubeck and Aleksandrs Slivkins. 2012. The best of both worlds: Stochastic and adversarial bandits. In COLT 2012 - The 25th Annual Conference on Learning Theory, June 25-27, 2012, Edinburgh, Scotland. 42.1\u201342.23. http:\/\/www.jmlr.org\/proceedings\/papers\/v23\/bubeck12b\/bubeck12b.pdf."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020579"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591867"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/363095.363141"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2972953"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764536"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90041-V"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80060-1"},{"key":"e_1_2_2_24_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning (Proceedings of Machine Learning Research), Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.)","volume":"97","author":"Gollapudi Sreenivas","year":"2019","unstructured":"Sreenivas Gollapudi and Debmalya Panigrahi . 2019 . Online algorithms for rent-or-buy with expert advice . In Proceedings of the 36th International Conference on Machine Learning (Proceedings of Machine Learning Research), Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.) , Vol. 97 . PMLR, Long Beach, California, USA, 2319\u20132327. http:\/\/proceedings.mlr.press\/v97\/gollapudi19a.html. Sreenivas Gollapudi and Debmalya Panigrahi. 2019. Online algorithms for rent-or-buy with expert advice. In Proceedings of the 36th International Conference on Machine Learning (Proceedings of Machine Learning Research), Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.), Vol. 97. PMLR, Long Beach, California, USA, 2319\u20132327. http:\/\/proceedings.mlr.press\/v97\/gollapudi19a.html."},{"key":"e_1_2_2_25_1","volume-title":"International Conference on Learning Representations (ICLR).","author":"Hsu Chen-Yu","year":"2019","unstructured":"Chen-Yu Hsu , Piotr Indyk , Dina Katabi , and Ali Vakilian . 2019 . Learning-based frequency estimation algorithms . In International Conference on Learning Representations (ICLR). Chen-Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. 2019. Learning-based frequency estimation algorithms. In International Conference on Learning Representations (ICLR)."},{"key":"e_1_2_2_26_1","unstructured":"Piotr Indyk Frederik Mallmann-Trenn Slobodan Mitrovi\u00c4\u011e and Ronitt Rubinfeld. 2020. Online Page Migration with ML Advice. arxiv:cs.DS\/2006.05028  Piotr Indyk Frederik Mallmann-Trenn Slobodan Mitrovi\u00c4\u011e and Ronitt Rubinfeld. 2020. Online Page Migration with ML Advice. arxiv:cs.DS\/2006.05028"},{"key":"e_1_2_2_27_1","volume-title":"Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP).","author":"Jiang Zhihao","year":"2020","unstructured":"Zhihao Jiang , Debmalya Panigrahi , and Kevin Sun . 2020 . Online algorithms for weighted paging with predictions . In Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP). Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun. 2020. Online algorithms for weighted paging with predictions. In Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP)."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/3381089.3381203"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188918"},{"key":"e_1_2_2_31_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning (Proceedings of Machine Learning Research). PMLR, 3296\u20133305","author":"Lykouris Thodoris","year":"2018","unstructured":"Thodoris Lykouris and Sergei Vassilvtiskii . 2018 . Competitive caching with machine learned advice . In Proceedings of the 35th International Conference on Machine Learning (Proceedings of Machine Learning Research). PMLR, 3296\u20133305 . Thodoris Lykouris and Sergei Vassilvtiskii. 2018. Competitive caching with machine learned advice. In Proceedings of the 35th International Conference on Machine Learning (Proceedings of Machine Learning Research). PMLR, 3296\u20133305."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2071379.2071381"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/3294771.3294948"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095250"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/3326943.3326986"},{"key":"e_1_2_2_37_1","volume-title":"Queues with small advice. CoRR abs\/2006.15463","author":"Mitzenmacher Michael","year":"2020","unstructured":"Michael Mitzenmacher . 2020. Queues with small advice. CoRR abs\/2006.15463 ( 2020 ). arxiv:2006.15463https:\/\/arxiv.org\/abs\/2006.15463. Michael Mitzenmacher. 2020. Queues with small advice. CoRR abs\/2006.15463 (2020). arxiv:2006.15463https:\/\/arxiv.org\/abs\/2006.15463."},{"key":"e_1_2_2_38_1","volume-title":"Proceedings of the 29th Conference on Learning Theory, COLT 2016","author":"Morgenstern Jamie","year":"2016","unstructured":"Jamie Morgenstern and Tim Roughgarden . 2016 . Learning simple auctions . In Proceedings of the 29th Conference on Learning Theory, COLT 2016 , New York, USA , June 23-26, 2016. 1298\u20131318. http:\/\/jmlr.org\/proceedings\/papers\/v49\/morgenstern16.html. Jamie Morgenstern and Tim Roughgarden. 2016. Learning simple auctions. In Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016. 1298\u20131318. http:\/\/jmlr.org\/proceedings\/papers\/v49\/morgenstern16.html."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/211390"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/3327546.3327635"},{"key":"e_1_2_2_41_1","volume-title":"Proceedings of the 26th Annual Conference on Learning Theory (COLT).","author":"Rakhlin Alexander","year":"2013","unstructured":"Alexander Rakhlin and Karthik Sridharan . 2013 . Online learning with predictable sequences . In Proceedings of the 26th Annual Conference on Learning Theory (COLT). Alexander Rakhlin and Karthik Sridharan. 2013. Online learning with predictable sequences. In Proceedings of the 26th Annual Conference on Learning Theory (COLT)."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/3381089.3381201"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/2969442.2969519"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3404835.3462793"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"e_1_2_2_46_1","volume-title":"International Conference on Learning Representations. http:\/\/arxiv.org\/abs\/1312","author":"Szegedy Christian","year":"2014","unstructured":"Christian Szegedy , Wojciech Zaremba , Ilya Sutskever , Joan Bruna , Dumitru Erhan , Ian Goodfellow , and Rob Fergus . 2014 . Intriguing properties of neural networks . In International Conference on Learning Representations. http:\/\/arxiv.org\/abs\/1312 .6199. Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. 2014. Intriguing properties of neural networks. In International Conference on Learning Representations. http:\/\/arxiv.org\/abs\/1312.6199."},{"key":"e_1_2_2_47_1","volume-title":"Partitioned learned bloom filter. CoRR abs\/2006.03176","author":"Vaidya Kapil","year":"2020","unstructured":"Kapil Vaidya , Eric Knorr , Tim Kraska , and Michael Mitzenmacher . 2020. Partitioned learned bloom filter. CoRR abs\/2006.03176 ( 2020 ). arxiv:2006.03176 https:\/\/arxiv.org\/abs\/2006.03176. Kapil Vaidya, Eric Knorr, Tim Kraska, and Michael Mitzenmacher. 2020. Partitioned learned bloom filter. CoRR abs\/2006.03176 (2020). arxiv:2006.03176 https:\/\/arxiv.org\/abs\/2006.03176."},{"key":"e_1_2_2_48_1","volume-title":"International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX).","author":"Wei Alexander","year":"2020","unstructured":"Alexander Wei . 2020 . Better and simpler learning-augmented online caching . In International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). Alexander Wei. 2020. Better and simpler learning-augmented online caching. In International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447579","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3447579","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3447579","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:28:37Z","timestamp":1750181317000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447579"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,14]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["10.1145\/3447579"],"URL":"https:\/\/doi.org\/10.1145\/3447579","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,14]]},"assertion":[{"value":"2019-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}