Noisy Search with Comparative Feedback

Shiau Hong Lim, Peter Auer
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:502-509, 2011.

Abstract

We present theoretical results in terms of lower and upper bounds on the query complexity of noisy search with comparative feedback. In this search model, the noise in the feedback depends on the distance between query points and the search target. Consequently, the error probability in the feedback is not fixed but varies for the queries posed by the search algorithm. Our results show that a target out of n items can be found in O(log n) queries. We also show the surprising result that for k possible answers per query, the speedup is not log k (as for k-ary search) but only log log k in some cases.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-lim11a, title = {Noisy Search with Comparative Feedback}, author = {Lim, Shiau Hong and Auer, Peter}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {502--509}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/lim11a/lim11a.pdf}, url = {https://proceedings.mlr.press/r9/lim11a.html}, abstract = {We present theoretical results in terms of lower and upper bounds on the query complexity of noisy search with comparative feedback. In this search model, the noise in the feedback depends on the distance between query points and the search target. Consequently, the error probability in the feedback is not fixed but varies for the queries posed by the search algorithm. Our results show that a target out of n items can be found in O(log n) queries. We also show the surprising result that for k possible answers per query, the speedup is not log k (as for k-ary search) but only log log k in some cases.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Noisy Search with Comparative Feedback %A Shiau Hong Lim %A Peter Auer %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-lim11a %I PMLR %P 502--509 %U https://proceedings.mlr.press/r9/lim11a.html %V R9 %X We present theoretical results in terms of lower and upper bounds on the query complexity of noisy search with comparative feedback. In this search model, the noise in the feedback depends on the distance between query points and the search target. Consequently, the error probability in the feedback is not fixed but varies for the queries posed by the search algorithm. Our results show that a target out of n items can be found in O(log n) queries. We also show the surprising result that for k possible answers per query, the speedup is not log k (as for k-ary search) but only log log k in some cases. %Z Reissued by PMLR on 04 October 2026.
APA
Lim, S.H. & Auer, P.. (2011). Noisy Search with Comparative Feedback. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:502-509 Available from https://proceedings.mlr.press/r9/lim11a.html. Reissued by PMLR on 04 October 2026.

Related Material