Source-linked AI summary
Bayesian Optimization with Gradients
Jian Wu, Matthias Poloczek, Andrew Gordon Wilson, Peter I. Frazier
TL;DR
Bayesian optimization typically omits derivative information despite its usefulness for expensive, multimodal objectives. The paper develops d-KG, a derivative-enabled knowledge-gradient method with exact discretization-free computation, and reports reduced evaluation needs and strong benchmark performance while supporting noisy or incomplete gradients.
Problem
Bayesian optimization typically does not use derivative information, motivating methods that reduce objective evaluations when gradients are available, noisy, or incomplete.
Method
The paper develops d-KG, a sequential and batch Bayesian optimization algorithm that uses derivative observations and an exact discretization-free acquisition-gradient estimator.
Results
d-KG shows one-step Bayes-optimality, asymptotic consistency, greater one-step value of information, and state-of-the-art performance across benchmarks with and without gradients.
Takeaways & Limitations
Derivative information can greatly decrease objective evaluations for low-dimensional Bayesian optimization, including when gradients are noisy or available for only some variables.
Takeaways & Limitations
The core formulation initially assumes observing the function value and all d partial derivatives at each sampled point, before relaxing this assumption to a single directional derivative.
Abstract
from arXiv · showhide
Bayesian optimization has been successful at global optimization of expensive-to-evaluate multimodal objective functions. However, unlike most optimization methods, Bayesian optimization typically does not use derivative information. In this paper we show how Bayesian optimization can exploit derivative information to decrease the number of objective function evaluations required for good performance. In particular, we develop a novel Bayesian optimization algorithm, the derivative-enabled knowledge-gradient (dKG), for which we show one-step Bayes-optimality, asymptotic consistency, and greater one-step value of information than is possible in the derivative-free setting. Our procedure accommodates noisy and incomplete derivative information, comes in both sequential and batch forms, and can optionally reduce the computational cost of inference through automatically selected retention of a single directional derivative. We also compute the d-KG acquisition function and its gradient using a novel fast discretization-free technique. We show d-KG provides state-of-the-art performance compared to a wide range of optimization procedures with and without gradients, on benchmarks including logistic regression, deep learning, kernel learning, and k-nearest neighbors.
1 Introduction
Bayesian optimization targets expensive, noisy, multimodal objectives but generally underuses derivative information. The paper develops d-KG to incorporate gradients and evaluates it against derivative-aware and derivative-free alternatives.
- Bayesian optimization: Bayesian optimization uses a function prior and acquisition functions to balance exploration and exploitation when selecting objective queries.The posterior is updated as new objective values are observed, commonly under a Gaussian-process prior.
- Motivation: Gradients provide directional information about objective values and can supply d + 1 values per query in d dimensions.The paper argues this information advantage is particularly significant for high-dimensional problems.
- Contribution: The derivative-enabled knowledge-gradient, d-KG, handles noisy and incomplete gradients in sequential and batch Bayesian optimization.It can retain a single automatically selected directional derivative to reduce inference overhead.
- Contribution: The paper introduces a faster exact discretization-free method for computing the knowledge-gradient acquisition function and its gradient.The method is intended to improve speed and avoid discretization in d-KG optimization.
- Evaluation: Experiments compare derivative-enabled and derivative-free batch Bayesian optimization methods with BFGS using full gradients.The comparisons cover synthetic and real problems, including machine-learning applications.
2 Related Work
Prior work incorporated derivative observations into Gaussian-process Bayesian optimization, but the paper distinguishes d-KG through broader derivative handling and a new continuous-space computation method. Recent advances make this direction increasingly practical.
- Derivative-aware Bayesian optimization: Earlier derivative-aware Bayesian optimization used derivative observations to improve Gaussian-process covariance conditioning, without letting derivatives affect acquisition decisions.The paper contrasts this with its approach, where derivative information directly influences acquisition.
- Derivative-aware Bayesian optimization: Lizotte’s derivative-aware expected improvement can outperform BFGS with complete gradients, whereas this paper supports noisy and incomplete derivative information.The paper identifies incomplete gradients, batch support, and a novel acquisition function among its key differences.
- Directional derivatives: Related work retained a randomly selected directional derivative for computational reasons, while this paper selects a single directional derivative using value of information.The distinction concerns how the retained direction is chosen.
- Batch knowledge gradient: The paper generalizes batch knowledge gradient to derivatives and replaces discretization with an exact method for continuous search spaces.The authors report that this generalization improves speed and accuracy and applies to other knowledge-gradient methods.
- Practical context: Improved access to derivatives and more tractable Gaussian processes make gradient-enabled Bayesian optimization increasingly practical.The paper connects this trend to the timeliness of discussing Bayesian optimization with gradients.
3 Knowledge Gradient with Derivatives
The paper develops d-KG, a derivative-enabled knowledge-gradient algorithm that incorporates noisy, incomplete, and directional derivative observations into Bayesian optimization. It defines the acquisition function, efficient exact computation, and theoretical guarantees including improved value of information, one-step Bayes-optimality, and asymptotic consistency.
- 3.1 Derivative Information: d-KG models function values and derivatives jointly with a Gaussian process, supporting noisy, incomplete, and directional derivative observations.When observations are incomplete, the corresponding rows and columns are removed; directional derivatives are incorporated as linear transformations of gradients.
- 3.2 The d-KG Acquisition Function: The derivative-enabled knowledge gradient selects batches of points by maximizing the expected value of information from future function and derivative observations.Its acquisition function accounts not only for how observed gradients update the posterior, but also for the prospect of future gradient observations.
- 3.2 The d-KG Acquisition Function: d-KG differs from derivative-free KG because future gradient observations directly change the acquisition function and its posterior mean.This dependence requires integrating over the distribution of future gradient observations.
- 3.2 The d-KG Acquisition Function: In a one-dimensional example, d-KG chooses a better evaluation point than derivative-enabled EI, yielding more accurate knowledge of the optimum’s location.The corresponding d-EI observation leaves substantial uncertainty about the optimum.
- 3.3 Efficient Exact Computation of d-KG: Including all d partial derivatives can make inference scale as O(n^3(d + 1)^3), so d-KG can retain one automatically selected directional derivative per iteration.This option reduces computational overhead while retaining derivative-observation value.
- 3.3 Efficient Exact Computation of d-KG: A discretization-free method provides an unbiased estimator of the d-KG gradient for stochastic gradient ascent, avoiding discretization and significantly improving speed.The method is described as exact because it avoids discretization.
- 3.4 Theoretical Analysis: d-KG’s value of information exceeds that of derivative-free KG under mild conditions, and d-KG is one-step Bayes-optimal when one iteration remains.The one-step guarantee applies when both function values and partial derivatives can be observed.
- 3.4 Theoretical Analysis: With a finite feasible set and a GP prior with known hyperparameters, d-KG is asymptotically consistent as the number of iterations tends to infinity.The recommended point converges almost surely to a global minimizer.
4 Experiments
The experiments evaluate d-KG on synthetic functions and machine-learning hyperparameter problems under noisy, incomplete, full, and batch derivative settings. Across these benchmarks, d-KG generally achieves the strongest performance, while specific competitors lead temporarily or on particular tasks.
- Experimental scope: d-KG is evaluated on six synthetic benchmarks and on weighted KNN, logistic regression, deep learning, and spectral mixture kernel learning.The comparisons include batch Bayesian optimization methods with and without derivatives, plus gradient-based optimizers where full gradients are available.
- Experimental settings: Noisy derivative experiments add zero-mean normal noise with standard deviation σ = 0.5 to objective and partial-derivative observations, with σ estimated from observations.The experiments also examine incomplete gradients and use batch size q = 4 for Branin, Rosenbrock, and Ackley.
- Synthetic test functions: After 40 function evaluations on Branin, d-KG outperforms its competitors and obtains the best solution within the evaluation limit.BFGS progresses faster initially but later stalls; on Hartmann, d-KG dominates across evaluations, while on Ackley d-KG overtakes d-EI after about 50 evaluations.
- Synthetic test functions: With incomplete derivatives on Rosenbrock, d-KG finds a near-optimal solution after approximately 50 evaluations, while derivative-free KG catches up after approximately 75.Both EI and d-EI get stuck early; on Levy, the ordering differs from the other incomplete-derivative benchmark.
- Real-world test functions: d-KG outperforms alternative approaches on the weighted KNN, spectral mixture kernel, logistic regression, and deep neural network benchmarks.For KNN, d-KG overtakes alternatives; for spectral mixture kernels, it most consistently finds a good solution and obtains the best solution within the step limit.
5 Discussion
The discussion concludes that derivative information can substantially reduce objective evaluations in low-dimensional Bayesian optimization, including when derivatives are noisy or incomplete. It also identifies scalability and model-flexibility extensions as future directions.
- Conclusions: Derivative information can greatly decrease the number of objective function evaluations required for good solutions, especially with the knowledge-gradient acquisition function.The conclusion covers synthetic benchmarks and applications in logistic regression, deep learning, kernel learning, and k-nearest neighbors.
- Implications: Bayesian optimization with derivatives is positioned as a way to support more automatic and principled machine-learning parameter tuning.The discussion specifically connects derivative information with automating expensive hyperparameter optimization, including deep neural networks.
- Future work: Combining derivative information with deep projections and scalable Gaussian processes is proposed as future work for applying Bayesian optimization to a wider range of problems.The proposed scalable GP advances target O(n) training and O(1) test-time predictions.
Supplementary Material
The supplementary material identifies the paper’s authors and their institutional affiliations.
- Authors: The paper is authored by Jian Wu, Matthias Poloczek, Andrew Gordon Wilson, and Peter I. Frazier.
- Affiliations: The authors are affiliated with Cornell University and the University of Arizona.
A The Computation of d-KG and its Gradient: Additional Details
The supplementary material derives a Gaussian representation for noisy function and directional-derivative observations, then uses it to estimate d-KG and its gradient. Posterior mean updates are expressed through a standard-normal random vector and a covariance-factor construction.
- Posterior representation: After n evaluations, the function and a directional derivative form a bivariate Gaussian process with posterior mean and kernel functions.The directional derivative is taken along direction θ.
- Observation model: Conditioned on batch points and current knowledge, function and directional-derivative observations are normally distributed with posterior covariance plus observation-noise variances.The mapping returns both the function value and directional derivative observation at each queried point.
- Posterior update: The updated posterior mean is represented as ˆµ(n+q)(x) = ˆµ(n)(x) + ˆσ(n)(x, θ, z(1:q))Z2q.Z2q is a 2q-dimensional standard normal vector.
- Acquisition computation: The Cholesky factor of the noisy observation covariance is used to complete the estimator for d-KG and its gradient.This construction follows the main document’s estimation procedure.
B Proof of Proposition 1 and Proposition 2
The analysis formulates Bayesian optimization as a dynamic program whose state is the current posterior belief. This framework establishes d-KG’s one-step Bayes-optimality and shows derivative information can strictly improve value when it affects the predicted optimum.
- Value of derivative information: Derivative observations yield a strict value-of-information improvement when they affect the posterior-dependent predicted minimizer.Equality can occur only when the relevant minimizer remains unchanged across conditionally possible derivative observations.
- Optimization formulation: The proof’s optimization objective selects sampling decisions and a final implementation decision under a finite sample budget.The function and derivative process are modeled with a Gaussian-process prior and updated posterior.
- Dynamic-programming formulation: The dynamic-programming state S_n=(μ̃(nq), K̃(nq)) completely characterizes the belief about f after iteration n.The value function and Bellman recursion are defined over this posterior state.
- One-step optimality: d-KG is obtained from the Bellman equation for the one-step stopping problem, proving one-step Bayes-optimality.The proof identifies the resulting decision rule with the d-KG algorithm.
C Proof of Theorem 1
The theorem analysis studies finite-horizon Bayesian optimization through dynamic programming and establishes conditions under which d-KG converges to the correct solution. The key condition is continued measurement of every feasible alternative, with different sampling requirements for noisy and noise-free settings.
- Value of additional samples: For stationary policies, one additional iteration improves expected performance on average, and the optimal value is nondecreasing with the sample budget.The result follows from comparisons between policy values and the value of an additional fixed batch of samples.
- Consistency condition: If every alternative is sampled infinitely often with noise, or at least once without noise, the policy is asymptotically consistent and attains value U(s).The feasible set A is assumed finite.
- Posterior convergence: Repeated sampling drives the posterior mean toward the true function, yielding convergence of the estimated minimum under the finite-variance noise assumption.The proof uses the vector-version strong law of large numbers and uniform integrability.
- d-KG sampling behavior: d-KG measures every alternative infinitely often in the noisy case or at least once in the noise-free case as the iteration count grows.The argument shows that alternatives sampled only finitely often retain benefits from additional measurement and are therefore selected.
- Theorem consequence: Consequently, d-KG satisfies the sampling condition required for asymptotic consistency under the theorem’s finite-set and known-hyperparameter assumptions.The limiting policy value equals the optimal value U(s).