# Scalable First-Order Bayesian Optimization via Structured Automatic Differentiation

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 76 references that are in the map.
- First posted on arXiv 16 Jun 2022.

## Builds on (most cited first, 30 of 33)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Automatic differentiation in machine learning: a survey](https://mlsanity.com/paper/1502.05767/) (2015)
- [Deep Bayesian Active Learning with Image Data](https://mlsanity.com/paper/1703.02910/) (2017)
- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Deep Kernel Learning](https://mlsanity.com/paper/1511.02222/) (2015)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [Gradient-based Hyperparameter Optimization through Reversible Learning](https://mlsanity.com/paper/1502.03492/) (2015)
- [Scalable Bayesian Optimization Using Deep Neural Networks](https://mlsanity.com/paper/1502.05700/) (2015)
- [Kernel Interpolation for Scalable Structured Gaussian Processes (KISS-GP)](https://mlsanity.com/paper/1503.01057/) (2015)
- [GPflow: A Gaussian process library using TensorFlow](https://mlsanity.com/paper/1610.08733/) (2016)
- [Gaussian Process Kernels for Pattern Discovery and Extrapolation](https://mlsanity.com/paper/1302.4245/) (2013)
- [Fast Bayesian Optimization of Machine Learning Hyperparameters on Large Datasets](https://mlsanity.com/paper/1605.07079/) (2016)
- [Exact Gaussian Processes on a Million Data Points](https://mlsanity.com/paper/1903.08114/) (2019)
- [Variational Bayesian Optimal Experimental Design](https://mlsanity.com/paper/1903.05480/) (2019)
- [Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspaces](https://mlsanity.com/paper/1902.03229/) (2019)
- [Tuning Hyperparameters without Grad Students: Scalable and Robust Bayesian Optimisation with Dragonfly](https://mlsanity.com/paper/1903.06694/) (2019)
- [Bayesian Optimization with Gradients](https://mlsanity.com/paper/1703.04389/) (2017)
- [Don't Unroll Adjoint: Differentiating SSA-Form Programs](https://mlsanity.com/paper/1810.07951/) (2018)
- [Scalable Log Determinants for Gaussian Process Kernel Learning](https://mlsanity.com/paper/1711.03481/) (2017)
- [Product Kernel Interpolation for Scalable Gaussian Processes](https://mlsanity.com/paper/1802.08903/) (2018)
- [Modeling and interpolation of the ambient magnetic field by Gaussian processes](https://mlsanity.com/paper/1509.04634/) (2015)
- [Scaling Gaussian Process Regression with Derivatives](https://mlsanity.com/paper/1810.12283/) (2018)
- [A survey of active learning algorithms for supervised remote sensing image classification](https://mlsanity.com/paper/2104.07784/) (2021)
- [Practical Bayesian optimization in the presence of outliers](https://mlsanity.com/paper/1712.04567/) (2017)
- [BayesOpt: A Bayesian Optimization Library for Nonlinear Optimization, Experimental Design and Bandits](https://mlsanity.com/paper/1405.7430/) (2014)
- [High-Dimensional Gaussian Process Inference with Derivatives](https://mlsanity.com/paper/2102.07542/) (2021)
- [Scaling Gaussian Processes with Derivative Information Using Variational Inference](https://mlsanity.com/paper/2107.04061/) (2021)
- [Improving the Gaussian Process Sparse Spectrum Approximation by Representing Uncertainty in Frequency Inputs](https://mlsanity.com/paper/1503.02424/) (2015)

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

- [Unexpected Improvements to Expected Improvement for Bayesian Optimization](https://mlsanity.com/paper/2310.20708/) (2023)
- [A survey and benchmark of high-dimensional Bayesian optimization of discrete sequences](https://mlsanity.com/paper/2406.04739/) (2024)
- [SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems](https://mlsanity.com/paper/2210.12547/) (2022)
- [Scalable Gaussian Processes with Latent Kronecker Structure](https://mlsanity.com/paper/2506.06895/) (2025)
- [BayeSQP: Bayesian Optimization through Sequential Quadratic Programming](https://mlsanity.com/paper/2602.03232/) (2026)
- [Auto-Differentiation of Relational Computations for Very Large Scale Machine Learning](https://mlsanity.com/paper/2306.00088/) (2023)
- [FastBO: Fast HPO and NAS with Adaptive Fidelity Identification](https://mlsanity.com/paper/2409.00584/) (2024)
- [Dependency Structure Search Bayesian Optimization for Decision Making Models](https://mlsanity.com/paper/2308.00629/) (2023)
- [Novel Pivoted Cholesky Decompositions for Efficient Gaussian Process Inference](https://mlsanity.com/paper/2507.20678/) (2025)
- [Scalable Derivative Gaussian Processes via Exact Gradient Reduction](https://mlsanity.com/paper/2606.02909/) (2026)

## Abstract (arXiv)

Bayesian Optimization (BO) has shown great promise for the global optimization of functions that are expensive to evaluate, but despite many successes, standard approaches can struggle in high dimensions. To improve the performance of BO, prior work suggested incorporating gradient information into a Gaussian process surrogate of the objective, giving rise to kernel matrices of size nd × nd for n observations in d dimensions. Na"ively multiplying with (resp. inverting) these matrices requires O(n2d2) (resp. O(n3d3)) operations, which becomes infeasible for moderate dimensions and sample sizes. Here, we observe that a wide range of kernels gives rise to structured matrices, enabling an exact O(n2d) matrix-vector multiply for gradient observations and O(n2d2) for Hessian observations. Beyond canonical kernel classes, we derive a programmatic approach to leveraging this type of structure for transformations and combinations of the discussed kernel classes, which constitutes a structure-aware automatic differentiation algorithm. Our methods apply to virtually all canonical kernels and automatically extend to complex kernels, like the neural network, radial basis function network, and spectral mixture kernels without any additional derivations, enabling flexible, problem-dependent modeling while scaling first-order BO to high d.