Probabilistic Bisection Converges Almost as Quickly as Stochastic Approximation

The probabilistic bisection algorithm (PBA) solves a class of stochastic\nroot-finding problems in one dimension by successively updating a prior belief\non the location of the root based on noisy responses to queries at chosen\npoints. The responses indicate the direction of the root from the queried\npoint, and are incorrect with a fixed probability. The fixed-probability\nassumption is problematic in applications, and so we extend the PBA to apply\nwhen this assumption is relaxed. The extension involves the use of a power-one\ntest at each queried point. We explore the convergence behavior of the extended\nPBA, showing that it converges at a rate arbitrarily close to, but slower than,\nthe canonical "square root" rate of stochastic approximation.\n