aiqbench analysis
This research closes the theoretical gap in learning-augmented paging by introducing a new framework that achieves the optimal competitive ratio of $H_k + O(1)$, addressing the limitations of prior algorithms that either overused or underutilized predictions. By formalizing the concept of a "relative prediction budget," the authors provide a unified primitive that ensures bounded robustness, guaranteeing worst-case performance even when ML predictions are inaccurate. The work bridges online algorithm theory and machine learning, offering a more reliable foundation for real-world systems that require guaranteed performance bounds alongside predictive capabilities.
Towards Optimal Robustness in Learning-Augmented Paging
arXiv:2606.01342v3 Announce Type: replace-cross Abstract: Learning-augmented paging has been extensively studied in recent years. A key advantage over naive ML-based approaches is \emph{bounded robustness}, which guarantees worst-case performance even when predictions are inaccurate, making these algorithms valuable for real-world systems. Prior work achieves robustness bounds of $2H_k + O(1)$ in the randomized setting, leaving a gap to the optimal competitive ratio $H_k$. In this paper, we study how to close this gap. We begin by reviewing online optimality and proving a new property of the latest $H_k$-competitive algorithm, which facilitates our analysis in the learning-augmented setting. Then, we review existing learning-augmented paging algorithms and introduce a unifying primitive, the \emph{relative prediction budget}, which captures the essence of establishing robustness and reveals that prior algorithms either overuse or underutilize predictions. Guided by the above analysis, we develop a new framework that achieves the best-possible robustness up to an additive constant for learning-augmented paging: $H_k + O(1)$. Experiments further demonstrate strong practical performance.
Abstract:Learning-augmented paging has been extensively studied in recent years. A key advantage over naive ML-based approaches is \emph{bounded robustness}, which guarantees worst-case performance even when predictions are inaccurate, making these algorithms valuable for real-world systems. Prior work achieves robustness bounds of $2H_k + O(1)$ in the randomized setting, leaving a gap to the optimal competitive ratio $H_k$. In this paper, we study how to close this gap. We begin by reviewing online optimality and proving a new property of the latest $H_k$-competitive algorithm, which facilitates our analysis in the learning-augmented setting. Then, we review existing learning-augmented paging algorithms and introduce a unifying primitive, the \emph{relative prediction budget}, which captures the essence of establishing robustness and reveals that prior algorithms either overuse or underutilize predictions. Guided by the above analysis, we develop a new framework that achieves the best-possible robustness up to an additive constant for learning-augmented paging: $H_k + O(1)$. Experiments further demonstrate strong practical performance.
Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG)
arXiv:2606.01342 [cs.DS]
(or arXiv:2606.01342v3 [cs.DS] for this version)
Full text under the publisher's open licence · 172 words