Research map / Learning theory and algorithms / Prediction and decision losses
Binary Search with Distributional Predictions
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.
Studies binary search when the prediction is a distribution rather than a point, proposing an algorithm interleaving median bisection with endpoint binary search that achieves O(H(p) + log η) query complexity, matched by a lower bound.
Problem
Binary search (searching a sorted array / optimal BST) with a distributional prediction of the key-location distribution, where the prediction may be erroneous; prior algorithms-with-predictions work assumes point predictions.
Approach
Interleave median-based bisection on the predicted distribution (which is optimal when the prediction is correct) with doubling-width endpoint binary-search probes (which guard against errors), yielding query complexity O(H(p)+log EMD) measured via earth mover's distance, and show a matching lower bound.
Key results
- Learned BST achieves O(H(p)+log η) expected query complexity, with a matching Ω(H(p)+log η) worst-case lower bound up to constants.
- On AskUbuntu and SuperUser, Learned BST saves about 20-25% comparisons on average versus baselines.
- On StackOverflow, Learned BST is about 10% worse than the Bisection method, but never worse than Classic on the other datasets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Learned BST instead of the baselines | Binary search · AskUbuntu and SuperUser | comparisons: saving 20-25\% comparisons on average | Helped |
| Use Learned BST instead of Bisection | Binary search · StackOverflow | comparisons: about 10\% worse than bisection method | Hurt |
| Use Learned BST rather than Classic | Binary search · AskUbuntu and SuperUser | comparisons | Helped |
| Use Learned BST rather than Bisection | Binary search · Synthetic data with increasing test-distribution shift | average search cost | Mixed |
| Increase the shift between training and test distributions | Bisection · Synthetic data | average search cost | Hurt |
| Use the convex-combination distribution instead of the predicted distribution directly | Bisection · Real-world datasets | average search cost | No clear effect |
| Increase the training-data fraction | Distribution-dependent search algorithms · AskUbuntu, SuperUser, and StackOverflow | average search cost | Helped |
| Increase distribution error (EMD) | Learned BST · Real-world datasets | average search cost | Hurt |
Surprising findings
- Converting the distributional prediction to any single point prediction and running the doubling binary search with it can incur Ω(log n) cost even when the prediction is perfect and H(p)=1.
- The Bisection (median) algorithm can be made to use Ω(n) comparisons when the prediction is wrong, performing worse than classic binary search under small shifts.
Limitations
- Constant factors are large; the learned approach is not competitive with other learned approaches in practice on real data.
- Bisection-based design only handles comparison-based search; the extension to multiple predictions incurs a log m overhead.
- Real-data experiments use temporal network sequences rather than an ML model's predictions.
Experimental setup
Datasets: SNAP temporal network StackOverflow answers-to-questions SNAP AskUbuntu answers-to-questions SNAP SuperUser answers-to-questions synthetic normal-distributed keys
Benchmarks: synthetic shifted-normal search AskUbuntu SuperUser StackOverflow
Metrics: expected number of comparisons (query complexity) log EMD sensitivity
Baselines: Classic binary search Bisection (median) algorithm Convex Combination heuristic
Builds on: doubling binary search with predictions median/bisection search algorithm Yao's principle
Closest papers by meaning
- On the Power of Learning-Augmented Search Trees (ICML 2025 · similarity 0.84)
- Learning-Augmented Search Data Structures (ICLR 2025 · similarity 0.84)
- Optimal Algorithms for Augmented Testing of Discrete Distributions (NeurIPS 2024 · similarity 0.83)
- Learnability of Parameter-Bounded Bayes Nets (AAAI 2025 · similarity 0.83)
- Derandomizing Multi-Distribution Learning (NeurIPS 2024 · similarity 0.83)
- Scenario-Based Robust Optimization of Tree Structures (AAAI 2025 · similarity 0.83)
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.