Probabilistic Bisection Converges Almost as Quickly as Stochastic Approximation

Peter I. Frazier, Shane G. Henderson, Rolf Waeber

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…