# Efficient Batch Black-box Optimization with Deterministic Regret Bounds

arXiv: https://arxiv.org/abs/1905.10041 · HTML: https://mlsanity.com/paper/1905.10041/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2019.

## Built on by (most cited first, 8 of 8)

- [Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency](https://mlsanity.com/paper/2310.15351/) (2023)
- [Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance](https://mlsanity.com/paper/2502.06363/) (2025)
- [Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits](https://mlsanity.com/paper/2502.19006/) (2025)
- [Enhancing Gaussian Process Surrogates for Optimization and Posterior Approximation via Random Exploration](https://mlsanity.com/paper/2401.17037/) (2024)
- [Regret Bounds for Noise-Free Cascaded Kernelized Bandits](https://mlsanity.com/paper/2211.05430/) (2022)
- [Convergence Rates of Constrained Expected Improvement](https://mlsanity.com/paper/2505.11323/) (2025)
- [Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2608.16492/) (2026)
- [Practical Efficient Global Optimization is No-regret](https://mlsanity.com/paper/2603.25311/) (2026)

## Abstract (arXiv)

In this work, we investigate black-box optimization from the perspective of frequentist kernel methods. We propose a novel batch optimization algorithm, which jointly maximizes the acquisition function and select points from a whole batch in a holistic way. Theoretically, we derive regret bounds for both the noise-free and perturbation settings irrespective of the choice of kernel. Moreover, we analyze the property of the adversarial regret that is required by a robust initialization for Bayesian Optimization (BO). We prove that the adversarial regret bounds decrease with the decrease of covering radius, which provides a criterion for generating a point set to minimize the bound. We then propose fast searching algorithms to generate a point set with a small covering radius for the robust initialization. Experimental results on both synthetic benchmark problems and real-world problems show the effectiveness of the proposed algorithms.