PaperlayerView exact revision on arXiv

Source-linked AI summary

Batched Large-scale Bayesian Optimization in High-dimensional Spaces

Zi Wang, Clement Gehring, Pushmeet Kohli, Stefanie Jegelka

arXiv:1706.01445v4stat.MLcs.LGmath.OC

TL;DR

Bayesian optimization is difficult to scale to high-dimensional problems with many observations and parallel batch queries. EBO uses randomized partitioned additive GP ensembles with parallel inference and query selection, achieving faster posterior inference and applications involving tens of thousands of observations.

  • Problem

    Bayesian optimization remains limited by large observation sets, high-dimensional inputs, and the need to select diverse high-quality batch queries.

  • Method

    EBO combines randomized partition-based approximations, additive tile-coded Gaussian processes, ensemble learning, and parallelized Gibbs sampling and query selection.

  • Results

    EBO speeds posterior inference by 2-3 orders of magnitude, including 400 times in one experiment, while handling real-world problems with tens of thousands of observations.

  • Takeaways & Limitations

    EBO provides a framework for jointly addressing scalability, high-dimensional inputs, and batch evaluation in Bayesian optimization.

  • Takeaways & Limitations

    Random-feature approximations generally require more features as observations increase, while Mondrian features are not well compatible with learning additive structure and typically require a tree forest.

Abstract

from arXiv · show

Bayesian optimization (BO) has become an effective approach for black-box function optimization problems when function evaluations are expensive and the optimum can be achieved within a relatively small number of queries. However, many cases, such as the ones with high-dimensional inputs, may require a much larger number of observations for optimization. Despite an abundance of observations thanks to parallel experiments, current BO techniques have been limited to merely a few thousand observations. In this paper, we propose ensemble Bayesian optimization (EBO) to address three current challenges in BO simultaneously: (1) large-scale observations; (2) high dimensional input spaces; and (3) selections of batch queries that balance quality and diversity. The key idea of EBO is to operate on an ensemble of additive Gaussian process models, each of which possesses a randomized strategy to divide and conquer. We show unprecedented, previously impossible results of scaling up BO to tens of thousands of observations within minutes of computation.

1 Introduction

Bayesian optimization faces simultaneous scalability, dimensionality, and batch-query challenges. EBO addresses them with randomized partition-based additive GP ensembles and reports substantially faster inference while handling tens of thousands of observations.

  • Motivation: Bayesian optimization remains difficult to scale because high-dimensional acquisition optimization and uncertainty estimation can be computationally expensive.These limitations are especially consequential when parallel experiments produce many observations.
  • Contribution: EBO targets high-dimensional, large-scale parameter searches whose queries are parallelizable.The framework is designed to address batch selection, high-dimensional inputs, and scalability jointly.
  • Method: EBO combines efficient partition-based approximators with ensemble learning and stochastic inference.Its ensemble maintains a posterior distribution over models and samples one member for search and estimation at each iteration.
  • Method: A hierarchical additive GP based on tile coding learns kernel width and additive structure, while randomized Mondrian blocks accelerate Gram-matrix computations.Sampling and query selection can be parallelized across blocks.
  • Results: 2-3 orders of magnitude: EBO speeds posterior inference compared with the state-of-the-art without sacrificing quality.One experiment reports a 400-times speedup, and real-world applications use tens of thousands of observations.
  • Positioning: The paper presents EBO as the first framework, to the authors’ knowledge, to address batch evaluations, high-dimensional inputs, and scalability jointly.Earlier work typically addressed these challenges separately or in partial combinations.

2 Background and Challenges

The background identifies GP computation, feature approximation, additive-structure learning, and variance estimation as barriers in high-dimensional Bayesian optimization. The section motivates randomized partitioned approximations and additive models as responses to these barriers.

  • Problem setting: The goal is to maximize a black-box function over a high-dimensional search space X = [0, R]^D.The function is expensive or unavailable analytically, motivating Bayesian optimization.
  • Gaussian-process bottlenecks: O(n3) GP matrix inversion and determinant computations become bottlenecks for posterior prediction and likelihood estimation as observations increase.This affects both function-value predictions and data-likelihood calculations.
  • Additive structure: Additive structure reduces sample complexity and permits component-wise acquisition optimization, but learning the decomposition can require expensive Gibbs sampling.The cited prior sampler takes hours for only a few hundred points.
  • Random features: Random-feature approximations do not generally scale with observations because the number of features needed for accurate GP approximation increases with sample size.A fixed feature count is therefore insufficient for large-scale observations.
  • Random features: Learning random-feature hyperparameters can require feature recomputation and O(D3R) inverse and determinant calculations.Mondrian features improve kernel-width learning efficiency but are not well suited to jointly learning additive structure and typically require a forest of trees.
  • Tile coding: Tile coding provides k-hot nonlinear features from random partitions and can approximate kernels such as the hat kernel.This makes tile coding suitable for the paper’s GP approximations.
  • Uncertainty estimation: Variance starvation occurs when finite random features underestimate variance relative to the mean, especially in regions without observations.The paper reports that both mean and confidence-bound predictions can become poor once observations exceed features.

3 Ensemble Bayesian Optimization

EBO partitions the search space, learns local TileGP models, and aggregates their proposals across iterations. It combines randomized partitioning, additive structure learning, and diversity-aware batch filtering for scalable parallel BO.

  • Ensemble Bayesian Optimization: EBO uses a stochastic series of Mondrian trees to partition the input space, learn local GP kernel parameters, and aggregate them across BO iterations.Each iteration draws a new partition, so the forest spans multiple BO iterations.
  • Ensemble Bayesian Optimization: Each partition learns a local TileGP using random tile coding, additive structure, and Gibbs sampling before generating acquisition-function candidates.TileGPs use additive kernels with components represented by tilings.
  • 3.2 Learning a local TileGP via Gibbs sampling: TileGP jointly learns the additive decomposition and kernel parameters through Gibbs sampling over discrete cut and group-assignment variables.The model marginalizes the Poisson rate and mixing proportion, leaving k and z to sample.
  • 3.2 Learning a local TileGP via Gibbs sampling: The partitioning ensures more features than observations within each local model, which can alleviate variance starvation.Variance starvation is the underestimation of variance relative to the mean when finite random features face many observations.
  • 3.3 Acquisition functions and filtering: EBO selects batch points by combining acquisition quality with a log-determinant diversity term and maximizing the resulting score greedily.When partitions are fewer than the batch size, the method can use batch BO within each partition.

4 Experiments

Experiments evaluate EBO’s scalability and optimization effectiveness across large-observation, high-dimensional, synthetic, control, and trajectory tasks. EBO substantially accelerates inference while generally finding good solutions faster than BO alternatives, though CEM performs better on the trajectory task.

  • Scalability of EBO: EBO and SKL achieve similar additive-structure quality, with Rand Index scores of 96.8% and 96.3%, respectively.
  • Effectiveness of EBO: On four 50D synthetic functions, EBO finds a good point much faster than BO-SVI, BO-Add-SVI, and PBO.BO-SVI has the highest regret for all functions, while BO-Add-SVI improves over the full-kernel SVI model.
  • Effectiveness of EBO: The experiments compare EBO with BO-SVI, BO-Add-SVI, and CEM on a 14-parameter robot-pushing task using repeated batched evaluations.All methods receive the same 10^4 random observations and run for 200 iterations with batch size 100.
  • Effectiveness of EBO: On the 60-dimensional rover trajectory task, CEM achieves better results than the BO methods, while EBO outperforms the SVI-based BO alternatives.The task uses a nonsmooth, discontinuous, and concave reward function in parts of the input.

5 Conclusion

The conclusion presents EBO as a framework for scaling Bayesian optimization to high dimensions and large observation sets. It combines randomized partitioning, additive TileGP ensembles, efficient Gibbs sampling, and automatic batch-query generation, with empirical validation on tens of thousands of observations.

  • EBO jointly targets high-dimensional inputs and large numbers of observations in black-box optimization.
  • EBO combines randomized adaptive partitions, an ensemble of additive TileGPs, efficient Gibbs sampling, and automatic batch queries.
  • EBO’s scalability and effectiveness are empirically demonstrated on high-dimensional parameter-search tasks with tens of thousands of observations.

A An Illustration of EBO

A two-dimensional additive function illustrates how EBO distributes early queries and then optimizes using partitioned local models. The example specifies the function’s global maximum and the configuration used for the demonstration.

  • The function is sampled from a 2D TileGP with decomposition z = [0, 1], inverse bandwidth k = [10, 10], and noise σ = 0.01.
  • The illustrated function is a 2D additive function whose global maximum is marked with “+”.

B Partitioning the input space via a Mondrian process

The Mondrian partitioning procedure recursively divides the input domain into hyperrectangular regions while respecting partition-count and minimum-data constraints. It starts from the full domain and stops when the target number of partitions is reached or further valid splits are unavailable.

  • The algorithm samples partitions for splitting using their lengths and the number of associated observations exceeding the minimum threshold S.
  • Each selected partition is split at a sampled cut location, producing left and right child regions.
  • Mondrian partitioning initializes the leaf set with the full function domain represented as the root hyperrectangle.
  • Partitioning stops when the number of leaves reaches Np or no partition contains more than S data points.Np denotes the maximum number of Mondrian partitions, while S denotes the minimum number of data points per partition.

C Budget allocation and batched BO

EBO distributes candidate generation across local workers and filters their recommendations into batches using aggregated information. Its current budget allocation and batch-selection procedures are heuristic, while alternative batched BO methods may improve results.

  • Budget allocation and batched BO: Local workers learn local GPs and recommend candidate points, after which an aggregation-based filter selects the evaluation batch.The filter operates on recommendations from all workers using aggregated information about the function.
  • Budget allocation and batched BO: Early iterations may have fewer Mondrian partitions than the batch size, requiring budget allocation across workers.Partitions are initially limited because splitting stops once a partition reaches a minimum number of data points.
  • Budget allocation and batched BO: EBO generates at least 2B recommendations, allocating each worker a budget proportional to partition volume plus its best function value.This is the heuristic used in the current EBO implementation.
  • Budget allocation and batched BO: Batched BO always includes the top n acquisition-function points and fills remaining positions with random points from the partition.Acquisition optimization samples 1000 points in each additive component's low-dimensional space before L-BFGS-B refinement.
  • Budget allocation and batched BO: Other batched BO methods can potentially improve EBO's results.The paper does not specify which alternative methods would provide such improvements.

D Relations to Mondrian Kernels and Random Binning

EBO’s partition-based approximations connect tile coding, Mondrian grids, random binning, and Mondrian features through randomized spatial partitions. These constructions support additive kernel approximations, while BlockOpt provides a comparative acquisition-optimization strategy.

  • Relations to Mondrian Kernels and Random Binning: TileGP uses Mondrian grids or tile coding to infer the decomposition z and number of cuts k, the inverse of kernel bandwidth.The paper distinguishes these constructions from related Mondrian kernels and random binning despite their close relationship.
  • Relations to Mondrian Kernels and Random Binning: Tile coding samples k from POISSON(λR) and uses a uniformly sampled offset for each feature layer.Here, k denotes the number of cuts in the layer.
  • Relations to Mondrian Kernels and Random Binning: Mondrian grids sample the cut count like tile coding but place cuts independently uniformly, whereas random binning samples inter-cut distance δ from GAMMA(2, λR).Random binning then samples an offset and places the cuts.
  • Relations to Mondrian Kernels and Random Binning: Mondrian features partition all dimensions jointly, while the other three random-feature constructions operate independently by dimension before combining cuts.This is the principal structural distinction among the four feature types.
  • Relations to Mondrian Kernels and Random Binning: BlockOpt finds solutions as well as or better than Add-GP-UCB, Add-MES-R, and Add-MES-G in an experiment averaged over 20 functions.The comparison uses maximum-value information unavailable to the three competing approaches because they lack a credit-assignment strategy.
  • Relations to Mondrian Kernels and Random Binning: For M additive components, the kernel normalization changes from L to LM, reflecting the additive decomposition.The supplied passages state the normalization but do not provide the full surrounding derivation.
  • Relations to Mondrian Kernels and Random Binning: TileGP’s kernel construction is analyzed through Poisson-process cuts, with the no-cut probability between coordinates given by e^−λdR|xAm−x′Am|.The result is used with kernel additivity in the supplied proof passages.

E Experiments

The experiments evaluate EBO’s scalability, acquisition optimization, and application performance across high-dimensional and large-batch settings. EBO is tested against SVI-based BO variants and CEM, including a 20,000-observation regime and robot-control tasks.

  • Experiments: BlockOpt achieves comparable or better results than other acquisition functions for BO with an additive GP.The comparison is summarized in Figure 11.
  • Experiments: EBO’s scalability test uses a fully partitioned 20-dimensional GP with an additive Laplace kernel, up to 1000 Mondrian partitions, and 100 points per partition.These settings define the large-scale scalability experiment.
  • Experiments: EBO is compared with BO-SVI and BO-Add-SVI on four functions sampled from a 50-dimensional GP with an additive kernel.The competing methods use SVI-GP and additive SVI-GP, respectively, with the same acquisition and batch-selection strategy.
  • Experiments: EBO, BO-SVI, BO-Add-SVI, and CEM use 10^4 random initial observations and batches of 100 parameters in the robot-pushing comparison.The experiment repeats each method 10 times.
  • Experiments: 2 × 10^4 additional data points are collected by each method after 200 iterations with batch size 100.This count excludes the 10^4 initializations.
  • Experiments: EBO illustrates a trajectory-optimization result on a reward function that is non-smooth, discontinuous, and concave in selected input dimensions.The supplied passage identifies this as the rover-trajectory experiment and states that BO-Add-SVI uses a randomized decomposition.

F.1 Failure modes of EBO

EBO’s scalability comes with boundary-handling and dimensionality limitations. Region padding is difficult to tune, and the additive acquisition optimization becomes costly beyond many components or several hundred dimensions.

  • F.1 Failure modes of EBO: Choosing the region-padding value ϵ creates a trade-off between computational cost and boundary selections.Large ϵ increases computation within each region, while very small ϵ can produce points on region boundaries; experiments use ϵ = 0.
  • F.1 Failure modes of EBO: More than 50 additive components increase EBO’s computational cost, and functions above a few hundred dimensions become harder to optimize.The paper suggests low-dimensional projection or block coordinate descent as possible directions, without claiming they resolve the limitation.
  • F.1 Failure modes of EBO: Gaussian processes provide confidence-bound estimates but are difficult to scale, motivating EBO’s focus on avoiding variance starvation.This frames the scaling challenge that EBO addresses rather than a failure unique to EBO.

F.3 Future directions

The paper identifies several future directions for improving and extending large-scale Bayesian optimization, including principled strategy design and alternatives to additive Gaussian processes.

  • Future work should theoretically analyze input-space partitioning and batch-worker budget distribution strategies.These strategies determine how the optimization problem and computational resources are divided.
  • More principled variance-prediction methods, potentially beyond Gaussian processes, remain an open direction.
  • The paper calls for better small-scale Bayesian optimization methods and ways to adapt them to large-scale settings.
  • Additive Gaussian processes are only one function-space reduction approach, leaving room for other suitable alternatives.
Loading 1706.01445v4…