# Extrinsic Bayesian Optimization on Manifolds
## 2 Bayesian Optimization (BO) on Manifolds  
Let \(f(x)\) be an objective function defined over some manifold \(M\). We are interested in solving  
\[\mu=\operatorname{argmin}_{x\in M}f(x). \tag{1}\]  
Typically, the function \(f\) lacks a known special structure such as concavity or linearity that would make it easy to optimize using techniques that leverage such structure to improve efficiency. Furthermore, we assume one only needs to be able to evaluate \(f(x)\) without having to know first or second-order information, such as gradient, when evaluating \(f\). We refer to problems having this property as \"derivative-free\". Lastly, we seek to know if the global optimizer exists. The principal ideas behind Bayesian optimization are to build a probabilistic model for the objective function by imposing a _Gaussian process prior_, and this probabilistic model will be used to guide to where in \(M\) the function is next evaluated. The posterior predictive distribution will then be computed. Instead of optimizing the usually expensive objective function, a cheap proxy function is often optimized, which will determine the next point to evaluate. One of the inherent difficulties lies in constructing _valid Gaussian processes on manifolds_ that will be utilized for Bayesian optimization on manifolds. To be more specific, as above, let \(f(x)\) be the objective function on \(M\) for which we omit the potential dependence on some data; for now, the goal is to find the minimum: \(\mu=\operatorname{argmin}_{x\in M}f(x)\). Let \(f(x)\sim GP(\
u(\cdot),R(\cdot,\cdot))\), \(x\in M\), be a Gaussian process (GP) on the manifold \(M\) with mean function \(\
u(x)\) and covariance kernel \(R(\cdot,\cdot)\). Then we evaluate \(f(x)\) at a finite number of points on the manifold following a multivariate Gaussian distribution, that is,  
\[(f(x_{1}),\ldots,f(x_{n}))\ \sim\ N((\
u(x_{1}),\ldots,\
u(x_{n})), \Sigma),\] \[\Sigma_{ij}=cov\big{(}f(x_{i}),f(x_{j})\big{)}=R(x_{i},x_{j}).\]  
Here \(R(\cdot,\cdot):M\times M\to\mathbb{R}\) is a covariance kernel defined on the manifold, which is a _positive semi-definite kernel_ on \(M\). It states that, for any sequence \((a_{1},\ldots,a_{n})\in\mathbb{R}^{n}\), \(\sum_{i=1}^{n}\sum_{i=1}^{n}a_{i}a_{j}R(x_{i},x_{j})\geq 0\). After some evaluations, the GP gives us closed-form marginal means and variances. We denote the predictive means and variance as \(\
u(x,\mathcal{D})\) and \(\sigma^{2}(x,\mathcal{D})\), where \(\mathcal{D}=\{x_{1},\ldots,x_{n}\}\). The acquisition function, which we denote by \(a:M\to\mathbb{R}^{+}\), determines which point in \(M\) should be evaluated next via a proxy optimization  
\[x_{next}=\operatorname{arg\max}_{x\in M}a(x). \tag{2}\]  
There are several popular choices of acquisition functions that are proposed for Bayesian optimization in Euclidean space [49]. The analogous version can be generalized to manifolds. Under the Gaussian process prior, these functions depend on the model solely through its predictive mean function \(\
u(x,\mathcal{D})\) and variance \(\sigma^{2}(x,\mathcal{D})\). In the preceding, we denote the best current value as  
\[x_{best}=\operatorname{argmin}_{x_{n}}f(x_{n}). \tag{3}\]We denote the cumulative distribution function of the standard normal as \(\Phi(\cdot)\). We adopt one of the acquisition functions as  
\[a(x)=\Phi(r(x)),\text{ where }r(x)=\frac{f(x_{best})-\
u(x,\mathcal{D})}{\sigma(x, \mathcal{D})}, \tag{4}\]  
which represents the _probability of improvement_. Other acquisition functions, such as knowledge gradient and entropy search on manifolds, could also be developed, but here we focus on probability improvement. As seen above, a key component of Bayesian optimization methods on manifolds is utilizing Gaussian processes on a manifold \(M\), which are non-trivial to construct. The critical challenge for constructing the Gaussian process is constructing _valid covariance kernel_ on manifolds.