PaperlayerView exact revision on arXiv

Source-linked AI summary

A General Framework for Constrained Bayesian Optimization using Information-based Search

José Miguel Hernández-Lobato, Michael A. Gelbart, Ryan P. Adams, Matthew W. Hoffman, Zoubin Ghahramani

arXiv:1511.09422v2stat.ML

TL;DR

The paper addresses global black-box optimization with black-box constraints, especially when objective and constraint functions can be evaluated independently. It develops PESC, an information-based acquisition function that separates contributions across evaluations, and reports strong performance across coupled and decoupled settings. It also introduces PESC-F to trade computation time against approximation accuracy when function-evaluation costs differ.

  • Problem

    Global black-box optimization with black-box constraints requires methods that support independently evaluated objective and constraint functions rather than only joint evaluations.

  • Method

    PESC approximates expected information gain about the constrained solution and uses an additive acquisition function for arbitrary subsets of independently evaluated functions.

  • Results

    PESC achieves state-of-the-art results in coupled problems and significantly outperforms coupled PESC in the evaluated decoupled scenarios.

  • Takeaways & Limitations

    PESC provides a separable information-based approach for general constrained Bayesian optimization, including decoupled tasks and resource competition.

  • Takeaways & Limitations

    PESC-F makes sub-optimal decisions because time constraints require trading accuracy against computation time, and selecting its rationality level remains future work.

Abstract

from arXiv · show

We present an information-theoretic framework for solving global black-box optimization problems that also have black-box constraints. Of particular interest to us is to efficiently solve problems with decoupled constraints, in which subsets of the objective and constraint functions may be evaluated independently. For example, when the objective is evaluated on a CPU and the constraints are evaluated independently on a GPU. These problems require an acquisition function that can be separated into the contributions of the individual function evaluations. We develop one such acquisition function and call it Predictive Entropy Search with Constraints (PESC). PESC is an approximation to the expected information gain criterion and it compares favorably to alternative approaches based on improvement in several synthetic and real-world problems. In addition to this, we consider problems with a mix of functions that are fast and slow to evaluate. These problems require balancing the amount of time spent in the meta-computation of PESC and in the actual evaluation of the target objective. We take a bounded rationality approach and develop partial update for PESC which trades off accuracy against speed. We then propose a method for adaptively switching between the partial and full updates for PESC. This allows us to interpolate between versions of PESC that are efficient in terms of function evaluations and those that are efficient in terms of wall-clock time. Overall, we demonstrate that PESC is an effective algorithm that provides a promising direction towards a unified solution for constrained Bayesian optimization.

1. Introduction

The paper frames constrained Bayesian optimization as global black-box minimization under simultaneously satisfied black-box constraints, often with expensive or independently evaluated functions. It introduces PESC as an information-based approach designed for decoupled evaluations and mixed evaluation costs.

  • Motivation: Constrained optimization seeks a global minimizer of a black-box objective while satisfying all black-box constraints.The motivating examples include tuning speech-recognition hyperparameters under runtime limits and discovering synthesizable molecules with desirable properties.
  • Motivation: Unknown objectives and constraints may be noisy, expensive to query, and require solving the problem with as few evaluations as possible.The formulation assumes pointwise access through potentially noise-corrupted black-box queries over the search domain.
  • Motivation: Existing constrained Bayesian optimization methods often lack generality and usually assume joint objective-constraint evaluations.These limitations make them unsuitable for settings where only subsets of functions are evaluated at a time.
  • Contributions: PESC approximates expected information gain about the constrained solution and additively separates information contributions from independently modeled function evaluations.This separability enables acquisition decisions for decoupled objective and constraint evaluations.
  • Contributions: The paper extends an earlier coupled-evaluation description of PESC to broader decoupled-function settings.The extension targets problems in which function evaluations may be separated across tasks and resources.
  • Contributions: The paper develops a general framework for coupled and decoupled tasks, analyzes PESC for resource competition, and introduces partial updates with adaptive switching for mixed fast and slow functions.The partial-update strategy trades accuracy for computation speed and balances Bayesian-optimization overhead against data-collection time.

2. Related Work

Prior constrained Bayesian optimization methods largely build on expected improvement and commonly assume coupled evaluations, while specialized alternatives impose additional assumptions or computational burdens. Decoupled evaluation exposes a sharper failure mode for standard EIC, motivating methods that select locations and tasks more jointly.

  • Expected-improvement methods: Expected Improvement with Constraints weights expected improvement by the posterior probability that all constraints are satisfied.The factorization follows from modeling the objective and constraints with independent Gaussian processes.
  • Expected-improvement methods: Constrained EI methods can become problematic when no point has sufficiently high posterior feasibility, because they may ignore objective information and focus only on finding feasible locations.The cited threshold example uses posterior feasibility above 1−δ, with δ such as 0.05.
  • Alternative acquisition functions: IECI measures the expected reduction in EI across the domain after observing the objective at a candidate point, using a density h(x′).For constrained BO, h(x′) can be set to the probability that the constraints are satisfied at x′.
  • Alternative acquisition functions: IECI can value information from infeasible locations, unlike EIC, but one reported topic-model comparison found EIC outperformed IECI.The distinction arises because IECI considers EI over the whole domain rather than only at the current evaluation location.
  • Alternative acquisition functions: Picheny’s expected-volume method assumes noiseless objective and constraint evaluations and requires nested numerical integration and global optimization over the search domain.This nesting limits its application to small input dimension, whereas PESC approximates its analogous expectation using samples of the global feasible minimizer.
  • Augmented-Lagrangian methods: Augmented-Lagrangian BO requires noiseless constraints for correct parameter updates and, in the cited work, focuses on a known objective.On the referenced synthetic benchmark, PESC and EIC outperform the augmented-Lagrangian approach even when it accesses the true objective.
  • Decoupled evaluations: Standard EIC fails under decoupled evaluations because evaluating only one function cannot simultaneously satisfy its objective-improvement and constraint-feasibility conditions.Under a myopic policy, the resulting EIC acquisition is zero everywhere.
  • Decoupled evaluations: EIC-D first chooses a location with EIC and then selects the task using expected entropy reduction, making its two-stage decision sub-optimal relative to joint location-task selection.The paper positions PESC as avoiding this disadvantage while supporting a wider range of decoupled problems.

3. Decoupled Function Evaluations and Resource Allocation

The framework represents constrained Bayesian optimization through coupled or decoupled tasks mapped to resources, including competitive and non-competitive decoupling. A separable acquisition function supports selecting evaluations across tasks and resources, and Algorithm 1 handles arbitrary combinations of coupling, parallelism, NCD, and CD.

  • Formalization: Functions are grouped into tasks when they require coupled evaluation; functions in different tasks are decoupled and may be evaluated independently.Tasks partition the objective and constraints according to which functions must be evaluated together.
  • Competitive and non-competitive decoupling: Competitive decoupling uses different tasks competing for the same resource, whereas non-competitive decoupling uses different resources for different tasks.The framework distinguishes CD and NCD through the task-resource mapping.
  • Resource allocation: Coupling, parallelism, NCD, and CD are represented through tasks, resources, capacities, and a bipartite task-resource graph.The graph maps tasks to resources, while capacities determine how many evaluations can run concurrently.
  • Acquisition and task selection: The general algorithm requires a separable acquisition function that measures the utility of evaluating any arbitrary subset of functions or any possible task.PESC has this property under independent function models, unlike EIC-D in the general case.
  • General algorithm: Algorithm 1 updates the Bayesian model, maximizes each task’s acquisition function over inputs, and selects the available task with the highest utility.It then submits the evaluation, accounts for pending data, and repeats until termination before returning a feasible final recommendation.
  • General algorithm: Algorithm 1 can solve problems exhibiting any combination of coupling, parallelism, non-competitive decoupling, and competitive decoupling.This generality follows from its task-resource representation and task-specific acquisition functions.

4. Predictive Entropy Search with Constraints (PESC)

PESC approximates expected information gain about the constrained minimizer and decomposes it into function-specific acquisition functions, enabling separate evaluation of objectives and constraints. Its approximations and efficient computation support task-specific acquisition functions, while empirical results assess their accuracy and informativeness.

  • Information-theoretic acquisition: PESC approximates expected information gain about the constrained minimizer by reformulating mutual information between the minimizer and observations.The reformulation exchanges the minimizer and observation variables, producing an expression based on predictive observation entropy conditioned on sampled minimizers.
  • Approximation procedure: The method assumes independent Gaussian-process priors for the objective and constraints and Gaussian noise for black-box measurements.Under this model, the predictive entropy term is computed exactly using GP predictive variances, while the remaining expectation is approximated with samples of the constrained minimizer.
  • Information-theoretic acquisition: A factorization assumption yields a sum of K + 1 function-specific acquisition functions, each measuring the information gained by evaluating one black box.The functions include the objective and constraint functions, and their information values share a common unit based on bits about the minimizer.
  • Approximation procedure: The function-specific acquisition terms are averaged over M samples from the posterior distribution of the constrained minimizer to obtain practical acquisition functions.A toy example shows that the objective can be more informative than a constraint, although this ordering is not universal.
  • Decoupled evaluations: PESC is separable because task-specific acquisition functions for any subset of functions can be constructed from the individual function-specific terms.This separability supports decoupled evaluations while retaining an efficient construction from the individual acquisition functions.
  • Computational considerations: PESC avoids recomputing the acquisition approximation for each model-hyperparameter sample by using joint posterior samples of hyperparameters and the constrained minimizer.Its numerical approximations are reported to perform on par with a rejection-sampling ground-truth method, although numerical global optimization provides no guarantee of finding the true global optimum.

5. PESC-F: Speeding Up the BO Computations

PESC-F accelerates PESC by reusing intermediate computations and adaptively switching between full and partial updates. Its rationality level controls the approximate share of wall-clock time devoted to Bayesian-optimization computations rather than function evaluations, while extremely fast evaluations remain a boundary case.

  • Full and partial computations: The full PESC computation samples GP hyper-parameters, fits the GP, samples x⋆, computes EP solutions, and globally maximizes acquisition functions.These operations define the slow update that partial PESC seeks to shorten.
  • Partial updates: PESC-F reduces computation by reusing GP hyper-parameter, x⋆, and EP samples across iterations instead of recomputing them from scratch.It also updates the Cholesky decomposition in O(N^2) time and reuses previous EP solutions.
  • Adaptive switching: PESC-F switches between slow full updates and fast partial updates to keep Bayesian-optimization computation time approximately proportional to function-evaluation time.The most recent slow-update duration is used because computation time can increase as the dataset grows.
  • Adaptive switching: PESC-F reduces to standard PESC when function evaluations are sufficiently slow relative to the slow Bayesian-optimization computations.This follows from the switching condition based on τnow, τlast, τslow, and γ.
  • Rationality level: The rationality level γ is intended to keep Bayesian-optimization computations at most a fraction γ of function-evaluation time, with proposed values around 0.1–1 corresponding to roughly 50–90% of total time on evaluations.The optimal γ may vary by problem and over the optimization process; PESC-F therefore makes time-constrained, potentially sub-optimal decisions.
  • Boundary case: When function evaluations are faster than even the fast PESC updates, PESC-F cannot maintain the condition that decision-making takes less time than evaluation.The method is therefore not designed to guarantee computation-time dominance in this regime.

6. Empirical Analyses in the Coupled Case

The coupled-case experiments evaluate PESC on synthetic GP-prior problems, a constrained toy problem, and machine-learning hyperparameter tasks. Across these settings, PESC closely approximates a rejection-sampling acquisition function and generally outperforms the compared constrained Bayesian-optimization methods, especially as dimension increases or constraints are noisy.

  • Synthetic functions: PESC’s acquisition-function approximation is quite accurate, with its maximum value very close to the rejection-sampling approximation.Both methods use M = 50 samples from p(x⋆|D) in the illustrated D = 1 case.
  • Synthetic functions: PESC is the best method overall on GP-prior problems with D = 2 and D = 8, while grid-based RSDG becomes significantly worse than PESC when D = 8.RSDG performs similarly to PESC at D = 2, whereas EIC follows PESC and RSDG in the reported ordering.
  • Toy problem: PESC is significantly better than EIC and AL on the constrained toy problem, while EIC is superior to AL.The comparison averages utility gaps over 500 repetitions with different Latin-hypercube initializations.
  • Machine-learning tasks: 7.0 ± 0.6% for PESC versus 49 ± 4% for EIC in ground-truth final-recommendation evaluation of the neural-network task.Each method’s final recommendation was evaluated 50 times across five repeated experiments, treating constraint violations as 100% classification error.
  • Machine-learning tasks: 3300 ± 1200 effective samples for PESC versus 2300 ± 900 for EIC in constrained Hamiltonian Monte Carlo tuning.The comparison uses ten realizations and ground-truth assessment of final recommendations.

7. Empirical Analyses with Decoupled Functions

The experiments assess PESC’s decoupled acquisition functions, competitive task selection, and fast-update trade-offs across synthetic and toy problems. Decoupled PESC accurately identifies informative evaluations, prioritizes important constraints, and improves wall-clock performance when computation and evaluation time are balanced.

  • Accuracy of the PESC Approximation: PESC’s decoupled acquisition functions closely match rejection-sampling approximations, including their maxima.The approximation remains similar after three additional constraint observations.
  • Accuracy of the PESC Approximation: Additional constraint observations can reduce the value of evaluating that constraint and shift the most informative evaluation to the objective.In the reported case, the objective is most informative near x ≈ 0.25.
  • Comparing Coupled and Decoupled PESC: With three parallel task evaluations, competitive decoupling selects evaluations across objective and constraint tasks rather than enforcing a shared input.The comparison includes Coupled, NCD, CD, CD-F, and EIC-CD.
  • Comparing Coupled and Decoupled PESC: CD-F and CD perform best in the parallel toy experiment, while fast PESC-F updates incur no significant performance loss relative to CD.The result is based on average utility gaps across 500 repetitions.
  • Comparing Coupled and Decoupled PESC: CD-F adapts task allocation to constraint relevance, avoiding evaluations of uninteresting tasks when they may be more expensive.Its allocation changes depending on whether constraint c1 is active at the solution.
  • Performance of PESC-F with Respect to Wall-clock Time: For wall-clock performance, reducing γ from ∞ to 0.1 improves PESC-F, but γ = 0 performs significantly worse because excessive fast updates produce suboptimal decisions.The experiments evaluate objective f instantaneously, c1 in 2 seconds, and c2 in 1 minute.
  • Performance of PESC-F with Respect to Wall-clock Time: The coupled approach wastes time repeatedly evaluating the slow, less informative constraint c2, whereas decoupled PESC-F allocates evaluations more selectively.BO computation time decreases monotonically as γ decreases, and the reported optimal γ is close to 0.1.

8. Conclusions and Future Work

The framework handles coupled and decoupled constrained Bayesian optimization, including resource competition and heterogeneous evaluation costs. PESC provides separable information-based acquisition, while PESC-F trades computational accuracy for wall-clock efficiency.

  • Framework: The framework represents coupled functions as tasks and supports competitive or non-competitive decoupled evaluation across resources.Tasks contain functions requiring joint evaluation, while different tasks may run independently and either compete for resources or run in parallel.
  • PESC: PESC uses a factorized acquisition function that adds information contributions across the functions selected for evaluation.This makes PESC applicable to constrained Bayesian optimization with decoupled evaluation.
  • Empirical findings: Decoupled PESC achieves state-of-the-art performance in coupled problems and significantly outperforms coupled PESC under competitive decoupling.Under competition, it selects more informative functions and avoids evaluations unlikely to improve the current solution estimate.
  • PESC-F: PESC-F automatically switches between faster approximate and slower accurate operations to balance Bayesian optimization computation against data collection.Experiments measured by wall-clock time in a competitive-decoupling scenario found PESC-F significantly better than the original PESC.
  • Future work: The authors identify multi-objective optimization, multi-resource tasks, richer bounded-rationality levels, alternative models, and theoretical analysis as future directions.The current implementation is available in the PESC branch of Spearmint.

Appendix A. The Expectation Propagation Method Used by PESC

PESC uses expectation propagation to approximate non-Gaussian factors in its posterior representation. The appendix separates factors independent of the candidate location from the factor that depends on it, enabling reusable computations.

  • EP approximation: Expectation propagation adjusts a Gaussian approximation to the non-Gaussian factors used by PESC.The approximation is constructed from the posterior over the objective and constraint values.
  • Represented variables: The appendix represents the optimization state using objective and constraint values at previously evaluated locations and a sampled solution location.Replacing the continuous domain with the finite set Z restricts the represented values to evaluated objective locations.
  • Computational structure: PESC separates the factor depending on the acquisition candidate x from factors that do not depend on x.Factors independent of x can be approximated and reused when evaluating the acquisition function at many candidate locations.

A.1 Approximating the Non-Gaussian Factors that do not Depend on x

For factors independent of x, expectation propagation forms Gaussian approximations from the posterior and constraint-related factors, then updates their parameters by moment matching. The resulting parameters are fixed before candidate-dependent calculations.

  • Gaussian approximation: The approximation combines the Gaussian posterior with Gaussian approximations to non-Gaussian factors, yielding a Gaussian q(f, c1, . . . , cK).Products of Gaussian factors remain Gaussian, with parameters obtained from corresponding means, covariances, and natural parameters.
  • Parameters: The approximation encodes posterior means, covariances, noise variances, and cross-covariances for objective and constraint values at observed or sampled locations.These quantities determine the Gaussian factors associated with the objective and each constraint.
  • Parameter updates: Expectation propagation updates the objective and constraint factor parameters by minimizing Kullback-Leibler divergences and matching first and second moments.The appendix defines cavity distributions, marginalizes variables, and uses derivatives of normalization constants for these updates.
  • Numerical robustness: Second partial derivatives are used in selected updates for numerical robustness.This choice appears in the updates for constraint-related parameters and sampled-solution factors.

A.2 Approximating the Non-Gaussian Factor that Depends on x

After the x-independent EP updates converge, PESC approximates the remaining candidate-dependent factor using Gaussian marginals over the candidate objective and constraint values. These marginals provide the quantities used to evaluate the acquisition function.

  • Candidate-dependent update: EP first converges on the factors independent of x, after which PESC approximates the candidate-dependent factor Ψ(x).This ordering allows the x-independent computations to be completed before evaluating arbitrary acquisition candidates.
  • Marginalization: The candidate-dependent calculation marginalizes the Gaussian approximation to the variables on which Ψ(x) depends: γ(f) and c1(x), . . . , cK(x).Here γ(f) contains the objective at the candidate and sampled solution locations.
  • Reuse across candidates: Stored means and covariance matrices from the converged EP approximation are reused to compute candidate-specific moments for arbitrary x.These moments include the objective and constraint marginal means and variances.
  • Acquisition evaluation: The resulting means and variances are obtained from the normalization constant and used in PESC’s acquisition function.Equations (58)–(61) provide the EP output used in Eq. (20).

Appendix B. Implementation Considerations

This appendix section provides practical implementation details for PESC.

  • The appendix focuses on PESC’s practical implementation.
  • PESC is described through implementation considerations rather than its theoretical formulation.
  • The section supplies details intended to guide implementation of PESC.

B.1 Initialization, Convergence of EP and Parallel EP Updates

The implementation initializes EP’s approximate factors, stops when parameter changes fall below 10^-4, and uses parallel updates to speed convergence.

  • Initialization: All approximate factors eΓ(x_j^f) are initialized to zero.
  • Convergence of EP: EP stops when absolute changes in means and covariance matrices fall below 10^-4 for the specified elements of f and the constraints.
  • Parallel EP Updates: Approximate factors are updated in parallel, while q is updated once per iteration after all factors are refined.

B.2 EP with Damping

EP uses damping to improve convergence, gradually reduces the damping parameter, and retries iterations with a smaller step when covariance matrices become invalid.

  • Damping: Damping replaces each KL-minimizing factor update with a damped new factor value.
  • Damping: The damping parameter ϵ starts at 1, meaning no damping, and is multiplied by 0.99 after each iteration.
  • Damping: If covariance matrices become non-positive-definite, ϵ is halved and the EP iteration is repeated.

B.3 Sampling x⋆in PESC

PESC samples x⋆ by approximating the objective and constraint GPs with finite-basis Bayesian linear models, then optimizing sampled functions.

  • Sampling x⋆: The objective and constraint GPs are approximated with finite basis functions to obtain analytic approximate posterior samples.
  • Sampling x⋆: Approximate GP posterior samples are generated by sampling the linear model posterior and replacing f and the constraints in the optimization problem.
  • Sampling x⋆: The finite-basis GP approximation is a Bayesian Gaussian linear model built from a collection of basis functions.

B.4 Cholesky Update in PESC-F

PESC-F accelerates fast Bayesian optimization by reusing the previous GP hyperparameters and updating the kernel factorization incrementally. The same rank-one Cholesky update also applies to Bayesian optimization methods that do not update GP hyperparameters every iteration.

  • PESC-F keeps GP hyperparameters, including length scales, fixed during fast BO computations.
  • A new kernel-matrix row and column can therefore be incorporated through a rank-one Cholesky update.This avoids recomputing the full O(N^3) decomposition and can significantly speed computation as N grows.
  • The same update applies to any Bayesian optimization method that does not update GP hyperparameters at every iteration.
Loading 1511.09422v2…