Probabilistic Bisection Converges Almost as Quickly as Stochastic Approximation
Probabilistic Bisection Converges Almost as Quickly as Stochastic Approximation
复制标题
概率二分法的收敛速度几乎与随机逼近一样快
DOI：
--
复制
发表时间：
2016
影响因子：
1.7
通讯作者：
Rolf Waeber
中科院分区：
文献类型：
--
作者：
P. Frazier;S. Henderson;Rolf Waeber
概率二分算法 (PBA) 通过基于对选定点查询的噪声响应连续更新对根位置的先验信念，解决了一维随机寻根问题。响应指示根从查询点的方向，并且以固定概率不正确。固定概率假设在应用中存在问题，因此我们将 PBA 扩展为在放宽该假设时应用。该扩展涉及在每个查询点使用幂一测试。我们探索了扩展 PBA 的收敛行为，表明它的收敛速度任意接近但慢于随机近似的规范“平方根”速率。
The probabilistic bisection algorithm (PBA) solves a class of stochastic root-finding problems in one dimension by successively updating a prior belief on the location of the root based on noisy responses to queries at chosen points. The responses indicate the direction of the root from the queried point, and are incorrect with a fixed probability. The fixed-probability assumption is problematic in applications, and so we extend the PBA to apply when this assumption is relaxed. The extension involves the use of a power-one test at each queried point. We explore the convergence behavior of the extended PBA, showing that it converges at a rate arbitrarily close to, but slower than, the canonical "square root" rate of stochastic approximation.