Research map / Bandits and online learning / Online convex optimization and games
Robust Learning-Augmented Dictionaries
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes RobustSL, a skip list built by combining an optimistic prediction-based BST (learned treap) with a pessimistic balanced BST, achieving static optimality under accurate predictions and O(log n) per operation under adversarial predictions.
Problem
Learning-augmented dictionary data structures that are simultaneously statically optimal (consistent) under accurate frequency predictions and logarithmic (robust) under adversarial predictions; prior learned treaps lose robustness.
Approach
Merge an optimistic BST (learned treap trusting frequency predictions) and a pessimistic balanced BST (AVL tree) into one skip list by taking the union of their levels, so each access costs at most twice the cheaper of the two trees, with a dynamic variant that updates replica counts on insert/delete.
Key results
- On synthetic data with n=1000 under random ordering, RobustSL uses about 1.2x more comparisons per query than learned treaps in static tests, while being 3.6x lower than learned treaps under adversarial ordering.
- Theorem: RobustSL search cost is at most 2 times the minimum of the two component trees' search costs per key.
- Learned treaps' cost degrades linearly as the adversarial dataset grows, while RobustSL stays steady.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RobustSL instead of learning-augmented treaps | Static dictionary · Synthetic data, random frequency ordering with perfect predictions | comparisons/query: 1.2× more | Hurt |
| Use RobustSL instead of learning-augmented treaps | Static dictionary · Synthetic data, adversarial frequency ordering with noisy predictions, dictionary size 1000 | comparisons/query: 3.6× lower | Helped |
| Use RobustSL instead of learning-augmented treaps | Dynamic dictionary · Synthetic data, random frequency ordering with perfect predictions | comparisons/query: 1.6× more | Hurt |
| Use RobustSL instead of learning-augmented treaps | Dynamic dictionary · Synthetic data, adversarial frequency ordering with noisy predictions, dictionary size 1000 | comparisons/query: 2.2× lower | Helped |
| Use RobustSL instead of Learned Treaps | Dictionary · BBC news articles, low prediction error | comparisons/query | Hurt |
| Use RobustSL instead of Learned Treaps | Dictionary · BBC news articles, fully adversarial predictions | comparisons/query | Helped |
| Add a pessimistic balanced tree to the prediction-based tree in the combined skip list | RobustSL · Dictionary searches with adversarial predictions | comparisons: O(m log n) | Helped |
| Use a prediction-based tree in the combined skip list | RobustSL · Dictionary searches with correct predictions | comparisons: O(m H(p)) | Helped |
Surprising findings
- Any learning-augmented treap with frequency-plus-random priorities has robustness n, suggesting treaps alone cannot achieve both properties.
Limitations
- Dynamic variant's amortized insertion/deletion cost left unresolved in the text (marked with placeholder)
- Dynamic-setting analysis includes unfinished or inconsistent claims and proofs
- Theoretical robustness bounds incur constant factor overhead (factor 2 or 3) relative to optimal trees
Experimental setup
Datasets: Synthetic Zipfian sequences (Zipf parameter 2, m=100,000) BBC news article dataset
Benchmarks: Synthetic Zipfian search sequences BBC news article dataset with adversarial additions
Metrics: average number of comparisons per query
Baselines: AVL Trees Red-Black Trees Splay Trees Balanced Binary Trees Learning-augmented Treaps
Builds on: Learning-augmented Treap (Lin, Luo, Woodruff 2022) Chen and Chen 2023 learned treap Skip list (Pugh) Splay trees AVL trees
Closest papers by meaning
- Learning-Augmented Search Data Structures (ICLR 2025 · similarity 0.84)
- Adversarial Robustness of Supervised Sparse Coding (NeurIPS 2020 · similarity 0.83)
- Boosting Barely Robust Learners: A New Perspective on Adversarial Robustness (NeurIPS 2022 · similarity 0.83)
- Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization (NeurIPS 2022 · similarity 0.83)
- Robust Sequence Submodular Maximization (NeurIPS 2020 · similarity 0.83)
- Overcoming Brittleness in Pareto-Optimal Learning Augmented Algorithms (NeurIPS 2024 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.