High Dimensional Bayesian Optimisation and Bandits via Additive Models

July 2015

High Dimensional Bayesian Optimisation and Bandits via Additive Models

Authors:

K. Kandasamy, J. Schneider, and B. Poczos
Conference Paper
Proceedings of (ICML) International Conference on Machine Learning

Abstract:

Bayesian Optimisation (BO) is a technique used in optimising a $D$-dimensional function which is typically expensive to evaluate. While there have been many successes for BO in low dimensions, scaling it to high dimensions has been a notoriously difficult problem. Existing literature on the subject are under very restrictive settings. In this paper, we identify two key challenges in this endeavour. We tackle these challenges by assuming an additive structure for the function. This setting is substantially more expressive and contains a richer class of functions than previous work. In our theoretical analysis we prove that for additive functions the regret has only linear (as opposed to exponential) dependence on $D$ even though the function depends on all $D$ dimensions. We also demonstrate several other statistical and computational benefits in our framework. Empirically via synthetic examples, a scientific simulation and a face detection problem we demonstrate that our method outperforms naive BO on additive functions and on several examples when the function is not additive.
@conference{Kandasamy-2015-119757,
author = {K. Kandasamy And J. Schneider And B. Poczos},
title = {High Dimensional Bayesian Optimisation and Bandits via Additive Models},
booktitle = {Proceedings of (ICML) International Conference on Machine Learning},
year = {2015},
month = {July},
volume = {37},
pages = {295 - 304},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.