Enhancing Trust-Region Bayesian Optimization via Derivatives of Gaussian Processes

• The validity of Assumptions 2, 3, and 4 is not discussed. I believe that these assumptions are not valid under the assumption $f \sim \mathcal{GP}(0, k)$ (suggested in Assumption 1), even if we adopt commonly-used SE or Matérn family kernels. Some assumptions seem to be valid for these commonly-used kernels by relying on more careful probabilistic arguments; however, others are unknown to me. I summarize my current understanding below:
  • Assumption 3: When the kernel is SE or Matérn, the boundedness of the sample path is valid with high probability if the input domain is compact (e.g., Ghosal & Roy (2006), Kandasamy et al. (2019)); however, the same result does not hold for $\mathbb{R}^D$ (as the authors assumed).
  • Assumption 1: When the kernel is four times continuously differentiable and stationary, the Lipschitz assumption holds with high probability for the compact input domain (e.g., Srinivas et al. (2009)).
  • Assumptions 2 and 4: When the kernel is four times continuously differentiable and stationary, the gradient norm is bounded from above with high probability in a compact input domain (e.g., Srinivas et al. (2009)); however, I do not know of any existing results that suggest the true and approximate Hessian matrices are bounded from above.

Ghosal, Subhashis, and Anindya Roy. "Posterior consistency of Gaussian process prior for nonparametric binary regression." (2006): 2413-2429.
Srinivas, Niranjan, et al. "Gaussian process optimization in the bandit setting: No regret and experimental design." arXiv preprint arXiv:0912.3995 (2009).
Kandasamy, Kirthevasan, et al. "Multi-fidelity Gaussian process bandit optimization." Journal of Artificial Intelligence Research 66 (2019): 151-196.

• There seem to be some gaps between the theoretically and practically verified algorithms without discussion. Discussions about the following gaps are desired:
  • The explanations in Section 3 and the empirical evaluations in Section 6 seem to allow noisy function evaluations; however, the theory and algorithm construction rely on noise-less function evaluation (e.g., Line 8 in Algorithm 1, construction of $m_k$ in Eq.(2)).
  • The treatment of the trust regions is different between practical (Lines 190, 191) and theoretical (Algorithm 2) usages.
  • The random subset-selection of the dimensions (Lines 213-226) seems not to be considered in the theorems.
• The description of the experimental section is inadequate to reproduce the results for the reader. For example, clarification of the following settings is desired:
  • The choice of the kernel.
  • The treatment of the hyperparameters of the kernel.
  • The parameter settings of the local optimization routine.

(Minor)

• Last year's NeurIPS paper (Wu et al. (2023)) is closely related to this paper in the sense that the convergence of the local Bayesian optimization routine is analyzed.

Wu, Kaiwen, et al. "The behavior and convergence of local Bayesian optimization." Advances in Neural Information Processing Systems 36 (2023).

Overall, I find the paper lacks clarity, particularly in the theory section. Each theorem or lemma is presented without any motivation or discussion, making them feel disconnected from the rest of the paper. Additionally, the presentation of the method itself sometimes lacks clarity; for example, the trust region update strategy is barely discussed, including how the trust regions are initialised.

1. The methods seem to have merit but are hard to validate due to the paper's lack of rigor and presentation clarity.

2. The authors claim their method is more sample-efficient than TRBO. Experimental results show that their method, TRBO-B, is sample efficient and obtains better final values than TRBO (as shown in the bottom row of Fig 1 and Fig 2). Why is that the case? It invalidates all the claims for me. Maybe I am wrong.

3. The paper suffers from issues in presentation, with insufficient explanations of key concepts, unclear notation, and missing justifications for several methodological choices. The cumulative effect of these issues reduces the paper's accessibility and perceived rigor. Here are the main points which make it hard to follow: a. The authors claim TRBO suffers from sample inefficiency. Nowhere in the paper is it explained or shown why that is the case. b. Why does using gradients and Hessians lead to better sample inefficiency? Why did the authors make this decision? c. The algorithm is stated without any explanation. How do the authors choose the final point? It seems like Algorithm 1 returns a point for each trust region. d. Baselines and experimental settings are not explained. What is ALEBO? Why did you compare against it? What is Griewank's function, or what is Ackley's?

4. The theoretical results and the actual proofs are stated in the middle of the paper without any supporting text. It is hard to infer what the authors are trying to show and validate its correctness.

Suggestions:

1. Please improve the presentation rigor. Each technical claim and design decision needs to be motivated.
2. The theoretical results need supporting text to explain the math and claims clearly.
3. Experimental settings and results need to be clearly explained.

1. I think an important related work [1] is missed by the authors, where the convergence analysis is conducted on a local BO method using GP gradients. The current work seems extend the convergence analysis to the multiple trust region setting.

2. The current experiment results only optimize the problem with a few hundred evaluations, which is far from convergence. I think more evaluations (e.g. a few thousand in original TuRBO paper) can better access the algorithm performance along with the convergence analysis.

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

[2] Eriksson, David, et al. "Scalable global optimization via local Bayesian optimization." Advances in neural information processing systems 32 (2019).

1. The complexity experiments are not included in the paper
2. The code has not been found in the paper

To me, it seems that more background and discussions on the original TuRBO method (Eriksson et al., 2019) could be provided. For instance, TuRBO method and the newly proposed TuRBO-D method has the following differences, which would be helpful to discuss the motivations and reasons:

1. TuRBO uses local GP within each trust region to deal with large number of observations, whereas TuRBO-D does local quadratic approximation to a glocal GP instead of local GPs
2. TuRBO choose samples across trust regions through Thompson sampling, whereas TuRBO-D traverse through all trust regions recursively, each time choosing a sample from a trust region.

There are many real world applications in the TuRBO paper (Eriksson et al., 2019). While the current applications do provide certain convincing justifications, it would be helpful to also see how TuRBO-D performs in applications of the TuRBO paper.

1. From my understanding and as the authors also describe in their paper, a main strength and motivation of TuRBO is to allow for the heterogeneous modeling of the objective function which is especially important in high dimension. This is done by local GP fits. On the other hand, the authors' approach globally fits the GP which seems to basically forgo this important strength of TuRBO. In other words, if the global GP fit is bad, then the extracted derivatives are also badly informed, and thus the method would work poorly in high dimension. The authors claim that their approach gains sampling efficiency, but how important is this compared to the heterogeneity in modeling the objective? It seems that heterogeneity is more important, as the GP fit typically depends negligibly on points that are far away but a poor modeling of the objective function is more impactful (please correct me if I'm wrong).

2. The main theoretical result (Theorem 4) is weak in the following sense: It says, with high probability, the inf of gradient over the solution sequence is close to 0. However, this inf only means that there exists a subsequence whose gradients are close to 0. If we stop the algorithm at some large iteration step, there is no guarantee that the gradient is small since that step may not be in that subsequence. That is, even putting aside the lack of convergence rate etc. (which I understand can be difficult to obtain in general for BO algorithms) and viewing at a basic level, the theoretical result does not seem meaningful.

The above are my main concerns. Additionally,

1. The authors propose to use a subset of dimensions instead of full dimension to form the quadratic approximation, but the theoretical analyses do not take this into account.

2. A possible strength of TuRBO is that the local fit uses less computation due to the smaller matrix inversion. However, by global fitting, the authors' approach faces a computation load as high as standard BO (as least for this posterior update step). This might need some discussions.

3. The implementation of the main benchmark TuRBO has no details, and it's unclear if the comparison is fair. E.g., how do you set the hyperparameters for TuRBO and TuRBO-D?