Bayesian Optimization in a Billion Dimensions via Random Embeddings¶
Authors: Ziyu Wang, Frank Hutter, Masrour Zoghi, David Matheson, Nando de Freitas
Published: 2013 (Journal Paper)
Source: Journal of Artificial Intelligence Research
Algorithm: REMBO
arXiv: 1301.1942
DOI: 10.1613/jair.4806
Summary¶
Introduces REMBO, a Bayesian optimization method that searches a random low-dimensional embedding of a very high-dimensional input space. The key contribution is showing that Gaussian-process Bayesian optimization can remain effective in billion-dimensional spaces when the objective has low intrinsic dimensionality, with both theory and solver-configuration experiments supporting the claim.
Abstract¶
Bayesian optimization techniques have been successfully applied to robotics, planning, sensor placement, recommendation, advertising, intelligent user interfaces and automatic algorithm configuration. Despite these successes, the approach is restricted to problems of moderate dimension, and several workshops on Bayesian optimization have identified its scaling to high-dimensions as one of the holy grails of the field. In this paper, we introduce a novel random embedding idea to attack this problem. The resulting Random EMbedding Bayesian Optimization (REMBO) algorithm is very simple, has important invariance properties, and applies to domains with both categorical and continuous variables. We present a thorough theoretical analysis of REMBO. Empirical results confirm that REMBO can effectively solve problems with billions of dimensions, provided the intrinsic dimensionality is low. They also show that REMBO achieves state-of-the-art performance in optimizing the 47 discrete parameters of a popular mixed integer linear programming solver.
Links¶
Primary
Standard
Alternate
Tags¶
-
REMBO
-
Bayesian optimization
-
Random embeddings
-
High-dimensional optimization
-
Black-box optimization
-
Gaussian processes
-
Algorithm configuration