PaperlayerView exact revision on arXiv

Source-linked AI summary

Predictive Entropy Search for Multi-objective Bayesian Optimization with Constraints

Eduardo C. Garrido-Merchán, Daniel Hernández-Lobato

arXiv:1609.01051v2stat.ML

TL;DR

Constrained multi-objective optimization with expensive black-box functions calls for choosing evaluations carefully while identifying feasible Pareto solutions. PESMOC selects evaluations to reduce uncertainty about that set, and synthetic experiments report more accurate recommendations than random search with fewer evaluations.

  • Problem

    The paper addresses simultaneous optimization of multiple objectives under constraints when evaluations may be expensive and noisy and functions lack closed-form expressions.

    Source: §I · pp. 1–2

  • Method

    PESMOC selects objective and constraint evaluations expected to reduce entropy over the posterior feasible Pareto set.

    Source: §I · p. 2, §II · p. 2

  • Results

    In synthetic experiments, PESMOC provides more accurate Pareto-set recommendations than random search with fewer evaluations.

    Source: §I · p. 2, §III · p. 5

  • Takeaways & Limitations

    The reported advantage is especially relevant when objective and constraint evaluations are very costly.

    Source: §I · p. 2, §III · p. 5

    The described constraint setting assumes unknown, expensive-to-evaluate functions whose observations may be noisy.

    Source: §I · p. 2

Abstract

from arXiv · show

This work presents PESMOC, Predictive Entropy Search for Multi-objective Bayesian Optimization with Constraints, an information-based strategy for the simultaneous optimization of multiple expensive-to-evaluate black-box functions under the presence of several constraints. PESMOC can hence be used to solve a wide range of optimization problems. Iteratively, PESMOC chooses an input location on which to evaluate the objective functions and the constraints so as to maximally reduce the entropy of the Pareto set of the corresponding optimization problem. The constraints considered in PESMOC are assumed to have similar properties to those of the objective functions in typical Bayesian optimization problems. That is, they do not have a known expression (which prevents gradient computation), their evaluation is considered to be very expensive, and the resulting observations may be corrupted by noise. These constraints arise in a plethora of expensive black-box optimization problems. We carry out synthetic experiments to illustrate the effectiveness of PESMOC, where we sample both the objectives and the constraints from a Gaussian process prior. The results obtained show that PESMOC is able to provide better recommendations with a smaller number of evaluations than a strategy based on random search.

I. INTRODUCTION

PESMOC addresses simultaneous multi-objective optimization with constraints when evaluations are expensive, noisy, and lack closed-form expressions. It selects evaluations to reduce uncertainty about the feasible Pareto set, and synthetic experiments report more accurate recommendations than random search with fewer evaluations.

I. INTRODUCTION

  • The target problem jointly minimizes K objectives subject to C non-negativity constraints over a bounded input domain, while treating only feasible solutions as valid.Objectives can conflict, so the solution is a set of non-dominated feasible points rather than a single optimum.Source: §I · p. 1
  • The setting is motivated by costly, noisy evaluations and functions without closed-form expressions, which make gradient computation difficult and increase the value of limiting evaluations.Examples include robot locomotion, chip energy use, cookie design, and machine-learning system tuning.Source: §I · pp. 1–2
  • PESMOC chooses evaluations expected to reduce uncertainty about the feasible Pareto set, extending information-based strategies to multiple objectives and constraints.The uncertainty reduction is measured by Shannon differential entropy.Source: §I · p. 2
  • PESMOC produces more accurate Pareto-set recommendations than random search with fewer objective and constraint evaluations in synthetic experiments.The experiments sample both objectives and constraints from a Gaussian process prior.Source: §I · p. 2

II. PREDICTIVE ENTROPY SEARCH FOR MULTI-OBJECTIVE OPTIMIZATION WITH CONSTRAINTS

PESMOC models the objectives and constraints probabilistically and selects the next evaluation point by expected reduction in entropy over the posterior feasible Pareto set. It recasts this objective as mutual information and approximates its intractable conditional term.

II. PREDICTIVE ENTROPY SEARCH FOR MULTI-OBJECTIVE OPTIMIZATION WITH CONSTRAINTS

  • The next input is selected to maximize expected reduction in differential entropy over the posterior distribution of the Pareto set in the feasible space.The model assumes independent Gaussian process priors for objectives and constraints, with i.i.d. zero-mean Gaussian observational noise; evaluations are coupled at one location per iteration.Source: §II · p. 2
  • PESMOC rewrites the entropy-reduction objective as mutual information between the Pareto set and noisy evaluations, exploiting symmetry to avoid computing entropy over a potentially infinite set.The resulting conditional predictive entropy is for objective and constraint evaluations at x given that X⋆ is the feasible Pareto set.Source: §II · p. 2
  • The predictive entropy term is a factorizing (K+C)-dimensional Gaussian, while the conditional term is intractable and is approximated using Monte Carlo samples of the Pareto set.Samples come from posterior draws of objectives and constraints; grid locations with strictly negative sampled constraints are discarded before selecting non-dominated points, and expectation propagation estimates conditional entropy.Source: §II · p. 3

A. Using Expectation Propagation to Approximate the Conditional Predictive Distribution

The method approximates the conditional predictive distribution given a Pareto set using expectation propagation (EP). It encodes feasibility and Pareto dominance, then replaces non-Gaussian factors with Gaussian approximations.

A. Using Expectation Propagation to Approximate the Conditional Predictive Distribution

  • The Pareto-set distribution assigns support only to feasible points that dominate every other feasible point in at least one objective.Feasibility is encoded by Φ factors, while Ω factors enforce dominance over feasible comparison points.Source: A. Using Expectation Propagation to… · p. 3
  • The approximation uses evaluated inputs, Pareto-set points, and the candidate input, replacing non-Gaussian factors with Gaussian factors.The noiseless observation model uses Dirac deltas; for noisy observations, they are replaced by Gaussians with the corresponding noise variance.Source: A. Using Expectation Propagation to… · p. 3
  • EP approximates each Φ factor with a one-dimensional Gaussian and each Ω factor with C one-dimensional and K two-dimensional Gaussian factors.The two-dimensional factors use paired objective values at a comparison point and a Pareto point.Source: A. Using Expectation Propagation to… · p. 4
  • EP approximates the conditional predictive distribution of objectives and constraints at a candidate input, given the Pareto set.The resulting distribution is a normalized Gaussian.Source: A. Using Expectation Propagation to… · p. 4
  • EP iteratively refines factors independent of the candidate input and reuses them, while refining candidate-dependent factors only once for faster acquisition evaluation.The Gaussian approximations are combined by multiplication to form the conditional predictive distribution.Source: A. Using Expectation Propagation to… · p. 4

B. The PESMOC Acquisition Function

PESMOC estimates information gain about the Pareto set from predictive entropies before and after conditioning on that set. Its acquisition can be separated by objective and constraint, enabling decoupled evaluations.

B. The PESMOC Acquisition Function

  • The acquisition is the sum of entropy differences before and after conditioning on the Pareto set, using predictive variances with observation-noise variances added.Samples of Pareto sets approximate the expectation in the acquisition expression.Source: B. The PESMOC Acquisition Function · p. 4
  • Each objective or constraint term measures its expected reduction in Pareto-set entropy, allowing separate selection of evaluation locations for each function.Maximizing the individual acquisition functions also identifies which objective or constraint is expected to be more useful to evaluate.Source: B. The PESMOC Acquisition Function · p. 4
  • The acquisition and EP cost O(KCq^3), with q depending on the number of observations and points in each Pareto-set sample.The reported Pareto-set samples contain 50 points, making q a few hundred at most in practice.Source: B. The PESMOC Acquisition Function · p. 4

III. EXPERIMENTS

In synthetic comparisons, PESMOC produced more accurate Pareto-set recommendations than random search with fewer evaluations. A toy example illustrates how its acquisition concentrates evaluations in the feasible region.

III. EXPERIMENTS

  • PESMOC selects evaluations using model uncertainty, whereas random search samples locations uniformly over the input space.The Gaussian-process models used a Matérn covariance function, with hyperparameters approximately sampled from their posterior.Source: §III · p. 4
  • The comparison used 100 synthetic problems with 3 input dimensions, 2 objectives, and 2 constraints, running each strategy for 100 evaluations.Evaluations were tested without noise and with Gaussian noise of standard deviation 0.1; performance used hyper-volume relative to the actual Pareto set.Source: §III · p. 5
  • PESMOC recommendations had hyper-volumes closer to the actual Pareto set than random search recommendations, with fewer objective and constraint evaluations.Fig. 1 reports the logarithm of the relative hyper-volume difference after successive evaluations for noiseless and Gaussian-noise settings.Source: §III · p. 5, Figure 1 · p. 5
  • In the toy example, PESMOC quickly identifies the feasible box and concentrates evaluations there, while random search explores more uniformly and more often evaluates infeasible regions.The PESMOC acquisition is high inside the feasible region and low outside it.Source: §III · p. 5

IV. CONCLUSIONS AND FUTURE WORK

PESMOC is presented as an information-based method for Bayesian optimization with multiple objectives and constraints, with synthetic experiments showing more accurate Pareto-set estimates using fewer evaluations. The authors identify further comparisons and extensions as future work.

IV. CONCLUSIONS AND FUTURE WORK

  • PESMOC chooses evaluations expected to reduce entropy of the posterior Pareto-set distribution and produced more accurate estimates with fewer evaluations than random search in synthetic experiments.The authors note this is useful when objectives and constraints are very expensive to evaluate.Source: §IV · p. 5
  • Future work will compare PESMOC with Feliot et al., whose expected hyper-volume improvement is computationally expensive and limited to a small number of objectives without approximation.For larger objective counts, approximate methods are expected to yield worse results.Source: §IV · pp. 5–6
  • The authors plan broader experiments on real-world problems and further study of decoupled objective and constraint evaluations.They expect decoupling may offer greater benefits when many functions must be evaluated.Source: §IV · p. 6
  • A batch-selection extension is proposed for settings where objectives and constraints can be evaluated in parallel at multiple candidate locations.The proposed extension draws on the setting considered by Shah and Ghahramani.Source: §IV · p. 6
Loading 1609.01051v2…