Regret for Expected Improvement over the Best-Observed Value and Stopping Condition

Vu Nguyen, Sunil Gupta, Santu Rana, Cheng Li, Svetha Venkatesh
Proceedings of the Ninth Asian Conference on Machine Learning, PMLR 77:279-294, 2017.

Abstract

Bayesian optimization (BO) is a sample-efficient method for global optimization of expensive, noisy, black-box functions using probabilistic methods. The performance of a BO method depends on its selection strategy through the acquisition function. Expected improvement (EI) is one of the most widely used acquisition functions for BO that finds the expectation of the improvement function over the incumbent. The incumbent is usually selected as the best-observed value so far, termed as $y^\max$ (for the maximizing problem). Recent work has studied the convergence rate for EI under some mild assumptions or zero noise of observations. Especially, the work of Wang and de Freitas (2014) has derived the sublinear regret for EI under a stochastic noise. However, due to the difficulty in stochastic noise setting and to make the convergent proof feasible, they use an alternative choice for the incumbent as the maximum of the Gaussian process predictive mean, $μ^\max$. This modification makes the algorithm computationally inefficient because it requires an additional global optimization step to estimate $μ^\max$ that is costly and may be inaccurate. To address this issue, we derive a sublinear convergence rate for EI using the commonly used $y^\max$. Moreover, our analysis is the first to study a stopping criteria for EI to prevent unnecessary evaluations. Our analysis complements the results of Wang and de Freitas (2014) to theoretically cover two incumbent settings for EI. Finally, we demonstrate empirically that EI using $y^\max$ is both more computationally efficiency and more accurate than EI using $μ^\max$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v77-nguyen17a, title = {Regret for Expected Improvement over the Best-Observed Value and Stopping Condition}, author = {Nguyen, Vu and Gupta, Sunil and Rana, Santu and Li, Cheng and Venkatesh, Svetha}, booktitle = {Proceedings of the Ninth Asian Conference on Machine Learning}, pages = {279--294}, year = {2017}, editor = {Zhang, Min-Ling and Noh, Yung-Kyun}, volume = {77}, series = {Proceedings of Machine Learning Research}, address = {Yonsei University, Seoul, Republic of Korea}, month = {15--17 Nov}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v77/nguyen17a/nguyen17a.pdf}, url = {https://proceedings.mlr.press/v77/nguyen17a.html}, abstract = {Bayesian optimization (BO) is a sample-efficient method for global optimization of expensive, noisy, black-box functions using probabilistic methods. The performance of a BO method depends on its selection strategy through the acquisition function. Expected improvement (EI) is one of the most widely used acquisition functions for BO that finds the expectation of the improvement function over the incumbent. The incumbent is usually selected as the best-observed value so far, termed as $y^\max$ (for the maximizing problem). Recent work has studied the convergence rate for EI under some mild assumptions or zero noise of observations. Especially, the work of Wang and de Freitas (2014) has derived the sublinear regret for EI under a stochastic noise. However, due to the difficulty in stochastic noise setting and to make the convergent proof feasible, they use an alternative choice for the incumbent as the maximum of the Gaussian process predictive mean, $μ^\max$. This modification makes the algorithm computationally inefficient because it requires an additional global optimization step to estimate $μ^\max$ that is costly and may be inaccurate. To address this issue, we derive a sublinear convergence rate for EI using the commonly used $y^\max$. Moreover, our analysis is the first to study a stopping criteria for EI to prevent unnecessary evaluations. Our analysis complements the results of Wang and de Freitas (2014) to theoretically cover two incumbent settings for EI. Finally, we demonstrate empirically that EI using $y^\max$ is both more computationally efficiency and more accurate than EI using $μ^\max$.} }
Endnote
%0 Conference Paper %T Regret for Expected Improvement over the Best-Observed Value and Stopping Condition %A Vu Nguyen %A Sunil Gupta %A Santu Rana %A Cheng Li %A Svetha Venkatesh %B Proceedings of the Ninth Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Min-Ling Zhang %E Yung-Kyun Noh %F pmlr-v77-nguyen17a %I PMLR %P 279--294 %U https://proceedings.mlr.press/v77/nguyen17a.html %V 77 %X Bayesian optimization (BO) is a sample-efficient method for global optimization of expensive, noisy, black-box functions using probabilistic methods. The performance of a BO method depends on its selection strategy through the acquisition function. Expected improvement (EI) is one of the most widely used acquisition functions for BO that finds the expectation of the improvement function over the incumbent. The incumbent is usually selected as the best-observed value so far, termed as $y^\max$ (for the maximizing problem). Recent work has studied the convergence rate for EI under some mild assumptions or zero noise of observations. Especially, the work of Wang and de Freitas (2014) has derived the sublinear regret for EI under a stochastic noise. However, due to the difficulty in stochastic noise setting and to make the convergent proof feasible, they use an alternative choice for the incumbent as the maximum of the Gaussian process predictive mean, $μ^\max$. This modification makes the algorithm computationally inefficient because it requires an additional global optimization step to estimate $μ^\max$ that is costly and may be inaccurate. To address this issue, we derive a sublinear convergence rate for EI using the commonly used $y^\max$. Moreover, our analysis is the first to study a stopping criteria for EI to prevent unnecessary evaluations. Our analysis complements the results of Wang and de Freitas (2014) to theoretically cover two incumbent settings for EI. Finally, we demonstrate empirically that EI using $y^\max$ is both more computationally efficiency and more accurate than EI using $μ^\max$.
APA
Nguyen, V., Gupta, S., Rana, S., Li, C. & Venkatesh, S.. (2017). Regret for Expected Improvement over the Best-Observed Value and Stopping Condition. Proceedings of the Ninth Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 77:279-294 Available from https://proceedings.mlr.press/v77/nguyen17a.html.

Related Material