Pith. sign in

REVIEW 2 major objections 4 minor 1 cited by

On the convergence rate of noisy Bayesian Optimization with Expected Improvement

T0 review · 2 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read The paper proves the first asymptotic convergence rates for expected improvement with noisy observations under a Gaussian-process prior on the objective.

desk verdict Real gap, nice decomposition, but the main proof applies fixed-β concentration at a randomly selected index and the advertised noisy rates are not established as written. read the letter →

arxiv 2501.09262 v2 pith:D7RBGPX3 submitted 2025-01-16 stat.ML cs.LGmath.OC

Jingyi Wang , Haowei Wang , Nai-Yuan Chiang , Cosmin G. Petra This is my paper · ORCID
classification stat.MLcs.LGmath.OC MSC 60G1562L0590C26
keywords BayesianoptimizationexpectedimprovementGaussianprocesspriornoisyobservationsconvergenceratesimpleregretMatérnkernelsquaredexponential
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

Expected improvement is a standard acquisition rule in Bayesian optimization, but until now its convergence rate was only known in the noiseless, reproducing-kernel setting. This paper proves the first asymptotic rate for noisy observations when the objective is drawn from a Gaussian-process prior: the best noisy value converges to below the true optimum at rate $O(t^{-1/2} \log^{(d+1)/2} t)$ for squared-exponential kernels and $O(t^{-\nu/(2\nu+d)} \log^{\nu/(2\nu+d)} t)$ for Matérn kernels, with probability at least $1-\delta$. The same analysis yields noiseless rates matching the known RKHS rates and an improved noiseless bound in the RKHS case. If correct, noisy expected improvement is not only practically effective but also provably rate-optimal up to logarithmic factors.

What carries the argument

The carrying object is the two-argument form $\mathrm{EI}(a,b) = a\Phi(a/b) + b\varphi(a/b)$, where $a$ is the exploitation term $y_t^+ - \mu_t(x)$ and $b$ is the exploration term $\sigma_t(x)$. Lemma 3.5 shows this function is increasing in both arguments, and the proof uses that monotonicity to compare the acquisition value at the optimum with its value at the next sampled point: unless the posterior standard deviation at the optimum is no larger than at the new sample, EI at the optimum dominates and contradicts the definition of the next sample. A second load-bearing mechanism is the information-theoretic bound $\sum_{i=1}^t \sigma_{i-1}^2(x_i) \le C_\gamma \gamma_t$ (Lemma 2.2), together with known growth rates for the maximum information gain $\gamma_t$, which converts the variance at the chosen point into the explicit $t^{-1/2}$ and $t^{-\nu/(2\nu+d)}$ rates.

What would settle it

Draw a sample path from a Matérn Gaussian process with $\nu<1$ and evaluate the ratios $|f(x)-f(y)|/\|x-y\|$ over increasingly dense grids on $\mathcal{C}$; the supremum grows without bound as the grid refines, showing the Lipschitz clause of Assumption 2.5 fails almost surely and the Matérn theorems as stated have no nonempty domain.

Watch

Extended reading notes

Core claim

Under Assumption 2.5—$f$ sampled from $\mathrm{GP}(0,k)$, Lipschitz continuous, with $k(x,x)=1$—the paper shows that the noisy simple regret $r_t = y_t^+ - f(x^*)$ satisfies $r_t \le C_1(M + \sqrt{c_t^\sigma}\sigma) \frac{6}{t-3} + (C_1\sqrt{\beta} + C_2)\sigma_{t_k}(x_{t_k+1})$ with probability at least $1-\delta$ (Theorem 4.6), and then converts the variance term into explicit kernel-dependent rates using the information-theoretic bound on summed posterior variances. For squared-exponential kernels this gives $O(t^{-1/2} \log^{(d+1)/2} t)$; for Matérn kernels it gives $O(t^{-\nu/(2\nu+d)} \log^{\nu/(2\nu+d)} t)$ (Theorem 4.9). In the noiseless GP-prior case the method recovers the rates previously known only under RKHS assumptions, $O(t^{-\min\{\nu,1\}/d} \log^{\eta} t)$, and under RKHS assumptions it proves a strictly smaller error bound than the earlier result.

Load-bearing premise

The load-bearing premise is that the objective is both a draw from a Gaussian process and Lipschitz continuous; for Matérn kernels with roughness $\nu<1$ no function satisfies both, so the advertised Matérn rate rests on a condition that is vacuous as stated.

Editorial extensions

If this is right

  • If the main theorem is correct, noisy GP-EI has simple regret decreasing at essentially the same rate as GP regression error, up to logarithmic factors: $O(t^{-1/2})$ for squared-exponential kernels.
  • For Matérn kernels, rougher objectives with smaller $\nu$ converge slower, exactly as the exponent $\nu/(2\nu+d)$ predicts.
  • The noiseless GP-prior result closes a gap between Bayesian and RKHS analyses: GP-EI attains the same convergence rates under a GP prior as under the RKHS assumption.
  • The exploration-exploitation comparison gives a strictly smaller error constant than the direct analysis, often an order of magnitude smaller for moderate $\delta$.
  • Under the RKHS assumption, the improved noiseless bound becomes increasingly better than the previous bound as the RKHS norm bound $B$ grows.

Reading between the lines

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

  • A direct consequence the authors do not spell out: the Matérn half of Theorem 4.9, as stated, has no nonempty support when $\nu<1$, because Matérn sample paths are almost surely not Lipschitz while Assumption 2.5 requires Lipschitz continuity. Replacing Lipschitz with continuity or Hölder regularity should preserve the proof, since the argument only uses boundedness $M$ and Gaussian posterior conc
  • The same comparison argument—EI at the optimum must not exceed EI at the next sample, which forces $\sigma_t(x^*)$ to be controlled by $\sigma_t(x_{t+1})$—could be adapted to prove cumulative regret bounds for unmodified EI, something current regret analyses only achieve with modified acquisition functions.
  • The logarithmic factors in the noisy rates likely come from the union-bound technique rather than from the algorithm itself; one could test whether the $\log^{(d+1)/2} t$ factor is removable by tracking tail probabilities more sharply.
Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

  1. Claim #1: Under Assumption 2.5—$f$ sampled from $\mathrm{GP}(0,k)$, Lipschitz continuous, with $k(x,x)=1$—the paper shows that the noisy simple regret $r_t = y_t^+ - f(x^*)$ satisfies $r_t \le C_1(M + \sqrt{c_t^\sigma}\sigma) \frac{6}{t-3} + (C_1\sqrt{\beta} + C_2)\sigma_{t_k}(x_{t_k+1})$ with probability at least $1-\delta$ (Theorem 4.6), and then converts the variance term into explicit kernel-dependent r

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper studies the asymptotic convergence of Bayesian optimization with the expected improvement acquisition function (GP-EI) when the objective is modeled as a sample from a Gaussian process prior. It claims the first asymptotic error rate for noisy GP-EI under this Bayesian assumption: for the noisy error r_t = y^+_t - f(x_*), the advertised bounds are O(t^{-1/2} log^{(d+1)/2} t) for squared-exponential kernels and O(t^{-\nu/(2\nu+d)} log^{\nu/(2\nu+d)} t) for Matérn kernels, with probability at least 1-\delta. The proof proceeds by establishing pointwise Gaussian concentration lemmas for the improvement function and for GP prediction errors, then selecting a favorable time index t_k via an exploration/exploitation argument, and finally feeding information-theoretic bounds on the sum of posterior variances into the resulting error estimate. The paper also derives improved noiseless bounds under the GP prior and an improved bound for RKHS objectives.

Significance. If the advertised rates are correct, the paper would fill a genuine gap: existing asymptotic analyses of GP-EI either assume an RKHS objective or treat the noiseless case only, so a noisy Bayesian analysis with explicit rates would be a substantive contribution. The exploration/exploitation trade-off argument is original and could be useful beyond EI, and the route through the maximum information gain \gamma_t is standard and well matched to the problem. The paper also gives explicit constants and illustrative numerics. However, the main proof contains a load-bearing measurability gap involving the randomly selected index t_k, and the assumptions are internally inconsistent for Matérn kernels with low smoothness. These issues must be resolved before the advertised rates can be considered established.

major comments (2)
  1. [§4.1, Eq. (4.6) and (4.14)] The proof applies the fixed-δ, fixed-t concentration inequalities of Lemmas 3.7, 3.9, and 3.10 at a random index t_k whose definition involves y_{t_k+1}, equivalently f(x_{t_k+1}). Since t_k is not measurable with respect to F_{t_k}, these pointwise bounds are not valid conditionally on the selection event. The event y^+_{t_k} - y^+_{t_k+1} < (2M+2\sqrt{c^\sigma_t}\sigma)/k conditions on the new observation being not too low, which can bias f(x_{t_k+1}) upward and inflate the upper tail f(x_{t_k+1}) - \mu_{t_k}(x_{t_k+1}). This invalidates the chain (4.7)-(4.8) in Theorem 4.2, the analogous chain (4.15)-(4.17) in Theorem 4.6, and therefore also Theorem 4.9, which explicitly relies on Theorem 4.6. The standard repair via Lemma 3.8 would force β_t = O(log(t/δ)); carrying that through the proof makes the constants C1 and C2 (or c_τ(β_t)) depend on t, so the noiseless bounds in Theorems 4.6 and 4.7 no longer tend to zero, while the noisy exponents in Theorem 4.9 would gain an additional logarithmic factor. The authors need either to prove a valid concentration inequality for a data-dependent t_k with fixed β, or to restate the theorems under the union-bound version with β_t and adjust the advertised rates accordingly.
  2. [Assumption 2.5 and Theorems 4.7/4.9] Assumption 2.5 requires f to be Lipschitz continuous, but a sample path of a Matérn Gaussian process with smoothness parameter ν ≤ 1 is almost surely not Lipschitz; such paths are only Hölder of every order strictly less than ν. Consequently, the Matérn half of Theorems 4.7 and 4.9 has empty support as stated for the advertised range ν > 0. The proofs appear to use only boundedness of f (Lemma 4.1) and Gaussian posterior concentration, not the Lipschitz constant L, so the inconsistency is fixable by replacing Lipschitz continuity with almost sure boundedness/continuity, or by restricting the Matérn statement to ν > 1. As written, however, this is an internal inconsistency in a load-bearing assumption.
minor comments (4)
  1. [§4.1, after Eq. (4.4)] The text first defines w_t = 2 log(π^2 t^2 / (6δ)) and then writes 'Let c^σ_t = w_t = 2 log(π^2 t^2 / (2δ))'; these two expressions are not equal. The intended statement is presumably that c^σ_t = 2 log(π^2 t^2 / (2δ)) gives probability at least 1 - δ/3 via a union bound.
  2. [Theorem 4.7] The statement defines c_α = 1+2π/π, which is missing parentheses; based on Lemma 3.9 and Theorem 4.6 it should presumably be c_α = (1+2π)/(2π).
  3. [§4.3, proof of Theorem 4.15] The sentence 'We note that the probability δ = 0' is unclear; since the RKHS bound is deterministic rather than probabilistic, the intended meaning is probably 'with probability one' or 'deterministically'.
  4. [Throughout] There are several typographical errors, including 'convergnce' in the introduction to Section 4, 'charaterized' in Theorem 4.15, and 'respetively' in Section 5; these should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the noisy-EI convergence rates are derived from external information-gain bounds and standard GP concentration arguments, not from the target rates themselves.

full rationale

I walked the derivation chain and found no step in which a claimed prediction reduces by construction to a fitted input, a self-citation, or a definitional equivalence. The paper's central result, Theorem 4.9, obtains the noisy rates by combining Lemma 2.2, the information-theoretic bound on summed posterior variances, and Lemma 2.3, the kernel-specific maximum information gain rates, both cited from independent external literature ([18], [32]). These external bounds are fed into EI-specific inequalities derived in Section 3 directly from the closed-form EI definition (2.3), such as Lemmas 3.9 and 3.10. No parameter is fitted to the error sequence rt, and no benchmark is assumed that is itself the rate being proved. The exploration-exploitation contradiction argument in Theorem 4.6 rests on the algorithm's own maximization property EItk(xtk+1) >= EItk(x*), which is a logical consequence of (2.6), not a restatement of the theorem's conclusion. There are no load-bearing self-citations: the cited prior works are not by the present authors, and the GP posterior concentration used in Lemma 3.7 is a standard external result. The two substantive concerns about this paper are correctness risks rather than circularity: the random index tk chosen via (4.6)/(4.14) may not be F_tk-measurable, so Lemma 3.7 is applied at a data-dependent index without a union bound; and Assumption 2.5 combines GP sample paths with Lipschitz continuity, which is incompatible with Matérn smoothness parameter nu < 1. Both concerns challenge the proof's validity or assumption support, but neither involves deriving X from an input that already contains X. Therefore the appropriate circularity score is 0.

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

The paper introduces no fitted numerical parameters: all constants such as beta, w, C1, C2, and c_sigma_t are explicit functions of delta, sigma, and kernel quantities. The main axioms are the GP prior, Lipschitz continuity, Gaussian noise, compact domain, and external information-theoretic and RKHS lemmas. No new physical or mathematical entities are postulated.

assumptions (8)
  • domain assumption Objective f is a sample from GP(0,k) with k(x,x)<=1 and k(x,x)=1
    Assumption 2.5; gives Gaussian posterior and the pointwise concentration Lemma 3.7 used throughout.
  • domain assumption Objective f is Lipschitz continuous with constant L
    Assumption 2.5; used only to guarantee boundedness M, but inconsistent with Matérn nu<1 sample paths.
  • domain assumption Observation noise is i.i.d. N(0, sigma^2)
    Assumption 2.8; needed for the probability f(x_i)>=y_i equals 1/2 and for the information gain bounds.
  • domain assumption Domain C subset [0,r]^d is compact
    Assumption 2.7; supports covering arguments, boundedness, and Bull Lemma 7.
  • standard math Information gain sum bound (Lemma 2.2)
    Cited from Srinivas et al. [18]; converts posterior variance sums to gamma_t in Theorem 4.9.
  • standard math Rates for gamma_t for SE and Matérn kernels (Lemma 2.3)
    Cited from Vakili et al. [32]; drives the explicit noisy rates O(t^{-1/2} log^{(d+1)/2} t) and O(t^{-nu/(2nu+d)} log^{nu/(2nu+d)} t).
  • domain assumption Bull Lemma 7 counting bound on posterior variance of EI iterates
    Cited from [17]; used in Theorem 4.7 to turn posterior variance bounds into kernel-specific noiseless rates.
  • domain assumption RKHS prediction error bound and EI deviation bound (Lemmas 4.12 and 4.13)
    Cited from [30] and [17]; used in the Section 4.3 improvement for RKHS objectives.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the convergence rate of noisy Bayesian Optimization with Expected Improvement." pith.science (2026). https://pith.science/paper/D7RBGPX3

@misc{pith2026250109262,
  author       = {Pith},
  title        = {Pith review of: On the convergence rate of noisy Bayesian Optimization with Expected Improvement},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/D7RBGPX3}},
  note         = {Machine review of arXiv:2501.09262}
}
read the original abstract

Expected improvement (EI) is one of the most widely used acquisition functions in Bayesian optimization (BO). Despite its proven success in applications for decades, important open questions remain on the theoretical convergence behaviors and rates for EI. In this paper, we contribute to the convergence theory of EI in three novel and critical areas. First, we consider objective functions that fit under the Gaussian process (GP) prior assumption, whereas existing works mostly focus on functions in the reproducing kernel Hilbert space (RKHS). Second, we establish for the first time the asymptotic error bound and its corresponding rate for GP-EI with noisy observations under the GP prior assumption. Third, by investigating the exploration and exploitation properties of the non-convex EI function, we establish improved error bounds of GP-EI for both the noise-free and noisy cases.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Simple-regret rates and minimax optimality of fixed-prior expected improvement in Mat\'ern and squared-exponential RKHSs

    stat.ML 2026-07 accept novelty 8.0 of 10

    Fixed-prior expected improvement attains the minimax simple-regret rate N^{-ν/d} on Matérn RKHS balls and near-optimal exponential rates on squared-exponential RKHS balls.

Reference graph

Works this paper leans on

33 extracted references · 27 canonical work pages · cited by 1 Pith paper

  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 based on response surfaces.Journal of global optimization, 21:345–383, 2001

    work page 2001

  3. [3]

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

    work page 2023

  4. [4]

    J. Wu, X. Chen, H. Zhang, L. Xiong, H. Lei, and S. Deng. Hyperparameter optimization for machine learning models based on Bayesian optimization.Journal of Electronic Science and Technology, 17(1):26–40, 2019

    work page 2019

  5. [5]

    Multi-objectiveconstrainedBayesianoptimization for structural design.Structural and Multidisciplinary Optimization, 63:689–701, February 2021

    A.Mathern, O.S.Steinholtz, A.Sjöberg, etal. Multi-objectiveconstrainedBayesianoptimization for structural design.Structural and Multidisciplinary Optimization, 63:689–701, February 2021

    work page 2021

  6. [6]

    Calandra, A

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

    work page 2016

  7. [7]

    Optimization of process parameters in additive manufacturing based on the finite element method

    J. Wang and P. Papadopoulos. Optimization of process parameters in additive manufacturing based on the finite element method.arXiv preprint arXiv:2310.15525, 2023

    work page Pith review arXiv 2023

  8. [8]

    J. Wang, N. Y. Chiang, A. Gillette, and J. L. Peterson. A multifidelity Bayesian optimization method for inertial confinement fusion design.Phys Plasmas, 2024

    2024

Show all 33 references
  1. [9]

    Toscano-Palmerin and P

    S. Toscano-Palmerin and P. I. Frazier. Bayesian optimization with expensive integrands.SIAM Journal on Optimization, 32(2):417–444, 2022

    2022

  2. [10]

    Shapiro, E

    A. Shapiro, E. Zhou, and Y. Lin. Bayesian distributionally robust optimization.SIAM Journal on Optimization, 33(2):1279–1304, 2023

    2023

  3. [11]

    Bayesian optimization of risk measures

    Sait Cakmak, Raul Astudillo Marban, Peter Frazier, and Enlu Zhou. Bayesian optimization of risk measures. Advances in Neural Information Processing Systems, 33:20130–20141, 2020

    2020

  4. [12]

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

    2018

  5. [13]

    Globalversuslocalsearchinconstrainedoptimization of computer models.Lecture notes-monograph series, pages 11–25, 1998

    M.Schonlau, W.J.Welch, andD.R.Jones. Globalversuslocalsearchinconstrainedoptimization of computer models.Lecture notes-monograph series, pages 11–25, 1998

    1998

  6. [14]

    Eriksson and M

    D. Eriksson and M. Poloczek. Scalable constrained Bayesian optimization. InInternational Conference on Artificial Intelligence and Statistics, pages 730–738. PMLR, 2021

    2021

  7. [15]

    J. R. Gardner, M. J. Kusner, Z. Xu, K. Q. Weinberger, and J. P. Cunningham. Bayesian optimization with inequality constraints. InProceedings of the 31st International Conference on International Conference on Machine Learning - Volume 32, ICML’14. JMLR.org, 2014

    2014

  8. [16]

    D. R. Jones, M. Schonlau, and W. J. Welch. Efficient global optimization of expensive black-box functions. Journal of Global optimization, 13:455–492, 1998

    1998

  9. [17]

    A. D. Bull. Convergence rates of efficient global optimization algorithms.Journal of Machine Learning Research, 12(10), 2011

    2011

  10. [18]

    Srinivas, A

    N. Srinivas, A. Krause, S. M. Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design.arXiv preprint arXiv:0912.3995, 2009

    2009 arXiv

  11. [19]

    Wang and N

    Z. Wang and N. de Freitas. Theoretical analysis of Bayesian optimisation with unknown Gaussian process hyper-parameters, 2014

    2014

  12. [20]

    Nguyen, S

    V. Nguyen, S. Gupta, S. Rana, C. Li, and S. Venkatesh. Regret for expected improvement over the best-observed value and stopping condition. InProceedings of the Ninth Asian Conference on Machine Learning, volume 77, pages 279–294. PMLR, 2017

    2017

  13. [21]

    S. Hu, H. Wang, Z. Dai, B. K. H. Low, and S. H. Ng. Adjusted expected improvement for cumulative regret minimization in noisy Bayesian optimization, 2022

    2022

  14. [22]

    Tran-The, S

    H. Tran-The, S. Gupta, S. Rana, and S. Venkatesh. Regret bounds for expected improvement algorithms in Gaussian process bandit optimization.arXiv preprint arXiv:2203.07875, 2022

    2022 arXiv

  15. [23]

    Lederer, J

    A. Lederer, J. Umlauft, and S. Hirche. Uniform error bounds for Gaussian process regression with application to safe control.Advances in Neural Information Processing Systems, 32, 2019

    2019

  16. [24]

    F. J. Narcowich, J. D. Ward, and H. Wendland. Sobolev error estimates and a bernstein inequality for scattered data interpolation via radial basis functions.Constructive Approximation, 24:175–186, 2006

    2006

  17. [25]

    Van Der Vaart and H

    A. Van Der Vaart and H. Van Zanten. Information rates of nonparametric Gaussian process methods. Journal of Machine Learning Research, 12(6), 2011

    2011

  18. [26]

    Steinwart

    I. Steinwart. On the influence of the kernel on the consistency of support vector machines. Journal of machine learning research, 2(Nov):67–93, 2001. 27

    2001

  19. [27]

    J. Bect, F. Bachoc, and D. Ginsbourger. A supermartingale approach to Gaussian process based sequential design of experiments. 2019

    2019

  20. [28]

    Vazquez and J

    E. Vazquez and J. Bect. Convergence properties of the expected improvement algorithm with fixed mean and covariance functions.Journal of Statistical Planning and inference, 140(11):3088–3095, 2010

    2010

  21. [29]

    I. O. Ryzhov. On the convergence rates of expected improvement methods.Operations Research, 64(6):1515–1528, 2016

    2016

  22. [30]

    S. R. Chowdhury and A. Gopalan. On kernelized multi-armed bandits. In International Conference on Machine Learning, pages 844–853. PMLR, 2017

    2017

  23. [31]

    T. M. Cover.Elements of information theory. John Wiley & Sons, 1999

    1999

  24. [32]

    Vakili, K

    S. Vakili, K. Khezeli, and V. Picheny. On information gain and regret bounds in Gaussian process bandits. InInternational Conference on Artificial Intelligence and Statistics, pages 82–90. PMLR, 2021

    2021

  25. [33]

    R. Jiao, S. Zeng, C. Li, Y. Jiang, and Y. Jin. A complete expected improvement criterion for Gaussian process assisted highly constrained expensive optimization.Information Sciences, 471:80–96, 2019. 28

    2019

Pith tools

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