PaperlayerView exact revision on arXiv

Source-linked AI summary

Predictive Entropy Search for Bayesian Optimization with Unknown Constraints

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

arXiv:1502.05312v2stat.ML

TL;DR

Constrained Bayesian optimization must handle expensive, noisy black-box objectives and constraints despite failure modes in EI-based methods. The paper introduces PESC, an information-based acquisition function that approximates information gain about the constrained minimizer. PESC performs favorably across constrained problems and avoids the cited infeasibility and decoupling pathologies, although its EP implementation can be numerically unstable.

  • Problem

    Expensive, noisy black-box constrained optimization is difficult for EI-based methods because a feasible incumbent may not exist and decoupled evaluations can make expected improvement zero.

  • Method

    PESC approximates expected information gain about the constrained minimizer using samples of the minimizer and Gaussian approximations computed with Expectation Propagation.

  • Results

    PESC outperforms current methods such as EIC and AL over a variety of problems and performs about equally well to a ground-truth rejection-sampling method.

  • Takeaways & Limitations

    PESC provides a unified approach that naturally handles decoupled constraints without additional computational cost or the pathologies discussed for EI-based methods.

  • Takeaways & Limitations

    PESC is relatively difficult to implement because its Expectation Propagation approximation often leads to numerical instabilities.

Abstract

from arXiv · show

Unknown constraints arise in many types of expensive black-box optimization problems. Several methods have been proposed recently for performing Bayesian optimization with constraints, based on the expected improvement (EI) heuristic. However, EI can lead to pathologies when used with constraints. For example, in the case of decoupled constraints---i.e., when one can independently evaluate the objective or the constraints---EI can encounter a pathology that prevents exploration. Additionally, computing EI requires a current best solution, which may not exist if none of the data collected so far satisfy the constraints. By contrast, information-based approaches do not suffer from these failure modes. In this paper, we present a new information-based method called Predictive Entropy Search with Constraints (PESC). We analyze the performance of PESC and show that it compares favorably to EI-based approaches on synthetic and benchmark problems, as well as several real-world examples. 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 formulates constrained global optimization when objective and constraint functions are expensive, noisy black boxes. It introduces PESC, which selects evaluations by approximating information gain about the constrained minimizer.

  • Problem formulation: The goal is to find the global minimum of an objective over a bounded domain while satisfying non-negativity constraints.The problem is formalized as minimizing f(x) over x ∈ X subject to c_k(x) ≥ 0 for all constraints.
  • Problem formulation: The objective and constraints are unknown, noise-corrupted, and accessible only through expensive pointwise queries.The optimization seeks a solution using as few queries as possible.
  • Bayesian optimization: Bayesian optimization builds models of the unknown objective and constraints, then uses an acquisition function to represent the utility of evaluating each input.
  • Proposed approach: PESC extends Predictive Entropy Search by approximating expected information gain about the constrained minimizer.The paper presents PESC as applicable to a wider variety of constrained problems than existing methods.

2. Related Work and Challenges

Prior constrained Bayesian optimization methods largely extend expected improvement, but they face feasibility, decoupling, and computational difficulties. PESC is presented as avoiding these pathologies by operating without a current feasible incumbent and separating objective and constraint tasks.

  • EI-based approaches: Most prior approaches use expected improvement, including EIC, augmented-Lagrangian EI, IECI, and EVR-based acquisition functions.EIC discounts EI by posterior constraint-violation probability; IECI and EVR instead target uncertainty reduction through expected improvement or feasible-region volume.
  • Challenges: When no point is feasible, the incumbent η does not exist, so EI cannot be computed for EIC, IECI, or EVR.Gelbart et al. address this for EIC by temporarily dropping its EI factor and searching using posterior constraint satisfaction.
  • Challenges: In decoupled evaluations, standard EIC yields zero expected improvement because evaluating only one task cannot create a feasible incumbent under a myopic policy.Gelbart et al. handle this pathology with a special two-stage acquisition procedure that selects a location and then chooses the evaluation task.
  • Challenges: EVR and IECI require domain-wide numerical integration and subsequent global acquisition optimization on grids, limiting their application to small dimensions.The nested grid operations cover both the integration variable x′ and the optimization variable x.
  • PESC: PESC avoids dependence on the current best feasible solution, separates objective and constraint contributions, and therefore requires no ad hoc decoupling modification.The paper presents these properties as preventing the feasibility and decoupling pathologies affecting EI-based methods.

3. Predictive entropy search with constraints

PESC selects evaluations by maximizing information about the constrained global minimizer and approximates this objective using posterior sampling and tractable Gaussian approximations. Its additive acquisition structure supports separate objective or constraint evaluations, while reusable EP computations reduce repeated work across locations.

  • PESC chooses the next query by maximizing the expected reduction in posterior entropy about the constrained minimizer x⋆.
  • The acquisition function can be rewritten as mutual information between noisy evaluations and x⋆, using a conditioned predictive distribution.
  • Samples of x⋆ are generated by sampling objective and constraint functions from their GP posteriors and solving the resulting constrained optimization problems.
  • PESC approximates the conditioned predictive distribution by Gaussian constructions, EP factorization, marginalization, and a final product of independent Gaussians.
  • The constrained minimizer is characterized as a feasible point whose objective value is the smallest among feasible points, encoded through conditional factors.
  • PESC is additive across evaluations of the objective and constraints, enabling decoupled queries; its coupled-setting complexity is O(MKN 3) per iteration.The EP approximation can be reused across locations, while matrix inversion in the EP step dominates the coupled-setting cost.

4. Experiments

Experiments evaluate PESC on synthetic, benchmark, and real-world constrained optimization problems. Across these settings, PESC closely approximates the information gain and generally outperforms or matches competing methods, especially when grid-based approaches scale poorly.

  • Accuracy of the PESC approximation: PESC’s approximation closely matches rejection sampling, including a nearly identical maximum acquisition value.Both methods use 50 samples of x⋆ in the illustrated one-dimensional case.
  • Accuracy of the PESC approximation: PESC slightly outperforms rejection sampling at the end of data collection, while RSDG is faster but less accurate.RSDG’s lower computational cost makes it attractive when computing time is very limited.
  • Synthetic functions in 2 and 8 input dimensions: PESC is best overall on synthetic problems in dimensions 2 and 8, with RSDG degrading substantially at dimension 8.The comparison includes EIC; grid-based methods are disadvantaged as dimensionality increases.
  • A toy problem: On the toy constrained problem, PESC performs significantly better than EIC and augmented Lagrangian optimization.The comparison averages utility gaps over 500 independent realizations, while AL has access to the true objective.
  • Finding a fast neural network: 7.0 ± 0.6% versus 49 ± 4% classification error: PESC beats EIC on the constrained neural-network task.These are ground-truth scores from repeated evaluations of the final recommendations; constraint violations count as 100% classification error.
  • Tuning Markov chain Monte Carlo: 3300 ± 1200 versus 2300 ± 900 effective samples: PESC outperforms EIC on Hamiltonian Monte Carlo tuning, but only by a small margin.The experiment averages 10 independent runs and is described as very noisy.

5. Discussion

The paper presents PESC for global optimization with unknown constraints and finds accurate approximations and strong performance across constrained problems. Its main implementation limitation is difficulty from numerical instabilities in the EP approximation.

  • 5. Discussion: PESC uses expected information gain about the constrained minimizer and produces accurate approximations to the target quantity.The paper reports performance about equally well to a ground-truth rejection-sampling method.
  • 5. Discussion: Across sections 4.2–4.5, PESC outperforms current methods such as EIC and AL over a variety of problems.
  • 5. Discussion: PESC applies to decoupled constraints without additional computational cost or the pathologies discussed for existing methods.
  • 5. Discussion: PESC is relatively difficult to implement because the EP approximation often leads to numerical instabilities.The authors integrated an implementation addressing these issues into Spearmint.

Supplementary Material

The supplementary material identifies the paper’s authors and their university affiliations. The author list includes researchers from Harvard University and the University of Cambridge.

  • Supplementary Material: José Miguel Hernández-Lobato and Michael A. Gelbart are affiliated with Harvard University, USA.
  • Supplementary Material: Matthew W. Hoffman and Zoubin Ghahramani are affiliated with the University of Cambridge, UK.

1 Description of Expectation Propagation

The supplementary material describes Expectation Propagation as a Gaussian approximation procedure for the factors forming the NFCPD. EP updates individual approximate factors using cavity distributions and moment matching until convergence.

  • 1 Description of Expectation Propagation: Expectation Propagation approximates a product of factors with a tractable Gaussian distribution by replacing individual factors with Gaussian approximations.This differs from the Laplace approximation, which fits one Gaussian to the whole posterior.
  • 1 Description of Expectation Propagation: EP tunes each approximate factor using a cavity distribution formed by removing that factor from the overall approximate distribution.
  • 1 Description of Expectation Propagation: Moment matching is performed in the context of the other approximate factors, prioritizing regions where the overall posterior probability is high.
  • 1 Description of Expectation Propagation: The EP procedure chooses a factor, computes its cavity distribution, updates moments, and repeats the updates until convergence.
  • 1 Description of Expectation Propagation: Factor updates can be performed in parallel using the same current approximate distribution, after which the updated Gaussian factors are multiplied together.

2 The Gaussian approximation to the NFCPD

The supplementary material constructs a Gaussian approximation to the joint distribution of objective and constraint values using Gaussian replacements for non-Gaussian factors. It defines the resulting precision matrices, mean vectors, covariance terms, and EP parameters used to obtain the approximation.

  • 2 The Gaussian approximation to the NFCPD: The approximation represents objective and constraint values at the candidate point and observed locations as vectors indexed from 0 through n.
  • 2 The Gaussian approximation to the NFCPD: mf, mck, and the corresponding covariance terms combine posterior information with the Gaussian factor parameters.The supplementary material defines posterior means and covariance matrices for f and ck from their observed data.
  • 2 The Gaussian approximation to the NFCPD: Non-Gaussian factors are replaced by Gaussian factors for the objective-related and constraint-related terms.The construction uses the assumed independence of the objective and constraints.
  • 2 The Gaussian approximation to the NFCPD: EP supplies the values of the Gaussian natural parameters used in the approximation.
  • 2 The Gaussian approximation to the NFCPD: The Gaussian factors are combined with the posterior terms using products of Gaussians, producing the approximation’s defined matrix and vector components.
  • 2 The Gaussian approximation to the NFCPD: Vf is an (N + 1) × (N + 1) precision matrix, while Vck is an (N + 1) × (N + 1) diagonal precision matrix.

3 The EP approximation to hn and gk

The section describes expectation propagation (EP) updates for approximate Gaussian factors associated with h_n and g_k. EP constructs cavity distributions, matches moments by minimizing KL divergence, and updates factors through Gaussian operations before approximating the NFCPD.

  • Updating h_n and g_k: EP refines the approximate Gaussian factors h_n and g_k iteratively by minimizing KL divergences and matching first and second moments.Moments are obtained from derivatives of normalization constants.
  • Updating h_n: For h_n, EP forms a Gaussian cavity distribution by removing the factor from the global approximation and marginalizing to the variables on which h_n depends.The relevant variables are f_n, f_0, and c_1,n, ..., c_K,n.
  • Updating h_n: The h_n update uses Gaussian moment matching and a ratio of Gaussians to obtain new factor parameters a_hn and b_hn.Second partial derivatives with respect to m_c_k,n are used instead of first derivatives with respect to v_c_k,n for numerical robustness.
  • Updating g_k: The analogous g_k update removes g_k from the global Gaussian approximation, marginalizes to c_k,0, and applies moment matching to update a_gk and b_gk.The normalization constant for the relevant moments is Z = Φ(α).
  • NFCPD approximation: After EP converges, the NFCPD is approximated by integrating the product of objective and constraint likelihood factors with the Gaussian approximation q̃.The objective and constraints are treated as conditionally independent in this factorization.

4 Performing the integration in Eq. (31)

The integration in Eq. (31) is made tractable by exploiting Gaussian predictive distributions and the Gaussian approximation q̃. Integrating latent training variables produces lower-dimensional Gaussian distributions needed for the next NFCPD approximation.

  • Analytic integration: The inner integral is evaluated analytically because the marginal posterior predictive distributions and q̃ are Gaussian.The integrand is rewritten using the Gaussian factors in the definition of q̃.
  • Constraint integration: For each constraint c_k, integrating out its latent variables leaves a univariate Gaussian for c_k(x) with mean and variance determined by the product distribution.The corresponding Gaussian product has dimension N + 2 before marginalization.
  • Objective integration: For the objective, integrating out f_1, ..., f_N leaves a bivariate Gaussian for f′ = (f(x), f_0).Its parameters are a mean vector and covariance matrix obtained from the Gaussian product.
  • Gaussian parameters: The required Gaussian means, covariances, and cross-covariances are defined from posterior quantities and prior covariance matrices for the objective and each constraint.The definitions include m_f, V_f, k_f, K_f, k_k, and K_k.
  • NFCPD approximation: The resulting inner integral yields the next approximation to the NFCPD, and the computations producing m_f do not depend on x.A final Gaussian approximation is performed separately for every x.

5 Final Gaussian approximation to the NFCPD, for each x

The final approximation replaces the generally nontractable NFCPD with a product of Gaussians matching the marginal means and variances of the objective and constraints at each x. EP uses convergence checks and damping during this computation.

  • Final Gaussian approximation: Because the right-hand side of Eq. (35) is not tractable, it is approximated by a product of Gaussians with matching marginal means and variances.The matched quantities are the marginal means and variances of f(x) and c_k(x).
  • Final Gaussian approximation: The marginal means and variances are computed from derivatives of the normalization constant Z using the cited EP moment formulas.These quantities define the Gaussian factors used in the final NFCPD approximation.
  • Implementation: EP initializes all approximate-factor parameters to zero and declares convergence when the absolute change in every parameter falls below 10^-4.This is the stated convergence criterion for the iterative procedure.
  • Implementation: Damping improves convergence by replacing each minimizing factor with a damped update, with α = 1 corresponding to no damping and α reduced by a factor of 0.99 per iteration.The same damping procedure is applied to h̃_n and g̃_k.
  • Implementation: The h̃_n and g̃_k factors are updated in parallel to speed convergence, although excessive updates can make covariance matrices non-positive definite.The passage identifies parallel updates and covariance definiteness as implementation considerations.
Loading 1502.05312v2…