Bayesian optimization (BO) (Shahriari et al., 2016) is a powerful and versatile tool for black-box function optimization, with applications including parameter tuning, robotics, molecular design, sensor networks, and more. The idea is to model the unknown function as a Gaussian process with a given kernel function dictating the smoothness properties. This model is updated using (typically noisy) samples, which are selected to steer towards the function maximum.

One of the most attractive properties of BO is its efficiency in terms of the number of function samples used. Consequently, algorithms with rigorous guarantees on the tradeoff between samples and optimization performance are particularly valuable. Perhaps the most prominent work in the literature giving such guarantees is that of (Srinivas et al.,

2010), who consider the cumulative regret:

where f is the function being optimized, and is the point chosen at time t. Under a Gaussian process (GP) prior and Gaussian noise, it is shown in (Srinivas et al., 2010) that an algorithm called Gaussian Process Upper Confidence Bound (GP-UCB) achieves a cumulative regret of the form

where (with function values f = and noisy samples ) is known as the maximum information gain. Here I(f; y) denotes the mutual information (Cover & Thomas, 2001) between the function values and noisy samples, and denotes asymptotic notation up to logarithmic factors.

The guarantee (2) ensures sub-linear cumulative regret for many kernels of interest. However, the literature is severely lacking in algorithm-independent lower bounds, and without these, it is impossible to know to what extent the upper bounds, including (2), can be improved. In this work, we address this gap in detail in the special case of a one-dimensional function. We show that the best possible cumulative regret behaves as under mild assumptions on the kernel, thus identifying both cases where (2) is nearoptimal, and cases where it is strictly suboptimal.

1.1. Related Work

An extensive range of BO algorithms have been proposed in the literature, typically involving the maximization of an acquisition function (Hennig & Schuler, 2012; Hernández- Lobato et al., 2014; Russo & Van Roy, 2014; Wang et al., 2016); see (Shahriari et al., 2016) for a recent overview. As mentioned above, the most relevant algorithm to this work for the noisy setting is GP-UCB (Srinivas et al., 2010), which constructs confidence bounds in which the function lies with high probability, and samples the point with the highest upper confidence bound. Several extensions to GPUCB have also been proposed, including contextual (Krause & Ong, 2011; Bogunovic et al., 2016a), batch (Contal et al., 2013; Desautels et al., 2014), and high-dimensional (Kan- dasamy et al., 2015; Rolland et al., 2018) variants.

In the noiseless setting, it has been shown that it is possible to achieve bounded cumulative regret (de Freitas et al., 2012; Kawaguchi et al., 2015) under some technical assumptions. In (de Freitas et al., 2012), this is done by keeping track of a set of potential maximizers, and sampling increasingly finely in order to shrink that set and “zoom in” towards the optimal point. Similar ideas have also been used in the noisy setting for studying batch variants of GP-UCB (Con- tal et al., 2013), simultaneous online optimization (SOO) methods (Wang et al., 2014), and lookahead algorithms that use confidence bounds (Bogunovic et al., 2016b). Returning to the noiseless setting, upper and lower bounds were given in (Grünewälder et al., 2010) for kernels satisfying certain smoothness assumptions, with the lower bounds showing that bounded cumulative regret is not always to be expected.

Alongside the Bayesian view of the Gaussian process model, several works have also considered a non-Bayesian counterpart assuming that the function has a bounded norm in the associated reproducing kernel Hilbert space (RKHS). Interestingly, GP-UCB still provides similar guarantees to (2) in this setting (Srinivas et al., 2010). Moreover, lower bounds have been proved; see (Bull, 2011) for the noiseless setting, and (Scarlett et al., 2017) for the noisy setting. In the latter, the lower bounds nearly match the GP-UCB upper bound for the squared exponential (SE) kernel, but gaps remain for the Matérn kernel. For reference, we note that these kernels are defined as follows:

where l > 0 is a lengthscale parameter, is a smoothness parameter, is the modified Bessel function, and is the gamma function.

The multi-armed bandit (MAB) (Bubeck & Cesa-Bianchi, 2012) literature has developed alongside the BO literature, with the two often bearing similar concepts. The MAB literature is far too extensive to cover here, but it is worth mentioning that sharp lower bounds are known in numerous settings (Bubeck & Cesa-Bianchi, 2012), and the abovementioned concept of “zooming in” to the optimal point has also been explored (Kleinberg et al., 2008). To our knowledge, however, none of the existing MAB results are closely related to our own.

1.2. Our Results and Their Implications

The main results of this paper are informally summarized as follows.

Main Results (Informal). Under mild technical assumptions on the kernel, satisfied (for example) by the SE kernel and Matérn-kernel with , the best possible cumulative regret of noisy BO in one dimension behaves as and

Our results have several important implications:

• To our knowledge, our lower bound is the first of any kind in the noisy Bayesian setting, and is tight up to a factor under our technical assumptions.

• Our lower bound also establishes the order-optimality of the upper bound of (Srinivas et al., 2010) applied to the SE kernel, up to logarithmic factors.

• On the other hand, our upper bound establishes that the upper bound of (Srinivas et al., 2010) for the Matérn-kernel, namely , is strictly suboptimal for . For example, if , then this is as opposed to our upper bound of . (See also (Shekhar & Javidi, 2017) for recent improvements over (Srinivas et al., 2010) under the Matérn kernel in higher dimensions and/or with smaller

• Another important implication for the Matérn kernel with is that the Bayesian setting is provably less difficult than the non-Bayesian RKHS counterpart; the latter has cumulative regret (Scarlett et al., 2017), which is strictly worse than

Our upper bound is stated formally in Section 3, and its technical assumptions are given in Section 2.1. We build on the ideas of (de Freitas et al., 2012) for the noiseless setting, while addressing highly non-trivial challenges arising in the presence of noise.

Our lower bound is stated formally in Section 4, and its technical assumptions are given in Section 2.1. The analysis is based on a reduction to binary hypothesis testing and an application of Fano’s inequality (Cover & Thomas, 2001). This approach is inspired by previous work on lower bounds for stochastic convex optimization (Raginsky & Rakhlin, 2011), but the details are very different.

2.1. Bayesian Optimization

We seek to sequentially optimize an unknown reward function f(x) over the one-dimensional domain D = [0, 1]; note that any interval can be transformed to this choice via re-scaling. At time t, we query a single point serve a noisy sample for some noise variance , with independence across different times. We measure the performance using the cumulative regret , defined in (1).

We henceforth assume f to be distributed according to Gaussian process (GP) (Rasmussen, 2006) having mean zero and kernel function . The posterior distribution of f given the points and observations up to time t is again a GP, with the posterior mean and variance given by (Rasmussen, 2006)

where , and is the identity matrix.

2.2. Technical Assumptions

Here we introduce several assumptions that will be adopted in our main results, some of which were also used in the noiseless setting (de Freitas et al., 2012).

Assumption 1. We have the following:

1. The kernel k is stationary, depending on its inputs only through

2. The kernel k satisfies for all , and

Given the stationarity assumption, the assumptions and k(x, x) = 1 are without loss of generality, as one can always re-scale the function and adjust the noise variance accordingly.

Next, we give some high-probability assumptions on the random function f itself.

Assumption 2. There exists a constant such that, with probability at least , we have the following:

for any local maximum that differs from , for some constant

2. The function f is twice differentiable;

3. The function f and its first two derivatives are bounded:

for all and some constants . This implies that f is -Lipschitz continuous, and is -Lipschitz continuous.

The assumption of a unique maximizer holds with probability one in most non-trivial cases (de Freitas et al., 2012), and (7) simply formally defines the gap to the second-highest peak. Moreover, given twice differentiability, the remaining conditions in (8) are very mild, only requiring that the function value and its derivatives are bounded, and formally defining the corresponding constants.

Next, we provide assumptions regarding the derivatives of f and the resulting Taylor expansions (typically around the optimizer ). We adopt slightly different assumptions for the upper and lower bounds, starting with the former.

Assumption 3. There exist constants and such that conditioned on the events in Assumption 2, we have with probability at least that one of the following is true:

1. The maximizer is at an endpoint (i.e., 1), and satisfies the following locally linear behavior: For all (if ) or (if ), it holds that

2. The maximizer satisfies fies the following locally quadratic behavior: For all

This assumption is near-identical to the main assumption adopted in the noiseless setting (de Freitas et al., 2012), and is also mild given the assumption of twice differentiability. Indeed, (9) and (10) amount to standard Taylor expansions, with the assumptions and only requiring non-vanishing gradient at the endpoint (first case) or non-vanishing second derivative at the function maximizer (second case). These conditions typically hold with probability one (de Freitas et al., 2012).

The following assumption will be used for the lower bound. Assumption 4. There exists constants such that conditioned on the events in Assumption 2, both of the following hold with probability at least

1. For any we have

2. The maximizer satisfies fies the following for all

Figure 1. Illustration of some of the main assumptions: The function is bounded within and its derivative within the gap to the second highest peak is at least , and the function is locally quadratic for points within a distance of the maximizer.

The first part is similar to (10), but performs a Taylor expansion around an arbitrary point rather than the specific point , and the second part is precisely (10). Note, however, that here we are assuming both of two conditions to hold, rather than one of two. Hence, we are implicitly assuming that the first item of Assumption 3 does not have a significant probability of occurring. For stationary kernels, the only situations where an endpoint has a high probability of being optimal are those where f varies very slowly (e.g., the SE kernel with a larger lengthscale than the domain width). Such functions are of limited practical interest.

Similarly to the noiseless setting (de Freitas et al., 2012), all of the above assumptions hold for the SE kernel, as well as the Matérn-kernel with , with the added caveat that in Assumption 4 is a function of the lengthscale and cannot be chosen arbitrarily. Specifically, a smaller lengthscale implies a smaller value of . In contrast, in Assumptions 2 and 3 can be made arbitrary small by suitably changing the constants , and so on.

An illustration of some of the main assumptions and their associated constants is given in Figure 1.

Our upper bound is formally stated as follows.

Theorem 1. (Upper Bound) Consider the problem of BO in one dimension described in Section 2.1, with time horizon T and noise variance 0 and . Under Assumptions 1, 2, and 3, there exists an algorithm satisfying the following: With probability at least (with respect to the Gaussian process f), the average cumulative regret (averaged over the noisy

samples) satisfies

Here and are defined in Assumptions 2 and 3, and C depends only on the constants therein and

The assumption that for some is very mild, since typically is constant with respect to T. The proof of Theorem 1 extends immediately to a high probability guarantee with respect to both f and the noisy samples (i.e., holding with probability 1 below). We have stated the above form for consistency with the lower bound, which will be given in Section 4.

3.1. High-Level Description of the Algorithm

The algorithm considered in the proof of Theorem 1 is described informally in Algorithm 1; the details will be established throughout the proof of Theorem 1, and a complete description is given in Appendix B.

As in the noiseless setting (de Freitas et al., 2012), the idea is to operate in epochs and sample a set of increasingly closelypacked points to reduce the posterior variance, but only within a set of potential maximizers that are updated according to the confidence bounds. As a simple means of bringing the effective noise level down, we perform resampling, i.e., sampling the same point times consecutively. In each epoch, we sample enough to be able to produce upper and lower confidence bounds that differ by at most a target value within , and then the target is halved for the next epoch.

We do not expect our algorithm to perform well in practice by any means, but it still suffices for our purposes in establishing regret. Indeed, we have made no attempt to optimize the corresponding constant factors, and doing so would require more sophisticated techniques. Moreover, the quantities , and in Algorithm 1 are chosen as functions of both the kernel and the constants appearing in our assumptions, which limits the algorithm’s practical utility even further. Note, however, that these constants are merely a function of the kernel, and that suitable bounds suffice in place of exact values (e.g., lower bound on , upper bound on

While our algorithm assumes a known time horizon T (which is used when selecting ; see Appendix B), this assumption can easily be dropped via a standard doubling trick. The details are given in Appendix A.

3.2. Auxiliary Lemmas

Here we present two very standard auxiliary lemmas. We begin with a simpler version of the conditions of Srinivas et al. (Srinivas et al., 2010) guaranteeing that the posterior mean and variance provide valid confidence bounds with high probability. The reason for being slightly simpler is that we are considering a fixed time horizon.

Lemma 1. Fix . For any finite set of points D and time horizon T, under the choice , it holds that

with probability at least

Proof. It was shown in (Srinivas et al., 2010) that for fixed x and t, the event holds with probability at least . the lemma follows by substituting the choice of and taking the union bound over the

The following lemma is also standard, and has been used (implicitly or explicitly) in the study of multiple algorithms that eliminate suboptimal points based on confidence bounds (de Freitas et al., 2012; Contal et al., 2013; Bogunovic et al., 2016b). For completeness, we give a short proof.

Lemma 2. Suppose that at time t, for all x within a set of points , it holds that

for some bounds

Then any point satisfying must also satisfy

That is, any -suboptimal point can be ruled out according to the confidence bounds (15).

Proof. We have

where (18) and (22) follow from (16), (19) and (21) follow from the confidence bounds in (15), and (20) follows from the assumption

3.3. Outline of Proof of Theorem 1

Here we provide a high-level outline of the Proof of Theorem 1; the details are given in Appendix B.

Algorithm 1 only samples on a discrete sub-domain L. This set is chosen to be a set of regularly-spaced points that are fine enough to ensure that the cumulative regret with respect to is within a constant value of the cumulative regret with respect to . Working with the finite set L helps to simplify the subsequent analysis.

We split the epochs into two classes, which we call early epochs and late epochs. The late epochs are those in which we have shrunk the potential maximizers down enough to be entirely within the locally quadratic region, cf., Figure 1; here we only discuss the second case of Assumption 3, which is the more interesting of the two. Since the width of the locally quadratic region is constant, we can show that this occurs after a finite number of epochs, each lasting for at most O(log T) time. Hence, even if we naively upper bound the instant regret by according to (8), the overall regret incurred within the early epochs is insignificant.

In the later epochs, we exploit the locally quadratic behavior to show that the set of potential maximizers shrinks rapidly, i.e., by a constant factor after each epoch. As a result, we can let the repeatedly-sampled set in Algorithm 1 lie within a given interval that similarly shrinks, thereby controlling the number of samples we need to take in the epoch.

By Lemma 2, after we attain uniform -confidence, the instant regret incurred at each time thereafter is at most Using the fact that and summing over the epochs, we find that the overall regret behaves as in (13).

A notable difficulty that we omitted above is how we attain the confidence bounds in order to update the potential maximizers . While we directly apply Lemma 1 for the points that were repeatedly sampled, we found it difficult to do this for the non-sampled points. For those, we instead use Lipschitz properties of the function. In the early epochs, we use the global Lipschitz constant from Assumption 2, whereas in the later epochs, we find a considerably smaller Lipschitz constant due to the locally quadratic behavior.

Our lower bound is formally stated as follows.

Theorem 2. (Lower Bound) Consider the one-dimensional BO problem from Section 2.1, with time horizon T and noise variance . Under Assumptions 1, 2, and 4, any algorithm must yield the following: With probability at least respect to the Gaussian process f), the average cumulative regret (averaged over the noisy samples) satisfies

Here are defined in Assumptions 2 and 4, and depends only on the constants therein and

The assumption that for some is very mild, since typically is constant with respect to T. The assumption is required to avoid (23) contradicting the trivial O(T) upper bound. We also note that Theorem 2 immediately implies an lower bound on the expected regret with respect to both f and the noisy samples, as long as . As discussed following Assumption 4, the latter condition is mild.

In the remainder of the section, we introduce some of the main tools and ideas, and then outline the proof. We note that is trivial, as the average regret of the first sample alone is lower bounded by a constant. As a result, we only need to show that

4.1. Reduction to Binary Hypothesis Testing

Recall that f is a one-dimensional GP on [0, 1] with a stationary kernel , and think of the GP as being generated by the following procedure:

1. Generate a GP with the same kernel on the larger domain

2. Randomly shift equal probability, to obtain

Figure 2. Examples of functions considered in the lower bound. The two are identical up to a small horizontal shift.

Since the kernel is stationary, the shifting does not affect the distribution, so the induced distribution of f is indeed the desired GP on [0, 1].

We consider a genie argument in which is revealed to the algorithm. Clearly this additional information can only help the algorithm, so any lower bound still remains valid for the original setting. Stated differently, the algorithm knows that

See Figure 2 for an illustrative example.

This argument allows us to reduce the BO problem to a binary hypothesis test with adaptive sampling, as depicted in Figure 3. The hypothesis, indexed by the underlying function is . We show that under a suitable choice of , achieving small cumulative regret means that we can construct a decision rule high probability, i.e., the hypothesis test is successful. The contrapositive statement is then that if the hypothesis test cannot be successful, we cannot achieve small cumulative regret, from which it only remains to prove the former. This idea was used previously for stochastic convex optimization in (Raginsky & Rakhlin, 2011).

In the remainder of the analysis, we implicitly condition on an arbitrary realization of , meaning that all expectations and probabilities are only with respect to the random index V and/or the noise. We also assume that satisfies the conditions in Assumptions 1, 2, and 4, which holds with probability at least . For sufficiently small , the same assumptions are directly inherited by and .

Figure 3. Illustration of reduction from optimization to binary hypothesis testing. The gray boxes are considered to be fixed, whereas the white boxes are introduced for the purpose of proving the lower bound.

We henceforth assume that is indeed sufficiently small; we will verify that this is the case when we set its value.

We introduce some further notation. Letting , and denote the maximizers of and (which are unique by Assumption 2), we see that Assumption 4 ensures these are in the interior (0, 1), and hence the optimal values coincide: . To simplify some of the notation, instead of working with these functions directly, we consider the equivalent problem of minimizing the corresponding regret functions:

Indeed, since we assume the algorithm knows also the optimal value , it can always choose to transform the samples as . In this form, we have the convenient normalization

4.2. Auxiliary Lemmas

We first state the following useful properties of

Lemma 3. The functions and constructed above satisfy the following for sufficiently small under the conditions in Assumptions 2 and 4:

Proof. See Appendix C.

The first part states that any point can be better than -optimal for at most one of the two functions, the second part shows that the two functions are close for points near , and the third part shows that the instant regret is lower bounded by a quadratic function.

The first part of the Lemma 3 allows us to bound the cumulative regret using Fano’s inequality for binary hypothesis testing with adaptive sampling (Raginsky & Rakhlin, 2011). This inequality lower bounds the success probability of such a hypothesis test in terms of a mutual information quantity (Cover & Thomas, 2001). The resulting lower bound on regret is stated in the following; it is worth noting that the consideration of cumulative regret here provides a distinction from the analogous bound on the instant regret in (Raginsky & Rakhlin, 2011).

Lemma 4. Under the preceding setup, we have

where V is equiprobable on , and (x, y) are the selected points and samples when the minimization algorithm is applied to . Here is the functional inverse of the binary entropy function

Since this result is particularly fundamental to our analysis, we provide a proof at the end of this section.

4.3. Outline of Proof of Theorem 2

Here we provide a high-level outline of the proof of Theorem 2; the details are given in Appendix D.

Once the lower bound in Lemma 4 is established, the main technical challenge is upper bounding the mutual infor- mation. A useful property called tensorization (e.g., see (Raginsky & Rakhlin, 2011)) allows us to simplify the mutual information with the vectors (x, y) to a sum of mutual informations containing only a single pair :

Each such mutual information term can further be upper bounded by the KL divergence (Cover & Thomas, 2001) between the conditional output distributions corresponding to , which in turn equals

when . By substituting the property (29) given in Lemma 3, we find that I(V ; x, y) is upper bounded by a constant times . If we can further upper bound I(V ; x, y) by a constant in (0, log 2), then (31) establishes an lower bound.

We proceed by considering the cases separately, with mer case will immediately give the lower bound in Theorem 2 when we set , whereas in the latter case, we can use (30) to show that is upper bounded by a constant times , which means that the desired mutual information upper bound (see the previous paragraph) is attained under a choice of scaling as. Under this choice, the lower bound evaluates to , as required.

4.4. Proof of Lemma 4

As mentioned above, the proof of Lemma 4 follows along the lines of (Raginsky & Rakhlin, 2011), which in turn builds on previous works using Fano’s inequality to establish minimax lower bounds in statistical estimation problems; see for example (Yu, 1997).

In the following, we use to denote the cumulative regret associated with , respectively, and we generically write to denote one of the two with

We first use Markov’s inequality to write

for any . We proceed by analyzing the probability on the right-hand side.

Recall that V is equiprobable on erated by running the optimization algorithm on the sequence of inputs x, let be the index with the lower cumulative regret . By Lemma 3, can be less than for at most one of the two functions, and hence, if we must have . Therefore,

where, here and subsequently, and denote probabilities and expectations when the underlying instant regret function is (i.e., the underlying function that the algorithm seeks to maximize is

Continuing, we can lower bound the probability appearing

in (32) as follows:

where (35) follows from (33), and (36) follows from Fano’s inequality for binary hypothesis testing with adaptive sampling (see Eq. (22) and (24) of (Raginsky & Rakhlin, 2011)). The proof is completed by combining (32) and (36), and recalling that can be arbitrarily small.

We have established tight scaling laws on the regret for Bayesian optimization in one dimension, showing that the optimal scaling is and under mild technical assumptions on the kernel. Our results highlight some limitations of the widespread upper bounds based on the information gain, as well as providing cases where the noisy Bayesian setting is provably less difficult than its non-Bayesian RKHS counterpart.

An immediate direction for further work is to sharpen the constant factors in the upper and lower bounds, and to establish whether the upper bound is attained by any algorithm that can also provide state-of-the-art performance in practice. We re-iterate that our algorithm is certainly not suitable for this purpose, as its cumulative regret contains large constant factors, and the algorithm makes use of a variety of specific constants present in the assumptions (though they are merely a function of the kernel).

We expect our techniques to extend to any constant dimension ; the main ideas from the noiseless upper bound still apply (de Freitas et al., 2012), and in the lower bound we can choose an arbitrary single dimension and introduce a random shift in that direction as per Section 4.1. While these extensions may still yieldregret, the dependence on d would be exponential or worse in the upper bound, but constant in the lower bound, with the latter dependence certainly being suboptimal. Multi-dimensional lower bounding techniques based on Fano’s inequality (Ra- ginsky & Rakhlin, 2011) may improve the latter to poly(d), but overall, attaining a sharp joint dependence on T and d appears to require different techniques.

Acknowledgments. I would like to thank Ilija Bogunovic for his helpful comments and suggestions. This work was supported by an NUS startup grant.

Bogunovic, I., Scarlett, J., and Cevher, V. Time-varying Gaussian process bandit optimization. In Int. Conf. Art. Intel. Stats. (AISTATS), 2016a.

Bogunovic, I., Scarlett, J., Krause, A., and Cevher, V. Trun- cated variance reduction: A unified approach to Bayesian optimization and level-set estimation. In Conf. Neur. Inf. Proc. Sys. (NIPS), 2016b.

Bubeck, S. and Cesa-Bianchi, N. Regret Analysis of Stochastic and Nonstochastic Multi-Armed Bandit Problems. Found. Trend. Mach. Learn. Now Publishers, 2012.

Bull, A. D. Convergence rates of efficient global optimiza- tion algorithms. J. Mach. Learn. Res., 12(Oct.):2879– 2904, 2011.

Contal, E., Buffoni, D., Robicquet, A., and Vayatis, N. Machine Learning and Knowledge Discovery in Databases, chapter Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Exploration, pp. 225–240. Springer Berlin Heidelberg, 2013.

Cover, T. M. and Thomas, J. A. Elements of Information Theory. John Wiley & Sons, Inc., 2001.

de Freitas, N., Zoghi, M., and Smola, A. J. Exponential regret bounds for Gaussian process bandits with deterministic observations. In Int. Conf. Mach. Learn. (ICML), 2012.

Desautels, T., Krause, A., and Burdick, J. W. Parallelizing exploration-exploitation tradeoffs in Gaussian process bandit optimization. J. Mach. Learn. Res., 15(1):3873– 3923, 2014.

Grünewälder, S., Audibert, J.-Y., Opper, M., and Shawe- Taylor, J. Regret bounds for Gaussian process bandit problems. In Int. Conf. Art. Intel. Stats. (AISTATS), pp. 273–280, 2010.

Hennig, P. and Schuler, C. J. Entropy search for information- efficient global optimization. J. Mach. Learn. Research, 13(1):1809–1837, 2012.

Hernández-Lobato, J. M., Hoffman, M. W., and Ghahra- mani, Z. Predictive entropy search for efficient global optimization of black-box functions. In Adv. Neur. Inf. Proc. Sys. (NIPS), pp. 918–926, 2014.

Kandasamy, K., Schneider, J., and Póczos, B. High di- mensional Bayesian optimisation and bandits via additive models. In Int. Conf. Mach. Learn., 2015.

Kawaguchi, K., Kaelbling, L. P., and Lozano-Pérez, T. Bayesian optimization with exponential convergence. In Conf. Neur. Inf. Proc. Sys. (NIPS), 2015.

Kleinberg, R., Slivkins, A., and Upfal, E. Multi-armed bandits in metric spaces. In Proc. ACM Symp. Theory Comp. (STOC), pp. 681–690, 2008.

Krause, A. and Ong, C. S. Contextual Gaussian process bandit optimization. In Conf. Neur. Inf. Proc. Sys. (NIPS), pp. 2447–2455. Curran Associates, Inc., 2011.

Raginsky, M. and Rakhlin, A. Information-based complexity, feedback and dynamics in convex programming. IEEE Trans. Inf. Theory, 57(10):7036–7056, Oct. 2011.

Rasmussen, C. E. Gaussian processes for machine learning. MIT Press, 2006.

Rolland, P., Scarlett, J., Bogunovic, I., and Cevher, V. High- dimensional Bayesian optimization via additive models with overlapping groups. In Int. Conf. Art. Intel. Stats. (AISTATS), 2018.

Russo, D. and Van Roy, B. Learning to optimize via information-directed sampling. In Conf. Neur. Inf. Proc. Sys. (NIPS), 2014.

Scarlett, J., Bogunovic, I., and Cevher, V. Lower bounds on regret for noisy Gaussian process bandit optimization. In Conf. Learn. Theory (COLT). 2017.

Shahriari, B., Swersky, K., Wang, Z., Adams, R. P., and de Freitas, N. Taking the human out of the loop: A review of Bayesian optimization. Proc. IEEE, 104(1): 148–175, 2016.

Shekhar, S. and Javidi, T. Gaussian process bandits with adaptive discretization. http://arxiv.org/abs/1712.01447, 2017.

Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M. Gaussian process optimization in the bandit setting: No regret and experimental design. In Int. Conf. Mach. Learn. (ICML), 2010.

Wang, Z., Shakibi, B., Jin, L., and de Freitas, N. Bayesian multi-scale optimistic optimization. In Int. Conf. Art. Intel. Stats. (AISTATS), pp. 1005–1014, 2014.

Wang, Z., Zhou, B., and Jegelka, S. Optimization as esti- mation with Gaussian processes in bandit settings. In Int. Conf. Art. Intel. Stats. (AISTATS), 2016.

Yu, B. Assouad, Fano, and le Cam. In Festschrift for Lucien Le Cam, pp. 423–435. Springer, 1997.

Tight Regret Bounds for Bayesian Optimization in One Dimension (Jonathan Scarlett, ICML 2018)

Suppose that we have an algorithm that depends on the time horizon and achieves for some C > 0. We show that we can also achieve is unknown.

To see this, fix an arbitrary integer , and repeatedly run the algorithm with fixed time horizons , etc., until T points have been sampled. The number of stages is no more than . Moreover, we have

where the first inequality uses , and the last inequality uses . This establishes the desired claim.

We continue from the auxiliary results given in Section 3, proceeding in several steps. Algorithm 2 gives a full description of the algorithm; the reader is encouraged to refer to this throughout the proof, rather than trying to understand all the steps therein immediately. Note that the constants used in the algorithm come from Assumptions 2 and 3.

Reduction to a finite domain. Our algorithm only samples f within a finite set of pre-defined points. We choose these points to be regularly spaced, and close enough to ensure that the highest function value is within of the maximum . Under condition (8) in Assumption 2 (which implies that -Lipschitz continuous), it suffices to choose

where Z denotes the integers. Here we add x = 1 to L because it will be notationally convenient to ensure that the endpoints {0, 1} are both included in the set. Note that , which we crudely upper bound by

Since , the cumulative regret with respect to the best point in L is such that

Hence, it suffices to bound instead of . For convenience, we henceforth let denote an arbitrary input that achieves , and we define the instant regret as

Conditioning on high-probability events. By assumption, the events in Assumptions 2 and 3 simultaneously hold with probability at least . Moreover, by setting in Lemma 1 and letting L be as in (38) with , we deduce that (14) holds with probability at least

Denoting the intersection of all events in Assumptions 2 and 3 by A, and the event in Lemma 1 by B, we can write the average regret given A as follows:

Algorithm 2 Full description of our algorithm, based on reducing uncertainty in epochs via repeated sampling.

Require: Domain D, GP prior (), time horizon T, constants

, and initial potential maximizers 2: Initialize time index t = 1 and epoch number i = 1. 3: while less than T samples have been taken do

• Initialize

• Construct (not necessarily a subset of or L) containing regularly-spaced points within the interval, with spacing

• For each , add its two nearest points in

For each sample taken, increment , and terminate if t > T. 9: Update the posterior distribution according to (5)–(6), with and respectively containing all the selected points and noisy samples so far. 10: For each

where Update the set of potential maximizers:

12: Increment i.

13: end while

where (43) follows since and , and (44) follows since condition (8) in Assumption 2 ensures that , in order to prove Theorem 1, it suffices to show that whenever the conditions of Assumptions 2–3 and Lemma 1 hold true. We henceforth condition on this being the case.

Sampling mechanism. Recall that represents the target confidence to attain by the end of the i-th epoch, and each such value is half of the previous value. For this interpretation to be valid, should be sufficient large so that the entire function is a priori known up to confidence ) in Assumption 2, the choice certainly suffices for this purpose.

In the i-th epoch, we repeatedly sample a sufficiently fine subset of L sufficiently many times to attain an overall confidence of ). Specifically:

• We sample each point times and average the resulting observations, yielding an effective noise variance of and we choose large enough so that is sufficient.

• To design , we consider the interval

which is the smallest interval (intersected with L) containing . We select a Lipschitz constant (to be specified later) such that -Lipschitz within , and then we choose to ensure the following:

is the width of the interval. With the restriction of sampling within the fine discretization L, we can simply “round” to the two nearest points,1 yielding a suitable set of cardinality at most

Combining these, the total number of samples is given by

At the points that were sampled, we performed enough repetitions to attain a variance of at most based on those samples

alone. The information from any earlier samples only reduces the variance further, so the overall posterior variance2

For the points in that we didn’t sample, we note that the following confidence bounds are valid as long as f is -Lipschitz continuous within

where is the closest sampled point to x. If x is itself in , these expressions reduce to (50).

Now, since we have ensured the condition (46), we find that we can weaken (51)–(52) to

That is, as long as the Lipschitz constant is valid, we have -confidence at the end of the i-th epoch. As a result, by Lemma 2, the updated set of potential maximizers

with t being the ending time of the epoch, must only contain points within L whose function value is within Below, we will choose differently in different epochs, while still ensuring the required Lipschitz condition is valid.

Analysis of early epochs. Recall the following:

• By Assumption 1, the constant lower bounds the separation between and the function value at the second highest local maximum (if any).

• By Assumption 3, we either have at an endpoint and the locally linear behavior (9), or we have and the locally quadratic behavior (10).

In the epochs for which , we choose ), which is clearly a valid Lipschitz constant. We claim that after a finite number of epochs, all points , and therefore, to be greater than . We henceforth distinguish between the two cases using the terminology early epochs and late epochs.

To see that the preceding claim is true, we consider the two cases of Assumption 3:

• In the first case, all points satisfying are at least -suboptimal by the locally linear behavior (9) and the

• In the second case, all points satisfying are at least -suboptimal by the locally quadratic behavior (9) and the

Hence, in either case, all points satisfying are at least -suboptimal, where . As a result, to establish the desired claim, we only need to show that contains no points with instant regret

Since (as stated following (38)), we find that as long as ,3 it suffices that only contains

points such that , this happens as soon as is constant and we halve end of each epoch, it must be that only a finite number of epochs pass before this occurs, with depending only on

For these early epochs, we simply upper bound ) by one, meaning their overall cumulative time

where we have used the fact that in these epochs.

Analysis of late epochs. Recall that we consider ourselves in a late epoch as soon as . This condition implies that all points in are within a distance of ,4 yielding the locally linear behavior (9) if is an endpoint, and the locally quadratic behavior (10) otherwise. Moreover, Assumption 3 assumes in the latter case, and as a result, the algorithm can identify which case has occurred: If contains an endpoint, then we are in the first case, whereas if , then we are in the second case.

Accordingly, the algorithm can choose the Lipschitz constant differently in the two cases. In the first case, we simply continue to use the global choice from (8). In the second case, we observe that , and recall from (8) that -Lipschitz continuous. Since the width of the interval of interest , we conclude that within , and accordingly, we can set

We initially focus on this second case (which is the more interesting of the two), and later return to the first case.

Recall that within the i-th epoch, all points with have already been removed from the potential maximizers (cf., Lemma 2). This implies that the points sampled incur instant regret at most

and hence, since we have established that

From this fact and the locally quadratic behavior (10), we deduce that the width defined in (47) satisfies

Grouping all the constants together and writing , we can simplify this to

for suitably-chosen

Bounding the cumulative regret. In the early epochs, we crudely upper bound the regret at each time instant by (cf., (8)). Hence, since the total cumulative time of these epochs satisfies (55) for bounded , and as per (41), the corresponding total cumulative regret is upper bounded by

for some

For the late epochs, we make use of the instant regret bound in (57), depending on the epoch index i. Since this upper bound is decreasing in i, and the epoch lengths satisfy (60), we can upper bound by considering the hypothetical case that the epoch lengths are exactly the right-hand side of (60), and the instant regret incurred at time

In this situation, we can easily upper bound the total number of epochs: The last epoch must certainly be no larger than , defined to be the smallest i such that the term on the right-hand side of (60) is T or higher. Substituting

For technical reasons, here and subsequently we can assume without loss of generality that

for arbitrarily small and sufficiently large T; otherwise, Theorem 1 states the trivial bound . Since , this technical condition means the right-hand side of (62) exceeds one.

where (64) follows from (60) and the fact that , (65) follows since , (66) follows since , (67) follows since and , and (68) follows by substituting the upper bound on ). Using the fact that , and recalling that is constant, we simplify (68) to

for some . Note that we can safely drop the term in (68) due to the assumption in Theorem 1.

Handling the first case in Assumption 3. From (56) onwards, we focused only on the second case of Assumption 3. In the first case, we have a worse Lipschitz constant , but the width also shrinks faster: By the locally linear behavior (9), achieving -confidence not only brings the interval width down to at most , but also further down to . Hence, we lose a factor of in the Lipschitz constant, but we gain a factor of in the upper bound on Since the number of points sampled in (49) contains the product of the two, the final result remains unchanged, i.e., we still have (69), possibly with a different constant

Completion of the proof. Combining (39), (44), (61) and (69), we obtain

for some constant . As stated following (62), we can assume without loss of generality that

, which means that the third term of (70) dominates the second, and the proof is compete.

For the first part, we consider sufficiently small so that , for given in Assumption 2 and in Assumption 4. Since all local maxima are at least -suboptimal, achieving requires that x lies within a small interval around . Moreover, the locally quadratic behavior (12) in Assumption 4 yields within this interval when is sufficiently small. Combining this with gives , and since , the triangle inequality yields . Again using (12), we conclude that , as required.

For the second part, we recall from (24)–(25) that and , where . Again assuming is sufficiently small (i.e., less than ), we can apply the general Taylor expansion according to (11) to obtain

where . Since is -Lipschitz continuous (see (8)) and equals zero at , we must have . Hence, and using the triangle inequality along with (71)–(72), we have

which proves (29).

Using the locally quadratic behavior in (12), we deduce that (30) holds for all x within distance of the respective function optimizer. On the other hand, if the distance from the optimizer is more than , then a combination of (7) and (12) reveals that r(x) is bounded away from zero. Since the quadratic terms in (30) are also bounded from above due to the fact that , we conclude that (30) holds for sufficiently small

We continue from the reduction to binary hypothesis testing and auxiliary results given in Section 4. These results hold for an arbitrary given (deterministic) BO algorithm, which in general is simply a sequence of mappings that return the next point based on the previous samples . Recall also that we implicitly condition on an arbitrary realization of satisfying the events in Assumptions 2 and 4, meaning that all expectations and probabilities are only with respect to the random index and/or the noise. We proceed in two main steps.

Bounding the mutual information. To bound the mutual information term I(V ; x, y) appearing in (31), we first apply the following tensorization bound for adaptive sampling, which is based on the chain rule for mutual information (e.g., see (Raginsky & Rakhlin, 2011)):5

It is well known that the conditional mutual information is upper bounded by the maximum KL divergence between the resulting conditional output distributions (e.g., see Eq. (31) of (Raginsky & Rakhlin, 2011)). In our setting, there are only two values of v, and since we are considering Gaussian noise, their conditional output distributions are . Using the standard property that the KL divergence between the density functions is , we deduce that

Substituting property (29) in Lemma 3 gives

where (78) follows since . Averaging over , we obtain and substitution into (75) gives

Bounding the regret. We consider the cases and separately, where is defined in Lemma 3. In the former case, we immediately have a lower bound on the average cumulative regret, whereas in the latter case, the following lemma is useful.

Lemma 5. If defined in Lemma 3, then

Proof. Since V is equiprobable on

where (81) follows from (30) in Lemma 3, and (82) follows by expanding the square and lower bounding the cross-term by its negative absolute value.

Substituting the assumption , and canceling the term appearing on both sides, we obtain

where (84) follows from the Cauchy-Schwartz inequality, and (85) follows from Jensen’s inequality. Solving for yields the desired claim.

In the case , we claim that under the choice with a sufficiently large constant , it holds

that for some constant . Once this is established, combining the two cases with the choice of

which yields Theorem 2. We also note that by the assumption , we have for sufficiently large T that is indeed arbitrarily small under the above choice, as was assumed throughout the proof.6

It only remains to establish the claim stated above (86) when . By Lemma 5, we have , and substitution into (79) gives

Since , we deduce that (say) when is sufficiently large. As a result, (31) gives

where