Source-linked AI summary
Bayesian Optimization with Unknown Constraints
Michael A. Gelbart, Jasper Snoek, Ryan P. Adams
TL;DR
The paper addresses Bayesian optimization when constraints are unknown, noisy, and potentially evaluated separately from the objective. It formulates probabilistic constrained optimization and develops acquisition functions for efficient search, demonstrating effectiveness across machine-learning and sampling applications. The framework also exposes an author-noted choice between individual and joint constraint-satisfaction formulations.
Problem
Bayesian optimization needs to handle real-world problems whose constraints may be unknown, noisy, costly, or independently evaluated from the objective.
Method
The paper models objectives and constraints with uncertainty-aware models, formulates probabilistic constraints, and proposes acquisition functions including support for independently evaluated tasks.
Results
The framework is demonstrated on online LDA with topic-sparsity constraints, neural-network memory constraints, and Hamiltonian Monte Carlo with convergence-diagnostic constraints.
Takeaways & Limitations
Constrained Bayesian optimization can express risk-aware, cost-aware optimization across multiple practical machine-learning and sampling settings.
Takeaways & Limitations
The formalization checks each constraint individually, while a joint probability requirement for all constraints is an alternative formulation.
Abstract
from arXiv · showhide
Recent work on Bayesian optimization has shown its effectiveness in global optimization of difficult black-box objective functions. Many real-world optimization problems of interest also have constraints which are unknown a priori. In this paper, we study Bayesian optimization for constrained problems in the general case that noise may be present in the constraint functions, and the objective and constraints may be evaluated independently. We provide motivating practical examples, and present a general framework to solve such problems. We demonstrate the effectiveness of our approach on optimizing the performance of online latent Dirichlet allocation subject to topic sparsity constraints, tuning a neural network given test-time memory constraints, and optimizing Hamiltonian Monte Carlo to achieve maximal effectiveness in a fixed time, subject to passing standard convergence diagnostics.
1 Introduction
The paper frames Bayesian optimization for black-box objectives with constraints that may be unknown, noisy, costly, or independently evaluated. It introduces a general constrained formulation and acquisition functions designed to manage uncertainty, evaluation costs, and complex restrictions.
- 1 Introduction: Bayesian optimization targets global optimization of expensive, unknown black-box objectives by iteratively updating a statistical model and selecting promising evaluations.The acquisition function balances exploitation of low predicted objective values with exploration of uncertain regions.
- 1 Introduction: Constrained optimization incorporates requirements such as achieving at least 95% customer approval while minimizing recipe calories.The cookie example illustrates a noisy constraint evaluated through differing human taste judgments.
- 1 Introduction: The framework models noisy constraints probabilistically, allowing users to specify the confidence required for constraint satisfaction.This directly represents the tradeoff between constraint-violation risk and optimization cost.
- 1 Introduction: The proposed acquisition function supports settings where objective and constraint evaluations are decoupled and have different user-specified costs.This avoids spending resources on expensive evaluations when cheaper information may be more useful.
- 1 Introduction: The framework supports arbitrarily many constraints and complicated restrictions, including constraints defined by known safety or resource limits.Examples include chemical-explosion restrictions and neural-network test-time memory bounds.
- 1 Introduction: Prior constrained Bayesian optimization includes IECI for learning in likely feasible regions and PAL for classifying Pareto-optimal candidates in discrete spaces.The paper positions its formulation alongside these earlier approaches while addressing a broader constrained setting.
2 Modeling the Constraints
The framework models objectives and constraints with uncertainty-aware statistical models, representing feasibility through latent functions and adapting observation models to the constraint data. Gaussian likelihoods permit closed-form inference, while non-Gaussian likelihoods require approximation or sampling.
- Independent Gaussian processes model the objective and constraints, although different model types may be used if each represents uncertainty.The paper assumes independence but does not require every function to use a GP or the same model family.
- Each constraint is represented by a latent real-valued function g_k(x), with feasibility defined by g_k(x) ≥0.The posterior over g_k yields the probability of satisfying constraint C_k at each input.
- Constraint-specific observation models determine the likelihood on g(x), with Gaussian likelihoods enabling closed-form posteriors and non-Gaussian likelihoods requiring approximation or sampling.This accommodates continuous measurements, counts, and other noisy constraint observations.
- For bounded running time, the transformation g(x) = log τmax −log τ converts τ ≤τmax into g(x) ≥0 and implies log-normal modeling for τ(x).A Gaussian prior and likelihood on g provide a computationally convenient closed-form GP posterior.
- For cookie tastiness, binomial counts are modeled through the latent transform g(x) = s^-1(ρ(x)), with a Gaussian-CDF link and a non-Gaussian posterior.Here ρ(x) is the probability that a subject likes the cookie, and the likelihood combines the binomial model with s^-1.
3 Acquisition Functions
The paper develops acquisition functions that incorporate uncertain feasibility into Bayesian optimization and address independent evaluation of objectives and constraints. It uses constraint-weighted expected improvement for coupled selection and entropy search for decoupled tasks.
- 3.1 Constraint weighted expected improvement: Constraint-weighted expected improvement multiplies objective improvement by the probability that the constraints are satisfied.The framework is presented for Expected Improvement but can be combined with any improvement criterion.
- 3.1 Constraint weighted expected improvement: Under independent constraints, the joint feasibility probability factors into the product of individual probabilities Pr(g_k(x) ≥0).This factorization follows from the assumed independence of the constraints.
- 3.2 Finding the feasible region: When every input violates a probabilistic constraint, the acquisition function drops the EI factor and searches for inputs with higher feasibility probability.This feasibility-search mode can also be used when no objective function exists.
- 3.3 Decoupled constraints: Independent objective and constraint evaluations require choosing which task to evaluate at each iteration, making task-selection strategy important when evaluation costs differ.The paper calls this structure decoupling and notes that some functions may be much more expensive than others.
- 3.3.1 Chicken and Egg Pathology: Myopic EI for separately evaluating tasks can create a chicken-and-egg pathology: learning either the objective or constraint alone may not produce improvement.The paper therefore motivates a non-myopic acquisition function based on improvement after a sequence of observations, despite its general intractability.
- 3.3.2 Entropy Search Criterion: Entropy search selects the task expected to reduce uncertainty about the constrained solution location, represented by the distribution p_min(x).The criterion minimizes expected relative entropy between p_min(x) and an uninformative base distribution.
- 3.3.3 Cost-sensitive selection: Scaling task-specific acquisition functions by user-provided costs selects the task with the most information gain per unit cost.If λ_A is the cost of observing task A, the acquisition criterion is adjusted using those costs.
4 Experiments
The experiments apply constrained Bayesian optimization to benchmark functions and machine-learning or sampling systems with objective-specific constraints. Results include feasible optimization of Branin-Hoo, topic sparsity in online LDA, memory-limited neural-network tuning, and HMC convergence constraints.
- Branin-Hoo function: After 33 objective and 17 constraint evaluations, the Branin-Hoo optimizer found a feasible solution with value 0.48 versus the true best value of 0.40.The constrained disk removes two of Branin-Hoo’s three global minima, leaving a unique feasible global minimum at x = (π, 2.275).
- Online LDA with sparse topics: Constrained Bayesian optimization significantly outperforms unconstrained Bayesian optimization on online LDA under a per-topic entropy constraint.The experiment optimizes five hyperparameters while requiring average per-topic word-distribution entropy below log2 200 bits.
- Memory-constrained neural networks: The neural-network experiment optimizes validation classification error subject to fewer than one million model parameters.The memory constraint is decoupled from the objective and inexpensive to evaluate because parameter counts are calculated directly from the hyperparameters.
- Tuning Markov chain Monte Carlo: HMC optimization maximizes effective samples in fixed computation time while requiring successful Geweke and Gelman-Rubin convergence diagnostics.The optimized parameters include leapfrog steps, step size, mass, and burn-in fraction.
- Tuning Markov chain Monte Carlo: After 50 iterations, HMC optimization selected τ = 2 leapfrog steps, 3.8% burn-in, and a 70% acceptance rate instead of the baseline’s τ = 100 configuration.The baseline’s longer proposals produce many fewer total samples and significantly fewer effective samples.
5 Conclusion
The paper extends Bayesian optimization to constrained problems with noisy constraints and independently evaluated objectives and constraints. It formulates probabilistic constraints, introduces a corresponding acquisition function, and demonstrates the approach on machine-learning and sampling meta-optimization.
- Conclusion: The framework uses probabilistic constraints so users can express cost-risk tradeoffs through a confidence parameter δ.It supports noisy constraint observations and independent evaluation of objectives and constraints.
- Conclusion: The proposed constrained Bayesian optimization is demonstrated on machine-learning algorithms and sampling techniques.The paper identifies product design, mobile speech recognition, and other expensive or noisy optimization settings as potential applications.