# Automated Random Embedding for Practical Bayesian Optimization with Unknown Effective Dimension

arXiv: https://arxiv.org/abs/2605.23473 · HTML: https://mlsanity.com/paper/2605.23473/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 42 references that are in the map.
- First posted on arXiv 22 May 2026.

## Builds on (most cited first, 24 of 24)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Automatic chemical design using a data-driven continuous representation of molecules](https://mlsanity.com/paper/1610.02415/) (2016)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [Bayesian Optimization in a Billion Dimensions via Random Embeddings](https://mlsanity.com/paper/1301.1942/) (2013)
- [High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspaces](https://mlsanity.com/paper/2103.00349/) (2021)
- [Re-Examining Linear Embeddings for High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2001.11659/) (2020)
- [Vanilla Bayesian Optimization Performs Great in High Dimensions](https://mlsanity.com/paper/2402.02229/) (2024)
- [A survey on high-dimensional Gaussian process modeling with application to Bayesian optimization](https://mlsanity.com/paper/2111.05040/) (2021)
- [BBTv2: Towards a Gradient-Free Future with Large Language Models](https://mlsanity.com/paper/2205.11200/) (2022)
- [Increasing the Scope as You Learn: Adaptive Bayesian Optimization in Nested Subspaces](https://mlsanity.com/paper/2304.11468/) (2023)
- [LassoBench: A High-Dimensional Hyperparameter Optimization Benchmark Suite for Lasso](https://mlsanity.com/paper/2111.02790/) (2021)
- [LIMO: Latent Inceptionism for Targeted Molecule Generation](https://mlsanity.com/paper/2206.09010/) (2022)
- [Monte Carlo Tree Search based Variable Selection for High Dimensional Bayesian Optimization](https://mlsanity.com/paper/2210.01628/) (2022)
- [Are Random Decompositions all we need in High Dimensional Bayesian Optimisation?](https://mlsanity.com/paper/2301.12844/) (2023)
- [Active Learning of Linear Embeddings for Gaussian Processes](https://mlsanity.com/paper/1310.6740/) (2013)
- [Standard Gaussian Process is All You Need for High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2402.02746/) (2024)
- [The Differentiable Cross-Entropy Method](https://mlsanity.com/paper/1909.12830/) (2019)
- [High Dimensional Bayesian Optimization via Supervised Dimension Reduction](https://mlsanity.com/paper/1907.08953/) (2019)
- [Comparison of High-Dimensional Bayesian Optimization Algorithms on BBOB](https://mlsanity.com/paper/2303.00890/) (2023)
- [Derivative-Free Reinforcement Learning: A Review](https://mlsanity.com/paper/2102.05710/) (2021)
- [Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits](https://mlsanity.com/paper/2206.03520/) (2022)
- [Relaxing the Additivity Constraints in Decentralized No-Regret High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2305.19838/) (2023)
- [Constrained global optimization of functions with low effective dimensionality using multiple random embeddings](https://mlsanity.com/paper/2009.10446/) (2020)
- [A Collection of Challenging Optimization Problems in Science, Engineering and Economics](https://mlsanity.com/paper/1504.02366/) (2015)

## Abstract (arXiv)

Bayesian optimization is widely employed for optimizing complex black-box functions but struggles with the curse of dimensionality. Random embedding, as a dimension reduction strategy, simplifies tasks that possess the effective dimension by optimizing within a low-dimensional subspace. However, determining the effective dimension of a task in advance remains a significant challenge, which influences the selection of the subspace dimensionality and the optimization performance. Traditional methods use fixed subspace dimensions provided by experts or rely on trial and error to estimate subspace dimensions with resources consumed. To this end, this paper proposes an automated random embedding for high-dimensional Bayesian optimization with unknown effective dimension, called Dynamic Shared Embedding Bayesian Optimization (DSEBO). DSEBO starts with a low dimension and switches to a higher subspace if the solutions in the current subspace show preliminary convergence. DSEBO dynamically determines the dimension of the next subspace based on the quality of the solutions in different subspaces and shares the queried solutions with the new subspace for a better initialization. Theoretically, we derive a regret bound for DSEBO and demonstrate that DSEBO can better balance approximation and optimization errors. Extensive experiments on functions with dimensionality of varying magnitudes and real-world tasks with unknown effective dimensions reveal that, compared with state-of-the-art methods, alternating optimization across different subspaces results in significant improvements in high-dimensional optimization, both in terms of optimization regret and time.