PaperlayerView exact revision on arXiv

Source-linked AI summary

Batched High-dimensional Bayesian Optimization via Structural Kernel Learning

Zi Wang, Chengtao Li, Stefanie Jegelka, Pushmeet Kohli

arXiv:1703.01973v2stat.MLcs.LGmath.OC

TL;DR

High-dimensional Bayesian optimization faces computational and statistical challenges that limit its use beyond low-dimensional problems. The paper learns latent additive structure with a Bayesian Gibbs-sampling approach and selects batched evaluations using structured-kernel methods. Experiments show the techniques are effective, with gains over existing methods increasing as input dimensionality grows.

  • Problem

    Bayesian optimization is limited to low-dimensional black-box problems by computational and statistical challenges in high-dimensional settings.

    Source: §1 · p. 1

  • Method

    The method learns a latent additive decomposition with Gibbs sampling and uses the structured kernel to select diverse batches of evaluations.

    Source: §1 · pp. 1–2, §3 · p. 3, §4 · p. 4

  • Results

    The proposed techniques are effective on high-dimensional black-box functions, and their gain over existing methods increases with input dimensionality.

    Source: §6 · p. 8

  • Takeaways & Limitations

    The results have the potential to enable increased use of Bayesian optimization for machine-learning black-box problems with many parameters.

    Source: §6 · p. 8

    Hyperparameter selection, such as choosing βt, is challenging, and tuning βt is suggested as a preliminary way to favor the ground-truth decomposition.

    Source: §5.1 · p. 6

Abstract

from arXiv · show

Optimization of high-dimensional black-box functions is an extremely challenging problem. While Bayesian optimization has emerged as a popular approach for optimizing black-box functions, its applicability has been limited to low-dimensional problems due to its computational and statistical challenges arising from high-dimensional settings. In this paper, we propose to tackle these challenges by (1) assuming a latent additive structure in the function and inferring it properly for more efficient and effective BO, and (2) performing multiple evaluations in parallel to reduce the number of iterations required by the method. Our novel approach learns the latent structure with Gibbs sampling and constructs batched queries using determinantal point processes. Experimental validations on both synthetic and real-world functions demonstrate that the proposed method outperforms the existing state-of-the-art approaches.

1. Introduction

Bayesian optimization is popular for black-box optimization but remains limited to low dimensions by computational and statistical challenges. This paper frames latent structure learning and batched evaluation as ways to address high-dimensional BO.

1. Introduction

  • High-dimensional settings expose computational and statistical challenges that limit Bayesian optimization, despite its popularity for black-box optimization.Earlier work assumes simpler structure, but learning feature subspaces without known dimensions remains computationally difficult.Source: §1 · p. 1
  • The proposed formulation places a prior on structured kernels, enabling simultaneous learning of the function-domain decomposition.Prior approaches face combinatorial partition optimization and use randomized search heuristics.Source: §1 · pp. 1–2
  • The authors extend structured-kernel high-dimensional BO to select batches of evaluations for parallel execution.Prior latent-decomposition methods explore one point at a time, which can make problems requiring many evaluations time-consuming.Source: §1 · p. 2
  • Existing batch BO methods use greedy acquisition or diversity selection, but greedy choices may lie far from an optimum.Prior methods also address high-dimensional BO through low-dimensional or additive structure, while Duvenaud et al. (2013) search explicitly over kernel structures.Source: §1 · p. 2

2. Background

The background assumes a latent additive decomposition of input dimensions and uses Gaussian-process components to model the resulting function. It evaluates BO through cumulative and simple regret, including batch regret.

2. Background

  • The input dimensions are partitioned into disjoint subspaces, and the function is modeled as an additive sum of components.Each component is independently drawn from a Gaussian process, making the aggregate function a GP as well.Source: §2 · p. 2
  • Assuming each f_m is drawn independently from GP(0, k(m)) for all m ∈ [M], the resulting f is also a sample from a GP: f ∼ GP(µ, k).Source: §2 · p. 2
  • BO performance is measured with averaged cumulative regret and simple regret; batch regret uses the best point in each batch.Averaged cumulative regret upper-bounds simple regret.Source: §2 · p. 2

3. Learning Additive Kernel Structure

The method places a Bayesian model over the latent partition of input dimensions and learns that partition alongside optimization. Gibbs sampling produces candidate decompositions, from which the method selects one with the highest data likelihood.

3. Learning Additive Kernel Structure

  • The generative model draws mixing proportions from a Dirichlet distribution and assigns each input dimension to one of M groups.The objective is the sum of Gaussian-process components, each supported on the dimensions assigned to its group.Source: §3 · p. 3
  • The method learns the posterior over decomposition assignments with Gibbs sampling, then selects the sampled decomposition with the highest data likelihood before BO.Each Gibbs step resamples a coordinate assignment; the Gumbel trick efficiently samples from its categorical distribution.Source: §3 · p. 3
  • In practice, the method sets the number of possible groups M equal to the input dimension D.The authors note that a Dirichlet process could instead make the number of groups infinite.Source: §3 · p. 3
  • The graphical model identifies η as the GP-kernel hyperparameter and z as controlling the input-space decomposition..Source: Figure 1 · p. 3

4. Diverse Batch Sampling

Batched BO selects multiple evaluations for parallel observation, while high-dimensional batch selection must balance acquisition value with exploration and diversity. The method uses the learned structure to select diverse points groupwise.

4. Diverse Batch Sampling

  • Batch BO selects B observations in parallel and updates the model after all are observed.This is motivated by settings where evaluations are time-intensive experiments.Source: §4 · p. 3
  • Naive high-dimensional DPP or greedy diversity selection can become intractable, so the proposed approach uses structured kernels for relevant, non-redundant batch selection.The passage illustrates DPP cost on a finite categorical domain and says the method also applies to continuous box-constrained domains.Source: §4 · p. 3
  • Assuming bounded group sizes, sampling a DPP independently within each group gives an exponential speedup over using the full kernel.The method extends from a single sampled decomposition to a distribution by sampling decompositions and selecting points for each individually.Source: §4 · pp. 3–4
  • A DPP assigns higher probability to diverse subsets, while greedy determinant maximization can perform no better than stochastic coordinate combination early in learning.The text reports this comparison in Figure 6 when the GP is not yet approximating the function well.Source: §4 · p. 4
  • The method can combine subspace samples randomly without replacement or greedily by repeatedly selecting the available combination with the highest quality score.Both strategies retain diversity, and both can be paired with a range of quality and acquisition functions.Source: §4 · p. 4

5. Empirical Results

The experiments first assess Gibbs-based learning of additive decompositions, then evaluate diverse batched Bayesian optimization on synthetic and real-world tasks.

5.1. Effectiveness of Decomposition Learning

  • Decomposition recovery improves with more observed data, and Gibbs can converge to the ground truth with enough data for relatively small dimensions; higher dimensions require more data.The recovery experiment also evaluates whether dimension pairs are correctly grouped or separated.Source: Table 1 · p. 4, §5.1 · p. 5, Table 2 · p. 5
  • Gibbs outperforms both partial-learning methods and sometimes beats the known decomposition at higher dimensions, while remaining comparable to Known in the synthetic comparison.The comparison includes 2, 10, 20, and 50-dimensional synthetic additive functions.Source: Figure 2 · p. 5, §5.1 · p. 6
  • Changing partitions across iterations can create implicit exploration, while merging true parts can increase UCB exploration; the authors say Gibbs balances exploration and exploitation.They note that more exploration is not always better and that tuning β_t may help the ground-truth decomposition perform best.Source: §5.1 · p. 6
  • On the 14-parameter robot-pushing task, Gibbs-based decomposition learning outperforms partial learning, no partitions, and full partitioning.The authors suggest the task may have additive structure in some regions, such as when the robot hands are relatively distant.Source: Figure 4 · p. 6, §5.1 · p. 6

5.2. Diverse Batch Sampling

  • Across synthetic and Walker benchmarks, diverse batch methods outperform random sampling; Batch-UCB-DPP-Fnc is best among the four methods on Walker data at B = 5.On synthetic functions, the batch methods perform comparably; on Walker data, Batch-UCB-DPP-Fnc performs best among them.Source: §5.2 · pp. 7–8, Figure 5 · p. 7, Figure 6 · p. 8
  • With larger batches, differences among batch-selection approaches become more pronounced, and Batch-UCB-DPP-Fnc performs somewhat better, particularly at larger batch sizes.The batch-size comparison uses the 14-dimensional Robot dataset with B ∈ {5, 10}.Source: §5.2 · p. 8

6. Conclusion

The paper combines latent-structure inference with batch Bayesian optimization, and reports that its gains over existing methods increase with input dimensionality. On a 14-parameter robot-pushing task, Batch-UCB-DPP-Fnc performs slightly better than four other diverse batch-sampling variants, with a larger gap at batch size 10 than 5.

6. Conclusion

  • Batch-UCB-DPP-Fnc performs a bit better than four other diverse batch-sampling variants on robot pushing, with the gap increasing at batch size 10.The experiment tunes 14 parameters and compares batch sizes 5 and 10.Source: Figure 7 · p. 8
  • The proposed techniques are effective on high-dimensional black-box functions, and their gains over existing methods increase as input dimensionality grows.The paper presents latent-structure inference combined with batch Bayesian optimization as its two solutions.Source: §6 · p. 8

A. Add-UCB-DPP-BBO Algorithm

The algorithm framework presents four Add-UCB-DPP-BBO variants and can accommodate acquisition and quality functions beyond UCB.

A. Add-UCB-DPP-BBO Algorithm

B. Additional experiments

This section introduces additional experimental details.

B. Additional experiments

B.1. Optimization of the Acquisition Functions

The acquisition function is split by additive component and optimized separately, using random low-dimensional starts for gradient descent. The authors report strong performance below five dimensions and the familiar optimization difficulties as dimensionality grows.

B.1. Optimization of the Acquisition Functions

  • The acquisition function is decomposed into M subacquisition functions, one for each part, and these are optimized separately.Source: §B.1 · p. 10
  • 10,000 randomly sampled low-dimensional points are evaluated, and the best starts gradient descent in the search space.The search space is the range of the box on R^|A_m|.Source: §B.1 · p. 10
  • Below five dimensions, this approach optimizes functions very well; with more dimensions, high-dimensional BO and global nonconvex optimization difficulties arise.Source: §B.1 · p. 10

B.2. Effectiveness of Decomposition Learning

The section evaluates learned decompositions through synthetic and real-world optimization results. Learning can improve regret, while performance depends on how well the function fits the additive-structure assumption.

B.2. Effectiveness of Decomposition Learning

  • Decomposition evaluation includes Rand Index and post-burn-in probabilities of correctly grouping or separating dimension pairs.Source: §B.2 · p. 10
  • The reported decomposition quality is empirically not very sensitive to α when it is below the total number of dimensions.The paper attributes this to log data likelihood mattering more than log(|A_m|+α); reported results use α = 1.Source: §B.2 · p. 10
  • For D = 20 and 30, simple regret improves after newly observed data are used to learn a partition.The full synthetic comparisons include Known, Gibbs, PL-1, PL-2, FP, and NP.Source: §B.2 · p. 10
  • On the 25-parameter walker, Gibbs-L performs slightly better than other methods, while unconstrained Gibbs performs similarly to no partition.The function lacks additive structure; limiting each group to at most two dimensions yields the Gibbs-L result.Source: §B.2 · p. 10
  • Gibbs, PL-1, PL-2, and FP all performed relatively well on this function, suggesting that exploiting additive structure may benefit Bayesian optimization even when the function itself is not additive.Source: §B.2 · p. 11

B.3. Diverse Batch Sampling

The experiments compare batch-sampling strategies and decomposition-learning variants. Batch methods outperform random sampling on synthetic functions, while constrained Gibbs performs slightly better than other methods on the walker task.

B.3. Diverse Batch Sampling

  • On the walker function, Gibbs-L performs slightly better than PL-2 and FP, whereas unconstrained Gibbs performs poorly because it learns large groups.Source: Figure 9 · p. 12
  • Gibbs achieves results comparable to Known and performs much better than PL-1 and PL-2; sampling more partitions helps PL-1 find a better one.Source: Figure 10 · p. 13
  • Batch-UCB-PE, Batch-UCB-DPP, Batch-UCB-PE-Fnc, and Batch-UCB-DPP-Fnc perform comparably and outperform random sampling by a large gap.Source: Figure 11 · p. 14
Loading 1703.01973v2…