{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T18:27:34Z","timestamp":1780338454961,"version":"3.54.1"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2026,3,26]]},"abstract":"<jats:p>\n                    <jats:italic toggle=\"yes\">Algorithms with predictions<\/jats:italic>\n                    have emerged as a powerful framework to combine the robustness of traditional online algorithms with the data-driven performance benefits of machine-learned (ML) predictions. However, most existing approaches in this paradigm are overly conservative, as they do not leverage problem structure to optimize performance in a prediction-specific manner. In this paper, we show that such prediction-specific performance criteria can enable significant performance improvements over the coarser notions of consistency and robustness considered in prior work. Specifically, we propose a notion of\n                    <jats:italic toggle=\"yes\">strongly-optimal<\/jats:italic>\n                    algorithms with predictions, which obtain Pareto optimality not just in the worst-case tradeoff between robustness and consistency, but also in the prediction-specific tradeoff between these metrics. We develop a general bi-level optimization framework that enables systematically designing strongly-optimal algorithms in a wide variety of problem settings, and we propose explicit strongly-optimal algorithms for several classic online problems: deterministic and randomized ski rental, and one-max search. Our analysis reveals new structural insights into how predictions can be optimally integrated into online algorithms by leveraging a prediction-specific design. To validate the benefits of our proposed framework, we empirically evaluate our algorithms in case studies on problems including dynamic power management and volatility-based index trading. Our results demonstrate that prediction-specific, strongly-optimal algorithms can significantly improve performance across a variety of online decision-making settings.\n                  <\/jats:p>","DOI":"10.1145\/3788100","type":"journal-article","created":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T18:49:47Z","timestamp":1774550987000},"page":"1-57","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Prediction-Specific Design of Learning-Augmented Algorithms"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-6596-7749","authenticated-orcid":false,"given":"Sizhe","family":"Li","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8330-8964","authenticated-orcid":false,"given":"Nicolas","family":"Christianson","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9806-8964","authenticated-orcid":false,"given":"Tongxin","family":"Li","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,3,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591971.2591984"},{"key":"e_1_2_1_2_1","volume-title":"Proc. 37th Int'l Conf. Mach. Learn. (ICML). PMLR, 345-355","author":"Antoniadis Antonios","year":"2020","unstructured":"Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Berthold Simon. 2020a. Online Metric Algorithms with Untrusted Predictions. In Proc. 37th Int'l Conf. Mach. Learn. (ICML). PMLR, 345-355."},{"key":"e_1_2_1_3_1","volume-title":"Advances in Neural Information Processing Systems (NeurIPS","author":"Antoniadis Antonios","year":"2021","unstructured":"Antonios Antoniadis, Christian Coester, Marek Eli\u00e1\u0161, Adam Polak, and Bertrand Simon. 2021. Learning-augmented dynamic power management with multiple states via new ski rental bounds. In Advances in Neural Information Processing Systems (NeurIPS 2021). https:\/\/proceedings.neurips.cc\/paper\/2021\/hash\/8b8388180314a337c9aa3c5aa8e2f37a-Abstract.html"},{"key":"e_1_2_1_4_1","volume-title":"Advances in Neural Information Processing Systems 33 (NeurIPS","author":"Antoniadis Antonios","year":"2020","unstructured":"Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. 2020b. Secretary and Online Matching Problems with Machine Learned Advice. In Advances in Neural Information Processing Systems 33 (NeurIPS 2020). https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/5a378f8490c8d6af8647a753812f6e31-Abstract.html"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 2025 International Conference on Machine Learning (ICML 2025","author":"Benomar Ziyad","year":"2025","unstructured":"Ziyad Benomar, Lorenzo Croissant, Vianney Perchet, and Spyros Angelopoulos. 2025. Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search. In Proceedings of the 2025 International Conference on Machine Learning (ICML 2025). https:\/\/icml.cc\/virtual\/2025\/poster\/44853 Poster."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 28th International Conference on Artificial Intelligence and Statistics. PMLR, 802-810","author":"Benomar Ziyad","year":"2025","unstructured":"Ziyad Benomar and Vianney Perchet. 2025. On Tradeoffs in Learning-Augmented Algorithms. In Proceedings of the 28th International Conference on Artificial Intelligence and Statistics. PMLR, 802-810. https:\/\/proceedings.mlr.press\/v258\/benomar25a.html"},{"key":"e_1_2_1_7_1","volume-title":"Online Computation and Competitive Analysis","author":"Borodin Allan","unstructured":"Allan Borodin and Ran El-Yaniv. 2005. Online Computation and Competitive Analysis. Cambridge University Press. https:\/\/books.google.com\/books\/about\/Online_Computation_and_Competitive_Analy.html?id=v3faI8pER6IC"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 2021 Symposium on Discrete Algorithms (SODA). 1-40","author":"Bubeck S\u00e9bastien","year":"2021","unstructured":"S\u00e9bastien Bubeck, Yassine Engel, Yin Tat Lee, Yifeng Li, and Aleksandar Nikolov. 2021. Online Multiserver Convex Chasing and Optimization. In Proceedings of the 2021 Symposium on Discrete Algorithms (SODA). 1-40. https:\/\/dl.acm.org\/doi\/10.5555\/3458064.3458189"},{"key":"e_1_2_1_9_1","first-page":"867","volume-title":"Proceedings of the Conference on Learning Theory","volume":"178","author":"Christianson Nicolas","year":"2022","unstructured":"Nicolas Christianson, Tinashe Handina, and Adam Wierman. 2022. Chasing convex bodies and functions with black-box advice. In Proceedings of the Conference on Learning Theory, Vol. 178. PMLR, 867-908. https:\/\/proceedings.mlr.press\/v178\/christianson22a.html"},{"key":"e_1_2_1_10_1","first-page":"4223","volume-title":"Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS)","volume":"206","author":"Christianson Nicolas","year":"2023","unstructured":"Nicolas Christianson, Junxuan Shen, and Adam Wierman. 2023. Optimal Robustness-Consistency Tradeoffs for Learning-Augmented Metrical Task Systems. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS), Vol. 206. PMLR, 4223-4254. https:\/\/proceedings.mlr.press\/v206\/christianson23a.html"},{"key":"e_1_2_1_11_1","volume-title":"Risk-Sensitive Online Algorithms. In The Thirty Seventh Annual Conference on Learning Theory. PMLR, 1140-1141","author":"Christianson Nicolas","year":"2024","unstructured":"Nicolas Christianson, Bo Sun, Steven Low, and Adam Wierman. 2024. Risk-Sensitive Online Algorithms. In The Thirty Seventh Annual Conference on Learning Theory. PMLR, 1140-1141."},{"key":"e_1_2_1_12_1","volume-title":"Competitive Algorithms for Online Knapsack with Succinct Predictions. arXiv preprint arXiv:2406.18752","author":"Daneshvaramoli Mohammadreza","year":"2024","unstructured":"Mohammadreza Daneshvaramoli, Helia Karisani, Adam Lechowicz, Bo Sun, Cameron Musco, and Mohammad Hajiesmaili. 2024. Competitive Algorithms for Online Knapsack with Succinct Predictions. arXiv preprint arXiv:2406.18752 (2024). https:\/\/arxiv.org\/abs\/2406.18752"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.147"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0003-0"},{"key":"e_1_2_1_15_1","volume-title":"Advances in Neural Information Processing Systems (NeurIPS","author":"Elenter Alex","year":"2024","unstructured":"Alex Elenter, Spyros Angelopoulos, Christoph D\u00fcrr, and Yanni Lefki. 2024. Overcoming Brittleness in Pareto-Optimal Learning Augmented Algorithms. In Advances in Neural Information Processing Systems (NeurIPS 2024). https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2024\/hash\/11c6625b0481a7d5625831369f6b7c82-Abstract-Conference.html"},{"key":"e_1_2_1_16_1","first-page":"4548","volume-title":"Proceedings of the Thirty-Fifth Conference on Learning Theory","volume":"178","author":"Golowich Noah","year":"2022","unstructured":"Noah Golowich and Ankur Moitra. 2022. Can Q-learning be Improved with Advice?. In Proceedings of the Thirty-Fifth Conference on Learning Theory, Vol. 178. PMLR, 4548-4619. https:\/\/proceedings.mlr.press\/v178\/golowich22a.html"},{"key":"e_1_2_1_17_1","first-page":"9588","volume-title":"Proceedings of the 39th International Conference on Machine Learning","volume":"162","author":"Im Sungjin","year":"2022","unstructured":"Sungjin Im, Ravi Kumar, Aditya Petety, and Manish Purohit. 2022. Parsimonious Learning-Augmented Caching. In Proceedings of the 39th International Conference on Machine Learning, Vol. 162. PMLR, 9588-9601. https:\/\/proceedings.mlr.press\/v162\/im22a.html"},{"key":"e_1_2_1_18_1","volume-title":"Mahshid Montazer Qaem, and Manish Purohit","author":"Im Sungjin","year":"2021","unstructured":"Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. 2021. Online Knapsack with Frequency Predictions. In Advances in Neural Information Processing Systems 34 (NeurIPS 2021). 161c5c5ad51fcc884157890511b3c8b0. https:\/\/proceedings.neurips.cc\/paper\/2021\/hash\/161c5c5ad51fcc884157890511b3c8b0-Abstract.html"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/860176.860180"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380845"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762111"},{"key":"e_1_2_1_22_1","volume-title":"Advances in Neural Information Processing Systems 35 (NeurIPS","author":"Khodak Mikhail","year":"2022","unstructured":"Mikhail Khodak, Maria-Florina Balcan, Ameet Talwalkar, and Sergei Vassilvitskii. 2022. Learning Predictions for Algorithms with Predictions. In Advances in Neural Information Processing Systems 35 (NeurIPS 2022). https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2022\/file\/17061a94c3c7fda5fa24bbdd1832fa99-Paper-Conference.pdf"},{"key":"e_1_2_1_23_1","volume-title":"Advances in Neural Information Processing Systems 31 (NeurIPS","author":"Kumar Ravi","year":"2018","unstructured":"Ravi Kumar, Manish Purohit, and Zoya Svitkina. 2018. Improving Online Algorithms via ML Predictions. In Advances in Neural Information Processing Systems 31 (NeurIPS 2018). 1-10. https:\/\/papers.nips.cc\/paper\/8174-improving-online-algorithms-via-ml-predictions"},{"key":"e_1_2_1_24_1","first-page":"26259","volume-title":"Proceedings of the 41st International Conference on Machine Learning","volume":"235","author":"Lechowicz Adam","year":"2024","unstructured":"Adam Lechowicz, Nicolas Christianson, Bo Sun, Noman Bashir, Mohammad Hajiesmaili, Adam Wierman, and Prashant Shenoy. 2024a. Chasing Convex Functions with Long-term Constraints. In Proceedings of the 41st International Conference on Machine Learning, Vol. 235. PMLR, 26259-26289. https:\/\/proceedings.mlr.press\/v235\/lechowicz24a.html"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3652963.3655074"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3711701"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626776"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the International Conference on Learning Representations (ICLR","author":"Lechowicz Adam","year":"2024","unstructured":"Adam Lechowicz, Rik Sengupta, Bo Sun, Shahin Kamali, and Mohammad Hajiesmaili. 2024c. Time Fairness in Online Knapsack Problems. In Proceedings of the International Conference on Learning Representations (ICLR 2024). https:\/\/openreview.net\/forum?id=9kG7TwgLYu"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447555.3464860"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3632775.3639590"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3726854.3727293"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 37th Conference on Neural Information Processing Systems (NeurIPS 2023","author":"Li Tongxin","year":"2023","unstructured":"Tongxin Li, Yiheng Lin, Shaolei Ren, and Adam Wierman. 2023. Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictions. In Proceedings of the 37th Conference on Neural Information Processing Systems (NeurIPS 2023). https:\/\/proceedings.neurips.cc\/paper\/2023\/file\/8e806d3c56ed5f1dab85d601e13cbe38-Paper-Conference.pdf"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 37th Annual Conference on Neural Information Processing Systems (NeurIPS 2024","author":"Li Tongxin","year":"2024","unstructured":"Tongxin Li, Hao Liu, and Yisong Yue. 2024. Disentangling Linear Quadratic Control with Untrusted ML Predictions. In Proceedings of the 37th Annual Conference on Neural Information Processing Systems (NeurIPS 2024). 86860-86898. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2024\/hash\/9dff3b83d463fab213941bfee23341ba-Abstract-Conference.html"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3547353.3522658"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3508038"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447579"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2071379.2071381"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the ACM SIGCOMM 2019 Conference. ACM. https:\/\/dl.acm.org\/doi\/10","author":"Mao Hongzi","year":"2019","unstructured":"Hongzi Mao, Malte Schwarzkopf, Shaileshh Bojja Venkatakrishnan, Zili Meng, and Mohammad Alizadeh. 2019. Learning Scheduling Algorithms for Data Processing Clusters. In Proceedings of the ACM SIGCOMM 2019 Conference. ACM. https:\/\/dl.acm.org\/doi\/10.1145\/3341302.3342080"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90151-1"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/3381089.3381201"},{"key":"e_1_2_1_41_1","first-page":"1","volume-title":"Proceedings of the IEEE Conference on Computer Communications (INFOCOM 2018","author":"Shi Ming","year":"2018","unstructured":"Ming Shi, Xiaojun Lin, Sonia Fahmy, and Dong-Hoon Shin. 2018. Competitive Online Convex Optimization with Switching Costs and Ramp Constraints. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM 2018). IEEE, 1-9. https:\/\/www.cs.purdue.edu\/homes\/fahmy\/papers\/infocom2018.pdf"},{"key":"e_1_2_1_42_1","first-page":"47056","volume-title":"Proceedings of the 41st International Conference on Machine Learning (ICML","volume":"235","author":"Sun Bo","year":"2024","unstructured":"Bo Sun, Jerry Huang, Nicolas Christianson, Mohammad Hajiesmaili, Adam Wierman, and Raouf Boutaba. 2024. Online Algorithms with Uncertainty-Quantified Predictions. In Proceedings of the 41st International Conference on Machine Learning (ICML 2024), Vol. 235. PMLR, 47056-47077. https:\/\/proceedings.mlr.press\/v235\/sun24f.html"},{"key":"e_1_2_1_43_1","volume-title":"Tsang","author":"Sun Bo","year":"2021","unstructured":"Bo Sun, Russell Lee, Mohammad Hajiesmaili, Adam Wierman, and Danny H.K. Tsang. 2021a. Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems. In Advances in Neural Information Processing Systems 34 (NeurIPS 2021). 55a988dfb00a914717b3000a3374694c. https:\/\/proceedings.neurips.cc\/paper\/2021\/file\/55a988dfb00a914717b3000a3374694c-Paper.pdf"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3543516.3456271"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2020.60"},{"key":"e_1_2_1_46_1","volume-title":"Advances in Neural Information Processing Systems 33 (NeurIPS","author":"Wei Alexander","year":"2020","unstructured":"Alexander Wei and Fred Zhang. 2020. Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms. In Advances in Neural Information Processing Systems 33 (NeurIPS 2020). 21219-21229. https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/5bd844f11fa520d54fa5edec06ea2507-Abstract.html"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence (AAAI","volume":"35","author":"Zeynali Ali","year":"2021","unstructured":"Ali Zeynali, Bo Sun, Mohammad Hajiesmaili, and Adam Wierman. 2021. Data-Driven Competitive Algorithms for Online Knapsack and Set Cover. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI 2021), Vol. 35. 10821-10829. https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/17133"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2015.8"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3788100","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T18:50:57Z","timestamp":1774551057000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3788100"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,26]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,26]]}},"alternative-id":["10.1145\/3788100"],"URL":"https:\/\/doi.org\/10.1145\/3788100","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,26]]},"assertion":[{"value":"2026-03-26","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}