PaperlayerView exact revision on arXiv

Source-linked AI summary

A Flexible Framework for Multi-Objective Bayesian Optimization using Random Scalarizations

Biswajit Paria, Kirthevasan Kandasamy, Barnabás Póczos

arXiv:1805.12168v3cs.LGstat.ML

TL;DR

Multi-objective Bayesian optimization often targets the whole Pareto front even when users need only selected regions. This paper samples user-preference-weighted random scalarizations, combining them with Bayesian optimization to obtain flexible region targeting. It reports sublinear or zero-in-the-limit regret guarantees, competitive regret in experiments, and computationally inexpensive scaling with the number of objectives.

  • Problem

    Existing multi-objective methods commonly recover the whole Pareto front, although applications may require only user-relevant regions because some Pareto-optimal solutions are impractical.

  • Method

    The framework places a user-specified prior over scalarization functions and randomly samples a scalarization before optimizing it with scalarized Bayesian-optimization acquisitions.

  • Results

    The method flexibly samples specified or entire Pareto-front regions, achieves sublinear regret guarantees, and obtains smaller or comparable regret to baselines experimentally.

  • Takeaways & Limitations

    The approach offers a flexible and computationally cheap way to focus multi-objective optimization on preferred Pareto-front regions while retaining whole-front coverage.

  • Takeaways & Limitations

    The method requires users to specify the prior and scalarization class, and the paper provides no general method for choosing or updating the prior.

Abstract

from arXiv · show

Many real world applications can be framed as multi-objective optimization problems, where we wish to simultaneously optimize for multiple criteria. Bayesian optimization techniques for the multi-objective setting are pertinent when the evaluation of the functions in question are expensive. Traditional methods for multi-objective optimization, both Bayesian and otherwise, are aimed at recovering the Pareto front of these objectives. However, in certain cases a practitioner might desire to identify Pareto optimal points only in a subset of the Pareto front due to external considerations. In this work, we propose a strategy based on random scalarizations of the objectives that addresses this problem. Our approach is able to flexibly sample from desired regions of the Pareto front and, computationally, is considerably cheaper than most approaches for MOO. We also study a notion of regret in the multi-objective setting and show that our strategy achieves sublinear regret. We experiment with both synthetic and real-life problems, and demonstrate superior performance of our proposed algorithm in terms of the flexibility and regret.

1 Introduction

Multi-objective Bayesian optimization must balance competing objectives, yet practitioners may need only selected Pareto-front regions rather than the entire front. The paper proposes random scalarizations with user-specified priors, providing flexible sampling, regret guarantees, and lower computational cost.

  • Motivation: Competing objectives prevent simultaneous optimization, so conventional multi-objective methods typically approximate the Pareto front.A Pareto-optimal point cannot improve in one objective without degrading another.
  • Proposed framework: User-specified priors over scalarizations let the method target selected, including non-connected, Pareto-front regions or the entire front.The prior induces a probability distribution over Pareto-optimal values and encodes user preference.
  • Proposed framework: At each step, the algorithm samples a scalarization from the prior and optimizes it using scalarized UCB or Thompson sampling.The acquisition function scalarizes either individual upper confidence bounds or posterior samples of the objectives.
  • Contributions: The framework supports more general Lipschitz, monotonic scalarizations than prior work and is naturally suited to arbitrary Pareto-front regions.Its flexibility includes recovering the whole front when needed.
  • Contributions: The paper proves sublinear regret under Lipschitzness and monotonicity assumptions and evaluates the method on synthetic and real-life tasks.The experiments compare the algorithm with existing multi-objective approaches.
  • Contributions: Computational complexity scales linearly with the number of objectives, unlike EHI and SUR, whose complexity scales exponentially with that number.The paper also characterizes the approach as cheaper than entropy-based methods such as PESMO.

2 Background

The paper reviews Gaussian-process surrogates and sequential Bayesian optimization before extending them to multiple noisy objectives. Thompson sampling uses posterior draws, while GP-UCB uses an upper confidence bound to select the next point.

  • Gaussian Processes: Gaussian processes place a prior over functions using a mean function and kernel, with finite function values following a multivariate Gaussian distribution.Conditioning on noisy observations produces a posterior Gaussian process.
  • Bayesian Optimization: Bayesian optimization sequentially uses past observations to determine the next evaluation point.The reviewed procedures operate through a surrogate posterior.
  • Bayesian Optimization: Thompson sampling draws a function from the posterior and evaluates its maximizer, whereas GP-UCB maximizes posterior mean plus an uncertainty term.GP-UCB uses Ut(x) = µt−1(x) + √βtσt−1(x).
  • Multi-objective setting: For multiple objectives, the paper assumes noisy objective observations generated from known Gaussian-process priors over a common compact domain.Each objective has its own GP prior and Gaussian observation noise.

3 Our Approach

The approach samples scalarizations from a user-specified prior and selects points that represent high-probability regions of the Pareto front. It combines multi-objective acquisition functions with Bayes-regret minimization while allowing interactive preference changes, with computational costs driven by maintaining one GP per objective.

  • 3.1 Random Scalarizations: The prior p(λ) induces a probability distribution over Pareto-optimal values, defining which regions of the front are preferred.Each λ maps to a Pareto-optimal value, so the prior concentrates attention on high-probability regions.
  • 3.2 Bayes Regret: The objective is to return a finite set whose objective values span the high-probability region rather than optimize a single scalarization.The desired set should avoid being clustered in a small region and should represent the user-specified region of the Pareto front.
  • 3.2 Bayes Regret: Bayes regret is small when selected points are Pareto optimal and approximate high-probability regions, even if low-probability regions are poorly represented.High regret can result from clustering, sampling from the wrong distribution, or selecting non-Pareto-optimal points.
  • 3.3 Scalarized Thompson Sampling and UCB: At each iteration, the method samples λ from p(λ), builds a scalarized acquisition function, and selects its maximizer using separate Gaussian processes for the objectives.UCB scalarizes objective-wise upper bounds, while TS scalarizes posterior samples of the objectives.
  • 3.3 Scalarized Thompson Sampling and UCB: The prior and scalarization class are domain-dependent inputs that users may update interactively, but the paper provides no general prior-selection or prior-update method.The paper uses a simple heuristic for demonstration in the experiments.
  • 3.4 Computational Complexity: Fitting K objective-specific GPs costs at most O(KT^3), while evaluating the proposed acquisition at each point costs O(KT).The additional factor K reflects maintaining K Gaussian processes rather than one.

4 Regret Bounds

The paper defines multi-objective instantaneous, cumulative, and Bayes regret, then bounds expected regret using information gain under Gaussian-process assumptions. The resulting guarantees apply to both UCB and Thompson Sampling, recover the single-objective bound when K = 1, and imply vanishing Bayes regret under additional regularity assumptions.

  • Regret definitions: The analysis defines instantaneous and cumulative regret for multi-objective optimization, then introduces expected Bayes and cumulative regret over the algorithm’s randomness.Expected Bayes regret averages over the process, observation noise, and algorithmic randomness; expected cumulative regret additionally averages over sampled scalarizations.
  • Information gain: Maximum information gain quantifies uncertainty reduction about the objective process from noisy observations and is used to upper-bound expected cumulative regret.The analysis first relates expected Bayes regret to expected cumulative regret, then bounds the latter using maximum information gain.
  • Regret bounds: Theorem 1 upper-bounds expected cumulative regret for MOBO-RS after T observations under both UCB and Thompson Sampling.The assumptions include Gaussian objective distributions with marginal variances bounded by 1 and Gaussian observation noise, together with bounds on objective-specific information gain.
  • Regret bounds: When K = 1, the bound recovers the single-objective BO rate O(√TdγT ln T), while additional boundedness and Lipschitz assumptions imply Bayes regret converges to zero as T →∞.The single-objective specialization matches the bound reported by Russo and Van Roy (2014).

5 Experimental Results

The experiments evaluate random-scalarization methods on synthetic and real multi-objective problems, showing that they concentrate samples in specified Pareto-front regions while maintaining competitive regret. The setup uses linear and Tchebyshev scalarizations with user preferences represented through weight distributions.

  • Experimental setup: The experiments compare the proposed methods with PESM, EHI, SMSego, ParEGO, and MOEA/D-EGO on synthetic and real-world problems.EHI is described as computationally infeasible beyond two objectives.
  • Preference specification: Bounding boxes are converted into sampling strategies by drawing nonnegative weights uniformly within objective-specific intervals and normalizing them.This heuristic approximately samples points from inside the specified bounding box.
  • Synthetic experiments: The synthetic two-objective study samples top, mid, flat, and mixed regions defined by objective-space bounding boxes using Branin-4 and CurrinExp-4.The regions are specified as top, mid, flat, and a mixture of top and mid distributions.
  • Synthetic experiments: The six-objective experiment uses six Gaussian-process objectives and a mid region with each objective bounded in [2/3, 1].The objective values are linearly transformed to [0, 1].
  • Real-world experiments: The LSH-Glove and Viola-Jones studies optimize multiple practical objectives, including time, precision or sensitivity, specificity, and memory-related quantities.The LSH-Glove objectives include Time, 1−Precision, and Memory; Viola-Jones includes 1−Sensitivity, 1−Specificity, and query time.
  • Results: The proposed approach concentrates later samples in the specified Pareto-front region after initial exploration and achieves smaller or comparable regret to baselines, with the largest improvement in high-dimensional experiments.The authors attribute the high-dimensional advantage plausibly to learning only part of the Pareto front.

6 Conclusion

The paper concludes that random scalarizations provide an efficient and flexible way to explore selected Pareto-front regions or the whole front. Its preference-aware regret is theoretically controlled and empirically smaller or comparable to baseline regret.

  • Conclusion: The proposed MOBO algorithm efficiently explores specified parts of the Pareto front while remaining flexible enough to sample the whole front.The algorithm is also described as computationally cheap and scaling linearly with the number of objectives.
  • Conclusion: The preference-aware regret is high when sampling misses or leaves the user-specified region, and the algorithm achieves zero regret in the limit under necessary regularity assumptions.The regret formulation incorporates user preferences through the prior and scalarization.
  • Conclusion: Experiments show that the proposed approach achieves smaller or comparable regret relative to the baselines.This conclusion is reported across the paper’s experimental comparisons.

B Proofs

The proofs analyze UCB and Thompson sampling through a common regret decomposition under Gaussian-process and scalarization assumptions. The analysis proceeds from finite domains toward continuous domains using discretization.

  • Thompson-sampling analysis: For Thompson sampling, the proof uses independently sampled objective functions from the posterior and requires independence of the objectives’ GP priors.The independence assumption is used specifically in the Thompson-sampling proof.
  • Assumptions and notation: The proof assumes Gaussian-process objectives with bounded marginal variances and defines the optimal point for each sampled scalarization.The scalarization-specific optimum is x⋆_t = argmax_x∈X s_λt(f(x)).
  • UCB analysis: For UCB, the selected point maximizes the upper-confidence objective, which supports the regret decomposition through a conditional comparison with the scalarization-specific optimum.The proof uses U_t(λ_t, x_t) ≥ U_t(λ_t, x⋆_t) conditioned on the history.
  • Domain extension: The analysis first bounds regret for finite X and then extends the result to continuous domains with a discretization argument.The same proof strategy is stated for both the finite-domain and continuous-domain settings.

B.1 Upper Bounds for Finite |X| 

The finite-domain proof bounds cumulative regret for both UCB and Thompson sampling by decomposing it into terms controlled through the algorithm’s confidence or posterior-sampling structure. The resulting bound is stated in Proposition 1.

  • Finite-domain bounds: The finite-domain analysis begins by bounding terms in a regret decomposition for the proposed UCB and Thompson-sampling algorithms.The proof uses intermediate lemmas and conditional expectation arguments.
  • Finite-domain bounds: The proof controls Gaussian tail terms using the normal-distribution inequality for variables with nonpositive mean.The positive-part operator is defined as (x)+ = max(0, x).
  • Finite-domain bounds: The proof aggregates per-round bounds over t and invokes Cauchy-Schwarz and an upper bound involving maximum information gain.The final step substitutes the scalarization-dependent quantity into the resulting bound.
  • Finite-domain bounds: The cumulative regret bound for Algorithm 1 applies to both UCB and Thompson sampling.This result is stated as Proposition 1 and follows from Lemmas 1, 2, and 3.

B.2 Extending to continuous X

For continuous domains, the analysis discretizes X at each time step and incorporates approximation errors into separate TS and UCB regret decompositions. Bounding the resulting terms yields a theorem applying to both methods.

  • B.2 Extending to continuous X: The continuous domain X is replaced at each time step by a uniformly spaced finite grid Xt with |Xt| = τ^d.Each point x is associated with its closest grid point [x]t.
  • B.2 Extending to continuous X: The discretization introduces approximation factors into the regret decomposition before the finite-domain framework is applied.The treatment then separates the continuous-case decompositions for TS and UCB.
  • B.2 Extending to continuous X: The TS decomposition relies on x⋆t and xt having the same distribution conditional on Ht.
  • B.2 Extending to continuous X: The decomposed terms are bounded using the discretized sets, corresponding βt values, and earlier lemmas for the individual components.The text specifically reuses Lemmas 2 and 3 and the bound associated with (17).
  • B.2 Extending to continuous X: The resulting theorem holds for both UCB and TS, with global constants C1, C2 > 0.

B.3 Upper bound on Bayes regret

The Bayes-regret analysis compares the sampling distribution over scalarizations with its empirical samples using a Wasserstein metric and Lipschitz regularity. The resulting regret bound has two components that both vanish as T grows.

  • B.3 Upper bound on Bayes regret: The analysis assumes a bounded scalarization domain Λ and that sλ(y) is J-Lipschitz in λ.
  • B.3 Upper bound on Bayes regret: The regret decomposition uses equality of the expected maxima under sampled λt and generic λ to relate observed pointwise regret to regret over unseen scalarizations.
  • B.3 Upper bound on Bayes regret: The distance between the scalarization sampling distribution and its empirical distribution is measured with the Wasserstein-1 distance W1.
  • B.3 Upper bound on Bayes regret: O*(T^-1/2) bounds the convergence rate of component I as T → ∞, ignoring logarithmic factors.
  • B.3 Upper bound on Bayes regret: O*(T^-1/D) bounds the convergence rate of component II when D ≥ 2 under mild regularity conditions.

B.4 Auxilliary Results

The auxiliary results establish a bound for monotone Lipschitz scalarizations by decomposing the coordinate differences between two objective vectors. The positive-part operator captures only excess scalarized value.

  • B.4 Auxilliary Results: The auxiliary lemma assumes s: R^D → R is L-Lipschitz in the ℓ1 norm and monotonically increasing in every coordinate.
  • B.4 Auxilliary Results: The notation (x)+ denotes max(0, x), retaining only positive differences.
  • B.4 Auxilliary Results: The proof handles the case s(x) ≤ s(y) trivially and otherwise constructs intermediate vectors Ud that replace coordinates one at a time.
  • B.4 Auxilliary Results: Because consecutive Ud vectors differ in one component and s is coordinatewise increasing, the scalarized difference can be bounded componentwise.

C Implementation Details

The experiments use repeated evaluations on normalized domains, periodic Gaussian-process hyperparameter fitting, and a common acquisition-optimization procedure. Batch evaluation is disabled for fair comparison across methods.

  • C Implementation Details: The two-objective experiment uses 10 runs with 150 iterations, while all other experiments use 5 runs with 120 iterations.
  • C Implementation Details: All input domains are mapped to X = [0, 1]^d.
  • C Implementation Details: Each experiment begins by randomly selecting ninit points and evaluating the multi-objective function at those points.
  • C Implementation Details: The GP uses a squared exponential kernel and is refit every 10 evaluations by maximizing marginal likelihood for its hyperparameters.Separate bandwidths are used for each input dimension.
  • C Implementation Details: The experiments use βt = 0.125 log(2t + 1) for UCB and optimize each acquisition function with DiRect.
Loading 1805.12168v3…