Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912708282023936 |
|---|---|
| author | Chen, Peng Zhao, Hailiang Zhang, Jiaji Tang, Xueyan Wang, Yixuan Deng, Shuiguang |
| author_facet | Chen, Peng Zhao, Hailiang Zhang, Jiaji Tang, Xueyan Wang, Yixuan Deng, Shuiguang |
| contents | The online caching problem aims to minimize cache misses when serving a sequence of requests under a limited cache size. While naive learning-augmented caching algorithms achieve ideal $1$-consistency, they lack robustness guarantees. Existing robustification methods either sacrifice $1$-consistency or introduce excessive computational overhead. In this paper, we introduce Guard, a lightweight robustification framework that enhances the robustness of a broad class of learning-augmented caching algorithms to $2H_{k-1} + 2$, while preserving their $1$-consistency. Guard achieves the current best-known trade-off between consistency and robustness, with only O(1) additional per-request overhead, thereby maintaining the original time complexity of the base algorithm. Extensive experiments across multiple real-world datasets and prediction models validate the effectiveness of Guard in practice. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_16242 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency Chen, Peng Zhao, Hailiang Zhang, Jiaji Tang, Xueyan Wang, Yixuan Deng, Shuiguang Data Structures and Algorithms Machine Learning The online caching problem aims to minimize cache misses when serving a sequence of requests under a limited cache size. While naive learning-augmented caching algorithms achieve ideal $1$-consistency, they lack robustness guarantees. Existing robustification methods either sacrifice $1$-consistency or introduce excessive computational overhead. In this paper, we introduce Guard, a lightweight robustification framework that enhances the robustness of a broad class of learning-augmented caching algorithms to $2H_{k-1} + 2$, while preserving their $1$-consistency. Guard achieves the current best-known trade-off between consistency and robustness, with only O(1) additional per-request overhead, thereby maintaining the original time complexity of the base algorithm. Extensive experiments across multiple real-world datasets and prediction models validate the effectiveness of Guard in practice. |
| title | Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2507.16242 |