Parallel Predictive Entropy Search for Batch Global Optimization of Expensive Objective Functions
We develop parallel predictive entropy search (PPES), a novel algorithm for Bayesian optimization of expensive black-box objective functions. At each iteration, PPES aims to select a batch of points which will maximize the information gain about the global maximizer of the objective. Well known strategies exist for suggesting a single evaluation point based on previous observations, while far fewer are known for selecting batches of points to evaluate in parallel. The few batch selection schemes that have been studied all resort to greedy methods to compute an optimal batch. To the best of our knowledge, PPES is the first nongreedy batch Bayesian optimization strategy. We demonstrate the benefit of this approach in optimization performance on both synthetic and real world applications, including problems in machine learning, rocket science and robotics.
Paper Summary: Motivated by the optimization of objective functions which are extremely expensive to evaluate, but which can be accessed in parallel, the authors construct an algorithm for selecting batches of several instances to evaluate, called Parallel Predictive Entropy Search, or PPES.PPES is an extension of the Predictive Entropy Search (PES) algorithm of Hernandez-Lobato et al., 2014.PPES is constructed such that the instances which compose a batch jointly (i.e., non-greedily) optimize an approximate expected conditional mutual information between the corresponding observations and the location of the global optimizer of the objective function. In order to accomplish this, the authors develop an approximation to the mutual information using EP, construct an approximate sampler from the posterior over the global maximizer's location, and address how the optimization over the approximate expected conditional mutual information (i.e., the selection of the instances for the batch) can be performed.They then proceed to test their approximate expected conditional mutual information in a simple setting.Finally, they test the whole algorithm on a variety of data sets against several competing batch algorithms.Quality: The approach taken by the authors is rigorous, sensible, and produces useful results.There are several approximations, but they are well-motivated.The numerical experiments are quite complete, though they could do with a bit more information in the supplement as to precisely what code was being run.The approximation which most interests me is the one taken in Equation 4; essentially, the authors approximate p(f|D,S_t,x*) by a PDF conditioned on a series of necessary (f(x) < f(x*)) or quasi-necessary (f(x*) >= ymax + eps) conditions; how does this affect the entropy of the resulting distribution?Intuitively, I would expect that conditioning only on necessary conditions would produce an entropy which is at least as large as the original, but what about the quasi-necessary conditioning?Should we expect the information gain to be consistently under-estimated?Is it reasonable to expect that the quasi-necessary condition won't bias the location of the maximizer?Some intuition from the authors might be helpful here and in other places. Clarity: The material and algorithm are both quite complicated, but the presentation is well done and this explanation is fairly clear.Section 3, the major technical section, is particularly well constructed.  In regard to the experiments, it would be best if the implementations of the competing algorithms were discussed a bit, perhaps in the supplementary material; some of the algorithms are not explicitly designed to give a most probable maximizer, and the code for others (GP-BUCB, at least, and perhaps the Azimi et al. simulation matching algorithms) are unfortunately publicly available only in a form which takes discrete input sets; without having this information in some form, it's a bit hard to assess how much value the experiments have.PPES looks to perform quite well, clearly, but how strong are the baselines?Of course, the authors of this work should not be responsible for fixing the code of others, but some information on this would be handy.   Originality: The primary basis for the paper is Hernandez-Lobato, Hoffman, and Ghahramani 2014.Relative to that work, which introduced PES, the PPES algorithm is a parallelized version that allows the selection of batches of actions.Practically, this is an important new capability.So far as I can tell, the primary theoretical differences are the removal of a condition from the approximation of the predictive entropy (conditioned on x*) in section 3.1, which appear to make this computation similar, and some differences in computing the gradient of the approximate decision function in section 3.3.The EP implementation may also be substantially different, but this is somewhat hard to tell from the text.These innovations do not appear to be enormous, or fundamental changes of approach.Undoubtedly, there was plenty of work which went into extending PES to PPES, but the authors have not done a good job of highlighting precisely what the theoretical novelties of the present work are, or why they were necessary or interesting.  Significance: This work appears to be a good fit for the setting of controlling computationally intensive simulations, and will likely make a good impact there.In particular, in this setting the method's high computational cost would be still very small as compared to the large simulations it would be controlling, the parallelism it presumes is available, and the experiments are very expensive.I would argue that this combination of strong writing, good mathematical meat, and the availability of a well-suited problem domain make this a significant paper for practice. That said, I can imagine that this setting would also often have batch sizes which are larger than the 2-4 attempted in this paper, and as the authors point out, their algorithm scales poorly for these cases.How does this cost compare against the computational expense of a single observation in a reasonable setting, e.g., the robot problem addressed here? At what point is it reasonable to run a simpler algorithm to allow greater parallelism?Again, some practical guidance would be helpful.