Bisection Search with Noisy Responses
Authors:
- Rolf WaeberRWRolf Waeber
- Peter I. FrazierPFPeter I. Frazier
- Shane G. HendersonSHShane G. Henderson
- 1 January 2013
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Control and Optimization
- Vol. 51 (3) , 2261-2279
Abstract
Bisection search is the most efficient algorithm for locating a unique point $X^{\ast} \in [0,1]$ when we are able to query an oracle only about whether $X^{\ast}$ lies to the left or right of a point $x$ of our choosing. We study a noisy version of this classic problem, where the oracle's response is correct only with probability $p$. The probabilistic bisection algorithm (PBA) introduced by Horstein [IEEE Trans. Inform. Theory, 9 (1963), pp. 136--143] can be used to locate $X^{\ast}$ in this setting. While the method works extremely well in practice, very little is known about its theoretical properties. In this paper, we provide several key findings about the PBA, which lead to the main conclusion that the expected absolute residuals of successive search results, i.e., $\mathbb{E}[|X^{\ast} - X_n|]$, converge to 0 at a geometric rate.
Keywords
This publication has 9 references indexed in Scilit:
- Twenty Questions with Noise: Bayes Optimal Policies for Entropy LossJournal of Applied Probability, 2012
- Minimax Bounds for Active LearningIEEE Transactions on Information Theory, 2008
- A Knowledge-Gradient Policy for Sequential Information CollectionSIAM Journal on Control and Optimization, 2008
- Computing with Noisy InformationSIAM Journal on Computing, 1994
- Searching with known error probabilityTheoretical Computer Science, 1989
- Coping with errors in binary search proceduresJournal of Computer and System Sciences, 1980
- Location of the Maximum on Unimodal SurfacesJournal of the ACM, 1965
- Sequential transmission using noiseless feedbackIEEE Transactions on Information Theory, 1963
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963