Learning Where to Search: Evolutionary Embedding Search for High-Dimensional Bayesian Optimization

Bayesian optimization (BO) uses probabilistic models to optimize expensive black-box functions, guiding evaluations with predictions and their uncertainty. In high-dimensional BO (HDBO), fixed random embeddings reduce the number of search variables but leave the choice of bounded search region unoptimized for the objective. This region may therefore exclude good solutions that further BO evaluations cannot reach. To address this limitation, we propose Evolutionary Embedding Search (EES), which directly optimizes the embedding using objective evaluations. EES maps the same low-dimensional sample points through candidate embeddings and uses their objective values to guide evolution before running BO in the selected region. Our analysis motivates this matrix search: even within the same subspace, rotating a bounded embedding can change which solutions BO can reach. On synthetic benchmarks, EES achieves lower mean final log regret than random embedding search and evolution with shuffled scores under matched budgets. In real-world application benchmarks for rover trajectory planning and support-vector regression, EES also finds better solutions early in the subsequent BO run than direct baselines. The results show that optimizing the embedding, not only the points within it, can improve subsequent BO, and position EES as a direct, derivative-free mechanism for learning where HDBO should search.