- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
As data is sampled, the response time of a BO step is expected to increase. Most methods assume this increase to be nonexistent (constant), but this may not be the case in practice, with the response time increasing quadratically or worse. The authors derive a regret bound for GP-UCB with a FIFO policy keeping the n most recent observations, accounting for increase in response time. They then derive a recommendation on the dataset size, based on this bound. They also provide theoretical support for Bardou et al.'s forgetting heuristic and propose an algorithm that combines that with their recommended dataset size. In near constant response time, quasi static and general long-horizon problems, they demonstrate better or comparable regret to other TVBO algorithms (including Bardou et al.'s), and report response times in the same range as W-DBO, FIFO and TV-GPUCB.
Main contributions: A regret bound for GP-UCB considering non-constant response times, a dataset size recommendation derived from it, and the method BOLT, which has the lowest average regret in comparison to the baselines.
Critical strengths
- S1: First regret analysis linking dataset size, non-constant response time and temporal kernel choice.
- S2: The proposed algorithm has the best average normalized regret on evaluations on the three relevant regimes, and all the methods are evaluated on the same framework, in wall-clock time.
- S3: FIFO and W-DBO each implement one of the recommendations, as proposed in this paper, naturally serving as ablations.
Critical weaknesses
- W1: Limited algorithmic novelty: BOLT corresponds to W-DBO with the user-specified removal budget replaced by n* from recommendation 1.
- W2: The related work is sparse. Especially, the claim that few works study TVBO is uncited, whereas several works that do study it are mentioned later in the paper. In Section 2.3, the first mention of the state of the art methods in TVBO does not link them to their papers (they are first linked in the numerical results section, and W-GPUCB/SW-GPUCB are never explicitly linked). Additionally, since the paper is discussing the trade-off between dataset size and inference time, works on approximate or sparse GP inference should also be discussed.
- W3: Lemma A.3 (and hence Theorem 3.6) relies on FIFO removal, which the proof uses but the statements don't mention, instead referring to the general TVBO case. Furthermore, the bound built on ||u_n||^2, used to derive recommendation 1, depends on the fixed time gaps from FIFO, and thus does not cover BOLT, which is the main proposed algorithm.
- W4: Recommendation 1 is not contrasted against fixed dataset sizes. The paper does not compare against SW-GPUCB and FIFO (as implemented) follows recommendation 1. Comparison against SW-GPUCB or FIFO with fixed n would allow for observing the effect of choosing the dataset size with the proposed recommendation.
- W5: ET-GPUCB appears to never reset (its dataset grows monotonically and its regret strongly resembles GPUCB). Thus, the comparison with the event-triggered case is uninformative. Brunzema et al. (2025) propose learning hyperparameters only after each reset to avoid the inflation of noise variance that suppresses triggers. The paper acknowledges hyperparameter difficulties but does not report the settings used.
- W6: The code is only promised upon acceptance, and key baseline settings are missing (e.g. the aforementioned hyperparameters of ET-GPUCB, R-GPUCB's reset period, etc)
Questions for authors
- Q1: As I understand it, Bogunovic's regret bounds condition on all data that the query choices depend on (the full history or the data since the last reset). Could you please clarify how this extends to the FIFO window, where retained points were selected using discarded data?
- Q2: Can Theorem 3.6 be extended to BOLT's/W-DBO's Wasserstein removal? Otherwise, please restrict Lemma A.3 and Theorem 3.6 to FIFO and state that BOLT carries no regret guarantee.
- Q3: How does the approach relate to reducing response time with sparse or approximate GP inference (e.g., Calandriello et al., 2019)?
- Q4: What dominates BOLT's runtime (computation of n*, Wasserstein removal, hyperparameter inference)?
- Q5: How do SW-GPUCB or FIFO with fixed n perform against FIFO-n* and BOLT?
- Q6: What settings were used in the baseline implementations?
3 comments
I consider [W1, W3, W4, W6, Q2, Q3, Q5, Q6] as fully addressed. Especially, thank you for adding the results in App. E and the hyperparameters in App. D.
As for [W2, W5, Q1, Q4], I see them partially addressed, with the remaining questions I will mention below.
Q1: Thank you for making the Assumption explicit. Theorem 3.6 clearly holds under the assumption that 'f|D_i is the GP posterior computed from the dataset D_i'. I wonder, however, if FIFO with GP-UCB satisfies this assumption. This is, considering that with a UCB acquisition function, the sampling will have over time gotten further away from areas with low values, so that these areas are forgotten. The window posterior then returns to the prior, and then the fact that there is no data there implicitly carries information about the values there being low. Then, the distribution of f|D_i and the posterior from D_i might be different, making the confidence bound in eq. 11 hold with less confidence than stated. I would appreciate it if the authors could either explain why this does not apply to GP-UCB with a FIFO policy, or acknowledge it as a limitation in the text.
W2: The statement 'Yet only a handful of works study Time-Varying Bayesian Optimization (TVBO)' is still uncited. Since the statement refers to the works in Table 1, it should refer to them. It seems like a more suitable space to introduce them than the R(n) analysis sentence of the introduction.
W5: I understand the choice of a shared protocol with online hyperparameter inference. However, Brunzema et al. (2025) caution against the noise (and thus threshold) inflation obtained by re-estimating all hyperparameters at every iteration. They suggest learning the hyperparameters during the first steps after each reset and freezing them until the next trigger. This seems compatible with the shared protocol, since it still implies online hyperparameter inference, only in less steps. I would appreciate it if the authors could either run ET-GPUCB this way, or state explicitly in Sec. 5.3 that ET-GPUCB does not trigger under this protocol and effectively reduces to GP-UCB.
Q4: The plots mix the effects of the dataset size and the cost of each of the components. Also, the relation between the W-DBO/FIFO/BOLT algorithms varies, so it is hard to make a general statement purely through them. A timing table for each of the stages of BOLT would settle this more easily.
As main points have been addressed and the paper improved overall, I will adjust my score (2 to 3).
We thank the reviewer for their follow-up and for raising their score.
Q1. The selection effect described by the reviewer can indeed occur under FIFO, which is why the revision states the assumption explicitly. Its strength is governed by the information that discarded observations still carry about . They are at least old, so the information they carry about degrades with : for instance, the fact that a region had low values when it was forgotten says less and less about its current values, because the function changes over time. This can be verified empirically, and we did so on the 240 runs of App. E, where is known. At each queried point , where the mechanism described by the reviewer would bias the window posterior, we computed . With the full history (), the posterior is exact and , which provides a control. These results range over , with about 2,000 points per cell (these can be aggregated because in all runs):
| (control) | ||||||
|---|---|---|---|---|---|---|
| Mean of | −0.32 to −0.24 | −0.15 to −0.13 | −0.04 (all ) | −0.01 to 0.02 | −0.02 to 0.03 | 0.02 to 0.03 |
| (nominal 2.5%) | 3.6–4.0% | 3.5–3.6% | 2.5–3.0% | 2.6–3.4% | 2.1–2.6% | 2.0–2.9% |
The bias predicted by the reviewer is visible for windows much smaller than , whose discarded observations are recent: the window posterior is then optimistic at the queried points. At and beyond, the bias is at most 0.04 standard deviations, and the tail probabilities are close to those of the exact posterior. Rec. 1 thus selects windows in which the assumption is empirically accurate. We added this check to App. E (paragraph "Calibration of the window posterior", Table 6), and the mechanism pointed out by the reviewer to the discussion of the assumption in App. A (paragraph "Conditioning under a FIFO policy"), both in purple.
W2. As suggested, the works of Table 1 are now cited in the sentence "Yet only a handful of works study TVBO" (Sec. 1, first paragraph), instead of the sentence on .
W5. Sec. 5.3 now states explicitly that, under the shared protocol, ET-GPUCB does not trigger and effectively reduces to GPUCB. We will not be able to run the variant proposed by Brunzema et al. (2025) before the end of the discussion period. However, for the sake of completeness, we will run this variant of ET-GPUCB and report the results in the camera-ready version.
Q4. We timed each stage of BOLT on a single CPU thread (, Matérn kernels), as a function of the dataset size (in ms):
| Stage \ | 12 | 25 | 50 | 100 | 200 |
|---|---|---|---|---|---|
| Hyperparameter inference | 211 | 220 | 235 | 289 | 604 |
| Acquisition optimization | 223 | 122 | 132 | 176 | 363 |
| Search for | 0.8 | 0.8 | 0.8 | 0.9 | 0.9 |
| Wasserstein criterion (all observations) | 0.3 | 1.6 | 15 | 157 | 1,942 |
Each iteration runs hyperparameter inference (followed by the fit of and the search for ) and acquisition optimization. When , it also evaluates the Wasserstein criterion, followed by a new inference. Up to , inference and acquisition optimization dominate, and the search for is negligible. In adversarial settings (objective very smooth with large and large , see, e.g., the Powell benchmark), the criterion may dominate (see our reply to Reviewer PG2s). However, even on the Powell synthetic benchmark (where removal occurs at a median dataset size of 267 and on 1.7% of the iterations), BOLT still has the lowest regret. On all the other settings, removal costs at most as much as hyperparameter inference and acquisition optimization, often less. Since BOLT's measured includes the removal stage, Rec. 1 accounts for this cost. This table and its discussion are now in the new App. F (Table 7), referenced from Secs. 4 and 5.2. They are in green, as they also answer Reviewer PG2s.
We remain available to discuss any further concern and we thank the reviewer for the interesting discussion conducted so far.
We thank the reviewer for their thorough review. References are to the revised PDF (changes in purple).
W1 (novelty). The algorithmic change is deliberately minimal. The contribution is the analysis: it replaces the dataset size W-DBO leaves to the user with a principled recommendation (Thm 3.6, Rec. 1) and justifies its removal policy (Thm 3.8). This reduces the aggregate normalized regret from 0.21 to 0.04 (Table 4).
W2, Q3 (related work). The claim in the introduction refers to the works of Table 1, which were only cited later in the paper. The introduction now cites them where the claim is made, and Table 1's caption links each method to its paper.
Approximate inference (e.g., Calandriello et al., 2019) does not remove the need to choose n: with online hyperparameters, sparse inference still has a diverging R(n), and constant-cost schemes forget within a fixed budget. See Sec. 2.3 ("A note on approximate inference") and our answer to Reviewer PG2s.
W3, Q2 (scope of Thm 3.6). The FIFO setting is stated in the paragraph introducing Thm 3.6, and recalled in Secs. 2.3 and 3.3. It is now also in the statements of Thm 3.6 and Lemma A.3. The paper does not claim a regret bound for BOLT, which would have limited interest: any algorithm has ri≤maxSf(⋅,ti)−minSf(⋅,ti), so E[RT]≤2TE[maxSf(⋅,0)] holds trivially, and all regret bounds are linear in this setting (Bogunovic et al., 2016). FIFO is the analytically tractable reference from which BOLT takes its dataset size (Thm 3.6), whereas Thm 3.8 justifies its removal policy, as stated at the start of Sec. 4.
Q1 (conditioning under FIFO). Discarding observations is not the issue. Let Hi be the full history. For given inputs, f−μDi=(f−μHi)+(μHi−μDi), where the two terms are independent centered Gaussians with variances σHi2 and σDi2−σHi2, respectively. Hence f−μDi∼N(0,σDi2): the window posterior is less informative than the full one, but remains calibrated, and Lemma A.1 applies.
The reviewer points out a selection effect: the inputs of Di were chosen using discarded observations, so they could carry information about f beyond Di. Lemma A.1 assumes they do not, i.e., that f∣Di is the GP posterior computed from Di, as now stated in Thm 3.6 and discussed in App. A. Lemma A.3, which provides the dependence on n and R(n), is unaffected.
W4, Q5 (fixed sizes). Table 4 already isolates the dataset-size rule (Table 1): BOLT and W-DBO share the removal policy and differ only in how the dataset size is chosen (Rec. 1 vs. a user-specified removal budget), with 0.04 vs. 0.21 aggregate regret. Fixed maximal dataset sizes need a fixed n∗ as reference, which the benchmarks of Sec. 5.3 cannot provide, since R(n) and the kernel hyperparameters are inferred online. We therefore added a controlled experiment where n∗ is fixed (Sec. 5.1, App. E), comparing FIFO with n∈n∗/4,…,4n∗,T, i.e., SW-GPUCB's sliding window applied to our model. BOLT is not included, since its Wasserstein removal is outside the scope of Thm 3.6. For every q≥1, n∗ yields the lowest average regret among all the values of n (Tables 2 and 5).
W5, W6, Q6 (ET-GPUCB, settings). All methods share one protocol: hyperparameters, unknown in practice, are inferred online at every iteration (Sec. 5.2). Under this protocol, ET-GPUCB does not trigger, a difficulty that Brunzema et al. themselves discuss. The reset strategy is nevertheless represented by R-GPUCB, which does reset (Figs. 4–13). BOLT beats R-GPUCB on 9/10 benchmarks and is statistically tied on the tenth one (Temperature).
The baseline-specific parameters derive from hyperparameters inferred online, and thus vary during a run. R-GPUCB resets every ⌈12ϵ−1/4⌉ observations (Bogunovic et al., 2016), with the forgetting rate ϵ inferred as in TV-GPUCB. ET-GPUCB's threshold uses the inferred noise and posterior variances, with δB=0.1, and ABO selects query times in [t,t+0.1lT]. All methods use 15 initial uniform queries and βn=2dlog(2n), with n the dataset size, and W-DBO uses α=1/4 (Bardou et al., 2024). These settings are now listed in App. D.
Q4 (runtime). Figs. 4–13 report the response times of FIFO (n∗ only), W-DBO (removal only) and BOLT (both), isolating the cost of each component. All three stay in the same range as TV-GPUCB, which performs neither. This is consistent with Sec. 5.2: hyperparameter inference and acquisition optimization are the time-consuming stages of the process.