期刊
SIAM JOURNAL ON CONTROL AND OPTIMIZATION
卷 51, 期 3, 页码 2261-2279出版社
SIAM PUBLICATIONS
DOI: 10.1137/120861898
关键词
probabilistic bisection; noisy bisection; geometric rate of convergence; sequential analysis; Bayesian performance analysis
资金
- 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
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据