Bayesian Optimization with Exponential Convergence
This paper presents a Bayesian optimization method with exponential convergence without the need of auxiliary optimization and without the δ-cover sampling. Most Bayesian optimization methods require auxiliary optimization: an additional non-convex global optimization problem, which can be time-consuming and hard to implement in practice. Also, the existing Bayesian optimization method with exponential convergence [1] requires access to the δ-cover sampling, which was considered to be impractical [1,2]. Our approach eliminates both requirements and achieves an exponential convergence rate.
The paper presents a variant of Bayesian Global Optimization where future samples are generated through a space/interval partitioning algorithm.Using UCB, this avoids the (internal) global optimization problem of how to choose the next sample.Theoretical analysis shows that the approach yields theoretical improvements (exponential regret), thereby improving over previous work.The algorithm is clearly described and explained/illustrated with an example.The paper makes a novel contribution and is overall clearly presented.I have one reservation with this paper.The experimental results seem to be only for 1D test functions (not explicitly stated).I suspect that the interval partitioning approach does not scale well to higher dimensions (hyperrectangles) because the "resolution" would be required to grow exponentially.The approach is related to the well-known DIRECT algorithm, which is known to suffer badly when the dimensionality of the problem increases.I think something at least needs to be said about this in the paper.It does not change the theoretical contribution but is clearly significant for any practical purposes.Minor comments:p.2, UCB is considered "for brevity".Does this mean you could do something with expected improvement, for example?I got the feeling it had to be UCB.p.3 "...we simultaneously conduct global and local searches based on all the candidates of the bounds."I couldn't understand this statement.p.4 "At n=16, the far right...but no function evaluation occurs."Can you say why for clarity?