# On Information Gain and Regret Bounds in Gaussian Process Bandits

Sattar Vakili,
MediaTek Research, UK
<EMAIL_ADDRESS>Kia Khezeli
Mayo Clinic, MN, USA
<EMAIL_ADDRESS>Victor Picheny
Secondmind, UK
<EMAIL_ADDRESS>
###### Abstract

Consider the sequential optimization of an expensive to evaluate and possibly
non-convex objective function $f$ from noisy feedback, that can be regarded as
a continuum-armed bandit problem. Upper bounds on the regret performance of
several learning algorithms (GP-UCB, GP-TS, and their variants) are known
under both a Bayesian (when $f$ is a sample from a Gaussian process (GP)) and
a frequentist (when $f$ lives in a reproducing kernel Hilbert space) setting.
The regret bounds often rely on the maximal information gain $\gamma_{T}$
between $T$ observations and the underlying GP (surrogate) model. We provide
general bounds on $\gamma_{T}$ based on the decay rate of the eigenvalues of
the GP kernel, whose specialisation for commonly used kernels improves the
existing bounds on $\gamma_{T}$, and subsequently the regret bounds relying on
$\gamma_{T}$ under numerous settings. For the Matérn family of kernels, where
the lower bounds on $\gamma_{T}$, and regret under the frequentist setting,
are known, our results close a huge polynomial in $T$ gap between the upper
and lower bounds (up to logarithmic in $T$ factors).

Keywords— Information gain, effective dimension, regret bounds, Bayesian
optimization, GP-UCB, GP-TS, continuum-armed bandits.

##  1 Introduction

Bayesian optimization building on Gaussian Process (GP) models has been shown
to efficiently address the exploration-exploitation trade-off in the
sequential optimization of non-convex objective functions with bandit
feedback. There have been significant recent advances in the analysis of GP-
based Bayesian optimization algorithms, providing performance guarantees in
terms of regret. Regret is defined as the cumulative loss in the value of the
objective function $f$ at a sequence of observation points
$\\{x_{t}\\}_{t=1}^{T}$, $T\in\mathbb{N}$, in comparison to its value at a
global maximum $x^{*}\in\text{argmax}_{x\in\mathcal{X}}{f(x)}$ over the search
space $\mathcal{X}\in\mathbb{R}^{d}$ (see (1)). In their seminal paper,
Srinivas et al. (2010) established performance guarantees for GP-UCB, an
_optimistic_ optimization algorithm which sequentially selects the $x_{t}$
that maximize an upper confidence bound score over the search space. They
considered a fully Bayesian setting where $f$ is assumed to be a sample from a
GP with a known kernel, as well as a frequentist setting (referred to as
agnostic in Srinivas et al. (2010)) where $f$ is assumed to live in a
reproducing kernel Hilbert space (RKHS) with a known kernel. They showed an
$\tilde{\mathcal{O}}(\sqrt{\gamma_{T}T})$111We use the notations $\mathcal{O}$
and $\Omega$ to denote the standard mathematical orders and the notation
$\tilde{\mathcal{O}}$ to suppress the logarithmic factors. and an
$\tilde{\mathcal{O}}(\gamma_{T}\sqrt{T})$ regret bound for GP-UCB under the
Bayesian and frequentist settings, respectively, where $\gamma_{T}$ is the
maximal information gain between the observed sequence and the underlying
model (see section 2.5). Sublinearly scaling with $T$, $\gamma_{T}$ depends on
the underlying kernel and is interpreted as a measure for the difficulty of
the optimization task. Since the pioneering work of Srinivas et al., there
have been several results on improving the bounds toward their optimal value.
Chowdhury and Gopalan (2017) improved the regret bounds under the frequentist
setting by multiplicative logarithmic in $T$ factors. A variant of GP-UCB
(called SupKernelUCB), which builds on episodic independent batches of
observations, was shown in Valko et al. (2013) to achieve the
$\tilde{\mathcal{O}}(\sqrt{\gamma_{T}T})$ regret bound under the frequentist
setting. Furthermore, Chowdhury and Gopalan (2017) showed that
$\tilde{O}(\gamma_{T}\sqrt{T})$ regret bounds, under the frequentist setting,
also hold for GP-TS, a Bayesian optimization algorithm based on Thompson
Sampling which sequentially draws $x_{t}$ from the posterior distribution of
$x^{*}$. Under the Bayesian setting, Kandasamy et al. (2018) built on ideas
from Russo and Van Roy (2014, 2016) to show that GP-TS achieves the same order
of regret as GP-UCB.

The regret bounds mentioned above become complete only when $\gamma_{T}$ is
properly bounded, which proves challenging. We first overview the existing
upper and lower bounds on the maximal information gain in the literature. We
then discuss our contribution and compare it against the state of the art.

###  1.1 Upper and Lower Bounds on $\gamma_{T}$

Srinivas et al. (2010) showed that
$\gamma_{T}=\tilde{\mathcal{O}}(T^{\frac{d(d+1)}{2\nu+d(d+1)}})$ for the
Matérn-$\nu$ kernel (a Matérn kernel with smoothness parameter $\nu$; see
section 2.2 for the details), and $\gamma_{T}=\mathcal{O}(\log^{d+1}(T))$ for
the Squared Exponential (SE) kernel. Recently, Janz et al. (2020) introduced a
GP-UCB based algorithm (specific to the Matérn family of kernels), that
constructs a cover for the search space (as many hypercubes) and fits an
independent GP to each cover element. This analysis elicited an improved bound
for the Matérn-$\nu$ kernel;
$\gamma_{T}=\tilde{\mathcal{O}}(T^{\frac{d(d+1)}{2\nu+d(d+\bm{2})}})$.
Plugging these bounds on $\gamma_{T}$ into the
$\tilde{\mathcal{O}}(\sqrt{\gamma_{T}T})$ regret bounds mentioned above yields
explicit upper bounds, in terms of $T$, which are in the forms of
$\tilde{\mathcal{O}}(T^{\frac{\nu+d(d+1.5)}{2\nu+d(d+2)}})$ and
$\tilde{\mathcal{O}}(T^{\frac{1}{2}}\log^{\frac{d}{2}+1}(T))$, with
Matérn-$\nu$ and SE, respectively.

Finding the order optimal regret bounds is a long standing open question.
Under the frequentist setting, Scarlett et al. (2017) proved the
$\Omega(T^{\frac{\nu+d}{2\nu+d}})$ and
$\Omega(T^{\frac{1}{2}}\log^{\frac{d}{2}}(T))$ lower bounds on the regret
performance of any learning algorithm, with Matérn-$\nu$ and SE, respectively.
From the results of Scarlett et al. (2017) and Valko et al. (2013),
$\Omega(T^{\frac{d}{2\nu+d}})$ and $\Omega(\log^{d}(T))$ lower bounds on
$\gamma_{T}$ can be concluded for Matérn-$\nu$ and SE, respectively (see also
Janz et al., 2020), which facilitate the assessment of the upper bounds.

While the bounds are tight up to logarithmic factors for SE, a comparison
between the lower and upper bounds for the practically useful Matérn family of
kernels shows a drastic gap, which can surprisingly be as large as
$\mathcal{O}(\sqrt{T})$ in the case of regret, and as large as
$\mathcal{O}(T)$ in the case of $\gamma_{T}$, with particular configurations
of parameters $\nu$ and $d$.222Consider a case where $\nu$ and $d$ grow large;
$\nu$ grows faster than $d$ and slower than $d^{2}$. Then, the lower bound and
the upper bound on regret become arbitrarily close to $\Omega(\sqrt{T})$ and
$\mathcal{O}(T)$, respectively. Therefore, the worst case gap between them is
in $\mathcal{O}(\sqrt{T})$. The lower bound and the upper bound on
$\gamma_{T}$ become arbitrarily close to $\Omega(1)$ and $\mathcal{O}(T)$,
respectively. Therefore, the worst case gap between them is in
$\mathcal{O}({T})$. Motivated by this huge gap in the literature, we aim to
provide tight bounds on $\gamma_{T}$ (reducing these polynomial in $T$ gaps to
logarithmic ones), as outlined in the next section.

###  1.2 Contribution

Our contribution is in establishing novel bounds on $\gamma_{T}$, which
directly translate to new regret bounds for Bayesian optimization algorithms.
To achieve this, we use Mercer’s theorem to represent the GP kernel in terms
of its eigenvalue-eigenfeature decomposition —an inner product in the
corresponding reproducing kernel Hilbert space (RKHS)— which is infinite
dimensional for typical kernels. To overcome the difficulty of working in
infinite dimensional spaces, we use a projection on a finite $D$ dimensional
space that allows us to bound the information gain in terms of $D$ and the
spectral properties of the GP kernel. For a kernel with decreasing eigenvalues
$\\{\lambda_{m}\\}_{m=1}^{\infty}$, we consider two cases of polynomial,
$\lambda_{m}=\mathcal{O}(m^{-\beta_{p}})$, $\beta_{p}>1$, and exponential,
$\lambda_{m}=\mathcal{O}(\exp(-m^{\beta_{e}}))$, $\beta_{e}>0$, decays. We
prove
$\mathcal{O}\left(T^{\frac{1}{\beta_{p}}}\log^{1-\frac{1}{\beta_{p}}}(T)\right)$
and $\mathcal{O}\left(\log^{1+\frac{1}{\beta_{e}}}(T)\right)$ upper bounds on
$\gamma_{T}$ under these two cases, respectively. The application of our
bounds on $\gamma_{T}$ to the regret bounds results in new upper bounds based
on $\beta_{p}$ and $\beta_{e}$ which are summarized in Table 1. In comparison
to the existing works, which rely on specific kernels (e.g. Matérn-$\nu$ and
SE) for explicit regret bounds, our results provide general explicit regret
bounds, providing the conditions on the decay rate of the eigenvalues of the
GP kernel (referred to as eigendecay for brevity) are satisfied.

As an instance of polynomially decaying eigenvalues, our results apply to the
Matérn-$\nu$ kernel (see section 2.2) showing
$\tilde{\mathcal{O}}(T^{\frac{d}{2\nu+d}})$ and
$\tilde{\mathcal{O}}(T^{\frac{\nu+d}{2\nu+d}})$ bounds on $\gamma_{T}$ and
regret, respectively. Our bounds on $\gamma_{T}$ and regret (under the
frequentist setting) are tight, closing the gap with the respective
$\Omega(T^{\frac{d}{2\nu+d}})$ and ${\Omega}(T^{\frac{\nu+d}{2\nu+d}})$ lower
bounds reported in Scarlett et al. (2017); Janz et al. (2020), both up to
logarithmic factors. As an instance of exponentially decaying eigenvalues, our
results apply to the Squared Exponential (SE) kernel. A summary of the results
is given in Table 1.

Kernel Bound on $\gamma_{T}$ Regret Lower Bound Regret Upper Bound
$(\tilde{\mathcal{O}}(\sqrt{\gamma_{T}T}))$ Polynomial eigendecay
$\mathcal{O}\left(T^{\frac{1}{\beta_{p}}}\log^{1-\frac{1}{\beta_{p}}}(T)\right)$
- $\tilde{\mathcal{O}}\left(T^{\frac{\beta_{p}+1}{2\beta_{p}}}\right)$
Exponential eigendecay
$\mathcal{O}\left(\log^{1+\frac{1}{\beta_{e}}}(T)\right)$ -
$\tilde{\mathcal{O}}\left(T^{\frac{1}{2}}\log^{\frac{1}{2\beta_{e}}}(T)\right)$
Matérn$-\nu$
${\mathcal{O}}\left(T^{\frac{d}{2\nu+d}}\log^{\frac{2\nu}{2\nu+d}}(T)\right)$
$\Omega(T^{\frac{\nu+d}{2\nu+d}})$
$\tilde{\mathcal{O}}\left(T^{\frac{\nu+d}{2\nu+d}}\right)$ SE
$\mathcal{O}\left(\log^{d+1}(T)\right)$
$\Omega\left(T^{\frac{1}{2}}\log^{\frac{d}{2}}(T)\right)$
$\tilde{\mathcal{O}}\left(T^{\frac{1}{2}}\log^{\frac{d}{2}}(T)\right)$

Table 1: The Upper bounds on the maximal information gain $\gamma_{T}$ and the
regret of Bayesian optimization algorithms under general polynomial and
exponential conditions on the eigendecay of the GP kernel (see Definition 1),
as well as, with Matérn-$\nu$ and SE kernels (established in this paper). The
lower bounds on regret under the frequentist setting (on the third column of
the table) were reported in Scarlett et al. (2017). The gap between the upper
and lower bounds is reduced to logarithmic factors.

While we focus on the standard sequential optimization problem in this paper,
it is worth noting that the bounds on $\gamma_{T}$ are also essential for
numerous variants of the problem such as the ones under the settings with
contextual information, safety constraints and multi-fidelity evaluations (see
section 1.3 for a list of references). Our bounds on $\gamma_{T}$ directly
apply and improve the regret bounds depending on $\gamma_{T}$ under these
various settings.

The interest in the bounds on $\gamma_{T}$ goes beyond the regret bounds. For
example, the confidence bounds for the RKHS elements (see e.g., Chowdhury and
Gopalan, 2017, Theorem 2) depend on $\gamma_{T}$. Another closely related
quantity is the so called effective dimension $\tilde{\mathcal{D}}_{T}$ of the
problem that satisfies $\tilde{\mathcal{D}}_{T}=\mathcal{O}(\gamma_{T})$ (see
Valko et al., 2013; Calandriello et al., 2019; Janz et al., 2020, and Remark
1). Calandriello et al. (2019) introduced a variation of GP-UCB which improves
its computational cost. The improved computational cost depends on
$\tilde{\mathcal{D}}_{T}$. Our bounds on $\gamma_{T}$ (consequently on
$\tilde{\mathcal{D}}_{T}$) improve such bounds on the algorithmic properties
of GP-based methods.

###  1.3 Other Related Work

Recent years have shown an increasing interest in Bayesian optimization based
on GP models. Performance guarantees in terms of regret are studied under
various settings including contextual information (Krause and Ong, 2011), high
dimensional spaces (Djolonga et al., 2013; Mutny and Krause, 2018), safety
constraints (Berkenkamp et al., 2016; Sui et al., 2018), parallelization
(Kandasamy et al., 2018), multi-fidelity evaluations (Kandasamy et al., 2019),
ordinal models (Picheny et al., 2019), online control (Kakade et al., 2020),
and corruption tolerance (Bogunovic et al., 2020), to name a few. Javidi and
Shekhar (2018) introduced an adaptive discretization of the search space
improving the computational complexity of a GP-UCB based algorithm. Sparse
approximation of GP posteriors are shown to preserve the regret orders while
significantly improving the computational complexity of both GP-UCB (Mutny and
Krause, 2018; Calandriello et al., 2019) and GP-TS (Vakili et al., 2020). Most
of existing work reports regret bounds in terms of $\gamma_{T}$. Our results
directly apply to, and improve, the regret bounds in all of the works
mentioned above, should our bounds on $\gamma_{T}$ replace the existing ones.

Our analytical approach and conditions on the eigendecay of GP kernels bear
similarity to Chatterji et al. (2019), where the authors studied the problem
of online learning with kernel losses. The problems and their analysis,
however, hold substantial differences. A more challenging adversarial setting
was considered for the objective function in Chatterji et al. (2019). However,
the objective function was restricted to the subspace of one dimensional
functions in the RKHS, which is very limiting for our purposes (one of the
main challenges in our analysis is the infinite-dimensionality of the RKHS).
The algorithmic designs, based on exponential weights, under the adversarial
setting, are also significantly different from GP-UCB and GP-TS, especially,
in the sense that their analysis does not rely on the information gain.

Instead of Mercer’s Theorem, other decompositions of GP kernels may also be
used in a similar way to our analysis. For instance, decompositions based on
Fourier features were used in Mutny and Krause (2018) to implement
computationally efficient variations of GP-TS and GP-UCB. They did not however
consider the analysis of $\gamma_{T}$.

Under the Bayesian setting, Scarlett (2018) proved tight $\Omega(\sqrt{T})$
(up to a logarithmic in $T$ factor) lower bounds on regret when the search
space is one-dimensional ($d=1$). To the best of our knowledge, lower bounds
are unknown for the general case ($d>1$), under the Bayesian setting.

Both GP-UCB and GP-TS are rooted in the classic multi-armed bandit literature
(see Auer et al., 2002; Russo and Van Roy, 2016; Slivkins, 2019; Zhao, 2019,
and references therein). Our work strengthens the link between linear (Dani et
al., 2008; Rusmevichientong and Tsitsiklis, 2010; Abbasi-Yadkori et al., 2011;
Agrawal and Goyal, 2013; Abeille and Lazaric, 2017) and kernelized (GP-based)
(Srinivas et al., 2010; Chowdhury and Gopalan, 2017) models for sequential
optimization with bandit feedback, as we build our analysis based on a finite-
dimensional projection that is equivalent to linear bandits.

The remainder of the paper is organized as follows. The problem formulation,
the preliminaries on GPs, GP-UCB, GP-TS, and the background on the connection
between the regret bounds and the information gain are presented in section 2.
The analysis of the bounds on $\gamma_{T}$ is provided in section 3. The
explicit regret bounds (in terms of $T$) for Bayesian optimization algorithms
are given in section 4. The paper is concluded in section 5.

##  2 Problem Formulation and Preliminaries

In this section, we provide background information on sequential optimization,
GPs, and the connection between the information gain and the regret bounds for
Bayesian optimization algorithms.

We use the following notations throughout the paper. For a square matrix
$M\in\mathbb{R}^{n\times n}$, the notations $\det(M)$ and $\text{tr}(M)$
denote the determinant and the trace of $M$, respectively. The notation
$M^{\top}$ is used for the transpose of an arbitrary matrix $M$. For a
positive definite matrix $P$, $\log\det(P)$ denotes $\log(\det(P))$. The
identity matrix of dimension $n$ is denoted by $\mathbf{I}_{n}$. For a vector
$z\in\mathbb{R}^{n}$, the notation $\|z\|_{2}$ denotes its $l^{2}$ norm.

###  2.1 The Sequential Optimization Problem

Consider the sequential optimization of a fixed and unknown objective function
$f$ over a compact set $\mathcal{X}\subset\mathbb{R}^{d}$. A learning
algorithm $\pi$ sequentially selects an observation point
$x_{t}\in\mathcal{X}$ at each discrete time instance $t=1,2,\dots$, and
receives the corresponding real-valued reward $y_{t}=f(x_{t})+\epsilon_{t}$,
where $\epsilon_{t}$ is the observation noise. Specifically,
$\pi=\\{\pi_{t}\\}_{t=1}^{\infty}$ is a sequence of mappings
$\pi_{t}:\mathcal{H}_{t-1}\rightarrow\mathcal{X}$ from the history of
observations to a new observation point;
$\mathcal{H}_{t}=\\{\mathbf{X}_{t},\mathbf{y}_{t}\\}$,
$\mathbf{X}_{t}=[x_{1},x_{2},...,x_{t}]^{\top}$,
$\mathbf{y}_{t}=[y_{1},y_{2},...,y_{t}]^{\top}$, $x_{s}\in\mathcal{X}$,
$y_{s}\in\mathbb{R}$, for all $s\geq 1$. The regularity assumptions on $f$ and
$\epsilon_{t}$ are specified in section 2.4.

The goal is to minimize regret, defined as the cumulative loss compared to the
maximum attainable objective, over a time horizon $T$. Specifically,

$\displaystyle R(T;\pi)=\sum_{t=1}^{T}\left(f(x^{*})-f(x_{t})\right),$ (1)

where $x^{*}{\in}\footnotesize\mbox{argmax}_{x\in\mathcal{X}}f(x)$ is a global
maximum of $f$. To simplify the notation, the dependency on $\pi$ in the
notation of $\mathbf{X}_{t}$ has been omitted.

###  2.2 Gaussian Processes

The learning algorithms considered here build on GP (surrogate) models. A GP
is a random process $\\{{\hat{f}}(x)\\}_{x\in\mathcal{X}}$, in which all
finite subsets follow multivariate Gaussian distributions (Rasmussen and
Williams, 2006). The distribution of a GP can be specified by its mean
function $\mu(x)=\mathbb{E}[\hat{f}(x)]$ and a positive definite kernel (or
covariance function)
$k(x,x^{\prime})=\mathbb{E}\left[(\hat{f}(x)-\mu(x))(\hat{f}(x^{\prime})-\mu(x^{\prime}))\right]$.
Without loss of generality, it is typically assumed that $\forall
x\in\mathcal{X},\mu(x)=0$ for prior GP distributions.

Conditioning GPs on available observations provides us with powerful non-
parametric Bayesian (surrogate) models over the space of functions. In
particular, conditioned on $\mathcal{H}_{t}$, the posterior of $\hat{f}$ is a
GP with mean function $\mu_{t}(x)=\mathbb{E}[\hat{f}(x)|\mathcal{H}_{t}]$ and
kernel function
$k_{t}(x,x^{\prime})=\mathbb{E}[(\hat{f}(x)-\mu_{t}(x))(\hat{f}(x^{\prime})-\mu_{t}(x^{\prime}))|\mathcal{H}_{t}]$
specified as follows:

$\displaystyle\mu_{t}(x)$ $\displaystyle=$ $\displaystyle
k^{\top}_{\mathbf{X}_{t},x}(K_{\mathbf{X}_{t},\mathbf{X}_{t}}+\tau\mathbf{I})^{-1}\mathbf{y}_{t},$
$\displaystyle k_{t}(x,x^{\prime})$ $\displaystyle=$ $\displaystyle
k(x,x^{\prime})-k^{\top}_{\mathbf{X}_{t},x}(K_{\mathbf{X}_{t},\mathbf{X}_{t}}+\tau\mathbf{I})^{-1}k_{\mathbf{X}_{t},x^{\prime}},$

where $k_{\mathbf{X}_{t},x}=\left[\leavevmode\nobreak\
k(x_{1},x),k(x_{2},x),\dots,k(x_{t},x)\leavevmode\nobreak\ \right]^{\top}$ and
$K_{\mathbf{X}_{t},\mathbf{X}_{t}}$ is the ${t}\times{t}$ positive definite
covariance matrix, $[k(x_{i},x_{j})]_{i,j=1}^{t}$. The posterior variance of
$\hat{f}(x)$ is denoted by $\sigma^{2}_{t}(x)=k_{t}(x,x)$.

Matérn and squared exponential (SE) are perhaps the most popular kernels in
practice for Bayesian optimization (see e.g., Snoek et al., 2012; Shahriari et
al., 2016),

$\displaystyle\scriptsize k_{\text{Mat{\'{e}}rn}}(x,x^{\prime})$
$\displaystyle=$
$\displaystyle\frac{1}{\Gamma(\nu)2^{\nu-1}}\left(\frac{\sqrt{2\nu}r}{l}\right)^{\nu}B_{\nu}\left(\frac{\sqrt{2\nu}r}{l}\right),$
$\displaystyle\scriptsize k_{\text{SE}}(x,x^{\prime})$ $\displaystyle=$
$\displaystyle\exp\left(-\frac{r^{2}}{2l^{2}}\right),$

where $l>0$, $r=\|x-x^{\prime}\|_{2}$ is the Euclidean distance between $x$
and $x^{\prime}$, $\nu>0$ is referred to as the smoothness parameter, $\Gamma$
is the gamma function, and $B_{\nu}$ is the modified Bessel function of the
second kind. Variation over parameter $\nu$ creates a rich family of kernels.
The SE kernel can also be interpreted as a special case of Matérn family when
$\nu\rightarrow\infty$.

###  2.3 Bayesian Optimization Algorithms (GP-UCB and GP-TS)

GP-UCB relies on an _optimistic_ upper confidence bound score to select the
observation points. Specifically, at each time $t$, $x_{t}$ is selected as

$\displaystyle
x_{t}=\text{argmax}_{x\in\mathcal{X}}\mu_{t-1}(x)+\alpha_{t}\sigma_{t-1}(x),$

where $\mu_{t-1}$ and $\sigma_{t-1}$ are the posterior mean and the standard
deviation, based on previous observations defined in section 2.2, and
$\alpha_{t}$ is a user-specified scaling parameter.

GP-TS selects the observation points by posterior sampling. Specifically, at
each time $t$, a sample $\hat{f}_{t}(x)$ is drawn from a GP with mean
$\mu_{t-1}$ and kernel function $\alpha_{t}^{2}k_{t-1}$ where $\mu_{t-1}$ and
$k_{t-1}$ are the posterior mean and the posterior kernel, based on previous
observations defined in section 2.2, and $\alpha_{t}$ is a user-specified
scaling parameter. Then, $x_{t}$ is selected as

$\displaystyle x_{t}=\text{argmax}_{x\in\mathcal{X}}\ \hat{f}_{t}(x).$ (2)

The scaling parameters $\alpha_{t}$ are designed to balance the trade-off
between exploitation and exploration of the search space and increase with $t$
($\alpha_{t}>\alpha_{t^{\prime}}$ when $t>t^{\prime}$). See, e.g., Srinivas et
al. (2010); Chowdhury and Gopalan (2017) for the specifications of
$\alpha_{t}$.

###  2.4 Regularity Assumptions

The regret performance of the learning algorithms is analysed under two
different settings, referred to as Bayesian and frequentist.

Under the Bayesian setting, $f$ is assumed to be a sample from a prior GP with
kernel $k$. The observation noise $\\{\epsilon_{t}\\}_{t=1}^{T}$ are assumed
to be i.i.d. zero mean Gaussian random variables with variance $\tau$.

Under the frequentist setting, $f$ is assumed to live in the RKHS
corresponding to $k$. In particular, $\|f\|_{H_{k}}\leq B$, for some $B>0$,
where $\|\cdot\|_{H_{k}}$ denote the RKHS norm (see section 3.1 for the
definition of the RKHS norm). The observation noise are assumed to be i.i.d.
sub-Gaussian random variables. Specifically, it is assumed that $\forall
h\in\mathbb{R},\forall
t\in\mathbb{N},\mathbb{E}[e^{h\epsilon_{t}}]\leq\exp(\frac{h^{2}R^{2}}{2}),$
for some $R>0$. The sub-Gaussian assumption implies that
$\mathbb{E}[\epsilon_{t}]=0$, for all $t$.

###  2.5 The Information Gain and The Upper Bounds on Regret

The regret analysis of Bayesian optimization algorithms typically consists of
two main components. One is a bound on the maximal information gain
$\gamma_{T}$, and the other is a confidence bound for random processes. The
bound on $\gamma_{T}$ is treated identically under both Bayesian and
frequentist settings. Confidence bounds which are utilized under each setting
are different, however. To motivate the analysis of $\gamma_{T}$, we provide a
sketch for the analysis of GP-UCB. Since our bounds on $\gamma_{T}$ are
independent of the learning algorithm, they are indiscriminately applicable to
all settings where the regret bound is given in terms of $\gamma_{T}$.

A classic approach to the sequential optimization problem is to construct a
$1-\delta$ upper confidence bound for $f$, after $t-1$ observations, in the
form of

$\displaystyle U_{t}(x)=\mu_{t-1}(x)+\beta_{t}(\delta)\sigma_{t-1}(x).$ (3)

GP modelling provides us with closed form expressions for $\mu_{t-1}(x)$ and
$\sigma_{t-1}(x)$, while $\beta_{t}(\delta)$ is a properly chosen confidence
width multiplier that ensures $U_{t}(x)\geq f(x)$, with probability at least
$1-\delta$. Following the standard analysis (see e.g., Srinivas et al., 2010),
a probability union bound implies that, with probability at least $1-\delta$,
for all $t\geq 1$,

$\displaystyle f(x^{*})-f(x_{t})$ $\displaystyle\leq$
$\displaystyle\mu_{t-1}(x^{*})+\beta_{t}(3\delta/(\pi^{2}t^{2}))\sigma_{t-1}(x^{*})$
$\displaystyle-\mu_{t-1}(x_{t})+\beta_{t}(3\delta/(\pi^{2}t^{2}))\sigma_{t-1}(x_{t}).$

The selection rule of GP-UCB with
$\alpha_{t}=\beta_{t}(3\delta/(\pi^{2}t^{2}))$ indicates that
$\mu_{t-1}(x^{*})+\alpha_{t}\sigma_{t-1}(x^{*})\leq\mu_{t-1}(x_{t})+\alpha_{t}\sigma_{t-1}(x_{t})$.
Therefore, for GP-UCB, with probability at least $1-\delta$,
$f(x^{*})-f(x_{t})\leq 2\alpha_{t}\sigma_{t-1}(x_{t})$, for all $t\geq 1$.
Summing up both sides over $t$ and applying Cauchy-Schwarz inequality, we get,
with probability at least $1-\delta$,

$\displaystyle R(T;\text{GP-UCB})\leq 2\alpha_{T}\sqrt{\mathcal{D}_{T}T},$

where $\mathcal{D}_{T}=\sum_{t=1}^{T}\sigma^{2}_{t-1}(x_{t})$.

Srinivas et al. (2010) showed that, under the Bayesian setting with some mild
regularity assumptions which hold for most typical kernels (e.g., SE and
Matérn-$\nu$ with $\nu>2$),
$\beta_{t}(\delta)=\mathcal{O}(\sqrt{\log(t/\delta)})$, consequently
$\alpha_{T}=\mathcal{O}(\sqrt{\log(T/\delta)})$. Under the frequentist
setting, Chowdhury and Gopalan (2017) established similar confidence bounds;
albeit, with a much larger width multiplier
$\beta_{t}(\delta)=B+R\sqrt{2(\gamma_{t-1}+1+\log(1/\delta))}$ resulting in
$\alpha_{T}=\mathcal{O}(\sqrt{\gamma_{T}})$, and consequently an
$\mathcal{O}(\sqrt{\gamma_{T}})$ gap between the regret bounds, for GP-UCB,
under the Bayesian and frequentist settings. It is unknown whether this
confidence bound and the regret bounds for vanilla GP-UCB under the
frequentist setting can be improved. The main challenge in establishing
confidence bounds is the adaptivity of the observation sequence in the
sequential optimization problem (in contrast to an offline setting with
predetermined observation points). Of significant theoretical value, the
SupKernelUCB algorithm (Valko et al., 2013) gets around this technicality and
achieves $\mathcal{O}(\sqrt{\mathcal{D}_{T}T}\log^{2}(T))$ regret through the
use of an independent batch observation trick, which can be attributed back to
Auer (2002). The original analysis of SupKernelUCB, which was given on a
finite search space, can be extended to more general compact sets through a
discretization argument, preserving $\tilde{O}(\sqrt{\mathcal{D}_{T}T})$
regret (see Cai and Scarlett, 2020, Appendix A.4).

It remains to bound the cumulative variance at the observation points,
$\mathcal{D}_{T}$. The standard approach for bounding $\mathcal{D}_{T}$ is to
use the information gain that refers to the mutual information
$I(\mathbf{y}_{t};\hat{f})$ (Cover and Thomas, 2012) between $\mathbf{y}_{t}$
and $\hat{f}$. From the closed form expression of mutual information between
two multivariate Gaussian distributions, we know that
$I(\mathbf{y}_{t};\hat{f})=\frac{1}{2}\log\det(\mathbf{I}_{t}+\frac{1}{\tau}K_{\mathbf{X}_{t},\mathbf{X}_{t}}).$
Using Jensen’s inequality, Srinivas et al. (2010) proved that
$\mathcal{D}_{T}\leq c_{1}I(\mathbf{y}_{T};\hat{f})$ where
$c_{1}=2/\log(1+1/\tau)$ is an absolute constant.

It is standard to proceed by defining a kernel-specific and
$\mathbf{X}_{T}$-independent maximal information gain,

$\displaystyle\gamma_{T}=\sup_{\mathbf{X}_{T}\subseteq\mathcal{X}}I(\mathbf{y}_{T};\hat{f}).$
(4)

The regret bounds are then given in terms of $\gamma_{T}$.

For specific kernels (Matérn and SE), Srinivas et al. (2010); Janz et al.
(2020) proved upper bounds on $\gamma_{T}$ which are commonly used to provide
explicit regret bounds. The contribution of this paper is to derive novel
bounds on $\gamma_{T}$ (consequently, on $\mathcal{D}_{T}$) which immediately
translate to improved regret bounds under various settings.

##  3 Upper Bounds on the Information Gain

Our bounds on the information gain are achieved through a finite dimensional
projection of the GP model in the RKHS corresponding to $k$. We start with
outlining the details of the RKHS and the finite dimensional projection of the
GP model. We then present the bounds on $\gamma_{T}$.

###  3.1 RKHS and Mercer’s Theorem

Consider a positive definite kernel
$k:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}$ with respect to a finite
Borel measure (e.g., the Lebesgue measure) supported on $\mathcal{X}$. A
Hilbert space $H_{k}$ of functions on $\mathcal{X}$ equipped with an inner
product $\langle\cdot,\cdot\rangle_{H_{k}}$ is called an RKHS with reproducing
kernel $k$ if the following are satisfied. For all $x\in\mathcal{X}$,
$k(\cdot,x)\in H_{k}$, and for all $x\in\mathcal{X}$ and $f\in H_{k}$,
$\langle f,k(\cdot,x)\rangle_{H_{k}}=f(x)$ (reproducing property).

An RKHS is completely specified with its kernel function and vice-versa. The
inner product induces the RKHS norm $\|f\|^{2}_{H_{k}}=\langle
f,f\rangle_{H_{k}}$ that can be interpreted as a measure for the complexity of
$f$.

Mercer’s theorem provides an alternative representation for GP kernels as an
inner product of infinite dimensional feature maps (see e.g., Kanagawa et al.,
2018, Theorem 4.1).

######  Theorem 1 (Mercer’s Theorem).

Let $k$ be a continuous kernel with respect to a finite Borel measure on
$\mathcal{X}$. There exists $\\{(\lambda_{m},\phi_{m})\\}_{m=1}^{\infty}$ such
that $\lambda_{m}\in\mathbb{R}^{+}$, $\phi_{m}\in H_{k}$, for $m\geq 1$, and

$\displaystyle
k(x,x^{\prime})=\sum_{m=1}^{\infty}\lambda_{m}\phi_{m}(x)\phi_{m}(x^{\prime}).$

The $\\{\lambda_{m}\\}_{m=1}^{\infty}$ and the $\\{\phi_{m}\\}_{m=1}^{\infty}$
are referred to as the eigenvalues and the eigenfeatures (or eigenfunctions)
of $k$, respectively. Throughout the paper, it is assumed that
$\\{\lambda_{m}\\}_{m=1}^{\infty}$ are in a decreasing order:
$\lambda_{1}\geq\lambda_{2}\geq\dots$. Our technical assumption on $k$, used
in the analysis of $\gamma_{T}$, is specified next, that is the same as in
Chatterji et al. (2019), and holds for practically relevant kernels (cf.
Riutort-Mayol et al., 2020).

######  Assumption 1.

a) $k$ is a Mercer kernel (that is to satisfy the conditions of Mercer’s
theorem). b) $\forall x,x^{\prime}\in\mathcal{X}$,
$|k(x,x^{\prime})|\leq\bar{k}$, for some $\bar{k}>0$. c) $\forall
m\in\mathbb{N},\forall x\in\mathcal{X}$, $|\phi_{m}(x)|\leq\psi$, for some
$\psi>0$.

As a result of Mercer’s theorem, we can express a GP sample $\hat{f}$ in terms
of a weight vector in the feature space of $k$

$\displaystyle\hat{f}(\cdot)=\sum_{m=1}^{\infty}W_{m}\lambda^{\frac{1}{2}}_{m}\phi_{m}(\cdot),$
(5)

where the weights $W_{m}$ are i.i.d. random variables with standard normal
distribution (see e.g., Kanagawa et al., 2018, Remark 4.4). It is
straightforward to check that $\hat{f}$ given in (5) is a zero mean GP with
kernel $k$. We refer to this representation as the feature space
representation in contrast to the function space representation presented in
section 2.2.

The RKHS can also be represented in terms of
$\\{(\lambda_{m},\phi_{m})\\}_{m=1}^{\infty}$ using Mercer’s representation
theorem (see e.g., Kanagawa et al., 2018, Theorem 4.2).

######  Theorem 2 (Mercer’s Representation Theorem).

Let $\\{(\lambda_{m},\phi_{m})\\}_{m=1}^{\infty}$ be the same as in Theorem 1.
Then, the RKHS of $k$ is given by

$\displaystyle H_{k}=$
$\displaystyle\left\\{f(\cdot)=\sum_{m=1}^{\infty}w_{m}\lambda_{m}^{\frac{1}{2}}\phi_{m}(\cdot):\|f\|_{H_{k}}\triangleq\sum_{m=1}^{\infty}w_{m}^{2}<\infty\right\\}.$

Mercer’s representation theorem provides an explicit definition for the RKHS
norm. It also indicates that
$\\{\lambda_{m}^{\frac{1}{2}}\phi_{m}\\}_{m=1}^{\infty}$ form an orthonormal
basis for $H_{k}$.

###  3.2 Projection onto a Finite Dimensional Space

The feature space representation of typical GP kernels is infinite
dimensional. To overcome the difficulty of working in infinite dimensional
spaces, we use a projection $\mathcal{P}_{D}$ on a $D$ dimensional RKHS
consisting of the first $D$ features (corresponding to the $D$ largest
eigenvalues of the kernel). Specifically, consider the $D$-dimensional feature
space
$\bm{\phi}_{D}(\cdot)=[\phi_{1}(\cdot),\phi_{2}(\cdot),\dots,\phi_{D}(\cdot)]^{\top}$,
the $D$-dimensional column vector
$\mathbf{W}_{D}=[W_{1},W_{2},\dots,W_{D}]^{\top}$ and the diagonal matrix
$\Lambda_{D}=\text{diag}([\lambda_{1},\lambda_{2},\dots,\lambda_{D}])$ with
$[\lambda_{1},\lambda_{2},\dots,\lambda_{D}]$ as the diagonal entries. The
projection of $\hat{f}$ on the $D$-dimensional space is given by

$\displaystyle\mathcal{P}_{D}[\hat{f}(\cdot)]$ $\displaystyle=$
$\displaystyle\mathbf{W}_{D}^{\top}\Lambda_{D}^{\frac{1}{2}}\bm{\phi}_{D}(\cdot).$

Notice that $\mathcal{P}_{D}[\hat{f}]$ is a zero mean GP with kernel
$k_{P}(x,x^{\prime})=\sum_{m=1}^{D}\lambda_{m}\phi_{m}(x)\phi_{m}(x^{\prime})$.
We used the subscript $P$ to signify the space resulted from the projection.
In addition, let
$\mathcal{P}^{\bot}_{D}[\hat{f}]=\hat{f}-\mathcal{P}_{D}[\hat{f}]$ be the
orthogonal part of $\hat{f}$ with respect to the projection. Notice that
$\mathcal{P}^{\bot}_{D}[\hat{f}]$ is also a GP, with kernel
$k_{O}(x,x^{\prime})=k(x,x^{\prime})-k_{P}(x,x^{\prime})$. We used the
subscript $O$ to signify the orthogonal part.

We define the following quantity based on the tail mass of the eigenvalues of
$k$

$\displaystyle\delta_{D}=\sum_{m=D+1}^{\infty}\lambda_{m}\psi^{2}.$ (6)

If $\lambda_{m}$ diminishes at a sufficiently fast rate (see Defenition 1),
$\delta_{D}$ becomes arbitrarily small when $D$ is large enough. For all
$x,x^{\prime}\in\leavevmode\nobreak\ \mathcal{X}$, we then have
$k_{O}(x,x^{\prime})\leq\delta_{D}.$

###  3.3 Analysis of the Information Gain

Here, we establish a novel upper bound on $\gamma_{T}$.

######  Theorem 3 (Bounding $\gamma_{T}$).

Consider a GP with a kernel $k$ satisfying Assumption 1. For $D\in\mathbb{N}$,
let $\delta_{D}$ be as defined in (6). The following upper bound on
$\gamma_{T}$, defined in (4), holds for all $D\in\mathbb{N}$.

$\displaystyle\gamma_{T}\leq\frac{1}{2}D\log\left(1+\frac{\bar{k}T}{\tau
D}\right)+\frac{1}{2}\frac{\delta_{D}T}{\tau}.$

The expression can be simplified as

$\displaystyle\gamma_{T}=\mathcal{O}\left(D\log(T)+\delta_{D}T\right).$ (7)

In contrast to the existing results, Theorem 3 provides an upper bound in
terms of the spectral properties of the GP kernel through $\delta_{D}$ that is
applicable to all kernels based on their eigendecay. Specializing this bound
for common kernels (Matérn and SE) results in tight upper bounds on
$\gamma_{T}$ (up to a $\log(T)$ factor), and consequently improved bounds on
regret, across various settings, compared to the existing ones.

_Proof Sketch._ Recall
$I(\mathbf{y}_{t};\hat{f})=\frac{1}{2}\log\det(\mathbf{I}_{t}+\frac{1}{\tau}K_{\mathbf{X}_{t},\mathbf{X}_{t}}).$
The problem is thus bounding the $\log\det$ of the covariance matrix
$\mathbf{I}_{t}+\frac{1}{\tau}K_{\mathbf{X}_{t},\mathbf{X}_{t}}$ for an
arbitrary sequence $\mathbf{X}_{t}$ of observation points. To achieve this, we
use the $D$-dimensional projection in the RKHS. Recall $k=k_{P}+k_{O}$. Let us
use the notations
$K_{P,\mathbf{X}_{t},\mathbf{X}_{t}}=[k_{P}(x_{i},x_{j})]_{i,j=1}^{T}$ and
$K_{O,\mathbf{X}_{t},\mathbf{X}_{t}}=[k_{O}(x_{i},x_{j})]_{i,j=1}^{T}$ to
denote the corresponding covariance matrices. We show that
$\log\det(\mathbf{I}_{t}+\frac{1}{\tau}K_{\mathbf{X}_{t},\mathbf{X}_{t}})$ is
bounded in terms of
$\log\det(\mathbf{I}_{t}+\frac{1}{\tau}K_{P,\mathbf{X}_{t},\mathbf{X}_{t}})$
and a residual term, depending on $K_{O,\mathbf{X}_{t},\mathbf{X}_{t}}$. The
finite dimensionality of the RKHS of $k_{P}$ allows us to use
Weinstein–Aronszajn identity and the Gram matrix $G_{t}$ in the feature space
of $k_{P}$ to bound
$\log\det(\mathbf{I}_{t}+\frac{1}{\tau}K_{P,\mathbf{X}_{t},\mathbf{X}_{t}})$
in terms of $\log\det(\mathbf{I}_{D}+\frac{1}{\tau}G_{t})$. Elementary
calculation can be used to establish a bound on the $\log\det$ of a positive
definite matrix in terms of its trace. Utilizing this result, we bound
$\log\det(\mathbf{I}_{D}+\frac{1}{\tau}G_{t})$ by $\mathcal{O}(D\log(T))$. We
use the bound on the $\log\det$ of a positive definite matrix in terms of its
trace, again, to bound the residual term depending on
$K_{O,\mathbf{X}_{t},\mathbf{X}_{t}}$ by $\mathcal{O}(\delta_{D}T)$, taking
advantage of the property that $k_{O}(x,x^{\prime})\leq\delta_{D}$. A detailed
proof is given in Appendix A.

######  Remark 1.

The quantity $\tilde{\mathcal{D}}_{T}=\sum_{t=1}^{T}\sigma_{T}^{2}(x_{t})$ is
often referred to as the effective dimension of the sequential optimization
problem (Valko et al., 2013; Calandriello et al., 2019; Janz et al., 2020). To
obtain an explicit bound on $\gamma_{T}$, we increase $D$ such that $D\log(T)$
and $T\delta_{D}$ on the right hand side of (7) become of the same order. For
such sufficiently large $D$, we have $\gamma_{T}=\mathcal{O}(D\log(T))$;
consequently, $\tilde{\mathcal{D}}_{T}=\mathcal{O}(D\log(T))$, which explains
the use of the term effective dimension. That is to say the behavior of the
kernel becomes similar to that of a finite $D$-dimensional kernel (up to a
$\log(T)$ factor).

###  3.4 Conditions on the Eigendecay of the GP Kernel

We now discuss the implications of Theorem 3, under conditions on the
eigendecay of $k$. In particular, we define the following characteristic
eigendecay profiles (which are similar to those outlined in Chatterji et al.
(2019)).

######  Definition 1 (Polynomial and Exponential Eigendecay).

Consider the eigenvalues $\\{\lambda_{m}\\}_{m=1}^{\infty}$ of $k$ as given in
Theorem 1 in a decreasing order.

  1. 1.

For some $C_{p}>0$, $\beta_{p}>1$, $k$ is said to have a $(C_{p},\beta_{p})$
polynomial eigendecay, if for all $m\in\mathbb{N}$, we have $\lambda_{m}\leq
C_{p}m^{-\beta_{p}}$.

  2. 2.

For some $C_{e,1},C_{e,2},\beta_{e}>0$, $k$ is said to have a
$(C_{e,1},C_{e,2},\beta_{e})$ exponential eigendecay, if for all
$m\in\mathbb{N}$, we have $\lambda_{m}\leq
C_{e,1}\exp(-C_{e,2}m^{\beta_{e}})$.

The following corollary is a consequence of Theorem 3.

######  Corollary 1.

Consider $\gamma_{T}$ defined in (4). If $k$ has a $(C_{p},\beta_{p})$
polynomial eigendecay, we have

$\displaystyle\gamma_{T}\leq\left((\frac{C_{p}\psi^{2}T}{\tau})^{\frac{1}{\beta_{p}}}\log^{-\frac{1}{\beta_{p}}}(1+\frac{\bar{k}T}{\tau})+1\right)\log(1+\frac{\bar{k}T}{\tau}).$

The expression can be simplified as
$\gamma_{T}=\mathcal{O}\left(T^{\frac{1}{\beta_{p}}}\log^{1-\frac{1}{\beta_{p}}}(T)\right)$.

If $k$ has a $(C_{e,1},C_{e,2},\beta_{e})$ exponential eigendecay, we have

$\displaystyle\gamma_{T}\leq\left(\left(\frac{2}{C_{e,2}}(\log(T)+C_{\beta_{e}})\right)^{\frac{1}{\beta_{e}}}+1\right)\log(1+\frac{\bar{k}T}{\tau}),$

where $C_{\beta_{e}}=\log(\frac{C_{e,1}\psi^{2}}{\tau C_{e,2}})$ if
$\beta_{e}=1$, and
$C_{\beta_{e}}=\log(\frac{2C_{e,1}\psi^{2}}{\tau\beta_{e}C_{e,2}})+(\frac{1}{\beta_{e}}-1)\left(\log(\frac{2}{C_{e,2}}(\frac{1}{\beta_{e}}-1))-1)\right)$,
otherwise. The expression can be simplified as
$\gamma_{T}=\mathcal{O}(\log^{1+\frac{1}{\beta_{e}}}(T))$.

Corollary 1 gives general bounds on $\gamma_{T}$ providing the polynomial and
exponential conditions on the eigendecay of $k$ are satisfied. A detailed
proof is provided in Appendix B.

######  Remark 2.

It is known that, in the case of a Matérn kernel with smoothness parameter
$\nu>\frac{1}{2}$, $\lambda_{m}=O(m^{-\frac{2\nu+d}{d}})$ (Santin and
Schaback, 2016); and, in the case of SE kernel,
$\lambda_{m}=O(\exp(-m^{\frac{1}{d}}))$ (Belkin, 2018). Also, see Riutort-
Mayol et al. (2020) which gave closed form expression of their eigenvalue-
eigenfeature pairs on hypercubes. Thus, as special cases of polynomial and
exponential eigendecays, we have

$\displaystyle\gamma_{T}$ $\displaystyle=$
$\displaystyle{O}\left(T^{\frac{d}{2\nu+d}}\log^{\frac{2\nu}{2\nu+d}}(T)\right),\leavevmode\nobreak\
\leavevmode\nobreak\ \text{for Mat{\'{e}}rn-$\nu$ kernel},$
$\displaystyle\gamma_{T}$ $\displaystyle=$
$\displaystyle{O}\left(\log^{d+1}(T)\right),\leavevmode\nobreak\
\leavevmode\nobreak\ \text{for SE kernel},$

which are tight up to $\log(T)$ factors, based on the lower bounds reported in
Scarlett et al. (2017).

##  4 The Improved Regret Bounds for Bayesian Optimization Algorithms

Utilizing the upper bounds on $\gamma_{T}$ established in Theorem 3 and
Corollary 1, we can derive new regret bounds for Bayesian optimization
algorithms. In particular, consider the sequential optimization problem given
in section 2.1. Under the Bayesian setting, the application of our bounds on
$\gamma_{T}$ to $\mathcal{O}(\sqrt{\log(T)\gamma_{T}T})$ regret bounds for GP-
UCB and GP-TS established in Srinivas et al. (2010); Kandasamy et al. (2018)
results in
$\mathcal{O}\left(T^{\frac{\beta_{p}+1}{2\beta_{p}}}\log^{1-\frac{1}{2\beta_{p}}}(T)\right)$
and $\mathcal{O}\left(T^{\frac{1}{2}}\log^{1+\frac{1}{2\beta_{e}}}(T)\right)$
regret bounds under the polynomial and exponential eigendecays, respectively.
As special cases of polynomial and exponential eigendecays, the regret bound
for both GP-UCB and GP-TS with Matérn and SE kernels is
${\mathcal{O}}\left(T^{\frac{\nu+d}{2\nu+d}}\log^{\frac{4\nu+d}{4\nu+2d}}(T)\right)$
and $\mathcal{O}\left(T^{\frac{1}{2}}(\log(T))^{\frac{d}{2}+1}\right)$,
respectively.

Under the frequentist setting, the application of our bounds on $\gamma_{T}$
to $\mathcal{O}(\log^{2}(T)\sqrt{\gamma_{T}T})$ regret bounds for SupKernelUCB
reported in Valko et al. (2013), results in
$\mathcal{O}\left(T^{\frac{\beta_{p}+1}{2\beta_{p}}}\log^{\frac{5}{2}-\frac{1}{2\beta_{p}}}(T)\right)$
and
$\mathcal{O}\left(T^{\frac{1}{2}}\log^{\frac{5}{2}+\frac{1}{2\beta_{e}}}(T)\right)$
regret bounds under the polynomial and exponential eigendecays, respectively.
Consequently, the regret bounds for SupKernelUCB with Matérn and SE kernels
are
${\mathcal{O}}\left(T^{\frac{\nu+d}{2\nu+d}}\log^{\frac{5}{2}-\frac{d}{4\nu+2d}}(T)\right)$
and
$\mathcal{O}\left(T^{\frac{1}{2}}\log^{\frac{d}{2}+\frac{5}{2}}(T)\right)$,
respectively, reducing the gap with the lower bounds reported in Scarlett et
al. (2017) to a $\log^{\frac{5}{2}}(T)$ factor. Furthermore, under the
frequentist setting, our bounds on $\gamma_{T}$ improve the
$\tilde{\mathcal{O}}(\gamma_{T}\sqrt{T})$ regret bounds for vanilla GP-UCB and
GP-TS reported in Chowdhury and Gopalan (2017).

##  5  Conclusion

We introduced a general approach to bounding the information gain in Bayesian
optimization problems. We provided explicit bounds in terms of $T$ on
$\gamma_{T}$ and regret, under conditions on the eigendecay of the kernel,
which directly apply to common kernels such as Matérn and SE and show
significant improvements over the state of the art. Our results establish the
first tight regret bounds (up to $\log(T)$ factors) with the Matérn kernel
under the frequentist setting, which shows our bound on $\gamma_{T}$ is tight
(up to $\log(T)$ factors). The application of our bounds on $\gamma_{T}$ to
numerous other settings, where the regret bounds are given in terms of
$\gamma_{T}$, as listed in section 1.3, improves the best known regret bounds.

## Acknowledgment

We thank Jonathan Scarlett for insightful comments on an earlier version of
this paper.

## References

  * Abbasi-Yadkori et al. (2011) Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári.  Improved algorithms for linear stochastic bandits.  In _Advances in Neural Information Processing Systems_ , pages 2312–2320, 2011.
  * Abeille and Lazaric (2017) M. Abeille and A. Lazaric.  Linear Thompson sampling revisited.  In _Proceedings of Machine Learning Research_ , volume 54, pages 176–184, 2017.
  * Agrawal and Goyal (2013) S. Agrawal and N. Goyal.  Thompson sampling for contextual bandits with linear payoffs.  In _International Conference on Machine Learning_ , pages 127–135, 2013.
  * Auer (2002) P. Auer.  Using confidence bounds for exploitation-exploration trade-offs.  _Journal of Machine Learning Research_ , 3(Nov):397–422, 2002.
  * Auer et al. (2002) P. Auer, N. Cesa-Bianchi, and P. Fischer.  Finite-time analysis of the multiarmed bandit problem.  _Mach. Learn._ , 47(2–3):235–256, May 2002\.  ISSN 0885-6125.
  * Belkin (2018) M. Belkin.  Approximation beats concentration? an approximation view on inference with smooth radial kernels.  In _Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018_ , volume 75 of _Proceedings of Machine Learning Research_ , pages 1348–1361. PMLR, 2018.
  * Berkenkamp et al. (2016) F. Berkenkamp, A. Krause, and A. P. Schoellig.  Bayesian optimization with safety constraints: safe and automatic parameter tuning in robotics.  _arXiv preprint arXiv:1602.04450_ , 2016.
  * Bogunovic et al. (2020) I. Bogunovic, A. Krause, and J. Scarlett.  Corruption-tolerant Gaussian process bandit optimization.  _arXiv preprint arXiv:2003.01971_ , 2020.
  * Cai and Scarlett (2020) X. Cai and J. Scarlett.  On lower bounds for standard and robust Gaussian process bandit optimization.  _arXiv preprint arXiv:2008.08757_ , 2020.
  * Calandriello et al. (2019) D. Calandriello, L. Carratino, A. Lazaric, M. Valko, and L. Rosasco.  Gaussian process optimization with adaptive sketching: scalable and no regret.  In _Proceedings of the Thirty-Second Conference on Learning Theory_ , volume 99 of _Proceedings of Machine Learning Research_ , Phoenix, USA, 25–28 Jun 2019. PMLR.
  * Chatterji et al. (2019) N. Chatterji, A. Pacchiano, and P. Bartlett.  Online learning with kernel losses.  In _Proceedings of Machine Learning Research_ , volume 97, pages 971–980, Long Beach, California, USA, 09–15 Jun 2019. PMLR.
  * Chowdhury and Gopalan (2017) S. R. Chowdhury and A. Gopalan.  On kernelized multi-armed bandits.  In _International Conference on Machine Learning_ , pages 844–853, 2017.
  * Cover and Thomas (2012) T. M. Cover and J. A. Thomas.  _Elements of Information Theory_.  John Wiley & Sons, 2012.
  * Dani et al. (2008) V. Dani, T. P. Hayes, and S. M. Kakade.  Stochastic linear optimization under bandit feedback.  In _COLT_ , pages 355–366, 2008.
  * Djolonga et al. (2013) J. Djolonga, A. Krause, and V. Cevher.  High-dimensional Gaussian process bandits.  In _Advances in Neural Information Processing Systems 26_ , pages 1025–1033. Curran Associates, Inc., 2013.
  * Fang et al. (1994) Y. Fang, K. A. Loparo, and X. Feng.  Inequalities for the trace of matrix product.  _IEEE Transactions on Automatic Control_ , 39(12):2489–2490, 1994.
  * Janz et al. (2020) D. Janz, D. Burt, and J. Gonzalez.  Bandit optimisation of functions in the Matérn kernel RKHS.  In _Proceedings of Machine Learning Research_ , volume 108, pages 2486–2495. PMLR, 26–28 Aug 2020.
  * Javidi and Shekhar (2018) T. Javidi and S. Shekhar.  Gaussian process bandits with adaptive discretization.  _Electron. J. Statist._ , 12(2):3829–3874, 2018\.
  * Kakade et al. (2020) S. Kakade, A. Krishnamurthy, K. Lowrey, M. Ohnishi, and W. Sun.  Information theoretic regret bounds for online nonlinear control.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 15312–15325. Curran Associates, Inc., 2020.
  * Kanagawa et al. (2018) M. Kanagawa, P. Hennig, D. Sejdinovic, and B. K. Sriperumbudur.  Gaussian processes and kernel methods: A review on connections and equivalences.  _arXiv preprint arXiv:1807.02582_ , 2018.
  * Kandasamy et al. (2018) K. Kandasamy, A. Krishnamurthy, J. Schneider, and B. Póczos.  Parallelised Bayesian optimisation via Thompson sampling.  In _International Conference on Artificial Intelligence and Statistics_ , pages 133–142, 2018.
  * Kandasamy et al. (2019) K. Kandasamy, G. Dasarathy, J. Oliva, J. Schneider, and B. Poczos.  Multi-fidelity Gaussian process bandit optimisation.  _Journal of Artificial Intelligence Research_ , 66:151–196, 2019.
  * Krause and Ong (2011) A. Krause and C. S. Ong.  Contextual Gaussian process bandit optimization.  In _Advances in Neural Information Processing Systems 24_ , pages 2447–2455. Curran Associates, Inc., 2011.
  * Mutny and Krause (2018) M. Mutny and A. Krause.  Efficient high dimensional Bayesian optimization with additivity and quadrature fourier features.  In _Advances in Neural Information Processing Systems 31_ , pages 9005–9016. Curran Associates, Inc., 2018.
  * Picheny et al. (2019) V. Picheny, S. Vakili, and A. Artemev.  Ordinal Bayesian optimisation.  _arXiv preprint arXiv:1912.02493_ , 2019.
  * Pozrikidis (2014) C. Pozrikidis.  _An introduction to grids, graphs, and networks_.  Oxford University Press, 2014.
  * Rasmussen and Williams (2006) C. E. Rasmussen and C. K. Williams.  _Gaussian Processes for Machine Learning_.  MIT Press, 2006.
  * Riutort-Mayol et al. (2020) G. Riutort-Mayol, P.-C. Bürkner, M. R. Andersen, A. Solin, and A. Vehtari.  Practical hilbert space approximate bayesian gaussian processes for probabilistic programming.  _arXiv preprint arXiv:2004.11408_ , 2020.
  * Rusmevichientong and Tsitsiklis (2010) P. Rusmevichientong and J. N. Tsitsiklis.  Linearly parameterized bandits.  _Mathematics of Operations Research_ , 35(2):395–411, 2010.
  * Russo and Van Roy (2014) D. Russo and B. Van Roy.  Learning to optimize via posterior sampling.  _Mathematics of Operations Research_ , 39(4):1221–1243, 2014.
  * Russo and Van Roy (2016) D. Russo and B. Van Roy.  An information-theoretic analysis of Thompson sampling.  _The Journal of Machine Learning Research_ , 17(1), 2016\.
  * Santin and Schaback (2016) G. Santin and R. Schaback.  Approximation of eigenfunctions in kernel-based spaces.  _Advances in Computational Mathematics_ , 42(4):973–993, 2016.
  * Scarlett (2018) J. Scarlett.  Tight regret bounds for Bayesian optimization in one dimension.  _arXiv preprint arXiv:1805.11792_ , 2018.
  * Scarlett et al. (2017) J. Scarlett, I. Bogunovic, and V. Cevher.  Lower bounds on regret for noisy Gaussian process bandit optimization.  In _Proceedings of the 2017 Conference on Learning Theory_ , volume 65 of _Proceedings of Machine Learning Research_ , pages 1723–1742, Amsterdam, Netherlands, 07–10 Jul 2017. PMLR.
  * Shahriari et al. (2016) B. Shahriari, K. Swersky, Z. Wang, R. P. Adams, and N. de Freitas.  Taking the human out of the loop: A review of bayesian optimization.  _Proceedings of the IEEE_ , 104(1):148–175, 2016\.
  * Slivkins (2019) A. Slivkins.  Introduction to multi-armed bandits.  _arXiv preprint arXiv:1904.07272_ , 2019.
  * Snoek et al. (2012) J. Snoek, H. Larochelle, and R. P. Adams.  Practical Bayesian optimization of machine learning algorithms.  In _Advances in Neural Information Processing Systems 25_ , pages 2951–2959. Curran Associates, Inc., 2012.
  * Srinivas et al. (2010) N. Srinivas, A. Krause, S. Kakade, and M. Seeger.  Gaussian process optimization in the bandit setting: no regret and experimental design.  In _Proceedings of the 27th International Conference on International Conference on Machine Learning_ , pages 1015–1022. Omnipress, 2010\.
  * Sui et al. (2018) Y. Sui, V. Zhuang, J. W. Burdick, and Y. Yue.  Stagewise safe Bayesian optimization with Gaussian processes.  _arXiv preprint arXiv:1806.07555_ , 2018.
  * Vakili et al. (2020) S. Vakili, V. Picheny, and A. Artemev.  Scalable Thompson sampling using sparse gussian process mdels.  _Available at Arxiv._ , 2020.
  * Valko et al. (2013) M. Valko, N. Korda, R. Munos, I. Flaounas, and N. Cristianini.  Finite-time analysis of kernelised contextual bandits.  In _Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence_ , UAI’13, page 654–663, Arlington, Virginia, USA, 2013\. AUAI Press.
  * Zhao (2019) Q. Zhao.  Multi-armed bandits: theory and applications to online learning in networks.  _Synthesis Lectures on Communication Networks_ , 12(1):1–165, 2019.

##  Appendix A (Proof of Theorem 3)

We bound
$I(\mathbf{y}_{t};\hat{f})=\frac{1}{2}\log\det(\mathbf{I}_{t}+\frac{1}{\tau}K_{\mathbf{X}_{t},\mathbf{X}_{t}})$
for an arbitrary observation sequence $\mathbf{X}_{t}$. Recall $k_{P}$ and
$k_{O}$ and the respective covariance matrices
$K_{P,\mathbf{X}_{t},\mathbf{X}_{t}}=[k_{P}(x_{i},x_{j})]_{i,j=1}^{T}$ and
$K_{O,\mathbf{X}_{t},\mathbf{X}_{t}}=[k_{O}(x_{i},x_{j})]_{i,j=1}^{T}$, where
$k_{P}$ corresponds to the $D$-dimensional projection in the RKHS of $k$, and
$k_{O}$ corresponds to the orthogonal element. Noticing
$K_{\mathbf{X}_{t},\mathbf{X}_{t}}=K_{P,\mathbf{X}_{t},\mathbf{X}_{t}}+K_{O,\mathbf{X}_{t},\mathbf{X}_{t}}$,
we have

$\displaystyle I(\mathbf{y}_{t};\hat{f})$ $\displaystyle=$
$\displaystyle\frac{1}{2}\log\det(\mathbf{I}_{t}+\frac{1}{\tau}K_{\mathbf{X}_{t},\mathbf{X}_{t}})$
(8) $\displaystyle=$
$\displaystyle\frac{1}{2}\log\det\left(\mathbf{I}_{t}+\frac{1}{\tau}(K_{P,\mathbf{X}_{t},\mathbf{X}_{t}}+K_{O,\mathbf{X}_{t},\mathbf{X}_{t}})\right)$
$\displaystyle=$
$\displaystyle\frac{1}{2}\log\det\left((\mathbf{I}_{t}+\frac{1}{\tau}K_{P,\mathbf{X}_{t},\mathbf{X}_{t}})(\mathbf{I}_{t}+\frac{1}{\tau}(\mathbf{I}_{t}+\frac{1}{\tau}K_{P,\mathbf{X}_{t},\mathbf{X}_{t}})^{-1}K_{O,\mathbf{X}_{t},\mathbf{X}_{t}})\right)$
$\displaystyle=\frac{1}{2}\log\det(\mathbf{I}_{t}+\frac{1}{\tau}K_{P,\mathbf{X}_{t},\mathbf{X}_{t}})+\frac{1}{2}\log\det\left(\mathbf{I}_{t}+\frac{1}{\tau}(\mathbf{I}_{t}+\frac{1}{\tau}K_{P,\mathbf{X}_{t},\mathbf{X}_{t}})^{-1}K_{O,\mathbf{X}_{t},\mathbf{X}_{t}}\right),\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ $

where for the last line we used $\det(AB)=\det(A)\det(B)$ which holds for all
two square matrices of the same dimensions. The equation (8) decouples the
$\log\det$ of the covariance matrix corresponding to $k$ into that of $k_{P}$
and a residual term depending on $k_{O}$. We now proceed to bounding the two
terms on the right hand side of (8).

We can upper bound the first term on the right hand side of (8) using a bound
on the $\log\det$ of the Gram matrix in the $D$-dimensional feature space of
$k_{P}$. Let us define
$\bm{\Phi}_{t,D}=[\bm{\phi}_{D}(x_{1}),\bm{\phi}_{D}(x_{2}),\dots,\bm{\phi}_{D}(x_{t})]^{\top}$,
a $t\times D$ matrix which stacks the feature vectors
$\bm{\phi}^{\top}_{D}(x_{s})$, $s=1,\dots,t$, at the observation points, as
its rows. Notice that

$\displaystyle
K_{P,\mathbf{X}_{t},\mathbf{X}_{t}}=\bm{\Phi}_{t,D}\Lambda_{D}\bm{\Phi}_{t,D}^{\top}.$

Consider the Gram matrix

$\displaystyle
G_{t}=\Lambda_{D}^{\frac{1}{2}}\bm{\Phi}_{t,D}^{\top}\bm{\Phi}_{t,D}\Lambda_{D}^{\frac{1}{2}}.$

By Weinstein–Aronszajn identity333That is a special case of matrix determinant
lemma. [Pozrikidis, 2014]

$\displaystyle\det(\mathbf{I}_{D}+\frac{1}{\tau}G_{t})=\det(\mathbf{I}_{t}+\frac{1}{\tau}K_{P,\mathbf{X}_{t},\mathbf{X}_{t}}).$
(9)

We can prove the following lemma on the relation between the $\log\det$ and
the trace of a positive definite matrix.

######  Lemma 1.

For all positive definite matrices $P\in\mathbb{R}^{n\times n}$, we have

$\displaystyle\log\det(P)\leq n\log(\text{tr}(P)/n).$

The proof is provided at the end of this section.

We next bound the trace of $\mathbf{I}_{D}+\frac{1}{\tau}G_{t}$. Notice that,
for all $x\in\mathcal{X}$,

$\displaystyle\|\bm{\phi}_{D}(x)\Lambda^{\frac{1}{2}}_{D}\|^{2}_{2}$
$\displaystyle=$ $\displaystyle\sum_{m=1}^{D}\lambda_{m}\phi^{2}_{m}(x)$
$\displaystyle=$ $\displaystyle k_{P}(x,x)$ $\displaystyle\leq$
$\displaystyle\bar{k}.$

Thus,

$\displaystyle\text{tr}(\mathbf{I}_{D}+\frac{1}{\tau}G_{t})$ $\displaystyle=$
$\displaystyle
D+\frac{1}{\tau}\text{tr}\left(\sum_{s=1}^{t}\Lambda^{\frac{1}{2}}\bm{\phi}_{D}(x_{s})\bm{\phi}^{\top}_{D}(x_{s})\Lambda^{\frac{1}{2}}\right)$
$\displaystyle=$ $\displaystyle
D+\frac{1}{\tau}\sum_{s=1}^{t}\text{tr}\left(\Lambda^{\frac{1}{2}}\bm{\phi}_{D}(x_{s})\bm{\phi}^{\top}_{D}(x_{s})\Lambda^{\frac{1}{2}}\right)$
$\displaystyle=$ $\displaystyle
D+\frac{1}{\tau}\sum_{s=1}^{t}\text{tr}\left(\Lambda^{\frac{1}{2}}\bm{\phi}^{\top}_{D}(x_{s})\bm{\phi}_{D}(x_{s})\Lambda^{\frac{1}{2}}\right)$
$\displaystyle=$ $\displaystyle
D+\frac{1}{\tau}\sum_{s=1}^{t}{\|\bm{\phi}_{D}(x_{s})\Lambda^{\frac{1}{2}}\|_{2}^{2}}$
$\displaystyle\leq$ $\displaystyle D+\frac{t\bar{k}}{\tau}.$

For the first line we expanded the Gram matrix, the second line holds by
distributivity of trace over sum, and the third line is a result of
$\text{tr}(AA^{\top})=\text{tr}(A^{\top}A)$ which holds for any matrix $A$.

Using Lemma 1 and (9), we have

$\displaystyle\log\det(\mathbf{I}_{t}+\frac{1}{\tau}K_{P,\mathbf{X}_{t},\mathbf{X}_{t}})$
$\displaystyle=$ $\displaystyle\log\det(\mathbf{I}_{D}+\frac{1}{\tau}G_{t})$
(10) $\displaystyle\leq$ $\displaystyle
D\log\left(\frac{\text{tr}(\mathbf{I}_{D}+\frac{1}{\tau}G_{t})}{D}\right)$
$\displaystyle=$ $\displaystyle D\log(1+\frac{\bar{k}t}{\tau D}).$

To upper bound the second term on the right hand side of (8), we use
$k_{O}(x,x^{\prime})\leq\delta_{D}$. Notice that
$(\mathbf{I}_{t}+\frac{1}{\tau}K_{P,\mathbf{X}_{t},\mathbf{X}_{t}})^{-1}$ is a
positive definite matrix whose largest eigenvalue is upper bounded by $1$. For
two positive definite matrices $P_{1},P_{2}$ with the same dimensions, we have
$\text{tr}(P_{1}P_{2})\leq\bar{\lambda}_{P_{1}}\text{tr}(P_{2})$ where
$\bar{\lambda}_{P_{1}}$ is the largest eigenvalue of $P_{1}$ (cf. Fang et al.
[1994]). Thus

$\displaystyle\text{tr}\left((\mathbf{I}_{t}+\frac{1}{\tau}K_{P,\mathbf{X}_{t},\mathbf{X}_{t}})^{-1}K_{O,\mathbf{X}_{t},\mathbf{X}_{t}}\right)\leq\text{tr}(K_{O,\mathbf{X}_{t},\mathbf{X}_{t}}).$

Since $\forall x,x^{\prime}\in\mathcal{X},\leavevmode\nobreak\
k_{O}(x,x^{\prime})\leq\delta_{D}$, we have
$\text{tr}(K_{O,\mathbf{X}_{t},\mathbf{X}_{t}})\leq t\delta_{D}$. Therefore,

$\displaystyle\text{tr}\left(\mathbf{I}_{t}+\frac{1}{\tau}(\mathbf{I}_{t}+\frac{1}{\tau}K_{P,\mathbf{X}_{t},\mathbf{X}_{t}})^{-1}K_{O,\mathbf{X}_{t},\mathbf{X}_{t}}\right)\leq
t(1+\frac{1}{\tau}\delta_{D}).$

Using Lemma 1, we have

$\displaystyle\log\det\left(\mathbf{I}_{t}+\frac{1}{\tau}(\mathbf{I}_{t}+\frac{1}{\tau}K_{P,\mathbf{X}_{t},\mathbf{X}_{t}})^{-1}K_{O,\mathbf{X}_{t},\mathbf{X}_{t}}\right)$
$\displaystyle\leq$ $\displaystyle
t\log\left(\frac{t(1+\frac{1}{\tau}\delta_{D})}{t}\right)$ (11)
$\displaystyle=$ $\displaystyle t\log(1+\frac{1}{\tau}\delta_{D})$
$\displaystyle\leq$ $\displaystyle\frac{t\delta_{D}}{\tau},$

where for the last line we used $\log(1+z)\leq z$ which holds for all
$z\in\mathbb{R}$.

Putting (8), (10) and (11) together, we arrive at the following bound on the
information gain.

$\displaystyle I(\mathbf{y}_{t};\hat{f})$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}D\log(1+\frac{\bar{k}t}{\tau
D})+\frac{1}{2}\frac{t\delta_{D}}{\tau},$

which holds for any arbitrary sequence $\mathbf{X}_{t}\subseteq\mathcal{X}$.
Thus

$\displaystyle\gamma_{T}$ $\displaystyle=$
$\displaystyle\sup_{\mathbf{X}_{T}\subseteq\mathcal{X}}I(\mathbf{y}_{T};\hat{f})$
$\displaystyle\leq$ $\displaystyle\frac{1}{2}D\log(1+\frac{\bar{k}T}{\tau
D})+\frac{1}{2}\frac{T\delta_{D}}{\tau}.$

###### Proof of Lemma 1.

Let $\\{\kappa_{m}>0\\}_{m=1}^{n}$ denote the eigenvalues of $P$. Using the
inequality of arithmetic and geometric means

$\displaystyle\prod_{m=1}^{n}\kappa_{m}\leq(\frac{1}{n}\sum_{m=1}^{n}\kappa_{m})^{n}.$

Thus,

$\displaystyle\log\det(P)$ $\displaystyle=$
$\displaystyle\log\left(\prod_{m=1}^{n}\kappa_{m}\right)$ $\displaystyle\leq$
$\displaystyle\log\left((\frac{1}{n}\sum_{m=1}^{n}\kappa_{m})^{n}\right)$
$\displaystyle=$ $\displaystyle\log\left((\frac{\text{tr}(P)}{n})^{n}\right)$
$\displaystyle=$ $\displaystyle n\log\left(\frac{\text{tr}(P)}{n}\right).$

∎

##  Appendix B (Proof of Corollary 1)

Under the $(C_{p},\beta_{p})$ polynomial eigendecay condition, the following
bound on $\delta_{D}$ is straightforwardly derived from the decay rate of
$\lambda_{m}$.

$\displaystyle\delta_{D}$ $\displaystyle=$
$\displaystyle\sum_{m=D+1}^{\infty}\lambda_{m}\psi^{2}$ $\displaystyle\leq$
$\displaystyle\sum_{m=D+1}^{\infty}C_{p}m^{-\beta_{p}}\psi^{2}$
$\displaystyle\leq$
$\displaystyle\int_{z=D}^{\infty}C_{p}z^{-\beta_{p}}\psi^{2}dz$
$\displaystyle=$ $\displaystyle C_{p}D^{1-\beta_{p}}\psi^{2}.$

We select
$D=\lceil(C_{p}\psi^{2}T)^{\frac{1}{\beta_{p}}}\tau^{-\frac{1}{\beta_{p}}}\log^{-\frac{1}{\beta_{p}}}(1+\frac{\bar{k}T}{\tau})\rceil$
which is the smallest $D$ ensuring $\frac{T\delta_{D}}{\tau}\leq
D\log(1+\frac{\bar{k}T}{\tau})$; thus, resulting in the lowest growth rate of
$\gamma_{T}$ based on Theorem 3, which implies $\gamma_{T}\leq
D\log(1+\frac{\bar{k}T}{\tau})$

$\displaystyle\gamma_{T}\leq\left((C_{p}\psi^{2}T)^{\frac{1}{\beta_{p}}}\tau^{-\frac{1}{\beta_{p}}}\log^{-\frac{1}{\beta_{p}}}(1+\frac{\bar{k}T}{\tau})+1\right)\log(1+\frac{\bar{k}T}{\tau}).$

Under the $(C_{e,1},C_{e,2},\beta_{e})$ exponential eigendecay condition,

$\displaystyle\delta_{D}$ $\displaystyle=$
$\displaystyle\sum_{m=D+1}^{\infty}\lambda_{m}\psi^{2}$ $\displaystyle\leq$
$\displaystyle\sum_{m=D+1}^{\infty}C_{e,1}\exp(-C_{e,2}m^{\beta_{e}})\psi^{2}$
$\displaystyle\leq$
$\displaystyle\int_{z=D}^{\infty}C_{e,1}\exp(-C_{e,2}z^{\beta_{e}})\psi^{2}dz.$

Now, consider two different cases of $\beta_{e}=1$ and $\beta_{e}\neq 1$. When
$\beta_{e}=1$,

$\displaystyle\int_{z=D}^{\infty}\exp(-C_{e,2}z^{\beta_{e}})dz$
$\displaystyle=$ $\displaystyle\int_{z=D}^{\infty}\exp(-C_{e,2}z)dz$
$\displaystyle=$ $\displaystyle\frac{1}{C_{e,2}}\exp(-C_{e,2}D).$

When $\beta_{e}\neq 1$, we have

$\displaystyle\int_{z=D}^{\infty}\exp(-C_{e,2}z^{\beta_{e}})dz$
$\displaystyle=$
$\displaystyle\frac{1}{{\beta_{e}}}\int_{z=D^{{\beta_{e}}}}^{\infty}z^{\frac{1}{{\beta_{e}}}-1}\exp(-C_{e,2}z)dz$
$\displaystyle=$
$\displaystyle\frac{1}{{\beta_{e}}}\int_{z=D^{{\beta_{e}}}}^{\infty}z^{\frac{1}{{\beta_{e}}}-1}\exp(-C_{e,2}\frac{z}{2})\exp(-C_{e,2}\frac{z}{2})dz$
$\displaystyle\leq$
$\displaystyle\frac{1}{{\beta_{e}}}\int_{z=D^{{\beta_{e}}}}^{\infty}(\frac{2}{C_{e,2}}(\frac{1}{{\beta_{e}}}-1))^{\frac{1}{{\beta_{e}}}-1}\exp(-(\frac{1}{{\beta_{e}}}-1))\exp(-C_{e,2}\frac{z}{2})dz$
$\displaystyle=$
$\displaystyle\frac{2}{C_{e,2}{\beta_{e}}}(\frac{2}{C_{e,2}}(\frac{1}{{\beta_{e}}}-1))^{\frac{1}{{\beta_{e}}}-1}\exp(-(\frac{1}{{\beta_{e}}}-1))\exp(-C_{e,2}\frac{D^{{\beta_{e}}}}{2}).$

The first equality is obtained by a change of parameter. The inequality holds
since

$\displaystyle\max_{z\in\mathbb{R}}z^{\frac{1}{{\beta_{e}}}-1}\exp(-C_{e,2}\frac{z}{2})=(\frac{2}{C_{e,2}}(\frac{1}{{\beta_{e}}}-1))^{\frac{1}{{\beta_{e}}}-1}\exp(-(\frac{1}{{\beta_{e}}}-1))$
(12)

which can be verified using the standard method of equating the derivative of
the left hand side to zero.

With a similar logic to the polynomial eigendecay case, when $\beta_{e}=1$, we
select

$\displaystyle D=\lceil\frac{1}{C_{e,2}}\log(\frac{C_{e,1}\psi^{2}T}{\tau
C_{e,2}})\rceil.$

When $\beta_{e}\neq 1$, we select

$\displaystyle
D=\left\lceil\left(\frac{2}{C_{e,2}}\left(\log(T)+\log(\frac{2C_{e,1}\psi^{2}}{\tau\beta_{e}C_{e,2}})+(\frac{1}{\beta_{e}}-1)\left(\log(\frac{2}{C_{e,2}}(\frac{1}{\beta_{e}}-1))-1)\right)\right)\right)^{\frac{1}{\beta_{e}}}\right\rceil.$

Theorem 3 implies

$\displaystyle\gamma_{T}\leq\left(\left(\frac{2}{C_{e,2}}(\log(T)+C_{\beta_{e}})\right)^{\frac{1}{\beta_{e}}}+1\right)\log(1+\frac{\bar{k}T}{\tau}),$

$C_{\beta_{e}}=\log(\frac{C_{e,1}\psi^{2}}{\tau C_{e,2}})$ when $\beta_{e}=1$,
and
$C_{\beta_{e}}=\log(\frac{2C_{e,1}\psi^{2}}{\tau\beta_{e}C_{e,2}})+(\frac{1}{\beta_{e}}-1)\left(\log(\frac{2}{C_{e,2}}(\frac{1}{\beta_{e}}-1))-1)\right)$,
otherwise.