Gradient-based Sample Selection for Faster Bayesian Optimization
This work addresses computational bottlenecks for practitioners using BO in resource-intensive applications, though it is incremental as it builds on existing BO methods.
The paper tackles the computational inefficiency of Bayesian optimization (BO) in large-budget scenarios by proposing GSSBO, which uses gradient-based sample selection to reduce GP fitting costs while achieving sublinear regret bounds and maintaining competitive optimization performance in experiments.
Bayesian optimization (BO) is an effective technique for black-box optimization. However, its applicability is typically limited to moderate-budget problems due to the cubic complexity of fitting the Gaussian process (GP) surrogate model. In large-budget scenarios, directly employing the standard GP model faces significant challenges in computational time and resource requirements. In this paper, we propose a novel approach, gradient-based sample selection Bayesian Optimization (GSSBO), to enhance the computational efficiency of BO. The GP model is constructed on a selected set of samples instead of the whole dataset. These samples are selected by leveraging gradient information to remove redundancy while preserving diversity and representativeness. We provide a theoretical analysis of the gradient-based sample selection strategy and obtain explicit sublinear regret bounds for our proposed framework. Extensive experiments on synthetic and real-world tasks demonstrate that our approach significantly reduces the computational cost of GP fitting in BO while maintaining optimization performance comparable to baseline methods.