PaperlayerView exact revision on arXiv

Source-linked AI summary

Predictive Entropy Search for Multi-objective Bayesian Optimization

Daniel Hernández-Lobato, José Miguel Hernández-Lobato, Amar Shah, Ryan P. Adams

arXiv:1511.05467v3stat.ML

TL;DR

Expensive, conflicting objectives make efficient identification of the Pareto set difficult, especially when existing methods require joint evaluations or scale poorly with the number of objectives. PESMO selects evaluations by reducing posterior Pareto-set entropy and decomposes its acquisition by objective. Across synthetic and real-world problems, it reports better recommendations with fewer evaluations, while decoupled evaluation can improve performance when objectives differ in difficulty or cost.

  • Problem

    Expensive black-box objectives and limitations of existing methods—scalarization, joint objective evaluations, and exponential acquisition cost—make efficient Pareto-set identification challenging.

  • Method

    PESMO uses Gaussian-process models and predictive entropy search to select evaluations that maximize expected information gain about the posterior Pareto set, with objective-specific acquisition terms enabling decoupling.

  • Results

    PESMO produces better recommendations with fewer objective evaluations than related methods, and decoupled evaluation performs significantly better in a four-objective synthetic case.

  • Takeaways & Limitations

    Objective-wise decoupling can allocate more evaluations to difficult objectives, improving performance particularly when the number of objectives is large.

  • Takeaways & Limitations

    The method assumes each unknown objective follows a Gaussian-process prior with i.i.d. Gaussian observation noise.

Abstract

from arXiv · show

We present PESMO, a Bayesian method for identifying the Pareto set of multi-objective optimization problems, when the functions are expensive to evaluate. The central idea of PESMO is to choose evaluation points so as to maximally reduce the entropy of the posterior distribution over the Pareto set. Critically, the PESMO multi-objective acquisition function can be decomposed as a sum of objective-specific acquisition functions, which enables the algorithm to be used in \emph{decoupled} scenarios in which the objectives can be evaluated separately and perhaps with different costs. This decoupling capability also makes it possible to identify difficult objectives that require more evaluations. PESMO also offers gains in efficiency, as its cost scales linearly with the number of objectives, in comparison to the exponential cost of other methods. We compare PESMO with other related methods for multi-objective Bayesian optimization on synthetic and real-world problems. The results show that PESMO produces better recommendations with a smaller number of evaluations of the objectives, and that a decoupled evaluation can lead to improvements in performance, particularly when the number of objectives is large.

1 Introduction

The paper addresses expensive multi-objective optimization, where conflicting objectives make a single best point inappropriate and the goal is to approximate the Pareto set efficiently. It introduces PESMO, which selects evaluations by reducing uncertainty about that set while supporting decoupled objectives.

  • Multi-objective optimization seeks to optimize K real-valued functions over a bounded input domain rather than a single objective.
  • Conflicting objectives prevent simultaneous optimization, so the relevant solution is a Pareto set of non-dominated points.Users can choose among Pareto-optimal points according to their preferences.
  • Expensive black-box evaluations motivate probabilistic models and acquisition functions that identify promising evaluation locations cheaply.Gaussian processes model uncertainty in the unknown objectives.
  • Existing model-based methods may rely on suboptimal scalarization, require evaluating all objectives together, and incur acquisition costs that grow exponentially with the number of objectives.
  • PESMO chooses evaluations by maximizing expected information gain about the posterior Pareto set and decomposes its acquisition into objective-specific terms for decoupled evaluation.Experiments report better performance than related methods, while decoupling can evaluate objectives separately.

2 Multi-objective Bayesian Optimization via Predictive Entropy Search

PESMO models each objective with a Gaussian process and selects the next evaluation to maximize expected reduction in posterior entropy over the Pareto set. Predictive entropy search makes this tractable by conditioning predictive uncertainty on sampled Pareto sets, while objective-wise decomposition supports decoupled evaluations.

  • PESMO assumes independent Gaussian-process priors for noisy, unknown objectives and seeks evaluations that maximize information about the Pareto set.Observation noise is modeled as i.i.d. Gaussian with zero mean.
  • The next query maximizes the expected reduction in entropy of the posterior distribution over the Pareto set.The acquisition function evaluates the information gained from a candidate objective observation.
  • Predictive entropy search exchanges the entropy terms through mutual-information symmetry, avoiding direct evaluation of the potentially difficult Pareto-set entropy.The resulting acquisition favors regions where the Pareto set is informative about objective predictions.
  • The predictive entropy term is computed from a factorizable K-dimensional Gaussian, while the conditional term is approximated using Monte Carlo samples of Pareto sets.Posterior objective functions are sampled to approximate the expectation over Pareto sets.
  • Expectation propagation replaces non-Gaussian Pareto-set factors with approximate Gaussian factors to obtain a tractable conditional predictive distribution.Factors independent of the candidate location are reused, while candidate-dependent factors are updated once for efficiency.
  • PESMO's acquisition is a sum of K objective-specific functions, allowing each objective's best evaluation location to be compared in decoupled settings.The objective with the largest individual acquisition can be selected for the next evaluation.
  • The acquisition-function evaluation includes expectation propagation with computational cost O(Km^3), where m depends on observations and sampled Pareto-set size.

3 Related Work

Related methods use scalarization, hyper-volume improvement, or uncertainty-region strategies for multi-objective Bayesian optimization. PESMO instead avoids scalarization, supports decoupled evaluations, and has linear computational cost in the number of objectives.

  • ParEGO: ParEGO scalarizes the multi-objective problem into a single objective, then applies Gaussian-process modeling and expected improvement.Its acquisition evaluation costs O(N 3), reflecting the cost of fitting the GP.
  • SMSego: SMSego uses optimistic objective estimates to select points by their gain in hyper-volume without reducing the problem to a single objective.It fits a separate GP for each objective and costs O(KN 3), excluding the additional hyper-volume computation cost.
  • PAL: PAL maintains uncertainty regions for each input and classifies points as Pareto-optimal, non-Pareto-optimal, or uncertain.The classifications compare best and worst objective values across points with an ϵ tolerance.
  • EHI and SUR: EHI selects evaluations by expected hyper-volume improvement, but its cell-based computation grows exponentially with the number of objectives.The total number of cells is (|X̃ ⋆| + 1)^K, making EHI feasible for at most two or three objectives.
  • PESMO: PESMO differs by avoiding scalarization, decomposing acquisition into K objective-specific terms for decoupled evaluations, and scaling linearly with K.These properties directly address limitations involving joint evaluations and exponential acquisition cost.

4 Experiments

Experiments evaluate PESMO’s approximation accuracy, computational cost, synthetic-objective performance, and neural-network optimization results. Across these settings, PESMO performs strongly, while decoupled evaluation especially benefits problems with difficult objectives or few evaluations.

  • Accuracy of the PESMO Approximation: PESMO’s acquisition estimates are compared with a more accurate Monte Carlo and non-parametric entropy estimator in a two-objective, one-dimensional problem.The comparison uses posterior GP means and standard deviations alongside both acquisition-function estimates.
  • Experiments with Synthetic Objectives: PESMO obtains the best results on synthetic problems with 2 objectives and 3 dimensions under both noiseless and noisy observations.Performance is measured by the logarithm of the relative hyper-volume difference between the actual Pareto set and the recommendation.
  • Experiments with Synthetic Objectives: PESMO’s acquisition-function evaluation cost scales linearly with the number of objectives, unlike the exponential cost of EHI and SUR.The reported timing comparison includes ParEGO, SMSego, PESMO, PESMOdec, EHI, and SUR; PESMOdec takes longer because it separately optimizes objective-specific acquisitions.
  • Experiments with Synthetic Objectives: PESMO is the best method on synthetic problems with 4 objectives and 6 dimensions, while decoupled evaluation performs significantly better.EHI and SUR are excluded because their costs become infeasible with four objectives.
  • Experiments with Synthetic Objectives: The decoupled method evaluates difficult synthetic objectives almost three times more often than easy objectives.In the illustrative case, the first two objectives are nonlinear and the last two are linear.
  • Finding a Fast and Accurate Neural Network: On neural-network optimization, PESMOdec has the best hyper-volume after 100 evaluations, while PESMO is best after 200 evaluations in both settings.The objectives are prediction error and prediction time; the decoupled method evaluates prediction time only a few times and focuses on prediction error.

5 Conclusions

PESMO selects evaluations expected to reduce uncertainty about the Pareto set and improves recommendation quality with fewer evaluations. Its objective-specific acquisition decomposition supports decoupled evaluation, while computational cost scales linearly with the number of objectives.

  • 5 Conclusions: PESMO chooses each evaluation location to most reduce the posterior entropy of the Pareto set.The method uses a probabilistic model of the objectives to quantify expected information gain.
  • 5 Conclusions: PESMO obtains better recommendations with fewer evaluations under both noiseless and noisy observations.
  • 5 Conclusions: The acquisition function decomposes into K objective-specific acquisition functions, enabling decoupled evaluation by maximizing individual acquisition functions.This allows the most promising objective to be selected separately.
  • 5 Conclusions: In decoupled evaluation, PESMO identifies difficult objectives and focuses evaluations on them, providing better results.The paper illustrates this behavior on a problem involving an accurate and fast neural network.
  • 5 Conclusions: PESMO's computational cost scales linearly with the number of objectives.

A Detailed Description of Expectation Propagation

This section details the expectation propagation computations required to evaluate the PESMO acquisition function. It focuses on approximating each objective's conditional predictive distribution and refining the Gaussian factors used in that approximation.

  • A Detailed Description of Expectation Propagation: The EP procedure computes the approximate conditional predictive distribution for each objective function f_k.The distribution is formed from Gaussian-process posteriors and approximate factors.
  • A Detailed Description of Expectation Propagation: The EP updates refine the approximate factors used to evaluate the acquisition function.
  • A Detailed Description of Expectation Propagation: PESMO uses Gaussian approximate factors in its expectation propagation representation.

A.1 Reconstruction of the Conditional Predictive Distribution

The conditional predictive distribution is reconstructed for an objective using a sampled Pareto set, observed inputs and objective observations, and EP Gaussian factors. Gaussian closure yields a multivariate Gaussian parameterized by updated natural parameters.

  • A.1 Reconstruction of the Conditional Predictive Distribution: The reconstruction conditions objective f_k on a sampled Pareto set of size M, N input locations, their observations, and EP approximate factors.
  • A.1 Reconstruction of the Conditional Predictive Distribution: Only EP factors depending on the current objective f_k are included when forming the conditional distribution.
  • A.1 Reconstruction of the Conditional Predictive Distribution: Because the GP posterior and EP factors are Gaussian, their product gives a multivariate Gaussian q(f_k) over N + M variables.
  • A.1 Reconstruction of the Conditional Predictive Distribution: The resulting covariance matrix and mean vector are obtained from the inverse precision matrix and its product with the natural-parameter vector.This inversion costs O((N + M)^3) and is performed once per optimization iteration, then reused across candidate locations.

A.2 The Conditional Predictive Distribution at a New Point

At a new candidate location, PESMO computes the conditional predictive variance for an objective by extending the Gaussian approximation and extracting the candidate-related variance. A block structure enables efficient reuse of existing computations.

  • A.2 The Conditional Predictive Distribution at a New Point: The conditional predictive distribution at x_N+1 extends q(f_k) with one additional dimension for f_k(x_N+1).
  • A.2 The Conditional Predictive Distribution at a New Point: Gaussian integration produces a univariate Gaussian distribution for the new-point predictive quantity.
  • A.2 The Conditional Predictive Distribution at a New Point: Variables unrelated to the new-point factors can be marginalized from the conditional distribution.
  • A.2 The Conditional Predictive Distribution at a New Point: The variance required for entropy computation is the last diagonal entry of the inverse matrix S_x^-1.
  • A.2 The Conditional Predictive Distribution at a New Point: Only the last row and column of S_x depend on x_N+1, allowing the candidate variance to be computed with block-matrix inversion at cost O(M^3).
  • A.2 The Conditional Predictive Distribution at a New Point: The final predictive variance for y_k includes the additive Gaussian observation-noise variance.

A.3 Update of an Approximate Factor

The update begins with conditional predictive distributions for each objective and uses their Gaussian statistics to construct the exact factor.

  • The method assumes parameters μ_k and Σ_k are already available for each objective’s conditional predictive distribution q(f_k).
  • For each objective, inference focuses on the joint variables f_k(x_i) and f_k(x⋆_j), while marginalizing all other variables.These variables follow bivariate Gaussian distributions under q(f_k).

A.3.1 Computation of the Cavity Distribution

The EP cavity-distribution update removes the current approximate factor, forms a tilted distribution, and moment-matches it to update objective-specific Gaussian factors.

  • Computation of the Cavity Distribution: The cavity distribution q_old is obtained by dividing out the current approximate factor from the Gaussian approximation.The resulting distribution remains bivariate Gaussian for each objective.
  • Computation of the Cavity Distribution: Natural parameters are subtracted during cavity construction and converted back to means and covariances using a 2 × 2 matrix inverse.The small matrix makes this computation inexpensive in practice.
  • Computation of the Cavity Distribution: A normalized tilted distribution is formed, with its normalization constant computed in closed form and its moments obtained from derivatives of log Ẑ.The Gaussian cumulative distribution function appears in the closed-form normalization expression.
  • Computation of the Cavity Distribution: The approximate factors are updated by matching Gaussian moments to the tilted distribution and factorizing the result across objectives.The update transforms parameters to natural form before subtracting the corresponding moments of the factorized Gaussian approximation.
  • Computation of the Cavity Distribution: Parallel EP updates and damping are used to improve convergence without changing EP’s convergence points.Damping limits large parameter changes while preserving the convergence points.

B Finding a Small and Accurate Ensemble of Decision Trees

The decision-tree experiment evaluates methods on the conflicting goals of minimizing ensemble size and prediction error. PESMO performs competitively, with decoupling offering an early advantage but smaller objective-allocation differences than in neural-network experiments.

  • The task seeks ensembles with small total tree-node counts and low prediction error, which are conflicting objectives.The experiments use the German Credit dataset and compare recommendations after 100 and 200 evaluations.
  • The ensemble uses randomized decision-tree construction, with adjustable tree count, feature subsampling, node-splitting threshold, training-data fraction, and label-change fraction.
  • The setting supports decoupled PESMO because node count and cross-validated error can be evaluated separately, with error requiring multiple ensemble builds.
  • After 100 evaluations, decoupled PESMO achieves the best average hyper-volume; after 200, coupled PESMO performs best, followed closely by decoupled PESMO and SUR.SMSego, EHI, and especially ParEGO perform worse in general.
  • PESMO finds smaller ensembles at similar or better prediction error than EHI, SMSego, and ParEGO, while SUR finds the most accurate ensembles overall.In some cases, PESMO finds intermediate-size ensembles with better prediction error than SUR.
  • The decoupled method evaluates the node-count objective 135 times versus 65 evaluations of the other objective.This allocation difference is smaller than the 175-versus-25 split reported for neural networks, coinciding with smaller coupled–decoupled performance differences.

C Accuracy of the Acquisition in the Decoupled Setting

The decoupled acquisition approximation is assessed against a more accurate Monte Carlo estimate in a two-objective one-dimensional problem. The two methods produce closely matching acquisition functions.

  • The experiment compares PESMO’s objective-specific acquisition functions α_1(·) and α_2(·) with expensive Monte Carlo estimates.The comparison tests whether the approximations remain accurate in the decoupled setting.
  • The plotted acquisition functions from PESMO and Monte Carlo look very similar for both objectives, including the global maximizer’s location.The result indicates that expectation propagation may provide a good approximation in the decoupled setting.
  • The diagnostic also displays each objective’s observations, posterior mean, and posterior standard deviation at a step of optimization.
Loading 1511.05467v3…