Understanding High-Dimensional Bayesian Optimization

We appreciate the reviewer's positive feedback regarding the insights and empirical observations presented in our paper. We are glad to hear that our work is seen as valuable to the HDBO community, well-written, and enjoyable.

General claims in the title and abstract

We will tone down the "identifying fundamental challenges" part of the text and edit the abstract and introduction to communicate the empirical focus of our work to set the right expectations for the reader.

Sublinear regret bounds

Most theoretical analyses of Bayesian Optimization, including those that derive sublinear regret bounds, assume that the acquisition function can be maximized exactly [1-4]. RAASP, as a technique to avoid vanishing gradients of the acquisition function, is orthogonal to this. Arguably, it was a long-standing belief that maximizing the acquisition function is simple enough for proofs not to focus on this aspect [5]. Our analysis shows that the error introduced during the acquisition function maximization deserves more attention, but we leave the derivation of sublinear regret bounds under RAASP for future work.

References

We appreciate the suggestion to include more recent references on additivity assumptions. We will incorporate the recommended papers to contextualize our work better.

Typos and minor issues

We will correct the typos and clarify the interchangeable use of 'acquisition function' and 'AF.' We will also fix the undefined reference and ensure consistency throughout the paper.

[1] Srinivas, Niranjan, et al. "Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design." Proceedings of the 27th International Conference on Machine Learning.

[2] Wu, Kaiwen, et al. "The behavior and convergence of local bayesian optimization." Advances in neural information processing systems 36 (2023)

[3] Scarlett, Jonathan. "Tight regret bounds for Bayesian optimization in one dimension." International Conference on Machine Learning.

[4] Wang, Ziyu, and Nando de Freitas. "Theoretical analysis of Bayesian optimisation with unknown Gaussian process hyper-parameters." arXiv preprint arXiv:1406.7758 (2014).

[5] Bull, Adam D. "Convergence rates of efficient global optimization algorithms." Journal of Machine Learning Research 12.10 (2011).

We would like to thank the reviewer for their positive feedback, particularly for recognizing the thorough analysis of Gaussian Processes in high-dimensional Bayesian Optimization (HDBO), as well as the clarity and practical insights provided in the paper. We appreciate the reviewer's thoughtful comments and considered each point to enhance the clarity and impact of our manuscript, as detailed below.

Focus on Gaussian Processes

We will clarify in the discussion section that our analysis is specifically tailored to GPs and does not extend to other surrogates. This focus allows us to provide a deep dive into the behavior of GP length scales in high-dimensional spaces. However, studying other surrogates is an important avenue for future work. The vanishing gradients we observe are primarily related to popular stationary kernels for which the covariance of two points vanishes quickly with their distance. Other surrogates, such as random forests or Bayesian neural networks, use different techniques to relate input and output similarity and may show different susceptibility to vanishing gradients.

We appreciate the positive feedback regarding the clarity of our writing and the potential impact of our simple yet effective solution. We implemented enhancements to clarify our methodology and bolster the impact of our findings.

Implementation of RAASP

We will improve the description of the RAASP implementation in Section 3.2. We will further clarify that MSR uses BoTorch’s RAASP implementation. Since we cannot upload a revised manuscript, we will briefly outline the details here.

We perturb the top 5% observations using a normal distribution with $\sigma=0.001$, truncated within $\mathcal{X}$. For $D\geq 20$, we also generate samples with only a subset of dimensions perturbed, each with a $\frac{20}{D}$ probability. Of $4m$ random samples, $2m$ are global samples from a scrambled Sobol sequence, $m$ are local samples around the top 5%, perturbing all dimensions, and $m$ are local samples around the top 5%, perturbing 20 dimensions on average if $D\geq 20$, or all dimensions if $D<20$. We call the $2m$ local samples the RAASP samples. The starting points for the gradient-based optimization of the acquisition function are drawn from the $4m$ overall samples using Boltzmann sampling [1].

Details on the AF and its optimization

We will expand the methodology section to detail the AF and optimization process without RAASP to improve reproducibility and clarity. We briefly outline the details below.

We use the LogEI AF [1] for its numerical stability. It is maximized by evaluating it on 512 scrambled Sobol points, then selecting five starting points via Boltzmann sampling for gradient-based optimization using L-BFGS-B, with up to 2000 iterations.

Magnitude of the contribution

This work sheds new light on key challenges and fundamental issues in HDBO, like vanishing gradients in GP model fitting and AFs. These are critical for understanding the limitations of popular algorithms and were not part of prior work. This revision of prior concepts will prompt broader comfort for BO practitioners to use methods such as DSP and MSR. We expect that our identification of a more straightforward, high-performing implementation - supported by uncovering fundamental principles and efficiencies - enables researchers to investigate novel algorithmic variations and applications. MSR introduces a simple initialization method for GP length scales using MLE that scales with the problem dimensionality, eliminating the need for prior beliefs (Section 4). We further identify the importance of RAASP for avoiding vanishing gradients and reducing variance in length scale estimates (Sections 3.2 and 4). We also show that the MLE estimates have high variance while MAP estimates are biased, relating it to the variance-bias tradeoff (Section 3.3).

Comparisons with other HDBO algorithms

We now compare our method with TuRBO (https://ibb.co/jkx3MXN1), which is competitive on Mopta08 and Lasso-DNA and performs well on Humanoid for the first half of the optimization but stagnates in the second half.

Discussion of AF optimization budgets

We interpret this comment as 1) gradient descent budget, 2) RAASP budget, and 3) multi-start initialization for the AF. We will clarify this in the manuscript by adding these explanations.

1. We capped the number of gradient descent steps to 2000, the BoTorch default budget. We will add to the manuscript that this budget is rarely depleted, as shown in this histogram plot https://ibb.co/bjQQvskj
2. When augmenting the candidate set of starting points for the AF maximization with RAASP samples, we see fewer gradient descent steps required to optimize the AF. This aligns with previous work claiming that EI attains maxima close to good observations [1,2] and our observation that the starting points for the gradient-based AF maximizer predominantly originate from the RAASP samples. We will add this explanation to the manuscript and pose the question of how much optimization is sufficient in the future work section.
3. Evaluating the AF on more initial points before selecting starting points can reduce the risk of vanishing gradients. This figure (https://ibb.co/XkL4yCpn) illustrates this by plotting the fraction of points that moved a positive distance after maximizing the AF against the number of initial points. We maximized LogEI on a 50-dimensional GP prior sample ($\ell=0.2$, isotropic kernel) and repeated the experiment 50 times. With $2^{11}$ random samples, only 2% of final candidates moved a non-zero distance. With $2^{17}$ samples, this increased to 50%. Using RAASP sampling with just 512 raw samples, none of the starting points exhibited vanishing gradients across all 50 repetitions.

These discussions will corroborate our arguments, and we will add them to the manuscript.

[1] Ament et al. "Unexpected improvements to expected improvement for bayesian optimization." NeurIPS 2023

[2] Hvarfner et al. "Vanilla Bayesian Optimization Performs Great in High Dimensions." ICML 2024

We are grateful for the reviewer's thoughtful feedback and recognition of our work's strengths, particularly the systematic summary of high-dimensional Bayesian optimization (HDBO) issues and the effectiveness of our proposed methodology. In response to the constructive comments, we have addressed the concerns and further strengthened our contributions.

Structure of the Lasso-DNA and Mopta08 benchmarks and inclusion of additional benchmarks

We recognize the reviewer's concern about the structural risks associated with Lasso-DNA and Mopta08. Since these benchmarks are nearly always included in related work, we included them to demonstrate the effectiveness of our method in scenarios with specific structural properties against other methods. In the spirit of ensuring a broader evaluation, we added the SVM benchmark [1] (https://ibb.co/jkx3MXN1) and will add another benchmark for the camera-ready version at the latest.

Add baselines that use the RAASP sampling strategy, such as TuRBO, and compare against recent SOTA methods like RDUCB.

As demonstrated in [2], the DSP method we compare to already significantly outperforms RDUCB. Given this established performance gap, we have focused our comparisons on DSP. However, we acknowledge RDUCB and other milestones in HDBO in the related work section. To provide additional data points, as suggested by the reviewer, we have now added TuRBO (https://ibb.co/jkx3MXN1). TuRBO is competitive on the Mopta08 and Lasso-DNA benchmarks and has good anytime performance on Humanoid for the first half of the optimization but stagnates in the second half.

Include a baseline that uses RAASP without scaled length scales to isolate the effect of RAASP.

We have included TuRBO as a baseline that uses RAASP without scaled length scales (https://ibb.co/jkx3MXN1). We further compare MLE without scaled length scales to RAASP (https://ibb.co/6J7g8XRn) and will add this result to the appendix.

MSR is simply a combination of previous works.

While MSR builds on existing techniques, its practical significance lies in effectively combining them to address the challenges of HDBO and provide a straightforward yet powerful approach that practitioners can readily adopt.

Revise Section 4 to identify and describe each method mentioned clearly.

We will revise Section 4 to improve clarity, ensuring each method is identified and described, making the experimental setup and benchmarks easier to follow.

Potential for incorporating MSR with other HDBO techniques.

Integrating MSR with methods such as TRs, adaptive subspace embeddings, and additive structures is a relevant future work direction, which could further enhance the performance and applicability of MSR in various HDBO scenarios. We will add this idea in the future work section.

[1] Eriksson, David, and Martin Jankowiak. "High-dimensional Bayesian optimization with sparse axis-aligned subspaces." Uncertainty in Artificial Intelligence. PMLR, 2021.

[2] Hvarfner, Carl, Erik Orm Hellsten, and Luigi Nardi. "Vanilla Bayesian Optimization Performs Great in High Dimensions." International Conference on Machine Learning.