Pith. sign in

REVIEW 3 major objections 4 minor 23 references

On Improved Regret Bounds In Bayesian Optimization with Gaussian Noise

T0 review · 3 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read With Gaussian observation noise, a fixed confidence multiplier bounds GP prediction error at every point and time, improving cumulative regret rates for GP-UCB and GP-TS to near the known lower bounds.

desk verdict The GP-UCB half of this paper is a real contribution; the Thompson sampling half is not ready as written because the proof relies on a false tail bound and an algebra slip. read the letter →

arxiv 2412.18789 v1 pith:NSZZPUNY submitted 2024-12-25 cs.LG stat.ML

Jingyi Wang , Haowei Wang , Cosmin G. Petra , Nai-Yuan Chiang This is my paper · ORCID
classification cs.LGstat.ML
keywords BayesianoptimizationGaussianprocessupperconfidenceboundThompsonsamplingcumulativeregretpredictionerrorfrequentistsettingnoise
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper seeks to close the gap between Bayesian and frequentist regret analyses of Gaussian-process bandit algorithms. The authors prove a pointwise prediction-error bound under the frequentist assumption that the objective lies in an RKHS, with i.i.d. Gaussian observation noise: at any fixed query point and time, |f(x)-mu_t(x)| <= $beta^{{1/2}}$ sigma_t(x) with a constant $\beta$ that depends only on the confidence level, not on t. In earlier frequentist analyses the confidence multiplier had to grow with t, which inflated regret. From the constant-$\beta$ bound they derive cumulative regret rates for GP-UCB of O($\sqrt$(T) $log^{{(d+2)/2}}$ T) for squared-exponential kernels and O($T^{{(nu+d)/(2nu+d)}}$ $log^{{(4nu+d)/(4nu+2d)}}$ T) for Matérn kernels, with GP-TS rates a half-log factor worse. A sympathetic reader should care because these are the closest upper bounds to the known lower bounds and they make the frequentist and Bayesian settings agree in order.

What carries the argument

The argument's central object is the linear-smoother representation of the posterior mean, mu_t(x) = h_t(x)^T y_{1:t} with h_t(x) = (K_t + $sigma^{2}$ I)^{-1} k_t(x). The paper proves the weight vector satisfies ||h_t(x)|| <= sigma_t(x)/$\sigma$ by a positive-semidefinite Schur-complement argument. Since the noise-induced part of the prediction error, e_t(x) = h_t(x)^T epsilon_{1:t}, is a Gaussian of variance ||h_t(x)||^2 $sigma_eps^{2}$ <= (sigma_eps/$\sigma$)^2 sigma_t(x)^2, a standard Gaussian tail bound with a confidence-dependent threshold gives the constant-$\beta$ pointwise error bound. The second load-bearing component is Lemma 3.2 (borrowed from references [9,18,20]), which bounds the noiseless part by B sigma_t(x).

What would settle it

Simulate the theorem directly: fix a kernel with k(x,x)=1, a function f with RKHS norm B, and Gaussian noise of variance $sigma_eps^{2}$; repeat many draws of the noise, compute mu_t(x) and sigma_t(x) at fixed x and t, and check whether the empirical 1-delta quantile of |f(x)-mu_t(x)|/sigma_t(x) exceeds B+(sigma_eps/$\sigma$) $\sqrt$(2 log(1/delta)). Any kernel-point choice where the bound is violated with probability greater than delta would refute Theorem 3.3; a cheaper check is to test whether Lemma 3.2 can be replaced by a t-dependent factor.

Watch

Extended reading notes

Core claim

Under Assumption 2.2 (f in the RKHS with norm at most B) and Assumption 2.6 (i.i.d. Gaussian noise of variance $sigma_eps^{2}$), the paper proves that for any delta in (0,1), choosing $beta^{{1/2}}$ = B + (sigma_eps/$\sigma$) $\sqrt$(2 log(1/delta)) gives P(|f(x)-mu_t(x)| <= $beta^{{1/2}}$ sigma_t(x)) >= 1-delta at every fixed x and t. The novelty is that $\beta$ is constant in t, so the prediction-error bound does not deteriorate as sampling proceeds. Lifting this pointwise bound to a discrete grid via union bounds yields GP-UCB cumulative regret R_T <= (C_1 T beta_T gamma_T)^{1/2} + 2 with probability at least 1-delta, and the corresponding GP-TS bound, which when instantiated with the maximum information gain gamma_T for SE and Matérn kernels gives the improved rates in Table 1.

Load-bearing premise

The load-bearing premise is that the function-only part of the prediction error is bounded by B times the posterior standard deviation with one time-independent constant B (a lemma the paper imports rather than proves); if that constant must grow with the number of samples, or if the noise variance is not known well enough to set beta, the regret improvement collapses.

Editorial extensions

If this is right

  • For squared-exponential kernels, GP-UCB reduces its frequentist cumulative regret from O(sqrt(T) log^{(d+5)/2} T) to O(sqrt(T) log^{(d+2)/2} T).
  • For Matérn kernels, GP-UCB regret becomes O(T^{(nu+d)/(2nu+d)} log^{(4nu+d)/(4nu+2d)} T), compared with O(T^{(nu+d)/(2nu+d)} log^{(10nu+4d)/(4nu+2d)} T) in the prior state of the art.
  • GP-TS improves to O(sqrt(T) log^{(d+3)/2} T) for squared-exponential kernels and O(T^{(nu+d)/(2nu+d)} log^{(3nu+d)/(2nu+d)} T) for Matérn kernels, within a half-log factor of GP-UCB.
  • The frequentist GP-UCB regret rates now match, in order, the Bayesian-setting rates, closing that long-standing gap.
  • The constant-beta pointwise bound applies to any acquisition function whose analysis needs a finite confidence radius, including expected improvement under noise.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the same constant-beta pointwise bound should yield a simple-regret bound for the best point found at essentially the same rate, since the paper's union bound controls f(x*) - mu_{t-1}([x*]_t) at the optimum.
  • Editorial inference: the improvement over prior sub-Gaussian analyses is exactly the d log(T) versus gamma_T gap, so the practical gain is largest for smooth kernels in low dimension; in high dimension the log-factor savings may be negligible compared with the leading term.
  • Editorial inference: if sigma_eps is unknown, a practitioner can estimate it from the data, but the fixed-beta guarantee requires a valid upper bound on sigma_eps; the paper does not develop an adaptive choice, so an empirical plug-in would need its own confidence analysis.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies cumulative regret of GP-UCB and GP-TS in the frequentist setting under i.i.d. Gaussian observation noise. Its main technical step is a pointwise prediction-error bound |f(x)-μ_t(x)| ≤ β^{1/2}σ_t(x) with a confidence-dependent but time-independent β, proved via a spectral argument bounding the noise-induced posterior mean by σ_t(x). From this it derives a GP-UCB regret bound O(√(Tβ_Tγ_T)) and claims GP-TS rates O(d log T √(Tγ_T)), specializing to improved squared-exponential and Matérn rates that are within logarithmic factors of existing lower bounds. The GP-UCB argument appears sound; the GP-TS proof contains several invalid steps that must be repaired.

Significance. The constant-β pointwise bound is the paper's core conceptual contribution: it removes the t-dependent β_t from the frequentist UCB analysis and closes the gap with the Bayesian setting. The spectral proof of ‖(K_t+σ²I)^{-1}k_t‖ ≤ σ_t(x)/σ is clean, the union-bound extension is standard, and the GP-UCB regret proof is transparent and appears correct. The claimed Thompson-sampling improvements are also of interest, but they are not established as written because the TS section relies on a false Gaussian tail bound, an incorrect summation step, and an inconsistent supermartingale definition. These defects are localized and likely repairable without changing the stated rates, but the proof must be corrected before the TS results can be accepted.

major comments (3)
  1. [§4.1, Lemma 4.11] Lemma 4.11 is false. For w=1, the claimed lower bound e^{-1/4}/√π ≈ 0.44 exceeds the true standard-normal tail Φ(-1) ≈ 0.159, and for w=0.5 the right-hand side exceeds 1. Since Lemma 4.12 applies this bound with w=1 to obtain p = 1/(4e√π), the proof of Eq. (4.16) is invalid. The conclusion P_t{f_t(x) > f(x)} ≥ p can be recovered directly from Φ(-1) > p, but the false lemma must be removed or replaced. Note also that the normalization in Eq. (4.17) divides by ν_t σ_{t-1}(x), whereas f_t(x) has standard deviation ν_t^{1/2}σ_{t-1}(x); this denominator must be fixed before Lemma 4.11 could be applied.
  2. [§4.1, Eq. (4.38)] The inequality bounding the martingale term is algebraically wrong: √(Σ_{t=1}^T ζ_t) is bounded by √(T ζ_T), not by √(ζ_T). Thus the displayed simplification in Eq. (4.38) is missing a factor √T, and the corresponding term in Eq. (4.35) is also inconsistent because it writes ζ_T where the proof yields ζ_T^{1/2}. For the SE and Matérn rates in Theorem 4.19 this omission does not change the final exponent, but Lemma 4.18 and Eq. (4.38) must be corrected before the TS regret proof is valid.
  3. [§4.1, Eqs. (4.31)-(4.34)] The definition of X_t in Eq. (4.31) and the conditional expectation in Eq. (4.34) appear to have a sign error: X_t is written as \bar r_t - 11ζ_t^{1/2}/p · σ_{t-1}(x_t) - 2B + 1/t², but Lemma 4.14 gives E[\bar r_t] ≤ 11ζ_t^{1/2}/p · E[σ_{t-1}(x_t)] + 2B + 1/t². For the supermartingale inequality E_t[X_t] ≤ 0 to hold, the last two terms must be -(2B + 1/t²). With the displayed definition, on E_f(t) one only obtains E_t[X_t] ≤ 2/t², so Lemma 4.17 is not justified as written. The later bound in Eq. (4.36) treats 2B+1/t² as a positive summand, which confirms the intended correction, but the displayed definitions need to be fixed.
minor comments (4)
  1. [§3.2, proof of Lemma 3.6] The notation α_t^{1/2} is defined as 2 log(|C|π_t/δ), but the subsequent union-bound algebra |C|∑e^{-α_t/2}=δ requires α_t = 2 log(|C|π_t/δ), i.e., α_t^{1/2} = √(2 log(|C|π_t/δ)). The statement's β_t definition is correct, so this is a notational slip in the proof.
  2. [§2.3 and throughout] There are several typos: 'CP-UCB' in the description of Algorithm 2.2 should be 'GP-UCB', and words such as 'acqusition', 'spetral', and 'genearlity' should be corrected.
  3. [§4.1, Lemma 4.12] The proof's last inequality is written as '≥ 1/(4√π e)' while the stated p is 1/(4e√π); after fixing Lemma 4.11 the constant should be rederived consistently.
  4. [§4.1, proof of Theorem 4.19] In Eq. (4.42), the summation ∑_{t−1} σ_{t-1}(x_t) should read ∑_{t=1}^T σ_{t-1}(x_t).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the prediction-error bound is derived from an external RKHS lemma and Gaussian tail bounds, and the regret results follow from standard information-gain bounds without fitting any target quantity.

full rationale

The paper's central derivation is self-contained relative to standard external results and does not reduce to its own inputs by construction. Theorem 3.3 bounds |f(x)-mu_t(x)| by beta^{1/2} sigma_t(x) by combining Lemma 3.2 (the noiseless RKHS projection error bound, cited to [9,18,20], none of which are by the present authors) with a variance analysis of the noise term e_t(x)=k_t(x)^T(K_t+sigma^2 I)^{-1} eps_{1:t}. The constant beta is explicitly constructed from delta, B, sigma_eps, and sigma; it is not fitted to data and it does not presuppose the regret bound. The GP-UCB regret proof (Theorem 4.4) uses Lemma 4.3, which in turn uses the pointwise bounds of Lemmas 3.7 and 3.9, plus the standard information-gain lemmas from [8]; the final rate O(sqrt(T beta_T gamma_T)) is a direct Cauchy-Schwarz consequence. The GP-TS analysis follows the framework of [9] with no parameter fitted to the target regret. The cited maximum-information-gain rates for SE and Matérn kernels from [11] are external and independent of the paper's claims. The only notable weaknesses in the paper are correctness issues in the GP-TS proof (Lemma 4.11's Gaussian lower tail bound is false as stated, and the last inequality in (4.38) omits a sqrt(T) factor), but those are mathematical validity defects, not circularity: they do not involve defining a result in terms of itself or fitting a parameter and then calling it a prediction. Accordingly, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim rests on standard BO assumptions (RKHS membership, Lipschitz continuity, Gaussian noise) and two external results: the noiseless error bound and maximum information gain rates. No parameters are fitted to data and no new entities are postulated.

assumptions (5)
  • domain assumption The objective f lies in the reproducing kernel Hilbert space H_k of the known kernel, with ||f||_{H_k} <= B, and the kernel satisfies k(x,x)=1 and k(x,x')<=1 (Assumption 2.2).
    Used in Lemma 3.2 to bound the noiseless prediction error by B sigma_t(x), which is what makes the constant beta possible.
  • domain assumption The objective f is Lipschitz continuous with known constant L (Assumption 2.3).
    Used to construct discretizations C_t with h_t=1/(L t^2), adding the 1/t^2 term in Lemma 3.9 and Lemma 4.3.
  • domain assumption The observation noise is zero-mean i.i.d. Gaussian with variance sigma_eps^2 (Assumption 2.6).
    This makes e_t(x) Gaussian with variance at most (sigma_eps^2/sigma^2) sigma_t^2(x), which is the core property enabling the constant-beta pointwise bound.
  • standard math The noiseless posterior mean error bound in Lemma 3.2 is valid as stated.
    Cited from [9,18,20] and not proved in this paper; it is a known RKHS interpolation bound.
  • standard math The maximum information gain rates gamma_T for squared exponential and Matérn kernels from [11] are valid.
    These rates are substituted into the generic regret expressions in Theorems 4.4 and 4.19 to report the final kernel-specific bounds.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Improved Regret Bounds In Bayesian Optimization with Gaussian Noise." pith.science (2026). https://pith.science/paper/NSZZPUNY

@misc{pith2026241218789,
  author       = {Pith},
  title        = {Pith review of: On Improved Regret Bounds In Bayesian Optimization with Gaussian Noise},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NSZZPUNY}},
  note         = {Machine review of arXiv:2412.18789}
}
read the original abstract

Bayesian optimization (BO) with Gaussian process (GP) surrogate models is a powerful black-box optimization method. Acquisition functions are a critical part of a BO algorithm as they determine how the new samples are selected. Some of the most widely used acquisition functions include upper confidence bound (UCB) and Thompson sampling (TS). The convergence analysis of BO algorithms has focused on the cumulative regret under both the Bayesian and frequentist settings for the objective. In this paper, we establish new pointwise bounds on the prediction error of GP under the frequentist setting with Gaussian noise. Consequently, we prove improved convergence rates of cumulative regret bound for both GP-UCB and GP-TS. Of note, the new prediction error bound under Gaussian noise can be applied to general BO algorithms and convergence analysis, e.g., the asymptotic convergence of expected improvement (EI) with noise.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 20 canonical work pages

  1. [1]

    D. J. Lizotte. Practical bayesian optimization . PhD thesis, University of Alberta, Edmonton, Alberta, Canada, 2008

    work page 2008

  2. [2]

    D. R. Jones. A taxonomy of global optimization methods ba sed on response surfaces. Journal of global optimization , 21:345–383, 2001

    work page 2001

  3. [3]

    W ang, Y

    X. W ang, Y. Jin, S. Schmitt, and M. Olhofer. Recent advanc es in Bayesian optimization. ACM Comput. Surv. , 55(13s), jul 2023

    work page 2023

  4. [4]

    P. I. Frazier. Bayesian optimization. In Recent advances in optimization and modeling of contemporary problems, pages 255–278, October 2018

    work page 2018

  5. [5]

    Hyperparam- eter optimization for machine learning models based on baye sian optimization

    Jia W u, Xiu-Yun Chen, Hao Zhang, Li-Dong Xiong, Hang Lei, and Si-Hao Deng. Hyperparam- eter optimization for machine learning models based on baye sian optimization. Journal of Electronic Science and Technology , 17(1):26–40, 2019

    work page 2019

  6. [6]

    Mathern, O

    A. Mathern, O. S. Steinholtz, A. Sjöberg, et al. Multi-ob jective constrained Bayesian opti- mization for structural design. Structural and Multidisciplinary Optimization , 63:689–701, February 2021

    work page 2021

  7. [7]

    Calandra, A

    R. Calandra, A. Seyfarth, J. Peters, and M. P. Deisenroth . Bayesian optimization for learn- ing gaits under uncertainty. Annals of Mathematics and Artificial Intelligence , 76:5–23, February 2016

    work page 2016

  8. [8]

    Gaussian process optimization in the bandit setting: No regret and experimen tal design

    Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Ma tthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimen tal design. arXiv preprint arXiv:0912.3995, 2009

    arXiv 2009

Show all 23 references
  1. [9]

    On kernelized mu lti-armed bandits

    Sayak Ray Chowdhury and Aditya Gopalan. On kernelized mu lti-armed bandits. In Interna- tional Conference on Machine Learning , pages 844–853. PMLR, 2017

    2017

  2. [10]

    Scalable thompson sampling using sparse gaussian process models

    Sattar Vakili, Henry Moss, Artem Artemev, Vincent Duto rdoir, and Victor Picheny. Scalable thompson sampling using sparse gaussian process models. Advances in neural information processing systems, 34:5631–5643, 2021

    2021

  3. [11]

    On info rmation gain and regret bounds in gauss- ian process bandits

    Sattar Vakili, Kia Khezeli, and Victor Picheny. On info rmation gain and regret bounds in gauss- ian process bandits. In International Conference on Artificial Intelligence and St atistics, pages 82–90. PMLR, 2021

    2021

  4. [12]

    Par- allelised bayesian optimisation via thompson sampling

    Kirthevasan Kandasamy, Akshay Krishnamurthy, Jeff Sch neider, and Barnabás Póczos. Par- allelised bayesian optimisation via thompson sampling. In International conference on artificial intelligence and statistics , pages 133–142. PMLR, 2018

    2018

  5. [13]

    Finite-time analysis of kernelised contextual bandits

    Michal Valko, Nathaniel Korda, Rémi Munos, Ilias Flaou nas, and Nelo Cristianini. Finite-time analysis of kernelised contextual bandits. arXiv preprint arXiv:1309.6869 , 2013

    2013 arXiv

  6. [14]

    Bandit opt imisation of functions in the matérn kernel rkhs

    David Janz, David Burt, and Javier González. Bandit opt imisation of functions in the matérn kernel rkhs. In International Conference on Artificial Intelligence and St atistics, pages 2486–2495. PMLR, 2020

    2020

  7. [15]

    Efficient high dimensio nal bayesian optimization with additivity and quadrature fourier features

    Mojmir Mutny and Andreas Krause. Efficient high dimensio nal bayesian optimization with additivity and quadrature fourier features. Advances in Neural Information Processing Systems, 31, 2018

    2018

  8. [16]

    Gaussian process optimization with adaptive sketching: Sc alable and no regret

    Daniele Calandriello, Luigi Carratino, Alessandro La zaric, Michal Valko, and Lorenzo Rosasco. Gaussian process optimization with adaptive sketching: Sc alable and no regret. In Con- ference on Learning Theory , pages 533–557. PMLR, 2019

    2019

  9. [17]

    Lower bounds on regret for noisy gaussian process bandit optimization

    Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher . Lower bounds on regret for noisy gaussian process bandit optimization. In Conference on Learning Theory , pages 1723–

  10. [18]

    Convergence rates of efficient global optimi zation algorithms

    Adam D Bull. Convergence rates of efficient global optimi zation algorithms. Journal of Machine Learning Research, 12(10), 2011

    2011

  11. [19]

    Thompson sampling for c ontextual bandits with linear payoffs

    Shipra Agrawal and Navin Goyal. Thompson sampling for c ontextual bandits with linear payoffs. In International conference on machine learning , pages 127–135. PMLR, 2013

    2013

  12. [20]

    Regret optimali ty of gp-ucb

    W enjia W ang, Xiaowei Zhang, and Lu Zou. Regret optimali ty of gp-ucb. arXiv preprint arXiv:2312.01386, 2023

    2023 arXiv

  13. [21]

    Gaussian processes for machine learn- ing, volume 2

    Christopher KI Williams and Carl Edward Rasmussen. Gaussian processes for machine learn- ing, volume 2. MIT press Cambridge, MA, 2006

    2006

  14. [22]

    Applied numerical linear algebra

    James W Demmel. Applied numerical linear algebra . SIAM, 1997

    1997

  15. [23]

    Unifo rm error bounds for gaussian process regression with application to safe control

    Armin Lederer, Jonas Umlauft, and Sandra Hirche. Unifo rm error bounds for gaussian process regression with application to safe control. Advances in Neural Information Processing Systems, 32, 2019. 18 Appendix A. Proof for auxiliary results. Lemma A.1. If a function f : Rn → R...

    2019

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.