acceptodds
Withdrawn from ICLR 2027

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

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

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.

Primary area:
optimization
Keywords:
high-dimensional Bayesian optimization, embedding optimization, low-dimensional embeddings, evolutionary algorithms, black-box optimization

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_XpNxOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes a Bayesian optimization method for high-dimensional space, where embedding is optimized using objective evaluations. It combines an evolutionary algorithm, which is used to searching embeddings, and BO, which is used for searching the optimum in the embedding space. In the experiments, the proposed method is compared with existing BO methods on optimization of synthetic functions, rover trajectory planning and hyperparameter tuning in support-vector regression.

Critical strengths

It searches embedding that is useful for Bayesian optimization.

Critical weaknesses

The technical contribution of the proposed method is incremental. There have been proposed many embedding existing methods for BO, and existing methods for learning embeddings. The use of an evolutionary algorithm for optimization is not well motivated.

For learning the embeddings using the evolutionary algorithm, it requires a lot of evaluations of expensive black-box functions. In Figure 2, the number of evaluations used for learning the embedding should be included for fair comparison. Since the total cost is large, it is unclear in what kinds of situations the proposed method is useful.

There are many hyperparameters in the proposed method, whose appropriate values might be different across tasks.

Questions for authors

How do we tune the hyperparameters of the proposed method?

Reviewer_VMY5OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper studies high-dimensional Bayesian optimization (HDBO) with bounded linear embeddings. Its central observation is that an embedding determines not only a low-dimensional subspace but also the bounded region accessible to the optimizer; consequently, even two bases spanning the same subspace may induce different reachable sets. Based on this observation, the paper proposes Evolutionary Embedding Search (EES), which maintains a population of orthonormal embedding matrices, evaluates each matrix using a shared Sobol design, and evolves the population according to a score combining the mean of the best sampled objective values and a clipping penalty. A standard GP with LogEI is then run for 100 evaluations in the selected embedding.

The paper provides geometric results concerning basis dependence, reachability, clipping, and restriction error. Empirically, EES is compared with random-embedding and shuffled-score controls, several HDBO baselines, and Sobol sampling on synthetic benchmarks, rover trajectory optimization, and SVR hyperparameter/feature-scale optimization.

Critical strengths
  • Clear and useful geometric motivation. The distinction between selecting a subspace and selecting a bounded embedding is important and often underemphasized. Proposition 1 and the accompanying examples clearly demonstrate why basis orientation matters when the latent domain is bounded.

  • Careful experimental controls. The random-pool and shuffled-score baselines are useful attempts to isolate the value of objective-guided evolution. Sharing the same Sobol points among candidates within a generation is also a sensible variance-reduction device.

  • Strong transparency and reproducibility. The paper is unusually explicit about unequal budgets, initialization differences, configuration selection, noisy observations, SVR preprocessing, and negative follow-up results. The appendix provides extensive implementation and statistical details.

  • Generally strong presentation. The paper is well organized, the figures are readable, and the distinction between embedding search and subsequent BO is maintained consistently.

Critical weaknesses
  • The comparison against direct BO methods does not establish an equal-cost end-to-end efficiency advantage. Figure 3 does evaluate the complete EES pipeline, including embedding selection followed by BO. However, the plotted horizontal axis contains only the 100 subsequent BO evaluations. EES additionally spends 102,400 objective evaluations on embedding search, while BAxUS, TuRBO-1, Vanilla BO, and the other direct baselines use only the displayed 100 evaluations. Thus, the experiment demonstrates that an extensively optimized embedding can support better subsequent BO, but it does not show that EES is more sample-efficient under a matched total objective-evaluation budget. Figure 9 partially addresses total cost through an equal-budget Sobol reference, but no equally budgeted adaptive BO baseline is included.
  • The application evidence is affected by configuration selection and becomes substantially weaker on new seeds. The displayed application settings are selected from the same 1212-configuration grid and five seeds used to report performance. Thus, the main Rover and SVR curves include in-sample configuration-selection optimism, while the cost of choosing (s,d)(s,d) is not part of the reported method budget. More importantly, in the reduced-budget evaluation on ten new seeds, the confidence intervals against the random pool include zero on both applications. On SVR, spherical linear BO wins all 10 final-value comparisons, despite using a much smaller total objective budget. This result weakens the claim that the application experiments demonstrate a reliable practical benefit.
  • The final embedding selection lacks an independent validation step. Retained matrices are reevaluated on multiple generation-specific Sobol designs, and each evaluation is stored as a separate archive entry. Final selection may therefore choose the most favorable realization of a repeatedly evaluated matrix rather than the matrix with the best expected score. The subsequent BO experiments provide useful out-of-sample evidence that mitigates this concern, but an independent final rescore or aggregation of repeated measurements would be needed to validate the embedding score itself and to separate proposal adaptation from evaluation-allocation effects.
  • The experiments do not isolate the basis-orientation mechanism emphasized by the geometric analysis. EES searches the full Stiefel matrix, so both the column space and the orientation of the bounded latent box change simultaneously. Consequently, its improvement over random or shuffled-score controls may be driven primarily by better subspace alignment rather than by optimizing the basis within a fixed subspace. Proposition 1 establishes that basis orientation can matter, but a fixed-subspace experiment over B=UQB=UQ, or a comparison between Stiefel, Grassmann, and basis-only search, is needed to determine whether this mechanism materially contributes to the reported gains.
Questions for authors
  • Does EES remain competitive with strong adaptive BO baselines when all methods receive the same total objective-evaluation budget, including embedding search?
  • Can the application configurations (s,d)(s,d) be selected on one set of seeds and evaluated on an independent set? How should the main SVR result be reconciled with the weaker reduced-budget follow-up?
  • Does EES retain its advantage if shortlisted embeddings are independently rescored on fresh Sobol points, or if repeated evaluations of the same matrix are aggregated before final selection?
  • Can the authors include a fixed-subspace experiment, such as optimizing B=UQB=UQ with UU fixed, to determine how much of the gain comes from basis orientation rather than selecting a better subspace?
Reviewer_6puxOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes a new approach Evolutionary Embedding Search (EES) to construct low-dimensional embedding for high-dimensional Bayesian optimization (HDBO). The authors show that the subsequent BO performance of EES can outperform other embedding approach for HDBO on synthetic and two real-world benchmark.

Critical strengths

None

Critical weaknesses

The proposed approach requires an impractically large number of evaluations before BO begins, which conflicts with the setting BO is designed for. Accordingly, the proposed method is unrealistic and it totally doesn't make sense in my mind. According to the experiment setting in Table 1, the proposed approach require G×N×m=20×10×512G\times N \times m = 20 \times 10 \times 512 samples before performing any BO run.

Furthermore, the approach introduced in this paper involve many hyperparameters that need careful tuning. The robustness of the algorithm's performance to those hyperparameters remain unclear, which makes this algorithm a poorly designed method.

Questions for authors

N/A

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.