A General Framework for Constrained Bayesian Optimization using Information-based Search

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

TL;DR

This paper introduces Predictive Entropy Search with Constraints (PESC), a novel information-theoretic framework for tackling complex optimization problems with both objectives and constraints that are "black-box" (meaning their internal workings are unknown and they can only be queried). PESC is particularly adept at handling problems where different parts of the problem (objective vs. constraints) can be evaluated independently, a common scenario in real-world applications.

What Problem Does This Paper Address?

Many real-world optimization tasks involve finding the best solution (e.g., minimizing error, maximizing performance) while satisfying certain conditions or limitations (constraints). Think of optimizing a machine learning model's accuracy while ensuring its prediction time stays within a strict limit, or designing a new material with optimal properties that is also synthesizable. The challenge is that these objective and constraint functions are often "black-boxes" – we can't see inside them, only query them at specific points, and these queries can be very expensive (e.g., running a complex simulation).

Traditional Bayesian Optimization (BO) methods, while successful for unconstrained problems, struggle with constraints, especially when the objective and constraint functions can be evaluated independently. This "decoupled evaluation" scenario is common: imagine evaluating a model's accuracy on a CPU while simultaneously checking its prediction time on a GPU. Existing methods often require joint evaluation, which is inefficient or impossible in such cases. Furthermore, balancing the computational cost of the optimization algorithm itself with the cost of evaluating the black-box functions is a significant challenge, especially when some evaluations are fast and others are slow.

Methods

The core contribution is Predictive Entropy Search with Constraints (PESC). PESC is an information-theoretic approach that aims to maximize the expected information gain about the optimal solution. Key aspects include:

  • Information-Theoretic Framework: Instead of focusing on direct improvement (like Expected Improvement), PESC focuses on how much information a new evaluation will provide about the global minimizer of the constrained problem.
  • Separable Acquisition Function: A crucial innovation is that PESC's acquisition function naturally decomposes into contributions from individual function evaluations. This means if you have an objective and several constraints, the information gained from evaluating them independently can be summed up. This is vital for handling decoupled evaluations.
  • General Framework for Decoupled Problems: The paper formalizes a framework for constrained BO problems that encompasses coupled (jointly evaluated) and decoupled (independently evaluated) functions, as well as resource competition and parallelism.
  • PESC-F (Fast PESC): To address the challenge of balancing computation time, PESC-F introduces a "bounded rationality" approach. It uses partial, faster updates for its internal computations, allowing it to adaptively switch between quick, approximate decisions and slower, more accurate ones. This helps ensure the optimization algorithm's decision-making time doesn't dominate the overall process, especially when function evaluations are fast.

Datasets

Not discussed in the paper. The paper focuses on synthetic problems and benchmarks, rather than specific real-world datasets.

Key Insights and Ideas

  • Information Gain is Key for Decoupled Problems: For problems where objective and constraints can be evaluated separately, focusing on the information gained about the solution, rather than just direct improvement, is more effective. This is because independent evaluations provide pieces of information that can be combined.
  • Separability is a Game-Changer: The additive nature of PESC's acquisition function is its superpower. It allows the algorithm to intelligently choose which function (objective or constraint) to evaluate next, even when they are decoupled, and to do so efficiently.
  • Bounded Rationality for Real-World Speed: When function evaluations are fast, the optimization algorithm's own computation time becomes a bottleneck. PESC-F's adaptive approach to balancing computation speed and accuracy is a practical solution for real-world scenarios where time is a critical factor.
  • Decoupling Uncovers Hidden Value: By treating decoupled functions as separate "tasks," PESC can learn which tasks are more informative and focus resources accordingly, avoiding wasted effort on less useful evaluations.

Key Results

  • State-of-the-Art Performance: PESC demonstrates state-of-the-art performance in coupled optimization problems, outperforming existing methods like Expected Improvement with Constraints (EIC) and Rejection Sampling (RS) on synthetic benchmarks.
  • Effective for Decoupled Problems: PESC significantly outperforms coupled approaches when dealing with decoupled functions, especially in competitive scenarios where tasks vie for limited resources.
  • PESC-F Balances Speed and Accuracy: The PESC-F variant effectively balances BO computation time with function evaluation time, showing improved performance in scenarios with fast function evaluations. For instance, in a toy problem with varying evaluation costs, PESC-F with appropriate rationality levels significantly outperformed a coupled approach.
  • Automatic Task Prioritization: In experiments, PESC automatically learned to prioritize evaluating more informative constraints or objectives, demonstrating its ability to adapt to problem structures.

Limitations and Future Work

  • Computational Cost: While PESC is efficient for decoupled problems, its full implementation can still be computationally intensive, especially when dealing with a large number of data points or complex GP models.
  • Hyperparameter Tuning: The paper mentions that optimal values for certain parameters (like the rationality level γ in PESC-F) might be problem-dependent and could be a subject for future research, potentially through online learning or reinforcement learning.
  • More Complex Resource Allocation: The current framework assumes tasks require a single resource. Future work could extend this to tasks requiring multiple resources or time-dependent resource allocations.
  • Theoretical Analysis: A formal theoretical analysis of PESC, particularly in the context of information-directed sampling, is suggested for future work.
  • Multi-Objective Optimization: The authors note that the framework can be extended to multi-objective Bayesian optimization problems.

Summary updated

Abstract

We present an information-theoretic framework for solving global black-box optimization problems that also have black-box constraints. Of particular interest to us is to efficiently solve problems with decoupled constraints, in which subsets of the objective and constraint functions may be evaluated independently. For example, when the objective is evaluated on a CPU and the constraints are evaluated independently on a GPU. These problems require an acquisition function that can be separated into the contributions of the individual function evaluations. We develop one such acquisition function and call it Predictive Entropy Search with Constraints (PESC). PESC is an approximation to the expected information gain criterion and it compares favorably to alternative approaches based on improvement in several synthetic and real- world problems. In addition to this, we consider problems with a mix of functions that are fast and slow to evaluate. These problems require balancing the amount of time spent in the meta- computation of PESC and in the actual evaluation of the target objective. We take a bounded rationality approach and develop a partial update for PESC which trades off accuracy against speed. We then propose a method for adaptively switching between the partial and full updates for PESC. This allows us to interpolate between versions of PESC that are efficient in terms of function evaluations and those that are efficient in terms of wall-clock time. Overall, we demonstrate that PESC is an effective algorithm that provides a promising direction towards a unified solution for constrained Bayesian optimization.
BibTeX
@article{hernandezlobato2016general,
  author = {José Miguel Hernández-Lobato and Michael A. Gelbart and Ryan P. Adams and Matthew W. Hoffman and Zoubin Ghahramani},
  title = {{A General Framework for Constrained Bayesian Optimization using Information-based Search}},
  journal = {J. Mach. Learn. Res.},
  year = {2016},
  url = {https://openreview.net/forum?id=fFnXw3Z7v31},
}
Figure