mlsanityData to 7 Oct 2026

A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance

arXiv 2010.13997 ↗First posted 27 Oct 2020stat.ML cs.LGcited by 38

Not on the map. Why?

Abstract (arXiv)

We consider sequential optimization of an unknown function in a reproducing kernel Hilbert space. We propose a Gaussian process-based algorithm and establish its order-optimal regret performance (up to a poly-logarithmic factor). This is the first GP-based algorithm with an order-optimal regret guarantee. The proposed algorithm is rooted in the methodology of domain shrinking realized through a sequence of tree-based region pruning and refining to concentrate queries in increasingly smaller high-performing regions of the function domain. The search for high-performing regions is localized and guided by an iterative estimation of the optimal function value to ensure both learning efficiency and computational efficiency. Compared with the prevailing GP-UCB family of algorithms, the proposed algorithm reduces computational complexity by a factor of O(T2d-1) (where T is the time horizon and d the dimension of the function domain).

Key facts. Cited by 38 papers in the map (data through 7 Oct 2026). First posted on arXiv 27 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 10; 2023: 7; 2024: 5; 2025: 8; 2026: 6.

38 papers.

Sort:

By area:

  1. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  2. 2022On Kernelized Multi-Armed Bandits with Constraintscited by 23
  3. 2021Lipschitz Bandits with Batched Feedbackcited by 21
  4. 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
  5. 2022Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learningcited by 18
  6. 2022An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledgecited by 17
  7. 2023Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiencycited by 16
  8. 2023Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixturescited by 12
  9. 2023Quantum Bayesian Optimizationcited by 12
  10. 2025Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variancecited by 12
  11. 2023Delayed Feedback in Kernel Banditscited by 10
  12. 2025Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Banditscited by 9
26 more
  1. 2022Stochastic Zeroth order Descent with Structured Directionscited by 8
  2. 2023Sample Complexity of Kernel-Based Q-Learningcited by 8
  3. 2023Learning Regions of Interest for Bayesian Optimization with Adaptive Level-Set Estimationcited by 8
  4. 2024Near-Optimal Algorithm for Non-Stationary Kernelized Banditscited by 8
  5. 2022Global Optimization with Parametric Function Approximationcited by 7
  6. 2022Provably and Practically Efficient Neural Contextual Banditscited by 6
  7. 2022Collaborative Learning in Kernel-based Bandits for Distributed Userscited by 6
  8. 2024Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithmcited by 6
  9. 2022Instance-Dependent Regret Analysis of Kernelized Banditscited by 5
  10. 2026Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hyperspherecited by 4
  11. 2022Regret Bounds for Noise-Free Cascaded Kernelized Banditscited by 3
  12. 2025Differentially Private Kernelized Contextual Banditscited by 3
  13. 2025Bayesian Optimization from Human Feedback: Near-Optimal Regret Boundscited by 3
  14. 2024Open Problem: Order Optimal Regret Bounds for Kernel-Based Reinforcement Learningcited by 2
  15. 2026Batched Kernelized Bandits: Refinements and Extensionscited by 2
  16. 2024Dimensionality Reduction Techniques for Global Bayesian Optimisationcited by 1
  17. 2025Consequences of Kernel Regularity for Bandit Optimizationcited by 1
  18. 2026Nearly-Optimal Algorithm for Adversarial Kernelized Banditscited by 1
  19. 2022Optimistic Optimization of Gaussian Process Samplescited by 0
  20. 2024Order-Optimal Regret in Distributed Kernel Bandits using Uniform Sampling with Shared Randomnesscited by 0
  21. 2025Representative Action Selection for Large Action Space Bandit Familiescited by 0
  22. 2025Differential Privacy in Kernelized Contextual Bandits via Random Projectionscited by 0
  23. 2025Nonlinear Dimensionality Reduction Techniques for Bayesian Optimizationcited by 0
  24. 2026A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedbackcited by 0
  25. 2026Sharper Guarantees for Misspecified Kernelized Bandit Optimizationcited by 0
  26. 2026Near-Optimal Regret in Adversarial Kernel Banditscited by 0