Re-Examining Linear Embeddings for High-Dimensional Bayesian Optimization

Motivation

• Random embeddings are attractive because they avoid learning the embedding and can be sample-efficient, but their empirical performance in high-dimensional BO has been mixed.The approach estimates only a low-dimensional Gaussian process rather than D × d embedding parameters.Source: §1 · p. 1, §2 · p. 2

Challenges

• Existing linear-embedding methods can produce representations that Gaussian processes model poorly or that fail to contain an optimum.The paper identifies both issues as central explanations for poor HDBO performance.Source: §1 · p. 1

Contributions

• ALEBO combines a Mahalanobis kernel, polytope bounds, and embedding design that maintains a high probability of containing an optimum.These choices are intended to improve modelability while avoiding problematic ambient-space projections.Source: §1 · pp. 1–2

Related work

• Linear embeddings are one branch of high-dimensional BO alongside surrogate models that impose structure directly, such as additive, cylindrical, and deep neural network kernels.The paper focuses specifically on the embedding approach and random linear projections.Source: §2 · p. 2

REMBO

• REMBO uses a random Gaussian projection and performs BO in the embedding, but box bounds require clipping projected points and separate projections.Clipping can make the effective mapping nonlinear, while separate projections prevent sharing data across embeddings.Source: §3 · p. 3

Nonlinear projections

• Clipping projected points to ambient box facets creates nonlinear, non-stationary distortions that can prevent standard stationary Gaussian processes from modeling the embedding.The distortion depends on facet orientation relative to the true subspace, and is especially severe when d_e > 2 because most embedded points reach facets.Source: §4 · pp. 3–4, Figure 1 · p. 4

Optimum coverage

• Some linear embeddings have low probability of containing an optimum, particularly for axis-aligned subspaces where features can collide or map to opposing embedding coordinates.Restricting the embedding to avoid clipping also reduces reachable ambient volume, making Popt a central design criterion.Source: §4 · p. 4, A Kernel for Learning in a Linear… · p. 6

Kernel mismatch

• A product kernel in the true subspace becomes a Mahalanobis kernel in the linear embedding, so ARD distance is generally misspecified there.The induced metric has d_e(d_e+1)/2 parameters rather than the usual d_e ARD lengthscales.Source: §4 · p. 4, A Kernel for Learning in a Linear… · p. 5
• In a 6-dimensional Hartmann6 embedding, the ARD RBF kernel predicts the mean instead of learning the function, whereas the Mahalanobis kernel makes accurate test-set predictions.The comparison uses 100 training points and 50 test points sampled from the interior, avoiding clipping distortion.Source: A Kernel for Learning in a Linear… · p. 5

Optimum coverage

• Under uniform priors with D=100, increasing d_e above d rapidly improves Popt, and hypersphere sampling performs best, especially for small d.The analysis evaluates Popt across REMBO, HeSBO, and hypersphere projection strategies.Source: A Kernel for Learning in a Linear… · p. 6

ALEBO

• ALEBO combines adaptive embedding bounds with the corrected kernel metric to address projection distortion and optimum coverage in one HDBO method.Its embedding formulation uses B and the pseudoinverse B†, with optimization restricted to points whose ambient projections satisfy the box bounds.Source: §5 · p. 5, A New Method for BO with Linear… · p. 6

• The results attribute prior REMBO weakness to modeling issues and show that ALEBO's adjustments improve performance across linear-embedding methods.Source: §6 · pp. 7–8
• The benchmark suite averaged optimization performance over 50 runs on Branin extended to D=100, Hartmann6 extended to D=1000, and Gramacy extended to D=100.Source: §6 · p. 7
• Several competing methods failed to complete a single D=1000 run within 24 hours and lacked support for the Gramacy problem's black-box constraints.Source: §6 · p. 8
• ALEBO achieved the best average optimization performance overall on three high-dimensional linear-subspace benchmarks, while REMBO was worse than random on the D=1000 problem.ALEBO also had low variance in final best value, supporting robustness when only one optimization run is practical.Source: §6 · pp. 7–8

Constrained Neural Architecture Search

• The NAS objective maximized CIFAR-10 test accuracy subject to training time below 30 minutes, demonstrating that HDBO can find well-performing models under a runtime constraint.Source: §7 · p. 8
• ALEBO was the only embedding method to outperform random search on constrained D=36 NAS, and it significantly exceeded Sobol, CMA-ES, HeSBO, and REMBO by the final iteration.TuRBO was not significantly different from ALEBO in later iterations.Source: Figure 6 · p. 8

Policy Search for Robot Locomotion

• On the D=72 Daisy locomotion task, ALEBO was the strongest linear-embedding method and outperformed EBO, SMAC, Sobol, and REMBO, but CMA-ES outperformed every HDBO method.The figure reports means and two standard errors over 100 runs.Source: §7 · p. 8, Figure 7 · p. 9
• On locomotion, discontinuities can make small perturbations cause falls and sharply reduce reward, helping explain why model-free CMA-ES surpassed model-based HDBO methods.Expert tripod-gait tuning achieved rewards above 40, higher than any optimization run reported here.Source: §7 · p. 9

• Useful embeddings require both a function that is well-modeled in the embedding and an embedding that contains an optimum.Source: §8 · p. 9
• Polytope constraints remove boundary distortions, while a Mahalanobis kernel tailored to linear embeddings improves GP modeling.Source: §8 · p. 9
• Hypersphere sampling with de > d constructs embeddings with a high probability of containing an optimum, and ALEBO resolved poor REMBO performance on tested problems.Source: §8 · p. 9
• The conclusions extend beyond linear embeddings: VAE-based BO must also address modelability, box bounds, and the probability that the embedding contains an optimum.Source: §8 · p. 9
• Linear constraints were optimized directly in the acquisition function; nonlinear VAE constraints could be handled using backpropagated gradients.Source: §8 · p. 9

• High-dimensional BO applications include robotics, internet technology, pharmaceutical molecule design, solar-cell materials, and aerospace engineering.Source: Broader Impact · p. 10
• The authors fully open-sourced ALEBO code for researchers and practitioners.Source: Broader Impact · p. 10
• The paper links optimizing more parameters to potential improvements and acceleration across these application areas.Source: Broader Impact · p. 10

S1 HeSBO Embeddings

• For d = 2, the probability that a HeSBO embedding contains an optimum equals the probability of selecting the embedding that captures the active parameters and increases with de.This probability does not depend on D under the stated prior.Source: S1 HeSBO Embeddings · p. 14
• The three HeSBO embeddings can respectively contain all three Branin optima, miss them while coming close, or miss them substantially.The corresponding subspaces are the full embedding, x1 = −x2, and x1 = x2.Source: Figure S1 · p. 14
• On Hartmann6 with D = 100, an ARD RBF GP predicts the mean, whereas the Mahalanobis kernel makes accurate test-set predictions from the same data.The experiment used a 6-dimensional embedding, 100 training points, and 50 test points within the polytope.Source: S2 The Mahalanobis Kernel · p. 15, Figure S2 · p. 15
• Posterior sampling for the Mahalanobis kernel preserves reasonable predictive variance and improves predictive log likelihood relative to its point estimate.The point estimate significantly undercovers, while optimization results show strong performance with fewer than 50 iterations.Source: S2 The Mahalanobis Kernel · pp. 15–16, Figure S3 · p. 16

S3 Stationarity in the Embedding

• For a stationary GP on the true subspace, the implied kernel in the linear embedding is stationary and depends only on the embedded-point difference.The embedded kernel is defined by composing the original stationary kernel with the linear map g.Source: S3 Stationarity in the Embedding · p. 16
• Thus, a kernel appropriate for an unclipped linear embedding need not model the function correctly after ambient-space clipping.This follows from the change from a translation-invariant linear map to a non-translation-invariant projection.Source: S3 Stationarity in the Embedding · p. 16
• Clipping projected points to box bounds changes the mapping to include the L2 projection pB, producing an implied kernel that is non-stationary.The reason is that pB is not translation invariant.Source: S3 Stationarity in the Embedding · p. 16

S4 Polytope Bounds on the Embedding

• Hypersphere sampling with polytope bounds expands the embedding to capture optima and avoids the nonlinear distortions seen with REMBO-style clipping.For the Branin D = 100 example, the Gaussian projection contained no optima, while its normalized version captured two.Source: S4 Polytope Bounds on the Embedding · pp. 16–17, Figure S4 · p. 17
• Polytope constraints remove clipping distortions but reduce the ambient volume reachable from the embedding, lowering the probability that it contains an optimum.This trade-off motivates analyzing Popt rather than relying only on unconstrained embedding guarantees.Source: S4 Polytope Bounds on the Embedding · p. 17
• The probability Popt that an embedding contains an optimum can be estimated by testing feasibility of the embedding constraints for sampled true subspaces, optima, and projection matrices.The stated feasibility problem uses (B†B − I)x = 0 with −1 ≤ x ≤ 1.Source: S5 Evaluating the Probability the… · p. 17
• Increasing the embedding dimension de above the true dimension d rapidly improves Popt across the evaluated projection strategies.Figure S5 extends this comparison to d = 10, and Figure S6 shows high Popt for many d values with reasonable de even at high D.Source: S5 Evaluating the Probability the… · p. 17, Figure S5 · p. 18, Figure S6 · p. 18

S6 Selecting the Embedding Dimension

• The embedding dimension should exceed the true subspace dimension because doing so is vital for obtaining a high probability that the embedding contains an optimum.If d were known, Popt could in principle determine de for a desired containment probability.Source: S6 Selecting the Embedding Dimension · p. 18
• In expensive BO, the feasible embedding dimension is constrained by the available iteration budget, which may be fewer than 50 evaluations for week-long A/B tests.A 500-iteration experiment could instead use de in the 15–20 range under the stated normal-BO limit.Source: S6 Selecting the Embedding Dimension · p. 18
• Selecting de remains an open practical problem because simulations and model cross-validation can help identify the maximum tunable dimension, but little work has addressed this trade-off.The trade-off between dimensionality and iteration budget applies beyond linear-embedding HDBO.Source: S6 Selecting the Embedding Dimension · p. 19
• The same embedding can support constrained and multi-objective BO by fitting separate outcome models and applying the corresponding acquisition function in the shared embedding.For constrained BO, ALEBO uses a Mahalanobis kernel for each objective or constraint outcome.Source: S7 Handling Black-Box Constraints in… · p. 19

Benchmark results

• ALEBO’s average log-regret improvement over other methods was statistically significant across the benchmark experiments.Figure S7 reports means over 50 runs with error bars showing two standard errors of the mean.Source: S8.2 Analysis of experimental results · p. 20, Figure S7 · p. 21

Branin D=100

• On Branin D=100, ALEBO performed best from about iteration 20 and achieved the best average performance across nearly all runs.One run missed an optimum in the embedding, but nearly all 50 runs found values close to the optimum.Source: S8.2 Analysis of experimental results · p. 20
• HeSBO’s poor Branin performance arose entirely from embeddings that excluded the optimum, yielding an expected best value of 2.56.For de = 4, the probability of containing an optimum was 0.75, while one embedding had best value 17.18.Source: S8.2 Analysis of experimental results · p. 20

Hartmann6 D=100

• At Hartmann6 D=100, ALEBO, REMBO-γkΨ, TuRBO, and SMAC were the best-performing methods, while HeSBO and Add-GP-UCB stalled after about iteration 50.For HeSBO, the reported limitation was the low probability that its embedding contained an optimum.Source: Figure S7 · p. 21, S8.2 Analysis of experimental results · p. 22

Sensitivity analysis

• Increasing ALEBO’s embedding dimension trades faster early optimization for a higher chance of containing an optimum, with de = 8 ultimately outperforming all comparison methods from Fig. 5.For de = 2, progress quickly flattened; for de = 8, initial performance was worse but final solutions were better.Source: S8.3 Sensitivity of ALEBO to Embedding… · p. 23

Hartmann6 D=1000

• At Hartmann6 D=1000, ALEBO remained computationally scalable and was better than benchmark methods on D=100, whereas additive kernels and REMBO-γkΨ could not scale.ALEBO was slower than other linear embeddings but faster than additive-kernel methods and an order of magnitude faster than SMAC at D=1000.Source: S8.2 Analysis of experimental results · p. 20, Table S1 · p. 22, S8.3 Sensitivity of ALEBO to Embedding… · p. 23

Problem setup

• The optimization maximized CNN test-set accuracy subject to training time below 30 minutes.The search space was parameterized continuously through operation and edge variables before selecting discrete architectures.Source: S9 Constrained Neural Architecture… · pp. 24–25

Optimization results

• By the final iteration, ALEBO performed significantly better than Sobol, CMA-ES, HeSBO, and REMBO on NAS-Bench-101.TuRBO performed worse early but was not significantly different from ALEBO later.Source: S9 Constrained Neural Architecture… · p. 25, Figure S11 · p. 25
• HeSBO improved strongly in early iterations but flattened quickly and ended worse than random on average.Source: S9 Constrained Neural Architecture… · p. 25

Task definition

• The task optimizes a simulated robot gait policy to reach a target location within a fixed time while reducing joint velocities and height deviation.The controller is a Central Pattern Generator, and the objective is evaluated after a 30-second trajectory.Source: S10 Locomotion Optimization Problem · p. 25

Optimization performance

• CMA-ES was the clear best-performing method across the 50-run locomotion optimization experiment.All methods showed high variance in final best values; the supplied passage identifies CMA-ES as the clear best performer.Source: S10 Locomotion Optimization Problem · p. 25
• ALEBO had the lowest variance in final best value and therefore the most robust performance.SMAC found a good value in one run but performed slightly worse than ALEBO on average, while TuRBO performed better.Source: S10 Locomotion Optimization Problem · p. 25