Relaxing the Additivity Constraints in Decentralized No-Regret High-Dimensional Bayesian Optimization

We thank you for the detailed review. We address the comments and questions you have raised below: **This decomposition is not explicitly explained in Section 3.1** Thank you for the suggestion. Figure 2 was not included in the main text for lack of space. Under acceptance, we will try to make room for it or to improve the presentation of the additive decomposition. **The authors assume that the acquisition function is a restricted prox-regular function that satisfies the KL condition’’. The authors should provide a formal definition of this condition. [...] The authors might discuss under what conditions the acquisition function satisfies this assumption.** In the updated PDF, we prove that this assumption (Assumption 5.1 in the previous version of the paper) always holds under a very mild assumption on the Hessian matrix of the kernel (Assumption 3.1 in the updated PDF), which is met by the majority of common kernel functions used in BO. Assumption 5.1 has now become Theorem 5.1 in the updated PDF, and is proven in Appendix F. **The theoretical results do not exhibit sufficient novelty.** As mentioned above, please refer to the updated PDF as we believe our new theoretical result (Theorem 5.1) significantly strengthens the theoretical value of the paper. It removes the potentially strong assumption on the acquisition function (Assumption 5.1 in the previous version of the paper), replacing it by a much weaker assumption (Assumption 3.3 in the updated PDF) that is met by the majority of common kernel functions used in BO. **Is the algorithm performance sensitive to the inference results of the decomposition? How to incorporate the inference uncertainty into the regret analysis?** Indeed, the quality of the decomposition will impact the performance of the algorithm. When the additive decomposition is unknown, [1] is used to infer it. Under the hood, [1] uses a Monte-Carlo Markov Chain (MCMC) method, and more specifically a Metropolis-Hastings algorithm. As far as we know, it does not provide any uncertainty criterion. Using the absolute difference of log-likelihoods between decompositions as a distance on the space of possible additive decompositions could perhaps allow us to define an uncertainty criterion on the decomposition. We did not explore this in the current work, but it is an interesting extension to our paper, and we will definitely consider it for future work. Thank you for the suggestion. **How many rounds are required to generate the data for decomposition inference?** The experiments in [1] suggest that, under a hundred iterations, the MCMC approach is able to match the performance obtained from the true additive decomposition. **The authors might provide a more detailed comparison with the existing algorithm Add-GP-UCB, since the decomposition of the objective function is quite similar.** In our opinion, ADD-GP-UCB and DuMBO are not really similar. Unlike DuMBO, ADD-GP-UCB assumes a very low $\bar d$ with orthogonal domains. Note that a similar comment can be made for DEC-HBO (although the MFS does not have to be as low as the one required by ADD-GP-UCB, it still needs to be quite low, which tends to limit the complexity of the additive decomposition inference). Conversely, our algorithm does not make any assumption on the additive structure of $f$. This feature is actually one of the main strengths of our algorithm, as it allows DuMBO to infer arbitrarily complex additive decomposition, and to outperform significantly both ADD-GP-UCB and DEC-HBO (please refer to Table 2 or, more specifically, to Figures 1(a-c) and 4(b)). [1] Gardner, J., Guo, C., Weinberger, K., Garnett, R., & Grosse, R. (2017, April). Discovering and exploiting additive structure for Bayesian optimization. In Artificial Intelligence and Statistics (pp. 1311-1319). PMLR.

Dear reviewer, This is a gentle reminder that our rebuttal as well as our updated paper are online. In particular, we draw your attention on Theorem 5.1 that addresses a concern you have raised and that, in our opinion, significantly strengthens the theoretical contribution of this paper by establishing the asymptotical optimality of DuMBO under a very mild assumption (Assumption 3.3). We also added more baselines to our numerical results (see Section 6) to strengthen our experiments. We understand that your time is very valuable, but as the discussion period ends in a few days, we kindly ask you to consider providing any feedback and/or increasing your score. We are of course ready to discuss any remaining concern you may have.

We thank you for the detailed review. We address the comments and questions you have raised below: **It would have been nice if the authors could show a proof sketch of their main theoretical result.** Thank you for the suggestion. A proof sketch was not included in the main text because of lack of space, but we will include it in the camera-ready version, space permitting. **It would be nice if the authors could highlight the main contributions and the technical (or analytical) challenges they faced. [...] What were the major technical challenges the authors faced while deriving the regret bounds?** Thank you for the suggestion. Our main analytical challenge was embodied by Assumption 5.1, but has been lifted now as it became Theorem 5.1. We kindly refer you to the updated PDF for this new result that completes the theoretical proof of the asymptotic optimality of DuMBO. Under acceptance, we will try to make room for highlighting the contributions and the challenges we faced. **Are there known lower bounds for the problem? If yes, it would be nice to see how the proposed algorithm does in comparison.** We are not aware of a lower bound on the regret for this problem, especially under the additive assumption. If you have any references to this matter, we will be happy to further investigate this point and discuss it with you.

We thank you for the detailed review. We address the comments and questions you have raised below: **The paper's experiment part is not valid enough. The baseline it compares TurBo is not that up to date. Also notice that in the paper, some other methods are mentioned, but didn't show up in the experiments part.** Thank you for bringing up this additional reference. Note that this paper proposes to use a meta-algorithm (as coined by the authors themselves) that relies on other high-dimensional BO algorithms (and especially TuRBO) for their sampling needs. In contrast, our paper proposes a no-regret BO algorithm, DuMBO, that solves high-dimensional problems by assuming an additive decomposition of the objective function. This is why we compare DuMBO directly to other no-regret BO algorithms, including TuRBO. To fully address your concerns, we added two other baselines in our experiments. Please refer to Figures 1, 4 and 5 in the updated PDF. **In general, the performance improvement to other baseline is not significant enough.** With all due respect, we beg to differ. The results in the updated PDF show that DuMBO consistently outperforms all the 6 other baselines by more than a confidence interval in 4 out of 7 benchmarks. In the 3 remaining benchmarks, DuMBO systematically belongs to the set of top performing BO algorithms. This observation is further illustrated by Figure 1 in the main text and Figures 4 and 5 in the appendix. Moreover, when the additive structure of the function is known, DuMBO can exploit this additional information, and obtain performance that are even better (see Table 2, line ADD-DuMBO). **Ablation study about other hyperparameters should be given.** The only hyperparameter of our method is the parameter $\eta$ in the augmented Lagrangian (see (11), or (12) in the updated PDF). Indeed $\bar d$ is computed by the algorithm (see below), and the kernel that is used is a well-known Matérn kernel, which is not a hyper-parameter specific to DuMBO. Note that DuMBO runs without having to adjust hyperparameters by hand. Indeed $\eta$ itself does not actually have to be set as a hyper-parameter, because it can be adjusted online, during the course of ADMM, without hindering the convergence guarantees. The detailed procedure is specified in [1], and this is indeed what we do in practice. We added a sentence regarding the value of $\eta$ under Equation (12) in the updated PDF. Thank you for pointing it out. **In Table 2, why the standard deviation is not given?** The standard deviations were not provided in Table 2 only to maintain its readability, because of lack of space. But they are displayed in all the relevant figures (please refer to Figures 1, 4, 5 and 7). Under acceptance, we could try to make room for them. We would be happy to discuss ways to include them in the main text, if you have some suggestions. **Is the algorithm sensitive to $\bar d$ and other hyper-parameters?** As $\bar d$ grows, the underlying additive decomposition of the objective function $f$ becomes more complex, in the sense that at least one factor increases its dimensionality. However, since we relaxed any assumption on $\bar d$ (and we do not require the user to provide it), Theorems 5.1 and 5.2 as well as Corollary 5.3 state that $\bar d$ will not influence the convergence in a significant manner. In fact, the larger $\bar d$ is, the better DuMBO performs when compared to the other additive no-regret BO algorithms. Conversely, when $\bar d$ is low, the assumptions made by other additive no-regret BO algorithms become more valid (or at least, less restrictive) so that their performance and DuMBO’s performance tend to become similar. This is pointed out in the comment of Figure 4(a), in the supplementary material. **In figure 1c. The performance of DuMBO is close to TurBO. Does that mean DuMBO does not outperform baseline much on higher dimensional tasks?** Unfortunately, we have to move the experiments discussing this point in the supplementary material because of lack of space. Among them, we compared the baselines on the Rastrigin function, with $d=100$ (Figure 4(c)): DuMBO significantly outperforms TuRBO in this example. Note that, unlike TuRBO, DuMBO is proven to be asymptotically optimal. Hence, in the long run, DuMBO’s asymptotic performance will be at least as good as those from TuRBO’s. In the short run, our experiments show that the transient performance of DuMBO is better in 5 out of the 7 benchmarks (see Table 2 and Figures 1 and 4).

**Why the time step is only about 100? For figure 1a. Some methods's cost are still decaying.** As mentioned at the beginning of Section 6, BO is usually applied for the optimization of expensive black-box functions. Hence we put the focus on the performance of all algorithms on the first hundred iterations. Note that this is a choice made by some previous works (e.g. [2, 3]). The rationale for this choice is that it is precisely in this first transient phase that methods that have not been shown asymptotically optimal can outperform their asymptotically optimal counterparts (since for the latter the theory predicts, by definition, a global convergence with a sublinear regret). Furthermore, rapid convergence matters for real-time applications. Nevertheless, to fully address your concerns, we have extended the number of iterations for Figure 1(a). The performance of all the baselines with this new horizon can be found in Table 2 (Powell column) and in Figure 1(a) in the updated PDF. [1] Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011). Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine learning, 3(1), 1-122. [2] Gupta, S., Rana, S., & Venkatesh, S. (2020, April). Trading convergence rate with computational budget in high dimensional Bayesian optimization. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 34, No. 03, pp. 2425-2432). [3] Hoang, T. N., Hoang, Q. M., Ouyang, R., & Low, K. H. (2018, April). Decentralized high-dimensional Bayesian optimization with factor graphs. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 32, No. 1).

We thank you for the detailed review. We address the comments and questions you have raised below: **The related works are missing [...] that do not impose assumptions on the structure of the function.** Thank you for bringing up these additional references. We included them in our Related Works section, and we also discuss them below. [1] This article introduces LineBO. Although the core idea in this article (successive line searches with random directions) does not impose any assumption on the structure of the function and allows LineBO to find its next query very rapidly, the algorithm does not provide a no-regret guarantee. We implemented LineBO and added it to our baselines. After testing this algorithm with our benchmarks, it seems that searching along a line becomes less effective as the dimension of the domain grows. Please refer to Table 2 and Figures 1, 4 and 5 in the updated PDF for the additional experimental results. Note that, unlike LineBO, DuMBO provides a no-regret guarantee and is less sensitive to the dimension of the problem. [2] This paper proposes MS-UCB. Its core idea is to perform the optimization of the acquisition function within two orthogonal, lower-dimensional subspaces $\mathcal{Y}$ and $\mathcal{Z}$ of dimension $d$ and $D - d$, respectively, instead of the original domain $\mathcal{X}$ of dimension $D$. MS-UCB is asymptotically optimal and does not impose any assumption on the structure of $f$. However, for the acquisition maximization, MS-UCB still uses a computationally expensive algorithm on subspace $\mathcal{Y}$ (this imposes $d << D$ in practice) and requires $O(t^{\alpha+1})$ GP inferences at each iteration $t$ on subspace $\mathcal{Z}$. If $\alpha$ is low, the cumulative regret is still sublinear but the average regret decreases quite slowly (see Theorem 2 in [2]). If $\alpha$ is large, MS-UCB becomes very slow in practice. We implemented MS-UCB and added it to our baselines. After testing this algorithm with our benchmarks, it appears that, similarly to LineBO, MS-UCB is very sensitive to the dimension of the problem. In fact, the acquisition function cannot be quickly maximized in $\mathcal{Z}$ without increasing $\alpha$ and drastically increasing the execution time. Please refer to Table 2 and Figures 1, 4 and 5 in the updated PDF for the additional experimental results. In contrast, DuMBO offers the same no-regret guarantee, but is decentralized, has a lower computational complexity, fewer hyperparameters and is able to exploit additional information about the problem (i.e., the additive structure of $f$, if it exists). [3] This paper proposes to use a high-dimensional Bayesian optimization algorithm (especially TuRBO) for their sampling needs: the authors do not propose a BO algorithm per se but a meta-algorithm (as coined by the authors) that relies on other BO algorithms. In contrast, our paper proposes a no-regret BO algorithm, DuMBO, that solves high-dimensional problems by assuming an additive decomposition of the objective function. This is why we compare DuMBO directly to other BO algorithms, including TuRBO. [4] Thank you for pointing us to this IMCL 2023 paper that appeared at the end of July. We are happy to add it in the related work section. Note that [4] appeared less than 2 months before the submission deadline and is considered by ICLR as contemporaneous. ICLR reviewing policy (see last item in the FAQ at https://iclr.cc/Conferences/2024/ReviewerGuide states indeed “if a paper was published (i.e., at a peer-reviewed venue) on or after May 28, 2023, authors are not required to compare their own work to that paper”. Nonetheless, we are also happy to engage in the discussion on that paper. It is based on the observation that decompositions that are learnt from data can be suboptimal. The authors conduct a regret analysis showing that, in an adversarial context, using random decompositions is on average the best way to lower the cumulative regret of a decomposing BO algorithm. However, they do not propose an algorithm that maximizes an acquisition function in an arbitrary dimensional space with a reasonable computational complexity. The paper is actually quite complementary to our work. In fact, instead of using [5] to infer an additive decomposition, the idea of random decompositions could be used in conjunction with our results (Theorems 3.5, 5.1, 5.2 and Corollary 5.3 in the updated PDF). This would increase the performance of the resulting BO algorithm in cases where the decomposition is hard to infer (although it would degrade its performance in other contexts). This is a very interesting extension and we will definitely consider it for future work. Thank you again for mentioning this reference. [5] Gardner, J., Guo, C., Weinberger, K., Garnett, R., & Grosse, R. (2017, April). Discovering and exploiting additive structure for Bayesian optimization. In Artificial Intelligence and Statistics (pp. 1311-1319). PMLR.

**Could we ensure to find the arg max when the function is non-convex? Do the authors need any assumption on the function $f$ such as the Lipschitz continuous to guarantee the convergence?** We do not need the function $f$ to be Lipschitz continuous because the assumptions given in Section 3.1, namely Assumption 3.1 and Assumption 3.3 in the updated PDF, provide sufficient regularity. **The experiments are insufficient to understand the effectiveness of the proposed method.** To fully address this concern, we implemented LineBO and MS-UCB and we added them to our baselines. The results (see Table 2) show that DuMBO consistently outperforms all the 6 baselines by a margin larger than one confidence interval on 4 out of 7 benchmarks. In the remaining 3 benchmarks, DuMBO is consistently in the set of the top performing BO algorithms. Moreover, when the additive structure of the function is known, DuMBO can exploit this additional information and obtain performance that is even better (see Table 2, line ADD-DuMBO). **Equation (8) seems incorrect to me. Is it a typo?** Thank you for pointing out (8). It is indeed a typo, that we corrected in the updated PDF.

Dear reviewer, This is a gentle reminder that our rebuttal as well as our updated paper are online. In particular, we draw your attention on Theorem 5.1 that addresses a concern you have raised and that, in our opinion, significantly strengthens the theoretical contribution of this paper by establishing the asymptotical optimality of DuMBO under a very mild assumption (Assumption 3.3). We also added more baselines to our numerical results (see Section 6) to strengthen our experiments. We understand that your time is very valuable, but as the discussion period ends in a few days, we kindly ask you to consider providing any feedback and/or increasing your score. We are of course ready to discuss any remaining concern you may have.