PaperlayerView exact revision on arXiv

Source-linked AI summary

Vanilla Bayesian Optimization Performs Great in High Dimensions

Carl Hvarfner, Erik Orm Hellsten, Luigi Nardi

arXiv:2402.02229v5cs.LGstat.ML

TL;DR

High-dimensional Bayesian optimization is challenged by low correlation and difficult surrogate modeling, while existing approaches commonly impose simplifying assumptions on objectives. The paper analyzes these complexity-related issues and adjusts the GP lengthscale prior. It reports that vanilla BO then substantially outperforms state-of-the-art high-dimensional methods on real-world tasks.

  • Problem

    High dimensionality makes high-variance regions exponentially large and GP surrogate modeling difficult, motivating methods that improve Bayesian optimization in this setting.

    Source: §1 · p. 1

  • Method

    The paper analyzes high-dimensional BO through model complexity and scales the GP lengthscale prior to reduce assumed complexity without conventional structural restrictions on the objective.

    Source: §1 · p. 1

  • Results

    The adjusted vanilla BO substantially outperforms state-of-the-art high-dimensional BO methods across a wide range of real-world tasks.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The authors conclude that a simple prior adjustment makes vanilla BO performant for high-dimensional tasks, including dimensionalities well into the thousands.

    Source: §1 · p. 1

    The problem setup assumes pointwise observations perturbed by Gaussian noise.

    Source: §2.2 · p. 2

Abstract

from arXiv · show

High-dimensional problems have long been considered the Achilles' heel of Bayesian optimization algorithms. Spurred by the curse of dimensionality, a large collection of algorithms aim to make it more performant in this setting, commonly by imposing various simplifying assumptions on the objective. In this paper, we identify the degeneracies that make vanilla Bayesian optimization poorly suited to high-dimensional tasks, and further show how existing algorithms address these degeneracies through the lens of lowering the model complexity. Moreover, we propose an enhancement to the prior assumptions that are typical to vanilla Bayesian optimization algorithms, which reduces the complexity to manageable levels without imposing structural restrictions on the objective. Our modification - a simple scaling of the Gaussian process lengthscale prior with the dimensionality - reveals that standard Bayesian optimization works drastically better than previously thought in high dimensions, clearly outperforming existing state-of-the-art algorithms on multiple commonly considered real-world high-dimensional tasks.

1. Introduction

High dimensionality challenges Bayesian optimization through low correlation and difficult GP modeling, while existing high-dimensional methods commonly reduce assumed objective complexity with structural restrictions. The paper diagnoses complexity-related failure modes and proposes scaling the GP lengthscale prior to improve vanilla BO without those restrictions.

1. Introduction

  • High dimensionality makes high-variance regions exponentially large and increases the GP surrogate's parameters relative to observations, hindering accurate modeling.The introduction situates these difficulties within the curse of dimensionality.Source: §1 · p. 1
  • Existing high-dimensional BO approaches commonly restrict the objective, contracting the search space to shorten distances and increase correlations that inform GP inference.The paper frames these approaches as reducing a priori assumed complexity.Source: §1 · p. 1
  • The paper analyzes high-complexity failure modes, relates existing high-dimensional BO classes to complexity reduction, and proves that uninformed-model EI does not explore along the boundary.The EI result is presented in contrast to claims by Swersky (2017) and Oh et al. (2018).Source: §1 · pp. 1–2
  • The proposed plug-and-play lengthscale-prior adjustment reduces assumed complexity and substantially outperforms state-of-the-art high-dimensional BO methods across real-world tasks.The authors report that the approach works across a wide range of dimensionalities, including into the thousands.Source: §1 · pp. 1–2

2. Background

The background introduces Gaussian-process surrogates and Bayesian optimization, then uses maximal information gain (MIG) to characterize assumed model complexity. It describes how kernel choices, priors, and correlation affect inference and optimization difficulty.

2.1. Gaussian Processes

  • A Gaussian process defines a distribution over functions through its mean and covariance, with the covariance determining the modeled dynamics under a constant mean.The text also describes automatic relevance determination (ARD) as individually scaling dimensions using lengthscale hyperparameters.Source: §2.1 · p. 2

2.2. Bayesian Optimization

  • Bayesian optimization seeks a black-box function's maximizer through pointwise, Gaussian-noise-perturbed observations, using acquisition functions to balance exploration and exploitation.Expected Improvement and LogEI are cited as common acquisition functions.Source: §2.2 · p. 2

A Working Definition of ”Vanilla” BO

  • The paper's vanilla BO setup uses standardized outputs, an RBF or Matérn 5/2 kernel with ARD lengthscales, EI-family acquisition, and multistart gradient-based acquisition optimization.Practical BO frameworks commonly use MAP hyperparameter estimation, with priors often placing high density on low lengthscales.Source: A Working Definition of ”Vanilla” BO · p. 2

2.3. The Maximal Information Gain

  • MIG measures the maximum information obtainable about a function from a fixed number of queries and serves as a measure of assumed complexity.For fixed observation noise, it depends on the covariance matrix, which reflects the kernel, dimensionality, and kernel hyperparameters.Source: §2.3 · pp. 2–3
  • When a complex model has low correlations, its MIG can track the independent-kernel reference for many queries, indicating substantial remaining information and difficult optimization.The figure caption reports that the complex model's MIG closely follows the reference for 20 samples; the text describes capacity for 20 almost-maximal-variance acquisitions even for a one-dimensional objective.Source: Figure 1 · p. 3, §2.3 · p. 3
  • Nearly linear MIG growth signals regions that remain almost independent of collected data, whereas small growth suggests little information remains to be learned from another query.The figure's vertical line marks the current iteration.Source: §2.3 · p. 3, Figure 1 · p. 3

3. Related Work

Related high-dimensional BO methods reduce complexity through assumptions about subspaces, additive structure, search locality, or search-space geometry. The paper distinguishes its ambient-space approach from these structural restrictions.

3. Related Work

  • The paper groups high-dimensional BO methods by the structural assumptions they impose on the objective to address optimization limitations.The approaches are presented as reducing complexity through assumptions on the objective or search space.Source: §3 · p. 3, Local Bayesian optimization · p. 4
  • Subspace methods assume a lower-dimensional representative space, either axis-aligned or non-axis-aligned, while explicit variable selection identifies important variables.These methods optimize using a reduced set of dimensions or variables.Source: §3 · p. 3
  • Additive Gaussian-process methods decompose the objective into low-dimensional component functions, each assumed to depend on only a small subset of variables.Source: §3 · p. 3

Local Bayesian optimization

  • Local BO methods adaptively restrict the search region, reducing modeled variation and susceptibility to the model.Restricting optimization to a smaller part of the search space simplifies optimization.Source: Local Bayesian optimization · pp. 3–4
  • Cylindrical kernels transform search-space geometry, expanding its center and shrinking its boundaries to address hypercube growth.Source: Local Bayesian optimization · p. 4
  • Unlike SAASBO and BOCK, the paper's approach optimizes in the ambient space without their specific structural assumptions; Elastic GPs also avoid simplifying model assumptions.Elastic GPs consider multiple GP lengthscales during acquisition optimization.Source: Local Bayesian optimization · p. 4

4. Pitfalls of High-Complexity Assumptions

The section links high dimensionality to increasing model complexity, then examines the resulting failure mode of expected improvement (EI) and how existing high-dimensional BO methods reduce complexity. It argues that EI’s behavior under low correlation differs from the commonly described boundary-exploration issue.

4.1. Complexity and Dimensionality

  • For D = 18, complexity visibly diverges from an independent kernel after about 3,000 samples, while for D = 24, 5,000 samples are insufficient to distinguish them.The covariance then resembles an identity matrix, making global modeling uninformative and inference between observed points difficult.Source: Figure 2 · p. 4, §4.1 · p. 4

4.2. The Boundary Issue Revisited

  • When model correlation is low, EI favors queries substantially correlated with the incumbent rather than uninformed, high-variance regions.In high-complexity settings, this can keep queries near the incumbent and produce exploitative, local-search-like behavior.Source: §4.2 · p. 5
  • Frequent boundary queries can still occur when fitted lengthscales are very long along one or more dimensions, including when lengthscales are learned by maximum likelihood.Such candidates can be low-variance and highly correlated with existing data even when they lie on the boundary.Source: §4.2 · p. 5

4.3. Complexity of Existing HDBO

  • At 1,000 data points, REMBO reduces complexity most, BOCK follows, and the proposed full-dimensional GP’s complexity growth flattens at a rate similar to BOCK.By contrast, vanilla BO with fixed lengthscales approaches independent complexity at about 20 dimensions.Source: Figure 4 · p. 6, §4.3 · p. 6
  • The compared HDBO methods use different assumptions to reach the same end: reducing model complexity to manageable levels.The section cautions that low complexity alone is not desirable; the model should have the lowest complexity that still aligns sufficiently with the objective.Source: §4.3 · pp. 5–6

5. Low-complexity High-dimensional Bayesian Optimization

The paper modifies standard BO’s GP lengthscale prior to keep complexity manageable as dimensionality rises, without imposing structural restrictions on the objective. It also fixes the signal variance to maintain its scale during optimization.

5. Low-complexity High-dimensional Bayesian Optimization

  • The proposed plug-and-play change scales the GP lengthscale prior with problem dimensionality to keep model complexity nearly constant as dimensions increase.The method also draws on findings about GPs in over-parameterized regimes to calibrate signal variance.Source: §5 · p. 6

5.1. Ensuring Meaningful Correlation

  • Increasing lengthscales with dimensionality counteracts the growth in distances that drives complexity for stationary kernels.The passage describes adjusting the lengthscale-prior parameterization, for example by scaling the μ term of a LogNormal prior.Source: §5.1 · p. 6
  • The method assumes the objective is simple enough to model globally at any dimensionality, while MAP estimation can still adjust lengthscales when variables differ in importance.The change does not add hyperparameters to a MAP-based BO setup and can also be applied to a Gamma prior.Source: §5.1 · p. 6

5.2. Calibrating Epistemic Uncertainty

  • The method fixes signal variance at 1 for standardized observations so it does not diminish over optimization iterations.Repeated data renormalization can otherwise further decrease the signal variance and reinforce selection of highly correlated queries.Source: §5.2 · p. 7

6. Results

Across sparse synthetic, mid-dimensional, and high-dimensional benchmarks, DSP performs competitively or better than established methods. Its high-dimensional results do not depend on consistently identifying active variables; the authors attribute performance to calibrated model complexity and inference.

6. Results

  • The evaluation compares DSP with subspace, local-BO, additive, variable-selection, and CMA-ES baselines.The methods use their official repositories, except SAASBO, which is run through Ax.Source: §6 · p. 7

6.1. Sparse Synthetic Test Functions

  • On sparse synthetic functions, SAASBO performs best on average and Vanilla BO ranks second, while running in a small fraction of SAASBO’s time.The authors say SAASBO’s sparse-lengthscale assumption aligns with these test functions.Source: §6.1 · p. 7, Figure 5 · p. 8

6.2. A Plug-in on Mid-Dimensional Tasks

  • On mid-dimensional tasks, DSP is competitive with or outperforms TuRBO and performs at least as well as the conventional Γ prior on all five tasks.The figure reports substantially better performance than the Γ prior on four of five tasks.Source: §6.2 · p. 7, Figure 6 · p. 8

6.3. High-dimensional Optimization Tasks

  • DSP does not consistently identify active variables on the 388D SVM task, yet calibrated complexity supports meaningful inference across dimensions.The authors say identifying active variables may help optimization but is not required for calibrated BO.Source: §6.3 · pp. 8–9
  • DSP is best by a substantial margin on Lasso-DNA and Humanoid and achieves top-two performance on the other high-dimensional tasks.On MuJoCo Ant, Bounce benefits from low-dimensional initialization and samples near the search-space center after DoE.Source: §6.3 · p. 8, Figure 7 · p. 9

7. Conclusion and Future Work

The conclusion argues that high-dimensional BO is hindered by assumed objective complexity rather than dimensionality itself. It presents dimensionality-scaled assumptions as a way to make complexity manageable, while retaining a role for tailored methods when their structural assumptions are supported by prior knowledge.

7. Conclusion and Future Work

  • The authors argue that BO’s high-dimensional hindrance stems from assumed objective complexity, not dimensionality, and that minor assumption changes make complexity scaling manageable.They report Vanilla BO outperforming state-of-the-art methods on problems with dimensions into the thousands.Source: §7 · p. 9
  • Tailored high-dimensional BO methods may be superior when prior knowledge supports effective-subspace or additive structure, or when non-stationarity facilitates local modeling.The authors caution against imposing those restrictions merely out of necessity.Source: §7 · p. 9

A. Experimental Setup

The appendix outlines experimental setup, reports SAASBO’s compute constraints, and specifies the baseline instantiations used for complexity comparisons.

A. Experimental Setup

  • The setup appendix makes the authors’ code publicly available.It provides the experimental setup and baseline-method specifics.Source: A. Experimental Setup · p. 15

A.1. SAASBO

  • SAASBO’s expensive model fitting and acquisition passes lead to a 500-evaluation cap and retraining once every four iterations.A later SVM model fit takes upwards of five minutes on four CPUs.Source: §A.1 · p. 15

A.2. Complexity Comparison Setup

  • The complexity comparison specifies cylindrical-kernel, AddGP, local-GP, and random-embedding baseline instantiations.These use a degree-3 angular kernel, randomized sequential grouping, a trust region sized from the lengthscale, and an embedding-derived lengthscale, respectively.Source: §A.2 · p. 15

B. Benchmarks

The section specifies synthetic and real-world benchmark sets, then examines locality and the boundary issue under conventional BO. Under stated assumptions, EI increases with correlation to the incumbent when the threshold in the analysis is met.

B. Benchmarks

  • The synthetic and real-world benchmark tables define the two benchmark groups; Levy offsets active dimensions, giving diagonal-search methods an arguably unrealistic advantage.The BAxUS SVM variant also uses a smaller subset than the original benchmark, and comparisons suggest their objective functions differ substantially.Source: B. Benchmarks · p. 15, Table 1 · p. 15, Table 2 · p. 16

C. The Locality Issue

  • The locality discussion frames high-complexity BO as prone to local search, while noting that several frameworks use similar short-lengthscale priors.The section presents this as a practical issue for conventional BO rather than as a property of one specific framework.Source: C. The Locality Issue · pp. 15–16

C.1. Theory: Non-existence of the Boundary Issue

  • Under the proposition’s assumptions—y_max > c, K = I, and a candidate correlated with at most one observation—EI is strictly increasing in ρ when ŷ_max ≥ ρ.Here, ρ is the correlation between the candidate query and the incumbent; the proposition concerns maximizing EI.Source: §C.1 · pp. 16–17

C.2. The Locality Issue in Practice

In practice, short-lengthscale, high-complexity models can keep BO queries local, even when large-variance regions remain available. DSP maintains more balanced query distances and shows the strongest initial performance across the real-world tasks discussed.

C.2. The Locality Issue in Practice

  • In the short-lengthscale example, EI never selects a large-variance region as best, even after repeated data renormalization.The locality behavior is illustrated on low-dimensional examples whose complexity was increased by shortening the model lengthscale.Source: §C.2 · pp. 17–18

C.3. The Boundary Issue through the Lens of Locality

  • A long lengthscale in one dimension lets near-maximal EI queries span boundaries while remaining highly correlated with the incumbent, so their apparent distance does not imply classical exploration.The green-line candidates are within a factor of 10^-5 of the maximum EI.Source: §C.3 · p. 18, Figure 10 · p. 19
  • Conventional MAP almost exclusively makes local queries after design of experiments, while DSP maintains a balance between exploration and exploitation despite comparable final performance.The comparison is shown for the non-embedded Hartmann 6D example; conventional MAP behaves like an initial random search followed by local search.Source: §C.3 · pp. 18–19, Figure 11 · p. 19

D. Low-budget Performance

  • Across the real-world tasks, DSP gives the strongest initial performance and improves rapidly after initialization, without identifying a subset of active variables.The figure describes a pronounced early performance jump after the design-of-experiments phase.Source: Figure 12 · p. 20, D. Low-budget Performance · p. 20

E. Ablation Studies

The ablations examine sensitivity to complexity, its uncertainty, and learning the signal variance, alongside comparisons with conventional MAP and MLE. Overall, the enhanced vanilla BO remains performant across a broad complexity range and robust to uncertainty changes, with some adverse cases at low assumed complexity or learned outputscale.

E. Ablation Studies

  • Vanilla BO remains highly performant across almost an order of magnitude of assumed complexity and is generally robust to uncertainty changes, though too-low complexity can sometimes hurt.The low-complexity variant performs slightly worse on average in the synthetic tests, while substantially higher assumed complexity can hurt SVM performance.Source: E. Ablation Studies · p. 20, Figure 17 · p. 23, Figure 18 · p. 23

E.2. Fixed Complexity - Varied uncertainty

  • Changing uncertainty while keeping the prior mode fixed leaves performance generally robust, with higher uncertainty marginally worse on SVM.Changing uncertainty affects how readily the model can disregard apparently unimportant dimensions or identify important ones.Source: E. Ablation Studies · p. 20, §E.2 · p. 21, Figure 15 · p. 22

E.1. Conventional MAP and MLE

  • MLE hyperparameter fitting is unstable on higher-dimensional tasks, while conventional MAP can match or exceed DSP on some tasks but suffers from local search behavior.The stabilized MLE variant is competitive on many tasks; the figures report fitting instability for MLE and compare methods on synthetic and real-world benchmarks.Source: §E.1 · pp. 20–21, Figure 13 · p. 21, Figure 14 · p. 21

E.3. Varied Complexity - Fixed uncertainty

  • The complexity ablation varies the prior’s default lengthscales; a substantially higher assumed complexity may harm performance, as shown for SVM.Increasing μ raises default lengthscales and corresponds to assuming lower complexity; the tested shifts of 0.5 change them by a factor of 1.65.Source: §E.3 · p. 21, Figure 18 · p. 23, Figure 17 · p. 23

F. Learning the signal variance

  • Learning signal variance yields comparable performance but is marginally less stable, and learned outputscale is associated with more exploitative, local behavior.The outputscale shrinks over optimization; fixed-outputscale variants can still vary because data normalization changes over time.Source: F. Learning the signal variance · pp. 21–22

F.1. Learning σ2

  • With learned signal variance, DSP can be competitive on the tested tasks, but its performance is substantially less stable than with fixed outputscale.The comparison covers MOPTA08 and SVM across DSP and conventional-prior models.Source: §F.1 · p. 22

F.2. Performance Ablation on Learned σ2

Learning signal variance can produce competitive results on some tasks, but is less consistent than fixed outputscale. The associated outputscale shrinkage and query distances point to more exploitative, local search behavior.

F.2. Performance Ablation on Learned σ2

  • Learned signal variance performs comparably on some synthetic and real-world tasks, but is substantially less stable than fixed outputscale.The figures show average log regret on Levy and Hartmann and average minimal observed value on MOPTA, Lasso-DNA, and SVM.Source: §F.2 · p. 23, Figure 21 · p. 24, Figure 22 · p. 25
  • Learned outputscale shrinks over time and is associated with increased exploitation and very local queries, as is a conventional lengthscale prior.The query-distance comparison is reported for MOPTA08 and SVM.Source: Figure 19 · p. 24, Figure 20 · p. 24
Loading 2402.02229v5…