PaperlayerView exact revision on arXiv

Source-linked AI summary

High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspaces

David Eriksson, Martin Jankowiak

arXiv:2103.00349v2cs.LGstat.ML

TL;DR

High-dimensional BO must define and infer suitable surrogate models when only a few evaluations are available. The paper introduces SAASBO, which uses sparse axis-aligned GP priors and Hamiltonian Monte Carlo to identify relevant subspaces. SAASBO performs strongly across synthetic and real-world problems, including tasks with up to 388 dimensions, without problem-specific hyperparameters.

  • Problem

    High-dimensional BO needs surrogate models that are sufficiently parsimonious to infer from few queries without overfitting.

  • Method

    SAASBO uses a sparsity-inducing axis-aligned GP function prior with NUTS inference to identify relevant low-dimensional subspaces.

  • Results

    SAASBO outperforms strong BO baselines on several synthetic and real-world problems, including problems with as many as 388 dimensions, without problem-specific hyperparameters.

  • Takeaways & Limitations

    The approach preserves input-domain structure, adapts with little hyperparameter sensitivity, and accommodates input and output constraints.

  • Takeaways & Limitations

    Making the most of the SAAS function prior may require a decision-theoretic framework better suited to high-dimensional settings.

Abstract

from arXiv · show

Bayesian optimization (BO) is a powerful paradigm for efficient optimization of black-box objective functions. High-dimensional BO presents a particular challenge, in part because the curse of dimensionality makes it difficult to define -- as well as do inference over -- a suitable class of surrogate models. We argue that Gaussian process surrogate models defined on sparse axis-aligned subspaces offer an attractive compromise between flexibility and parsimony. We demonstrate that our approach, which relies on Hamiltonian Monte Carlo for inference, can rapidly identify sparse subspaces relevant to modeling the unknown objective function, enabling sample-efficient high-dimensional BO. In an extensive suite of experiments comparing to existing methods for high-dimensional BO we demonstrate that our algorithm, Sparse Axis-Aligned Subspace BO (SAASBO), achieves excellent performance on several synthetic and real-world problems without the need to set problem-specific hyperparameters.

1 INTRODUCTION

High-dimensional BO is difficult because flexible surrogate models are hard to infer from few evaluations. SAASBO addresses this by using sparse axis-aligned GP models with NUTS inference to identify relevant subspaces and optimize efficiently.

  • High-dimensional BO remains challenging because overly flexible surrogate models can overfit when only a small number of evaluations is available.
  • SAASBO targets black-box optimization with hundreds of variables and only a few hundred objective queries.
  • The method uses Gaussian process surrogate models on sparse axis-aligned subspaces as a compromise between flexibility and parsimony.
  • SAASBO proposes a sparsity-inducing SAAS function prior and combines it with NUTS for inference.
  • SAASBO quickly identifies relevant low-dimensional subspaces, leading to sample-efficient Bayesian optimization.
  • SAASBO outperforms strong baselines on synthetic and real-world problems with up to 388 dimensions without problem-specific hyperparameters.

2 RELATED WORK

High-dimensional BO methods commonly exploit low-dimensional structure through projections, embeddings, additive decompositions, or constrained acquisition optimization. SAASBO instead works in the full space with a sparsity-inducing prior.

  • Existing high-dimensional BO research proposes varied surrogate-modeling and acquisition strategies.
  • Random-projection methods such as REMBO and ALEBO map low-dimensional points into the original space, while other methods learn linear or nonlinear embeddings.
  • Additive methods assume the objective is a sum of low-dimensional components, separating the input space into independent domains.
  • Some methods address boundary over-exploration by modifying the kernel or constraining acquisition optimization to interiors or one-dimensional lines.
  • COMBO combines a sparsity-inducing prior with finite feature expansions for combinatorial search spaces.
  • Finite feature expansions are unsuitable for real-valued inputs because the curse of dimensionality limits the flexibility of the resulting function prior.
  • Unlike many Bayesian approaches, evolutionary algorithms do not rely on Bayesian surrogate models and often require thousands of evaluations.

3 BACKGROUND

The paper models costly, noise-free black-box objectives with Gaussian processes and uses expected improvement to select queries. GP kernels provide flexible priors and uncertainty estimates, while EI balances exploration and exploitation.

  • The optimization problem is minimizing a costly, noise-free black-box function on [0, 1]^D without gradient information and with at most a few hundred evaluations.
  • Gaussian processes provide non-parametric function priors with strong flexibility and uncertainty quantification for Bayesian optimization.
  • The RBF kernel uses inverse squared length scales ρ_i and additional hyperparameters collectively denoted by ψ.
  • For scalar regression, the GP models latent function values and real-valued targets using inputs, a kernel matrix, and a likelihood variance.
  • For noise-free functions, the likelihood variance is set to a small constant, and the GP marginal likelihood can be computed in closed form.
  • The GP posterior at a query point is Normal with mean μ_f(x*) and variance σ_f(x*)^2.
  • Expected improvement measures the expected positive improvement over the best observed objective value and can be evaluated in closed form for the GP.

4 BAYESIAN OPTIMIZATION WITH SPARSE AXIS-ALIGNED SUBSPACES

SAASBO uses a sparsity-inducing Gaussian-process prior to model high-dimensional black-box functions on sparse axis-aligned subspaces. It combines NUTS or MAP inference with posterior-averaged expected improvement, while remaining most suitable for moderate numbers of observations.

  • 4.1 SAAS FUNCTION PRIOR: SAASBO assumes a hierarchy of feature relevances and uses a structured prior to induce sparsity in inverse squared length scales.Most dimensions are consequently turned off, while the prior retains flexible smooth non-linear GP functions.
  • 4.1 SAAS FUNCTION PRIOR: The SAAS prior uses half-Cauchy shrinkage on the global parameter τ and dimension-specific length scales ρ_i, with α controlling shrinkage.The default setting is α = 0.1; noise-free objectives use σ^2 → 10^-6, while noisy objectives can receive a weak prior on σ^2.
  • 4.2 INFERENCE: Inference uses NUTS for posterior samples or MAP for a faster but less faithful posterior approximation, integrating out the latent function analytically.MAP produces point estimates for selected τ values and chooses among them using leave-one-out predictive log likelihood.
  • 4.2 INFERENCE: Posterior sampling costs O(N^3D), making SAASBO most suitable for moderate datasets with approximately N ≲500 observations.This inherits the GP scalability bottleneck and reflects the computational cost of gradient terms involving D dimensions.
  • 4.3 ACQUISITION STRATEGY: Expected improvement is computed by averaging its value over posterior samples of the GP kernel hyperparameters before optimizing the acquisition function.The resulting objective is differentiable in x and is optimized from Sobol-generated starting points using L-BFGS-B.

5 EXPERIMENTS

Experiments show that SAASBO provides useful high-dimensional GP fits, identifies relevant subspaces quickly, and performs strongly across synthetic and real-world optimization problems without problem-specific hyperparameters.

  • 5.1 THE SAAS PRIOR PROVIDES GOOD MODEL FIT IN HIGH DIMENSIONS: Only the SAAS-prior GP provides a good fit on the D = 124 vehicle design and D = 388 SVM problems.The comparisons use 100 training points for vehicle design, 50 for SVM, and 100 test points for both.
  • 5.2 SAASBO CAN QUICKLY IDENTIFY THE MOST RELEVANT DIMENSIONS: NUTS outperforms MAP by a considerable margin, although both methods reliably identify Branin’s two relevant dimensions after ∼20 −30 evaluations.The authors attribute NUTS’s robustness to averaging expected improvement over multiple GP kernel-hyperparameter samples.
  • 5.2 SAASBO CAN QUICKLY IDENTIFY THE MOST RELEVANT DIMENSIONS: SAASBO-NUTS shows minimal optimization-performance dependence on α, while smaller α values favor smaller subspaces and larger values favor larger subspaces.After ∼20 function evaluations, the posterior concentrates on the two relevant dimensions.
  • 5.4 SYNTHETIC PROBLEMS: SAASBO and ALEBO-5 perform best on Branin, SAASBO performs best on Hartmann, and SAASBO, HeSBO-5, HeSBO-10, and ALEBO-5 have similar final performance on Rosenbrock.ALEBO and HeSBO show significant sensitivity to the embedded subspace dimension on at least two of three problems.
  • 5.7 VEHICLE DESIGN: SAASBO outperforms other methods by a large margin on the D = 124 MOPTA vehicle-design problem, while TuRBO and CMA-ES outperform the remaining methods.The constrained problem is converted to a scalar objective using a soft penalty, and the flexible SAAS prior performs well despite the absence of obvious low-dimensional structure.

6 DISCUSSION

SAASBO works directly in the full high-dimensional space while using a sparsity-inducing prior to identify a smaller relevant subspace. Its NUTS-based inference is computationally tunable, but fully exploiting the prior may require better decision-theoretic methods.

  • SAASBO works in the full input space and uses a sparsity-inducing function prior to mitigate high-dimensionality challenges.
  • Making the most of the SAAS prior may require a decision-theoretic framework better suited to high-dimensional settings.
  • Reducing NUTS settings from (512, 256, 16) to (128, 128, 8) causes only a relatively marginal performance drop on Branin.
  • NUTS inference quickly identifies relevant low-dimensional structure, while its sampling settings control computation rather than the function prior.
  • SAASBO can be accelerated through warm-started mass adaptation, fitting the GP every M iterations, and parallelizing acquisition optimization.
  • Continuous sparsity avoids the 2^D discrete search required by binary relevance variables and permits gradient-based posterior exploration.

C RUNTIME EXPERIMENT

The runtime experiment measures average per-iteration cost for SAASBO and baseline methods on a 100-dimensional Branin problem. SAASBO has moderate computational overhead when objective evaluations are expensive.

  • SAASBO requires more time per iteration than methods such as TuRBO and HeSBO, but its overhead is relatively moderate when black-box evaluations are expensive.
  • Runtime is measured per iteration on Branin embedded in 100 dimensions, using 10 initial points and 50 total evaluations.Measurements use a 2.4 GHz 8-Core Intel Core i9 CPU with 32 GB of RAM.

D.1 MODEL FITTING

With a Matérn-5/2 kernel, only the sparsity-inducing SAAS prior provides a good fit in the reproduced model-fitting experiment. SAASBO also rapidly identifies the SVM’s most important regularization hyperparameters.

  • Figure 7 compares MLE, weak-prior NUTS, and SAAS-prior NUTS GP fits using a Matérn-5/2 kernel.The vehicle-design and SVM problems use 100 and 50 training points, respectively, with 100 test points each.
  • Only the sparsity-inducing SAAS prior provides a good fit, showing that non-sparse GP overfitting is not fixed by changing kernels.
  • SAASBO consistently finds the SVM’s three regularization hyperparameters soon after the initial Sobol phase.The fourth most relevant dimension is a length scale.

D.3 SVM ABLATION STUDY

The SVM ablation finds poor performance for a non-sparse prior but similar performance for RBF and Matérn-5/2 kernels. On rotated Hartmann functions, SAASBO remains competitive despite its axis-aligned assumption.

  • SVM ablation: The non-sparse function prior performs very poorly on the SVM problem, while RBF and Matérn-5/2 kernels yield similar BO performance.
  • Rotated Hartmann: SAASBO outperforms other methods on rotated Hartmann functions despite the strained axis-aligned assumption.It quickly identifies important parameters in the rotated space, and its worst-case performance is better across all tested projection dimensionalities.

E ADDITIONAL EXPERIMENTAL DETAILS

The experiments use α = 0.1 and an RBF kernel by default, with specified exceptions for selected experiments.

  • α = 0.1 is used in all experiments except the experiment in Sec. 5.2 depicted in Fig. 2.
  • An RBF kernel is used in all experiments except those depicted in Fig. 7 and Fig. 9.
  • The experiment in Sec. 5.2 and the experiments depicted in Fig. 7 and Fig. 9 use exceptions to these defaults.

E.1 MODEL FIT EXPERIMENT

The model-fit experiment evaluates SAASBO using separate training and test runs in 100 dimensions and constructs 30-dimensional datasets with relevant and redundant variables.

  • The experiment uses data from two SAASBO runs in D = 100, assigning one run to training and the other to testing.Each run contains N = 100 datapoints.
  • Each of the training and test datasets contains N = 100 datapoints.
  • The D = 30 datasets retain 6 relevant dimensions and add 24 randomly chosen redundant dimensions.All remaining dimensions are dropped.

E.2 INFERENCE AND HYPERPARAMETER COMPARISON EXPERIMENT

The experiments compare SAASBO with multiple optimization baselines across synthetic and real-world problems, including high-dimensional and rotated settings, while documenting implementation choices and inference shortcuts.

  • Baselines and settings: SAASBO is compared with ALEBO, CMA-ES, EBO, HeSBO, SMAC, Sobol, and TuRBO.ALEBO and HeSBO use BoTorch implementations with settings from Letham et al. (2020).
  • Baselines and settings: Synthetic problems use embedding dimensionalities de = 5 and de = 10.These correspond to heuristics similar to de = d and de = 2d.
  • Synthetic problems: The synthetic suite includes Branin, Hartmann, and Rosenbrock embedded in 100-dimensional spaces.The original functions have dimensions 2, 6, and 3, respectively.
  • Real-world problems: The real-world experiments include rover trajectory optimization, the 385-dimensional CT slice SVM problem, and the 124-dimensional MOPTA08 vehicle design problem.MOPTA08 minimizes vehicle mass subject to 68 performance constraints, converted here into a penalized unconstrained objective.
  • Rotated function: The rotated Hartmann experiment uses d = 6 and projection dimensions dp ∈{6, 18, 30}; SAASBO outperforms the other methods.It also quickly identifies the most important parameters in the rotated coordinate system.
  • Inference settings: After iteration t > 150, SAASBO retains L = 8 NUTS samples to reduce runtime, although this may reduce inferred-GP accuracy.The paper reports that SAASBO still performs very well and outperforms other methods by a large margin on this problem.
Loading 2103.00349v2…