arXiv preprint ·
Tree Search With Distributional Predictions
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Learning-augmented algorithms use machine-learned predictions to improve classical algorithmic guarantees when the predictions are accurate, while retaining rigorous performance guarantees when they are not. We study this paradigm for search on trees. Given a tree $T$ containing an unknown target vertex $t$, an algorithm may query any vertex $v$ and learn which neighbor of $v$ lies on the unique path from $v$ to $t$. The goal is to find $t$ using as few queries as possible. We consider the distributional setting, in which the target is drawn from an unknown distribution $p$ and the algorithm is given a predicted distribution $\widehat p$ of unknown quality. We give an algorithm with expected query complexity $O\left(H(p)+k\log η\right)$, where $H(p)$ is the Shannon entropy of the true distribution and $η$ is the earth mover's distance between $p$ and $\widehat p$ in the tree metric. We also provide a matching lower bound that shows our algorithm is asymptotically tight. Finally, experiments on real-world and synthetic trees show that our prediction-based algorithm can use substantially fewer queries than a simple baseline that trusts the prediction completely.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Efficient Support Recovery of Mixtures of Sparse Linear Classifiers with Less Measurements
On Diverse Solutions to Max-k-CSP and Bounded Degree k-SAT
On the Guo-Fang-Lu Algorithm for Komlos Discrepancy
Single-or-Sample: Online Fair Allocation for Combinatorial Agents
On the Complexity of Forcing and Anti-Forcing Minimum Cuts
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.