Probabilistic bisection converges almost as quickly as stochastic approximation

DOI10.1287/MOOR.2018.0938MaRDI QIDQ5219733zbMATH OpenOpenAlexWikidataFDO

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

Publication date 12 March 2020

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.03964

zbMATH Keywords

stochastic root findingtests of power one

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Stochastic programming (90C15)

Abstract: 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.

Recommendations

• Probabilistic bisection with spatial metamodels
• Bisection search with noisy responses
• A novel technique for stochastic root-finding: enhancing the search with adaptive d-ary search
• Adaptive designs for stochastic root-finding
• A Bayesian stochastic approximation method

Cites work

• A Stochastic Approximation Method
• Acceleration of Stochastic Approximation by Averaging
• Asymptotic Behavior of Expected Sample Size in Certain One Sided Tests
• Asymptotic Properties of Distributed and Communicating Stochastic Approximation Algorithms
• Bisection search with noisy responses
• Collaborative 20 Questions for Target Localization
• scientific article; zbMATH DE number 3513625 (Why is no real title available?)
• scientific article; zbMATH DE number 3523429 (Why is no real title available?)
• scientific article; zbMATH DE number 1972910 (Why is no real title available?)
• New method of stochastic approximation type
• On the convergence rate for stochastic approximation in the nonsmooth setting
• Power-one tests based on sample sums
• Robust Stochastic Approximation Approach to Stochastic Programming
• Searching with known error probability
• Sequential transmission using noiseless feedback
• Spectral theory and limit theorems for geometrically ergodic Markov processes
• Statistical Methods Related to the Law of the Iterated Logarithm
• Stochastic approximation algorithms for parallel and distributed processing
• Stochastic approximation with long range dependent and heavy tailed noise
• Stochastic simulation: Algorithms and analysis
• The expected sample size of some tests of power one
• The stochastic root-finding problem: overview, solutions, and open questions
• Twenty questions with noise: Bayes optimal policies for entropy loss

Cited in

(6)

• Bisection hardly ever converges linearly
• Probabilistic bisection with spatial metamodels
• Bisection search with noisy responses
• Thompson sampling guided stochastic searching on the line for deceptive environments with applications to root-finding problems
• Generalized probabilistic bisection for stochastic root finding
• Computing systemic risk measures with graph neural networks

This page was built for publication: Probabilistic bisection converges almost as quickly as stochastic approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5219733)