🤖 machine learning

Understanding High-Dimensional Bayesian Optimization

This paper investigates the success of simple Bayesian optimization methods in high-dimensional settings by identifying vanishing gradients from Gaussian process initialization as a key failure factor, demonstrating that Maximum Likelihood Estimation of length scales suffices for state-of-the-art performance, and proposing a simple MSR variant that achieves superior results on real-world applications.

Original authors: Leonard Papenmeier, Matthias Poloczek, Luigi Nardi

Published 2026-05-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Leonard Papenmeier, Matthias Poloczek, Luigi Nardi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the absolute best spot to set up a new coffee shop in a massive, foggy city. You have a limited budget for how many locations you can visit to test the potential. This is the essence of Bayesian Optimization (BO): a smart way to find the "best" solution to a problem when testing every option is too expensive or time-consuming.

Usually, this works great in small cities (low dimensions). But what happens when the city is a sprawling metropolis with thousands of neighborhoods (high dimensions)? For a long time, experts believed it was impossible to find the best spot in such a huge city without getting lost.

This paper investigates why some recent, simple methods are suddenly succeeding in these massive cities and offers a new, simpler way to do it. Here is the breakdown:

1. The Problem: The "Fog" and the "Vanishing Compass"

In high-dimensional spaces, the "fog" (mathematical complexity) gets so thick that your compass (the algorithm's ability to learn) stops working.

The Vanishing Gradient: Imagine you are trying to tune a radio to find a clear station. In a small room, you can hear the static change as you turn the knob. But in a giant stadium, the signal is so weak that turning the knob feels like it's doing nothing at all. The math behind the algorithm gets stuck; the "knob" (a setting called the length scale) stops moving because the signal telling it to move is too faint.
The Flat Map: Because the city is so big, most of the map looks exactly the same (flat). The algorithm looks around and sees no hills or valleys to guide it, so it just picks a random spot and stops trying to improve.

2. The Discovery: Why Simple Methods Work

The authors found that recent "simple" methods succeed not because they built a perfect map of the whole city, but because they stopped trying to map the whole city at once. Instead, they started walking locally.

The Local Search: Instead of trying to see the whole city, the algorithm picks a spot, looks at the immediate neighborhood, and takes a small step. If that step is good, it keeps going. If the map looks flat, it just jiggles the current spot slightly to see if anything changes.
The "RAASP" Trick: One key technique mentioned is RAASP (Random Axis-Aligned Subspace Perturbation). Imagine you are in a dark room. Instead of trying to walk in a straight line across the whole room, you take a step, then randomly wiggle just one arm or leg to see if you bump into a wall. This keeps you moving locally and prevents you from getting stuck in the "flat" areas.

3. The Solution: MSR (The "Smart Start")

The paper proposes a new method called MSR (MLE Scaled with RAASP). It combines two ideas:

The Right Starting Point: The authors realized the algorithm fails because it starts with the radio knob set to the wrong position (too small), causing the signal to vanish immediately. They found that if you start the knob at a specific, larger setting (scaled by the size of the city), the signal stays strong, and the algorithm can actually learn.
The Local Walk: They combine this "smart start" with the local walking technique (RAASP).

The Result: MSR doesn't need complex rules or "guesses" about the city's layout. It just starts with the right settings and walks around locally. The paper shows this simple approach performs just as well as, or better than, the most complex, fancy algorithms currently available.

4. A Surprising Twist: The City Might Be a Trick

The authors also noticed something interesting about the "cities" (benchmarks) used to test these methods. In some of the famous test cases, the "best" coffee shop locations were almost always right on the edge of the city limits (the boundaries).

The Analogy: It turns out that for some of these test cities, the "best" spot isn't in the middle of a complex neighborhood; it's just "all the way to the left" or "all the way to the right."
The Implication: Because the best spots are on the edge, the algorithm doesn't actually need to understand the complex middle of the city. It just needs to push the variables to the edge. This suggests that some popular tests might be easier than they look, and the algorithms are succeeding by finding these "edge" solutions rather than solving a truly complex, high-dimensional puzzle.

Summary

The paper argues that high-dimensional optimization isn't as magical as we thought. The failures of the past were due to the algorithm getting "lost" because it started with the wrong settings (vanishing gradients). The successes of the present are due to algorithms that:

Start with the right settings so they can actually "hear" the signal.
Focus on local steps (walking around the neighborhood) rather than trying to map the whole world at once.

Their new method, MSR, is a simple, robust way to do this that works without needing complex assumptions or prior knowledge.

Technical Summary: Understanding High-Dimensional Bayesian Optimization

Problem Statement

High-dimensional Bayesian optimization (HDBO) aims to find the minimum of an expensive-to-evaluate black-box function $f: [0, 1]^d \to \mathbb{R}$ where the dimensionality $d$ is large. While Bayesian optimization (BO) is effective in low-dimensional settings, it has historically been considered infeasible for high dimensions due to the "curse of dimensionality" (COD). The COD necessitates exponentially more data points to maintain precision, complicates the fitting of Gaussian Process (GP) hyperparameters, and hinders the maximization of acquisition functions (AFs).

Recent literature (e.g., Hvarfner et al., 2024; Xu & Zhe, 2024) suggested that simple BO methods perform surprisingly well on high-dimensional real-world benchmarks, often outperforming sophisticated algorithms designed specifically for high dimensions. However, the underlying reasons for this success and the specific challenges remaining in HDBO were not thoroughly identified. This paper investigates these phenomena, focusing on the behavior of standard GP surrogates without relying on strong structural assumptions like additivity or low-dimensional active subspaces.

Methodology and Analysis

The authors conduct an exhaustive empirical analysis to identify the root causes of failure and success in HDBO, focusing on three main facets of the problem:

1. Vanishing Gradients in Model Fitting (MLE)

The paper identifies that standard Maximum Likelihood Estimation (MLE) for GP length scales often fails in high dimensions due to vanishing gradients.

Mechanism: When initializing the length scales with standard values (e.g., $\ln 2$ ), the gradient of the marginal log-likelihood (MLL) with respect to the length scales vanishes for high-dimensional problems. Consequently, the optimizer cannot update the length scales, leaving them at their initial values regardless of the observed data.
Evidence: Experiments show that with short initial length scales, gradients vanish even for moderate dimensions. This prevents the GP from adapting to the function's true scale.
Mitigation: The authors propose a simple initialization strategy where the initial length scale is scaled by $\sqrt{d}$ (specifically $\sqrt{d}/10$ ). This ensures the optimizer starts in a region where gradients are non-vanishing, allowing the length scales to be fitted effectively without requiring Maximum A-Posteriori (MAP) estimation or complex hyperpriors.

2. Vanishing Gradients in Acquisition Function Optimization

Even if the GP model is fitted correctly, the acquisition function (AF) optimization can fail.

Mechanism: In high dimensions, large regions of the search space remain unexplored. If the GP posterior is flat in these regions (due to insufficiently long length scales or lack of data), the AF surface becomes flat. Gradient-based optimizers used to maximize the AF (e.g., for Expected Improvement) then experience vanishing gradients, failing to move from the initial random candidates.
Role of RAASP: The paper highlights that Random Axis-Aligned Subspace Perturbation (RAASP) sampling, used in methods like TuRBO and BoTorch, is crucial. RAASP generates candidates by perturbing the best-performing points. In high dimensions, this forces the optimizer to start near incumbent observations where the AF is less likely to be flat, effectively reverting the search to a local behavior that avoids the vanishing gradient trap.

3. Bias-Variance Trade-off in GP Fitting

The authors compare MLE and MAP approaches for fitting GP hyperparameters.

Findings: MLE exhibits higher variance in length scale estimates, particularly with scarce data in high dimensions. MAP (using hyperpriors) reduces variance but introduces bias unless accurate prior information is available.
Insight: The proposed initialization for MLE (scaled by $\sqrt{d}$ ) allows MLE to achieve state-of-the-art performance without the bias introduced by arbitrary hyperpriors, which practitioners often lack.

Proposed Method: MSR

Based on these findings, the authors propose MSR (MLE Scaled with RAASP):

Initialization: Use MLE for GP length scales but initialize the optimizer with a length scale of $\sqrt{d}/10$ to prevent vanishing gradients during model fitting.
Acquisition: Maximize the acquisition function (LogEI) using RAASP sampling to ensure candidates are generated locally around the best observations, mitigating AF vanishing gradients.
Simplicity: Unlike other methods, MSR does not require specifying a prior belief on length scales (as in MAP) or complex embedding structures.

Results

The authors evaluate MSR on a comprehensive set of real-world applications and benchmarks, including:

Datasets: Mopta08 (124d), Lasso-DNA (180d), SVM (388d), Rover (60d), Ant (888d), and Humanoid (6392d).
Comparisons: MSR is compared against state-of-the-art methods including DSP (a MAP-based method with dimensionality-scaled priors), TuRBO, SAASBO, and Bounce.

Key Findings:

Performance: MSR achieves competitive, state-of-the-art performance across all benchmarks, matching or surpassing DSP. Notably, MSR outperforms DSP on the 124d Mopta08 and 888d Ant benchmarks.
Failure of Standard Initialization: Methods using the standard constant initialization ( $\ell = \ln 2$ ) fail on high-dimensional benchmarks (e.g., Ant, Humanoid) due to vanishing gradients, behaving effectively as random search.
Role of RAASP: The inclusion of RAASP sampling in MSR reduces the variance of length scale estimates and promotes local search behavior, which the authors argue is the primary driver of success in extremely high-dimensional problems (order of 1000 dimensions) rather than a globally well-fitted surrogate model.
Benchmark Analysis: The paper notes that popular benchmarks like Mopta08 and Lasso-DNA may possess simpler structures than expected (many dimensions are "secondary" and set to boundaries), which can benefit models with long length scales. However, MSR's robustness holds even on these specific structures.

Significance and Claims

The paper claims to provide a deeper understanding of why simple BO methods succeed in high dimensions, attributing success to:

Avoiding Vanishing Gradients: Proper initialization of length scales is critical for fitting the GP model.
Local Search Behavior: In high dimensions, successful optimization relies more on local search mechanisms (facilitated by RAASP) than on a globally accurate surrogate model.

The authors argue that practitioners do not need complex priors or structural assumptions to achieve state-of-the-art HDBO performance. Instead, a simple variant of MLE with dimensionality-scaled initialization, combined with RAASP sampling, is sufficient. The work emphasizes the importance of numerical stability in BO and suggests that future research should focus on benchmarks that better capture the complexity of real-world high-dimensional applications, as current popular benchmarks may be "overfitted" to simple structures.