Pareto-frontier Entropy Search with Variational Lower Bound Maximization

Masanori Ishikura, Masayuki Karasuyama

Introduction

In Multi-Objective Optimization (MOO), the goal is not to find a single optimal point, but rather to identify the Pareto frontier—the set of points representing the best possible trade-offs between conflicting objectives. Information-theoretic Multi-Objective Bayesian Optimization (MOBO) methods attempt to select the next sample point by maximizing the Mutual Information (MI) between the candidate point and the true, unknown Pareto frontier.

However, calculating MI exactly is intractable because the true frontier is continuous and hidden. Existing methods typically rely on a finite subset of points and "over-truncate" the probability distribution, assuming the true frontier is strictly better than what has been observed. This creates a biased estimate that often overestimates the value of new samples, a problem that intensifies as the number of objectives increases. This paper introduces Pareto-frontier Entropy Search with Variational Lower Bound Maximization (PFEV), a novel approach that transforms MI estimation into a variational optimization problem to provide a more accurate and flexible acquisition function.

Methodology

PFEV shifts the paradigm from biased approximation to variational lower bound maximization. The core innovation lies in how the algorithm handles the uncertainty of the Pareto frontier through a mixture model:

  1. Under-Truncation: The authors introduce a conservative approximation that underestimates the effect of the Pareto frontier, providing a counterweight to traditional aggressive estimates.
  2. Variational Mixture: They define a variational distribution $q$ as a mixture of the traditional over-truncated distribution and the new under-truncated distribution. This mixture is controlled by a weight parameter $\lambda$.
  3. Lower Bound Maximization: Instead of selecting a fixed truncation strategy, the authors derive a mathematical lower bound for the Mutual Information. By maximizing this bound with respect to both the candidate point $x$ and the mixture weight $\lambda$, the algorithm automatically identifies the optimal balance that minimizes approximation error.
  4. Implementation: The framework utilizes Gaussian Processes (GPs) for surrogate modeling, NSGA-II for identifying candidate frontiers, and Quick Hypervolume (QHV) for geometric calculations. It is designed to handle parallel querying, decoupled objective evaluations, and noisy observations.

Experimental Setup

The authors evaluated PFEV against several state-of-the-art baselines, including Expected Hypervolume Improvement (EHVI), Pareto-frontier Entropy Search (PFES), and Joint Entropy Search (JES). The testing suite included:

  • Synthetic Functions: Functions generated from Gaussian Processes with varying input and output dimensions.
  • Standard MOO Benchmarks: Classic test problems such as Fonseca-Fleming, Kursawe, Viennet, and the FES/DTLZ suites.
  • Hyperparameter Optimization: Tuning a LightGBM model on four real-world datasets: Abalone, Waveform, Pageblocks, and Gesturephase.

Key Insights and Results

The Advantage of the "Middle Ground"

The research demonstrates that the true Pareto frontier is effectively "sandwiched" between over-truncated (aggressive) and under-truncated (conservative) estimates. PFEV is the first method to formally optimize the balance between these two extremes. While the difference between these truncations may be negligible in 2D, the gap expands significantly in 3D or higher dimensions. This explains why PFEV shows its strongest advantages as the number of objectives ($L$) increases.

Performance and Scaling

  • High-Dimensional Superiority: PFEV consistently outperformed or matched existing methods, with the performance gap becoming particularly noticeable when the number of objectives was $\ge 3$.
  • Robustness in Real-World Tasks: In LightGBM hyperparameter optimization, PFEV achieved higher hyper-volumes (a measure of frontier coverage) across all tested datasets compared to random search and standard MOBO baselines.
  • Computational Efficiency: While more complex than simple scalarization, PFEV is significantly faster than EHVI as the number of objectives grows. EHVI’s computational cost increases exponentially in high-dimensional objective spaces, whereas PFEV remains relatively efficient.

Conclusion and Future Work

PFEV provides a theoretically grounded way to handle the "unknown" parts of the objective space by framing MI estimation as a variational problem. While the method shows empirical success, the authors note that a formal proof of convergence for this specific variational MI approximation remains an open challenge. Future research may explore more flexible, multi-parameter variational distributions to further tighten the lower bound and the development of gradient-based optimizers to enhance the speed of the PFEV acquisition function.

Summary updated

BibTeX
@inproceedings{ishikura2025pareto,
  author = {Masanori Ishikura and Masayuki Karasuyama},
  title = {{Pareto-frontier Entropy Search with Variational Lower Bound Maximization}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=9UxEydnM1N},
}
Figure