acceptodds
Under review as a conference paper at ICLR 2027

Time-Varying Bayesian Optimization Without a Metronome

Abstract

Time-Varying Bayesian Optimization (TVBO) is the go-to framework for optimizing time-varying, expensive, noisy black-box functions. However, most asymptotic guarantees for TVBO algorithms assume observations are acquired at a constant frequency. Since streaming GP inference scales quadratically with dataset size, this assumption is unrealistic in the long run. We relax it and derive the first upper regret bound that explicitly accounts for changes in observation sampling frequency. This analysis yields practical recommendations for dataset sizes and stale-data policies. Experiments on synthetic and real-world problems show that an algorithm (BOLT) following these recommendations outperforms state-of-the-art TVBO methods.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Time-Varying Optimization, Bayesian Optimization, Regret Bound

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_LVzjOpenReview ↗
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

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 nn: with online hyperparameters, sparse inference still has a diverging R(n)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≤max⁡Sf(⋅,ti)−min⁡Sf(⋅,ti)r_i \le \max_{\mathcal S} f(\cdot,t_i) - \min_{\mathcal S} f(\cdot,t_i), so E[RT]≤2TE[max⁡Sf(⋅,0)]\mathbb E[R_T] \le 2T\mathbb E[\max_{\mathcal S} f(\cdot,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\mathcal H_i be the full history. For given inputs, f−μDi=(f−μHi)+(μHi−μDi),f - \mu_{\mathcal D_i} = (f - \mu_{\mathcal H_i}) + (\mu_{\mathcal H_i} - \mu_{\mathcal D_i}), where the two terms are independent centered Gaussians with variances σHi2\sigma^2_{\mathcal H_i} and σDi2−σHi2\sigma^2_{\mathcal D_i} - \sigma^2_{\mathcal H_i}, respectively. Hence f−μDi∼N(0,σDi2)f - \mu_{\mathcal D_i} \sim \mathcal N(0, \sigma^2_{\mathcal D_i}): 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\mathcal D_i were chosen using discarded observations, so they could carry information about ff beyond Di\mathcal D_i. Lemma A.1 assumes they do not, i.e., that f∣Dif \mid \mathcal D_i is the GP posterior computed from Di\mathcal D_i, as now stated in Thm 3.6 and discussed in App. A. Lemma A.3, which provides the dependence on nn and R(n)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∗n^* as reference, which the benchmarks of Sec. 5.3 cannot provide, since R(n)R(n) and the kernel hyperparameters are inferred online. We therefore added a controlled experiment where n∗n^* is fixed (Sec. 5.1, App. E), comparing FIFO with n∈n∗/4,…,4n∗,Tn \in \\{n^*/4, \dots, 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≥1q \ge 1, n∗n^* yields the lowest average regret among all the values of nn (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⌉\lceil 12\epsilon^{-1/4}\rceil observations (Bogunovic et al., 2016), with the forgetting rate ϵ\epsilon inferred as in TV-GPUCB. ET-GPUCB's threshold uses the inferred noise and posterior variances, with δB=0.1\delta_B = 0.1, and ABO selects query times in [t,t+0.1lT][t, t + 0.1 l_T]. All methods use 15 initial uniform queries and βn=d2log⁡(2n)\beta_n = \frac{d}{2}\log(2n), with nn the dataset size, and W-DBO uses α=1/4\alpha = 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∗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.

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 f(⋅,ti)f(\cdot, t_i). They are at least (n+1)R(n)(n+1)R(n) old, so the information they carry about f(⋅,ti)f(\cdot, t_i) degrades with kTk_T: 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 ff is known. At each queried point xix_i, where the mechanism described by the reviewer would bias the window posterior, we computed zi=(f(xi,ti)−μDi(xi,ti))/σDi(xi,ti)z_i = (f(x_i,t_i) - \mu_{\mathcal D_i}(x_i,t_i))/\sigma_{\mathcal D_i}(x_i,t_i). With the full history (n=Tn = T), the posterior is exact and zi∼N(0,1)z_i \sim \mathcal N(0,1), which provides a control. These results range over q∈1,2,3q \in \\{1,2,3\\}, with about 2,000 points per cell (these can be aggregated because n∗=64n^* = 64 in all runs):

nnn∗/4n^*/4n∗/2n^*/2n∗n^*2n∗2n^*4n∗4n^*TT (control)
Mean of ziz_i−0.32 to −0.24−0.15 to −0.13−0.04 (all qq)−0.01 to 0.02−0.02 to 0.030.02 to 0.03
P(zi<−1.96)P(z_i < -1.96) (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 n∗n^*, whose discarded observations are recent: the window posterior is then optimistic at the queried points. At n∗n^* 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 R(n)R(n).

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 (d=2d = 2, Matérn kernels), as a function of the dataset size nn (in ms):

Stage \ nn122550100200
Hyperparameter inference211220235289604
Acquisition optimization223122132176363
Search for n∗n^*0.80.80.80.90.9
Wasserstein criterion (all nn observations)0.31.6151571,942

Each iteration runs hyperparameter inference (followed by the fit of RR and the search for n∗n^*) and acquisition optimization. When ∣D∣>n∗|\mathcal D| > n^*, it also evaluates the Wasserstein criterion, followed by a new inference. Up to n≈100n \approx 100, inference and acquisition optimization dominate, and the search for n∗n^* is negligible. In adversarial settings (objective very smooth with large lTl_T and large nn, 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 R(n)R(n) 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.

Reviewer_PG2sOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies Time-Varying Bayesian Optimization (TVBO) under the constraint that the time between consecutive queries, R(n)R(n), grows with the dataset size nn rather than the constant-response-time assumption underlying existing TVBO regret guarantees. Because the objective drifts while the algorithm computes, a larger dataset slows down GP inference and leaves its observations staler by the time the next query is issued, so retaining data and sampling frequently are in tension. The paper formalizes this trade-off with a regret bound that depends on both the temporal correlation of the objective and the response time, yielding a rule for how many observations to keep. It then uses the Wasserstein-based removal to decide which observations to discard. The resulting algorithm, BOLT, outperforms existing TVBO methods on synthetic and real-world benchmarks run in wall-clock time.

Critical strengths
  • First TVBO regret bound in which the response time R(n)R(n) appears explicitly, rather than being assumed constant.
  • Thorough numerical evaluation: wall-clock comparisons against all relevant baselines on both synthetic and real-world benchmarks.
Critical weaknesses
  • Scalable GP inference is excluded by assumption. Definition 3.5(iii) rules out sparse and low-rank (Nystrom) GPs, which implies bounded R(n)R(n). The paper's own rule recommends retaining every observation. Whether discarding data beats approximating the posterior is neither discussed nor tested, and no scalable-GP baseline is included. A discussion of scalable GPs should be added.
  • The removal rule is less tractable than presented. Recommendation 2 requires the Wasserstein distance for each of the nn candidate removals at every iteration, which has no closed form and must be integrated numerically. The paper does not say how this is computed, or how its cost enters R(n)R(n).
  • Results hold only in a well-specified Bayesian setting. Assumption 3.1 takes ff to be a GP sample path with known kernel and hyperparameters. The bound offers no guarantee under misspecification, and the RKHS setting used elsewhere in TVBO (Zhou & Shroff, 2021; Deng et al., 2022) is neither considered nor compared against.
  • Section 2.2 does not isolate the TVBO-specific difficulty. The regimes are framed around computational overhead, which is equally present in static BO. The actual distinguishing mechanism, that the inter-query lag R(n)R(n) determines how stale every stored observation is, only becomes clear at Theorem 3.6, so the problem and the contribution over W-DBO are hard to appreciate up front.

Based on these weaknesses, I do not think the manuscript can be accepted in its current form. The authors should address these points and consider resubmitting to a future venue.

Questions for authors
  1. The response-time definition requires the cost per iteration to grow without bound as the dataset grows. Sparse, low-rank GP approximations keep this cost bounded, and for a constant response time, the paper's own analysis (Section 3.2, recommendation 1) proposes to retain every observation. The framework therefore seems to imply that, if one can afford an approximate GP with constant cost, data removal is unnecessary. Why should a practitioner prefer an exact GP with observation removal over an approximate GP that keeps all observations? Can the authors compare BOLT against such a baseline, in both regret and wall-clock time? Further discussion should be added.

  2. How is the integrated 2-Wasserstein distance in Recommendation 2 computed online? Specifically: what numerical scheme is used, what does evaluating it for all nn candidate removals cost per iteration, and is that cost included in the measured R(n)R(n) that BOLT fits?

1 comment

We thank the reviewer for their detailed review. All references point to the revised PDF, where the changes made in response to this review are in green.

Scalable GPs (W1, Q1). Condition (iii) of Def. 3.5 in the submitted version, now moved to App. B, does not exclude sparse or low-rank GPs and is used only in the analysis of App. B (see our answer to Reviewer 2rJg's Q4). With mm inducing points, sparse inference (SGPR, Nyström) costs O(nm2+m3)O(nm^2 + m^3) per conditioning and per marginal-likelihood evaluation, and hyperparameters are inferred online. As a result, R(n)=Θ(n)R(n) = \Theta(n), App. B gives a finite n∗n^*, and our analysis does not recommend keeping every observation with a sparse GP.

A bounded RR requires methods that stop revisiting past data, e.g., streaming sparse GPs (Bui et al., 2017) or minibatch SVGP with a fixed step budget. These compress or subsample the past within a fixed budget, which is a forgetting mechanism whose budget must still be chosen. This is a non-trivial problem, and Rec. 1 addresses exactly this choice. Adaptive sketching (BKB; Calandriello et al., 2019) keeps O~(deff)\tilde O(d_{\rm eff}) inducing points. Under persistent temporal variation, deffd_{\rm eff} grows with time, and so does its per-iteration cost.

In practice, the choice is not "exact GP with removal or approximate GP with all data". Approximate inference changes R(n)R(n), and Rec. 1 then sets nn for that R(n)R(n). BOLT measures RR online, so it can be run unchanged on top of any inference engine. We agree with the reviewer that this is an important thing to highlight, so we added this discussion to Sec. 2.3 (paragraph "A note on approximate inference").

Computing W2W_2 (W2, Q2). Rec. 2 is computed as in W-DBO (Bardou et al., 2024, Sec. 4.1), as stated in Sec. 3.3, with no numerical integration but an approximation that can be run online. Leave-one-out posteriors are obtained from Δ−1\Delta^{-1} by block inversion, without refactorization. As Thm 3.8 also holds on S×[t0,∞)\mathcal S\times[t_0,\infty), minimizing this bound minimizes an upper bound on the acquisition perturbation.

The cost is visible in Figs. 4–13, which report the average response time R(n)R(n) of W-DBO (removal only), FIFO (n∗n^* only) and BOLT (both). All three stay in the same range as TV-GPUCB, which does neither. For the sake of completeness, these points are now in Sec. 4 (paragraph "Computability of Recommendation 2").

Well-specified setting (W3). To the best of our knowledge, all TVBO regret analyses that allow persistent temporal variation are Bayesian (Bogunovic et al., 2016; Brunzema et al., 2025). The RKHS analyses (Zhou & Shroff, 2021; Deng et al., 2022) are sublinear only under a sublinear variation budget, which excludes this regime (Sec. 2.3). This is a structural difference between the two frameworks: GP sample paths can vary persistently, whereas fixed-norm RKHS functions cannot. For instance, for a Matérn or an RBF kTk_T, every ff in the RKHS of kSkTk_Sk_T is such that t↦f(x,t)t \mapsto f(x,t) is square-integrable for every xx. We've completed Sec. 2.3, to better explain the setting.

Empirically, every reported result is misspecified: the 8 synthetic objectives are deterministic test functions, the 2 real-world ones are data-driven, and all hyperparameters are inferred online.

Sec. 2.2 (W4). Sec. 2.2 opens with this sentence: "Because R(n)R(n) grows with nn, every TVBO algorithm must implicitly address a trade-off between the information it retains and the frequency at which it can sample ff". Its regimes are defined by comparing R(n)R(n) with lTl_T, which has no static counterpart. In static BO, a larger R(n)R(n) only delays equally informative observations. In TVBO, it makes every stored observation staler and lets the optimum move between queries. Sec. 2.2 now states this contrast explicitly.

Summary. All four weaknesses are addressed in the revised PDF without changing the paper's claims: scalable GPs (W1) and the Bayesian setting (W3) are now discussed in Sec. 2.3, the computation of W2W_2 (W2) is detailed in Sec. 4, and the contrast with static BO (W4) is made explicit in Sec. 2.2. We hope these revisions resolve the reviewer's concerns. We are happy to clarify any remaining point during the discussion.

Reviewer_2rJgOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper argues time-varying Bayesian optimisation analyses assume a constant sampling interval, while real algorithms spend a dataset-size-dependent time on each iteration. It analyses GP-UCB with a hard cap n and FIFO replacement, and proves a high-probability cumulative regret bound in which the temporal kernel is evaluated at lags that are multiples of the response time R(n). The bound depends on the cap only through a multiplicative factor, maximising that factor gives a recommended dataset size n*. The paper then propose BOLT, which is W-DBO with its user-set removal budget replaced by n*, estimated online from a cubic fit to measured response times. Experiments cover ten benchmarks and replications, a fixed wall clock horizon and a shared BoTorch stack.

Critical strengths

The problem is real and the paper states it precisely. Response time is the quantity that makes long-horizon TVBO different from the iid bandit setting, and the FIFO construction is a clean way to expose the trade-off, keeping more observations improves the posterior, but the time spent on each iteration lets the objective drift further. Rec1 follows from the bound, and the app. checks when the maximiser exists.

The empirical study is competent and reproducible. Ten benchmarks, ten replications, a shared BoTorch stack, the same acquisition and the same hyperparameter inference for all arms, and a wall-clock horizon, so runs are compared in time. BOLT's aggregate normalised regret is 0.033, against 0.211 for W-DBO, 0.230 for FIFO and 0.623 for GP-UCB. They report where BOLT loses as well as where it wins.

Critical weaknesses

The abstract and the body describe different results. The abstract says BOLT "outperforms state-of-the-art TVBO methods", while Sec 5.2 says "competitive or superior". The static-case check sets k_T = 1, which violates Assumption 3.3. These are not cosmetic problems, and they should have been caught in a final read-through. The authors may need to review AI's output more carefully.

The theoretical contribution is thinner than the framing. With γ_n in O(n) and the bracket in Theorem 3.6, the bound is O(T) for every admissible cap, so the cap can change only the leading factor. A bound of that form cannot explain the differences in Table 3, and I dont find the paper computes it. The comparison that a "first bound" claim needs is also incomplete. The variation-budget line is mentioned but Besbes, Gur and Zeevi is absent, and no rate is compared. The paper explains why its rates are not in Table 1, so this is a positioning problem; the citation itself is a side issue. The static-case sanity check sets k_T to 1, which makes the envelope infinite and violates Assumption 3.3 . that check is outside the theorem.

The algorithm's headline property is not tested. BOLT's claimed advantage is that n* adapts to the response time, yet all ten benchmarks run on one laptop with one framework, and no experiment varies the growth of R(n). Fig 3 shows the dataset size adapting on Eggholder and Powell which is descriptive, and the response time itself is not varied. Fig1 predicts that n* should shrink as the growth exponent rises; that prediction is not confronted with data.

Questions for authors
  1. Maybe report C2 * square_norm_u for each benchmark and check whether the bound's predicted ordering across caps matches the observed ordering in Table 3.
  2. Can you add a controlled response-time knob, with per-iteration cost scaling as n^q for q in {0, 1, 2, 3}, and report how n* and the margin over W-DBO and FIFO change with q? and also maybe run SW-GPUCB with a small grid of fixed window sizes and W-GPUCB with n = T? These are the controls that separate the adaptive cap from a fixed cap.
  3. How sensitive is BOLT to error in the cubic fit of R(n)? The fit is refitted every iteration, and a non-monotone response-time series would violate Definition 3.5.
  4. Definition 3.5 requires R(n) to diverge, while Table 1 assigns R(n) in Θ(1) to several compared methods. Which regime is the theorem meant to cover, and does the bound still hold when R is bounded?
2 comments

We thank the reviewer for their careful review. References are to the revised PDF (changes in blue).

Abstract vs. Sec. 5.3 (formerly 5.2). The two statements are consistent and summarize Table 4 at two levels: aggregate ("outperforms"), with the lowest normalized regret, 0.04 ± 0.02 vs. 0.21 ± 0.07 for the runner-up; per benchmark ("competitive or superior"), best on 5/10, statistically tied with the best on 4/10, and slightly worse on 1/10. Secs. 1 and 5.3 now state both levels, and so will the camera-ready abstract.

Static case vs. Assumption 3.3. When n=Tn = T, the sum in the right-hand side of (17) in Lemma A.2 is empty, and it therefore becomes RT≤C1TβTγT+π2/6R_T \le \sqrt{C_1T\beta_T\gamma_T} + \pi^2/6. It relies only on Assumptions 3.1, 3.2 and 3.4. GG, and thus Assumption 3.3, is only used in Lemma A.3, which is not needed here. Sec. 3.2 now derives the static case this way.

Linear regret bound; Q1. For every maximal dataset size nn, the bound of Thm 3.6 is linear in TT. This is unavoidable under persistent temporal variation: Bogunovic et al. (2016) prove a linear lower bound in their model, and all known upper bounds are linear. TVBO algorithms therefore differ through their average regret RT/TR_T/T. Thm 3.6 bounds it as RTTβT≤C12σ02(1−C2∥un∥22)+o(1),\frac{R_T}{T\sqrt{\beta_T}} \le \sqrt{\frac{C_1}{2\sigma_0^2}\left(1 - C_2\|u_n\|_2^2\right)} + o(1), where nn only affects ∥un∥22\|u_n\|_2^2, since C1C_1 and C2C_2 do not depend on it. The bound is thus the smallest for n∗n^* (Rec. 1).

Thm 3.6 compares maximal dataset sizes for a single algorithm, GPUCB with a FIFO policy, not the TVBO algorithms of Table 4, which also differ in temporal model, removal policy and inference. The relevant check is whether FIFO's regret is lowest near n∗n^*, since the fact that n∗n^* shrinks as the growth exponent rises is checked on the right plot of Fig. 1. On the benchmarks of Sec. 5.3, n∗n^* is not a fixed reference, because R(n)R(n) and the kernel hyperparameters are inferred online. We therefore added a controlled experiment in the setting of Thm 3.6 (Sec. 5.1, Table 2, App. E): GP-prior objectives with known hyperparameters and a simulated clock with known R(n)=R(0)+cnqR(n) = R(0) + cn^q, q∈{0,1,2,3}q \in \{0,1,2,3\}, so that n∗n^* is fixed before the run (n∗=64n^* = 64 for q≥1q \ge 1, n∗=∞n^* = \infty for q=0q = 0). We compare FIFO with n∈n∗/4,…,4n∗,Tn \in \\{n^*/4, \dots, 4n^*, T\\}.

The results strongly support Rec. 1. For every q≥1q \ge 1, n∗n^* yields the lowest regret among all the values of nn (App. E, Table 5). For q=0q = 0, the regret decreases with nn and plateaus as ∥un∥22\|u_n\|_2^2 saturates, as Rec. 1 predicts. For every qq, the ranking of RT/TR_T/T follows that of ∥un∥22\|u_n\|_2^2 (Spearman correlation ≥0.94\ge 0.94). Table 2 reports ∥un∥22\|u_n\|_2^2 rather than C2∥un∥22C_2\|u_n\|_2^2, as C2C_2 does not depend on nn.

Besbes et al.; rates. We now cite Besbes, Gur & Zeevi (2014, 2015) in Sec. 2.3. Their results do not affect the claim in our paper, which is about the dependence on R(n)R(n): variation-budget analyses index time by iterations, i.e., assume a constant response time, and their rates are sublinear only if VT=o(T)V_T = o(T). These assumptions fail in our problem setting.

Adaptivity is untested; Q2. Rec. 1 depends on RR only through iR(n)/lTiR(n)/l_T. Across our benchmarks, lT/R(0)l_T/R(0) spans more than three orders of magnitude (Table 3), and the selected dataset sizes vary accordingly (Figs. 3-13), from strong removal (Eggholder) to a growing dataset (Powell). However, the growth of R(n)R(n) is shared by all benchmarks (same library and hardware). The controlled experiment above varies it, and isolates Rec. 1, where FIFO runs differ only by nn. The best nn follows RR: n=Tn = T for constant RR (q=0q = 0), and n∗n^* for growing RR (q≥1q \ge 1). W-DBO and BOLT are not included, since Wasserstein removal is outside the scope of Thm 3.6. Table 4 already isolates their margin because of the dataset-size rule (same removal policy, 0.04 vs. 0.21).

FIFO with fixed nn is SW-GPUCB's sliding window applied to our model, so these runs cover the requested grid. Growing datasets are represented by GPUCB, which ignores temporal variation, and TV-GPUCB, which models it.

Q3 (fit of RR). Def. 3.5 constrains RR, not individual measurements. In practice, measured times are noisy, and the cubic fit is how BOLT incorporates them. Errors on the fitted RR affect BOLT's dataset size, as errors on online inference of hyperparameters affect every compared method.

Q4 (bounded RR). Table 1 reports the assumption on RR made in the analysis of each method, not a property that RR must satisfy. Condition (iii) of Def. 3.5 in the submitted version, now moved to App. B, is not used by Thm 3.6: it is only used in App. B to guarantee that n∗n^* is finite. Since R(m)≥R(0)R(m) \ge R(0), we have G≤R(0)−1∫0∞gTG \le R(0)^{-1}\int_0^\infty g_T, so Thm 3.6 holds for bounded RR whenever gTg_T is integrable (e.g., Matérn, RBF). For constant RR, Rec. 1 returns n∗=Tn^* = T, in line with growing-dataset methods.

As the discussion period comes to an end, we thank the reviewer again for their review, and hope that our rebuttal and the revised PDF (changes in blue) have addressed their concerns. In particular:

  • the controlled experiment requested in Q1 and Q2 is now Sec. 5.1 (Table 2, App. E). With a simulated clock and R(n)=R(0)+c nqR(n) = R(0) + c\,n^q, q∈0,1,2,3q \in \\{0,1,2,3\\}, n∗n^* yields the lowest regret among all the values of nn for every q≥1q \ge 1, and the ranking of the maximal dataset sizes by regret follows that of ∥un∥22\|u_n\|_2^2;
  • the static case is now derived from Lemma A.2 (Sec. 3.2), and condition (iii) of Def. 3.5 is moved to App. B (Q4);
  • Secs. 1 and 5.3 now state both the aggregate and the per-benchmark results.

We remain available to discuss any further concern.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.