# Extrinsic Bayesian Optimization on Manifolds
## 3 Extrinsic Bayesian Optimization (eBO) on Manifolds  
In this section, we will present the extrinsic Bayesian optimization algorithm on manifolds with the help of the illustrated eGP on manifolds. The key component of the extrinsic framework is the embedding map. Let \(J:M\rightarrow\mathbb{R}^{D}\) be an embedding of \(M\) into some higher dimensional Euclidean space \(\mathbb{R}^{D}\) (\(D\geq d\)) and denote the image of the embedding as \(\tilde{M}=J(M)\). By definition of an embedding, \(J\) is a smooth map such that its differential \(d\)\(:T_{x}M\rightarrow T_{J(x)}\mathbb{R}^{D}\) at each point \(x\in M\) is an injective map from its tangent space \(T_{x}M\) to \(T_{J(x)}\mathbb{R}^{D}\), and \(J\) is a homeomorphism between \(M\) and its image \(\tilde{M}\). Figure 1 provides a visual illustration of equivariant embedding. See Section 4 in [6] for some concrete examples of equivariant embeddings for well-known manifolds, such as the space of the sphere, symmetric positive definite matrices, and planar shapes. As mentioned above, we use eGP as the prior distribution of the objective function, and the main algorithm is described in Algorithm 1. Let \(f(x)\sim eGP(m(\cdot),R(\cdot,\cdot))\) with prior mean \(m(x)\). \(R(\cdot,\cdot)\) is an covariance kernel on \(M\) induced by the embedding \(J\) as:  
\[R(x,z)=\tilde{R}(J(x),J(z)), \tag{5}\]  
where \(\tilde{R}(\cdot,\cdot)\) is a valid covariance kernel on \(\mathbb{R}^{D}\).  
Figure 1: A simple illustration of equivariant embeddings.  
As above, let the predictive means and variance be \(\
u(x,\mathcal{D})\) and \(\sigma^{2}(x,\mathcal{D})\), where \(\mathcal{D}\) denotes the data. The acquisition function defined by Equation (4) represents the probability of improvement. To find out the next point to evaluate, we need to maximize the acquisition question. Since we use the zero mean eGP where \(m(\cdot)\) equals 0, the expression of \(\
u(x,\mathcal{D})\) and \(\sigma(x,\mathcal{D})\) are given as follows:  
\[\
u(x,\mathcal{D}) = K(x_{D},x)^{T}(K(x_{D},x_{D})+\sigma_{n}^{2}I)^{-1}y, \tag{6}\] \[\sigma(x,\mathcal{D}) = K(x,x)-k(x_{D},x)^{T}(K(x_{D},x_{D})+\sigma_{n}^{2}I)^{-1}k(x_{D },x). \tag{7}\]  
Note that \(a(x)\) depends on \(x\) through \(J(x)\), let \(a(x)=\bar{a}(\bar{x})\) where \(\bar{x}=J(x)\in\tilde{M}\). Therefore, the optimization of \(a(x)\) over \(x\) is _equivalent to the optimization of \(\bar{a}(\bar{x})\) over \(\tilde{M}\)_. Let \(\bar{x}^{*}\) be the optimizer of \(\bar{a}(x)\) over \(\tilde{M}\), i.e.,  
\[\bar{x}^{*}=\operatorname{argmin}_{\bar{x}\in\tilde{M}}\bar{a}(\bar{x}). \tag{8}\]  
Then, one has  
\[x^{*}=J^{-1}(\bar{x}^{*}), \tag{9}\]  
where  
\[x^{*}=\operatorname{argmin}_{x\in M}a(x). \tag{10}\]  
The key is to solve (8). We consider the gradient descent or [PERSON]'s method over the submanifolds \(\tilde{M}\) since the gradient is easy to obtain on \(\tilde{M}\). Let \(grad\ \bar{a}(\bar{x})\) be the gradient of \(\bar{a}(\bar{x})\) in the Euclidean space, then the gradient of \(\bar{a}(\bar{x})\) over the submanifold \(\tilde{M}\) is given by  
\[\mathcal{P}grad\ \bar{a}(\bar{x}), \tag{11}\]  
where \(\mathcal{P}\) is the projection map \(P\) from \(T_{\bar{x}}\mathbb{R}^{\mathcal{D}}\) onto the tangent space \(T_{\bar{x}}\tilde{M}\). We propose the following gradient descent Algorithm 2 for finding \(\bar{x}^{*}\) of \(\bar{a}(\bar{x})\) over \(\tilde{M}\).  
```
for\(t=0,1,\ldots,T\)do  Let \(\bar{x}_{0}\in\tilde{M}\) be an initial point. \(\bar{x}_{t+1}=\exp_{\bar{x}_{t}}\lambda\mathcal{P}grad\ \bar{a}(\bar{x})\mid_{\bar{x}_{t}}\),  where \(\exp\) is the exponential map on the submanifold. This exponential map is with respect to the metric by restricting the Euclidean metric onto the image manifold or submanifold.
```  
**Algorithm 2** Gradient algorithms for optimization \(\bar{a}(\bar{x})\) along the submanifold \(\tilde{M}\).