Robust Learning-Augmented Dictionaries

Ali Zeynali, Shahin Kamali, Mohammad Hajiesmaili
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:58470-58483, 2024.

Abstract

We present the first learning-augmented data structure for implementing dictionaries with optimal consistency and robustness. Our data structure, named RobustSL, is a Skip list augmented by predictions of access frequencies of elements in a data sequence. With proper predictions, RobustSL has optimal consistency (achieves static optimality). At the same time, it maintains a logarithmic running time for each operation, ensuring optimal robustness, even if predictions are generated adversarially. Therefore, RobustSL has all the advantages of the recent learning-augmented data structures of Lin, Luo, and Woodruff (ICML 2022) and Cao et al. (arXiv 2023), while providing robustness guarantees that are absent in the previous work. Numerical experiments show that RobustSL outperforms alternative data structures using both synthetic and real datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-zeynali24a, title = {Robust Learning-Augmented Dictionaries}, author = {Zeynali, Ali and Kamali, Shahin and Hajiesmaili, Mohammad}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {58470--58483}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/zeynali24a/zeynali24a.pdf}, url = {https://proceedings.mlr.press/v235/zeynali24a.html}, abstract = {We present the first learning-augmented data structure for implementing dictionaries with optimal consistency and robustness. Our data structure, named RobustSL, is a Skip list augmented by predictions of access frequencies of elements in a data sequence. With proper predictions, RobustSL has optimal consistency (achieves static optimality). At the same time, it maintains a logarithmic running time for each operation, ensuring optimal robustness, even if predictions are generated adversarially. Therefore, RobustSL has all the advantages of the recent learning-augmented data structures of Lin, Luo, and Woodruff (ICML 2022) and Cao et al. (arXiv 2023), while providing robustness guarantees that are absent in the previous work. Numerical experiments show that RobustSL outperforms alternative data structures using both synthetic and real datasets.} }
Endnote
%0 Conference Paper %T Robust Learning-Augmented Dictionaries %A Ali Zeynali %A Shahin Kamali %A Mohammad Hajiesmaili %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-zeynali24a %I PMLR %P 58470--58483 %U https://proceedings.mlr.press/v235/zeynali24a.html %V 235 %X We present the first learning-augmented data structure for implementing dictionaries with optimal consistency and robustness. Our data structure, named RobustSL, is a Skip list augmented by predictions of access frequencies of elements in a data sequence. With proper predictions, RobustSL has optimal consistency (achieves static optimality). At the same time, it maintains a logarithmic running time for each operation, ensuring optimal robustness, even if predictions are generated adversarially. Therefore, RobustSL has all the advantages of the recent learning-augmented data structures of Lin, Luo, and Woodruff (ICML 2022) and Cao et al. (arXiv 2023), while providing robustness guarantees that are absent in the previous work. Numerical experiments show that RobustSL outperforms alternative data structures using both synthetic and real datasets.
APA
Zeynali, A., Kamali, S. & Hajiesmaili, M.. (2024). Robust Learning-Augmented Dictionaries. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:58470-58483 Available from https://proceedings.mlr.press/v235/zeynali24a.html.

Related Material