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

Constrained Bayesian optimization is difficult when objective and constraint functions are evaluated independently. The paper introduces PESC, an information-based separable acquisition function, and reports strong performance in coupled and decoupled settings, while PESC-F improves wall-clock performance through adaptive computation.

  • Problem

    Existing constrained Bayesian optimization methods largely address coupled evaluations, making decoupled objective and constraint evaluations difficult to handle.

    Source: §3 · p. 8

  • Method

    PESC approximates expected information gain with an additive acquisition function, while PESC-F adaptively switches between fast approximate and slow accurate updates.

    Source: §1 · p. 3, §8 · pp. 39–40

  • Results

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

    Source: §8 · p. 39

  • Takeaways & Limitations

    PESC provides a unified information-based approach for constrained Bayesian optimization across coupled and decoupled evaluation settings.

    Source: §8 · p. 39

    PESC-F makes sub-optimal decisions under time constraints, and selecting its optimal rationality level remains future work.

    Source: §5.2 · p. 25

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 targets expensive black-box global optimization with unknown, possibly noisy constraints, including settings where objectives and constraints can be evaluated independently. It introduces PESC, an information-based method whose additive acquisition function supports decoupled evaluations, and develops partial updates for balancing optimization overhead against evaluation cost.

Problem setting

  • The problem is to minimize an unknown, potentially noisy black-box objective over a bounded domain while satisfying multiple black-box constraints using as few queries as possible.The objective and each constraint are defined over the full search space and can only be evaluated pointwise through expensive queries.Source: §1 · p. 2

Limitations of prior methods

  • Existing constrained Bayesian optimization methods can lack generality and struggle with decoupled evaluations because their acquisition functions assume joint evaluations and require a best feasible incumbent.The incumbent may not exist when no point satisfies the constraints with high probability.Source: §1 · p. 3

PESC

  • PESC approximates expected information gain about the constrained optimum and additively separates the information contributions of independently modeled objective and constraint evaluations.This additive acquisition property enables efficient optimization when subsets of functions are evaluated independently.Source: §1 · p. 3

Decoupled optimization

  • The paper develops a taxonomy and general algorithm for constrained Bayesian optimization with tasks that may be coupled internally but decoupled across functions or resource-competing groups.It analyzes PESC in decoupled settings, including objectives and constraints competing for the same computational resource.Source: §1 · pp. 3–4

Computational efficiency

  • A faster, less accurate partial PESC update and adaptive switching between partial and full updates balance Bayesian optimization overhead with black-box evaluation time.This is intended for mixed settings containing both fast and slow decoupled functions.Source: §1 · p. 4

2. Related Work

Prior constrained Bayesian optimization methods extend expected improvement, integrated improvement, expected-volume reduction, or augmented-Lagrangian optimization, but face feasibility, dimensionality, noise, or decoupling limitations. In decoupled evaluations, standard EIC is identically zero, while EIC-D uses a suboptimal two-stage decision process.

2.1 Expected Improvement with Constraints

  • EIC weights expected improvement by constraint-satisfaction probability, but its incumbent may be undefined, prompting objective-ignoring feasibility search that can waste objective data.EIC was proposed by Schonlau et al. (1998) and revisited by Parr (2013), Snoek (2013), Gardner et al. (2014), and Gelbart et al. (2014).Source: §2.1 · p. 5

2.2 Integrated Expected Conditional Improvement

  • IECI values evaluations by their expected reduction of improvement across the domain, allowing potentially informative infeasible evaluations, although EIC outperformed it on a topic-model problem.IECI defines the incumbent using the lowest posterior objective mean over the entire domain, even if that location is infeasible.Source: §2.2 · pp. 5–6

2.3 Expected Volume Minimization

  • Expected-volume minimization integrates improvement and feasibility probabilities, but its nested grid integrations and optimization restrict practical use to small input dimensions.Picheny assumes noiseless objective and constraint evaluations and sets the incumbent to the best feasible value observed, or +∞ when none exists; PESC approximates its analogous expectation by sampling the feasible minimizer.Source: §2.3 · p. 6

2.4 Modeling an Augmented Lagrangian

  • The augmented-Lagrangian approach fits a GP to observed augmented-Lagrangian values and selects evaluations using expected improvement while iteratively updating penalties and multipliers.It assumes noiseless constraints for correct parameter updates, focuses on known objectives, and was outperformed by PESC and EIC on the cited synthetic benchmark even when given the true objective.Source: §2.4 · pp. 6–7

2.5 Existing Methods for Decoupled Evaluations

  • Standard EIC fails with decoupled evaluations because evaluating one function cannot simultaneously improve the objective and satisfy constraints, making its utility zero everywhere.EIC-D addresses this with separate location and task selection, but the two-stage process is suboptimal and less general than PESC.Source: §2.5 · p. 7

3. Decoupled Function Evaluations and Resource Allocation

The section formalizes constrained Bayesian optimization with coupled or decoupled tasks, resource competition, parallelism, and task-specific capacities. It introduces a separable-acquisition algorithm that selects evaluations across available resources and incorporates evaluation costs.

3. Decoupled Function Evaluations and Resource Allocation

  • Decoupled evaluation avoids paying for expensive objective computations before faster constraints can identify locations likely to be feasible, while artificial coupling becomes inefficient as cost differences grow.The motivating speech-recognition example evaluates prediction time without training the network, then reserves costly accuracy evaluations for promising locations.Source: §3 · pp. 8–9

3.1 Competitive Versus Non-competitive Decoupling and Parallel BO

  • Competitive decoupling uses a shared resource, whereas non-competitive decoupling uses different resources for concurrent evaluation; NCD is closely related to parallel Bayesian optimization but permits different pending and next tasks.Parallel BO has a single task, while NCD can have multiple task types evaluated concurrently.Source: §3.1 · p. 9

3.2 Formalization of Constrained Bayesian Optimization Problems

  • The framework partitions functions into coupled tasks and represents task-resource compatibility with a bipartite graph whose resources have execution capacities.This representation covers coupled evaluations, competitive and non-competitive decoupling, and parallel Bayesian optimization, while excluding tasks requiring multiple resources.Source: §3.2 · pp. 9–10

3.3 A General Algorithm for Constrained Bayesian Optimization

  • PESC is separable when functions are modeled independently, allowing utility to be computed for individual tasks, whereas EIC-D of Gelbart et al. (2014) is not separable in the general case.This separability enables the general algorithm to evaluate arbitrary subsets of functions and supports decoupled evaluations.Source: §3.3 · pp. 10–11
  • Algorithm 1 checks available resources, updates the Bayesian model with newly collected observations, and selects the task and input with highest utility among permitted evaluations; it handles coupling, parallelism, NCD, and CD.For pending evaluations, it can use virtual data from the model’s predictive distribution for acquisition selection, then return the input attaining the lowest expected objective value subject to constraints satisfied with posterior probability larger than 1 −δ.Source: §3.3 · pp. 11–12

3.4 Incorporating Cost Information

  • When task costs vary, acquisition values can be penalized by expected evaluation cost, modeled with an additional Gaussian process for each task or fixed a priori.Learning costs increases the total number of Gaussian-process models to |F| + |T|.Source: §3.4 · p. 12

4. Predictive Entropy Search with Constraints (PESC)

This section develops PESC as an additive information-gain acquisition function for constrained optimization with independently evaluable objective and constraint functions. It presents the approximations and efficient hyperparameter marginalization used to compute PESC in coupled and decoupled settings, and relates it to PES and rejection-sampling ground truth.

4.1 The PESC Acquisition Function

  • The factorization assumption makes PESC additive across functions, enabling meaningful information-based comparisons and acquisition functions for arbitrary subsets of objective and constraint evaluations.Each function-specific acquisition is measured in common bits of information about the minimizer and serves as a building block for decoupled evaluations.Source: §4 · p. 13, §4.1 · pp. 15–16

4. Predictive Entropy Search with Constraints (PESC)

  • PESC reformulates expected information gain about x⋆ as predictive-entropy mutual information, extending PES to vector-valued objective and constraint evaluations.The reformulation is α(x) = H[y | D, x] − E_x⋆|D[H[y | D, x, x⋆]], which is easier to approximate than the original entropy expression.Source: §4 · pp. 13–14

4.1 The PESC Acquisition Function

  • Under independent Gaussian-process priors with Gaussian observation noise, PESC computes the predictive-entropy term exactly and approximates the conditional term using samples of x⋆ and Gaussian approximations.The x⋆ samples come from posterior function samples followed by constrained optimization; conditional independence of evaluation components guarantees separability.Source: §4.1 · p. 14
  • For any coupled task evaluating a subset of functions, PESC combines the corresponding function-specific acquisition terms to construct an efficient, separable task-specific acquisition function.This lets the general algorithm evaluate arbitrary subsets while reusing the individual acquisition functions as building blocks.Source: §4.1 · pp. 15–16

4.2 How to Compute the Gaussian Approximation to p(yi|D, x, xj ⋆)

  • Expectation propagation approximates the intractable conditional distribution by enforcing feasibility and optimality of sampled x⋆, while replacing continuous search spaces with finite evaluated locations.The finite-set approximation is expected to become more accurate as more objective data are collected.Source: §4.2 · pp. 18–19
  • PESC reduces EP cost by separating computations depending on D and x⋆ from those depending on x, performing expensive computations once and reusing them across candidate locations.Without this split, EP would need to be rerun for every location at which the acquisition function is evaluated.Source: §4.2 · p. 19

4.3 Efficient Marginalization of the Model Hyper-parameters

  • In practice, GP amplitudes, length-scales, and black-box noise variances are unknown and must be estimated from data, for example by sampling their posterior distribution.This begins the proposed treatment of model hyper-parameter uncertainty.Source: §4.3 · p. 19
  • Hyperparameter marginalization replaces a loop over x⋆ samples with a loop over joint (Θ, x⋆) samples, adding no computational complexity.PESC averages function-specific acquisition functions over posterior hyperparameter samples rather than averaging predictive distributions before computing information gain.Source: §4.3 · p. 20

4.4 Computational Complexity

  • In the coupled setting, PESC has complexity O(MKN^3), while decoupled costs depend separately on objective and constraint evaluation counts; hyperparameter sampling does not change overall complexity.The coupled cost reflects EP iterations over K constraints and M constrained-minimizer samples, whereas decoupled covariance matrices scale with the corresponding observation counts.Source: §4.4 · pp. 20–21

4.5 Relationship between PESC and PES

  • With K = 0, PESC applies to unconstrained optimization and resembles PES, but it uses indicator functions to impose the minimum-value condition more principledly.PESC does not enforce zero-gradient or positive-definite-Hessian conditions because constrained optima may lie on feasible-region boundaries.Source: §4.5 · p. 21

4.6 Summary of the Approximations Made in PESC

  • PESC approximates expected entropy reduction through Monte Carlo minimizer samples, finite candidate locations, factorized EP, and acquisition marginalization over hyperparameter samples.The ideal predictive-distribution marginalization is considered too computationally expensive, and numerical global optimization introduces additional error without guarantees of finding the true optimum.Source: §4.6 · pp. 21–22
  • PESC’s practical approximations, excluding hyperparameter marginalization, perform on par with a ground-truth method based on rejection sampling.The implementation uses Monte Carlo sampling, finite-basis GP draws, a finite candidate set, expectation propagation, and separated computations for efficient acquisition evaluation.Source: §4.6 · pp. 21–22

5. PESC-F: Speeding Up the BO Computations

PESC-F reduces PESC’s computational overhead by reusing previous computations and loosening optimization precision, then adaptively switches between fast and slow updates to match function-evaluation times. Its rationality level controls this tradeoff, while its usefulness is greatest when evaluation time lies between fast and slow update times.

5. PESC-F: Speeding Up the BO Computations

  • PESC-F accelerates PESC by reusing hyper-parameter, x⋆, and EP samples or solutions, applying fast Cholesky updates, and using coarser acquisition-optimization tolerances and fewer restarts or grid points.These approximations reduce the costs of posterior sampling, EP computation, and acquisition maximization after each new data point.Source: §5 · p. 23

5.1 Choosing When to Run the Fast or the Slow Version

  • PESC-F switches between full and partial computations using recent slow-update duration and elapsed time, reverting to PESC for slow evaluations while favoring fast updates for fast evaluations.The switching rule uses the rationality level γ; the most recent slow-update duration is preferred because computation costs may increase with dataset size.Source: §5.1 · pp. 23–24

5.2 Setting the Rationality Level in PESC-F

  • The rationality level γ approximately bounds BO-computation time relative to function-evaluation time; proposed values from 0.1 to 1 correspond to roughly 50–90% of total time spent evaluating functions.Choosing γ is problem- and stage-dependent, and the resulting time-constrained decisions constitute a bounded-rationality approximation.Source: §5.2 · pp. 24–25

5.3 Bridging the Gap Between Fast and Slow Computations

  • PESC-F is most useful when τfast < τeval < τslow and its cost-control ideas can extend to other constrained or unconstrained acquisition functions.If evaluations are faster than fast updates, even PESC-F can violate the desired timing condition; bridging cheap- and expensive-function optimization remains future work.Source: §5.3 · p. 25

6. Empirical Analyses in the Coupled Case

The coupled-case experiments assess PESC’s approximation accuracy and optimization performance on synthetic, analytic, neural-network, and HMC problems. Across these settings, PESC generally outperforms competing methods, although HMC results show no significant difference from EIC under noisy evaluation.

6.1 Assessing the Accuracy of the PESC Approximation

  • PESC closely matches the rejection-sampling acquisition-function approximation and slightly outperforms RS in utility-gap experiments, while both outperform RSDG.PESC’s maximum acquisition value is very close to RS’s, and its grid-free construction may explain the slight performance advantage.Source: Figure 3 · p. 26, §6.1 · p. 27

6.2 Synthetic Functions in 2 and 8 Input Dimensions

  • PESC is the best method on synthetic GP-prior problems in D = 2 and D = 8, while grid-based RSDG deteriorates substantially at D = 8.RSDG performs similarly to PESC at D = 2 but is significantly worse at D = 8, whereas EIC ranks behind both methods.Source: §6.2 · pp. 27–28, Figure 4 · p. 28

6.3 A Toy Problem

  • PESC is significantly better than EIC and AL on the constrained toy problem, while EIC outperforms AL overall.The problem has two local minimizers, one global minimizer, and an active constraint c1 at the global solution, making learning c1 central.Source: §6.3 · pp. 28–29, Figure 5 · p. 29

6.4 Finding a Fast Neural Network

  • 7.0 ± 0.6% versus 49 ± 4%: PESC achieves a much lower validated neural-network error rate than EIC under the 2 ms prediction-time constraint.The scores average 50 final-recommendation evaluations across five repeated experiments, treating constraint violations as 100% classification error.Source: §6.4 · p. 30, Figure 6 · p. 30

6.5 Tuning Markov Chain Monte Carlo

  • 3300 ± 1200 versus 2300 ± 900 effective samples: PESC and EIC do not differ significantly when tuning HMC under convergence, stability, and time constraints.The ground-truth assessment indicates that apparent differences in Fig. 6(b) are overly optimistic because stochastic initialization and execution make diagnostic outcomes noisy.Source: Figure 6 · p. 30, §6.5 · p. 31

7. Empirical Analyses with Decoupled Functions

In decoupled optimization, PESC closely matches rejection-sampling acquisition estimates and competitive decoupling outperforms coupled alternatives by allocating evaluations according to task usefulness. PESC-F further improves wall-clock performance by balancing BO computation against task-evaluation time, with an intermediate rationality level performing best in the studied setup.

7.1 Accuracy of the PESC Approximation

  • PESC’s decoupled acquisition functions closely match rejection-sampling approximations, shifting the highest-information evaluation from constraint c1 near x ≈0.3 to the objective near x ≈0.25 after additional constraint observations.Both methods use M = 50 samples; as constraint information increases, the optimizer turns attention from the constraint to the objective.Source: §7.1 · p. 32, Figure 7 · p. 32

7.2 Comparing Coupled and Decoupled PESC

  • Across 500 repetitions, CD and CD-F perform best, while EIC-CD performs worse and NCD performs about the same as Coupled; CD-F’s fast updates incur no significant loss.The comparison uses three parallel evaluations and average utility gap; EIC-CD’s two-stage decision process is suboptimal, whereas NCD’s lack of task competition limits the benefit of decoupling.Source: §7.2 · p. 34, Figure 8 · p. 34
  • CD-F evaluates c1 much more frequently when it is active at the solution and much less when it is inactive, showing that PESC’s task-specific acquisitions measure evaluation usefulness.When c1 is inactive, evaluations decrease after the constraint is sufficiently unlikely to be active; in the toy problem, c1 is more informative than f or c2.Source: §7.2 · pp. 34–36

7.3 Performance of PESC-F with Respect to Wall-clock Time

  • With one nonparallel resource and task durations of 0, 2 seconds, and 1 minute, every PESC-F variant outperforms Coupled, while γ = 0.1 outperforms γ = ∞, 1, and 0 in wall-clock performance.Reducing γ initially shifts time from BO computations to data collection, but γ = 0 makes suboptimal decisions by performing too many fast updates and too few informative c1 evaluations.Source: §7.3 · p. 36, Figure 10 · p. 37
  • The optimal γ in the wall-clock experiment is close to 0.1, reflecting a favorable ratio between BO-computation time and task-evaluation time.BO-computation time decreases monotonically as γ decreases, but eliminating slow computations prevents learning that c2 is uninformative.Source: §7.3 · pp. 36, 38, Table 1 · p. 38

8. Conclusions and Future Work

The paper presents PESC as a separable information-based acquisition function for constrained Bayesian optimization with coupled or decoupled evaluations and resource competition. Experiments support its effectiveness, while PESC-F addresses computation time and several extensions remain future work.

General framework

  • The framework represents tasks and resources with a bipartite graph and uses separable acquisition functions to select arbitrary subsets of functions for evaluation.It supports coupled tasks, independently evaluable tasks, competitive decoupling, non-competitive decoupling, and parallel Bayesian optimization as a special case.Source: §8 · pp. 38–39

PESC

  • PESC uses a factorization assumption to make approximate information gain additive across evaluated functions, enabling constrained Bayesian optimization with decoupled evaluation.At each iteration, it selects locations expected to provide the greatest information about the optimization solution.Source: §8 · p. 39

Empirical evaluation

  • PESC achieves state-of-the-art results for coupled constrained Bayesian optimization and significantly outperforms coupled PESC under competitive decoupling.Under non-competitive decoupling, coupled and decoupled PESC perform similarly; the main benefit of decoupling comes from allocating evaluations unevenly across tasks.Source: §8 · p. 39

Bounded rationality

  • PESC-F significantly outperforms original PESC in wall-clock experiments by switching between fast approximate and slow accurate computations using a rationality level.This targets settings where informative tasks evaluate as quickly as Bayesian optimization computations.Source: §8 · pp. 39–40

Future work

  • Future work includes multi-resource and time-dependent task allocations, potentially requiring temporal planning and greedy decisions over resource allocations.The proposed extension generalizes single-resource tasks through alternative resource-allocation sets.Source: §8 · p. 40
  • Further research could use more than two bounded-rationality levels, alternative accuracy-cost modeling trade-offs, and theoretical analysis of PESC.The paper also notes straightforward applicability to multi-objective Bayesian optimization, with an existing multi-objective PES extension (Hern´andez-Lobato et al., 2016).Source: §8 · p. 40

Appendix A. The Expectation Propagation Method Used by PESC

Appendix A describes how PESC uses expectation propagation (EP) to Gaussian-approximate non-Gaussian factors after discretizing the input domain to previously evaluated locations and candidate points. It also reuses the candidate-independent EP approximation across acquisition evaluations to reduce computation.

Expectation propagation

  • EP approximates all non-Gaussian factors in PESC with Gaussians after replacing the infinite input set with a finite set of evaluated and candidate locations.The finite set includes locations where the objective has already been evaluated, the constrained optimum, and the prospective evaluation point.Source: Appendix A · p. 41

Factorization

  • PESC separates the candidate-dependent factor Ψ(x) from candidate-independent factors Γ(x_j) before applying EP.The candidate-independent factors are associated with previously evaluated function values and other locations in the finite approximation.Source: Appendix A · p. 41

Computational reuse

  • Reusing the EP approximation for candidate-independent factors across acquisition evaluations produces large speedups when evaluating many candidate locations.PESC computes and stores this approximation once, then recomputes only the remaining candidate-dependent factors for each x.Source: Appendix A · p. 41

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

The section approximates non-Gaussian factors with Gaussian terms using expectation propagation (EP). Because the posterior over the independent Gaussian-process functions is Gaussian, the resulting approximation remains Gaussian and is updated by cavity-based moment matching.

Gaussian approximation

  • Independent Gaussian-process posteriors and Gaussian approximations to the non-Gaussian factors yield a Gaussian approximation q(f, c1, ..., cK).The approximation is formed by multiplying the posterior with Gaussian replacements for the relevant factors and applying products-of-Gaussians identities.Source: §A.1 · pp. 42–43

Expectation propagation

  • EP adjusts the approximate-factor parameters by minimizing KL divergence between each tilted factor and its cavity distribution.Cavity distributions are obtained by dividing the global Gaussian approximation by the factor currently being updated.Source: §A.1 · pp. 43, 45

Moment matching

  • The updates match first and second moments of the tilted distributions, then recover Gaussian natural parameters using ratios of Gaussian distributions.For both factor types, the required moments derive from derivatives of the normalization constant, with Gaussian marginalization reducing the computations to relevant variables.Source: §A.1 · pp. 44–45

Numerical robustness

  • Second partial derivatives replace first derivatives in the EP updates for numerical robustness, for both constraint-related and objective-related approximate factors.The same procedure is applied analogously to update the parameters of the factors involving constraints at observed locations and at the sampled optimum.Source: §A.1 · pp. 44, 46

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

After EP converges, the method approximates the x-dependent factor Ψ(x) with Gaussian quantities while reusing EP results computed independently of x. These approximations provide the marginal means and variances needed to evaluate PESC’s acquisition function.

EP approximation

  • EP operations converge to Gaussian approximations that can be computed independently of the candidate location x.This permits the EP computation to be performed before evaluating PESC’s acquisition function at specific locations.Source: §A.2 · p. 46

Approximating Ψ(x)

  • The method replaces the exact Γ factors with their Gaussian approximations and marginalizes q to variables on which Ψ(x) depends: γ(f) and c1(x), . . . , cK(x).The resulting distribution is then used to construct a Gaussian approximation to the x-dependent factor.Source: §A.2 · p. 46

Efficient evaluation

  • Stored EP means and covariance matrices efficiently yield the means, variances, and covariance matrix for γ(f), c1(x), . . . , cK(x) at arbitrary x.These quantities are computed using prior cross-covariances and covariance matrices for the function values represented in q.Source: §A.2 · p. 46

Acquisition evaluation

  • The resulting Gaussian approximation produces marginal means and variances for f(x), c1(x), . . . , cK(x), which are used in Eq. (20) to evaluate PESC’s acquisition function.The moments are obtained from the normalization constant using the stated expectation-propagation formulas.Source: §A.2 · pp. 47–48

Appendix B. Implementation Considerations

This appendix discusses practical implementation details for PESC.

Appendix B. Implementation Considerations

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

EP initializes all approximate factors to zero and stops when changes in selected means and covariance matrices fall below 10^-4. Parallel factor updates accelerate convergence by updating q once per iteration.

Initialization

  • EP initializes all approximate factors eΓ(x_j^f) to zero.Source: §B.1 · p. 48

Convergence

  • EP stops when absolute changes in selected means and covariance matrices are below 10^-4.The criterion applies to the first N_1 + 1 elements of f and c_1, ..., c_K according to q.Source: §B.1 · p. 48

Parallel EP Updates

  • Parallel approximate-factor updates speed convergence by updating q only once per iteration after all factors are refined.Source: §B.1 · p. 48

B.2 EP with Damping

EP uses damping to improve convergence by replacing approximate-factor updates with damped values, applying the same procedure to both eΨ(x_n) and eΓ(x_j⋆). The damping parameter is scheduled downward and halved when covariance matrices become non-positive-definite.

B.2 EP with Damping

  • Damping improves EP convergence by replacing the KL-minimizing approximate factor with a damped new value.The same damping procedure is applied to eΨ(x_n) and eΓ(x_j⋆).Source: §B.2 · p. 48
  • The damping parameter ϵ starts at 1, meaning no damping, and is multiplied by 0.99 at each iteration.Source: §B.2 · p. 48
  • If an EP step makes a covariance matrix in q or a cavity distribution non-positive-definite, ϵ is halved and the iteration is repeated.This safeguard addresses excessively large step sizes associated with large ϵ.Source: §B.2 · p. 49

B.3 Sampling x⋆in PESC

PESC samples x⋆ from its posterior by approximating objective and constraint GPs with finite basis expansions, then optimizing each sampled problem to obtain a feasible candidate. The implementation combines grid initialization, MMA refinement, and efficient low-rank Gaussian sampling to reduce computational cost.

B.3 Sampling x⋆in PESC

  • PESC samples objective and constraint GP posteriors with finite basis approximations, then solves the resulting sampled constrained optimization problem.It uses a Bayesian Gaussian linear model and samples its posterior conditioned on observed data.Source: §B.3 · p. 49
  • Each sampled problem is initialized from the best feasible point on a uniform grid augmented with previous evaluation locations, then refined using MMA.The implementation uses a grid of size 10^3, 10^3 basis functions, and NLopt tolerance 10^-6 in scaled input-space units.Source: §B.3 · p. 49
  • Efficient posterior sampling costs O(N^2M) instead of naive O(M^3), yielding orders-of-magnitude speedups when M = 10^3 and typically N < 100.The speedup comes from exploiting a covariance matrix formed by a low-rank matrix plus a diagonal matrix.Source: §B.3 · p. 49

B.4 Cholesky Update in PESC-F

PESC-F accelerates fast Bayesian optimization by reusing the unchanged GP kernel structure and applying a rank-one Cholesky update when a new observation is added. This avoids the main O(N^3) decomposition bottleneck and can benefit other methods that do not update GP hyperparameters every iteration.

B.4 Cholesky Update in PESC-F

  • PESC-F reuses the previous Cholesky decomposition and performs a rank-one update because fixed GP hyperparameters leave the kernel matrix changed only by one row and column.During fast BO computations, GP hyperparameters, particularly length scales, remain unchanged from the previous iteration.Source: §B.4 · p. 49
  • Avoiding the O(N^3) kernel-matrix decomposition removes the main GP-based Bayesian optimization bottleneck and can substantially speed PESC-F as N grows.Source: §B.4 · p. 49
  • The rank-one Cholesky update also applies to Bayesian optimization methods that do not update GP hyperparameters at every iteration.The technique is described by Gill et al. (1974) and is commonly used in Bayesian optimization, including Osborne (2010).Source: §B.4 · p. 50

Related papers

Loading 1511.09422v2…