This Too Shall Pass: Removing Stale Observations in Dynamic Bayesian Optimization

Dear Reviewer NVX3,

Thank you for the detailed review. We are discussing below the weaknesses and questions you have raised. Also, please make sure to read the global response as we discuss some of your questions there.

Lack of discussion of sparse Gaussian processes.

Thank you for pointing out this very interesting connection between the sparse GP literature and our work.

Although these works are definitely related to our problem (because they also seek to discard some observations while still preserving the quality of the GP inference), applying them to a dynamic setting would require some non-trivial modifications. More precisely,

(i) In their current form, these works introduce solutions that take place into a spatial domain only. Consequently, they try to approximate an exact GP over a bounded domain, and assume that they can place inducing inputs arbitrarily in this very same domain. Conversely, in the dynamic setting, the domain is constantly changing and the domain where the inducing inputs can be located is restricted to the cartesian product of the spatial domain and the past $[0, t_0]$, with $t_0$ the present time. Moreover, the exact GP should be approximated on a different, complementary, unbounded domain, that is the cartesian product between the spatial domain and the future $[t_0, +\infty]$.

(ii) Most sparse GP solutions have an hyperparameter that controls the number of inducing inputs to place. Unfortunately, this hyperparameter should be set specifically for each objective function. Conversely, W-DBO can adapt its dataset size depending on the nature of the objective function, without the need to adjust its hyperparameter.

Still, we acknowledge the connections described by the reviewer. Upon acceptance, we will definitely discuss the mentioned papers in Section 2 of the camera-ready version.

The proposed approximation of the 2-Wasserstein distance criterion is potentially loose.

We plan to study more the approximation of the ratio of Wasserstein distances in future works, in order to better understand it theoretically.

Dear Reviewer iNzn,

Thank you for the detailed review. We are discussing below the weaknesses and questions you have raised. Also, please make sure to read the global response as we discuss some of your questions there.

On the usage of an ARD kernel.

We make no mention of setting an ARD kernel for ABO, nor for any other DBO algorithms. Appendix G.1 lists the kernels used for each solution. Let us detail precisely the number of hyperparameters that each solution has to infer:

GP-UCB and ET-GP-UCB.

• Spatial cov.: Matérn-5/2
• Temporal cov.: N/A
• Number of parameters: 3 (scale $\lambda$, spatial lengthscale $l_S$, noise level $\sigma^2_0$)

R-GP-UCB and TV-GP-UCB.

• Spatial cov.: Matérn-5/2
• Temporal cov.: fixed kernel with decay parameter $\epsilon$
• Number of parameters: 4 (scale $\lambda$, spatial lengthscale $l_S$, decay $\epsilon$, noise level $\sigma^2_0$)

ABO and W-DBO.

• Spatial cov.: Matérn-5/2
• Temporal cov.: Matérn-3/2
• Number of parameters: 4 (scale $\lambda$, spatial lengthscale $l_S$, temporal lengthscale $l_T$, noise level $\sigma^2_0$)

Although we acknowledge the usefulness of anisotropic kernels in practice, we would like to address (i) the issue of “conventionality” of ARD kernels in benchmarking, and (ii) the performance of W-DBO with an ARD kernel.

(i) Among the DBO papers (i.e., [1, 2, 3]), the vast majority of the benchmarking was done with a non-ARD kernel. More specifically, [1] explicitly uses a non-ARD kernel, [2] uses an ARD kernel on 1 experiment out of 7 (cf. Tables 4-10 in [2]), and [3] makes no mention of an ARD kernel. This makes us consider that using a non-ARD kernel for benchmarking is fairly standard, at least in the DBO literature. We do not understand therefore why the comprehensive benchmarking would be unconventional and/or unfair towards some solutions. Upon acceptance, we propose to explicitly list the kernel hyperparameters for each DBO solution in Appendix G.1 to prevent any confusion about our benchmarking.

(ii) Let us discuss how our framework can be applied to anisotropic kernels. Most of our analysis remains unchanged, but we need additional convolution formulas because the ones provided in Tables 3 and 4 only hold under Assumption 3.2. We now illustrate this point by providing additional results with the anisotropic SE kernel. Consider a $d \times d$ diagonal matrix $\Sigma = \text{diag}\left(l_1, \cdots, l_d\right)$ that gathers the $d$ lengthscales in its diagonal. It can be shown that the anisotropic convolution formula is $(k_S * k_S)(\mathbf x) = \pi^{d / 2} \det\left(\Sigma\right) e^{-\mathbf x^\top \Sigma^{-2} \mathbf x / 4}$. Observe that the formula reduces to the isotropic formula described in Table 3 when $l_1 = \cdots = l_d = l_S$. Additional experiments with the ARD SE kernel are listed on the PDF, which had to be uploaded in the global rebuttal (where they are discussed too).

I fail to see that the removed observations are stale. Provide an illustrative example of which observations are removed and a metric for staleness.

The concept of staleness is used in the title, as well as in Sections 1 and 2 to introduce our work because it is a term commonly used in the literature, but we replace it with the broader concept of “relevancy” from Section 3 onwards. Relevancy can be temporal (an observation that is too distant in time to be relevant for GP inference, a.k.a staleness) but also spatial (an observation that is too close from another to bring substantial information for GP inference). In other words, staleness coincides with temporal relevancy, whereas W-DBO accounts for both temporal and spatial relevancy. We provide a metric for the relevancy of an observation $\mathbf x_i$, namely the Wasserstein distance between the posterior GP conditioned on the entire dataset $\mathcal{D}$ and the posterior GP conditioned on $\tilde{\mathcal{D}} = \mathcal{D} \setminus \\{\mathbf x_i\\}$, defined on the cartesian product of the spatial domain $\mathcal{S}$ and the future $[t_0, +\infty]$, with $t_0$ the present time.

We use this metric because it is intuitive and it captures properly the concept of observation relevancy (e.g., it is 0 when removing an observation does not change the GP posterior in any way, and it can be arbitrarily large otherwise, depending on how the removal of an observation affects the posterior). We remove observations according to a normalized version of this metric, to ensure that the removed observations are indeed “stale” or, more broadly speaking, “irrelevant”.

We also provide an example illustrating which observations are being removed. Animated visualizations are provided in the supplementary material, and are discussed in Appendix G.4.

Please add standard errors to the tables.

Due to lack of space, we did not report the standard errors directly in Table 2. However, they are provided graphically whenever applicable, namely in Figures 1-3 and 6-17.

To further address this weakness while respecting the NeurIPS template, we propose to replicate Table 2 in a dedicated appendix of the camera-ready version, where we will also provide the standard errors.

There is a lot of important content that has been moved to the SM.

Upon acceptance, we will use the additional page allowed to move some important content from the SM to the main paper, and by possibly also reducing the Background section to make room for this material.

Typos.

Thank you for pointing out these typos. Upon acceptance, we will fix them in the camera-ready version.

References

[1] I. Bogunovic, J. Scarlett, and V. Cevher. Time-varying gaussian process bandit optimization. In AISTATS, pages 314–323. PMLR, 2016.

[2] P. Brunzema, A. von Rohr, F. Solowjow, and S. Trimpe. Event-triggered time-varying bayesian optimization. arXiv preprint arXiv:2208.10790, 2022.

[3] Nyikosa, F. M., Osborne, M. A., & Roberts, S. J. (2018). Bayesian optimization for dynamic problems. arXiv preprint arXiv:1803.03432.

Dear Reviewer mGHg,

Thank you for the detailed review. We are discussing below the weaknesses and questions you have raised. Also, please make sure to read the global response as we discuss some of your questions there.

The scalability of W-DBO (e.g., in high-dimensional spaces and/or with large datasets) is not discussed.

The Wasserstein distance is applied in the output space, which is one-dimensional regardless of the dimensionality of the input space, i.e., the objective function domain.

Our framework, which measures the observations relevancy and removes the irrelevant observations, can be seen as a simple post-processing stage running at the end of each iteration. As a consequence, it can be used in conjunction with any BO algorithm. The W-DBO algorithm presented in this paper exploits vanilla GP-UCB, and as such, will struggle in high-dimensional input spaces, precisely because GP-UCB struggles in high-dimensional input spaces. However, our framework could be paired with any state-of-the-art high-dimensional BO algorithm (e.g., [1]) and show good performance when optimizing high-dimensional dynamic black-boxes. This is an interesting future work, thank you for suggesting it.

Regarding very large dataset sizes, W-DBO suffers from the same limitations as any BO algorithm. This is because it also manipulates inverses of Gram matrices, which scale with the dataset size. That is precisely why we argue that removing irrelevant observations gives W-DBO a decisive advantage upon other DBO solutions. Nevertheless, upon acceptance, we will discuss this limitation explicitly in the Appendix H of the camera-ready version.

Is there ever a downside with the ‘greedy’ of removal of points?

Our framework could easily be extended to the power set $2^\mathcal{D}$ of the dataset $\mathcal{D}$, in order to measure the relevancy of a subset of observations, instead of only quantifying the relevancy of a single observation.

The greedy approach causes W-DBO to overestimate the impact of the observation removals on the GP posterior. To rapidly get an intuition explaining this, let us describe a simple example. Consider a dataset that contains an irrelevant pair of observations $\mathcal{P} = \\{\mathbf x_i, \mathbf x_j\\}$, in the sense that $W_2\left(\mathcal{GP}\_\mathcal{D}, \mathcal{GP}\_{\mathcal{D} \setminus \mathcal{P}}\right) = 0$. Furthermore, let us assume that $W_2\left(\mathcal{GP}\_\mathcal{D}, \mathcal{GP}\_{\mathcal{D} \setminus \\{\mathbf x_i\\}}\right) = W_2\left(\mathcal{GP}\_{\mathcal{D} \setminus \\{\mathbf x_i\\}}, \mathcal{GP}\_{\mathcal{D} \setminus \mathcal{P}}\right) = \epsilon > 0$. If W-DBO were able to directly capture the irrelevancy of the couple $\mathcal{P}$, it would have removed it without consuming any of its removal budget. However, the greedy removal procedure as described in Algorithm 1 causes W-DBO to remove first $\mathbf x_i$ and next $\mathbf x_j$. Consequently, it will consume $2\epsilon$ from its removal budget and, in that sense, it will overestimate the impact of removing $\mathbf x_i$ and $\mathbf x_j$.

Although working with the power set $2^\mathcal{D}$ of the dataset $\mathcal{D}$ is clearly more advantageous to avoid such budget depletion caused by greedy removals, the combinatorial explosion of $|2^\mathcal{D}|$ makes this strategy prohibitive in practice, even for moderately-sized datasets. That is why it is not advertised in the paper. Upon acceptance, we will include this remark in Section 4 of the camera-ready version. Thank you for pointing it out.

Can the algorithm remove observations that become relevant again in the future?

For usual stationary, decreasing kernels (e.g., Squared-Exponential or Matérn) and because of Assumption 3.2, the covariance between a function value at a time $t$, i.e., $f(\mathbf x, t)$, and a function value at a future time $t’$, i.e., $f(\mathbf x’, t’)$ with $t < t’$, can only decrease as $t’$ gets further and further away from $t$. Consequently, the relevancy of the observing $f(\mathbf x, t)$ will only decrease as time goes by.

An interesting case that is not discussed in the paper, is when the time kernel $k_T$ is a periodic kernel, e.g., $k_T(t, t’) = \exp\left(-\frac{2 \sin^2\left(\pi |t - t’| / p\right)}{l^2}\right)$. The objective function is thus periodic along its time dimension. In that case, the concept of stale observation vanishes completely since the observation of $f(\mathbf x, t)$ will always be useful to predict $f(\mathbf x, t’)$, even when $t’ \gg t$. The Wasserstein distance between the two posterior GPs with this time-periodic kernel can be shown to diverge to $+\infty$, and so does our approximation, as it indeed should.

References

[1] Bardou, A., Thiran, P., & Begin, T. Relaxing the Additivity Constraints in Decentralized No-Regret High-Dimensional Bayesian Optimization. In The Twelfth International Conference on Learning Representations. 2024.

Thanks for the response. In particular, I see I have misunderstood how the experimental case studies were defined (see authors' global response), and so this stated weakness is largely alleviated. I have raised my score correspondingly, and look forward to the authors' stated clarifications in the camera-ready (or otherwise future) version.

Dear Reviewer JgwK,

Thank you for the detailed review. We are discussing below the weaknesses and questions you have raised. Also, please make sure to read the global response as we discuss some of your questions there.

Direct comparison against other simpler (or even ad-hoc) methods for relevancy quantification (e.g., constant rate of decline over time).

TV-GP-UCB assumes a constant decreasing rate of the covariance function over time. Neglecting spatial relevancy, this precisely translates into a constant decreasing rate of the relevancy of an observation over time. Our approach (W-DBO) differs from TV-GP-UCB in three ways:

(i) W-DBO can use an arbitrary time kernel instead of a fixed kernel for TV-GP-UCB (see [1]),

(ii) W-DBO has a more sophisticated quantification of relevancy (i.e., the Wasserstein distance) that involves the relevancy both in the time dimension (staleness) and in the spatial domain,

(iii) W-DBO is able to remove observations when they are deemed irrelevant.

Together, (i), (ii) and (iii) explain the difference in the performance of TV-GP-UCB and the performance of W-DBO.

One could use the very same core idea of our framework (a distance function on stochastic processes) and come up with other definitions of relevancy. As an example, one could define the relevancy of an observation using the KL-divergence on the two GP posteriors. However, this would require a very different analysis to find an approximation of this distance, which would lead more to a new paper than to an ablation study.

The authors state that computational biology is a field that makes “heavy use of DBO”.

In Section 1, we cite computational biology as an application of BO, not of DBO. However, it is true that in our concluding remarks of Section 6, we cite computational biology as a field that could apply DBO. This is a typo that will be removed from the camera-ready version upon acceptance. Thank you for pointing it out.

References

[1] Ilija Bogunovic, Jonathan Scarlett, and Volkan Cevher. Time-varying gaussian process bandit optimization. In Artificial Intelligence and Statistics, pages 314–323. PMLR, 2016.