## 3 Preliminaries
### Gaussian Process Regression  
For the learning of an unknown function \(f(\cdot)\), we need an oracle to predict the value of \(f(\mathbf{x})\) for a given input \(\mathbf{x}\in\mathbb{X}\). In this paper, we use gaussian process as oracle which is a nonparametric model. **Definition 1** ([33]). : _A gaussian process is a collection of random variables, any finite number of which have a joint Gaussian distribution._  
Compared with other machine learning methods, GP does not only provide a prediction but also a prediction variance, an effective measure of the uncertainty of the learned model. A GP is used to describe a distribution over functions, which can be written as  
\[f(\mathbf{x})\sim\mathcal{GP}\bigl{(}m(\mathbf{x}),k\bigl{(}\mathbf{x},\mathbf{x}^{\prime} \bigr{)}\bigr{)}, \tag{7}\]  
where \(m(\mathbf{x}):\mathbb{X}\to\mathbb{R}\) is the prior mean function, which allows the inclusion of prior knowledge about the unknown function \(f(\mathbf{x})\) and is often set to zero if there do not have any prior knowledge, and \(k(\mathbf{x},\mathbf{x}^{\prime}):\mathbb{X}\times\mathbb{X}\to\mathbb{R}_{0,+}\) is the covariance function, which is associated with abstract concepts of function \(f(\mathbf{x})\) such as smoothness. Since the choice of kernel function is beyond the research of this paper, we choose squared exponential kernel typically as kernel function  
\[k(\mathbf{x},\mathbf{x}^{\prime})=\sigma_{f}^{\ 2}\exp\biggl{(}-\frac{1}{2}(\mathbf{x}- \mathbf{x}^{\prime})^{\top}\mathbf{\Omega}^{-1}(\mathbf{x}-\mathbf{x}^{\prime})\biggr{)}, \tag{8}\]  
where \(\sigma_{f}\geq 0\), \(\mathbf{\Omega}=diag\{l_{1}^{\ 2},l_{2}^{\ 2},\cdots,l_{n}^{\ 2}\}\), \(l_{i}\geq 0\) are hyperparameters. To explain the process of GP regression, we assume a training data set \(\mathcal{D}=\{\mathbf{X},\mathbf{Y}\}\) consisting of training inputs \(\mathbf{X}=\left\{\mathbf{x}^{(1)},\mathbf{x}^{(2)},\cdots,\mathbf{x}^{(M)}\right\}\) and training outputs \(\mathbf{Y}=\left\{y^{(1)},y^{(2)},\cdots,y^{(M)}\right\}\), which consists of noisy observations \(y^{(i)}=f(\mathbf{x}^{(i)})+\varsigma\), where \(i=1,\cdots,M\), of an unknown function \(f(\cdot)\) perturbed by Measurement noise \(\varsigma\). The unknown function \(f(\cdot)\) is a sample from a Gaussian process \(\mathcal{GP}(0,k(\mathbf{x},\mathbf{x}^{\prime}))\) and observations \(y^{(i)}=f(\mathbf{x}^{(i)})+\varsigma\) are perturbed by zero mean i.i.d. Gaussian noise \(\varsigma\) with variance \(\sigma_{0}^{2}\), i.e., \(\varsigma\sim\mathcal{N}(0,\sigma_{0}^{2})\). Based on Assumption 2, the evaluations of \(y^{*}\) at a given test input \(\mathbf{x}^{*}\) is again a Gaussian distribution with the posterior mean and variance  
\[\mu(y^{*}|\mathbf{x}^{*},\mathcal{D}) =\mathbf{k}(\mathbf{x}^{*})^{\top}\Big{(}\mathbf{K}(\mathbf{X})+\sigma_{0}^{2}\mathbf{ I}_{N}\Big{)}^{-1}\mathbf{Y}, \tag{9}\] \[\sigma^{2}(y^{*}|\mathbf{x}^{*},\mathcal{D}) =k(\mathbf{x}^{*},\mathbf{x}^{*})-\mathbf{k}^{\top}(\mathbf{x}^{*})\Big{(}\mathbf{K}( \mathbf{X})+\sigma_{0}^{2}\mathbf{I}_{N}\Big{)}^{-1}\mathbf{k}(\mathbf{x}^{*}), \tag{10}\]  
where the elements of \(\mathbf{k}(\mathbf{x}^{*})\in\mathbb{R}^{M}\) and \(\mathbf{K}(\mathbf{X})\in\mathbb{R}^{M\times M}\) are defined through \(\mathbf{k}_{i}(\mathbf{x}^{*})=k(\mathbf{x}^{*},\mathbf{X}^{(i)})\) and \(\mathbf{K}_{ii^{\prime}}(\mathbf{X})=k(\mathbf{X}^{(i)},\mathbf{X}^{(i^{\prime})})\), respectively. To capture the uncertainty of prediction, [PERSON] et al. [17] made the following assumption, and put forward Lemma 3. The continuous function \(f(\mathbf{x})\) is Lipschitz in \(\mathbf{x}\) with Lipschitz constant \(L_{f}\) to be a sample obtained from a Gaussian process \(\mathcal{GP}(0,k(\mathbf{x},\mathbf{x}^{\prime}))\) with Lipschitz continuous kernel \(k:\mathbb{X}\times\mathbb{X}\rightarrow\mathbb{R}_{0,+}\).