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 yield
regret, 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