TL;DR
Bayesian Optimization (BO) often uses random linear embeddings to scale to high-dimensional problems, but existing methods suffer from hidden boundary distortions and poor kernel choices. This paper identifies exactly why these legacy methods fail and introduces ALEBO (Adaptive Linear Embedding BO), a redesigned approach using a custom Mahalanobis kernel and polytope constraints. ALEBO significantly improves sample efficiency and optimization performance on high-dimensional tasks, from synthetic benchmarks to neural architecture search.
What Problem Does This Paper Address?
Bayesian Optimization (BO) is a highly sample-efficient way to optimize expensive black-box functions, but standard BO relies on Gaussian Processes (GPs) which notoriously fail when the parameter dimension ($D$) exceeds 15–20.
To bypass this "curse of dimensionality," researchers often use linear embeddings (like the popular REMBO algorithm). The assumption is that even if you have 1,000 parameters, the function only really varies along a small number of them (a low-dimensional subspace, $d$). You can optimize in a small random embedding and project the results back up to the high-dimensional "ambient" space.
However, the ambient space usually has physical box bounds (e.g., a pump rate must be between 0 and 10). When you pick a point in the low-dimensional embedding, its high-dimensional projection often falls outside these bounds. Previous methods "fixed" this by simply clipping the out-of-bounds points to the edges of the box. This paper reveals that this clipping creates severe, non-linear distortions that completely ruin the GP's ability to model the function.
Methods
The authors propose ALEBO (Adaptive Linear Embedding BO), which fixes the mathematical inconsistencies of prior embedding methods through three main innovations:
- Avoiding Nonlinear Projections via Polytope Constraints: Instead of letting the algorithm pick any point in the embedding and clipping it later, ALEBO restricts the BO acquisition function to only search within a specific polytope. This polytope is mathematically defined to ensure that every point inside it will project perfectly within the high-dimensional box bounds. No clipping required.
- A Custom Mahalanobis Kernel: The authors prove that a standard ARD (Automatic Relevance Determination) product kernel in the true subspace does not translate to a product kernel in the random embedding. To fix this, they derive a specific Mahalanobis distance metric tailored for linear embeddings, allowing the GP to accurately model the space.
- Hypersphere Sampling: By restricting the search space to avoid clipping, you reduce the overall volume you can explore, which lowers the probability that the global optimum is actually reachable. To counter this, ALEBO samples the random projection matrix from a unit hypersphere and sets the embedding dimension ($d_e$) slightly higher than the assumed true subspace dimension ($d$). This mathematically maximizes the chance of the optimum being in the search space.
Datasets
The authors evaluated ALEBO on both synthetic and real-world high-dimensional benchmarks:
- Synthetic Functions: Branin ($d=2$, embedded in $D=100$), Hartmann6 ($d=6, D=1000$), and Gramacy ($d=2, D=100$).
- Constrained Neural Architecture Search (NAS): Using the NAS-Bench-101 dataset, parameterized to $D=36$. The goal was to maximize CIFAR-10 accuracy subject to a 30-minute training time constraint.
- Robot Locomotion: A PyBullet simulation of a hexapod "Daisy" robot ($D=72$). The goal was to learn a walking policy that reaches a target while avoiding high joint velocities.
Key Insights and Ideas
- The "Clipping Catastrophe": The authors show empirically that for embedding dimensions $>2$, almost all points project outside the high-dimensional bounds. Clipping them to the boundary facets creates massive non-stationarity. The GP is essentially asked to learn a folded, distorted function, which is why older methods like REMBO often perform worse than random search on very high-dimensional problems.
- Kernel Mismatch is Fatal: Using a standard ARD RBF kernel in a linear embedding will fail to learn the function and just predict the mean. The geometry of the projection matrix fundamentally alters the covariance, necessitating the Mahalanobis kernel.
- The Optimum Probability Trade-off: There is a strict tension between keeping the embedding free of boundary distortions and ensuring the embedding actually contains the global optimum. Hypersphere sampling and over-parameterizing the embedding dimension ($d_e > d$) is the key to balancing this trade-off.
Key Results
- Synthetic Benchmarks: ALEBO consistently achieved the best average performance with low variance. On the $D=1000$ Hartmann6 problem, REMBO and several other baselines failed completely (performing worse than random search), while ALEBO successfully optimized the function.
- Neural Architecture Search: ALEBO was the only embedding method to outperform random search (Sobol) in finding high-accuracy architectures under the strict training time constraints.
- Robot Locomotion: On the $D=72$ robot task, ALEBO significantly outperformed REMBO (which barely beat random search). However, an evolutionary strategy (CMA-ES) actually beat all BO methods on this specific task.
Limitations and Future Work
- Vulnerability to Discontinuities: The authors honestly note that on the robot locomotion task, the model-free CMA-ES algorithm beat ALEBO. This is likely because the robot simulation contains sharp discontinuities (e.g., the robot falls over, causing an instant drop in reward) that global GP models struggle to fit, favoring local search methods.
- Future Work - Nonlinear Embeddings: The insights from this paper apply to nonlinear embeddings (like VAEs) as well. If you clip a VAE's decoded output to fit physical bounds, you will destroy the model's ability to learn the latent space. Future work will look at backpropagating linear constraints directly into VAE acquisition function optimization.
Summary updated