Pith. sign in

REVIEW 2 major objections 5 minor 2 cited by

Bayesian Optimization with Inexact Acquisition: Is Random Grid Search Sufficient?

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read A fresh random grid per round can replace exact acquisition in Bayesian optimization without losing sublinear regret.

desk verdict First real regret bounds for inexact acquisition in BO, with a genuine random-grid result, but a missing proof for the GP-TS theorem and a hidden 1/δ in the discretization bound need fixing. read the letter →

arxiv 2506.11831 v1 pith:7QRGBQS5 submitted 2025-06-13 stat.ML cs.LGstat.ME

Hwanwoo Kim , Chong Liu , Yuxin Chen This is my paper · ORCID
classification stat.MLcs.LGstat.ME MSC 62L0560G1590C26
keywords BayesianoptimizationGaussianprocessbanditsinexactacquisitionfunctionmaximizationrandomgridsearchcumulativeregretThompsonsamplingGP-UCBfilldistance
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

Bayesian optimization normally assumes the acquisition function is maximized exactly at every round, but in practice that inner maximization is solved approximately by grid search or multi-start heuristics. The paper's central claim is that this inexactness is harmless under a quantifiable budget: if the worst-case accumulated inaccuracy $M_T = \sum_{t=1}^T (1-\tilde\eta_t)$ grows slowly, both GP-UCB and GP-TS still achieve sublinear cumulative regret. It then shows that a particularly crude solver, a fresh uniform random grid of size $\Theta(t)$ at round $t$, meets that budget automatically, giving $R_T = O(\gamma_T \sqrt{T}) + \widetilde{O}(T^{(d-1)/d})$ for GP-UCB and an analogous GP-TS bound with an extra $\sqrt{\log T}$ factor. This relaxes the exponentially large $t^{2d}$ grid that prior theory required for Thompson sampling, so practitioners can use a simple random grid without losing convergence guarantees. The numerical experiments show the uniform random grid keeping pace with L-BFGS-B, Nelder-Mead, and conjugate-gradient solvers at a fraction of the runtime.

What carries the argument

The argument runs on three pieces. (1) Worst-case accumulated inaccuracy $M_T = \sum_t (1-\tilde\eta_t)$ converts an imperfect acquisition maximizer into an additive regret term, because the suboptimality gap at round $t$ is bounded by $(1-\eta_t)\alpha_t^*$ plus the usual confidence-region tail. (2) For random grids, the fill distance $h_t$ measures how far an arbitrary point can be from the nearest grid point; Lemma 18 turns the expectation bound of Helin et al. into a high-probability bound on $\sum_t h_t$, and the Lipschitz property of the objective turns $h_t$ into discretization regret. (3) The standard GP-UCB and GP-TS confidence bounds plus the sum-of-posterior-variances bound $\sum_t \sigma_{t-1}(x_t) \le \sqrt{4(T+2)\gamma_T}$ control the statistical part of the regret, with $\gamma_T$ denoting the maximum information gain of the kernel.

What would settle it

Run random-grid GP-UCB on a smooth two-dimensional objective with a fixed grid of 100 points reused every round instead of a fresh $\Theta(t)$ grid: after the first round the fill distance is bounded below by a positive constant, so the discretization term in the proof contributes $\Omega(T)$ and cumulative regret should fail to be sublinear, directly testing Assumption 5.

Watch

Extended reading notes

Core claim

The discovery is that the regret of Bayesian optimization degrades gracefully with the quality of the acquisition maximizer, not abruptly. Defining $\eta_t = \alpha_t(x_t)/\alpha_t^*$ as the ratio of the chosen point's acquisition value to the true maximum, and $M_T$ as the sum of worst-case deficits, Theorem 3 gives $R_T = O(\gamma_T \sqrt{T} + M_T \sqrt{\gamma_T})$ for inexact GP-UCB, and Theorem 4 gives the GP-TS analogue with a $\sqrt{\log T}$ factor; when $M_T \sqrt{\gamma_T}/T \to 0$, the average regret vanishes. For a fresh uniform grid with $|X_t| = \Theta(t)$ points, the fill distance $h_t = \sup_{x\in X} \inf_{x_i \in X_t} \|x-x_i\|$ concentrates so that $\sum_{t=1}^T h_t = O(T^{(d-1)/d + \xi})$, which makes the accumulated inaccuracy term sublinear and yields Theorems 7 and 8. In the author's framing, random grid search is not merely a practical hack but a theoretically sufficient acquisition solver.

Load-bearing premise

The random-grid theorem depends on a new independent uniform grid every round; if a solver reuses one fixed grid or samples from a distribution with zero density near the optimum, the discretization error stops decaying and the sublinear regret proof no longer applies.

Editorial extensions

If this is right

  • If the accumulated inaccuracy $M_T$ is sublinear, inexact GP-UCB converges: $R_T/T \to 0$ whenever $M_T \sqrt{\gamma_T} = o(T)$, and GP-TS has the same behavior with an extra $\sqrt{\log T}$ factor.
  • A fresh uniform grid of $\Theta(t)$ points per round makes the inaccuracy term small enough that $R_T = O(\gamma_T \sqrt{T}) + \widetilde{O}(T^{(d-1)/d})$; for squared-exponential kernels this is sublinear because $\gamma_T$ grows only logarithmically.
  • The exponential $t^{2d}$ grid-size requirement previously used to analyze Thompson sampling is relaxed to linear growth, closing part of the gap between the theory and common practice.
  • The analysis is not tied to a particular solver or kernel family: any acquisition function with the same confidence-bound structure works, and any kernel with a known information-gain growth rate yields the corresponding regret bound.
  • Tuning the grid size trades computation against regret: $|X_t| = \Theta(t^2)$ improves the discretization term to $\widetilde{O}(T^{(d-2)/d})$, and $|X_t| = \Theta(t^d)$ brings it down to roughly $O(\log T)$.

Reading between the lines

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

  • Editorial inference: the proof structure suggests the grid need only be drawn from any density that is strictly positive on the search space, so an adaptive density concentrated near promising regions could reduce constants while preserving the theorem, although the paper does not analyze this.
  • Editorial inference: the refreshment is doing the load-bearing work. The paper's fixed-grid ablation is empirical only, and the theory's discretization term relies on a fresh grid each round; reused candidate sets should be expected to lose the decaying fill-distance term and move regret toward linear.
  • Editorial inference: deterministic low-discrepancy grids would likely achieve the same or better fill-distance decay with fewer points than uniform random grids, making a direct comparison between fresh uniform grids and quasi-random candidate sets a natural testable extension.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. This paper studies Bayesian optimization when acquisition functions are maximized inexactly. The authors introduce a per-round accuracy ratio eta_t and a worst-case accumulated inaccuracy M_T = sum_t (1 - eta~_t), and prove regret bounds for inexact GP-UCB (Theorem 3) and for a GP-TS variant with enlarged variance (Theorem 4). They then specialize to random grid search: under Assumption 5, where a fresh uniform grid of size Theta(t) is drawn at each round, Theorems 7 and 8 claim cumulative regret O(gamma_T sqrt T) + Otilde(T^{(d-1)/d}) for grid-based GP-UCB and GP-TS, respectively. Numerical experiments compare uniform random grids with quasi-Newton and Nelder-Mead solvers on synthetic benchmarks and an AutoML task, reporting competitive regret and lower runtime.

Significance. The central message, that inexact acquisition maximization can be tolerated when accumulated inaccuracy grows slowly, is valuable and is convincingly demonstrated for GP-UCB in Theorem 3; that proof is a clean extension of the Chowdhury-Gopalan analysis. The random-grid results, if restated with correct high-probability constants, would substantially strengthen the practical case for grid-based acquisition optimization, relaxing the t^{2d} grid-size requirement of Chowdhury and Gopalan to a linear-size fresh grid, and the authors provide code for reproducibility. However, the high-probability fill-distance bound used by Theorems 7 and 8 carries a hidden 1/delta factor, and the proof of Theorem 4 is explicitly omitted, so the full set of claimed results is not yet verified as stated.

major comments (2)
  1. [Appendix A.1, Lemma 18; Theorems 7 and 8] Lemma 18 proves by Markov's inequality that, with probability at least 1-delta, sum_{t=1}^T h_t <= sum_{t=1}^{t*} h_t + C T^{(d-1)/d + xi} / delta. The subsequent proofs of Theorems 23 and 36 substitute this as O(T^{(d-1)/d + xi}) with probability 1-delta/2, which is valid only if delta is a fixed constant independent of T. As written, Theorems 7 and 8 state the bound for arbitrary delta in (0,1), and the paper's stated convention is that O hides only universal constants; for delta = 1/T the discretization term becomes at least T^{1 + (d-1)/d + xi}, which is not sublinear for d >= 2. Please either restrict delta to a fixed constant and state this explicitly, or replace the Markov bound by a concentration inequality for the fill distance that yields a polylogarithmic or constant dependence on delta.
  2. [Appendix A.2, Theorem 22 (main-text Theorem 4)] The proof of Theorem 4, the inexact GP-TS bound with enlarged variance s_{t-1}^2(x) = (beta_t sigma_{t-1}(x) + v~_t)^2, is explicitly omitted: the appendix states 'We omit the proof ... as it substantially overlaps with the approach taken in [8] with a variance factor adjustment.' This is a load-bearing result because the enlarged variance is a new algorithmic element and the time-varying factor v~_t depending on eta~_t must be checked through the Chowdhury-Gopalan martingale argument, including the filtration, the constant-shift Lemma 20, and the final M_T dependence. Please provide a complete proof or a precise reduction to [8] that makes the M_T term explicit.
minor comments (5)
  1. [Sections 2.1 and 3.1] The definition of eta_t = alpha_t(x_t) / alpha*_t assumes alpha_t is nonnegative, but the main-text theorems do not state that the acquisition function has been shifted by the constant supplied in Lemmas 19 and 20; please make this convention explicit so the ratio and the resulting M_T are unambiguous.
  2. [Section 3.2, Theorem 4 vs. Appendix A.2, Lemma 20] The notation for the enlarged variance is inconsistent: the main text defines v~_t = (1/eta~_t - 1)B, while Lemma 20 uses v_t = (1/eta_t - 1)B and writes s_{t-1} = beta_t sigma_{t-1} + v_t; please unify the notation and use the worst-case quantity eta~_t.
  3. [Appendix A.4, Lemma 32 proof] There is a typo in the first inequality of the proof: 'sup_{x in cX} Delta_t(x)' should be 'sup_{x in X} Delta_t(x)', and the probability term P[E_f^t(t)^c | H_{t-1}] should be written with the filtration F_{t-1} defined in Definition 24.
  4. [Algorithm 2] The grid size expression '(2BLbdt2)d' appears garbled; please format it correctly and define the constants L, b, and d before its use.
  5. [Section 5, Figures 1 and 3] The cumulative regret plots report only pointwise means over 20 seeds; adding error bars or quantile bands would make the empirical comparison across solvers easier to assess.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the regret bounds are derived from external lemmas and input measures, not from the conclusions they claim.

full rationale

The paper's load-bearing derivation chain is not circular. The measure M_T (worst-case accumulated inaccuracy) is an input defined from the solver's accuracy ratios and is not fitted to regret data; Theorems 3 and 4 state regret bounds as functions of M_T rather than deriving M_T from the regret bound. The random-grid results in Theorems 7 and 8 rest on Assumption 5 (fresh independent uniform grids) and on Lemma 17/18, which is attributed to Helin et al. [18], an external fill-distance bound. The discretization term ~O(T^{(d-1)/d}) is obtained by applying Markov's inequality to that external expectation bound, not by assuming the theorem's conclusion. The paper's reliance on Chowdhury and Gopalan [8] for GP-UCB/GP-TS concentration and information-gain lemmas is standard external material, not self-citation. No parameter is fit to a subset of the regret data and then renamed a prediction, and no uniqueness theorem or ansatz is imported from the present authors' prior work. The fixed-grid experiment in Appendix B.2.1 is explicitly empirical, which may weaken the practical scope of the theoretical claim but does not make the derivation circular. The possible hidden 1/δ factor in Lemma 18 is a correctness or tightness concern about high-probability bounds as δ→0, not a circularity concern, because the disputed term still comes from an independent external source rather than from the claim being proved.

Assumptions & free parameters 0 free parameters · 9 assumptions · 1 invented entities

The theoretical claims rest on standard GP bandit lemmas (concentration, RKHS norm bounds, information gain bounds) and a known geometric fill-distance bound for uniform random points. No free parameters are fitted to data in the theory; the only new construct is the inaccuracy measure M_T, which is a definition rather than a postulated entity. Experimental constants (e.g., grid size 100t) are not part of the central claim.

assumptions (9)
  • domain assumption Kernel satisfies k(x,x) <= 1 for all x (Assumption 1 / 12).
    Used to bound posterior variances and alpha*_t in the proofs of Theorems 3 and 7.
  • domain assumption Kernel is squared-exponential or Matérn with smoothness nu >= 2 (Assumption 2 / 13).
    Establishes the maximum information gain growth rates gamma_T used in all regret bounds.
  • domain assumption Objective f lies in the RKHS H_k with ||f||_Hk <= B (Section 2.1).
    Provides the concentration inequality for f and bounds on sup|f| used throughout the proofs.
  • ad hoc to paper A fresh grid of t independent uniform samples is drawn at each iteration (Assumption 5 / 14).
    This sampling scheme is the paper's proposed algorithm; the T^((d-1)/d) term relies on the fill-distance decay of fresh uniform points.
  • standard math Concentration inequality |f(x)-mu_{t-1}(x)| <= beta_t sigma_{t-1}(x) (Lemma 15, from Chowdhury and Gopalan [8]).
    Workhorse for all regret arguments; cited as Theorem 2 of [8].
  • standard math Sum of posterior standard deviations satisfies sum sigma_{t-1}(x_t) <= sqrt(4(T+2)gamma_T) (Lemma 16, from [8]).
    Used to bound exploration terms in every theorem.
  • standard math Expected fill distance of t uniform random points in a hyperrectangle is O(t^{-1/d+xi}) for any xi>0 (Lemma 17, from Helin et al. [18]).
    Provides the discretization-error rate that yields the T^((d-1)/d) term in Theorems 7-8.
  • standard math f is Lipschitz with a constant depending on B and the kernel (Lemma 1 of de Freitas et al. [11]).
    Used to bound f(x*) - f([x*]_t) by the fill distance in the random-grid proofs.
  • standard math For GP-TS, posterior sample concentration and anti-concentration lemmas from [8] (Lemmas 25, 30, 31).
    Used in the random-grid GP-TS proof to control the probability that the selected point is not saturated.
invented entities (1)
  • Worst-case accumulated inaccuracy M_T = sum_{t=1}^T (1 - eta~_t)
    purpose: Quantifies the total inexactness of acquisition maximization across T rounds.
    A defined summary statistic, not a physical entity. It cannot be directly measured without knowing the true acquisition maximum alpha*_t, so it carries no independent falsifiable handle outside the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Bayesian Optimization with Inexact Acquisition: Is Random Grid Search Sufficient?." pith.science (2026). https://pith.science/paper/7QRGBQS5

@misc{pith2026250611831,
  author       = {Pith},
  title        = {Pith review of: Bayesian Optimization with Inexact Acquisition: Is Random Grid Search Sufficient?},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7QRGBQS5}},
  note         = {Machine review of arXiv:2506.11831}
}
read the original abstract

Bayesian optimization (BO) is a widely used iterative algorithm for optimizing black-box functions. Each iteration requires maximizing an acquisition function, such as the upper confidence bound (UCB) or a sample path from the Gaussian process (GP) posterior, as in Thompson sampling (TS). However, finding an exact solution to these maximization problems is often intractable and computationally expensive. Reflecting such realistic situations, in this paper, we delve into the effect of inexact maximizers of the acquisition functions. Defining a measure of inaccuracy in acquisition solutions, we establish cumulative regret bounds for both GP-UCB and GP-TS without requiring exact solutions of acquisition function maximization. Our results show that under appropriate conditions on accumulated inaccuracy, inexact BO algorithms can still achieve sublinear cumulative regret. Motivated by such findings, we provide both theoretical justification and numerical validation for random grid search as an effective and computationally efficient acquisition function solver.

Figures

Figures reproduced from arXiv: 2506.11831 by the authors.

Figure 1
Figure 1. Cumulative regret comparison between acquisition function solvers. [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Computational time comparison between acquisi [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Cumulative regret (upper) and average compu [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Performances with uniform random and uniform fixed grid sizes. [PITH_FULL_IMAGE:figures/full_fig_p020_4.png]
Figure 5
Figure 5. Figure 5: Average computational time of different acquisition optimization methods with a smaller initial design points [PITH_FULL_IMAGE:figures/full_fig_p020_5.png]
Figure 6
Figure 6. Figure 6: Cumulative regret of different acquisition optimization methods with a smaller initial design points ( [PITH_FULL_IMAGE:figures/full_fig_p021_6.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

  1. Optimal Transport-based Permutation-Invariant Bayesian Optimization of Offshore Wind Farm Layouts

    cs.AI 2026-03 conditional novelty 6.0 of 10

    Optimal-transport flows turn permutation-invariant layout optimization into a standard BO problem, yielding higher AEP and lower runtime than vanilla BO on a five-turbine wind-farm surrogate.

  2. Scalably computing metric magnitude

    math.NA 2026-07 conditional novelty 5.0 of 10

    Hierarchical low-rank solvers beat dense and sparsified approaches for metric magnitude solves in experiments up to n=30,000, with a projected path to n≈10^5 via a containerized STRUMPACK/MPI pipeline.

Reference graph

Works this paper leans on

56 extracted references · 53 canonical work pages · cited by 2 Pith papers

  1. [8]

    On ker- nelized multi-armed bandits

    Sayak Ray Chowdhury and Aditya Gopalan. On ker- nelized multi-armed bandits. In International Confer- ence on Machine Learning, pages 844–853, 2017

    work page 2017

  2. [1]

    Improved algorithms for linear stochastic bandits

    Yasin Abbasi-yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Process- ing Systems 24, 2011

    work page 2011

  3. [2]

    Thompson sam- pling for contextual bandits with linear payoffs

    Shipra Agrawal and Navin Goyal. Thompson sam- pling for contextual bandits with linear payoffs. In International Conference on Machine Learning, 2013

    work page 2013

  4. [3]

    Theory of reproducing kernels

    Nachman Aronszajn. Theory of reproducing kernels. Transactions of the American mathematical society , 68(3):337–404, 1950

    work page 1950

  5. [4]

    Batched bayesian optimiza- tion for drug design in noisy environments

    Hugo Bellamy, Abbi Abdel Rehim, Oghenejokpeme I Orhobor, and Ross King. Batched bayesian optimiza- tion for drug design in noisy environments. Journal of Chemical Information and Modeling, 62(17):3970– 3981, 2022

    work page 2022

  6. [5]

    Random search for hyper-parameter optimization

    James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of machine learning research, 13(2), 2012

    work page 2012

  7. [6]

    Repro- ducing Kernel Hilbert Spaces in Probability and Statis- tics

    Alain Berlinet and Christine Thomas-Agnan. Repro- ducing Kernel Hilbert Spaces in Probability and Statis- tics. Springer Science & Business Media, 2011

    work page 2011

  8. [7]

    Misspeci- fied gaussian process bandit optimization

    Ilija Bogunovic and Andreas Krause. Misspeci- fied gaussian process bandit optimization. Advances in Neural Information Processing Systems, 34:3004– 3015, 2021

    work page 2021

Show all 56 references
  1. [9]

    Bayesian optimization in drug discovery

    Lionel Colliandre and Christophe Muller. Bayesian optimization in drug discovery. In High Performance Computing for Drug Discovery and Biomedicine , pages 101–136. Springer, 2023

    2023

  2. [10]

    Sample-then-optimize batch neural Thompson sampling

    Zhongxiang Dai, Yao Shu, Bryan Kian Hsiang Low, and Patrick Jaillet. Sample-then-optimize batch neural Thompson sampling. In Advances in Neural Informa- tion Processing Systems 35, 2022

    2022

  3. [11]

    Re- gret bounds for deterministic gaussian process bandits

    Nando de Freitas, Alex Smola, and Masrour Zoghi. Re- gret bounds for deterministic gaussian process bandits. arXiv preprint arXiv:1203.2177, 2012

    2012 arXiv

  4. [12]

    Adapting to misspecification in con- textual bandits

    Dylan J Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert. Adapting to misspecification in con- textual bandits. Advances in Neural Information Pro- cessing Systems, 33:11478–11489, 2020

    2020

  5. [13]

    The knowledge-gradient policy for correlated normal be- liefs

    Peter Frazier, Warren Powell, and Savas Dayanik. The knowledge-gradient policy for correlated normal be- liefs. INFORMS Journal on Computing, 21(4):599– 613, 2009

    2009

  6. [14]

    A tutorial on bayesian optimization

    Peter I Frazier. A tutorial on bayesian optimization. arXiv preprint arXiv:1807.02811, 2018

    2018 arXiv

  7. [15]

    Bayesian optimization for materials design

    Peter I Frazier and Jialei Wang. Bayesian optimization for materials design. In Information science for ma- terials discovery and design, pages 45–75. Springer, 2016

    2016

  8. [16]

    Surrogates: Gaussian process modeling, design, and optimization for the applied sciences

    Robert B Gramacy. Surrogates: Gaussian process modeling, design, and optimization for the applied sciences. Chapman and Hall/CRC, 2020

    2020

  9. [17]

    Triangulation candidates for bayesian optimization

    Robert B Gramacy, Annie Sauer, and Nathan Wycoff. Triangulation candidates for bayesian optimization. Advances in Neural Information Processing Systems, 35:35933–35945, 2022

    2022

  10. [18]

    Introduction to gaus- sian process regression in bayesian inverse problems, with new results on experimental design for weighted error measures

    Tapio Helin, Andrew M Stuart, Aretha L Teckentrup, and Konstantinos C Zygalakis. Introduction to gaus- sian process regression in bayesian inverse problems, with new results on experimental design for weighted error measures. In International Conference on Monte Carlo and Quas...

    2022

  11. [19]

    Improved regret analysis in gaussian process bandits: Optimality for noiseless reward, rkhs norm, and non-stationary vari- ance

    Shogo Iwazaki and Shion Takeno. Improved regret analysis in gaussian process bandits: Optimality for noiseless reward, rkhs norm, and non-stationary vari- ance. arXiv preprint arXiv:2502.06363, 2025

    2025 arXiv

  12. [20]

    Efficient global optimization of expensive black-box functions

    Donald R Jones, Matthias Schonlau, and William J Welch. Efficient global optimization of expensive black-box functions. Journal of Global Optimization, 13(4):455–492, 1998

    1998

  13. [21]

    Playing games with approximation algorithms

    Sham M Kakade, Adam Tauman Kalai, and Katrina Ligett. Playing games with approximation algorithms. In Proceedings of the thirty-ninth annual ACM sympo- sium on Theory of computing, pages 546–555, 2007

    2007

  14. [22]

    High dimensional bayesian optimisation and bandits via additive models

    Kirthevasan Kandasamy, Jeff Schneider, and Barnabás Póczos. High dimensional bayesian optimisation and bandits via additive models. In International Confer- ence on Machine Learning, 2015

    2015

  15. [23]

    Parallelised bayesian optimisation via thompson sampling

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

    2018

  16. [24]

    Neu- ral architecture search with bayesian optimisation and optimal transport

    Kirthevasan Kandasamy, Willie Neiswanger, Jeff Schneider, Barnabas Poczos, and Eric P Xing. Neu- ral architecture search with bayesian optimisation and optimal transport. In Advances in neural information processing systems 31, 2018

    2018

  17. [25]

    Collins, Jeff Schneider, Barnabas Poczos, and Eric P

    Kirthevasan Kandasamy, Karun Raju Vysyaraju, Willie Neiswanger, Biswajit Paria, Christopher R. Collins, Jeff Schneider, Barnabas Poczos, and Eric P. Xing. Tuning hyperparameters without grad students: Scalable and robust bayesian optimisation with drag- onfly. Journal of Machi...

    2020

  18. [26]

    The hardness analysis of thompson sampling for com- binatorial semi-bandits with greedy oracle

    Fang Kong, Yueran Yang, Wei Chen, and Shuai Li. The hardness analysis of thompson sampling for com- binatorial semi-bandits with greedy oracle. Advances in Neural Information Processing Systems, 34:26701– 26713, 2021

    2021

  19. [27]

    Chembo: Bayesian optimization of small organic molecules with synthesizable recom- mendations

    Ksenia Korovina, Sailun Xu, Kirthevasan Kandasamy, Willie Neiswanger, Barnabas Poczos, Jeff Schneider, and Eric Xing. Chembo: Bayesian optimization of small organic molecules with synthesizable recom- mendations. In International Conference on Artificial Intelligence and Stati...

    2020

  20. [28]

    A new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise

    Harold 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, 1964

    1964

  21. [29]

    Bandit Algo- rithms

    Tor Lattimore and Csaba Szepesvári. Bandit Algo- rithms. Cambridge University Press, 2020

    2020

  22. [30]

    Learning with good feature representations in bandits and in rl with a generative model

    Tor Lattimore, Csaba Szepesvari, and Gellert Weisz. Learning with good feature representations in bandits and in rl with a generative model. In International Conference on Machine Learning, pages 5662–5670, 2020

    2020

  23. [31]

    Bayesian optimization with adap- tive surrogate models for automated experimental de- sign

    Bowen Lei, Tanner Quinn Kirk, Anirban Bhattacharya, Debdeep Pati, Xiaoning Qian, Raymundo Arroyave, and Bani K Mallick. Bayesian optimization with adap- tive surrogate models for automated experimental de- sign. Npj Computational Materials, 7(1):194, 2021

    2021

  24. [32]

    Ensemble sam- pling

    Xiuyuan Lu and Benjamin Van Roy. Ensemble sam- pling. Advances in neural information processing systems, 30, 2017

    2017

  25. [33]

    When combinatorial thompson sam- pling meets approximation regret

    Pierre Perrault. When combinatorial thompson sam- pling meets approximation regret. Advances in Neu- ral Information Processing Systems, 35:17639–17651, 2022

    2022

  26. [34]

    Thompson sampling and approximate inference

    My Phan, Yasin Abbasi Yadkori, and Justin Domke. Thompson sampling and approximate inference. Ad- vances in Neural Information Processing Systems, 32, 2019

    2019

  27. [35]

    Bayesian optimization with application to computer experiments

    Tony Pourmohamad and Herbert KH Lee. Bayesian optimization with application to computer experiments. Springer, 2021

    2021

  28. [36]

    Learning policies for contex- tual submodular prediction

    Stephane Ross, Jiaji Zhou, Yisong Yue, Debadeepta Dey, and Drew Bagnell. Learning policies for contex- tual submodular prediction. In International Confer- ence on Machine Learning, pages 1364–1372. PMLR, 2013

    2013

  29. [37]

    Learning to optimize via posterior sampling

    Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Op- erations Research, 39(4):1221–1243, 2014

    2014

  30. [38]

    Gaussian process optimization in the bandit setting: no regret and experimental design

    Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: no regret and experimental design. In International Conference on Machine Learning, 2010

    2010

  31. [39]

    On the likelihood that one unknown probability exceeds another in view of the evidence of two samples

    William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285– 294, 1933

    1933

  32. [40]

    Bayesian optimization is superior to random search for machine learning hyperparameter tuning: Analy- sis of the black-box optimization challenge 2020

    Ryan Turner, David Eriksson, Michael McCourt, Juha Kiili, Eero Laaksonen, Zhen Xu, and Isabelle Guyon. Bayesian optimization is superior to random search for machine learning hyperparameter tuning: Analy- sis of the black-box optimization challenge 2020. In NeurIPS 2020 Compet...

    2020

  33. [41]

    On information gain and regret bounds in gaussian pro- cess bandits

    Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in gaussian pro- cess bandits. In International Conference on Artificial Intelligence and Statistics, pages 82–90. PMLR, 2021

    2021

  34. [42]

    Scalable thompson sampling using sparse gaussian process models

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

    2021

  35. [43]

    Improved convergence rates for sparse approximation methods in kernel-based learn- ing

    Sattar Vakili, Jonathan Scarlett, Da-shan Shiu, and Alberto Bernacchia. Improved convergence rates for sparse approximation methods in kernel-based learn- ing. In International Conference on Machine Learning, pages 21960–21983. PMLR, 2022

    2022

  36. [44]

    Spline Models for Observational Data

    Grace Wahba. Spline Models for Observational Data. SIAM, 1990

    1990

  37. [45]

    Thompson sampling for combinatorial semi-bandits

    Siwei Wang and Wei Chen. Thompson sampling for combinatorial semi-bandits. In International Confer- ence on Machine Learning, pages 5114–5122. PMLR, 2018

    2018

  38. [46]

    Max-value entropy search for efficient bayesian optimization

    Zi Wang and Stefanie Jegelka. Max-value entropy search for efficient bayesian optimization. In Interna- tional conference on machine learning, pages 3627–

  39. [47]

    Ba- nanas: Bayesian optimization with neural architectures for neural architecture search

    Colin White, Willie Neiswanger, and Yash Savani. Ba- nanas: Bayesian optimization with neural architectures for neural architecture search. In AAAI Conference on Artificial Intelligence, pages 10293–10301, 2021

    2021

  40. [48]

    Maximizing acquisition functions for bayesian opti- mization

    James Wilson, Frank Hutter, and Marc Deisenroth. Maximizing acquisition functions for bayesian opti- mization. Advances in neural information processing systems, 31, 2018

    2018

  41. [49]

    Practical multi-fidelity bayesian optimization for hyperparameter tuning

    Jian Wu, Saul Toscano-Palmerin, Peter I Frazier, and Andrew Gordon Wilson. Practical multi-fidelity bayesian optimization for hyperparameter tuning. In Uncertainty in Artificial Intelligence, pages 788–798, 2020

    2020

  42. [50]

    V oronoi candidates for bayesian optimization

    Nathan Wycoff, John W Smith, Annie S Booth, and Robert B Gramacy. V oronoi candidates for bayesian optimization. arXiv preprint arXiv:2402.04922, 2024

    2024 arXiv

  43. [51]

    Simple combinatorial algo- rithms for combinatorial bandits: Corruptions and ap- proximations

    Haike Xu and Jian Li. Simple combinatorial algo- rithms for combinatorial bandits: Corruptions and ap- proximations. In Uncertainty in Artificial Intelligence, pages 1444–1454. PMLR, 2021

    2021

  44. [52]

    Batched stochastic bayesian optimization via combinatorial constraints design

    Kevin K Yang, Yuxin Chen, Alycia Lee, and Yisong Yue. Batched stochastic bayesian optimization via combinatorial constraints design. In The 22nd Interna- tional Conference on Artificial Intelligence and Statis- tics, pages 3410–3419. PMLR, 2019

    2019

  45. [53]

    Neural thompson sampling

    Weitong Zhang, Dongruo Zhou, Lihong Li, and Quan- quan Gu. Neural thompson sampling. In International Conference on Learning Representations, 2020

    2020

  46. [54]

    Bayesian optimization for materials design with mixed quantitative and qualitative variables

    Yichi Zhang, Daniel W Apley, and Wei Chen. Bayesian optimization for materials design with mixed quantitative and qualitative variables. Scientific re- ports, 10(1):4924, 2020

    2020

  47. [55]

    Neu- ral contextual bandits with ucb-based exploration

    Dongruo Zhou, Lihong Li, and Quanquan Gu. Neu- ral contextual bandits with ucb-based exploration. In International Conference on Machine Learning, 2020

    2020

  48. [56]

    logloss” or “exponential

    Hongpeng Zhou, Minghao Yang, Jun Wang, and Wei Pan. Bayesnas: A bayesian approach for neural archi- tecture search. In International conference on machine learning, pages 7603–7613, 2019. A PROOF FOR THEORETICAL STATEMENTS A.1 ASSUMPTIONS AND KEY LEMMAS We first list out neces...

    2019

Pith tools

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