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

Emmanuel Vazquez; S\'ebastien Petit

REVIEW 1 major objections 3 minor 13 references

Expected improvement attains minimax-optimal simple-regret rates in Matérn and squared-exponential RKHSs.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-03 10:52 UTC pith:2UVUNY2O

load-bearing objection Fixed-prior EI finally gets the Matérn minimax rate and exponential SE rates; the main thing to verify is the one-dimensional SE upper bound that leans on Yarotsky. the 1 major comments →

arxiv 2607.29245 v1 pith:2UVUNY2O submitted 2026-07-31 stat.ML cs.LGcs.NAmath.NAmath.STstat.TH

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

Emmanuel Vazquez , S\'ebastien Petit This is my paper

classification stat.ML cs.LGcs.NAmath.NAmath.STstat.TH MSC 41A4662L0560G1565K10

keywords expected improvementBayesian optimizationsimple regretminimax ratesreproducing kernel Hilbert spacesMatérn kernelssquared-exponential kernelKolmogorov widths

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper asks whether the expected-improvement (EI) heuristic—using a fixed Gaussian-process prior whose covariance is the same kernel as the objective's RKHS, with exact noiseless values—is not just consistent but near-optimal in the worst case. It proves that after N post-initial queries the simple regret (the gap between the best value found and the global minimum) is O(N^{-ν/d}) for Matérn kernels of smoothness ν, and exponentially small for squared-exponential kernels. More strongly, when the domain has nonempty interior and the RKHS ball has positive radius, exact EI attains the deterministic minimax rate for Matérn kernels and is optimal up to constants in the exponent for squared-exponential kernels. This closes a known gap: earlier upper bounds for exact EI plateaued at N^{-1/d} for smooth Matérn kernels, and the result shows EI needs no added random space-filling queries to reach the optimal rate. The proof reinterprets optimization as approximation geometry: the posterior standard deviation at a candidate point equals the norm of a feature-space innovation, and ranked innovations are bounded through sequential separation radii and Kolmogorov widths.

Core claim

The central claim is that fixed-prior expected improvement, used without randomized exploration, has essentially optimal simple-regret behavior on RKHS balls. For a Matérn kernel of smoothness ν on a compact subset of R^d, every weak-EI trajectory—one whose selected EI is at least a fixed fraction of the maximum—satisfies r_T = O(N^{-ν/d}) after N post-initial queries, uniformly over f in the RKHS ball of radius B. For the squared-exponential kernel, weak EI satisfies r_T = O(exp[-c min{N, N^{1/d} log(eN)}]), and exact EI maximization gives r_T = O(exp[-c N^{1/d} log(eN)]). If X has nonempty interior and B>0, exact EI is minimax-rate optimal among deterministic methods for Matérn kernels, an

What carries the argument

The load-bearing objects are the sequential separation radius and the Kolmogorov width. The innovation at a query point is the component of k(x,·) orthogonal to the span of previous evaluation representers; its norm equals the normalized posterior standard deviation. The separation radius δ_m(k,X) is the supremum over ordered m-point sequences of the smallest such innovation norm, and it bounds every ranked selected-point innovation over any finite horizon. Kolmogorov widths—the best uniform error in approximating the evaluation representers by an m-dimensional subspace—control the separation radii through Gram-determinant and eigenvalue estimates. The one-step regret inequality r_{n+1} ≤ q

Load-bearing premise

The load-bearing premise is that the best approximation of the kernel's evaluation functions by m basis functions decays at exactly the assumed rates (m^{-ν/d} for Matérn, e^{-c m^{1/d} log m} for squared-exponential) with no hidden logarithmic losses; the paper imports these scattered-data estimates rather than proving them.

What would settle it

Compute the sequential separation radius δ_m directly for the squared-exponential kernel in one dimension by greedy farthest-point sampling; the paper's Proposition E.5 predicts limsup_{m→∞} log δ_m/(m log m) ≤ -1/2, so a value strictly above -1/2 would disprove the refined exponential regret bound. For the Matérn claim, check whether the best m-point interpolation error on a cube really decays as O(m^{-ν/d}) uniformly over compact domains; any slower decay would invalidate the N^{-ν/d} upper bound.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

On Matérn RKHS balls of radius B, exact EI (and any weak-EI policy) achieves worst-case simple regret O(N^{-ν/d}) after N post-initial evaluations, matching the deterministic minimax lower bound for every smoothness ν.
On squared-exponential RKHS balls, exact EI achieves O(exp[-c N^{1/d} log(eN)]) simple regret, and no deterministic method can beat that exponent by more than a constant factor when the domain has interior.
The weak-EI condition means the rates hold for any implementation that keeps a fixed positive fraction of the maximum EI, so approximate EI maximizers inherit the guarantees.
The upper bounds are uniform over the RKHS ball and extend to a known continuous prior mean, so the conclusions apply to shifted function classes as well.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Editorial inference: Because the proof reduces regret to Kolmogorov-width decay, the same machinery should yield EI regret rates for other kernels with known width decay—for instance, Sobolev-type kernels of finite smoothness—though the paper only states the Matérn and squared-exponential cases.
Editorial inference: The arbitrariness of the fraction η in the weak-EI condition suggests the rates are robust to coarse EI maximization; a practitioner who maximizes EI on a finite candidate grid should still attain them as long as the grid resolves a constant fraction of the true EI maximum—an empirically testable claim.
Editorial inference: The minimax optimality is for deterministic, noiseless settings with a fixed prior. Noisy evaluations or data-driven kernel hyperparameters, which the paper explicitly leaves out, could change the rates; the feature-space mechanism alone does not predict by how much.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

Fixed-prior EI finally gets the Matérn minimax rate and exponential SE rates; the main thing to verify is the one-dimensional SE upper bound that leans on Yarotsky.

read the letter

The short version: this paper proves that the exact fixed-prior Expected Improvement policy attains the Matérn minimax simple-regret rate N^{-ν/d} for every ν>0, and gets near-optimal exponential rates for squared-exponential kernels. That closes a real gap in Bull (2011), and it does so with a proof that is actually about the geometry of the RKHS rather than about heuristics. The key idea—equating posterior standard deviation with an orthogonal innovation norm, then controlling ranked innovations via sequential separation radii—is clean and the main chain of lemmas is coherent.

What's good: the finite-budget bound in Theorem 4.4 is a genuinely useful tool. The way they apply the affine branch of the one-step regret inequality only at the L smallest innovations and use monotonicity elsewhere is a nice trick. The transfer from Kolmogorov widths to separation radii (Lemma 5.2 and Cor 5.3) is carefully done, with elementary product inequalities. The uniform-in-f constants are handled properly, which matters for minimax claims. The paper is also honest about scope: exact observations, fixed prior, no noise, and it flags the restriction to deterministic methods in the lower bounds.

Where the soft spots are: the upper bounds inherit constants and rates from external scattered-data and entropy results (Schaback–Wendland, Wendland, Yarotsky, Kühn, Xu et al.) that are cited but not reproved. For the Matérn case that's standard material and unlikely to be fragile. For the squared-exponential d=1 super-exponential bound, the load-bearing step is Prop E.5, which uses Yarotsky's conditional-variance bound to get uniform decay of the power function for any K distinct sites. The direction of the inequality is used as an upper bound, and based on the paper's own formulas (E.20)–(E.23) that looks right, but I did not go back to Yarotsky's theorem statement to verify constants and domain hypotheses. If that theorem has hidden assumptions (e.g., about the point configurations or the kernel parameter), the d=1 minimax claim in Theorem 7.4 would lose its upper half. So that is the one piece I'd want a referee to check aggressively. The lower bounds also rely on a chain through Kühn and Xu et al., but those are community-standard results.

Recommendation: this deserves a serious referee. The main theorems are important, the proof structure is transparent enough to audit, and the remaining risk is concentrated in a small number of imported estimates. Send it to review, ask specifically for verification of Prop E.5 and the Yarotsky citation, and leave the rest to the usual checking.

Referee Report

1 major / 3 minor

Summary. The paper studies the expected improvement (EI) policy for minimizing a deterministic function f in the RKHS of a continuous kernel on a compact set, under exact evaluations and a fixed zero-mean GP prior with covariance σ²k. The main claims are worst-case simple-regret bounds for weak-EI policies: O(N^{-ν/d}) for isotropic Matérn kernels and exp(-b' min{N, N^{1/d} log(eN)}) for the squared-exponential kernel; with exact EI maximization it claims the sharper SE bound exp(-c N^{1/d} log(eN)) and, on domains with nonempty interior, minimax-rate optimality for Matérn and optimality up to constants in the exponent for squared-exponential kernels. The proof methodology is a geometric reduction: posterior standard deviations are identified with feature-space innovation norms, their ranked values are bounded by sequential separation radii, width decay is transferred to separation-radius decay via Kolmogorov widths, and a one-step EI regret inequality is iterated through a finite-budget recursion.

Significance. If the concerns below are addressed, this is a substantial paper. It would resolve a real open question: fixed-prior EI, without randomized space-filling perturbations, attains the Matérn minimax rate for every smoothness ν>0, beyond the saturation in Bull (2011), and gives near-optimal squared-exponential rates. The paper is particularly strong in its general architecture: the innovation-norm viewpoint is elegant, the finite-budget bound of Theorem 4.4 is a genuinely useful tool, the constants are explicit and uniform over the RKHS ball, and no free parameters or fitting steps are introduced. The treatment of measurable exact-EI policies (Proposition F.1) and the use of external minimax lower bounds are careful. The Matérn upper bound and the d≥2 SE upper bound do not rely on the questionable step discussed below.

major comments (1)

[§E.5, Proposition E.5; used in Theorem 6.6(2) and Theorem 7.4 (d=1)] The uniform super-exponential power-function bound (E.18) is the only source of the N log(eN) exponent in the d=1 SE upper bound; without it, the best available bound is the exponential (6.10), which is exponentially worse than the minimax lower bound exp(-C N log(eN)) in Theorem 7.4. The proof of (E.18) is a single citation: 'Yarotsky (2013, Theorem 2 and Equation (14)) ... gives (E.21)'. The cited theorem's hypotheses, direction, and domain of validity are not stated. Since (E.21) is then converted to (E.23) by replacing each factor |x̃-x̃_i|² with 4, the reader cannot verify that the external inequality is truly an upper bound valid for arbitrary distinct sites in [-1,1] rather than a lower bound or a bound requiring separated designs or additional smoothness conditions. This is load-bearing: if (E.21) does not hold in exactly the stated form, the d=1 part of the squared-exponential m

minor comments (3)

[Eq. (E.22)] The expansion Fγ(K) = -K log K + O(K) is central to the exponent in (E.23). A short derivation of this expansion would help the reader check the constants and the uniformity in K.
[Theorem 6.6(2)] The statement says '(6.11) holds for every N≥1'. As written this is only true after choosing A'' large enough to absorb a finite initial block; the clarity would be improved by saying 'for all N sufficiently large, with A'' adjusted for finitely many small N'.
[Sections 6 and 7] The symbol N denotes the post-initial budget in Section 6 but the total number of evaluations in the minimax theorems of Section 7. The switch is not announced; please add a sentence in Section 7 to avoid confusion.

Circularity Check

0 steps flagged

No significant circularity: the EI regret bounds are genuine derivations from RKHS geometry and independent external approximation estimates; authors' prior self-citations are explicitly non-load-bearing.

full rationale

The derivation chain is self-contained in the sense required by the circularity check. The upper bounds follow from (i) the exact identity s_n(x)=dist(k(·,x),V_n) (Eq. 2.6), (ii) the one-step regret inequality (3.8) derived from the EI comparison Lemma 3.1, (iii) ranked-innovation bounds via Gram determinants and Kolmogorov widths (Lemmas 4.2, 5.1, 5.2), and (iv) external scattered-data width estimates (Schaback–Wendland 2002; Wendland 2004; Yarotsky 2013). No parameter is fitted to the target rates; the constants q_B, C_B depend only on B, sigma, eta. The authors' own Vazquez–Bect results are explicitly quarantined: 'The consistency and density results discussed in this subsection are recorded for completeness and insight. They are not used in the quantitative bounds that follow' (Section 2.5), and NEB/density is not needed for any of the rate theorems. The minimax lower bounds come from Bull (2011), Kühn (2011), and Xu et al. (2024), i.e., independent external work; they are not derived from EI, so the upper/lower comparison is not a self-comparison. The one genuinely fragile link, Proposition E.5's uniform super-exponential power-function bound imported from Yarotsky (2013), is a load-bearing external correctness risk, not a circular reduction: the paper does not define its conclusion into that citation, and the result is not an EI-specific fitted quantity. Thus central claims have independent content; only minor non-load-bearing self-citations are present.

Axiom & Free-Parameter Ledger

0 free parameters · 17 axioms · 0 invented entities

No free parameters are fitted; the constants (B, σ, η, kernel parameters) are fixed inputs. The central claim rests on standard RKHS/approximation-theory facts plus the explicit well-specified model assumptions; the paper introduces no new entities such as forces, particles, or additional degrees of freedom.

axioms (17)

standard math RKHS theory: continuous PSD kernel k on compact X, reproducing property, restriction/extension theorems (Aronszajn 1950; Wendland 2004 Thms 10.46–10.47)
Used throughout §2 and F.2 to define posterior, power function, and transfer width bounds from cube Q to X.
standard math Gram–Schmidt identity: det K_x = product of squared successive innovation norms
Lemma 5.1; standard linear algebra used to connect separation radii to Gram determinants.
standard math Eckart–Young theorem for rank-i approximation in Hilbert–Schmidt norm
Lemma D.1, used to bound Gram eigenvalues by Kolmogorov widths in Lemma 5.2.
standard math Greedy approximation product inequalities (Binev et al. 2011; DeVore et al. 2013; Wenzel et al. 2023)
Inspiration/input for Lemma 5.2 product bound and for the width-to-separation-radius transfer.
standard math Matérn power-function/fill-distance estimate (Schaback–Wendland 2002, Thm 3.2)
Gives d_m(k_ν,X)=O(m^{-ν/d}), used in Prop 6.2 and Theorem 6.3.
standard math Squared-exponential power-function estimate on cubes (Wendland 2004, Thm 11.22 and Eq. (11.11))
Gives d_m(k,X)=O(exp(-b m^{1/d} log m)), used in Lemma E.4 and Proposition 6.5.
standard math Yarotsky 2013, Thm 2 conditional-variance bound for 1D squared-exponential kernel
Gives limsup log δ_m/(m log m) ≤ -1/2, used in Prop E.5 and the exact d=1 rate (6.11).
standard math Kühn 2011, Thm 3 metric entropy of squared-exponential RKHS ball
Lower bound in Lemma F.2 for the SE minimax comparison.
standard math Xu et al. 2024, Thm 5.1 evaluation lower bound for noiseless optimization
Lower bound on required number of evaluations in Lemma F.3 and Theorem 7.4.
standard math Bull 2011, Thm 1 Matérn minimax lower bound
Lower bound in Theorem 7.3 for the Matérn minimax comparison.
domain assumption Objective lies in RKHS ball: f ∈ H_k, ||f||_{H_k} ≤ B
Eq. (2.2); this is the problem class over which regret is measured.
domain assumption Exact noiseless observations of f at queried points
§2.1; noise is explicitly outside scope.
domain assumption Fixed zero-mean GP prior with covariance σ²k, σ>0 fixed independently of data
Eq. (2.1); Appendix G extends to known prior mean μ0.
domain assumption Weak-EI condition: EI at selected point is at least η times the maximum EI, η∈(0,1]
Eq. (2.21); exact EI corresponds to η=1.
domain assumption Initial design fixed independently of f and of budget; kernel diagonal normalized to ≤1
§2.1 and Eq. (2.3); constants depend on initial design.
domain assumption For minimax comparisons: X has nonempty interior and B>0
Theorems 7.3–7.4; stated in Section 7.
domain assumption Deterministic algorithms with Borel measurable final recommendation; randomized wrapper for lower bounds
Definitions 7.1–7.2; measurable policies are constructed in Proposition F.1.

pith-pipeline@v1.3.0-daily-deepseek · 33993 in / 26764 out tokens · 242539 ms · 2026-08-03T10:52:42.609188+00:00 · methodology

0 comments

read the original abstract

We study the expected improvement (EI) policy for minimizing a deterministic objective function $f$ on a nonempty compact set $\mathcal X \subset\mathbb R^d$. We assume that $f$ belongs to the RKHS $\mathcal H_k$ of a continuous positive-semidefinite kernel $k$ on $\mathcal X$. Function values are observed exactly, and EI is computed from a fixed zero-mean Gaussian-process model with covariance $\sigma^2k$. After an initial design, the policy queries a point whose EI is at least a fixed positive fraction of its maximum. We identify the normalized posterior standard deviation at a candidate point $x$ with the norm of the corresponding innovation in the canonical feature space, namely the component of $k(x,\cdot)$ orthogonal to the span of the preceding evaluation representers. Sequential separation radii bound the ranked innovation norms along arbitrary query sequences. We estimate these radii using Gram determinants and Kolmogorov widths for subspaces of different dimensions, then combine the estimates with a one-step regret inequality to obtain finite-budget bounds for simple regret. After $N$ post-initial queries, simple regret is $O(N^{-\nu/d})$ for isotropic Mat\'ern kernels of smoothness $\nu>0$. For the isotropic squared-exponential kernel, simple regret is $O(\exp[-c_1\min\{N, N^{1/d}\log(eN)\}])$ for some $c_1>0$. With exact EI maximization, it is $O(\exp[-c_2N^{1/d} \log(eN)])$ for some $c_2>0$. For every fixed $B\geq0$, these bounds are uniform over the RKHS ball of radius $B$. If $\mathcal X$ has nonempty interior and $B>0$, then, among deterministic methods whose final recommendation may be any point of $\mathcal X$, the exact EI policy is minimax-rate optimal over the RKHS ball of radius $B$ for Mat\'ern kernels and minimax-rate optimal up to constants in the exponent for squared-exponential kernels.

discussion (0)

Reference graph

Works this paper leans on

13 extracted references · 3 canonical work pages

[1]

Aronszajn

N. Aronszajn. Theory of reproducing kernels.Transactions of the American Mathematical Society, 68(3):337–404, 1950.doi:10.1090/S0002-9947-1950-0051437-7. P. Binev, A. Cohen, W. Dahmen, R. DeVore, G. Petrova, and P. Wojtaszczyk. Convergence rates for greedy algorithms in reduced basis methods.SIAM Journal on Mathematical Analysis, 43(3):1457–1472, 2011.doi...

arXiv 1950
[13]

URL https://arxiv.org/abs/2501.09262v2. H. Wendland.Scattered Data Approximation, volume 17 ofCambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, Cambridge,

Pith/arXiv arXiv
[1936]

doi:10.2307/1968691. T. K¨ uhn. Covering numbers of Gaussian reproducing kernel Hilbert spaces.Journal of Complexity, 27(5):489–499, 2011.doi:10.1016/j.jco.2011.01.005. H. J. Kushner. A new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise.Journal of Basic Engineering, 86(1):97–106,

work page doi:10.2307/1968691 2011
[1962]

Moˇ ckus

J. Moˇ ckus. On Bayesian methods for seeking the extremum. In G. I. Marchuk, editor, Optimization Techniques: IFIP Technical Conference, Novosibirsk, July 1–7, 1974, volume 27 ofLecture Notes in Computer Science, pages 400–404. Springer, Berlin, Heidelberg, 1975.doi:10.1007/3-540-07165-2_55. J. Moˇ ckus, V. Tiesis, and A.ˇZilinskas. The application of Bay...

doi:10.1007/3-540-07165-2_55 1974
[1964]

doi:10.1115/1.3653121. Y. Li and J. W. Siegel. Entropy-based convergence rates of greedy algorithms. Mathematical Models and Methods in Applied Sciences, 34(5):779–802,

doi:10.1115/1.3653121
[1978]

Santin, T

G. Santin, T. Wenzel, and B. Haasdonk. On the optimality of target-data-dependent kernel greedy interpolation in Sobolev reproducing kernel Hilbert spaces.SIAM Journal on Numerical Analysis, 62(5):2249–2275, 2024.doi:10.1137/23M1587956. R. Schaback and H. Wendland. Inverse and saturation theorems for radial basis function interpolation.Mathematics of Comp...

doi:10.1137/23m1587956 2024
[1998]

doi:10.1023/A:1008306431147. A. N. Kolmogorov. ¨Uber die beste Ann¨ aherung von Funktionen einer gegebenen Funktionenklasse.Annals of Mathematics, 37(1):107–110,

doi:10.1023/a:1008306431147
[2002]

doi:10.1090/S0025-5718-01-01383-7. H. Tran-The, S. Gupta, S. Rana, and S. Venkatesh. Regret bounds for expected improvement algorithms in Gaussian process bandit optimization. InProceedings of the 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 8715–8737. PMLR,

work page doi:10.1090/s0025-5718-01-01383-7
[2004]

doi:10.1017/CBO9780511617539. T. Wenzel, G. Santin, and B. Haasdonk. Analysis of target data-dependent greedy kernel algorithms: convergence rates forf-,f·P-, andf /P-greedy.Constructive Approximation, 57(1):45–74, 2023.doi:10.1007/s00365-022-09592-3. W. Xu, Y. Jiang, E. T. Maddalena, and C. N. Jones. Lower bounds on the noiseless worst-case complexity of...

doi:10.1017/cbo9780511617539 2023
[2013]

doi:10.1007/s00365-013-9186-2. C. Eckart and G. Young. The approximation of one matrix by another of lower rank. Psychometrika, 1(3):211–218, 1936.doi:10.1007/BF02288367. R. Garnett.Bayesian Optimization. Cambridge University Press, Cambridge,

doi:10.1007/s00365-013-9186-2 1936
[2023]

ISBN 978-1-108-42578-0.doi:10.1017/9781108348973. S. Iwazaki. Gaussian process upper confidence bound achieves nearly-optimal regret in noise-free Gaussian process bandits. InAdvances in Neural Information Processing Systems, volume 38, pages 65863–65886. Curran Associates, Inc.,

doi:10.1017/9781108348973
[2024]

doi:10.1142/S0218202524500143. G. Matheron and P. Formery. Recherche d’optimum dans la reconnaissance et la mise en exploitation des gisements miniers. Note g´ eostatistique 41, Bureau de recherches g´ eologiques et mini` eres, Nov

work page doi:10.1142/s0218202524500143
[2025]

URL https://proceedings.neurips.cc/paper_files/paper/2025/file/ 5f1eee2509599faeeb3570a887016a64-Paper-Conference.pdf. 41 D. R. Jones, M. Schonlau, and W. J. Welch. Efficient global optimization of expensive black-box functions.Journal of Global Optimization, 13(4):455–492,

2025

[1] [1]

Aronszajn

N. Aronszajn. Theory of reproducing kernels.Transactions of the American Mathematical Society, 68(3):337–404, 1950.doi:10.1090/S0002-9947-1950-0051437-7. P. Binev, A. Cohen, W. Dahmen, R. DeVore, G. Petrova, and P. Wojtaszczyk. Convergence rates for greedy algorithms in reduced basis methods.SIAM Journal on Mathematical Analysis, 43(3):1457–1472, 2011.doi...

arXiv 1950

[2] [13]

URL https://arxiv.org/abs/2501.09262v2. H. Wendland.Scattered Data Approximation, volume 17 ofCambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, Cambridge,

Pith/arXiv arXiv

[3] [1936]

doi:10.2307/1968691. T. K¨ uhn. Covering numbers of Gaussian reproducing kernel Hilbert spaces.Journal of Complexity, 27(5):489–499, 2011.doi:10.1016/j.jco.2011.01.005. H. J. Kushner. A new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise.Journal of Basic Engineering, 86(1):97–106,

work page doi:10.2307/1968691 2011

[4] [1962]

Moˇ ckus

J. Moˇ ckus. On Bayesian methods for seeking the extremum. In G. I. Marchuk, editor, Optimization Techniques: IFIP Technical Conference, Novosibirsk, July 1–7, 1974, volume 27 ofLecture Notes in Computer Science, pages 400–404. Springer, Berlin, Heidelberg, 1975.doi:10.1007/3-540-07165-2_55. J. Moˇ ckus, V. Tiesis, and A.ˇZilinskas. The application of Bay...

doi:10.1007/3-540-07165-2_55 1974

[5] [1964]

doi:10.1115/1.3653121. Y. Li and J. W. Siegel. Entropy-based convergence rates of greedy algorithms. Mathematical Models and Methods in Applied Sciences, 34(5):779–802,

doi:10.1115/1.3653121

[6] [1978]

Santin, T

G. Santin, T. Wenzel, and B. Haasdonk. On the optimality of target-data-dependent kernel greedy interpolation in Sobolev reproducing kernel Hilbert spaces.SIAM Journal on Numerical Analysis, 62(5):2249–2275, 2024.doi:10.1137/23M1587956. R. Schaback and H. Wendland. Inverse and saturation theorems for radial basis function interpolation.Mathematics of Comp...

doi:10.1137/23m1587956 2024

[7] [1998]

doi:10.1023/A:1008306431147. A. N. Kolmogorov. ¨Uber die beste Ann¨ aherung von Funktionen einer gegebenen Funktionenklasse.Annals of Mathematics, 37(1):107–110,

doi:10.1023/a:1008306431147

[8] [2002]

doi:10.1090/S0025-5718-01-01383-7. H. Tran-The, S. Gupta, S. Rana, and S. Venkatesh. Regret bounds for expected improvement algorithms in Gaussian process bandit optimization. InProceedings of the 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 8715–8737. PMLR,

work page doi:10.1090/s0025-5718-01-01383-7

[9] [2004]

doi:10.1017/CBO9780511617539. T. Wenzel, G. Santin, and B. Haasdonk. Analysis of target data-dependent greedy kernel algorithms: convergence rates forf-,f·P-, andf /P-greedy.Constructive Approximation, 57(1):45–74, 2023.doi:10.1007/s00365-022-09592-3. W. Xu, Y. Jiang, E. T. Maddalena, and C. N. Jones. Lower bounds on the noiseless worst-case complexity of...

doi:10.1017/cbo9780511617539 2023

[10] [2013]

doi:10.1007/s00365-013-9186-2. C. Eckart and G. Young. The approximation of one matrix by another of lower rank. Psychometrika, 1(3):211–218, 1936.doi:10.1007/BF02288367. R. Garnett.Bayesian Optimization. Cambridge University Press, Cambridge,

doi:10.1007/s00365-013-9186-2 1936

[11] [2023]

ISBN 978-1-108-42578-0.doi:10.1017/9781108348973. S. Iwazaki. Gaussian process upper confidence bound achieves nearly-optimal regret in noise-free Gaussian process bandits. InAdvances in Neural Information Processing Systems, volume 38, pages 65863–65886. Curran Associates, Inc.,

doi:10.1017/9781108348973

[12] [2024]

doi:10.1142/S0218202524500143. G. Matheron and P. Formery. Recherche d’optimum dans la reconnaissance et la mise en exploitation des gisements miniers. Note g´ eostatistique 41, Bureau de recherches g´ eologiques et mini` eres, Nov

work page doi:10.1142/s0218202524500143

[13] [2025]

URL https://proceedings.neurips.cc/paper_files/paper/2025/file/ 5f1eee2509599faeeb3570a887016a64-Paper-Conference.pdf. 41 D. R. Jones, M. Schonlau, and W. J. Welch. Efficient global optimization of expensive black-box functions.Journal of Global Optimization, 13(4):455–492,

2025