Scalable First-Order Bayesian Optimization via Structured Automatic Differentiation

Sebastian E. Ament, Carla P. Gomes

Bayesian Optimization (BO) is widely considered the gold standard for optimizing expensive, black-box functions—such as tuning massive neural networks or designing novel materials. Standard BO relies solely on function values to guide its search. However, "First-Order" BO (FOBO) incorporates gradient information, which theoretically provides an exponential improvement in how quickly the algorithm converges on the optimum.

Despite this promise, FOBO has historically been held back by a massive computational catch: the "dimensionality tax."

The Dimensionality Tax

When gradients are included in a Gaussian Process (GP) surrogate model, the size of the kernel matrix explodes. For $n$ observations in $d$ dimensions, the matrix grows from $n \times n$ to $nd \times nd$. Naively multiplying or inverting these dense matrices requires $O(n^2d^2)$ and $O(n^3d^3)$ operations, respectively. If you are working in 100 dimensions, the system is essentially trying to process a matrix 1,000,000 times larger than usual. This computational bottleneck has traditionally restricted FOBO to very small, low-dimensional problems.

The Solution: Structured Automatic Differentiation

To break through this barrier, the authors introduce Structured Automatic Differentiation (AD). Instead of treating the expanded kernel matrix as a dense, monolithic block of numbers, they mathematically derive the analytical, "data-sparse" structures that naturally emerge when differentiating common kernels.

The core of this method focuses on the matrix-valued operator $\mathbf{G} = \nabla_x \nabla_y^\top$ acting on kernel functions. By deriving specific structure-aware rules for how this operator propagates through sums, products, vertical rescaling, and input transformations, the authors drastically reduce computational complexity.

For most canonical kernels (like RBF, Matérn, and Neural Network kernels), Matrix-Vector Multiplications (MVMs) can now be performed in $O(n^2d)$ for gradients and $O(n^2d^2)$ for Hessians.

Computational graphs demonstrating how complex kernels are decomposed for structured automatic differentiation.

As shown in the computational graphs above, this programmatic approach automatically extends to complex, composite kernels—such as Spectral Mixture or Radial Basis Function networks—without requiring manual, case-by-case derivations. This is implemented in their Julia library, CovarianceFunctions.jl, which uses lazy evaluation to maintain $O(1)$ memory usage during matrix multiplications.

Key Insights

  • Kernels as "Proto-Kernels": The authors observe that most kernels are built from three basic types: isotropic (distance-based), dot-product, or stationary linear functionals. The derivatives of these foundational types yield highly exploitable structures, such as rank-one corrections to an identity matrix.
  • Mathematical Exactness: Unlike previous scaling attempts (such as D-SKIP) that rely on approximations to gain speed, Structured AD is mathematically exact to machine precision.
  • Unlocking Second-Order BO: By reducing Hessian MVM complexity from an intractable $O(n^2d^4)$ to $O(n^2d^2)$, this framework opens the door for Second-Order BO, which was previously considered computationally unthinkable.
  • FOBO-Q: The paper proposes a specific model for BO called FOBO-Q (a sum of a quadratic kernel and a Matérn kernel). This provides a useful inductive bias for functions that are globally quadratic but feature local, non-convex variations.

Performance and Results

The authors evaluated their method on challenging non-convex optimization benchmarks (e.g., Griewank, Ackley, Rastrigin) scaled up to 16 dimensions.

The "Fast" Structured AD algorithm demonstrated orders of magnitude improvement over naive approaches, achieving strictly linear scaling in $d$ for gradient observations. In the 16-dimensional tests, FOBO significantly outperformed standard BO and L-BFGS with restarts, finding better optima with fewer function evaluations. Furthermore, their Julia implementation vastly outperformed GPyTorch’s specialized RBFKernelGrad as dimensionality increased, primarily because GPyTorch still relies on $O(n^2d^2)$ operations.

Limitations and Future Directions

While Structured AD elegantly solves the dimensionality ($d$) scaling problem, the complexity remains quadratic with respect to the number of observations ($n^2$). For massive datasets with tens of thousands of points, further innovations like fast kernel transforms will be necessary. Additionally, the authors note that global optimization remains NP-Hard; highly complex high-dimensional landscapes will always pose a fundamental challenge.

Looking forward, integrating this structured AD with hyper-parameter optimization algorithms and applying the Hessian derivations to Bayesian Quadrature represent exciting next steps for the field.

Summary updated

Abstract

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$ {\texttimes} $nd$ for $n$ observations in $d$ dimensions. Naı̈vely multiplying with (resp. inverting) these matrices requires $O(n^2d^2)$ (resp. $O(n^3d^3)$) 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(n^2d)$ matrix-vector multiply for gradient observations and $O(n^2d^2)$ 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$.
BibTeX
@inproceedings{ament2022scalable,
  author = {Sebastian E. Ament and Carla P. Gomes},
  title = {{Scalable First-Order Bayesian Optimization via Structured Automatic Differentiation}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=gcpHHR24TX},
}
Figure