BINOCULARS for efficient, nonmyopic sequential experimental design

Shali Jiang, Henry Chai, Javier Gonzalez, Roman Garnett
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:4794-4803, 2020.

Abstract

Finite-horizon sequential experimental design (SED) arises naturally in many contexts, including hyperparameter tuning in machine learning among more traditional settings. Computing the optimal policy for such problems requires solving Bellman equations, which are generally intractable. Most existing work resorts to severely myopic approximations by limiting the decision horizon to only a single time-step, which can underweight exploration in favor of exploitation. We present BINOCULARS: Batch-Informed NOnmyopic Choices, Using Long-horizons for Adaptive, Rapid SED, a general framework for deriving efficient, nonmyopic approximations to the optimal experimental policy. Our key idea is simple and surprisingly effective: we first compute a one-step optimal batch of experiments, then select a single point from this batch to evaluate. We realize BINOCULARS for Bayesian optimization and Bayesian quadrature – two notable example problems with radically different objectives – and demonstrate that BINOCULARS significantly outperforms significantly outperforms myopic alternatives in real-world scenarios.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-jiang20b, title = {{BINOCULARS} for efficient, nonmyopic sequential experimental design}, author = {Jiang, Shali and Chai, Henry and Gonzalez, Javier and Garnett, Roman}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {4794--4803}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/jiang20b/jiang20b.pdf}, url = {https://proceedings.mlr.press/v119/jiang20b.html}, abstract = {Finite-horizon sequential experimental design (SED) arises naturally in many contexts, including hyperparameter tuning in machine learning among more traditional settings. Computing the optimal policy for such problems requires solving Bellman equations, which are generally intractable. Most existing work resorts to severely myopic approximations by limiting the decision horizon to only a single time-step, which can underweight exploration in favor of exploitation. We present BINOCULARS: Batch-Informed NOnmyopic Choices, Using Long-horizons for Adaptive, Rapid SED, a general framework for deriving efficient, nonmyopic approximations to the optimal experimental policy. Our key idea is simple and surprisingly effective: we first compute a one-step optimal batch of experiments, then select a single point from this batch to evaluate. We realize BINOCULARS for Bayesian optimization and Bayesian quadrature – two notable example problems with radically different objectives – and demonstrate that BINOCULARS significantly outperforms significantly outperforms myopic alternatives in real-world scenarios.} }
Endnote
%0 Conference Paper %T BINOCULARS for efficient, nonmyopic sequential experimental design %A Shali Jiang %A Henry Chai %A Javier Gonzalez %A Roman Garnett %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-jiang20b %I PMLR %P 4794--4803 %U https://proceedings.mlr.press/v119/jiang20b.html %V 119 %X Finite-horizon sequential experimental design (SED) arises naturally in many contexts, including hyperparameter tuning in machine learning among more traditional settings. Computing the optimal policy for such problems requires solving Bellman equations, which are generally intractable. Most existing work resorts to severely myopic approximations by limiting the decision horizon to only a single time-step, which can underweight exploration in favor of exploitation. We present BINOCULARS: Batch-Informed NOnmyopic Choices, Using Long-horizons for Adaptive, Rapid SED, a general framework for deriving efficient, nonmyopic approximations to the optimal experimental policy. Our key idea is simple and surprisingly effective: we first compute a one-step optimal batch of experiments, then select a single point from this batch to evaluate. We realize BINOCULARS for Bayesian optimization and Bayesian quadrature – two notable example problems with radically different objectives – and demonstrate that BINOCULARS significantly outperforms significantly outperforms myopic alternatives in real-world scenarios.
APA
Jiang, S., Chai, H., Gonzalez, J. & Garnett, R.. (2020). BINOCULARS for efficient, nonmyopic sequential experimental design. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:4794-4803 Available from https://proceedings.mlr.press/v119/jiang20b.html.

Related Material