Probabilistic Bisection Converges Almost as Quickly as Stochastic Approximation

References

• [1] Anantharam V, Borkar VS (2012) Stochastic approximation with long range dependent and heavy tailed noise. Queueing Systems 71(1–2):221–242.Crossref, Google Scholar
• [2] Asmussen S, Glynn PW (2007) Stochastic stimulation: algorithms and analysis. Stochastic Modeling and Applied Probability, vol. 57 (Springer, New York).Google Scholar
• [3] Burnashev MV, Zigangirov KS (1974) An interval estimation problem for controlled observations. Probl. Peredachi Inf. 10(3):51–61.Google Scholar
• [4] Burnashev MV, Zigangirov KS (1975) On one problem of observation control. Probl. Peredachi Inf. 11(3):44–52.Google Scholar
• [5] Castro RM, Nowak RD (2008) Active learning and sampling. Hero AO, Castañón DA, Cochran D, Kastella K, eds. Foundations and Applications of Sensor Management (Springer, New York), 177–200.Crossref, Google Scholar
• [6] Farrell RH (1964) Asymptotic behavior of expected sample size in certain one sided tests. Ann. Math. Statist. 35(1):36–72.Crossref, Google Scholar
• [7] Golubev G, Levit B (2003) Sequential recovery of analytic periodic edges in binary image models. Math. Methods Statist. 12(1):95–115.Google Scholar
• [8] Horstein M (1963) Sequential transmission using noiseless feedback. IEEE Trans. Inform. Theory 9(3):136–143.Crossref, Google Scholar
• [9] Jedynak B., Frazier PI, Sznitman R (2012) Twenty questions with noise: Bayes optimal policies for entropy loss. J. Appl. Probab. 49(1):114–136.Crossref, Google Scholar
• [10] Kontoyiannis I, Meyn SP (2003) Spectral theory and limit theorems for geometrically ergodic Markov processes. Ann. Appl. Probab. 13(1):304–362.Crossref, Google Scholar
• [11] Kushner HJ, Yin G (1987) Asymptotic properties of distributed and communicating stochastic approximation algorithms. SIAM J. Control Optim. 25(5):1266–1290.Crossref, Google Scholar
• [12] Kushner HJ, Yin G (1987) Stochastic approximation algorithms for parallel and distributed processing. Stochastics 22(3–4):219–250.Crossref, Google Scholar
• [13] Kushner HJ, Yin G (2003) Stochastic Approximation and Recursive Algorithms and Applications (Springer, New York).Google Scholar
• [14] Lai TL (1977) Power-one tests based on sample sums. Ann. Statist. 5(5):866–880.Crossref, Google Scholar
• [15] Lim E (2011) On the convergence rate for stochastic approximation in the nonsmooth setting. Math. Oper. Res. 36(3):527–537.Link, Google Scholar
• [16] Nemirovski A, Juditsky A, Lan G, Shapiro A (2009) Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19(4):1574–1609.Crossref, Google Scholar
• [17] Pallone S, Frazier PI, Henderson SG (2014) Multisection: Parallelized bisection. Tolk A, Diallo D, Ryzhov IO, Yilmaz L, Buckley S, Miller JA, eds. Proc. 2014 Winter Simulation Conf. (IEEE, Piscataway, NJ), 3773–3784.Crossref, Google Scholar
• [18] Pasupathy R, Kim S (2011) The stochastic root-finding problem; Overview, solutions, and open questions. ACM Trans. Model. Comput. Simul. 21(3):19.Crossref, Google Scholar
• [19] Pelc A (1989) Searching with known error probability. Theoret. Comput. Sci. 63(2):185–202.Crossref, Google Scholar
• [20] Polyak BT (1990). New method of stochastic approximation type. Autom. Remote Control 51(7):937–946.Google Scholar
• [21] Polyak BT, Juditsky AB (1992) Acceleration of stochastic approximation by averaging. SIAM J. Control Optim. 30(4):838–855.Crossref, Google Scholar
• [22] Robbins H (1970) Statistical methods related to the law of the iterated logarithm. Ann. Math. Statist. 41(5):1397–1409.Crossref, Google Scholar
• [23] Robbins H, Monro S (1951) A stochastic approximation method. Ann. Math. Statist. 22(3):400–407.Crossref, Google Scholar
• [24] Robbins H, Siegmund D (1974) The expected sample size of some tests of power one. Ann. Statist. 2(3):415–436.Crossref, Google Scholar
• [25] Rodriguez S, Ludkovski M (2015) Information directed sampling for stochastic root finding. Proc. 2015 Winter Simulation Conf. (IEEE Press, New York), 3142–3143.Crossref, Google Scholar
• [26] Ruppert D (1988) Efficient estimators from a slowly convergent robbins-monro procedure. Technical Report, Cornell University, Ithaca, NY.Google Scholar
• [27] Ruppert D (1991) Stochastic approximation. Ghosh BK, Sen PK, eds. Handbook of Sequential Analysis (Marcel-Dekker, New York), 503–529.Google Scholar
• [28] Sznitman R, Lucchi A, Frazier PI, Jedynak BM, Fua P (2013) An optimal policy for target localization with application to electron microscopy. Dasgupta S, McAllester D, eds. Proc. 30th Internat. Conf. on Machine Learning (ICML) (Omnipress, Madison, WI), 1–9.Google Scholar
• [29] Tsiligkaridis T, Sadler BM, Hero AO (2014) Collaborative 20 questions for target localization. IEEE Trans. Inform. Theory 60(4):2233–2252.Crossref, Google Scholar
• [30] Ville J (1939) Étude Critique de la Notion de Collectif (Gauthier-Villars, Paris).Google Scholar
• [31] Waeber R (2013) Probabilistic bisection search for stochastic root-finding. Ph.D. thesis, Cornell University, Ithaca NY.Google Scholar
• [32] Waeber R, Frazier PI, Henderson SG (2013) Bisection search with noisy responses. SIAM J. Control Optim. 51(3):2261–2279.Crossref, Google Scholar