Re-Examining Linear Embeddings for High-Dimensional Bayesian Optimization

Benjamin Letham, Roberto Calandra, Akshara Rai, Eytan Bakshy

Abstract

Bayesian Optimization (BO) is a highly sample-efficient method for optimizing expensive black-box functions, yet it traditionally struggles when the parameter dimension ($D$) exceeds 20. While linear embedding methods like REMBO have been proposed to mitigate this "curse of dimensionality," they often suffer from hidden boundary distortions and mathematical inconsistencies. This paper identifies the root causes of these failures and introduces ALEBO (Adaptive Linear Embedding BO). By employing polytope constraints, a custom Mahalanobis kernel, and hypersphere sampling, ALEBO significantly improves sample efficiency and optimization performance on high-dimensional tasks ranging from synthetic benchmarks to neural architecture search.

Introduction

Standard Bayesian Optimization relies on Gaussian Processes (GPs), which face significant scaling challenges in high-dimensional spaces. A common workaround is the use of linear embeddings, which assume the objective function varies only along a low-dimensional subspace ($d$). By optimizing within a small random embedding and projecting results back to the high-dimensional ambient space, researchers hope to bypass dimensionality constraints. However, legacy methods frequently underperform, sometimes failing to beat simple random search. This work re-examines the geometry of these embeddings to resolve these performance gaps.

The "Clipping Catastrophe"

One of the primary failures in existing embedding methods is the treatment of physical box bounds in the ambient space. When a point is selected in the low-dimensional embedding, its high-dimensional projection often falls outside these bounds. Previous methods typically "fixed" this by clipping out-of-bounds points to the edges of the box.

Figure 1: Non-linear distortions and non-stationarity in a REMBO embedding caused by boundary clipping.

As shown in Figure 1, this clipping creates severe, non-linear distortions. The authors demonstrate that for embedding dimensions $d_e > 2$, almost all points project outside the high-dimensional bounds. The resulting "folded" function landscape is highly non-stationary, making it nearly impossible for a standard GP to model effectively.

ALEBO: Adaptive Linear Embedding BO

To address these issues, the authors propose ALEBO, which introduces three critical innovations:

  1. Polytope Constraints: Instead of post-hoc clipping, ALEBO restricts the acquisition function to search only within a mathematically defined polytope. This ensures that every point selected in the embedding projects perfectly within the high-dimensional box bounds, eliminating distortion.
  2. Custom Mahalanobis Kernel: Standard ARD product kernels do not translate correctly from the true subspace to a random linear embedding. ALEBO utilizes a derived Mahalanobis distance metric tailored for linear projections, allowing the GP to accurately model the covariance of the space.
  3. Hypersphere Sampling: To balance the trade-off between avoiding distortions and ensuring the global optimum is reachable, ALEBO samples the random projection matrix from a unit hypersphere and slightly over-parameterizes the embedding dimension ($d_e > d$).
Figure 2: The smoother, more accurate function landscape modeled by ALEBO's Mahalanobis kernel and polytope constraints.

As illustrated in Figure 2, these changes result in a much smoother and more learnable landscape compared to distorted legacy embeddings.

Experimental Results

ALEBO was evaluated across several challenging benchmarks:

  • Synthetic Functions: On the $D=1000$ Hartmann6 problem, ALEBO successfully optimized the function while baselines like REMBO failed to outperform random search.
  • Neural Architecture Search (NAS): In a constrained NAS-Bench-101 task ($D=36$), ALEBO was the only embedding method to consistently find high-accuracy architectures under strict training time limits.
  • Robot Locomotion: On a $D=72$ hexapod simulation, ALEBO significantly outperformed REMBO. However, the authors noted that evolutionary strategies (CMA-ES) performed better in this specific task due to sharp discontinuities in the reward function (e.g., the robot falling), which global GP models struggle to fit.

Conclusion

ALEBO provides a robust framework for high-dimensional BO by correcting the geometric and mathematical flaws of previous linear embedding approaches. While it shows great promise for smooth high-dimensional tasks, future work will explore extending these insights to non-linear embeddings, such as Variational Autoencoders (VAEs), to further enhance the optimization of complex latent spaces.

Summary updated

BibTeX
@inproceedings{letham2020re,
  author = {Benjamin Letham and Roberto Calandra and Akshara Rai and Eytan Bakshy},
  title = {{Re-Examining Linear Embeddings for High-Dimensional Bayesian Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=rqZnqXgMX5},
}
Figure