Bisection Search with Noisy Responses
Bisection Search with Noisy Responses
复制标题
带有噪声响应的二分搜索
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
S. Henderson
中科院分区：
文献类型：
--
作者：
Rolf Waeber;P. Frazier;S. Henderson
当我们只能查询到X∗在我们选择的点X的左边还是右边时，二分搜索是定位唯一点X∗∈(0,1)的最有效的算法。我们研究了这个经典问题的噪声版本，其中oracle的响应仅在概率p下是正确的。通知。Theory, 9 (1963), pp. 136-143)可以用来在这种情况下定位X *。虽然这种方法在实践中非常有效，但人们对其理论性质知之甚少。在本文中，我们提供了关于PBA的几个关键发现，这些发现导致了连续搜索结果的期望绝对残差，即E（|X *−Xn|）以几何速率收敛于0的主要结论。
Bisection search is the most efficient algorithm for locating a unique point X ∗ ∈ (0, 1) when we are able to query an oracle only about whether X ∗ 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 ∗ 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., E(|X ∗ − Xn|), converge to 0 at a geometric rate.