# Gradient-based Sample Selection for Faster Bayesian Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 58 references that are in the map.
- First posted on arXiv 10 Apr 2025.

## Builds on (most cited first, 26 of 26)

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds](https://mlsanity.com/paper/1906.03671/) (2019)
- [Gradient based sample selection for online continual learning](https://mlsanity.com/paper/1903.08671/) (2019)
- [Deep Kernel Learning](https://mlsanity.com/paper/1511.02222/) (2015)
- [Gaussian Processes for Big Data](https://mlsanity.com/paper/1309.6835/) (2013)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [Bayesian Optimization in a Billion Dimensions via Random Embeddings](https://mlsanity.com/paper/1301.1942/) (2013)
- [Differentiable Expected Hypervolume Improvement for Parallel Multi-Objective Bayesian Optimization](https://mlsanity.com/paper/2006.05078/) (2020)
- [Dataset Pruning: Reducing Training Data by Examining Generalization Influence](https://mlsanity.com/paper/2205.09329/) (2022)
- [Parallel Bayesian Optimization of Multiple Noisy Objectives with Expected Hypervolume Improvement](https://mlsanity.com/paper/2105.08195/) (2021)
- [Batch Bayesian Optimization via Local Penalization](https://mlsanity.com/paper/1505.08052/) (2015)
- [A survey on high-dimensional Gaussian process modeling with application to Bayesian optimization](https://mlsanity.com/paper/2111.05040/) (2021)
- [Recent Advances in Bayesian Optimization](https://mlsanity.com/paper/2206.03301/) (2022)
- [The Parallel Knowledge Gradient Method for Batch Bayesian Optimization](https://mlsanity.com/paper/1606.04414/) (2016)
- [Bayesian Optimization with Gradients](https://mlsanity.com/paper/1703.04389/) (2017)
- [A Unified Particle-Optimization Framework for Scalable Bayesian Sampling](https://mlsanity.com/paper/1805.11659/) (2018)
- [Inducing Point Allocation for Sparse Gaussian Processes in High-Throughput Bayesian Optimisation](https://mlsanity.com/paper/2301.10123/) (2023)
- [A Tutorial on Sparse Gaussian Processes and Variational Inference](https://mlsanity.com/paper/2012.13962/) (2020)
- [Connections and Equivalences between the Nystr"om Method and Sparse Variational Gaussian Processes](https://mlsanity.com/paper/2106.01121/) (2021)
- [Sampling-based Nystr"om Approximation and Kernel Quadrature](https://mlsanity.com/paper/2301.09517/) (2023)
- [Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Times](https://mlsanity.com/paper/2201.12909/) (2022)
- [Scalable Bayesian Optimization Using Vecchia Approximations of Gaussian Processes](https://mlsanity.com/paper/2203.01459/) (2022)
- [Gradient-based Sampling: An Adaptive Importance Sampling for Least-squares](https://mlsanity.com/paper/1803.00841/) (2018)
- [Non-smooth Bayesian Optimization in Tuning Problems](https://mlsanity.com/paper/2109.07563/) (2021)
- [Stochastic Gradient Line Bayesian Optimization for Efficient Noise-Robust Optimization of Parameterized Quantum Circuits](https://mlsanity.com/paper/2111.07952/) (2021)
- [Hybrid Parameter Search and Dynamic Model Selection for Mixed-Variable Bayesian Optimization](https://mlsanity.com/paper/2206.01409/) (2022)

## Abstract (arXiv)

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.