- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies the distributional search problem on trees. In this problem, there is a hidden target vertex that is drawn from an unknown distribution . The task is to find the target vertex by executing a minimum number of queries. A query of an vertex reveals whether and, if not, it reveals the unique neighbour of which is on the path from to . In the setting with distributional predictions, the algorithm is given a predicated distribution . Goal is to obtain an improved query complexity when is "close" to (consistency) that smoothly degrades as and diverge, while still maintaining a worst-case guarantee. The settings where or where is a point distribution (a single vertex has predicted probability mass of one) have already been studied. This paper combines and generalises these results to obtain an algorithm with a query complexity of where is the entropy of , is the earth mover distance between and , and is the path width of the tree. The authors complement this result with an asymptotically tight lower bound, which is an implication of a classical lower bound by Mehlhorn, 1975 and by the lower bound for point predictions by Dinitz and Dong, 2026. The main result is the algorithmic upper bound. It combines the algorithm by Dinitz and Dong for point predictions with the approach by Berendsohn et al, 2023 for a known distribution. The main technical contribution is a compression technique which reduces the number of relevant boundary vertices to a constant, which then allows running the point prediction algorithm on these boundary vertices.
Critical strengths
- A main strength of this paper is the model: distributional predictions are very well motivated by most ML methods. Yet, most papers on learning-augmented algorithms only study non-distributional predictions. This paper did not come up with the model, but extending the study of distributional predictions to more problems is a good contribution.
- The paper obtains asymptotically tight bounds to a problem, which generalises existing results on binary search with distributional predictions and on tree search with point predictions.
Critical weaknesses
- The technical contribution seems somewhat limited, as the paper is a combination of known ideas. The combination takes some technical work, but I'm not sure if there are any novel technical ideas.
Questions for authors
- What would you say is the main new technical idea of your algorithm?
2 comments
Thank you to the authors for the response and clarifications. I will maintain my overall positive score.
We thank the reviewer for their thoughtful review and for recognizing the motivation of distributional predictions and the tightness of our bounds. We agree that our algorithm builds on the interlacing framework and the existing point-prediction algorithm. Our main technical contribution is the boundary-compression technique.
The obstacle is that, on a path, the remaining feasible region has at most two boundary vertices, whereas on a tree it can have many. Directly running point-prediction search from every boundary vertex would therefore introduce an overhead that our bound cannot afford. Our compression procedure uses O(log∣A∣) queries to either find the target or reduce a boundary set A to at most two candidate anchors. Crucially, at least one resulting anchor is no farther from the target than the closest original boundary vertex.
We also explored other approaches, including applying distributional binary search along the spine or complicatedly interlacing weighted-median search with distributional binary search. In our attempts, these approaches introduced additional losses in either the EMD or the entropy term, and we were unable to obtain the same tight bound. These difficulties motivated the boundary-compression technique, which allows us to achieve the stated dependence on both quantities.