Regret bounds for meta Bayesian optimization with an unknown Gaussian process prior
Bayesian optimization usually assumes that a Bayesian prior is given. However, the strong theoretical guarantees in Bayesian optimization are often regrettably compromised in practice because of unknown parameters in the prior. In this paper, we adopt a variant of empirical Bayes and show that, by estimating the Gaussian process prior from offline data sampled from the same prior and constructing unbiased estimators of the posterior, variants of both GP-UCB and probability of improvement achieve a near-zero regret bound, which decreases to a constant proportional to the observational noise as the number of offline data and the number of online evaluations increase. Empirically, we have verified our approach on challenging simulated robotic problems featuring task and motion planning.
Detailed Comments:  Summary of the main ideas: The authors propose a method based in a variant of Empirical Bayes for GP-based-BO to provide point estimates for the mean and kernel of the GPs. This method, which is essentially a sort of transfer learning method as the authors state, has the restriction that it needs a dataset of points to work. Authors provide a theoretical analysis of a regret bound by using their method and the GP-UCB and the PI acquisition functions. The paper is more formally written that other papers in the field which is a relief and it is, in my humble opinion, very necessary. It also provides a theoretical analysis, which is also rare in the field, and also necessary.  Related to:  Kim, Beomjoon, Leslie Pack Kaelbling, and Tomás Lozano-Pérez. "Learning to guide task and motion planning using score-space representation." Robotics and Automation (ICRA), 2017 IEEE International Conference on. IEEE, 2017. BOX algorithm that is the base of the methods that this paper suggest to provide estimates of mean and covariance matrices over a discrete domain. (This paper generalizes this for a continuous domain).  Robbins, Herbert. "An empirical Bayes approach to statistics." Herbert Robbins Selected Papers. Springer, New York, NY, 1985. 41-47. The empirical Bayes methodology that suggest fixed values instead of a distribution to sample hyperparameters. They adopt a variant of empirical Bayes in this paper.  GP-UCB and PI acquisition functions, along with an easy to read tutorial of BO, that this paper analyze are described in Brochu, Eric, Vlad M. Cora, and Nando De Freitas. "A tutorial on Bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning." arXiv preprint arXiv:1012.2599 (2010).  Strengths:  Theoretical and empirical analysis of the method. Bayesian statistics applied in a way that it has not been applied before for BO priors. Very formally written. Very well organized.  Weaknesses:  Difficult for non BO experts. (This weakness can be overcome by the suggestions that I provide in this review).   Does this submission add value to the NIPS community? : Yes it does. I think that I have only read one or two papers in the BO field that provide such an excellent theoretical and empirical analysis. Moreover, theoretical results are critical in BO, and it does not only study the GP-UCB AF, which has been theoretically analyzed before, but also PI. The method is sound and based in solid bayesian statistics. It frees the BO user for having to select the kernel, which is a heavy burden sometimes and something ironical in a sense. If BO is used for AutoML it is ironical that it has to be auto-tuned as well. Personally, I think that these applications of bayesian statistics and theoretical analysis of BO should be more studied. But the key fact of the paper is that it is not only theoretical but it also provide a good empirical analysis. For all these reasons, I strongly recommend this paper and state that it does add value to the NIPS community.  Quality: Is this submission technically sound?: Yes, this way of estimating the mean and kernel has not been done before. Are claims well supported by theoretical analysis or experimental results?: Yes, it is the main strength of the paper. Is this a complete piece of work or work in progress?: Complete piece of work. Are the authors careful and honest about evaluating both the strengths and weaknesses of their work?:  Clarity: Is the submission clearly written?: It has some issues for non experts. The paper assumes strong knowledge of BO and bayesian statistics. This may be a burder for non experts. I suggest adding some images, for example. An image of an estimation of the mean in 1D given some data, or a flow diagram with the offline and online phases. This would add some friendly style that lots of readers of this conference would appreciate. Also, all the variables must be explained, for example, in line 120, the different indexes i and j are not explained, this may be confusing for some readers. Special cases of the PI and GP-UCB are not described and their equations are not given numbers. These expressions are so easy to explain and so necessary for not experts that if they are not explained they may abandon to read the paper further. It would be a great pity.  On the other hand, proofs of the papers add clarity to some settings as the hyperparameter setting of the GP-UCB that are great and are not also common in BO papers.  Algorithm for Meta-BO is very clear and helpful.  Is it well organized?: Yes it is. It is very well organized. All sections introduce the content of posterior ones. Algorithms are brillianty referenced. One thing that needs to be added is a conclusions section. Does it adequately inform the reader?: If clarity issues that I have stated in Question 1 of Clarity are solved. Then, it does adequately inform the reader.  Originality: Are the tasks or methods new?: There are extensions of well-known techniques (BOX and Empirical Bayes). Is the work a novel combination of well-known techniques?: Yes it also is. Because it combines the extensions. Is it clear how this work differs from previous contributions?: Yes it is. It is different to transfer learning BO techniques and usual BO initialization of the mean and variance. Is related work adequately cited?: Yes it is. Lots of references are provided.  Significance: Are the results important?: Yes they are. This methodology is different from previous ones and seeing theoretical and empirical results of it is a guarantee of the success. Are others likely to use the ideas or build on them?: The paper is a bit hard to read, if the style is frendlier, I am sure that it is going to be sused. Does the submission address a difficult task in a better way than previous work?: Yes, in a sense. Using empirical Bayes and leaving free the kernel is a good idea. Does it advance the state of the art in a demonstrable way?: Yes it does, it demonstrates from an empirical and theoretical way. Does it provide unique data, unique conclusions about existing data, or a unique theoretical or experimental approach?: Yes, proofs in the supplementary material complement the exposition of the manuscript and provide an unique theoretical approach.  Arguments for acceptance:  The theoretical and empirical analysis for a BO method that this paper performs is really unusual in BO. Moreover, the paper has coherence, the methodology is sound and solid and it advances the state of the art. I strongly suggest this paper for acceptance.  This paper is also written with an excellent style, rarely found in computer science papers. I had a hard time to find typos, everything is written very carefully. Authors have a really strong knowledge of the field.   Arguments against acceptance:  If clarity issues are not solved, the paper is difficult to read. The style is great but, again, the paper is difficult to read and understand. Variables and equations are not always explained. I suggest to provide more intuitive explanations.  Typos:  Line 17, provide here the Rasmussen reference. [37]. Line 82, instead of writing k, write $k$.  More detailed comments and suggestions:  Congratulations to the authors, please make it easier to read for newcomers and this paper will be a success.