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 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.
Introduction
In many real-world engineering and machine learning scenarios, optimization is rarely unconstrained. Whether tuning the hyperparameters of a deep neural network or designing a physical component, we often seek to maximize performance subject to strict black-box requirements—such as memory limits, latency thresholds, or safety constraints. Traditional Bayesian Optimization (BO) methods often assume that the objective and all constraints are evaluated simultaneously (coupled). However, in practice, these tasks are often "decoupled": a model's accuracy might be tested on a CPU cluster while its runtime is independently verified on a specific GPU.
This paper introduces Predictive Entropy Search with Constraints (PESC), a unified framework designed to handle these complexities by treating optimization as an information-gathering process. PESC is particularly adept at navigating search spaces where feasible points are difficult to find and where the costs of evaluating different constraints vary significantly.
The PESC Framework
PESC shifts the paradigm of acquisition functions from "improvement-based" (like Expected Improvement) to "information-based." Instead of looking for points that likely beat the current best, PESC identifies points that provide the most information about the location of the global feasible minimizer, $x_*$.
Key Methodological Components
- Information-Theoretic Acquisition: PESC calculates the Mutual Information between a potential evaluation and the location of $x_*$. By maximizing this value, the algorithm systematically reduces uncertainty about where the optimal feasible solution resides.
- Separability: A critical feature of PESC is that its acquisition function is additive. This allows the algorithm to evaluate the objective and various constraints independently. If a specific constraint is highly informative and cheap to evaluate, PESC can prioritize it over an expensive objective evaluation.
- Expectation Propagation (EP): Because calculating the entropy over the distribution of $x_*$ is analytically intractable, the authors employ EP to create a Gaussian approximation of the complex, non-linear constraints, making the computation feasible.
Balancing Meta-Computation: PESC-F
A common pitfall in BO is the "thinking time"—the meta-computation required to choose the next point. If an experiment takes only seconds to run, a BO algorithm that takes minutes to decide is inefficient. To address this, the authors propose PESC-F (Fast). This variant uses a bounded rationality approach, employing partial updates and reusing previous solutions to speed up decision-making when evaluations are quick. The system adaptively switches back to full computation when evaluations are slow, optimizing for total wall-clock time rather than just sample count.
Experimental Results
The authors validated PESC across several challenging domains:
- Neural Network Tuning: Tuning 12 hyperparameters for an MNIST classifier subject to a 2ms GPU latency constraint. PESC achieved a 7.0% error rate, vastly outperforming Expected Improvement with Constraints (EIC), which struggled at 49% error due to the difficulty of finding feasible points in a noisy environment.
- MCMC Tuning: Optimizing Hamiltonian Monte Carlo parameters to maximize effective sample size while satisfying convergence diagnostics.
- Wall-Clock Efficiency: In decoupled scenarios, PESC-F demonstrated a superior ability to find high-quality solutions faster in terms of actual elapsed time by balancing its internal computational overhead against the cost of the experiments.
Conclusion and Future Work
PESC represents a significant step toward a general framework for constrained Bayesian optimization. By leveraging information theory, it naturally handles decoupled evaluations and provides a principled way to "check the easy stuff first." While the current implementation relies on stationary kernels and carries some computational overhead, its robustness in noisy, constrained environments makes it a powerful tool for complex engineering tasks. Future research may extend this framework to non-stationary kernels and more intricate resource-dependency graphs.
Summary updated