Robust Learning-Augmented Dictionaries
This work addresses the need for robust data structures in machine learning applications, offering a novel solution that combines optimal consistency and robustness, though it builds incrementally on prior learning-augmented approaches.
The paper tackles the problem of designing learning-augmented dictionaries with optimal consistency and robustness, resulting in a data structure (RobustSL) that achieves static optimality with proper predictions and maintains logarithmic running time even under adversarial predictions, outperforming alternatives in experiments.
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.