PaperlayerView exact revision on arXiv

Source-linked AI summary

A survey on high-dimensional Gaussian process modeling with application to Bayesian optimization

Mickael Binois, Nathan Wycoff

arXiv:2111.05040v2math.OC

TL;DR

High dimensionality challenges GP-based Bayesian optimization because maintaining approximation quality requires exponentially more design points. This survey reviews structural assumptions and acquisition-function optimization strategies, finding that their practical effects vary: additive structure can reduce optimization to d one-dimensional problems, while embeddings often complicate acquisition optimization.

  • Problem

    High dimensionality is a critical challenge because the number of design points needed to maintain approximation quality grows exponentially.

  • Method

    The survey reviews structural model assumptions for high-dimensional Gaussian processes and how those structures affect acquisition-function optimization.

  • Results

    Additive structure allows solving d many one-dimensional problems, whereas embedding approaches more often complicate than simplify acquisition optimization.

  • Takeaways & Limitations

    Acquisition optimization must be considered alongside structural modeling because the chosen strategy can overshadow the rest.

  • Takeaways & Limitations

    More systematic comparisons and suitable benchmarks are needed.

Abstract

from arXiv · show

Bayesian Optimization, the application of Bayesian function approximation to finding optima of expensive functions, has exploded in popularity in recent years. In particular, much attention has been paid to improving its efficiency on problems with many parameters to optimize. This attention has trickled down to the workhorse of high dimensional BO, high dimensional Gaussian process regression, which is also of independent interest. The great flexibility that the Gaussian process prior implies is a boon when modeling complicated, low dimensional surfaces but simply says too little when dimension grows too large. A variety of structural model assumptions have been tested to tame high dimensions, from variable selection and additive decomposition to low dimensional embeddings and beyond. Most of these approaches in turn require modifications of the acquisition function optimization strategy as well. Here we review the defining structural model assumptions and discuss the benefits and drawbacks of these approaches in practice.

1 Introduction

High dimensionality creates difficulties for both GP surrogate modeling and acquisition-function optimization in Bayesian optimization. The survey reviews structural assumptions and corresponding acquisition adaptations, while noting trade-offs and unresolved comparison needs.

  • 1 Introduction: The survey covers structural GP assumptions, acquisition optimization consequences, test functions, practical guidelines, and promising research directions.It is incremental rather than exhaustive, focusing on recent trends across several communities.
  • 1 Introduction: In Bayesian optimization, increasing variables affects both GP distance-based modeling and optimization of the acquisition function.These effects may appear with ten variables or become evident with dozens, depending on problem difficulty.
  • 1 Introduction: High dimensionality is a critical scaling difficulty for black-box optimization because required design points grow exponentially with the number of variables.The curse of dimensionality also disperses designs and concentrates volume near the search-space boundary.
  • 1 Introduction: Three main structural strategies reduce high-dimensional difficulty: removing variables, constructing lower-dimensional combinations, and assuming additive effects.The chosen structure can also constrain the acquisition-search domain or support surrogate modeling.
  • 1 Introduction: Learning stronger structure introduces estimation risk, especially with limited evaluation budgets and initially scarce data.Researchers may infer structure online or separate structure estimation from later exploitation, with the best budget split depending on the problem.
  • 1 Introduction: Randomly defined structures avoid estimation but may incur variance and bias from randomization.Trust regions offer another way to limit dimensional effects by restricting the search volume.
  • 1 Introduction: High-dimensional GP and BO methods remain bounded by additional challenges, including scaling with design-point count, complex noise, non-stationarity, and constrained or batch settings.The survey generally assumes that black-box evaluations remain more limiting than running the BO framework.

2 Background

The background introduces Gaussian-process surrogates and Bayesian optimization for expensive black-box functions. It explains how distance behavior, hyperparameter growth, and acquisition optimization become problematic as input dimension increases.

  • 2 Background: A black-box simulator exposes no known functional form, so Bayesian optimization queries it at selected input points to find a global optimum.The simulator is treated as expensive to evaluate.
  • 2 Background: A Gaussian process specifies prior mean and covariance functions for joint distributions over function values at arbitrary finite sets of points.Gaussian-process conjugacy gives a conditional process whose mean and covariance are available in closed form after observations.
  • 2 Background: GP regression uses observed responses, kernel evaluations, the covariance matrix, and a noise hyperparameter to compute the posterior mean.The noise model assumes yi = f(x(i)) + εi with εi = N(0, τ 2).
  • 2 Background: Stationary kernels depend on input differences, while lengthscales control where covariance declines and kernel choice determines qualitative GP properties.Squared-exponential kernels yield infinitely differentiable metamodels; Matérn kernels provide explicit smoothness control.
  • 2 Background: Because GP covariance depends on distances, high-dimensional approaches often apply kernels after dimension-reducing transformations, keeping transformation and kernel modular.The survey views this modularity as helpful for model design and comparison.
  • 2 Background: Bayesian optimization builds an acquisition function from a GP posterior, optimizes it over the input domain, and sequentially evaluates the selected points.Expected improvement and upper confidence bound are common choices because their values and gradients are analytically tractable.
  • 2 Background: High-dimensional inputs make points farther apart, complicate distance-based learning, and increase the number of lengthscale hyperparameters in product kernels.Squared distances between uniformly sampled points increasingly concentrate farther away as dimension grows.

3 High-dimensional Gaussian process modeling

High-dimensional GP modeling relies on structural assumptions to avoid exponential dependence on dimension, including variable selection, additive decompositions, and embeddings. These approaches trade modeling flexibility and scalability against interpretability, computation, estimation difficulty, or restrictive assumptions.

  • Structural model assumptions are presented as the way to avoid exponential dependence on dimension in GP modeling.
  • Variable selection or screening: Variable selection screens inputs before optimization, often using expert knowledge or lengthscales and then fitting a GP on influential variables.ARD ranks variables by lengthscales, with larger lengthscales indicating weaker covariance variation; selected variables can support expected-improvement optimization.
  • Variable selection or screening: Variable selection is simple to implement and interpret, but choosing the retained dimension can be arbitrary and screening becomes harder as dimension increases.Its assumptions can fail when black-box functions depend strongly on all variables or when variables have equal influence.
  • Additive and ANOVA models: Additive and ANOVA models retain variables while representing effects through univariate components or selected interactions.ANOVA-style decompositions support sensitivity analysis, and GP predictive means can be decomposed into sums of univariate components.
  • Additive and ANOVA models: Sum-form additive models scale better in high dimension than tensor-product forms, but introduce additional variance hyperparameters and can yield zero predictive variance at unobserved points.Adding a noise term can alleviate the zero-variance side effect.
  • Non-linear embeddings and structured spaces: Nonlinear embeddings can succeed in high-dimensional, structured or non-Euclidean spaces, but add computational and interpretive complexity.The survey recommends reserving them for the toughest problems and considering simpler approaches when functional insight is desired.

4 High-dimensional acquisition function optimization

High-dimensional acquisition optimization is difficult because boundary effects, multimodality, and plateaus undermine global search. The survey reviews model-independent and structure-specific strategies that reduce or redirect this optimization burden, while noting important trade-offs.

  • Practical considerations: Structural assumptions are imperfect in practice, so approximation error generally requires a noise component that must be incorporated into acquisition optimization.The survey also identifies unexplored combinations among acquisition strategies and GP structures.
  • Optimization challenges: Faster acquisition evaluations and gradients provide limited help for globally optimizing multimodal functions, while scalable global-optimality guarantees remain unavailable.Large plateaus and local minima create additional obstacles, and branch-and-bound or DIRECT methods do not scale.
  • Model-independent strategies: Acquisition optimization strategies include inflated-to-decreasing lengthscales, random linear embeddings, finite subspace searches, and boundary-aware coordinate transformations.These methods modify the optimization procedure to improve gradient behavior, restrict candidate subspaces, or upweight the domain interior.
  • Optimization challenges: Expanding boundary volume causes uniform or evolutionary searches to concentrate near boundaries, where acquisition variance can place the optimum.This can leave the interior unexplored because evaluating all faces or vertices is infeasible.
  • Model-independent strategies: Trust regions focus search around the current best solution and expand or contract according to improvement, benefiting high-dimensional BO at the possible cost of less global search.Restarts or parallel trust regions may compensate for reduced global coverage.
  • Structural models: Additive models reuse the GP decomposition to replace one d-dimensional acquisition problem with several lower-dimensional searches, possibly in parallel.The approach can solve d one-dimensional problems, but its global-search behavior is affected by zero posterior variance at unobserved locations.
  • Structural models: Variable selection reduces the acquisition search dimension but does not decompose the problem and may require suboptimal values for inactive variables.The inactive coordinates must be fixed, sampled, or otherwise determined before evaluating the objective.
  • Structural models: Linear embeddings can complicate acquisition search because bounded domains require projections and may make the optimization noisy when inactive directions are ignored.The survey notes that embeddings can still be worthwhile when sufficient evaluation savings justify the additional effort.

5 Synthetic test optimization problems

The survey reviews synthetic, realistic, and data-driven options for evaluating high-dimensional GP and BO methods. It emphasizes that benchmark definitions, dimensions, budgets, and reproducibility vary substantially, limiting broad empirical conclusions.

  • Benchmarking limitations: A thorough empirical comparison is difficult because many methods and combinations exist, implementations are often unavailable, and inference techniques can differ.These factors complicate fair comparisons across approaches.
  • Benchmark sources: Standard high-dimensional benchmark functions are scarce, motivating reproducible test problems from global optimization, engineering, simulation, and machine-learning hyperparameter tuning.The survey lists realistic examples such as airfoil, wing, fan, automotive, alloy, biology, physics, and electronics applications.
  • Synthetic functions: Synthetic functions may be separable, unimodal with moderate or high conditioning, or multimodal with global structure.The survey notes that only the final category is explicitly recommended for optimization problems.
  • Synthetic functions: Adding inactive variables makes low-dimensional test functions nominally high dimensional and can scale to billions of variables, but may not be realistic.Repeated or rotated low-dimensional functions introduce more active variables but can create domain and rotation-dependent difficulties.
  • Benchmarking limitations: The relevance of synthetic and analytical benchmark results to real applications remains an open research question.Engineering and simulation benchmarks are realistic, but high-fidelity reproduction pipelines are rarely available.
  • Data-driven benchmarks: High-dimensional regression datasets can be adapted to BO by restricting candidates to observed inputs, but this removes continuous acquisition optimization.Using an interpolant as the black box can also produce unrealistically favorable results when the same interpolant is used for BO.
  • Open evaluation questions: Across surveyed examples, “high dimensional” ranges from the low tens to several thousands, while budgets vary similarly but are evaluated at fixed values.This leaves open which structure best matches a given dimension and budget, or how complexity should increase with additional evaluations.

6 Conclusion and perspectives

High-dimensional BO remains problem-dependent: structural assumptions, inference choices, and acquisition optimization each shape performance, with no consensus on a universally best approach. The authors review a progression from simpler models and recommend matching model complexity and optimization strategy to the dimension, budget, and application.

  • High-dimensionality is a major challenge for GP-based BO, motivating structural assumptions such as variable selection, additive decomposition, and linear embeddings.
  • No consensus exists on the best structural approach because the suitable choice is largely problem-dependent.
  • Inference methods restrict which structures can be assumed, while acquisition-function optimization can overshadow the rest of the BO strategy.
  • The authors identify promising research directions at intersections among structural models, inference methods, and optimization strategies, including hybrid methods and default kernel components.
  • 6.1 Some general guidelines: The recommended workflow starts with standard GP, ARD or sensitivity analysis, then tests additive or single-index models before considering functional ANOVA, block additive, projection-pursuit, or nonlinear embeddings.
  • 6.1 Some general guidelines: Model selection should account for d, budget n, and the complexity of f; when inference is too difficult at hundreds of dimensions, random structures remain an option.
  • 6.1 Some general guidelines: Simpler models scale better computationally with dimension, whereas more complex models may benefit from GPUs and automatic differentiation but require larger n to show improvements.
  • 6.1 Some general guidelines: Trust-region optimization, restricted-subspace search with filling strategies, and local dimension reduction offer practical routes for high-dimensional BO and can support parallelization.

A Synthetic benchmark functions

The paper uses synthetic global-optimization functions as benchmark problems for evaluating high-dimensional BO methods. Table 3 provides the benchmark list and references for additional function definitions and codes.

  • Synthetic global-optimization functions are used to test high-dimensional BO methods.
  • Table 3 lists the benchmark problems and points to sources for further details, expressions, and codes.
Loading 2111.05040v2…