Journal
SIAM JOURNAL ON CONTROL AND OPTIMIZATION
Volume 51, Issue 3, Pages 2261-2279Publisher
SIAM PUBLICATIONS
DOI: 10.1137/120861898
Keywords
probabilistic bisection; noisy bisection; geometric rate of convergence; sequential analysis; Bayesian performance analysis
Categories
Funding
- Air Force Office of Scientific Research Young Investigator Program [FA9550-11-1-0083]
- National Science Foundation [CMMI-0800688, CMMI-1200315]
- Directorate For Engineering
- Div Of Civil, Mechanical, & Manufact Inn [1200315] Funding Source: National Science Foundation
- Div Of Civil, Mechanical, & Manufact Inn
- Directorate For Engineering [1254298] Funding Source: National Science Foundation
- Div Of Information & Intelligent Systems
- Direct For Computer & Info Scie & Enginr [1247696, 1247637] Funding Source: National Science Foundation
Ask authors/readers for more resources
Bisection search is the most efficient algorithm for locating a unique point X* is an element of [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[vertical bar X* - X-n vertical bar], converge to 0 at a geometric rate.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
