Constrained Bayesian Optimization with Noisy Experiments

This article is interesting, not just because it's applied on a practical problem at Facebook, but also because it's quite fun to read the theory itself.

1. A Bayesian approach for A/B testing is advocated where noise is handled properly (not through heuristics).

2. Computationally efficiency is addressed through quasi-Monte Carlo.

3. It's practical use is shown through a production ranking system and optimization of a web server.

+ The Expected Improvement acquisition function (Mockus, 1978, Jones, 1998) is used to perform Bayesian optimization of the hyperparameters of a particular model.

+ Intuitively, it is an iterative procedure that picks a new point to fit a function in a sequential manner using the previously picked points.

+ Aside, to play with Gaussian processes, see e.g. https://github.com/fmfn/BayesianOptimization. To summarize, rather than searching for random variables it's searching for random functions.

+ Aside, Bayesian optimization is interesting because it reduces the number of evaluations required and replaces it by assumptions in the form of a (Gaussian Process) prior. See article http://papers.nips.cc/paper/4522-practical-bayesian-optimiza... by Snoek et al where by the way duration of execution time is also taken into consideration.

+ Aside, Bayesian optimization (in this form) does not use derivatives.

+ Aside, rather than ordinary MCMC, the "fit" of the posterior distribution is used to inform the sequential sampler through the acquisition function about where to sample next. Note that Bayesian optimization can even be used for adaptive MCMC: http://proceedings.mlr.press/v22/mahendran12/mahendran12.pdf.

+ Normally the Expected Improvement acquisition function assumes that observations are not noisy. (The Gaussian process prior defines stochastic relationships between parameters, not observations). The author introduce the Noisy Expected Improvement acquisition function.

+ The Noisy Expected Improvement integral is cast to an integral over the unit cube to be able to perform quasi Monte Carlo.

+ Aside, if you never read on quasi-randomness, check https://en.wikipedia.org/wiki/Low-discrepancy_sequence. Intuitively, the proportion of points in an (s-)interval is proportional to the (s-dimensional measure) length of that interval. This can be grid-like and does not need to be uniform randomly distributed. Note, quasi-randomness is not pseudo-randomness!

+ 6.2 describes the application for optimization of the JIT compiler part of the HipHop Virtual Machine (HHMV) to translate php/Hack into x86 machine code. Tunable parameters are about hot/cold code paths to reduce cache misses, choice for which type of functions to inline. The described algorithm is subsequently used to A/B test compiler flags w.r.t. CPU time, memory usage, database fetches, etc.

+ Results were good enough to be integrated in the HHVM: http://hhvm.com/.

Really nice work!