Constrained Bayesian Optimization with Noisy Experiments

Benjamin Letham; Brian Karrer; Guilherme Ottoni; Eytan Bakshy

Source-linked AI summary

Constrained Bayesian Optimization with Noisy Experiments

Benjamin Letham, Brian Karrer, Guilherme Ottoni, Eytan Bakshy

arXiv:1706.07094v2Jun 21, 2017stat.MLcs.LGstat.AP

TL;DR

Noisy randomized experiments make it difficult to optimize continuous system parameters because measurement error can be comparable to effect sizes and existing Bayesian-optimization heuristics may degrade. The paper derives noisy expected improvement for batch optimization with noisy constraints and uses quasi-Monte Carlo integration to optimize it. The method improves performance on noisy constrained problems and is demonstrated on ranking and compiler experiments at Facebook.

Problem
Randomized experiments can have high measurement error, limiting Bayesian optimization when existing approaches degrade under noisy observations and constraints.
Method
The paper integrates posterior uncertainty directly in noisy expected improvement for greedy batches and noisy constraints, approximating the integral with quasi-Monte Carlo methods.
Results
The method outperformed existing methods on noisy constrained synthetic problems and improved machine-learning infrastructure and JIT-compiler experiments.
Takeaways & Limitations
The approach is applicable to empirical optimization settings with measurement error in both online and offline contexts.
Takeaways & Limitations
NEI does not value replicating points, limiting its usefulness for discrete problems and leaving replication strategies as future work.

Abstract

from arXiv · show

Randomized experiments are the gold standard for evaluating the effects of changes to real-world systems. Data in these tests may be difficult to collect and outcomes may have high variance, resulting in potentially large measurement error. Bayesian optimization is a promising technique for efficiently optimizing multiple continuous parameters, but existing approaches degrade in performance when the noise level is high, limiting its applicability to many randomized experiments. We derive an expression for expected improvement under greedy batch optimization with noisy observations and noisy constraints, and develop a quasi-Monte Carlo approximation that allows it to be efficiently optimized. Simulations with synthetic functions show that optimization performance on noisy, constrained problems outperforms existing methods. We further demonstrate the effectiveness of the method with two real-world experiments conducted at Facebook: optimizing a ranking system, and optimizing server compiler flags.

1 Introduction

Real-world systems often expose continuous parameters whose effects are measured through costly, noisy randomized experiments. The paper develops Bayesian optimization for these settings, addressing noisy observations, noisy constraints, and batch proposals.

Randomized experiments measure parameter effects directly but consume limited samples and often leave production constants only lightly tuned.
Bayesian optimization uses a Gaussian-process model and an acquisition function to balance exploration against exploitation during black-box optimization.
High measurement noise can make heuristic extensions of Bayesian optimization perform poorly, while real systems commonly require trading off multiple outcomes.
The method derives noisy expected improvement for noisy observations and constraints, then approximates it with quasi-Monte Carlo integration for efficient optimization.
The approach is applied to randomized experiments tuning a ranking system and server compiler settings at Facebook.

2 Prior work on expected improvement

Prior work extends expected improvement from noiseless black-box optimization to noisy observations, constraints, and batch settings, but often relies on heuristics or restricted domains. Alternative acquisition functions address noise more naturally, while constrained extensions can lose tractability.

Expected improvement selects candidates by their expected improvement over the current best observation, using a Gaussian-process posterior.
Noisy observations: With noisy observations, the true best function value is unknown, motivating plug-in heuristics that replace it with the minimum GP mean.
Noisy observations: High noise can make GP-mean EI underperform, producing clustered candidates and insufficient exploration.
Noisy observations: Noisy-observation alternatives include augmented EI and quantile EI, which modify EI using predictive variance or quantiles.
Constraints: Constrained EI multiplies expected improvement by the probability that every black-box constraint is satisfied, assuming objective-constraint independence.
Constraints: Noisy constraints make the best feasible value uncertain, so prior methods use probability thresholds or feasibility-focused heuristics.
Batch optimization: Batch EI integrates over pending outcomes, while related approaches either use Monte Carlo on discrete candidate sets or optimize integrated EI continuously.
Alternative acquisition functions: Information-based methods handle noise naturally, but constrained knowledge gradient remains difficult because constraints threaten tractability.

3 Utility maximization and EI with noise

The paper derives expected improvement by treating it as myopic utility maximization, then extends the formulation to noisy observations and constraints through posterior integration. The constrained utility explicitly handles cases with no feasible observations.

Utility maximization and EI with noise: The acquisition function is derived by maximizing expected improvement under posterior distributions of the objective and constraint values.This extends EI's utility-based formulation to noisy observations and constraints without simplifying heuristics.
Utility maximization and EI with noise: When feasible observations exist, utility is based on the negative objective value of the best feasible point; otherwise, it uses penalty M.The best feasible objective is defined over the observed feasible set, while M penalizes having no feasible solution.
Utility maximization and EI with noise: The improvement depends on feasibility: infeasible candidates provide zero improvement, while feasible candidates improve the best feasible objective or receive M when none exists.The formulation distinguishes infeasible candidates, feasible candidates with no prior feasible observations, and feasible candidates when a feasible best already exists.
Utility maximization and EI with noise: With no feasible observations, the acquisition function balances expected objective value against probability of feasibility using penalty M.As M increases, the strategy approaches maximizing feasibility probability; finite M still favors better objectives among equally feasible points.
Noisy EI: Noisy expected improvement integrates over posterior distributions of the true objective and constraint values inferred from noisy observations.The objective and constraints have GP posterior distributions, and the resulting acquisition function lacks an analytic expression but has an optimizable gradient.
Noisy EI: The noisy formulation extends to batch and asynchronous optimization by integrating over both completed and pending observations.The integral includes the joint true values of previously sampled points and pending batch points.
Noisy EI: In the noiseless limit, NEI equals EI and typically samples near the optimum to reduce uncertainty without replicating observed points.NEI is zero at previously observed points, whereas nearby samples can reduce uncertainty under the GP model.

4 Efficient quasi-Monte Carlo integration of noisy EI

The paper makes noisy expected improvement practical by replacing high-dimensional Monte Carlo integration with quasi-Monte Carlo integration over the unit cube. Sobol-based normal samples improve coverage and support efficient acquisition-function optimization.

Efficient quasi-Monte Carlo integration of noisy EI: The NEI integral's dimensionality equals the total number of completed and pending observations, motivating a more efficient approximation.Batch and asynchronous settings increase the integration dimension as pending observations are added.
Efficient quasi-Monte Carlo integration of noisy EI: QMC approximates high-dimensional integrals with low-discrepancy, space-filling sequences rather than potentially clumped random samples.The paper uses Sobol sequences to reduce wasted sampling in smooth integrands.
Efficient quasi-Monte Carlo integration of noisy EI: QMC theoretically achieves convergence O((log N)^d/N), compared with the Monte Carlo rate O(1/sqrt(N)).The stated rates describe the integration-error convergence for QMC and MC, respectively.
Efficient quasi-Monte Carlo integration of noisy EI: A multivariate normal posterior is transformed from uniform unit-cube samples using AΦ^-1(u)+µ, with Σ = AAᵀ.The matrix A may be chosen as the Cholesky decomposition of Σ.
Efficient quasi-Monte Carlo integration of noisy EI: Quasirandom posterior draws provide faster convergence and lower integration error than random draws, reducing the required sample count N.The paper illustrates this with scrambled Sobol samples, which cover the multivariate normal distribution more evenly.
Efficient quasi-Monte Carlo integration of noisy EI: Algorithm 1 samples true noisy-observation values from GP posteriors, constructs noiseless GP models, and computes noiseless EI for each sample.The sampled EI values form the QMC estimate of NEI.
Efficient quasi-Monte Carlo integration of noisy EI: The gradient of the QMC-estimated NEI is available analytically, allowing optimization with standard nonlinear optimization methods.Despite the increased integral dimensionality, the paper states that optimizing NEI is no harder than optimizing batch EI.
Efficient quasi-Monte Carlo integration of noisy EI: For each sampled GP posterior, the method computes the posterior at candidate x and evaluates EI in the noiseless setting.These steps operationalize the conditional-model computation in the algorithm.

5 Synthetic problems

Synthetic experiments evaluated QMC efficiency and compared NEI with heuristic and established Bayesian-optimization baselines across four noisy constrained problems. NEI consistently achieved the strongest optimization performance, while QMC reduced the samples needed for accurate approximation.

5.1 Evaluating QMC performance: QMC reliably required half as many samples as MC to achieve the same integration error on the Gramacy problem.
5.1 Evaluating QMC performance: 16 QMC samples achieved the same optimizer distance as 50 MC samples, with similar results on the other three problems.
5.2 Optimization performance compared to heuristics and other methods: NEI consistently performed the best of all methods when optimizing the best feasible objective across all four synthetic problems.
5.2 Optimization performance compared to heuristics and other methods: Compared to EI+heuristics, NEI found better solutions with fewer iterations because it correctly handled observation noise.
5.2 Optimization performance compared to heuristics and other methods: PESC matched NEI on the Gardner problem but performed worse than EI+heuristics on the other problems.
5.2 Optimization performance compared to heuristics and other methods: On Hartmann6, NEI identified feasible points with significantly better objectives by the final optimization batch.

6 Bayesian optimization with real-world randomized experiments

The paper applies NEI to noisy, constrained randomized experiments for ranking-system and server-compiler optimization. In both Facebook case studies, NEI found configurations improving the objective while satisfying the relevant constraints.

6 Bayesian optimization with real-world randomized experiments: The case studies tuned many continuous parameters simultaneously using noisy objectives and noisy constraints in Facebook experiments.
6.1 Optimizing machine learning systems: In ranking optimization, NEI tuned a six-dimensional indexer-parameter space to maximize an objective subject to a lower-bound constraint.
6.1 Optimizing machine learning systems: With only three proposed configurations, NEI found a feasible ranking configuration improving over both the baseline and every initial quasirandom configuration.
6.1 Optimizing machine learning systems: The ranking experiment had highly negatively correlated objective and constraint metrics, with ρ = 0.78, and NEI proposed candidates near the constraint boundary.
6.2 Optimizing server performance: In compiler optimization, NEI tuned seven numeric HHVM flags to reduce CPU time without increasing peak memory usage.
6.2 Optimizing server performance: Experiment 83 produced the most CPU-time reduction without increasing peak memory, while NEI candidates were generally more likely to be feasible.
6.2 Optimizing server performance: The median probability of feasibility increased from 0.77 for initialization points to 0.89 for NEI candidates.

7 Discussion

The discussion argues that integrating uncertainty improves noisy Bayesian optimization, while highlighting implementation trade-offs, modeling assumptions, and limits of the NEI acquisition function. Empirical comparisons and Facebook applications support its effectiveness in noisy, constrained experiments.

Performance: Proper uncertainty integration substantially improves performance when measurement noise is high, whereas heuristic EI can succeed when noise is small relative to effect size.The comparison distinguishes low-noise settings, where heuristic EI may suffice, from high-noise settings, where integrating uncertainty improves optimization.
Method: QMC makes NEI’s higher-dimensional integral efficient enough for optimization using relatively few samples.The approximation averages expected improvement over possible realizations of the true function and remains useful even when samples do not fully characterize the posterior.
Method: NEI accounts for covariance between candidate points and the incumbent, preferring less-correlated candidates that can provide higher expected total utility.EI+heuristics treats points with identical marginal posteriors equally, whereas NEI distinguishes their correlations with the incumbent.
Assumptions: NEI assumes independent constraints and objective–constraint independence for its analytic inner EI computation; correlated objective and constraints remain an open challenge.Constraint correlations could be modeled with a multi-task GP, but extending EI to correlated objectives and constraints is unresolved.
Performance: NEI generally outperformed PESC, while EI+heuristics outperformed PESC in three of four experiments.These experiments used noisy settings and batches of five proposals, unlike several earlier low- or no-noise sequential evaluations.
Applications: NEI improved machine-learning infrastructure and a JIT compiler in real-world experiments, supporting applicability beyond the demonstrated settings.The authors state that the method is applicable to other empirical settings that naturally produce measurement error, online and offline.