Source-linked AI summary
Parallel Bayesian Global Optimization of Expensive Functions
Jialei Wang, Scott C. Clark, Eric Liu, Peter I. Frazier
TL;DR
The paper tackles parallel global optimization of expensive, derivative-free functions, where selecting a jointly optimal batch is difficult because q-EI is computationally challenging. It uses an unbiased IPA-based stochastic gradient estimator with multistart stochastic gradient ascent to optimize q-EI. Experiments report better performance than approximation methods and improved computational behavior for larger parallel batches, with an open-source MOE implementation.
Problem
Parallel optimization needs an efficient way to maximize q-EI, whose high-dimensional evaluation is slow and numerically challenging for moderately large q.
Method
The method uses infinitesimal perturbation analysis to construct an unbiased stochastic gradient estimator and optimizes q-EI with multistart stochastic gradient ascent.
Results
Numerical experiments show MOE-qEI outperforms existing approximation methods, uses fewer evaluations than CL-mix, and is faster than closed-form approaches for larger q.
Takeaways & Limitations
As restarts and ascent iterations grow, the method recovers the one-step Bayes-optimal parallel evaluation set and provides a practical MOE implementation.
Takeaways & Limitations
Closed-form q-EI methods become slow and numerically challenging as q grows because they require high-dimensional multivariate normal CDF computations.
Abstract
from arXiv · showhide
We consider parallel global optimization of derivative-free expensive-to-evaluate functions, and propose an efficient method based on stochastic approximation for implementing a conceptual Bayesian optimization algorithm proposed by Ginsbourger et al. (2007). At the heart of this algorithm is maximizing the information criterion called the "multi-points expected improvement'', or the q-EI. To accomplish this, we use infinitessimal perturbation analysis (IPA) to construct a stochastic gradient estimator and show that this estimator is unbiased. We also show that the stochastic gradient ascent algorithm using the constructed gradient estimator converges to a stationary point of the q-EI surface, and therefore, as the number of multiple starts of the gradient ascent algorithm and the number of steps for each start grow large, the one-step Bayes optimal set of points is recovered. We show in numerical experiments that our method for maximizing the q-EI is faster than methods based on closed-form evaluation using high-dimensional integration, when considering many parallel function evaluations, and is comparable in speed when considering few. We also show that the resulting one-step Bayes optimal algorithm for parallel global optimization finds high-quality solutions with fewer evaluations than a heuristic based on approximately maximizing the q-EI. A high-quality open source implementation of this algorithm is available in the open source Metrics Optimization Engine (MOE).
1 Introduction
The paper addresses parallel Bayesian global optimization when evaluations are expensive, derivative-free, and aimed at global rather than local optima. It makes the q-EI-based one-step optimal strategy practical through stochastic-gradient optimization, with experiments showing favorable computational and evaluation efficiency.
- Problem setting: Parallel Bayesian global optimization seeks globally good solutions when objective evaluations are expensive and provide no gradients or Hessians.The setting includes deterministic evaluations of complex computer codes, laboratory experiments, or prototype systems.
- q-EI motivation: The q-EI generalizes expected improvement from one point to a set of points evaluated simultaneously, quantifying their expected joint utility.Maximizing q-EI would yield the one-step Bayes-optimal parallel evaluation set.
- q-EI challenge: Unlike scalar expected improvement, q-EI lacks an easy-to-compute and differentiate expression, making naive inner optimization computationally difficult.Existing approaches rely on Monte Carlo simulation, high-dimensional integration, or high-dimensional multivariate normal CDFs, while heuristics do not attain the one-step optimum.
- Contribution: The paper constructs an unbiased stochastic gradient estimator using infinitesimal perturbation analysis and applies stochastic gradient ascent with multiple restarts to maximize q-EI.Under increasing restarts and iterations, the procedure recovers the one-step optimal evaluation set.
- Implementation: MOE-qEI supports both synchronous batch evaluations and asynchronous evaluations whose completion times differ.The method is implemented in the open-source Metrics Optimization Engine (MOE), which also uses parallel computing.
- Empirical results: MOE-qEI uses fewer function evaluations than CL-mix, provides substantial parallel speedup over single-threaded EGO, and is comparable for small q but superior for large q against exact q-EI methods.The closed-form gradient method requires O(q^4) multivariate-normal-CDF calls, whereas the simulation-based approach parallelizes more easily for q > 4.
2 Problem formulation and background
This section formulates Bayesian global optimization with Gaussian-process beliefs and parallel evaluations selected by maximizing posterior q-EI. The q-EI objective captures expected improvement from a candidate set, but its computation becomes expensive for q > 2; a positive separation constraint supports the paper’s convergence analysis.
- 2.1 Bayesian Global Optimization: Bayesian global optimization targets good solutions under a limited evaluation budget rather than asymptotic performance as evaluations grow.A Bayesian prior models uncertainty about the expensive objective before evaluations begin.
- 2.1 Bayesian Global Optimization: The objective is assumed expensive and derivative-free, while domain evaluation and projection onto the feasible domain are computationally easy.Function evaluations provide only objective values, not gradients or Hessians.
- 2.2 Gaussian process priors: The paper uses a Gaussian-process prior specified by a mean function and positive semidefinite covariance function.Previously observed values are combined with this prior to form a posterior distribution over candidate points.
- 2.3 Multi-points expected improvement (q-EI): The posterior distribution guides selection of the next parallel candidate set according to the utility of revealing better solutions than previously known.The decision-theoretic approach is presented as the basis for the subsequent q-EI optimization method.
- 2.3 Multi-points expected improvement (q-EI): For q candidate points, improvement is the positive difference between the current best value and the best value after the parallel evaluations.q-EI is the posterior expectation of this improvement over the joint distribution of the candidate evaluations.
- 2.3 Multi-points expected improvement (q-EI): The next evaluation set is chosen by maximizing q-EI over candidate tuples satisfying domain membership and optional minimum-distance constraints.The feasible set separates new points from one another and from previously evaluated points by at least r.
- 2.3 Multi-points expected improvement (q-EI): When q = 1, q-EI reduces to closed-form expected improvement, while q > 2 requires expensive computation involving high-dimensional Gaussian quantities.The paper notes an analytical expression for q = 2 and difficulty computing q-EI for larger q.
3 Algorithm
The algorithm maximizes q-EI with a stochastic-gradient method, using multistart search and Monte Carlo selection to obtain parallel evaluation batches. It also extends the procedure to asynchronous settings where some evaluations remain in progress.
- Synchronous optimization: MOE-qEI uses a stochastic gradient estimator within multistart stochastic gradient ascent to optimize the q-EI inner problem.The estimator is averaged over Monte Carlo replicates, and the method uses multiple starting points to locate several stationary points.
- Gradient estimation: The estimator g(X, Z) is used as an estimate of the q-EI gradient, with unbiasedness supporting convergence of stochastic gradient ascent.The estimator is based on infinitesimal perturbation analysis and can be computed using derivatives of the Cholesky decomposition.
- Synchronous optimization: After T iterations, Polyak-Ruppert averaging produces the estimated stationary point used for each multistart run.The averaging approach is more robust to stepsize misspecification than using the final iterate directly.
- Synchronous optimization: The algorithm evaluates q-EI at the resulting stationary points by Monte Carlo simulation and selects the candidate with the largest estimate.The implementation also includes optional Latin-hypercube fallback sampling when multistart ascent fails to find sufficient expected improvement.
- Asynchronous optimization: For asynchronous optimization, the method optimizes q-EI over points not currently being evaluated while accounting for the unfinished points in the batch.In practice, setting p = q −1 can reduce idle time by launching a replacement whenever one evaluation completes.
4 Theoretical analysis
The theoretical analysis establishes unbiasedness of the q-EI gradient estimator under smoothness conditions and almost-sure convergence of stochastic gradient ascent to stationary points. More readily checked covariance and mean-function conditions yield the same convergence conclusion.
- Unbiasedness: Theorem 1 establishes unbiasedness of the constructed q-EI gradient estimator under continuous differentiability and nonduplicate covariance rows.The theorem also requires that the relevant random gradient exists almost surely.
- Unbiasedness: The differentiability requirement on the Cholesky factor can be checked through the smoothness of the prior covariance function.A twice-differentiable symmetric nonnegative definite covariance matrix yields a Cholesky factor with corresponding differentiability.
- Convergence: The feasible set is represented by differentiable inequality constraints, including domain and minimum-distance constraints among candidate points.These constraints define the feasible batch space used by the stochastic gradient ascent analysis.
- Convergence: Theorem 2 shows that stochastic gradient ascent and its Polyak-Ruppert average converge almost surely to a connected set of stationary q-EI points.The result assumes continuously differentiable constraints plus twice-continuously differentiable positive-definite posterior mean and covariance functions.
- Convergence: When sampled points are distinct and the prior covariance is positive definite and twice differentiable, with a twice-differentiable prior mean, the iterates converge to a connected stationary-point set.The corollary provides conditions that can be checked before running MOE-qEI.
5 Numerical results
Numerical experiments show that MOE-qEI efficiently solves both the outer parallel optimization problem and the inner q-EI maximization problem. Its stochastic-gradient implementation achieves strong solution quality, scales well with parallelism, and can outperform closed-form gradient evaluation as q grows.
- Outer optimization: MOE-qEI consistently finds better solutions than CL-mix across four standard test functions.The experiments use Branin2, Hartmann3, Ackley5, and Hartmann6, with 100 repetitions using different initial point sets.
- Outer optimization: MOE-qEI achieves significant speedup over EGO as the parallelism level q grows.The sequential EGO algorithm makes the same decisions as MOE-qEI when q = 1.
- Inner optimization: MOE-qEI achieves the best inner-optimization solution quality among MOE-qEI, CL-mix, and Benchmark 1.Its runtime is almost comparable to CL-mix, while Benchmark 1 becomes sharply slower as q increases.
- Inner optimization: MOE-qEI’s runtime scales well as q grows, making the method feasible for applications with high parallelism.CL-mix is expected to be fastest because it sacrifices solution quality for speed, while Benchmark 1 was evaluated only up to q = 4 because its runtime rises drastically.
- Gradient evaluation: The Monte Carlo gradient estimator is faster than the closed-form method when q ≥4 and increases more slowly in computational time as q grows.The comparison uses a high-precision MOE-qEI estimator with 10^7 samples and a parallel GPU implementation.
- Gradient evaluation: Reducing Monte Carlo samples from 10^7 to 10^4 keeps each gradient component’s variance below 10^-7.The authors report that GPU parallelism provides roughly 100x to 1000x speedup, while stochastic gradient ascent can tolerate still noisier gradients.
6 Conclusions
The paper develops a stochastic-approximation method for maximizing q-EI and shows that its stochastic gradient estimator is unbiased. Numerical experiments demonstrate improved performance over existing approximation methods.
- IPA constructs an unbiased stochastic gradient estimator for the q-EI surface.
- The method uses stochastic approximation to implement parallel Bayesian global optimization.
- Numerical experiments show that the proposed method outperforms existing state-of-the-art approximation methods.
Appendix: proofs of results in the main paper
The appendix establishes the regularity and convergence properties underlying the stochastic-gradient method. It shows almost-sure convergence of the iterates to stationary points of the q-EI objective under the stated assumptions.
- The maximization of finitely many differentiable functions has only countably many non-differentiable points.
- Under differentiability and non-duplication conditions, the stochastic gradient exists almost surely.
- The IPA conditions imply that the expected stochastic gradient equals the gradient of expected q-EI.
- The stochastic-gradient iterates converge almost surely to a connected set of stationary points.
Appendix: Choice of batch size q
The appendix frames batch-size selection as a trade-off between parallel speedup within evaluations and optimization efficiency across batches. The proposed framework remains incomplete because key speedup functions are generally unknown and several settings are left for future work.
- With fixed maximum parallelism and non-parallelizable evaluations, setting q to qmax uses all available resources.
- Choosing q trades off faster individual evaluations against fewer parallel optimization batches.
- In the synchronous model, wall-clock time depends on evaluation speedup γ(q̂) and batch-efficiency β(q).
- The framework assumes nondecreasing γ and β when characterizing an optimal allocation of parallelism.
- The analysis is limited because γ(q̂) and β(q) are generally unknown and varying q̂ and q may be beneficial.