Efficient Batch Black-box Optimization with Deterministic Regret Bounds
arXiv:1905.10041
Abstract
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.
References in corpus (10)
- Practical Bayesian Optimization of Machine Learning Algorithms
- Predictive Entropy Search for Efficient Global Optimization of Black-box Functions
- Batch Bayesian Optimization via Local Penalization
- Max-value Entropy Search for Efficient Bayesian Optimization
- Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences
- The Parallel Knowledge Gradient Method for Batch Bayesian Optimization
- Batched Large-scale Bayesian Optimization in High-dimensional Spaces
- Parallel Predictive Entropy Search for Batch Global Optimization of Expensive Objective Functions
- Adversarially Robust Optimization with Gaussian Processes
- Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation