Efficient Batch Black-box Optimization with Deterministic Regret Bounds
This work addresses the challenge of efficient batch optimization for researchers and practitioners in machine learning, though it appears incremental as it builds on existing kernel methods and Bayesian Optimization frameworks.
The authors tackled the problem of batch black-box optimization by proposing a novel algorithm that jointly maximizes acquisition functions and selects points holistically, achieving effective results on synthetic and real-world benchmarks.
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.