Discovering and Exploiting Additive Structure for Bayesian Optimization
Jacob Gardner, Chuan Guo, Kilian Weinberger, Roman Garnett, Roger Grosse
Abstract
Bayesian optimization has proven invaluable for black-box optimization of expensive functions. Its main limitation is its exponential complexity with respect to the dimensionality of the search space using typical kernels. Luckily, many objective functions can be decomposed into additive subproblems, which can be optimized independently. We investigate how to automatically discover such (typically unknown) additive structure while simultaneously exploiting it through Bayesian optimization. We propose an efficient algorithm based on Metropolis-Hastings sampling and demonstrate its efficacy empirically on synthetic and real-world data sets. Throughout all our experiments we reliably discover hidden additive structure whenever it exists and exploit it to yield significantly faster convergence.
BibTeX
@InProceedings{pmlr-v54-gardner17a,
title = {{Discovering and Exploiting Additive Structure for Bayesian Optimization}},
author = {Gardner, Jacob and Guo, Chuan and Weinberger, Kilian and Garnett, Roman and Grosse, Roger},
booktitle = {Proceedings of the 20th International Conference on Artificial Intelligence and Statistics},
pages = {1311--1319},
year = {2017},
editor = {Singh, Aarti and Zhu, Jerry},
volume = {54},
series = {Proceedings of Machine Learning Research},
month = {20--22 Apr},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v54/gardner17a/gardner17a.pdf},
url = {https://proceedings.mlr.press/v54/gardner17a.html},
abstract = {Bayesian optimization has proven invaluable for black-box optimization of expensive functions. Its main limitation is its exponential complexity with respect to the dimensionality of the search space using typical kernels. Luckily, many objective functions can be decomposed into additive subproblems, which can be optimized independently. We investigate how to automatically discover such (typically unknown) additive structure while simultaneously exploiting it through Bayesian optimization. We propose an efficient algorithm based on Metropolis-Hastings sampling and demonstrate its efficacy empirically on synthetic and real-world data sets. Throughout all our experiments we reliably discover hidden additive structure whenever it exists and exploit it to yield significantly faster convergence.}
}