×

zbMATH — the first resource for mathematics

Probabilistic bisection with spatial metamodels. (English) Zbl 1443.62066
Summary: Probabilistic Bisection Algorithms perform root finding based on knowledge acquired from noisy oracle responses. We consider the generalized PBA setting (G-PBA) where the statistical distribution of the oracle is unknown and location-dependent, so that model inference and Bayesian knowledge updating must be performed simultaneously. To this end, we propose to leverage the spatial structure of a typical oracle by constructing a statistical surrogate for the underlying logistic regression step. We investigate several surrogates, including Binomial Gaussian Processes (B-GP), Polynomial, Kernel, and Spline Logistic Regression. In parallel, we develop sampling policies that adaptively balance learning the oracle distribution and learning the root. One of our proposals mimics active learning with B-GPs and provides a novel look-ahead predictive variance formula. The resulting gains of our Spatial PBA algorithm relative to earlier G-PBA models are illustrated with synthetic examples and a challenging stochastic root finding problem from Bermudan option pricing.
MSC:
62F15 Bayesian inference
62L05 Sequential statistical design
90C26 Nonconvex programming, global optimization
91G20 Derivative securities (option pricing, hedging, etc.)
Software:
GPstuff; R; NLopt; BayesDA; EGO
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ankenman, B.; Nelson, B. L.; Staum, J., Stochastic Kriging for simulation metamodeling, Operations Research, 58, 2, 371-382 (2010) · Zbl 1342.62134
[2] Azzimonti, D.; Bect, J.; Chevalier, C.; Ginsbourger, D., Quantifying uncertainties on excursion sets under a Gaussian random field prior, SIAM/ASA Journal Uncertainty Quantification, 4, 1, 850-874 (2016) · Zbl 1352.62144
[3] Bect, J.; Ginsbourger, D.; Li, L.; Picheny, V.; Vazquez, E., Sequential design of computer experiments for the estimation of a probability of failure, Statistics and Computing, 22, 3, 773-793 (2012) · Zbl 1252.62081
[4] Binois, M.; Gramacy, R. B.; Ludkovski, M., Practical heteroskedastic Gaussian process modeling for large simulation experiments, Journal of Computational and Graphical Statistics, 0, ja, 1-41 (2018)
[5] Binois, M.; Huang, J.; Gramacy, R. B.; Ludkovski, M., Replication or exploration? Sequential design for stochastic simulation experiments, Technometrics, 61, 1, 7-23 (2018)
[6] Chen, X.; Zhou, Q., Sequential design strategies for mean response surface metamodeling via stochastic Kriging with adaptive exploration and exploitation, European Journal of Operational Research, 262, 2, 575-585 (2017) · Zbl 1378.62039
[7] Chevalier, C.; Bect, J.; Ginsbourger, D.; Vazquez, E.; Picheny, V.; Richet, Y., Fast parallel kriging-based stepwise uncertainty reduction with application to the identification of an excursion set, Technometrics, 56, 4, 455-465 (2014)
[8] Cover, T. M.; Thomas, J. A., Elements of Information Heory (Wiley Series in Telecommunications and Signal Processing) (2006), Wiley-Interscience
[9] Frazier, P. I.; Henderson, S. G.; Waeber, R., Probabilistic bisection converges almost as quickly as Stochastic Approximation, Mathematics of Operations Research, (p. to Appear) (2019) · Zbl 1441.90105
[10] Friedman, J.; Hastie, T.; Tibshirani, R., The elements of statistical Learning, 1 (2001), Springer series in Statistics New York
[11] Gelman, A.; Carlin, J. B.; Stern, H. S.; Rubin, D. B., Bayesian data analysis, 2 (2014), Taylor & Francis · Zbl 1279.62004
[12] Henderson, H. V.; Searle, S. R., On deriving the inverse of a sum of matrices, SIAM Review, 23, 1, 53-60 (1981) · Zbl 0451.15005
[13] Hennig, P.; Schuler, C. J., Entropy search for information-efficient global optimization, Journal of Machine Learning Research, 13, Jun, 1809-1837 (2012) · Zbl 1432.65073
[14] Hernández-Lobato, J. M.; Hoffman, M. W.; Ghahramani, Z., Predictive entropy search for efficient global optimization of black-box functions, Proceedings of the Advances in neural information processing systems, 918-926 (2014)
[15] Jalali, H.; Van Nieuwenhuyse, I.; Picheny, V., Comparison of Kriging-based algorithms for simulation optimization with heterogeneous noise, European Journal of Operational Research, 261, 1, 279-301 (2017) · Zbl 1403.90553
[16] Jedynak, B.; Frazier, P. I.; Sznitman, R., Twenty questions with noise: Bayes optimal policies for entropy loss, Journal of Applied Probability, 49, 1, 114-136 (2012) · Zbl 1318.62017
[17] Johnson, S. G. (2014). The NLopt nonlinear-optimization package. http://www.github.com/stevengj/nlopt.
[18] Jones, D.; Schonlau, M.; Welch, W., Efficient global optimization of expensive black-box functions, Journal of Global optimization, 13, 4, 455-492 (1998) · Zbl 0917.90270
[19] Jones, D. R.; Perttunen, C. D.; Stuckman, B. E., Lipschitzian optimization without the Lipschitz constant, Journal of Optimization Theory and Applications, 79, 1, 157-181 (1993) · Zbl 0796.49032
[20] Kamiński, B., A method for the updating of stochastic Kriging metamodels, European Journal of Operational Research, 247, 3, 859-866 (2015) · Zbl 1346.62039
[21] Kapoor, A.; Grauman, K.; Urtasun, R.; Darrell, T., Active learning with Gaussian processes for object categorization, Proceedings of the ICCV IEEE 11th international conference on computer vision, 1-8 (2007), IEEE
[22] Letham, B.; Karrer, B.; Ottoni, G.; Bakshy, E., Constrained Bayesian optimization with noisy experiments, Bayesian Analysis, 14, 2, 495-519 (2019) · Zbl 1416.62156
[23] Longstaff, F. A.; Schwartz, E. S., Valuing American options by simulation: a simple least-squares approach, The Review of Financial Studies, 14, 1, 113-147 (2001)
[24] Ludkovski, M., Kriging metamodels and experimental design for Bermudan option pricing, Journal of Computational Finance, 22, 1, 37-77 (2018)
[25] Minka, T. P., Expectation propagation for approximate Bayesian inference, Proceedings of the seventeenth conference on uncertainty in artificial intelligence, 362-369 (2001), Morgan Kaufmann Publishers Inc
[26] Nickisch, H.; Rasmussen, C. E., Approximations for binary Gaussian process classification, Journal of Machine Learning Research, 9, Oct, 2035-2078 (2008) · Zbl 1225.62087
[27] Pasupathy, R.; Kim, S., The Stochastic Root-Finding Problem: Overview, Solutions, and Open Questions, ACM Transactions on Modeling and Computer Simulation, 21, 3, 19:1-19:23 (2011) · Zbl 1386.65054
[28] Picheny, V.; Ginsbourger, D.; Richet, Y.; Caplin, G., Quantile-based optimization of noisy computer experiments with tunable precision, Technometrics, 55, 1, 2-13 (2013)
[29] Picheny, V.; Wagner, T.; Ginsbourger, D., A benchmark of Kriging-based infill criteria for noisy optimization, Structural and Multidisciplinary Optimization, 48, 3, 607-626 (2013)
[30] Powell, W. B.; Ryzhov, I. O., Optimal learning, 841 (2012), John Wiley & Sons
[31] R Core Team (2016). R: A Language and Environment for Statistical Computing. R Foundation for Statistical ComputingVienna, Austria.
[32] Rasmussen, C. E., Gaussian processes in Machine Learning, Advanced lectures on machine learning, 63-71 (2004), Springer · Zbl 1120.68436
[33] Rodríguez, S., Generalized Probabilistic Bisection for Stochastic Root-Finding (2018), University of California, Santa Barbara, Ph.D. thesis
[34] Rodríguez, S., & Ludkovski, M. (2017). Generalized Probabilistic Bisection for Stochastic Root-Finding. arXiv:1711.00843.
[35] Russo, D.; Van Roy, B., Learning to optimize via information-directed sampling, Proceedings of the advances in neural information processing systems, 1583-1591 (2014)
[36] Russo, D.; Van Roy, B., An information-theoretic analysis of Thompson sampling, The Journal of Machine Learning Research, 17, 1, 2442-2471 (2016)
[37] Scott, W.; Frazier, P.; Powell, W., The correlated knowledge gradient for simulation optimization of continuous parameters using gaussian process regression, SIAM Journal on Optimization, 21, 3, 996-1026 (2011) · Zbl 1229.62018
[38] Sebastiani, P.; Wynn, H. P., Maximum entropy sampling and optimal bayesian experimental design, Journal of the Royal Statistical Society: Series B (Statistical Methodology), 62, 1, 145-157 (2000) · Zbl 0941.62084
[39] Tesch, M.; Schneider, J.; Choset, H., Expensive function optimization with stochastic binary outcomes, Proceedings of the international conference on machine learning, 1283-1291 (2013)
[40] Vanhatalo, J.; Riihimäki, J.; Hartikainen, J.; Jylänki, P.; Tolvanen, V.; Vehtari, A., Gpstuff: Bayesian modeling with Gaussian processes, Journal of Machine Learning Research, 14, Apr, 1175-1179 (2013) · Zbl 1320.62010
[41] Villemonteix, J.; Vazquez, E.; Walter, E., An informational approach to the global optimization of expensive-to-evaluate functions, Journal of Global Optimization, 44, 4, 509 (2009) · Zbl 1180.90253
[42] Waeber, R., Probabilistic Bisection Search for Stochastic Root-Finding (2013), Cornell University, Ph.D. thesis
[43] Waeber, R.; Frazier, P. I.; Henderson, S. G., A Bayesian approach to Stochastic Root Finding, Proceedings of the winter simulation conference (wsc), 4033-4045 (2011), IEEE
[44] Waeber, R.; Frazier, P. I.; Henderson, S. G., Bisection search with noisy responses, SIAM Journal on Control and Optimization, 51, 3, 2261-2279 (2013) · Zbl 1272.93133
[45] Wang, Z.; Zhou, B.; Jegelka, S., Optimization as estimation with Gaussian processes in bandit settings, Proceedings of the artificial intelligence and statistics, 1022-1031 (2016)
[46] Williams, C. K.; Barber, D., Bayesian classification with Gaussian processes, IEEE Transactions on Pattern Analysis and Machine Intelligence, 20, 12, 1342-1351 (1998)
[47] Wood, S. N., mgcv: GAMs and generalized ridge regression for R, R News, 1, 2, 20-25 (2001)
[48] Zhu, J.; Hastie, T., Kernel logistic regression and the import vector machine, Journal of Computational and Graphical Statistics, 14, 1, 185-205 (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.