\pi(x) \propto \exp\left[ -\frac{d^{\hspace{0.03cm}2}(y,x)+d^{\hspace{0.03cm}2}(x,z)}{2\sigma^2}\right]

On the other hand, $\hat{x}_{\scriptscriptstyle MAP} \,=\, z\, \#_{\scriptscriptstyle 1/2}\, y$ is the midpoint of the geodesic segment connecting $z$ to $y$ (note that $\rho = 1/2$). Let $s$ denote the geodesic symmetry at $\hat{x}_{\scriptscriptstyle MAP\,}$. Then, $s$ permutes $z$ and $y$, and therefore leaves invariant $\pi(x)$. Lemma <ref> (applied with $g = s$) implies the Riemannian barycentre $\hat{x}_{\scriptscriptstyle MMS}$ of $\pi$ verifies $s\cdot \hat{x}_{\scriptscriptstyle MMS} = \hat{x}_{\scriptscriptstyle MMS\,}$. However, $\hat{x}_{\scriptscriptstyle MAP}$ is the unique fixed point of $s$. Therefore, $\hat{x}_{\scriptscriptstyle MMS} = \hat{x}_{\scriptscriptstyle MAP\,}$.

Remark : to see that $\hat{x}_{\scriptscriptstyle MMS}$ is well-defined, it is enough to show the posterior density $\pi$ in (<ref>) satisfies (<ref>). Indeed, this implies that $\pi$ has a well-defined Riemannian barycentre.

Consider then the second-order moment in (<ref>), with $y_o = \hat{x}_{\scriptscriptstyle MAP\,}$. Specifically, this is

\begin{equation} \label{eq:mmap}
m_{\scriptscriptstyle 2}(\hat{x}_{\scriptscriptstyle MAP}) = \int_M d^{\hspace{0.03cm}\scriptscriptstyle 2}(\hat{x}_{\scriptscriptstyle MAP}\hspace{0.02cm},x)\hspace{0.03cm}\pi(x)\hspace{0.03cm}\mathrm{vol}(dx)
\end{equation}

Rearrange (<ref>) to obtain

\begin{equation} \label{eq:rearrangepi}
\pi(x) \propto \exp\left[ -h\left(\rho f_y(x)+(1-\rho)f_z(x)\right)\right] \hspace{1cm} \left(h = 1/\sigma^2 + 1/\tau^2\right)
\end{equation}

in the notation of <ref>. Now, let $f(x) = \rho f_y(x)+(1-\rho)f_z(x)$. For $x \in M$, let $x = \mathrm{Exp}_{\hat{x}_{\scriptscriptstyle MAP}}(v)$, and recall the Taylor expansion (<ref>),

\begin{equation} \label{eq:rearrangetaylor}
f\left(x\right) = f(\hat{x}_{\scriptscriptstyle MAP}) + \langle \mathrm{grad}\,f,v\rangle_{\scriptscriptstyle \hat{x}_{\scriptscriptstyle MAP}} + \frac{1}{2}\,\mathrm{Hess}\,f_{\scriptscriptstyle c(t^*)}(\dot{c},\dot{c})
\end{equation}

where $c(t^*)$ is a point along the geodesic $c(t) = \mathrm{Exp}_x(t\,v)$, corresponding to an instant $t^* \in (0,1)$. Note that $\mathrm{grad}\,f(\hat{x}_{\scriptscriptstyle MAP}) = 0$, as can be checked from (<ref>), and that, using (<ref>),

\mathrm{Hess}\,f(x) = \rho\hspace{0.03cm}\mathrm{Hess}\,f_y(x) + (1-\rho)\hspace{0.03cm}\mathrm{Hess}\,f_z(x)\,\geq\,g(y)

Replacing these into (<ref>), it follows that

f(x) \,\geq\, \rho\hspace{0.02cm}(1-\rho)\hspace{0.03cm}d^{\hspace{0.03cm}2}(z,y) + \frac{1}{2}\hspace{0.02cm}d^{\hspace{0.03cm}2}(\hat{x}_{\scriptscriptstyle MAP}\hspace{0.02cm},x)

Then, if $C^{-1}_\pi$ is the missing normalising factor in (<ref>),

\begin{equation} \label{eq:rearrangepi1}
\pi(x) \leq C^{-1}_\pi\hspace{0.03cm}\exp\left[ -\frac{\rho}{\tau^{\scriptscriptstyle 2}}\hspace{0.03cm}d^{\hspace{0.03cm}2}(z,y)-\frac{h}{2}\hspace{0.03cm}d^{\hspace{0.03cm}2}(\hat{x}_{\scriptscriptstyle MAP}\hspace{0.02cm},x)\right]
\end{equation}

From (<ref>) and (<ref>),

\begin{equation} \label{eq:rearrangepi2}
m_{\scriptscriptstyle 2}(\hat{x}_{\scriptscriptstyle MAP}) \,\leq\, C^{-1}_\pi\exp\left[ -\frac{\rho}{\tau^{\scriptscriptstyle 2}}\hspace{0.03cm}d^{\hspace{0.03cm}2}(z,y)\right]\hspace{0.02cm}\int_Md^{\hspace{0.03cm}\scriptscriptstyle 2}(\hat{x}_{\scriptscriptstyle MAP}\hspace{0.02cm},x)\hspace{0.03cm}
\exp\left[-\frac{h}{2}\hspace{0.03cm}d^{\hspace{0.03cm}2}(\hat{x}_{\scriptscriptstyle MAP}\hspace{0.02cm},x)\right]
\hspace{0.03cm}\mathrm{vol}(dx)
\end{equation}

which is finite, as required in (<ref>). In fact, by a direct application of the integral formula (<ref>), it is possible to show that

\int_Md^{\hspace{0.03cm}\scriptscriptstyle 2}(\hat{x}_{\scriptscriptstyle MAP}\hspace{0.02cm},x)\hspace{0.03cm}
\exp\left[-\frac{h}{2}\hspace{0.03cm}d^{\hspace{0.03cm}2}(\hat{x}_{\scriptscriptstyle MAP}\hspace{0.02cm},x)\right]
\hspace{0.03cm}\mathrm{vol}(dx) =
h^{\scriptscriptstyle -3/2}\hspace{0.02cm}Z^\prime(h^{\scriptscriptstyle -1/2})

where $Z(\sigma)$ was given in (<ref>), and the prime denotes the derivative. Finally, replacing this into (<ref>), it follows that

\begin{equation} \label{eq:prewasserstein}
m_{\scriptscriptstyle 2}(\hat{x}_{\scriptscriptstyle MAP}) \,\leq\, C^{-1}_\pi\exp\left[ (-\rho/\tau^{\scriptscriptstyle 2})\hspace{0.03cm}d^{\hspace{0.03cm}2}(z,y)\right]\hspace{0.02cm}h^{\scriptscriptstyle -3/2}\hspace{0.02cm}Z^\prime(h^{\scriptscriptstyle -1/2})
\end{equation}

§ BOUNDING THE DISTANCE

Proposition <ref> states that $\hat{x}_{\scriptscriptstyle MMS} = \hat{x}_{\scriptscriptstyle MAP\,}$, if $\rho = 1/2$. When $M$ is a Euclidean space, it is famously known that $\hat{x}_{\scriptscriptstyle MMS} = \hat{x}_{\scriptscriptstyle MAP}$ for any value of $\rho$. In general, one expects these two estimators to be different from one another, if $\rho \neq 1/2$.

However, when $M$ is a space of constant negative curvature, numerical experiments show that $\hat{x}_{\scriptscriptstyle MMS}$ and $\hat{x}_{\scriptscriptstyle MAP}$ lie surprisingly close to each other, and that they even appear to be equal. I am still unaware of any mathematical explanation of this phenomenon.

It is possible to bound the distance between $\hat{x}_{\scriptscriptstyle MMS}$ and $\hat{x}_{\scriptscriptstyle MAP\,}$, using the so-called fundamental contraction property [29] (this is an immediate application of Jensen's inequality, as explained in the proof of Theorem 6.3 in [29]).

\begin{equation} \label{eq:contraction}
d(\hat{x}_{\scriptscriptstyle MMS}\hspace{0.02cm},\hat{x}_{\scriptscriptstyle MAP}) \leq W(\pi,\delta_{\hat{x}_{\scriptscriptstyle MAP}})
\end{equation}

where $W$ denotes the Kantorovich ($L^{\scriptscriptstyle 1}$-Wasserstein) distance, and $\delta_{\hat{x}_{\scriptscriptstyle MAP}}$ denotes the Dirac probability distribution concentrated at $\hat{x}_{\scriptscriptstyle MAP\,}$. Now, the right-hand side of (<ref>) is equal to the first-order moment

\begin{equation} \label{eq:mmap1}
m_{\scriptscriptstyle 1}(\hat{x}_{\scriptscriptstyle MAP}) = \int_M d(\hat{x}_{\scriptscriptstyle MAP}\hspace{0.02cm},x)\hspace{0.03cm}\pi(x)\hspace{0.03cm}\mathrm{vol}(dx)
\end{equation}

Of course, the upper bound in (<ref>) is not tight, since it is strictly positive, even when $\rho = 1/2$, as one may see from (<ref>).

It will be shown below that a Metropolis-Hastings algorithm, with Gaussian proposals, can be used to generate (geometrically ergodic) samples $(x_n\,;n\geq 1)$ from the posterior density $\pi$.Using these samples, it is possible to approximate (<ref>), by an empirical average,

\begin{equation} \label{eq:mmapbis}
\bar{m}_{\scriptscriptstyle 1}(\hat{x}_{\scriptscriptstyle MAP}) = \frac{1}{N}\hspace{0.03cm}\sum^N_{n=1}d(\hat{x}_{\scriptscriptstyle MAP}\hspace{0.02cm},x_n)
\end{equation}

In addition, the samples $(x_n)$ can be used to compute a convergent approximation of $\hat{x}_{\scriptscriptstyle MMS\,}$. Precisely, the empirical barycentre $\bar{x}_{\scriptscriptstyle MMS}$ of the samples $(x_{\scriptscriptstyle 1},\ldots,x_{\scriptscriptstyle N})$ converges almost-surely to $\hat{x}_{\scriptscriptstyle MMS}$ (this is proved in <ref>).

Numerical experiments were conducted in the case when $M$ is a space of constant curvature, equal to $-1$, and of dimension $n$.  The following table was obtained for the values $\sigma^2 = \tau^2 = 0.1$, using samples $(x_{\scriptscriptstyle 1},\ldots,x_{\scriptscriptstyle N})$ where $N = 2\times10^5$.

\begin{array}{rlllllllll}
\text{dimension }n & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\[0.2cm]
\bar{m}_{\scriptscriptstyle 1}(\hat{x}_{\scriptscriptstyle MAP})     &         0.28    &  0.35  &  0.41   &  0.47       &   0.50       & 0.57          &  0.60        &        0.66& 0.70 \\[0.2cm]
d(\bar{x}_{\scriptscriptstyle MMS}\hspace{0.02cm},\hat{x}_{\scriptscriptstyle MAP})     & 0.00  & 0.00   & 0.00   & 0.01  &  0.01  & 0.02  & 0.02   & 0.02 & 0.03
\end{array}

and the following table for $\sigma^2 = 1$ and $\tau^2 = 0.5$, again using $N = 2\times10^5$.

\begin{array}{rlllllllll}
\text{dimension }n & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\[0.2cm]
\bar{m}_{\scriptscriptstyle 1}(\hat{x}_{\scriptscriptstyle MAP})    &         0.75    &  1.00  &  1.12   &  1.44       &   1.73       &  1.97         & 2.15     &   2.54     &2.91 \\[0.2cm]
d(\bar{x}_{\scriptscriptstyle MMS}\hspace{0.02cm},\hat{x}_{\scriptscriptstyle MAP})      & 0.00   &  0.00  & 0.03   & 0.02  & 0.02  &  0.03  &  0.04  &  0.03 &  0.12
\end{array}

The first table, as expected, confirms Proposition <ref>. The second table, more surprisingly, shows that $\hat{x}_{\scriptscriptstyle MMS}$ and $\hat{x}_{\scriptscriptstyle MAP}$ can be quite close to each other, even when $\rho \neq 1/2$.

Other values of $\sigma^2$ and $\tau^2$ lead to similar orders of magnitude for $\bar{m}_{\scriptscriptstyle 1}(\hat{x}_{\scriptscriptstyle MAP})$ and $  d(\bar{x}_{\scriptscriptstyle MMS}\hspace{0.02cm},\hat{x}_{\scriptscriptstyle MAP})$. While $\bar{m}_{\scriptscriptstyle 1}(\hat{x}_{\scriptscriptstyle MAP})$  increases with the dimension $n$, $d(\bar{x}_{\scriptscriptstyle MMS}\hspace{0.02cm},\hat{x}_{\scriptscriptstyle MAP})$ does not appear sensitive to increasing dimension.

Based on these experimental results, one may be tempted to conjecture that $\hat{x}_{\scriptscriptstyle MMS} = \hat{x}_{\scriptscriptstyle MAP\,}$, even when $\rho \neq 1/2$. Naturally, numerical experiments do not equate to a mathematical proof.

§ COMPUTING THE MMS

§.§ Metropolis-Hastings algorithm

A crucial step, in Bayesian inference, is sampling from the posterior density. Here, this is $\pi(x)$, given by (<ref>).
Since $\pi(x)$ is known only up to normalisation, a suitable sampling method is afforded by the Metropolis-Hastings algorithm. This algorithm generates a Markov chain $(x_n\,;n\geq 1)$, with transition kernel [50]

\begin{equation} \label{eq:hmP}
Pf(x) \,=\, \int_M\,\alpha(x\hspace{0.02cm},y)\hspace{0.02cm}q(x\hspace{0.02cm},y)f(y)\hspace{0.02cm}\mathrm{vol}(dy) + \rho(x)\hspace{0.02cm}f(x)
\end{equation}

for any bounded measurable function $f:M\rightarrow \mathbb{R}$, where $\alpha(x\hspace{0.02cm},y)$ is the probability of accepting a transition from $x$ to $dy$, and $\rho(x)$ is the probability of staying at $x$, and where $q(x,y)$ is the proposed transition density

\begin{equation} \label{eq:hmTr}
q(x\hspace{0.02cm},y) \geq 0 \hspace{0.2cm}\text{and}\hspace{0.2cm} \int_M\,q(x\hspace{0.02cm},y)\hspace{0.02cm}\mathrm{vol}(dy) = 1 \hspace{0.5cm} \text{for } x\in M
\end{equation}

In the following, $(x_n)$ will always be an isotropic Metropolis-Hastings chain, in the sense that $q(x\hspace{0.02cm},y) = q(d(x\hspace{0.02cm},y))$, so $q(x\hspace{0.02cm},y)$ only depends on the distance $d(x\hspace{0.02cm},y)$. In this case, the acceptance probability $\alpha(x\hspace{0.02cm},y)$ is given by $\alpha(x\hspace{0.02cm},y) = \mathrm{min}\left\lbrace1\hspace{0.02cm},\pi(y)/\pi(x) \right\rbrace$.

The aim of the Metropolis-Hastings algorithm is to produce a Markov chain $(x_n)$ which is geometrically ergodic. Geometric ergodicity means the distribution $\pi_n$ of $x_n$ converges to $\pi$, with a geometric rate, in the sense that there exist $\beta \in (0,1)$ and $R(x_{\scriptscriptstyle 1}) \in (0,\infty)$, as well as a function $V:M\rightarrow \mathbb{R}$, such that (in the following, $\pi(dx) = \pi(x)\hspace{0.02cm}\mathrm{vol}(dx)$)

\begin{equation} \label{eq:VV}
V(x) \geq \max\left\lbrace 1\hspace{0.02cm},d^{\hspace{0.03cm} 2}(x,x^*)\right\rbrace \text{ for some } x^* \in M
\end{equation}

\begin{equation} \label{eq:gergodic}
\left| \int_M\, f(x)\hspace{0.02cm}(\pi_n(dx) - \pi(dx)) \right| \,\leq\,R(x_{\scriptscriptstyle 1})\hspace{0.02cm}\beta^n \hspace{0.9cm}
\end{equation}

for any function $f:M\rightarrow \mathbb{R}$ with $|f|\leq V$. If the chain $(x_n)$ is geometrically ergodic, then it satisfies the strong law of large numbers [51]

\begin{equation} \label{eq:mcmclln}
\frac{1}{N}\hspace{0.03cm}\sum^N_{n=1}f(x_n) \longrightarrow \int_M\,f(x)\hspace{0.02cm}\pi(dx) \text{ \;\;(almost-surely)}
\end{equation}

as well as a corresponding central limit theorem (see Theorem 17.0.1, in [51]). Then, in practice, the Metropolis-Hastings algorithm generates samples $(x_n)$ from the posterior density $\pi(x)$.

In <ref>, the following general statement will be proved, concerning the geometric ergodicity of isotropic Metropolis-Hastings chains.

Let $M$ be a Riemannian symmetric space, which belongs to the non-compact case. Assume $(x_n\,;n\geq 1)$ is a Markov chain in $M$, with transition kernel given by (<ref>), with proposed transition density $q(x\hspace{0.02cm},y) = q(d(x\hspace{0.02cm},y))$, and with strictly positive invariant density $\pi$.

The chain $(x_n)$ satisfies (<ref>) and (<ref>), if the following assumptions hold,

(a1) there exists $x^* \in M$, such that $r(x) = d(x^*,x)$ and $\ell(x) = \log\hspace{0.02cm}\pi(x)$ satisfy

\limsup_{r(x)\rightarrow \infty}\hspace{0.02cm}\frac{\langle\mathrm{grad}\,r,\mathrm{grad}\,\ell\rangle_{\scriptscriptstyle x}}{r(x)}\,<\,0

(a2) if $n(x) = \left.\mathrm{grad}\,\ell(x)\middle/\Vert \mathrm{grad}\,\ell(x)\Vert\right.$, then $n(x)$ satisfies

\limsup_{r(x)\rightarrow \infty}\hspace{0.02cm}\langle\mathrm{grad}\,r,n\rangle_{\scriptscriptstyle x}\,<\,0

(a3) there exist $\delta_{\scriptscriptstyle q} > 0$ and $\varepsilon_{\scriptscriptstyle q} > 0$ such that $d(x\hspace{0.02cm},y) <\delta_{\scriptscriptstyle q}$ implies $q(x\hspace{0.02cm},y) > \varepsilon_{\scriptscriptstyle q\,}$

Remark : the posterior density $\pi$ in (<ref>) verifies Assumptions (a1) and (a2). To see this, let $x^* = z$, and note from (<ref>) and (<ref>) that

\mathrm{grad}\,\ell(x) \,=\, -\frac{1}{\tau^2}\hspace{0.02cm}r(x)\hspace{0.02cm}\mathrm{grad}\,r(x) - \frac{1}{\sigma^2}\hspace{0.02cm}\mathrm{grad}\,f_y(x)

Then, taking the scalar product with $\mathrm{grad}\,r$,

\begin{equation} \label{eq:proofconditiona1}
\langle\mathrm{grad}\,r,\mathrm{grad}\,\ell\rangle_{x} = -\frac{1}{\tau^2}\hspace{0.02cm}r(x) -
\frac{1}{\sigma^2}\hspace{0.02cm}\langle\mathrm{grad}\,r,\mathrm{grad}\,f_y\rangle_{x}
\end{equation}

since $\mathrm{grad}\,r(x)$ is a unit vector, for all $x \in M$. Now, $\mathrm{grad}\,f_y(x) = -\mathrm{Exp}^{-1}_x(y)$, by (<ref>). But,
since $r(x)$ is a convex function of $x$,

\langle \mathrm{grad}\,r,\mathrm{Exp}^{-1}_x(y)\rangle \,\leq\, r(y) - r(x)

for any $y \in M$. Thus, the right-hand side of (<ref>) is strictly negative, as soon as $r(x) > r(y)$, and Assumption (a1) is indeed verified. That Assumption (a2) is also verified can be proved by a similar reasoning.

Remark : on the other hand, Assumption (a3) holds, if the proposed transition density $q(x\hspace{0.02cm},y)$ is a Gaussian density, $q(x\hspace{0.02cm},y) = p(y|x,\tau^{\scriptscriptstyle 2}_{\scriptscriptstyle q})$.

With this choice of $q(x\hspace{0.02cm},y)$, all the assumptions of Proposition <ref> are verified, for the posterior density $\pi$ in (<ref>).  Proposition <ref> therefore implies that the Metropolis-Hastings algorithm generates geometrically ergodic samples $(x_n\,;n\geq 1)$, from this posterior density.

§.§ The empirical barycentre

Let $(x_n\,;n\geq 1)$ be a Metropolis-Hastings Markov chain in $M$, with its transition kernel (<ref>), and invariant density $\pi$. Assume the chain $(x_n)$ is geometrically ergodic, so it satisfies the strong law of large numbers (<ref>).

Then, let $\bar{x}_{\scriptscriptstyle N}$ denote the empirical barycentre of the first $N$ samples $(x_{\scriptscriptstyle 1},\ldots,x_{\scriptscriptstyle N})$. This is the unique global minimum of the variance function

\begin{equation} \label{eq:emprecursive}
\mathcal{E}_{\scriptscriptstyle N}(y) \,=\,\frac{1}{2N}\sum^N_{n=1}d^{\hspace{0.03cm}2}(y\hspace{0.02cm},x_n)
\end{equation}

Assuming it is well-defined, let $\hat{x}$ denote the Riemannian barycentre of the invariant density $\pi$. It turns out that $\bar{x}_{\scriptscriptstyle N}$ converges almost-surely to $\hat{x}$.

Let $(x_n)$ be any Markov chain in a Hadamard manifold $M$, with invariant distribution $\pi$. Denote
$\bar{x}_{\scriptscriptstyle N}$ the empirical barycentre of $(x_{\scriptscriptstyle 1},\ldots,x_{\scriptscriptstyle N})$, and $\hat{x}$ the Riemannian barycentre of $\pi$ (assuming it is well-defined). If $(x_n)$ satisfies the strong law of large numbers (<ref>), then $\bar{x}_{\scriptscriptstyle N}$ converges to $\hat{x}$, almost-surely.

According to the remarks after Proposition <ref>, the Metropolis-Hastings Markov chain $(x_n)$, whose invariant density is the posterior density $\pi(x)$, given by (<ref>), is geometrically ergodic. Therefore, by Proposition <ref>, the empirical barycentre $\bar{x}_{\scriptscriptstyle MMS\,}$, of the samples $(x_{\scriptscriptstyle 1},\ldots,x_{\scriptscriptstyle N})$, converges almost-surely to the minimum mean square error estimator $\hat{x}_{\scriptscriptstyle MMS}$ (since this is just the barycentre of the posterior density $\pi$). This provides a practical means of approximating $\hat{x}_{\scriptscriptstyle MMS\,}$. Indeed, $\bar{x}_{\scriptscriptstyle MMS}$ can be computed using the Riemannian gradient descent method (this method is discussed in <ref>, below).

The proof of Proposition <ref> is nearly a word-for-word repetition of the proof in [24] (that of Theorem 2.3).

Proof of Proposition <ref> : denote $\mathcal{E}_{\pi}$ the variance function of the invariant distribution $\pi$,

\mathcal{E}_{\pi}(y) = \frac{1}{2}\hspace{0.03cm}
\int_M\,d^{\hspace{0.03cm}\scriptscriptstyle 2}(y\hspace{0.02cm},x)\hspace{0.03cm}\pi(dx)

First, for any compact $K \subset M$, it will be proved that

\begin{equation} \label{eq:proofbhatta1}
\sup_{y\in K}\hspace{0.03cm}\left| \mathcal{E}_{\scriptscriptstyle N}(y) - \mathcal{E}_{\pi}(y)\right| \longrightarrow 0\text{ \;\;(almost-surely)}
\end{equation}

To do so, let $\delta > 0$ and let $\lbrace w_j\,;j=1,\ldots,J\rbrace$ be a $\delta$-net in $K$ (for any $y \in  K$, there exists $w_j$ such that $d(w_j\hspace{0.02cm},y) < \delta$). By the strong law of large numbers (<ref>),

\begin{equation} \label{eq:proofbhatta11}
\max_{j=1,\ldots, J}\hspace{0.03cm}\left| \mathcal{E}_{\scriptscriptstyle N}(w_j) - \mathcal{E}_{\pi}(w_j)\right| \longrightarrow 0\text{ \;\;(almost-surely)}
\end{equation}

Using the elementary identity

\left| d^{\hspace{0.03cm}\scriptscriptstyle 2}(y\hspace{0.02cm},x_n) - d^{\hspace{0.03cm}\scriptscriptstyle 2}(w\hspace{0.02cm},x_n)\right| \leq \left(d(y\hspace{0.02cm},x_n) + d(w\hspace{0.02cm},x_n)\right)\left|d(y\hspace{0.02cm},x_n) - d(w\hspace{0.02cm},x_n)\right|

it follows by the triangle inequality that

\begin{equation} \label{eq:squarelipschitz}
\left| d^{\hspace{0.03cm}\scriptscriptstyle 2}(y\hspace{0.02cm},x_n) - d^{\hspace{0.03cm}\scriptscriptstyle 2}(w\hspace{0.02cm},x_n)\right| \leq \left(d(y\hspace{0.02cm},x_n) + d(w\hspace{0.02cm},x_n)\right)d(w\hspace{0.02cm},y)
\end{equation}

From (<ref>), it is possible to show that, for $y$ and $w$ in $K$,

\begin{equation} \label{eq:proofbhatta12}
\left| \mathcal{E}_{\scriptscriptstyle N}(y) - \mathcal{E}_{\scriptscriptstyle N}(w)\right| \leq \sup_{z\in K}\left( \frac{1}{N}\sum^N_{n=1}d(z\hspace{0.02cm},x_n)\right)d(w\hspace{0.02cm},y)
\end{equation}

However, by the strong law of large numbers (<ref>), if $y_o \in K$ and $N$ is sufficiently large,

\frac{1}{N}\sum^N_{n=1}d(z\hspace{0.02cm},x_n) \leq 1 +
\int_M\,d(y_o\hspace{0.02cm},x)\hspace{0.03cm}\pi(dx) + \mathrm{diam}\,K\text{ \;\;(almost-surely)}

Calling this quantity $A$, it follows that for $N$ sufficiently large  (note that this is the same $N$, for all $y$ and $w$ in $K$),

\begin{equation} \label{eq:proofbhatta13}
\left| \mathcal{E}_{\scriptscriptstyle N}(y) - \mathcal{E}_{\scriptscriptstyle N}(w)\right| \leq A\hspace{0.03cm}d(w\hspace{0.02cm},y)\text{ \;\;(almost-surely)}
\end{equation}

From (<ref>), it is also possible to show that, for $y$ and $w$ in $K$,

\begin{equation} \label{eq:proofbhatta14}
\left| \mathcal{E}_{\pi}(y) - \mathcal{E}_{\pi}(w)\right| \leq A\hspace{0.03cm}d(w\hspace{0.02cm},y)
\end{equation}

Now, if $y \in K$, let $w(y) \in \lbrace  w_j\rbrace$ be such that $d(w(y),y) < \delta$. Then, for $y$ in $K$,

\left| \mathcal{E}_{\scriptscriptstyle N}(y) - \mathcal{E}_{\pi}(y)\right| \leq
\left| \mathcal{E}_{\scriptscriptstyle N}(y) - \mathcal{E}_{\scriptscriptstyle N}(w(y))\right|+
\left| \mathcal{E}_{\scriptscriptstyle N}(w(y)) - \mathcal{E}_{\pi}(w(y))\right|+
\left| \mathcal{E}_{\pi}(w(y)) - \mathcal{E}_{\pi}(y)\right|

By (<ref>) and (<ref>), if $N$ is sufficiently large, it follows that

\left| \mathcal{E}_{\scriptscriptstyle N}(y) - \mathcal{E}_{\pi}(y)\right| \leq 2A\delta + \max_{j=1,\ldots, J}\hspace{0.03cm}\left| \mathcal{E}_{\scriptscriptstyle N}(w_j) - \mathcal{E}_{\pi}(w_j)\right|

and (<ref>) follows from (<ref>), since $\delta > 0$ is arbitrary.

Second, for $N$ sufficiently large, and for any $C > 0$, it will be proved that there exists a compact $K \subset M$, such that

\begin{equation} \label{eq:proofbhatta2}
y\notin K \;\;\Longrightarrow\;\; \mathcal{E}_{\scriptscriptstyle N}(y) > C \text{ \;\;(almost-surely)}
\end{equation}

To do so, note from (<ref>), by the triangle inequality

\mathcal{E}_{\scriptscriptstyle N}(y) \geq \frac{1}{2N}\sum^N_{n=1}(d(y\hspace{0.02cm},\hat{x})-d(\hat{x}\hspace{0.02cm},x_n))^2
\, \geq \,\frac{1}{2}d^{\hspace{0.03cm}2}(y\hspace{0.02cm},\hat{x}) - \left(\frac{1}{N}\sum^N_{n=1}d(\hat{x}\hspace{0.02cm},x_n) \right)d(y\hspace{0.02cm},\hat{x})

However, by the strong law of large numbers (<ref>), if $N$ is sufficiently large

\frac{1}{N}\sum^N_{n=1}d(\hat{x}\hspace{0.02cm},x_n) \leq 1 + \int_M\,d(\hat{x}\hspace{0.02cm},x)\hspace{0.03cm}\pi(dx)

Calling this quantity $B$, it follows that for $N$ sufficiently large,

\begin{equation} \label{eq:proofbhatta21}
\mathcal{E}_{\scriptscriptstyle N}(y) \geq
\frac{1}{2}d^{\hspace{0.03cm}2}(y\hspace{0.02cm},\hat{x}) - B\hspace{0.02cm}d(y\hspace{0.02cm},\hat{x})
\end{equation}

and this directly yields (<ref>), since closed and bounded sets are compact (as a consequence of the Hopf-Rinow theorem [11]).

Now, to complete the proof, note the following. By (<ref>), for $N$ sufficiently large, there exists a compact $K \subset M$, such that
$\mathcal{E}_{\scriptscriptstyle N}(y) > \mathcal{E}_{\pi}(\hat{x})+1$ almost-surely, whenever $y \notin K$. That is,

\begin{equation} \label{eq:proofbhatta3}
\inf_{y\notin K}\hspace{0.02cm}\mathcal{E}_{\scriptscriptstyle N}(y) > \mathcal{E}_{\pi}(\hat{x})+1\text{ \;\;(almost-surely)}
\end{equation}

Moreover, one may always assume that $K$ is a neighborhood of $\hat{x}$. Then, if $B(\hat{x},\epsilon) \subset K$, it follows from (<ref>) that, for $N$ sufficiently large,

\inf_{y \in B(\hat{x},\epsilon)}\hspace{0.02cm}\mathcal{E}_{\scriptscriptstyle N}(y) <
\inf_{y \in B(\hat{x},\epsilon)}\hspace{0.02cm}\mathcal{E}_{\pi}(y) + \frac{\epsilon^2}{4}\text{ \;\;(almost-surely)}

or, since $\hat{x}$ is the unique global minimum of $\mathcal{E}_{\pi}(y)$,

\begin{equation} \label{eq:proofbhatta4}
\inf_{y \in B(\hat{x},\epsilon)}\hspace{0.02cm}\mathcal{E}_{\scriptscriptstyle N}(y) <
\mathcal{E}_{\pi}(\hat{x}) + \frac{\epsilon^2}{4}\text{ \;\;(almost-surely)}
\end{equation}

But, also by (<ref>), for $N$ sufficiently large,

\inf_{y \in K- B(\hat{x},\epsilon)}\hspace{0.02cm}\mathcal{E}_{\scriptscriptstyle N}(y) >
\inf_{y \in K- B(\hat{x},\epsilon)}\hspace{0.02cm}\mathcal{E}_{\pi}(y) - \frac{\epsilon^2}{4}\text{ \;\;(almost-surely)}

However, since the variance function $\mathcal{E}_{\pi}$ is $1/2$-strongly convex, with its global minimum at $\hat{x}$,

\mathcal{E}_{\pi}(y) \geq \mathcal{E}_{\pi}(\hat{x}) + \frac{1}{2}d^{\hspace{0.03cm}2}(y\hspace{0.02cm},\hat{x})

and this implies

\begin{equation} \label{eq:proofbhatta5}
\inf_{y \in K- B(\hat{x},\epsilon)}\hspace{0.02cm}\mathcal{E}_{\scriptscriptstyle N}(y) >
\mathcal{E}_{\pi}(\hat{x}) + \frac{\epsilon^2}{4}\text{ \;\;(almost-surely)}
\end{equation}

Finally, (<ref>), (<ref>) and (<ref>) show that, for $N$ sufficiently large

\inf_{y\in M}\hspace{0.02cm}\mathcal{E}_{\scriptscriptstyle N}(y) =
\inf_{y\in B(\hat{x},\epsilon)}\hspace{0.02cm}\mathcal{E}_{\scriptscriptstyle N}(y)\text{ \;\;(almost-surely)}

Since $\mathcal{E}_{\scriptscriptstyle N}$ has a unique global minimum $\bar{x}_{\scriptscriptstyle N\,}$, it follows  that $\bar{x}_{\scriptscriptstyle N}$ belongs to the closure of $B(\hat{x},\epsilon)$, almost-surely, when $N$ is sufficiently large. The proof is now complete, since $\epsilon$ is arbitrary.

§ RIEMANNIAN GRADIENT DESCENT

Since the minimum mean square error estimator $\hat{x}_{\scriptscriptstyle MMS}$ could not be computed directly, it was approximated by $\bar{x}_{\scriptscriptstyle MMS\hspace{0.03cm}}$, the global minimum of the variance function $\mathcal{E}_{\scriptscriptstyle N\hspace{0.03cm}}$, defined as in (<ref>). This function $\mathcal{E}_{\scriptscriptstyle N}$ being $1/2$-strongly convex, its global minimum can be computed using the Riemannian gradient descent method, which even guarantees an exponential rate of convergence.

This method is here studied from a general point of view. The aim is to minimise a function $f:M\rightarrow \mathbb{R}$, where $M$ is a Hadamard manifold, with sectional curvatures in the interval $[-c^{\hspace{0.02cm}\scriptscriptstyle 2},0]$, and $f$ is an $(\alpha/2)$-strongly convex function.

Recall from (<ref>) in <ref>, this means $f$ is $(\alpha/2)$-strongly convex along any geodesic in $M$. In particular, for $x\hspace{0.02cm}, y \in M$,

\begin{equation} \label{eq:strongconvtan}
f(y) - f(x) \geq \langle\mathrm{Exp}^{-1}_x(y),\mathrm{grad}\,f(x)\rangle_x\,+\,(\alpha/2)\hspace{0.02cm}d^{\hspace{0.03cm}2}(x,y)
\end{equation}

This implies that $f$ has compact sublevel sets. Indeed, let $x^*$ be the global minimum of $f$, so $\mathrm{grad}\,f(x^*) = 0$. Putting $x = x^*$ and $y = x$ in (<ref>), it follows that

\begin{equation} \label{eq:properconv}
f(x) - f(x^*) \geq (\alpha/2)\hspace{0.02cm}d^{\hspace{0.03cm}2}(x^*\!,x)
\end{equation}

Accordingly, if $S(y)$ is the sublevel set of $y$, then $S(y)$ is contained in the closed ball $\bar{B}(x^*\!,R_y)$, where $R_y = (2/\alpha)(f(y) - f(x^*))$. Therefore, $S(y)$ is compact, since it is closed and bounded [11].

The Riemannian gradient descent method is based on the iterative scheme

\begin{equation} \label{eq:pgd}
x^{t+1} = \mathrm{Exp}_{x^t}(-\mu\hspace{0.02cm}\mathrm{grad}\,f(x^t))
\end{equation}

where $\mu$ is a positive step-size, $\mu \leq 1$. If this is chosen sufficiently small, then the iterates $x^t$ remain within the sublevel set $S(x^{\scriptscriptstyle 0})$.
In fact, let $\bar{B}_{\scriptscriptstyle 0} = \bar{B}(x^*\!,R_{x^{\scriptscriptstyle 0}})$ and
$\bar{B}^\prime_{\scriptscriptstyle 0} = \bar{B}(x^*\!,R_{x^{\scriptscriptstyle 0}} + G)$, where $G$ denotes the supremum of the norm of $\mathrm{grad}\,f(x)$, taken over $x \in \bar{B}_{\scriptscriptstyle 0}$.  Then, let $H^\prime_{\scriptscriptstyle 0}$ denote the supremum of the operator norm of
$\mathrm{Hess}\,f(x)$, taken over $x \in \bar{B}^\prime_{\scriptscriptstyle 0}$.

For the Riemannian gradient descent method (<ref>), if $\mu \leq 2/\!H^\prime_{\scriptscriptstyle 0\hspace{0.02cm}}$, then the iterates $x^t$ remain within the sublevel set $S(x^{\scriptscriptstyle 0})$.

Once it has been ensured that the iterates $x^t$ remain within $S(x^{\scriptscriptstyle 0})$, it is even possible to choose $\mu$ in such a way that these iterates achieve an exponential rate of convergence towards $x^*$. This relies on the fact that $x^*$ is a “strongly attractive" critical point of the vector field $\mathrm{grad}\,f$. Precisely, putting $y = x^*$ in (<ref>), it follows that

\begin{equation}\label{eq:strongtangattract}
\langle\mathrm{Exp}^{-1}_x(x^*),\mathrm{grad}\,f(x)\rangle_x \leq -\,(\alpha/2)\hspace{0.02cm}d^{\hspace{0.03cm}2}(x,x^*)+ (f(x^*) - f(x))
\end{equation}

Now, let $C_{\scriptscriptstyle 0} = c\hspace{0.02cm}R_{x^{\scriptscriptstyle 0}}\coth(c\hspace{0.02cm}R_{x^{\scriptscriptstyle 0}})$.

Let $\bar{H}^\prime_{\scriptscriptstyle 0}  =\max\lbrace H^\prime_{\scriptscriptstyle 0\hspace{0.02cm}},1\rbrace$. If $\mu \leq 1/\!(\bar{H}^\prime_{\scriptscriptstyle 0}C^{\phantom{\prime}}_{\scriptscriptstyle 0})$ (this implies $\mu \leq 2/\!H^\prime_{\scriptscriptstyle 0}$) and $\mu \leq 1/\alpha$,

\begin{equation} \label{eq:proppgd}
d^{\hspace{0.03cm} 2}(x^t,x^*) \leq (1- \mu\alpha)^t\hspace{0.02cm}d^{\hspace{0.03cm} 2}(x^{\scriptscriptstyle 0},x^*)
\end{equation}

The proof of Proposition <ref> will employ the following lemma.

Let $\bar{H}^\prime_{\scriptscriptstyle 0}  =\max\lbrace H^\prime_{\scriptscriptstyle 0\hspace{0.02cm}},1\rbrace$.  For any $x \in \bar{B}_{\scriptscriptstyle 0\hspace{0.02cm}}$,

\begin{equation} \label{eq:lempgd}
\Vert\mathrm{grad}\,f\Vert^2_x \leq 2\bar{H}^\prime_{\scriptscriptstyle 0}(f(x) - f(x^*))
\end{equation}

Remark : the rate of convergence predicted by (<ref>) is exponential, but depends on the initial guess $x^{\scriptscriptstyle 0}$, through the constants $\bar{H}^\prime_{\scriptscriptstyle 0}$ and $C^{\phantom{\prime}}_{\scriptscriptstyle 0\hspace{0.02cm}}$. This rate can become arbitrarily bad, if $x^{\scriptscriptstyle 0}$ is chosen sufficiently far from $x^*$, since both $\bar{H}^\prime_{\scriptscriptstyle 0}$ and $C^{\phantom{\prime}}_{\scriptscriptstyle 0\hspace{0.02cm}}$ may then become arbitrarily large. By contrast, if $M$ is a Euclidean space (that is, in the limit $c = 0$), $C_{\scriptscriptstyle 0} = 1$, is a constant.

Remark : I have never met with a function $f:M \rightarrow \mathbb{R}$ ($M$ a non-Euclidean Hadamard manifold), which is strongly convex, and also has a bounded Hessian. I do not even know whether it is possible or not to construct such a function. Proof of Lemma <ref> : let $c:[0,1]\rightarrow M$ be the geodesic curve with $c(0) = x^t$ and $c(1) = x^{t+1}$. From (<ref>), $\dot{c}(0) = -\mu\hspace{0.02cm}\mathrm{grad}\,f(x^t)$. Then, by the Taylor expansion (<ref>),

\begin{equation} \label{eq:proofsublevel1}
f(x^{t+1}) = f(x^t) - \mu\hspace{0.02cm}\Vert \mathrm{grad}\,f\Vert^2_{x^t}
+ \frac{1}{2}\,\mathrm{Hess}\,f_{\scriptscriptstyle c(u)}(\dot{c},\dot{c})
\end{equation}

for some $u \in (0,1)$. Assume that $x^t$ belongs to $S(x^{\scriptscriptstyle 0}) \subset \bar{B}_{\scriptscriptstyle 0\hspace{0.02cm}}$. Then, by the triangle inequality,

d(x^*,c(u)) \leq d(x^*,x^t) + d(x^t,c(u)) \leq R_{x^{\scriptscriptstyle 0}} + \mu\hspace{0.02cm}G

where the second inequality follows from the definition of $G$, because $d(x^t,c(u)) = u\Vert \dot{c}(0)\Vert$. Since $\mu \leq 1$, it follows that $d(x^*,c(u))  \leq R_{x^{\scriptscriptstyle 0}} + G$. Therefore, $c(u) \in \bar{B}^\prime_{\scriptscriptstyle 0\hspace{0.02cm}}$. Then, from the definition of $H^\prime_{\scriptscriptstyle 0}$,

\mathrm{Hess}\,f_{\scriptscriptstyle c(u)}(\dot{c},\dot{c}) \leq H^\prime_{\scriptscriptstyle 0}\hspace{0.02cm}\Vert \dot{c}\Vert^2_{\scriptscriptstyle c(u)}
= H^\prime_{\scriptscriptstyle 0}\hspace{0.02cm}\mu^2\Vert \mathrm{grad}\,f\Vert^2_{x^t}

Replacing this into (<ref>),

\begin{equation} \label{eq:proofsublevel2}
f(x^{t+1}) \leq f(x^t) - \mu(1-\mu\hspace{0.02cm}(H^\prime_{\scriptscriptstyle 0}/2))\hspace{0.02cm}\Vert \mathrm{grad}\,f\Vert^2_{x^t}
\end{equation}

Clearly, then, taking $\mu \leq 2/\!H^\prime_{\scriptscriptstyle 0\hspace{0.03cm}}$, it follows that $f(x^{t+1}) \leq f(x^t)$ so that $x^{t+1}$ belongs to $S(x^{\scriptscriptstyle 0})$. The lemma is proved by induction.

Proof of Proposition <ref> : let $c:[0,1]\rightarrow M$ be the geodesic with $c(0) = x^t$ and $c(1) = x^{t+1}$.Note from (<ref>) that $\dot{c}(0) = -\mu\hspace{0.02cm}\mathrm{grad}\,f(x^t)$. Let $W(x) = d^{\hspace{0.03cm} 2}(x,x^*)/2$, and write down its Taylor expansion (<ref>),

\begin{equation} \label{eq:proofpgd1}
W(x^{t+1}) = W(x^t) - \mu\hspace{0.02cm}\langle\mathrm{grad}W,\mathrm{grad}\,f\rangle_{x^t} +
\frac{1}{2}\,\mathrm{Hess}\,W_{\scriptscriptstyle c(u)}(\dot{c},\dot{c})
\end{equation}

for some $u \in (0,1)$. Note that $\mathrm{grad}\,W$ and $\mathrm{Hess}\,W$ are given by (<ref>) and (<ref>), and also that $x^t$ and $x^{t+1}$ belong to $S(x^{\scriptscriptstyle 0}) \subset \bar{B}_{\scriptscriptstyle 0}\hspace{0.02cm}$, by Lemma <ref>, since $\mu \leq 2/\!H^\prime_{\scriptscriptstyle 0}$. Since $S(x^{\scriptscriptstyle 0})$ is a convex set (recall the definition from <ref>), $c(u)$ also belongs to $S(x^{\scriptscriptstyle 0}) \subset \bar{B}_{\scriptscriptstyle 0}\hspace{0.02cm}$. By the definition of $C_{\scriptscriptstyle 0\hspace{0.02cm}}$,

\mathrm{Hess}\,W_{\scriptscriptstyle c(u)}(\dot{c},\dot{c}) \leq
C_{\scriptscriptstyle 0}\hspace{0.02cm}\Vert \dot{c}\Vert^2_{\scriptscriptstyle c(u)}
= C_{\scriptscriptstyle 0}\hspace{0.02cm}\mu^2\Vert \mathrm{grad}\,f\Vert^2_{x^t}

Replacing into (<ref>), one now has

\begin{equation} \label{eq:proofpgd2}
W(x^{t+1}) \leq W(x^t) + \mu\hspace{0.02cm}\langle\mathrm{Exp}^{-1}_{x^t}(x^*),\mathrm{grad}\,f\rangle_{x^t} +
(C_{\scriptscriptstyle 0}/2)\hspace{0.02cm}\mu^2\Vert \mathrm{grad}\,f\Vert^2_{x^t}
\end{equation}

Therefore, by (<ref>) and (<ref>),

\begin{equation} \label{eq:proofpgd3}
W(x^{t+1}) \leq W(x^t)(1-\mu\alpha) + \mu(1-\mu(\bar{H}^\prime_{\scriptscriptstyle 0}C^{\phantom{\prime}}_{\scriptscriptstyle 0}))(f(x^*) - f(x))
\end{equation}

If $\mu \leq 1/\!(\bar{H}^\prime_{\scriptscriptstyle 0}C^{\phantom{\prime}}_{\scriptscriptstyle 0})$, then (<ref>) implies $W(x^{t+1}) \leq (1-\mu\alpha)W(x^t)$, because $f(x^*) - f(x) \leq 0$.The proposition easily follows by induction, since $1-\mu\alpha \geq 0$.

Proof of Lemma <ref> : let $c$ denote the geodesic with $c(0) = x$ and $\dot{c}(0) = (-1/\bar{H}^\prime_{\scriptscriptstyle 0})\hspace{0.02cm}\mathrm{grad}\,f(x)$. By the same arguments as in the proof of Lemma <ref>, one has that $c(u) \in \bar{B}^\prime_{\scriptscriptstyle 0}$ for all $u \in [0,1]$. Therefore, letting $y = c(1)$ and writing down the Taylor expansion (<ref>),

f(y) - f(x) \leq  (-1/\bar{H}^\prime_{\scriptscriptstyle 0})\Vert\mathrm{grad}\,f\Vert^2_x + (\bar{H}^\prime_{\scriptscriptstyle 0}/2)\Vert (1/\bar{H}^\prime_{\scriptscriptstyle 0})\hspace{0.02cm}\mathrm{grad}\,f(x)\Vert^2_x = (-1/2\bar{H}^\prime_{\scriptscriptstyle 0})\Vert\mathrm{grad}\,f\Vert^2_x

Multiplying this inequality by $-2\bar{H}^\prime_{\scriptscriptstyle 0\hspace{0.02cm}}$,

2\bar{H}^\prime_{\scriptscriptstyle 0}(f(x) - f(y)) \geq \Vert \mathrm{grad}\,f\Vert^2_x

Now, (<ref>) obtains by noting that $f(x) - f(x^*) \geq f(x) - f(y)$.

§ A VOLUME GROWTH LEMMA

Lemma <ref> will be used in the proof of Proposition <ref>, to be carried out in  <ref>. This lemma is of a purely geometric content, and is therefore considered separately, beforehand.

Let $M$ be a Riemannian symmetric space, which belongs to the non-compact case (see <ref>). Then, in particular, $M$ is a Hadamard manifold.

Fix $x^* \in M$, and let $(r,\theta)$ be geodesic spherical coordinates, with origin at $x^*$. Any $z \in M$, other than $x^*$, is uniquely determined by its coordinates $(r,\theta)$, and will be written $z(r,\theta)$.

Recall the volume density function $\det(\mathcal{A}(r,\theta))$, from the integral formula (<ref>). This will be denoted $\lambda(r,\theta) =\det(\mathcal{A}(r,\theta))$.

Essentially, the following lemma states the logarithmic rate of growth of the volume density function $\lambda(r,\theta)$ is bounded at infinity.

Let $M$ be a Riemannian symmetric space, which belongs to the non-compact case. Fix $x^* \in M$ and denote $r(x) = d(x^*,x)$ for $x \in M$. Then, for any $R > 0$,

\begin{equation} \label{eq:volmcmc}
\limsup_{r(x) \rightarrow \infty}\hspace{0.04cm}\frac{\sup_{\scriptscriptstyle z(r,\theta) \in B(x,R)}\hspace{0.04cm} \lambda(r,\theta)}
{\inf_{\scriptscriptstyle z(r,\theta) \in B(x,R)}\hspace{0.04cm} \lambda(r,\theta)}\,<\,\infty
\end{equation}

The proof of this lemma proceeds in the following way. Identify the unit sphere in $T_{x^*}M$ with $S^{n-1}$, and consider for $\theta \in S^{n-1}$ the self-adjoint curvature operator $R_\theta:T_{x^*M} \rightarrow T_{x^*}M$, given by

R_\theta(v) = -R(\theta,v)\hspace{0.02cm} \theta \hspace{0.2cm};\hspace{0.2cm} v \in T_{x^*}M

Recall that the Riemann curvature tensor is parallel (because $M$ is a symmetric space). Then, from (<ref>) and the definition of $\mathcal{A}(r,\theta)$, it follows that $\mathcal{A}(r,\theta)$ solves the Jacobi equation

\begin{equation} \label{eq:jacobiss}
\mathcal{A}^{\prime\prime} - R_{\theta}\hspace{0.02cm}\mathcal{A} = 0 \hspace{1cm} \mathcal{A}(0) = 0 \,,\, \mathcal{A}^\prime(0) = \mathrm{Id}_{x^*}
\end{equation}

where the prime denotes differentiation with respect to $r$. At present, all the eigenvalues of $R_\theta$ are positive. If $c^{\scriptscriptstyle 2}(\theta)$ runs through these eigenvalues, then it follows from (<ref>) that

\begin{equation} \label{eq:lambdamc1}
\lambda(r,\theta) \,=\, \prod_{c(\theta)}\left( \frac{\sinh(c(\theta)\hspace{0.02cm}r)}{c(\theta)}\right)^{\!\!m_{c(\theta)}}
\end{equation}

where $m_{c(\theta)}$ denotes the multiplicity of the eigenvalue $c^{\scriptscriptstyle 2}(\theta)$ of $R_\theta\hspace{0.02cm}$.

It is possible to express (<ref>) in a different form. Let $M = G/K$ where $K$ is the stabiliser in $G$ of $x^*$. Let $\mathfrak{g}$ and $\mathfrak{k}$ be the Lie algebras of $G$ and $K$, and $\mathfrak{g} = \mathfrak{k} + \mathfrak{p}$ the corresponding Cartan decomposition. Let $\mathfrak{a}$ be a maximal Abelian subspace of $\mathfrak{p}$, and recall that it is always possible to write $r\theta = \mathrm{Ad}(k)\,a$ for some $k \in K$ and $a \in \mathfrak{a}$ (see Lemma 6.3, Chapter V, in [10]). In this notation, $r = \Vert a \Vert_{x^*}$ and $c(\theta) = \lambda(a)/ \Vert a \Vert_{x^*}\hspace{0.02cm}$, where $\lambda$ is a positive roots of $\mathfrak{g}$ with respect to $\mathfrak{a}$, with multiplicity $m_\lambda = m_{c(\theta)}$ (see Lemma 2.9, Chapter VII, in [10]). Replacing into (<ref>) gives

\begin{equation} \label{eq:lambdamc2}
\lambda(r,\theta) \,=\, \prod_{\lambda \in \Delta_+}\left(  \frac{\sinh(\lambda(a))}{\lambda(a)/ \Vert a \Vert}\right)^{\!\!m_\lambda}
\end{equation}

Here, if the right-hand side is denoted by $f(a)$, then it is elementary that $\log\hspace{0.02cm}f(a)$ is a Lipschitz function, on the complement of any bounded subset of $\mathfrak{a}$ which contains the zero element of $\mathfrak{a}$.

Returning to (<ref>), let the supremum in the numerator be achieved at $(r_{\max\hspace{0.02cm}},\theta_{\max})$ and the infimum in the denominator be achieved at $(r_{\min\hspace{0.02cm}},\theta_{\min})$. Let $(k_{\max},a_{\max})$ and $(k_{\min},a_{\min})$ be corresponding values of $k$ and $a$. Note that for $z(r,\theta) \in B(x,R)$, by the triangle inequality, $r \geq r(x) - R$. But, since $r = \Vert a \Vert_{x^*\hspace{0.02cm}}$, this also means $\Vert a \Vert_{x^*\hspace{0.02cm}}  \geq r(x) - R$.

Therefore, if $r(x) > R$ then,  as stated above, $\log\hspace{0.02cm}f(a)$ is a Lipschitz function, on the set of  $a$ such that $\Vert a \Vert_{x^*\hspace{0.02cm}}  \geq r(x) - R$. If $\mathrm{C}$ is the corresponding Lipschitz constant,

\begin{equation} \label{eq:prooflemvolmc1}
\frac{\sup_{\scriptscriptstyle z(r,\theta) \in B(x,R)}\hspace{0.04cm} \lambda(r,\theta)}
{\inf_{\scriptscriptstyle z(r,\theta) \in B(x,R)}\hspace{0.04cm} \lambda(r,\theta)}\,\leq\, \exp[\mathrm{C}\hspace{0.02cm}\Vert a_{\max} - a_{\min}\Vert_{x^*}]
\end{equation}

Now, (<ref>) will follow by showing that $\Vert a_{\max} - a_{\min}\Vert_{x^*} < 2R$ wherever $r(x) > R$.

To do so, let $z_{\max} = z(r_{\max\hspace{0.02cm}},\theta_{\max})$ and $z_{\min} = z(r_{\min\hspace{0.02cm}},\theta_{\min})$, and note $d(z_{\max\hspace{0.02cm}},z_{\min}) \leq 2R$.If $c: [0,1]\rightarrow M$ is a geodesic curve with $c(0) = z_{\min}$ and $c(1) = z_{\max\hspace{0.02cm}}$, then

\begin{equation} \label{eq:prooflemvolmc2}
\int^{\scriptscriptstyle 1}_{\scriptscriptstyle 0}\,\Vert \dot{c}(t)\Vert_{\scriptscriptstyle c(t)}\hspace{0.03cm}dt = d(z_{\max\hspace{0.02cm}},z_{\min}) \leq 2R
\end{equation}

On the other hand, if $c(t) = c(r(t)\hspace{0.02cm},\theta(t))$, then it is possible to write $r(t)\hspace{0.02cm}\theta(t) = \mathrm{Ad}(k(t))\,a(t)$, where $k(t)$ and $a(t)$ are differentiable curves in $K$ and $\mathfrak{a}$. It will be shown below that this implies

\begin{equation} \label{eq:prooflemvolmc3}
\Vert \dot{c}(t)\Vert^2_{\scriptscriptstyle c(t)} = \Vert \dot{a}(t)\Vert^2_{\scriptscriptstyle x^*} + \sum_{\lambda \in \Delta_+} \sinh^2(\lambda(a(t))\hspace{0.02cm}\Vert \dot{k}_{\lambda}(t)\Vert^2_{\scriptscriptstyle x^*}
\end{equation}

where $\dot{k}_{\lambda}(t)$ is defined following (<ref>), below. Finally, from (<ref>) and (<ref>), it follows that

\Vert a_{\max} - a_{\min}\Vert_{x^*} \,\leq\, \int^{\scriptscriptstyle 1}_{\scriptscriptstyle 0}\Vert \dot{a}(t)\Vert_{\scriptscriptstyle x^*}\hspace{0.03cm}dt
\,\leq\, \int^{\scriptscriptstyle 1}_{\scriptscriptstyle 0}\Vert \dot{c}(t)\Vert_{\scriptscriptstyle c(t)}\hspace{0.03cm}dt \leq 2R

Replacing into (<ref>), this yields

\frac{\sup_{\scriptscriptstyle z(r,\theta) \in B(x,R)}\hspace{0.04cm} \lambda(r,\theta)}
{\inf_{\scriptscriptstyle z(r,\theta) \in B(x,R)}\hspace{0.04cm} \lambda(r,\theta)}\,\leq\, \exp(2\mathrm{C}R)

for all $x$ such that $r(x) > R$. However, this immediately implies (<ref>).

Proof of (<ref>) : in the notation of <ref>, $c(t) = \varphi(s(t)\hspace{0.02cm},a(t))$, where $s(t)$ is the representative of $k(t)$ in the quotient $K/K_{\mathfrak{a}\hspace{0.03cm}}$. Recall that $\varphi(s\hspace{0.02cm},a) = \mathrm{Exp}_o(\beta(s\hspace{0.02cm},a))$ where $\beta(s,a) = \mathrm{Ad}(s)\,a$(the dependence on $t$ is now suppressed). Then, by differentiating with respect to $t$,

\dot{\beta}(s,a) \,=\, \mathrm{Ad}(s)\left(\dot{a} \,+\, [\dot{s},a]\right)

Further, by replacing from (<ref>),

\dot{c} \,=\, \exp(r\theta)\cdot\mathrm{sh}(R_{r\theta})( \dot{\beta}(s,a))

However, $\mathrm{Ad}(s)$ preserves norms, and $\mathrm{Ad}(s^{\scriptscriptstyle -1})\circ R_{r\theta}\circ \mathrm{Ad}(s) = R_{a\hspace{0.02cm}}$, as in <ref>). Therefore,

\begin{equation} \label{eq:ncmetric1}
\Vert \dot{c}\Vert^2_{\scriptscriptstyle c} \,=\, \left\Vert\mathrm{sh}(R_{a})\left(\dot{a} \,+\, [\dot{s},a]\right)\right\Vert^2_{\scriptscriptstyle x^*}
\end{equation}

and from the definition of $\mathrm{sh}(R_{a})$,

\begin{equation} \label{eq:ncmetric2}
\mathrm{sh}(R_{a}) \,=\, \Pi_{\mathfrak{a}} + \sum_{\lambda \in \Delta_+}\frac{\sinh(\lambda(a))}{\lambda(a)}\,\Pi_{\lambda}
\end{equation}

Now, one has the orthogonal decomposition $\dot{s} = \sum_{\lambda \in \Delta_+} (\xi_\lambda + d\hspace{0.02cm}\theta(\xi_\lambda))$ where $[a,\xi_\lambda] = \lambda(a)\hspace{0.03cm}\xi_\lambda$ and $d\hspace{0.02cm}\theta$ was introduced before (<ref>) (see Lemma 3.6, Chapter VI, in [10]). In turn, this yields the orthogonal decomposition

\begin{equation} \label{eq:ncmetric3}
[a,\dot{s}] \,=\,\sum_{\lambda \in \Delta_+} \lambda(a)\hspace{0.03cm}(\xi_\lambda - d\hspace{0.02cm}\theta(\xi_\lambda))
\end{equation}

Letting $\dot{s}_\lambda = (\xi_\lambda - d\hspace{0.02cm}\theta(\xi_\lambda))$, it follows from (<ref>) and (<ref>) that

\Vert \dot{c}\Vert^2_{\scriptscriptstyle c} \,=\, \Vert \dot{a}\Vert^2_{\scriptscriptstyle x^*} + \sum_{\lambda \in \Delta_+} \sinh^2(\lambda(a))\hspace{0.02cm}\Vert \dot{s}_{\lambda}\Vert^2_{\scriptscriptstyle x^*}

This is the same as (<ref>), once $\dot{k}$ is identified with its representative $\dot{s}$.

§ PROOF OF GEOMETRIC ERGODICITY

The proof of Proposition <ref> relies on the so-called geometric drift condition. This condition requires that there exist a function $V:M \rightarrow \mathbb{R}$ such that

\begin{equation} \label{eq:VVbis}
V(x) \geq \max\left\lbrace 1\hspace{0.02cm},d^{\hspace{0.03cm} 2}(x,x^*)\right\rbrace \text{ for some } x^* \in M
\end{equation}

\begin{equation} \label{eq:gdrift}
PV(x) \leq \,\lambda\hspace{0.02cm}V(x) + b\hspace{0.02cm}\mathbf{1}_{\scriptscriptstyle C}(x) \hspace{3cm}
\end{equation}

for some $\lambda \in (0,1)$ and $b \in (0,\infty)$, and where $C$ is a small set for $P$ (for the definition, see [51]).
If the geometric drift condition (<ref>) is verified, then the geometric  ergodicity condition (<ref>) holds [51].

The proof is a generalisation of the proof carried out in the special case where $M$ is a Euclidean space, in [49]. The idea is to use Assumptions (a1)–(a3) to show that the following two conditions hold,

\begin{equation} \label{eq:ergod1}
\limsup_{r(x)\rightarrow \infty}\hspace{0.03cm}\frac{PV(x)}{V(x)}\,<\,1
\end{equation}

\begin{equation} \label{eq:ergod2}
\phantom{li}\, \sup_{x \in M}\hspace{0.03cm} \frac{PV(x)}{V(x)}\,<\,\infty
\end{equation}

where $r(x) = d(x^*,x)$, and $V(x) = a\hspace{0.03cm}\pi^{\scriptscriptstyle -\frac{1}{2}}(x)$ with $a$ chosen so $V(x) \geq 1$ for all $x \in M$. However, under Assumption (a3), these  two conditions are shown to imply (<ref>).

Let $(x_n)$ be a Markov chain in $M$, with transition kernel (<ref>), with proposed transition density $q(x\hspace{0.02cm},y) = q(d(x\hspace{0.02cm},y))$, and continuous, strictly positive invariant density $\pi$. Moreover, assume the proposed transition density satisfies Assumption (a3). If Conditions (<ref>) and (<ref>)  are verified, then the geometric drift condition (<ref>) holds.

On the other hand, (<ref>) (which is just the same as (<ref>)) is a straightforward result of Assumption (a1), which implies the existence of strictly positive $\mu, R$ and $\pi_{\scriptscriptstyle R}$ such that

\begin{equation} \label{eq:preVV}
r(x) \geq R \;\Longrightarrow\; \pi(x) \leq \pi_{\scriptscriptstyle R}\hspace{0.02cm}\exp\left(-\mu\hspace{0.02cm}r^2(x)\right)
\end{equation}

Then, to obtain (<ref>), it is enough to chose $a = \max\left\lbrace 1,R^{\hspace{0.03cm}\scriptscriptstyle 2},\pi^{\scriptscriptstyle 1/2}_{\scriptscriptstyle R},2\hspace{0.02cm}\mu^{\scriptscriptstyle -1}\right\rbrace\hspace{0.02cm}$.

Proof of Lemma <ref> : the proof is almost identical to the proofs for random-walk Metropolis chains in Euclidean space [49][52]. The main point is that Assumption (a3) implies that every non-empty bounded subset of $M$ is a small set for the transition kernel $P$ in (<ref>). With this in mind, the geometric drift condition (<ref>) follows almost directly from the two conditions (<ref>) and (<ref>). Indeed, (<ref>) implies that there exist $\lambda \in (0,1)$ and $R \in (0,\infty)$ such that

r(x) \geq R \;\Longrightarrow\; PV(x) \leq \lambda\hspace{0.02cm}V(x)

That is, (<ref>) is verified on $M - C$, where $C$ is the open ball $B(x^*,R)$. In addition, by (<ref>),

b = \left[ \sup_{x \in B(x^*,R)} V(x)\right]\,\left[\hspace{0.04cm} \sup_{x \in M}\hspace{0.03cm} \frac{PV(x)}{V(x)}\right]\,<\,\infty

Therefore, (<ref>) is also verified on $C$, since for $x \in C$,

PV(x) \leq b \leq \lambda\hspace{0.02cm}V(x) + b

Thus, (<ref>) is verified throughout $M$. It remains to note that $C$ is a small set, since it is bounded.

Now, the aim is to establish the two conditions (<ref>) and (<ref>). These will follow from Propositions <ref> and <ref>, below. Consider the proposed transition kernel

\begin{equation}\label{eq:propkernelQ}
Qf(x) \,=\, \int_M\,q(x\hspace{0.02cm},y)f(y)\hspace{0.02cm}\mathrm{vol}(dy)
\end{equation}

for any bounded measurable function $f:M\rightarrow \mathbb{R}$. If $f$ is the indicator function of a measurable set $A$, then it is usual to write $Qf(x) = Q(x,A)$. For $x \in M$, consider its acceptance region

A(x) = \left\lbrace y \in M: \pi(y) \geq \pi(x)\right\rbrace

Under the assumptions of Proposition <ref>, the following limit holds

\begin{equation} \label{eq:limQ}
\liminf_{r(x) \rightarrow \infty} Q(x\hspace{0.02cm},A(x))\,> \, 0
\end{equation}

Under the assumptions of Proposition <ref>, if (<ref>) holds, then the two conditions (<ref>) and (<ref>) are verified, where $V(x) = a\hspace{0.03cm}\pi^{\scriptscriptstyle -\frac{1}{2}}(x)$ with $a$ chosen so $V(x) \geq 1$ for all $x \in M$.

The proof of these two propositions will use the following fact, concerning the contour manifolds of the probability density function $\pi(x)$. For $x \in M$, the contour manifold of $x$ is the set $C_{x}$ of all $y \in M$ such that $\pi(y) = \pi(x)$. This is a hypersurface in $M$, whenever $\pi(x)$ is a regular value of  $\pi$ (by the “regular level set theorem" [53]).

fact : if $r(x)$ is sufficiently large, then $C_{x}$ can be parameterised by the unit sphere in $T_{x^*}M$. Precisely, it is possible to write

\begin{equation} \label{eq:contourm}
C_{x} = \left\lbrace \mathrm{Exp}_{x^*}\left( c(v)\hspace{0.02cm}v\right)\,; v \in S_{x^*}M\right\rbrace
\end{equation}

where $c$ is a positive continuous function on $S_{x^*}M$,  the set of unit vectors $v$ in $T_{x^*}M$. Moreover, $A(x)$ is exactly the region inside of $C_{x\hspace{0.03cm}}$. Precisely, $y \in A(x)$ if and only if $y = \mathrm{Exp}_{x^*}(c\hspace{0.02cm}v)$ where $v \in S_{x^*}M$ and $c \leq c(v)$.

Proof of Proposition <ref> : by Assumption (a2), there exist $\delta > 0$ and $R > 0$ such that

\begin{equation} \label{eq:proofproofgergodic11}
r(y) \geq R\;\Longrightarrow\; \langle\mathrm{grad}\,r,n\rangle_{y}\,<\,-\delta
\end{equation}

Let $-c^{\scriptscriptstyle 2}$ be a lower bound on the sectional curvatures of $M$, and $\Lambda$ be a positive number with

\begin{equation} \label{eq:Lambda}
(\dim\hspace{0.03cm}M)^{\scriptscriptstyle \frac{1}{2}}\hspace{0.03cm}\Lambda \,\leq\, \frac{\delta}{2c}\hspace{0.02cm}\tanh(c\hspace{0.02cm}R)
\end{equation}

Now, for any $x \in M$ with $r(x) \geq R + \Lambda$, consider the set

\Omega(x) \,=\,\left\lbrace \mathrm{Exp}_{x}(-a\hspace{0.02cm}u)\,; a \in (0,\Lambda)\,,u \in S_xM\,, \Vert \mathrm{grad}\,r(x) - u\Vert_{x} \hspace{0.02cm}\leq \frac{\delta}{2}\right\rbrace

Let $y = \mathrm{Exp}_{x}(-a\hspace{0.02cm}u)$ be a point in $\Omega(x)$, and $\gamma(t)$ the unit-speed geodesic with $\gamma(0) = x$ and $\gamma(a) = y$. It is first proved that

\begin{equation} \label{eq:proofproofgergodic12}
\langle\dot{\gamma}\hspace{0.02cm},n\rangle_{\gamma(t)}\, > 0 \hspace{0.3cm} \text{for } t \in (0,a)
\end{equation}

Indeed, the left-hand side of (<ref>) may be written

\langle\dot{\gamma}\hspace{0.02cm},n\rangle_{\gamma(t)} =   -\,\langle\mathrm{grad}\,r\hspace{0.02cm},n\rangle_{\gamma(t)}\hspace{0.03cm}

Then, if $\Pi^t_{\scriptscriptstyle 0}$ denotes the parallel transport along $\gamma$ from $\gamma(0) = x$ to $\gamma(t)$,

\begin{equation} \label{eq:proofproofgergodic13}
\langle\dot{\gamma}\hspace{0.02cm},n\rangle_{\gamma(t)} =   -\,\langle\mathrm{grad}\,r\hspace{0.02cm},n\rangle_{\gamma(t)}
+\langle\Pi^t_{\scriptscriptstyle 0}(\mathrm{grad}\,r(x) - u)\hspace{0.02cm},n\rangle_{\gamma(t)}
+\langle\mathrm{grad}\,r - \Pi^t_{\scriptscriptstyle 0}(\mathrm{grad}\,r(x))\hspace{0.02cm},n\rangle_{\gamma(t)}
\end{equation}

which may be checked by adding together the three terms, and noting that $\dot{\gamma}(t) = \Pi^t_{\scriptscriptstyle 0}(-u)$, since $\gamma$ is a geodesic with $\dot{\gamma}(0) = -u$. But, by the triangle inequality

r(\gamma(t)) \,\geq\, r(x) - d(x\hspace{0.02cm},\gamma(t))\,>\, (R+\Lambda) - \Lambda = R

since $d(x^*,x) = r(x) \geq  R + \Lambda$ and $d(x\hspace{0.02cm},\gamma(t)) \leq a \leq \Lambda$. Thus, it follows from (<ref>)

\begin{equation} \label{eq:proofproofgergodic14}
- \langle\mathrm{grad}\,r,n\rangle_{\gamma(t)}\,>\,\delta
\end{equation}

Moreover, since the parallel transport $\Pi^t_{\scriptscriptstyle 0}$ preserves norms, and since by definition of $\Omega(x)$, $\Vert\mathrm{grad}\,r(x) - u\Vert_{x} \leq \delta/2$, it follows from the Cauchy-Schwarz inequality

\begin{equation} \label{eq:proofproofgergodic15}
\langle\Pi^t_{\scriptscriptstyle 0}(\mathrm{grad}\,r(x) - u)\hspace{0.02cm},n\rangle_{\gamma(t)} \,\geq - \Vert \Pi^t_{\scriptscriptstyle 0}(\mathrm{grad}\,r(x) -u)\Vert_{x}= -\Vert\mathrm{grad}\,r(x) - u\Vert_{x} \geq -\delta/2
\end{equation}

On the other hand, let $(e_{\scriptscriptstyle i}\,;1,\ldots,n)$ be a parallel orthonormal base, along the geodesic $\gamma$. Then,

\langle \mathrm{grad}\,r - \Pi^t_{\scriptscriptstyle 0}(\mathrm{grad}\,r(x))\hspace{0.02cm},e_{\scriptscriptstyle i}\rangle_{\gamma(t)} \,=\,
\int^t_{\scriptscriptstyle 0}\left\langle\mathrm{Hess}\,r\cdot\dot{\gamma}\hspace{0.02cm},e_{\scriptscriptstyle i}\right\rangle_{\gamma(s)}ds

But, according to (<ref>) from Theorem <ref>,

\int^t_{\scriptscriptstyle 0}\left\langle\mathrm{Hess}\,r\cdot\dot{\gamma}\hspace{0.02cm},e_{\scriptscriptstyle i}\right\rangle_{\gamma(s)}ds\, \leq \int^t_{\scriptscriptstyle 0}c\hspace{0.02cm}\coth\left(c\hspace{0.02cm} r(\gamma(s))\right)ds\,\leq \Lambda\hspace{0.03cm}c\hspace{0.02cm}\coth\left(c\hspace{0.02cm} R\right)

Thus, using (<ref>), it follows by the Cauchy-Schwarz inequality

\begin{equation} \label{eq:proofproofgergodic16}
\langle \mathrm{grad}\,r - \Pi^t_{\scriptscriptstyle 0}(\mathrm{grad}\,r(x))\hspace{0.02cm},n\rangle_{\gamma(t)}\hspace{0.03cm}
\geq -\delta/2
\end{equation}

Finally, by adding (<ref>) to (<ref>) and (<ref>), it follows from (<ref>)

\langle\dot{\gamma}\hspace{0.02cm},n\rangle_{\gamma(t)}\, > \delta - \delta/2 - \delta/2 = 0

which is the same as (<ref>). Moving on, from (<ref>), it is possible to prove that

\begin{equation} \label{eq:proofproofgergodic17}
\Omega(x) \subset A(x)
\end{equation}

for all $x$ such that $r(x) \geq R + \Lambda$, where $A(x)$ is the acceptance region of $x$, defined after (<ref>).

To prove (<ref>), consider $y \in \Omega(x)$ and $\gamma(t)$ as before, with $\gamma(0) = x$ and $\gamma(a) = y$. Now, assume that $y \in C_{x\hspace{0.03cm}}$, the contour manifold of $x$, defined in (<ref>). Then, $\pi(\gamma(0)) = \pi(\gamma(a))$, so that, by the mean-value theorem, there exists $t \in (0,a)$ such that

\frac{d}{dt}\pi(\gamma(t)) = \langle\dot{\gamma}(t),\mathrm{grad}\,\pi\rangle_{\gamma(t)} = 0

But, from the definition of $n(x)$, this implies

\langle \dot{\gamma}(t),n\rangle_{\gamma(t)}=\,\Vert\mathrm{grad}\,\pi(x)\Vert^{\scriptscriptstyle -1}\hspace{0.03cm}\langle\dot{\gamma}(t),\mathrm{grad}\,\pi\rangle_{\gamma(t)} = 0

in contradiction with (<ref>). Thus, the assumption that $y \in C_{x}$ cannot hold. Since $y \in \Omega(x)$ is arbitrary, this means that

\begin{equation} \label{eq:proofproofgergodic18}
\Omega(x)\,\cap\, C_{x}\,=\, \varnothing
\end{equation}

However, note that $y_* = \mathrm{Exp}_{x}(-a\hspace{0.02cm}\mathrm{grad}\,r(x))$ belongs to $\Omega(x)$, as can be seen from the definition of $\Omega(x)$. Also, since $r(y_*) = r(x) - a$, it follows that $y_*$ is inside of $C_{x\hspace{0.03cm}}$. Therefore, $y_* \in A(x)$, and the intersection of $\Omega(x)$ and $A(x)$ is non-empty. Finally, it is enouh to note that the set $\Omega(x)$ is connected, since it is the image under $\mathrm{Exp}_{x}$ of a connected set. This implies that, if the intersection of $\Omega(x)$ and $R(x)$, the complement of $A(x)$, were non-empty, then $\Omega(x)$ would also intersect $C_{x\hspace{0.03cm}}$. Clearly, this would be in contradiction with (<ref>). Using (<ref>), it is now possible to prove (<ref>).  Indeed, for $x$ such that $r(x) \geq R+\Lambda$, it follows from (<ref>) that

\begin{equation} \label{eq:proofproofgergodic19}
Q(x\hspace{0.02cm},A(x)) \geq Q(x\hspace{0.02cm},\Omega(x)) = \int_{\Omega(x)}\,q(x\hspace{0.02cm},y)\hspace{0.02cm}\mathrm{vol}(dy)
\end{equation}

where the last equality follows from (<ref>). However, by Assumption (a3),

\begin{equation} \label{eq:proofproofgergodic20}
\int_{\Omega(x)}\,q(x\hspace{0.02cm},y)\hspace{0.02cm}\mathrm{vol}(dy) \,\geq\,\varepsilon_{\scriptscriptstyle q}\times\mathrm{vol}\left(\Omega(x)\cap B(x,\delta_{\scriptscriptstyle q})\right)
\end{equation}

Now, to prove (<ref>), it only remains to show that

\begin{equation} \label{eq:proofproofgergodic21}
\mathrm{vol}\left(\Omega(x)\cap B(x,\delta_{\scriptscriptstyle q})\right) \,\geq \mathrm{c}> 0
\end{equation}

where the constant $\mathrm{c}$ does not depend on $x$. Indeed, it is then clear from (<ref>) and (<ref>) that

\liminf_{r(x) \rightarrow \infty} Q(x\hspace{0.02cm},A(x))\,> \varepsilon_{\scriptscriptstyle q}\times\mathrm{c}> 0

To obtain (<ref>), let $(r,\theta)$ be geodesic spherical coordinates, with origin at $x$. Using the integral formula (<ref>), after noting $\lambda(r,\theta) =\det(\mathcal{A}(r,\theta))$, it follows

\begin{equation} \label{eq:proofproofgergodic22}
\mathrm{vol}\left(\Omega(x)\cap B(x,\delta_{\scriptscriptstyle q})\right) \,=\, \int^{\tau}_{\scriptscriptstyle 0}\!\!\!\int_{\scriptscriptstyle S^{n-1}}\mathbf{1}\lbrace\Vert \mathrm{grad}\,r(x) - u(\theta)\Vert_{x} \leq \delta/2 \rbrace\hspace{0.04cm}\lambda(r,\theta)\hspace{0.03cm}dr\hspace{0.02cm}\omega_{n-1}(d\theta)
\end{equation}

where $\tau = \min\lbrace\Lambda,\delta_{\scriptscriptstyle q}\rbrace$, and the map $\theta \mapsto u(\theta)$ identifies $S^{n-1}$ with $S_xM$. Here, by (<ref>) from Theoreom <ref>, $\lambda(r,\theta) \geq r^{n-1}$. Therefore, (<ref>) implies

\mathrm{vol}\left(\Omega(x)\cap B(x,\delta_{\scriptscriptstyle q})\right) \geq\left(\tau^{\scriptscriptstyle n}/n\right)\times\omega_{n-1}\!\left(\lbrace\Vert \mathrm{grad}\,r(x) - u(\theta)\Vert_{x} \leq \delta/2 \rbrace\right)

However, since the area measure $\omega$ is invariant by rotation, the area

\omega_{n-1}\!\left(\lbrace\Vert \mathrm{grad}\,r(x) - u(\theta)\Vert_{x} \leq \delta/2 \rbrace\right) = \varsigma

does not depend on $x$. Precisely, $\varsigma$ is equal to the area of a spherical cap, with angle equal to $2\hspace{0.02cm}\mathrm{acos}(1-\delta^{\scriptscriptstyle 2}/8)$.
Finally, (<ref>) is immediately obtained, by letting $\mathrm{c} = \left(\tau^{\scriptscriptstyle d}/d\right)\times \varsigma$.

Proof of Proposition <ref> : let $V(x) = a\hspace{0.03cm}\pi^{\scriptscriptstyle -\frac{1}{2}}(x)$, as in the proposition. Recall the transition kernel $P$ is given by (<ref>), which implies

\rho(x) = \int_M(1-\alpha(x\hspace{0.02cm},y))\hspace{0.02cm}q(x\hspace{0.02cm},y)\hspace{0.02cm}\mathrm{vol}(dy)

since the right-hand side of (<ref>) should integrate to $1$ when $f(x)$ is the constant function $f(x) = 1$. But, since $\alpha(x\hspace{0.02cm},y) = \mathrm{min}\left\lbrace1\hspace{0.02cm},\pi(y)/\pi(x) \right\rbrace$, it follows that $1 - \alpha(x\hspace{0.02cm},y) = 0$ when $y \in A(x)$, the acceptance region of $x$, defined after (<ref>). Thus,

\rho(x) = \int_{R(x)}\left[1 - \frac{\pi(y)}{\pi(x)}\right]q(x\hspace{0.02cm},y)\hspace{0.02cm}\mathrm{vol}(dy)

where $R(x)$, the complement of $A(x)$, is the rejection region of $x$. With this expression of $\rho(x)$, putting $f(x) = V(x)$ in (<ref>), it follows by a direct calculation that $PV(x)/V(x)$ is equal to

\begin{equation} \label{eq:proofproofgergodic21}
\int_{A(x)}q(x\hspace{0.02cm},y)\left[\frac{\pi(x)}{\pi(y)}\right]^{\! \frac{1}{2}\hspace{0.02cm}}\mathrm{vol}(dy) +
\int_{R(x)}q(x\hspace{0.02cm},y)\left( 1 - \left[\frac{\pi(y)}{\pi(x)}\right] + \left[\frac{\pi(y)}{\pi(x)}\right]^{\! \frac{1}{2}}\right)\mathrm{vol}(dy)
\end{equation}

Here, all the ratios are less than or equal to $1$, so that (<ref>) immediately implies (<ref>).

In order to prove (<ref>), it is enough to prove that

\begin{equation}\label{eq:proofproofgergodic22}
\lim_{r(x)\rightarrow\infty}\,\int_{A(x)}q(x\hspace{0.02cm},y)\left[\frac{\pi(x)}{\pi(y)}\right]^{\! \frac{1}{2}\hspace{0.02cm}}\mathrm{vol}(dy)\,=\,0\hspace{2.3cm}
\end{equation}

\begin{equation}\label{eq:proofproofgergodic23}
\lim_{r(x)\rightarrow\infty}\,\int_{R(x)}q(x\hspace{0.02cm},y)\left(\left[\frac{\pi(y)}{\pi(x)}\right]^{\! \frac{1}{2}}- \left[\frac{\pi(y)}{\pi(x)}\right] \right)\mathrm{vol}(dy) \,=\,0
\end{equation}

Indeed, if these two limits are replaced in (<ref>), it will follow that

\limsup_{r(x)\rightarrow\infty}\, \frac{PV(x)}{V(x)} = \limsup_{r(x)\rightarrow\infty}\,Q(x,R(x))
= \limsup_{r(x)\rightarrow\infty}\, 1 - Q(x,A(x)) < 1

where the inequality is obtained using (<ref>). However, this is the same as  (<ref>). Thus, to complete the proof, it is enough to prove (<ref>) and (<ref>). The proofs of (<ref>) and (<ref>) being very similar, only the proof of (<ref>) is presented.

Proof of (<ref>) : this is divided into three steps. First, it is proved that

\begin{equation} \label{eq:LLL1}
\lim_{L\rightarrow \infty}\,\int_{\scriptscriptstyle A(x) - B(x,L)}q(x\hspace{0.02cm},y)\hspace{0.02cm}(\alpha(y,x))^{\scriptscriptstyle \frac{1}{2}}\hspace{0.03cm}\mathrm{vol}(dy) = 0 \hspace{0.5cm} \text{uniformly in $x$}
\end{equation}

where $\alpha(y,x) = \pi(x)/\pi(y)$. To prove (<ref>) note that $\alpha(y,x) \leq 1$ for $y \in A(x)$, and that $A(x) - B(x,L) \subset M - B(x,L)$. It follows that, for any $x \in M$,

\begin{equation} \label{eq:LLL2}
\int_{\scriptscriptstyle A(x) - B(x,L)}q(x\hspace{0.02cm},y)\hspace{0.02cm}(\alpha(y,x))^{\scriptscriptstyle \frac{1}{2}}\hspace{0.03cm}\mathrm{vol}(dy) \,\leq\,
\int_{\scriptscriptstyle M - B(x,L)}q(x\hspace{0.02cm},y)\hspace{0.03cm}\mathrm{vol}(dy)
\end{equation}

Since $M$ is a symmetric space, there exists an isometry $g$ of $M$ such that $g\cdot x^* = x$. Since $g$ preserves Riemannian volume,

\int_{\scriptscriptstyle M - B(x,L)}q(x\hspace{0.02cm},y)\hspace{0.03cm}\mathrm{vol}(dy) =
\int_{\scriptscriptstyle M - B(x^*,L)}q(x\hspace{0.02cm},g\cdot y)\hspace{0.03cm}\mathrm{vol}(dy)

But, $q(x\hspace{0.02cm},y) = q(d(x\hspace{0.02cm},y))$ depends only on the Riemannian distance $d(x\hspace{0.02cm},y)$. This implies that $q(x\hspace{0.02cm},g\cdot y) = q(x^*,y)$, since $g$ is an isometry. Thus,

\int_{\scriptscriptstyle M - B(x,L)}q(x\hspace{0.02cm},y)\hspace{0.03cm}\mathrm{vol}(dy) =
\int_{\scriptscriptstyle M - B(x^*,L)}q(x^*,y)\hspace{0.03cm}\mathrm{vol}(dy)

Here, the right-hand side does not depend on $x$, and tends to zero as $L \rightarrow \infty$, as can be seen by putting $x = x^*$ in (<ref>). Now (<ref>) follows directly from (<ref>).

Second, assume that $r(x)$ is so large that the level set $C_x$ verifies (<ref>) and $A(x)$ is equal to the region inside $C_{x\hspace{0.03cm}}$. It is then proved that, for any $L > 0$,

\begin{equation} \label{eq:KKK1}
\lim_{r(x)\rightarrow\infty}\,\int_{\scriptscriptstyle A(x) \cap B(x,L) - C_x(\varepsilon)}
q(x\hspace{0.02cm},y)\hspace{0.02cm}(\alpha(y,x))^{\scriptscriptstyle \frac{1}{2}}\hspace{0.03cm}\mathrm{vol}(dy) = 0
\end{equation}

where $C_x(\varepsilon)$ is the tubular neighborhood of $C_x$ given by

C_x(\varepsilon) \,=\,\left\lbrace \mathrm{Exp}_y\left(s\hspace{0.02cm}\mathrm{grad}\,r(y)\right)\,;y \in C_x\,,|s|<\varepsilon\right\rbrace

Because of (<ref>), to prove (<ref>) it is enough to prove that

\begin{equation} \label{eq:KKK2}
\lim_{r(x)\rightarrow\infty}\,\alpha(y,x) = 0 \hspace{0.5cm} \text{uniformly in $y \in A(x) \cap B(x,L) - C_x(\varepsilon)$}
\end{equation}

However, this follows by Assumption (a1). Indeed, this assumption guarantees the existence of some strictly positive $\mu\hspace{0.02cm},R$ and $\pi_{\scriptscriptstyle R\hspace{0.04cm}}$, as in (<ref>). Then, take $r(x) \geq R + \varepsilon$ and note that,by (<ref>), for $y$ as in (<ref>), if $r(y) \leq R$,

\begin{equation} \label{eq:KKK3}
\alpha(y,x)  \leq \frac{\pi_{\scriptscriptstyle R}\hspace{0.02cm}\exp\left(-\mu\hspace{0.02cm}r^2(x)\right)}{\pi(y)} \leq
\frac{\pi_{\scriptscriptstyle R}\hspace{0.02cm}\exp\left(-\mu\hspace{0.02cm}r^2(x)\right)}{\min_{r(y)\leq R}\pi(y)}
\end{equation}

where the right-hand side converges to zero as $r(x) \rightarrow \infty$, uniformly in $y$. On the other hand, if $r(y) > R$, let $c$ be the unit-speed geodesic connecting $x^*$ to $y$. Since $y \in A(x)$ (so $y$ lies inside $C_x$) there exists some $r \geq r(y)$ such that $c(r) \in C_{x\hspace{0.03cm}}$. Moreover, since $y \notin C_x(\varepsilon)$, it follows that $r > r(y) + \varepsilon$. Then, it is possible to show, by Assumption (a1),

\alpha(y,x) = \frac{\pi(c(r))}{\pi(c(r(y)))} \leq \,\exp[-\mu\left( r^{\scriptscriptstyle 2} - r^{\scriptscriptstyle 2}(y)\right)]

By a direct calculation, this implies

\begin{equation} \label{eq:KKK4}
\alpha(y,x) \leq\exp[-\mu\left( 2\hspace{0.03cm}\varepsilon r - \varepsilon^{\scriptscriptstyle 2}\right)] \leq
\exp[-\mu\left( 2\hspace{0.03cm}\varepsilon r(w) - \varepsilon^{\scriptscriptstyle 2}\right)]
\end{equation}

where $w \in C_x$ is such that $r(w)$ is the minimum of $r(w^\prime)$, taken over all $w^\prime \in C_{x\hspace{0.03cm}}$. Note that the right-hand side of (<ref>) does not depend on $y$. Moreover, $\pi(w)$ tends to zero as $r(x) \rightarrow \infty$, since $\pi(w) = \pi(x)$, and $\pi(x)$ tends to zero as $r(x) \rightarrow \infty$. Therefore, because $\pi(w)$ is positive, it follows that $r(w) \rightarrow \infty$ as $r(x)\rightarrow \infty$. But, this implies the right-hand side of (<ref>) converges to zero as $r(x) \rightarrow \infty$, uniformly in $y$. Now, (<ref>) follows from (<ref>).

The third, and final, step is to show that, for any $L>0$,

\begin{equation} \label{eq:III1}
\lim_{\varepsilon\rightarrow 0}\limsup_{r(x)\rightarrow \infty}\,\int_{\scriptscriptstyle A(x) \cap B(x,L) \cap C_x(\varepsilon)}
q(x\hspace{0.02cm},y)\hspace{0.02cm}(\alpha(y,x))^{\scriptscriptstyle \frac{1}{2}}\hspace{0.03cm}\mathrm{vol}(dy) = 0
\end{equation}

For brevity, the proof is carried out under the assumption that $q(x\hspace{0.02cm},y)$ is bounded, uniformly in $x$ and $y$. If this assumption holds, then (<ref>) follows immediately by showing

\begin{equation} \label{eq:III2}
\lim_{\varepsilon\rightarrow 0}\limsup_{r(x)\rightarrow \infty}\,\mathrm{vol}\left( B(x,L) \cap C_x(\varepsilon)\right) = 0
\end{equation}

To show (<ref>), let $\theta \mapsto v(\theta)$ identify the Euclidean unit sphere $S^{n-1}$ with $S_{x^*}M$, and consider the following sets

\begin{array}{rl}
T(x) =& \lbrace \theta \in S^{n-1}: \mathrm{Exp}_{x^*}(rv(\theta)) \in B(x,L)\;\;\text{for some $r\geq 0$}\rbrace \\[0.2cm]
S(x) =& \lbrace \mathrm{Exp}_{x^*}(rv(\theta))\,; \theta \in T(x)\;\text{and}\;|r-r(x)|\leq L\rbrace
\end{array}

Using the triangle inequality, it is possible to show that

\begin{equation}\label{eq:III3}
B(x,L) \subset S(x) \subset B(x,3L)
\end{equation}

To estimate the volume in (<ref>), let $(r,\theta)$ be geodesic spherical coordinates, with origin at $x^*$. The first inclusion in (<ref>) implies $\mathrm{vol}\left(B(x,L)\cap C_x(\varepsilon)\right) \leq \mathrm{vol}\left(S(x)\cap C_x(\varepsilon)\right)$, and this yields

\mathrm{vol}\left(B(x,L)\cap C_x(\varepsilon)\right) \,\leq\, \int^{\scriptscriptstyle r(x)+L}_{\scriptscriptstyle r(x)-L}\!\!\int_{\scriptscriptstyle T(x)}\mathbf{1}_{C_x(\varepsilon)}\left( \mathrm{Exp}_{x^*}(rv(\theta))\right)\hspace{0.03cm}\lambda(r,\theta)\hspace{0.02cm}dr\hspace{0.02cm}\omega_{n-1}(d\theta)

in the notation of (<ref>), where $\lambda(r,\theta) = \det(\mathcal{A}(r,\theta))$. Bounding the last integral from above,

\begin{equation} \label{eq:III4}
\mathrm{vol}\left(B(x,L)\cap C_x(\varepsilon)\right) \,\leq\,2\varepsilon\hspace{0.02cm}\omega_{n-1}(T(x))\hspace{0.02cm}\sup_{z(r,\theta)\in B(x,3L)}\hspace{0.04cm} \lambda(r,\theta)
\end{equation}

where $z(r,\theta) =  \mathrm{Exp}_{x^*}(rv(\theta))$.  Similarly, the second inclusion in (<ref>) implies

\mathrm{vol}\left( B(x,3L)\right)\,\geq\,\mathrm{vol}(S(x))=
\int^{\scriptscriptstyle r(x)+L}_{\scriptscriptstyle r(x)-L}\!\!\int_{\scriptscriptstyle T(x)}\lambda(r,\theta)\hspace{0.02cm}dr\hspace{0.02cm}\omega_{n-1}(d\theta)

and bounding the last integral from below gives

\begin{equation} \label{eq:III5}
\mathrm{vol}\left( B(x,3L)\right)\,\geq\,2L
\hspace{0.02cm}\omega_{n-1}(T(x))\hspace{0.02cm}\inf_{z(r,\theta)\in B(x,3L)}\hspace{0.04cm} \lambda(r,\theta)
\end{equation}

From (<ref>) and (<ref>), it follows that

\begin{equation} \label{eq:III6}
\mathrm{vol}\left(B(x,L)\cap C_x(\varepsilon)\right) \,\leq\,
\left(\varepsilon\middle/L\right)\mathrm{vol}\left(B(x,3L)\right)\frac{\sup_{z(r,\theta)\in B(x,3L)}\hspace{0.04cm} \lambda(r,\theta)}{\inf_{z(r,\theta)\in B(x,3L)}\hspace{0.04cm} \lambda(r,\theta)}
\end{equation}

However, by the volume growth lemma <ref>, from <ref>,

\limsup_{r(x) \rightarrow \infty}\hspace{0.04cm}\frac{\sup_{z(r,\theta)\in B(x,3L)}\hspace{0.04cm} \lambda(r,\theta)}{\inf_{z(r,\theta)\in B(x,3L)}\hspace{0.04cm} \lambda(r,\theta)}= \mathrm{R}\,<\,\infty

Replacing into (<ref>), and noting that, since $M$ is a symmetric space,

$$\mathrm{vol}\left(B(x,3L)\right) = \mathrm{vol}\left(B(x^*,3L)\right)
it follows that

\limsup_{r(x) \rightarrow \infty}\hspace{0.04cm}\mathrm{vol}\left(B(x,L)\cap C_x(\varepsilon)\right) \leq
\left(\varepsilon\middle/L\right)\mathrm{vol}\left(B(x^*,3L)\right)\mathrm{R}

This immediately implies (<ref>), and therefore (<ref>).

Conclusion : finally, (<ref>) can be obtained by combining (<ref>), (<ref>) and (<ref>). Precisely, the integral under the limit in (<ref>) can be decomposed into the sum of three integrals

\left(\int_{\scriptscriptstyle A(x) - B(x,L)}+
\int_{\scriptscriptstyle A(x) \cap B(x,L) - C_x(\varepsilon)}+
\int_{\scriptscriptstyle A(x) \cap B(x,L) \cap C_x(\varepsilon)\hspace{0.02cm}}
\right)q(x\hspace{0.02cm},y)\hspace{0.02cm}(\alpha(y,x))^{\scriptscriptstyle \frac{1}{2}}\hspace{0.03cm}\mathrm{vol}(dy)

By (<ref>), for any $\Delta > 0$, it is possible to choose $L$ to make the first integral less than $\Delta/3$, irrespective of $x$ and $\varepsilon$. By (<ref>), it is possible to choose $\varepsilon$ to make the third integral less than $\Delta/3$, for all $x$ with sufficiently large $r(x)$. With $L$ and $\varepsilon$ chosen in this way, (<ref>) implies the second integral is less than $\Delta/3$, if $r(x)$ is sufficiently large. Then, the sum of the three integrals is  less than $\Delta$, and (<ref>) follows, because $\Delta$ is arbitrary.

CHAPTER: STOCHASTIC APPROXIMATION

The present chapter is based on [2][3]. It aims to give a general treatment, under realistic assumptions, of two problems related to stochastic approximation on Riemannian manifolds.

The first problem is to estimate the rate of convergence of a stochastic approximation scheme, to the set of critical points (i.e. zeros) of its mean field.

* <ref> introduces the concept of an approximate critical point of the mean field.

* <ref> and <ref> provide non-asymptotic upper bounds, for the number of iterations necessary, for a stochastic approximation scheme to find an approximate critical point of its mean field (specifically, exponential schemes are considered in <ref>, and retraction schemes in <ref>).

* <ref> and <ref> apply the results of <ref> and <ref> to two examples : estimation of a mixture of Gaussian densities, and principal component analysis (PCA).

The second problem is to derive a central limit theorem, describing the asymptotic behavior of constant-step-size exponential schemes, defined on Hadamard manifolds.

* <ref> states the central limit theorem : under realistic assumptions, a constant-step-size exponential scheme defines a geometrically ergodic Markov chain. As the step-size goes to zero, a re-scaled version of this Markov chain has the same asymptotic behavior as a linear diffusion process, with a multivariate normal invariant distribution.

* <ref> details the proof of this central limit theorem.

As a follow-up on the second problem, one final example is studied, as part of the present chapter.

* <ref> introduces the Riemannian AR(1) model : a Markov chain $(x_t\,;t=0,1,\ldots)$ with values in a Hadamard manifold $M$, where each $x_{t+1}$ is a geodesic convex combination of the old $x_t$ and of a new input $y_{\hspace{0.02cm}t+1}$, with respective weights $1-\mu$ (for $x_t$) and $\mu$ (for $y_{\hspace{0.02cm}t+1}$), for some $\mu \in (0,1)$.If $(y_t\,;t=1,2,\ldots)$ are independent samples from a probability distribution $P$ on $M$, then the Markov chain $(x_t)$ is geometrically ergodic, and its invariant distribution concentrates at the Riemannian barycentre of $P$, as $\mu$ goes to zero.

§ APPROXIMATE CRITICAL POINTS

Here, the main object of study will be a stochastic approximation scheme, on a Riemannian manifold $M$. Given some initial value $x_{\scriptscriptstyle 0} \in M$, and independent observations $(y_t\,;t=1,2,\ldots)$, drawn from a probability distribution $P$ on a measurable space $Y$, this computes a sequence of iterates $(x_t\,;t = 1,2,\ldots)$, according to the update rule

\begin{equation} \label{eq:retscheme}
x_{t+1} = \mathrm{Ret}_{x_t}\!\left(\mu_{\scriptscriptstyle t+1}\hspace{0.02cm}X_{y_{\scriptscriptstyle\hspace{0.02cm}t+1}}(x_t)\right)
\end{equation}

where $\mathrm{Ret}:TM \rightarrow M$ is a retraction, $(\mu_{\scriptscriptstyle t}\,;t=1,2,\ldots)$ is a sequence of (positive) step-sizes, and the map $X:Y\times M \rightarrow TM$ is such that $X(y,x) = X_y(x)$ always belongs to $T_xM$.

One says that $X:Y\times M \rightarrow TM$ is a random vector field. The corresponding mean vector field $X:M \rightarrow TM$ is given by

\begin{equation} \label{eq:meanfield}
X(x) = \int_{Y}\,X_y(x)\hspace{0.03cm}P(dy)
\end{equation}

which means that the noise vector field, given by $e_y(x) = X_y(x) - X(x)$, has zero expectation. In the following, it will be assumed the variance of this noise vector field is not too large,

\begin{equation} \label{eq:variancecontrol}
\int_{Y}\,\Vert e_y(x)\Vert^2_x\hspace{0.04cm}P(dy) \leq \sigma^2_{\scriptscriptstyle 0} + \sigma^2_{\scriptscriptstyle 1}\hspace{0.02cm}\Vert X\Vert^2_x
\end{equation}

for some constants $\sigma^2_{\scriptscriptstyle 0}\hspace{0.02cm},\sigma^2_{\scriptscriptstyle 1}$.

The scheme (<ref>) is often used to search for zeros (critical points) of the mean vector field $X$[Zeros of vector fields are also called “singular points", and “stationary points". The term “critical points" seems more in line with the context of stochastic approximation, where the mean vector field is often a gradient vector field, so the scheme (<ref>) is a stochastic gradient scheme, used to solve some optimisation problem.].After $t$ iterations, this scheme will have generated the iterates $(x_s\,;s = 1,\ldots,t)$. One may randomly sample these, by looking at $x_{\tau_t}$ where $\tau_t$ follows a discrete probability distribution

\begin{equation} \label{eq:tautt}
\mathbb{P}(\tau_t = s)  = \frac{\mu_{s+1}}{\sum^t_{s=1}\mu_{s+1}} \hspace{1cm} s = 1,\ldots, t
\end{equation}

Then, the scheme is said to have found an approximate critical point (precisely, an $\epsilon$-critical point, for some suitable accuracy $\epsilon > 0$) in expectation, if $\mathbb{E}\Vert X(x_{\tau_t})\Vert^2 \leq \epsilon$.

For example, note that if $\mu_{\scriptscriptstyle t} = \mu$ is a constant, so (<ref>) is a constant-step-size scheme,

\mathbb{E}\left[\Vert X(x_{\tau_t})\Vert^2_{x_{\tau_t}}\right] = \frac{1}{t}\sum^t_{s=1} \mathbb{E}\left[\Vert X(x_{s})\Vert^2_{x_{s}}\right]

is just the average, over the first $t$ iterates, of the expected norm of the mean field.

In order to study the stochastic approximation scheme (<ref>), it is helpful to introduce a Lyapunov function $V:M\rightarrow \mathbb{R}$. This is a positive function, which is continuously differentiable, and has $\ell$-Lipschitz gradient, in the sense of (<ref>). It is moreover assumed to satisfy

\begin{equation} \label{eq:lyapunov}
c\hspace{0.02cm}\Vert X\Vert^2_x \leq - \langle \mathrm{grad}\,V,X\rangle_x %\hspace{0.5cm}\text{and}\hspace{0.5cm} \Vert \mathrm{grad}\,V\Vert_x \leq \bar{c}\hspace{0.02cm}\Vert X\Vert_x
\end{equation}

for some constant $c > 0$.

Example 1 : let $M = S^n \subset \mathbb{R}^{n+1}$, the unit sphere of dimension $n$. If $x^*$ is some critical point of the mean field $X$, then one may choose $V(x) = 1-\cos d(x\hspace{0.02cm},x^*)$, where $d(x\hspace{0.02cm},x^*)$ denotes the Riemannian distance between $x$ and $x^*$. In this case, $V$ is positive and has $1$-Lipschitz gradient.

Example 2 : let $M$ be a Hadamard manifold, with sectional curvatures bounded below by $\kappa_{\min} = -c^{\hspace{0.02cm}\scriptscriptstyle 2}$. If $x^*$ is some critical point of the mean field $X$, then one may choose $V(x) = V_{x^*}(x)$, for some $\delta >0$, as in (<ref>). From Proposition <ref> and Lemma <ref>, $V$ is positive and has $(1+\delta\hspace{0.02cm}c)$-Lipschitz gradient. Lemma <ref> will be essential to all further analysis of the scheme (<ref>). The proof of this lemma, being somewhat elementary, is not given in detail.

If $V:M\rightarrow \mathbb{R}$ has $\ell$-Lipschitz gradient, then

\begin{equation} \label{eq:liptaylor}
\left|V(\mathrm{Exp}_x(v)) - V(x) -  \langle\mathrm{grad}\,V,v\rangle_{x}\right|\leq   (\ell/2)\hspace{0.02cm}\Vert v\Vert^2_x
\end{equation}

for any $x \in M$ and $v \in T_xM$.

Sketch of proof : consider the geodesic $c:[0,1]\rightarrow M$, given by $c(t) = \mathrm{Exp}_x(t\hspace{0.02cm}v)$. Then, let $V(t) = V(c(t))$ and note that $V^\prime(t) = \langle\mathrm{grad}\,V,\dot{c}\rangle_{c(t)\hspace{0.02cm}}$. Let $\Pi^{\scriptscriptstyle 0}_{t}$ denote parallel transport along $c$, from $c(t)$ to $c(0)$. Since this preserves scalar products, and $\dot{c}$ is parallel,

\begin{equation} \label{eq:vprime1}
V^\prime(t) = \langle\mathrm{grad}\,V,\dot{c}\rangle_{c(0)} + \langle \Pi^{\scriptscriptstyle 0}_{t}\left(\mathrm{grad}\,V_{c(t)}\right) - \mathrm{grad}\,V_{c(0)},\dot{c}\rangle_{c(0)}
\end{equation}

Then,  using (<ref>), it may be shown that

\begin{equation} \label{eq:vprime2}
\left| \langle \Pi^{\scriptscriptstyle 0}_{t}\left(\mathrm{grad}\,V_{c(t)}\right) - \mathrm{grad}\,V_{c(0)},\dot{c}\rangle_{c(0)}\right| \leq
\ell\hspace{0.02cm}t(L(c))^2
\end{equation}

Since $c(0) = x$ and $\dot{c}(0) = v$, (<ref>) follows by replacing (<ref>) into (<ref>), and integrating over $t$.

§ EXPONENTIAL SCHEMES

Consider now the case where $\mathrm{Ret} = \mathrm{Exp}$, in (<ref>). That is,

\begin{equation} \label{eq:expscheme}
x_{t+1} = \mathrm{Exp}_{x_t}\!\left(\mu_{\scriptscriptstyle t+1}\hspace{0.02cm}X_{y_{\scriptscriptstyle\hspace{0.02cm}t+1}}(x_t)\right)
\end{equation}

For this exponential scheme, Proposition <ref> provides a non-asymptotic bound on $\mathbb{E}\Vert X(x_{\tau_t})\Vert^2$, where
$\tau_t$ was defined in (<ref>). This proposition uses the notation

\begin{equation} \label{eq:barmup}
%  \lbrace \mu\hspace{0.02cm}t\rbrace_{\scriptscriptstyle -1} = \frac{1}{\sum^t_{s=1}\mu^{\scriptscriptstyle \phantom{p+1}}_s}\hspace{0.3cm};\hspace{0.2cm}
\lbrace\mu^{\scriptscriptstyle p}\rbrace_{t} = \frac{\sum^t_{s=1} \mu^{\scriptscriptstyle p+1}_{s+1}}{\sum^t_{s=1}\mu^{\scriptscriptstyle \phantom{p+1}}_{s+1}} %\hspace{0.5cm} \text{for $p \geq -1$}
\end{equation}

which is motivated by the fact that if $\mu_{\scriptscriptstyle t} = \mu$ is a constant, so (<ref>) is a constant-step-size scheme,then $\lbrace\mu^{\scriptscriptstyle p}\rbrace_{t} = \mu^{\scriptscriptstyle p}$. In this spirit, $\lbrace\mu^{\scriptscriptstyle 1}\rbrace_{t}$ will be written $\lbrace\mu^{\scriptscriptstyle 1}\rbrace_{ t} = \lbrace\mu\rbrace_{ t}$, throughout the following.

Consider the exponential scheme (<ref>), with mean vector field (<ref>), and where the noise variance satisfies (<ref>). Assume that there exists a positive function $V:M\rightarrow \mathbb{R}$, with $\ell$-Lipschitz gradient, which verifies (<ref>). If $\mu_t \leq c\hspace{0.02cm}(2\ell(1+\sigma^{\scriptscriptstyle 2}_{\scriptscriptstyle 1}))^{\scriptscriptstyle -1}$ for all $t$, then

\begin{equation} \label{eq:nasymp_exp}
\mathbb{E}\left[\Vert X(x_{\tau_t})\Vert^2_{x_{\tau_t}}\right] \leq (2/\!\hspace{0.02cm}c)\!\,\left[\left(V(x_{\scriptscriptstyle 0})\middle/t\right)\!\hspace{0.02cm}\lbrace \mu^{\scriptscriptstyle -1}\rbrace_{t} + (\ell\hspace{0.02cm}\sigma^2_{\scriptscriptstyle 0})\hspace{0.03cm}\lbrace\mu\rbrace_{t}\hspace{0.02cm} \right]
\end{equation}

Remark : the simplest application of this proposition is to a stochastic gradient scheme, whith mean field $X(x) = -\mathrm{grad}\,f(x)$ for a cost function $f:M\rightarrow \mathbb{R}$. If $f$ is positive (or just bounded below), and has $\ell_f$-Lipschitz gradient, then $V = f$ can be introduced, as a Lyapunov function, since (<ref>) then holds with $c = 1$. In the case of a constant-step-size scheme, with $\mu \leq (2\ell_f(1+\sigma^{\scriptscriptstyle 2}_{\scriptscriptstyle 1}))^{\scriptscriptstyle -1}$, it follows from (<ref>) that

\begin{equation} \label{eq:nasymp_exp_grad}
\frac{1}{2t}\sum^t_{s=1} \mathbb{E}\left[\Vert \mathrm{grad}\,f(x_{s})\Vert^2_{x_{s}}\right] \leq \left(f(x_{\scriptscriptstyle 0})\middle/t\hspace{0.02cm}\mu\right) + (\ell_f\hspace{0.02cm}\sigma^2_{\scriptscriptstyle 0})\hspace{0.03cm}\mu
\end{equation}

In particular, if $t$ is sufficiently large, then one must have $\mathbb{E}\Vert \mathrm{grad}\,f(x_{s})\Vert^2 \leq 3(\ell_f\hspace{0.02cm}\sigma^2_{\scriptscriptstyle 0})\hspace{0.03cm}\mu$, for at least one $s$ in the range $s = 1,\ldots, t$.

Remark : Proposition <ref> provides an estimate of the rate of convergence of a stochastic approximation scheme, to the set of critical points of its mean field, which is applicable even when this set of critical points is complicated. This is especially helpful for stochastic gradient schemes, with a cost function that has many global minima (see the the example in <ref>). Proposition <ref> will extend Proposition <ref>, from exponential schemes, to retraction schemes.

Proof of Proposition <ref> : for each $s = 0,1,\ldots,$ it follows from Lemma <ref> that

V(x_{s+1}) - V(x_s) \leq \mu_{\scriptscriptstyle s+1}\hspace{0.02cm}\langle\mathrm{grad}\,V,X_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}\rangle_{x_s} + \mu^2_{\scriptscriptstyle s+1}(\ell/2)\Vert X_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}\Vert^2_{x_s}
%\langle\mathrm{grad}\,V,\dot{c}\rangle_{c(0)} + (\ell/2)\hspace{0.02cm}(L(c))^2

Then, since $X_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}(x_s) = X(x_s) + e_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}(x_s)$,

\begin{equation} \label{eq:proofexpscheme1}
V(x_{s+1}) - V(x_s) \leq \mu_{\scriptscriptstyle s+1}\hspace{0.02cm}\langle\mathrm{grad}\,V,X_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}\rangle_{x_s} + \mu^2_{\scriptscriptstyle s+1}\ell\left(\Vert X \Vert^2_{x_s} + \Vert e_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}\Vert^2_{x_s}\right)
%\langle\mathrm{grad}\,V,\dot{c}\rangle_{c(0)} + (\ell/2)\hspace{0.02cm}(L(c))^2
\end{equation}

Let $\mathcal{Y}_s$ be the $\sigma$-algebra generated by $y_{\scriptscriptstyle 1},\ldots, y_s\hspace{0.03cm}$. Taking conditional expectations in (<ref>), it follows from (<ref>) that

-\mu_{\scriptscriptstyle s+1}\hspace{0.02cm}\langle\mathrm{grad}\,V,X\rangle_{x_s} \leq \mathbb{E}\left[V(x_{s}) - V(x_{s+1})\middle|\mathcal{Y}_s\right] + \mu^2_{\scriptscriptstyle s+1}\ell\left(\Vert X \Vert^2_{x_s} + \mathbb{E}\left[\Vert e_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}\Vert^2_{x_s}\middle|\mathcal{Y}_s\right]\right)

Then, from (<ref>),

-\mu_{\scriptscriptstyle s+1}\hspace{0.02cm}\langle\mathrm{grad}\,V,X\rangle_{x_s} \leq \mathbb{E}\left[V(x_{s}) - V(x_{s+1})\middle|\mathcal{Y}_s\right] + \mu^2_{\scriptscriptstyle s+1}\ell\left(\sigma^2_{\scriptscriptstyle 0} + (1+\sigma^2_{\scriptscriptstyle 1})\Vert X \Vert^2_{x_s}\right)

Therefore, using (<ref>), and rearranging terms,

\begin{equation} \label{eq:proofexpscheme2}
(c - \ell(1+\sigma^2_{\scriptscriptstyle 1})\mu_{\scriptscriptstyle s+1})\hspace{0.03cm}\mu_{\scriptscriptstyle s+1}\hspace{0.02cm}\Vert X \Vert^2_{x_s} \leq \mathbb{E}\left[V(x_{s}) - V(x_{s+1})\middle|\mathcal{Y}_s\right] + (\ell\hspace{0.02cm}\sigma^2_{\scriptscriptstyle 0})\hspace{0.03cm}\mu^2_{\scriptscriptstyle s+1}
\end{equation}

If $\mu_{s+1} \leq c\hspace{0.02cm}(2\ell(1+\sigma^{\scriptscriptstyle 2}_{\scriptscriptstyle 1}))^{\scriptscriptstyle -1}$, this becomes

(c/\!\hspace{0.04cm}2)\hspace{0.03cm}\mu_{\scriptscriptstyle s+1}\hspace{0.02cm}\Vert X \Vert^2_{x_s} \leq \mathbb{E}\left[V(x_{s}) - V(x_{s+1})\middle|\mathcal{Y}_s\right] + (\ell\hspace{0.02cm}\sigma^2_{\scriptscriptstyle 0})\hspace{0.03cm}\mu^2_{\scriptscriptstyle s+1}

Finally, (<ref>) follows by summing over $s = 1,\ldots, t$ and dividing by $\sum^t_{s=1}\mu_{s+1} = t/\!\hspace{0.02cm}\lbrace \mu^{\scriptscriptstyle -1}\rbrace_t\,$.

§ RETRACTION SCHEMES

Consider now the case where $\mathrm{Ret}$ in (<ref>) is a regular retraction, in the sense of <ref>. Then (<ref>) can be written under an exponential form,

\begin{equation} \label{eq:retexpscheme}
x_{t+1} = \mathrm{Exp}_{x_t}\!\left(\Phi_{x_t}\!\left(\mu_{\scriptscriptstyle t+1}\hspace{0.02cm}X_{y_{\scriptscriptstyle\hspace{0.02cm}t+1}}(x_t)\right)\right)
\end{equation}

where the maps $\Phi_x :T_xM\rightarrow T_xM$ were defined in (<ref>). This new exponential form is useful, since it renders possible the application of Lemma <ref>, as in the proof of Proposition <ref>.

In addition to being regular, the retraction $\mathrm{Ret}$ is assumed to verify

\begin{equation} \label{eq:retract_asump}
\Vert\Phi_x(v)\Vert_x \leq \Vert v\Vert_x \hspace{0.3cm}\text{and}\hspace{0.2cm}
\Vert\Phi_x(v) - v \Vert_x \leq \delta\hspace{0.02cm}\Vert v\Vert^3_x
\end{equation}

for all $x \in M$ and $v\in T_x M$, where $\delta > 0$ is a constant. This assumption holds true for the retractions studied in <ref> and <ref>, as may be verified, using elementary properties of the arctangent function.

It will also be assumed that the random vector field $X_y(x)$ has bounded third-order moments,

\begin{equation} \label{eq:thirdordermoments}
\int_{Y}\,\Vert X_y(x)\Vert^a_x\hspace{0.04cm}P(dy) \leq \tau_{\scriptscriptstyle a} \hspace{0.2cm}; a = 2,3
\end{equation}

for some constants $\tau_{\scriptscriptstyle 2}\hspace{0.02cm},\tau{\scriptscriptstyle 3} > 0$. This implies that it is possible to replace $\sigma^2_{\scriptscriptstyle 1} = 0$ in (<ref>).

The following Proposition <ref> is obtained by applying Lemma <ref> to the exponential form (<ref>) of the retraction scheme (<ref>), and taking advantage of the assumptions (<ref>) and (<ref>).

Consider the retraction scheme (<ref>), where $\mathrm{Ret}$ is a regular retraction, which satisfies (<ref>). Assume that (<ref>) holds, so it is possible replace $\sigma^2_{\scriptscriptstyle 1} = 0$ in (<ref>). Assume also that there exists a positive function, with bounded and $\ell$-Lipschitz gradient, which verifies (<ref>).If $\mu_t \leq (c/2\ell)$ for all $t$, then

\begin{equation} \label{eq:nasymp_ret}
\mathbb{E}\left[\Vert X(x_{\tau_t})\Vert^2_{x_{\tau_t}}\right] \leq (2/\!\hspace{0.02cm}c)\!\,\left[\left(V(x_{\scriptscriptstyle 0})\middle/t\right)\!\hspace{0.02cm}\lbrace \mu^{\scriptscriptstyle -1}\rbrace_{t} + (\ell\hspace{0.02cm}\sigma^2_{\scriptscriptstyle 0})\hspace{0.03cm}\lbrace\mu\rbrace_{t}+(\delta\tau_{\scriptscriptstyle 3}\hspace{0.02cm}\Vert V\Vert_{\scriptscriptstyle 1,\infty})\hspace{0.03cm}\lbrace\mu^{\scriptscriptstyle 2}\rbrace_{t}\hspace{0.02cm} \right]
\end{equation}

where $\Vert V\Vert_{\scriptscriptstyle 1,\infty} = \sup_{x \in M}\Vert \mathrm{grad}\,V\Vert_x\hspace{0.02cm}$.

The assumptions of Proposition <ref> (namely, that $X_y(x)$ has bounded third order moments, and that $\mathrm{grad}\,V(x)$ is uniformly bounded), can seem a bit too strong. In fact, these assumptions are quite natural, in several applications, where the underlying Riemannian manifold $M$ is compact. One such application, to the PCA problem, is presented in <ref>.

Remark : the first two terms on the right-hand side of (<ref>) are the same as on the right-hand side of (<ref>). Thus, replacing the Riemannian exponential $\mathrm{Exp}$ by a regular retraction $\mathrm{Ret}$ has the effect of introducing a second-order term (i.e. a constant multiple of $\lbrace\mu^{\scriptscriptstyle 2}\rbrace_{t}$) into (<ref>). This additional term vanishes, in the limit where $\delta$ goes to zero.

Proof of Proposition <ref> : for $s = 0,1,\ldots,$ it follows by applying Lemma <ref> to (<ref>) that

\begin{equation} \label{eq:proof_nasympret1}
V(x_{s+1}) - V(x_s) \leq \left\langle \mathrm{grad}\,V,\Phi_{x_s}\!\left(\mu_{\scriptscriptstyle s+1}\hspace{0.02cm}X_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}\right)\right\rangle_{x_s} + (\ell/2)\left\Vert
\Phi_{x_s}\!\left(\mu_{\scriptscriptstyle s+1}\hspace{0.02cm}X_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}\right)\right\Vert^2_{x_s}
\end{equation}

Here, the right-hand side may also be written

\mu_{\scriptscriptstyle s+1}\hspace{0.02cm}\left\langle \mathrm{grad}\,V,X_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}\right\rangle_{x_s} + (\ell/2)\left\Vert
\Phi_{x_s}\!\left(\mu_{\scriptscriptstyle s+1}\hspace{0.02cm}X_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}\right)\right\Vert^2_{x_s}
\left\langle \mathrm{grad}\,V,\Phi_{x_s}\!\left(\mu_{\scriptscriptstyle s+1}\hspace{0.02cm}X_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}\right) - \mu_{\scriptscriptstyle s+1}\hspace{0.02cm}X_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}\right\rangle_{x_s}

However, by (<ref>),

\begin{equation} \label{eq:proof_nasympret2}
\left\Vert
\Phi_{x_s}\!\left(\mu_{\scriptscriptstyle s+1}\hspace{0.02cm}X_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}\right)\right\Vert^2_{x_s} \leq
\mu^2_{s+1}\hspace{0.02cm}
\Vert X_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}\Vert^2_{x_s}
\end{equation}

and, in addition,

\begin{equation} \label{eq:proof_nasympret3}
\left\Vert
\Phi_{x_s}\!\left(\mu_{\scriptscriptstyle s+1}\hspace{0.02cm}X_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}\right) - \mu_{\scriptscriptstyle s+1}\hspace{0.02cm}X_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}\right\Vert_{x_s} \leq
\delta\hspace{0.02cm}\mu^3_{s+1}\hspace{0.02cm}
\Vert X_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}\Vert^3_{x_s}
\end{equation}

Replacing (<ref>) and (<ref>) into (<ref>), and using the Cauchy-Schwarz inequality,

V(x_{s+1}) - V(x_s) \leq \mu_{\scriptscriptstyle s+1}\hspace{0.02cm}\langle \mathrm{grad}\,V,X_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}\rangle_{x_s} + \mu^2_{s+1}(\ell/2)\hspace{0.02cm}
\Vert X_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}\Vert^2_{x_s} +
(\delta\Vert V\Vert_{\scriptscriptstyle 1,\infty})\hspace{0.02cm}\mu^3_{s+1}\hspace{0.02cm}
\Vert X_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}\Vert^3_{x_s}

Now, it is possible to proceed as in the proof of Proposition <ref>. Taking conditional expectations with respect to $\mathcal{Y}_s\hspace{0.03cm}$, and using (<ref>) and (<ref>),

- \mu_{\scriptscriptstyle s+1}\hspace{0.02cm}\langle \mathrm{grad}\,V,X\rangle_{x_s} -
\mu^2_{s+1}\ell\hspace{0.02cm}
\Vert X_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}\Vert^2_{x_s} \leq
-\Delta V_s +
(\ell\hspace{0.02cm}\sigma^2_{\scriptscriptstyle 0})\hspace{0.03cm}\mu^2_{s+1} +
(\delta\Vert V\Vert_{\scriptscriptstyle 1,\infty})\hspace{0.02cm}\mu^3_{s+1}\hspace{0.02cm}
\mathbb{E}\left[\Vert X_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}\Vert^3_{x_s}\middle|\mathcal{Y}_s\right]

where $\Delta V_s = \mathbb{E}\left[V(x_{s+1}) - V(x_{s})\middle|\mathcal{Y}_s\right]$.
Then, using (<ref>), it follows that

(c - \ell\mu_{\scriptscriptstyle s+1})\hspace{0.03cm}\mu_{\scriptscriptstyle s+1}\hspace{0.02cm}\Vert X \Vert^2_{x_s} \leq
-\Delta V_s +
(\ell\hspace{0.02cm}\sigma^2_{\scriptscriptstyle 0})\hspace{0.03cm}\mu^2_{s+1} +
(\delta\Vert V\Vert_{\scriptscriptstyle 1,\infty})\hspace{0.02cm}\mu^3_{s+1}\hspace{0.02cm}
\mathbb{E}\left[\Vert X_{y_{\scriptscriptstyle\hspace{0.02cm}s+1}}\Vert^3_{x_s}\middle|\mathcal{Y}_s\right]

so, inserting (<ref>), one obtains the inequality

(c - \ell\mu_{\scriptscriptstyle s+1})\hspace{0.03cm}\mu_{\scriptscriptstyle s+1}\hspace{0.02cm}\Vert X \Vert^2_{x_s} \leq
-\Delta V_s +
(\ell\hspace{0.02cm}\sigma^2_{\scriptscriptstyle 0})\hspace{0.03cm}\mu^2_{s+1} +
(\delta\tau_{\scriptscriptstyle 3}\hspace{0.02cm}\Vert V\Vert_{\scriptscriptstyle 1,\infty})\hspace{0.03cm}\mu^3_{s+1}

Here, if $\mu_t \leq (c/2\ell)$ for all $t$, then

(c/\!\hspace{0.04cm}2)\hspace{0.03cm}\mu_{\scriptscriptstyle s+1}\hspace{0.02cm}\Vert X \Vert^2_{x_s} \leq
-\Delta V_s +
(\ell\hspace{0.02cm}\sigma^2_{\scriptscriptstyle 0})\hspace{0.03cm}\mu^2_{s+1} +
(\delta\tau_{\scriptscriptstyle 3}\hspace{0.02cm}\Vert V\Vert_{\scriptscriptstyle 1,\infty})\hspace{0.03cm}\mu^3_{s+1}

Finally, (<ref>) follows by summing over $s = 1,\ldots, t$ and dividing by $\sum^t_{s=1}\mu_{s+1} = t/\!\hspace{0.02cm}\lbrace \mu^{\scriptscriptstyle -1}\rbrace_t\,$.

§ EXAMPLE : MIXTURE ESTIMATION

Let $M$ be a Riemannian symmetric space, which belongs to the non-compact case, (see <ref>). Consider a probability density $m$ on $M$, which is a mixture of Gaussian densities  (of the kind defined in <ref>),

\begin{equation} \label{eq:mixture}
m(y|x) = \frac{1}{K}\sum^K_{\kappa = 1}p(y|x_{\kappa}) \hspace{0.5cm} \text{where }\, p(y|x_{\kappa}) = (Z(1))^{-1}\exp\left[ -\frac{d^{\hspace{0.03cm}2}(y,x_\kappa)}{2}\right]
\end{equation}

where $K$ is the number of mixture components, and the normalising factor $Z(1)$ is given by (<ref>).The parameters $x = (x_\kappa\,;\kappa=1,\ldots,K)$ are to be estimated, by fitting the mixture density (<ref>) to data $y_{\scriptscriptstyle 1},\ldots, y_{\scriptscriptstyle N}\hspace{0.03cm}$. Then, maximum-likelihood estimation amounts to minimising the negative log-likelihood function

\begin{equation} \label{eq:neglh}
f(x) = -\log\hspace{0.02cm}Z(1)-\frac{1}{N}\sum^N_{n=1}\log\hspace{0.02cm} m(y_n|x)
\end{equation}

where the first term,  $-\log\hspace{0.02cm}Z(1)$, has been added to ensure that $f(x)$ is positive. The function $f$ is defined on the product Riemannian manifold, $M^{\scriptscriptstyle K} = M\times\ldots\times M$. Its gradient is then $\mathrm{grad}\,f = (\mathrm{grad}_{\kappa}\,f\,;\kappa = 1,\ldots, K)$, where $\mathrm{grad}_{\kappa}\,f$ denotes the gradient with respect to $x_{\kappa}\hspace{0.03cm}$.

For the negative log-likelihood function (<ref>),

\begin{equation} \label{eq:mixgrad}
\mathrm{grad}_{\kappa}\,f(x) = -\frac{1}{N}\sum^N_{n=1}\omega_\kappa(y_n)\hspace{0.03cm}\mathrm{Exp}^{-1}_{x_\kappa}(y_n)
\end{equation}

where $\omega_\kappa(y) \propto p(y|x_{\kappa})$ are positive weights, which add up to $1$.

Let $(y_t\,;t=1,2,\ldots)$ be chosen at random among the data $y_{\scriptscriptstyle 1},\ldots, y_{\scriptscriptstyle N}\hspace{0.03cm}$. By Lemma <ref>,

\begin{equation} \label{eq:mixstochgrad}
x^{t+1}_\kappa = \mathrm{Exp}_{x^t_\kappa}\!\left(\mu\hspace{0.03cm}X_\kappa(y_{\scriptscriptstyle\hspace{0.02cm}t+1},x^t_\kappa)\right) \hspace{0.5cm} \text{where }\,X_\kappa(y_{\scriptscriptstyle\hspace{0.02cm}t+1},x^t_\kappa) = \omega_\kappa(y_{\scriptscriptstyle\hspace{0.02cm}t+1})\hspace{0.03cm}\mathrm{Exp}^{-1}_{x^t_\kappa}(y_{\scriptscriptstyle\hspace{0.02cm}t+1})
\end{equation}

is a constant-step-size stochastic gradient scheme, for the cost function $f$. Here, the step-size $\mu$ is assumed to be less than  $1$ (in comparison to (<ref>), $t$ and $t+1$ have been written as superscripts, rather than subscripts, in order to accommodate the appearance of $\kappa$).

Now, let $C$ be a compact and convex subset of $M$, which contains all of the data points $y_{n}\hspace{0.03cm}$, as well as all of the initial values $x^{\scriptscriptstyle 0}_\kappa$ (since $M$ is a Hadamard manifold, one may take $C$ to be any sufficiently large closed geodesic ball). The diameter of $C$ will be denoted $\mathrm{D}_{\scriptscriptstyle C}\hspace{0.03cm}$. From (<ref>),

x^{t+1}_\kappa = x^t_\kappa\; \#_{\scriptscriptstyle \rho_{\hspace{0.01cm}t+1}}\,y_{\scriptscriptstyle\hspace{0.02cm}t+1} \hspace{0.5cm} \text{where } \rho_{\hspace{0.02cm}t+1} =
\mu\hspace{0.03cm}\omega_\kappa(y_{\scriptscriptstyle\hspace{0.02cm}t+1})

in the notation of (<ref>), from <ref>. Accordingly, the iterates $x^t_\kappa$ remain within $C$, for all $t$ and $\kappa$.Because $C$ is compact and convex, it then becomes possible to derive the following result, by repeating, with very minor changes, the arguments leading to (<ref>).

For the stochastic gradient scheme (<ref>), let $C$ be a compact and convex subset of $M$, which contains all of the data points $y_{n}\hspace{0.03cm}$, as well as all of the initial values $x^{\scriptscriptstyle 0}_\kappa$.If $\mu \leq (1/2\ell_{\scriptscriptstyle C})$, where $\ell_{\scriptscriptstyle C}$ denotes the supremum of the operator norm of $\mathrm{Hess}\,f(x)$, taken over $x = (x_{\kappa}\,;\kappa = 1,\ldots, K) \in C^{\scriptscriptstyle K}$, then for all $t = 1,2,\ldots$,

\begin{equation} \label{eq:mixnasymp_exp_grad}
\frac{1}{2t}\sum^t_{s=1} \mathbb{E}\left[\Vert \mathrm{grad}\,f(x^{s})\Vert^2_{x^{s}}\right] \leq \left(f_{\scriptscriptstyle C}\middle/t\hspace{0.02cm}\mu\right) + (\ell_{\scriptscriptstyle C}\hspace{0.02cm}\sigma^2_{\scriptscriptstyle 0})\hspace{0.03cm}\mu
\end{equation}

Here, $f_{\scriptscriptstyle C} = \sup_{x \in C^{\scriptscriptstyle K}} f(x)$ and $\sigma_{\scriptscriptstyle 0} = \sup_{x \in C^{\scriptscriptstyle K}}\Vert \mathrm{grad}\,f\Vert_x$  (explicit bounds on $f_{\scriptscriptstyle C\hspace{0.02cm}}$, $\sigma_{\scriptscriptstyle 0}$ and $\ell_{\scriptscriptstyle C}$ are given in the remark below).

Remark : tedious, but straightforward, calculations provide the upper bounds

\begin{equation} \label{eq:Cconstants1}
f_{\scriptscriptstyle C} \leq \frac{\mathrm{D}^2_{\scriptscriptstyle C}}{2} \hspace{0.27cm};\hspace{0.23cm} \sigma_{\scriptscriptstyle 0} \leq K\hspace{0.02cm}\mathrm{D}_{\scriptscriptstyle C}
\end{equation}

\begin{equation} \label{eq:Cconstants2}
\ell_{\scriptscriptstyle C} \leq (1+c\hspace{0.02cm}\mathrm{D}_{\scriptscriptstyle C}) + (1 + Z(1)\exp(\mathrm{D}_{\scriptscriptstyle C}/2))\mathrm{D}^2_{\scriptscriptstyle C}
\end{equation}

where $c$ is such that the sectional curvatures of $M$ lie within $[-c^{\hspace{0.02cm}\scriptscriptstyle 2},0]$.

Proof of Lemma <ref> : taking the gradient of (<ref>), it is clear that

\begin{equation} \label{eq:proofmixgrad0}
\mathrm{grad}_{\kappa}\,f(x) = -\frac{1}{N}\sum^N_{n=1}   \mathrm{grad}_{\kappa}\log m(y_n|x)
\end{equation}

Now, $\mathrm{grad}_{\kappa}\log m(y|x)$ can be computed as follows. If $\lambda$ is a random variable, independent from $y$, with $\mathbb{P}(\lambda = \kappa) = K^{\scriptscriptstyle -1}$, for $\kappa = 1,\ldots, K$, then $\mathbb{P}(\lambda = \kappa|y) = \omega_\kappa(y)$, with $\omega_\kappa(y)$ as in (<ref>). Therefore, using Bayes rule,

\frac{p(\lambda\hspace{0.02cm},y)}{m(y|x)} = \sum^K_{\nu = 1}\mathbf{1}\lbrace\lambda = \nu\rbrace\hspace{0.03cm}\omega_\nu(y)

where $p(\lambda\hspace{0.02cm},y)$ is the joint distribution of the couple $(\lambda\hspace{0.02cm},y)$. Taking logarithms,

\begin{equation} \label{eq:proofmixgrad1}
\log p(\lambda\hspace{0.02cm},y) - \log m(y|x) = \sum^K_{\nu = 1}\mathbf{1}\lbrace\lambda = \nu\rbrace\hspace{0.03cm}\log \omega_\nu(y)
\end{equation}

If $\mathbb{E}_y$ denotes conditional expectation with respect to $y$,

\mathbb{E}_y\left[\mathrm{grad}_{\kappa}\sum^K_{\nu = 1}\mathbf{1}\lbrace\lambda = \nu\rbrace\hspace{0.03cm}\log \omega_\nu(y)\right] = \sum^K_{\nu = 1}\omega_\nu(y)\hspace{0.03cm}\mathrm{grad}_{\kappa}\log \omega_\nu(y) = 0

where the second equality follows since the conditional probabilities $\omega_\nu(y)$ always add up to $1$. By replacing this into (<ref>),

\begin{equation} \label{eq:proofmixgrad2}
\mathrm{grad}_{\kappa}\log m(y|x) = \mathbb{E}_y\left[ \mathrm{grad}_{\kappa}  \log p(\lambda\hspace{0.02cm},y)\right]
\end{equation}

But, since $\lambda$ and $y$ are independent, the joint distribution $p(\lambda\hspace{0.02cm},y)$ reads

p(\lambda\hspace{0.02cm},y) = \frac{1}{K}\sum^K_{\nu = 1}\mathbf{1}\lbrace\lambda = \nu\rbrace\hspace{0.03cm} p(y|x_{\nu})

Therefore, taking logarithms,

\log p(\lambda\hspace{0.02cm},y) = -\log(K) + \sum^K_{\nu = 1}\mathbf{1}\lbrace\lambda = \nu\rbrace\hspace{0.03cm} \log p(y|x_{\nu})

This immediately yields,

\begin{equation} \label{eq:proofmixgrad4}
\mathbb{E}_y\left[ \mathrm{grad}_{\kappa}  \log p(\lambda\hspace{0.02cm},y)\right] =
\omega_\kappa(y)\hspace{0.03cm} \mathrm{grad}_{\kappa}\log p(y|x_{\kappa}) =
\omega_\kappa(y)\hspace{0.03cm}\mathrm{Exp}^{-1}_{x_\kappa}(y)
\end{equation}

where the second equality follows from (<ref>), and from the definition of $p(y|x_{\kappa})$ in (<ref>). Finally, replacing (<ref>) into (<ref>),

\begin{equation} \label{eq:proofmixgrad5}
\mathrm{grad}_{\kappa}\log m(y|x) = \omega_\kappa(y)\hspace{0.03cm}\mathrm{Exp}^{-1}_{x_\kappa}(y)
\end{equation}

so that (<ref>) follows by plugging (<ref>) into (<ref>).

§ EXAMPLE : THE PCA PROBLEM

Here, the notation will be the same as in <ref> and <ref>. The aim is to apply Proposition <ref>, to a constant-step-size stochastic gradient scheme, for the objective function (<ref>),

\begin{equation} \label{eq:pcafbis}
f(x) = \mathrm{tr}\left(x\Delta\right) \hspace{1cm} x \in \mathrm{Gr}_{\scriptscriptstyle \mathbb{R}}(p\,,q)
\end{equation}

where $\Delta$ is the covariance matrix of a zero-mean random vector $y$, with values in $\mathbb{R}^d$ ($d= p+q)$. It is assumed that $y$ has finite moments of order $6$.

The gradient of the objective function $f$ was given by (<ref>) and (<ref>). These can be written

\begin{equation} \label{eq:pcapxbis}
\mathrm{grad}\,f(x) = g\cdot \tilde{\omega}(x) \hspace{0.5cm} \text{where } \tilde{\omega}(x) = \mathrm{P}_o(g^\dagger\cdot \Delta)
\end{equation}

Now, let $b \in \mathrm{St}_{\scriptscriptstyle \mathbb{R}}(p\,,q)$ be such that $x = [b]$. By the discussion before (<ref>), choosing $g = (b,b^{\scriptscriptstyle \perp})$, it follows that $\mathrm{grad}\,f(x) = [X(b)]$, where $X(b) =  b^{\scriptscriptstyle \perp}\omega(b)\hspace{0.02cm}$. From (<ref>) and (<ref>), it is clear that $\omega(b) = (b^{\scriptscriptstyle \perp})^\dagger\Delta\hspace{0.03cm} b$. Therefore, using the fact that $x = bb^\dagger$ (this is the definition of $[b]$),

\begin{equation} \label{eq:pcameanfield}
X(b) = (\mathrm{I}_d - x)\Delta\hspace{0.03cm} b
\end{equation}

In terms of the random vector $y$, $X(b)$ is the expectation of $X_y(b)$, where

\begin{equation} \label{eq:pcaxy}
X_y(b) =  (\mathrm{I}_d - x)(yy^\dagger)\hspace{0.03cm} b
\end{equation}

Let $X_y(x) = [X_y(b)]$, and note that the expectation of $X_y(x)$ is equal to $\mathrm{grad}\,f(x)$ (by linearity).
Then, consider the constant-step-size stochastic gradient scheme

\begin{equation} \label{eq:pcascheme1}
x_{t+1} = \mathrm{Ret}_{x_t}\!\left(\mu\hspace{0.02cm}X_{y_{\scriptscriptstyle\hspace{0.02cm}t+1}}(x_t)\right)
\end{equation}

where $(y_t\,;t = 1,2,\ldots)$ are independent copies of $y$. If the retraction $\mathrm{Ret}$ is given as in (<ref>), this becomes

\begin{equation} \label{eq:pcascheme}
x_{t+1} = \mathrm{Span}(b_{t+1}) \hspace{0.25cm};\hspace{0.21cm} b_{t+1} = b_t +  \mu\hspace{0.03cm}(\mathrm{I}_d - b^{\phantom{\dagger}}_{\scriptscriptstyle\hspace{0.02cm}t}b^\dagger_{\scriptscriptstyle\hspace{0.02cm}t})(y^{\phantom{\dagger}}_{\scriptscriptstyle\hspace{0.02cm}t+1}y^\dagger_{\scriptscriptstyle\hspace{0.02cm}t+1})\hspace{0.03cm} b_t
\end{equation}

Proposition <ref>, applied to this scheme, yields the following bound.

Consider the constant-step-size scheme (<ref>)-(<ref>). For all $t = 1,2,\ldots,$

\begin{equation} \label{eq:pca_nasymp}
\frac{1}{2t}\sum^t_{s=1} \mathbb{E}\left[\Vert \mathrm{grad}\,f(x_{s})\Vert^2_{x_{s}}\right] \leq\left(p\Vert\Delta\Vert_{\scriptscriptstyle \mathrm{op}})\middle/t\hspace{0.02cm}\mu\right)\!\hspace{0.02cm} + (4\Vert\Delta\Vert_{\scriptscriptstyle \mathrm{op}}\hspace{0.02cm}m^{4}_y )\hspace{0.03cm}\mu+(\sqrt{8}\Vert \Delta\Vert_{\scriptscriptstyle F}\hspace{0.02cm}m^{6}_y)\hspace{0.03cm}\mu^{\scriptscriptstyle 2}
\end{equation}

where $\Vert\Delta\Vert_{\scriptscriptstyle \mathrm{op}}$ and $\Vert\Delta\Vert_{\scriptscriptstyle F}$ denote the operator norm and Frobenius norm of the matrix $\Delta$, while $m^{4}_y$ and $m^{6}_y$ denote the fourth-order and sixth-order moments of the random vector $y$.

Proposition <ref> follows directly from Proposition <ref>, by introducing $V(x) = p\Vert\Delta\Vert_{\scriptscriptstyle \mathrm{op}}-f(x)$, which satisfies $0 \leq V(x) \leq p\Vert\Delta\Vert_{\scriptscriptstyle \mathrm{op}\hspace{0.02cm}}$. Since $-\mathrm{grad}\,V(x) =\mathrm{grad}\,f(x)$, (<ref>) now holds with $c = 1$.

The function $V$ has $2\Vert\Delta\Vert_{\scriptscriptstyle \mathrm{op}}$-Lipschitz gradient, as will be shown in the remark below, and the norm of its gradient can be computed from (<ref>),

\begin{equation} \label{eq:pcav10}
\Vert\mathrm{grad}\,V\Vert_x = \Vert\mathrm{grad}\,f\Vert_x =
\Vert\tilde{\omega}_x\Vert_o \leq \Vert g^\dagger\cdot \Delta \Vert_{\scriptscriptstyle F}
\end{equation}

where the inequality follows from (<ref>), since $\mathrm{P}_o$ is an orthogonal projection. But, since $g$ is orthogonal, (<ref>) implies that $\Vert\mathrm{grad}\,V\Vert_x$ is bounded by $\Vert \Delta\Vert_{\scriptscriptstyle F\hspace{0.02cm}}$, uniformly in $x$.

Thus, to obtain (<ref>), it is possible to replace into (<ref>), $V(x_{\scriptscriptstyle 0}) \leq p\Vert\Delta\Vert_{\scriptscriptstyle \mathrm{op}\hspace{0.02cm}}$, $\ell = 2\Vert\Delta\Vert_{\scriptscriptstyle \mathrm{op}\hspace{0.02cm}}$, and $\Vert V\Vert_{\scriptscriptstyle 1,\infty} = \Vert \Delta\Vert_{\scriptscriptstyle F\hspace{0.02cm}}$.

For $\sigma^2_{\scriptscriptstyle 0}$ and $\tau_{\scriptscriptstyle 3\hspace{0.03cm}}$, recall that $X_y(x) = [X_y(b)]$, where $X_y(b) =  b^{\scriptscriptstyle \perp}\omega_y(b)$, with $\omega_y(b) =
(b^{\scriptscriptstyle \perp})^\dagger(yy^\dagger)\hspace{0.03cm} b$. However, this implies $X_y(x) = g\cdot \tilde{\omega}_y(b)$, ($\tilde{\omega}_y(b)$ is obtained from $\omega_y(b)$, according to (<ref>)). Thus, $\Vert X_y \Vert_x = \Vert \tilde{\omega}_y(b)\Vert_o = \sqrt{2}\Vert \omega_y(b)\Vert_{\scriptscriptstyle F\hspace{0.02cm}}$. By evaluating the Frobenius norm,

\Vert \omega_y(b)\Vert^2_{\scriptscriptstyle F} = \mathrm{tr}\left((\mathrm{I}_d - x)(yy^\dagger)x(yy^\dagger)\right) \leq
\Vert(\mathrm{I}_d - x)(yy^\dagger)\Vert_{\scriptscriptstyle F}\hspace{0.02cm}
\Vert (yy^\dagger)x\Vert_{\scriptscriptstyle F} \leq \Vert yy^\dagger\Vert^2_{\scriptscriptstyle F}

where the first inequality follows from the Cauchy-Schwarz inequality, and the second inequality follows because $x$ and $\mathrm{I}_d - x$ are orthogonal projectors. Since $\Vert yy^\dagger\Vert_{\scriptscriptstyle F}= \Vert y \Vert^2$ (the squared Euclidean norm of $y$), this implies $\Vert X_y \Vert_x \leq \sqrt{2}\Vert y \Vert^2$. Therefore, it is possible to set $\sigma^2_{\scriptscriptstyle 0} =2m^{4}_y$ and $\tau_{\scriptscriptstyle 3} = \sqrt{8}m^{6}_y\hspace{0.03cm}$.

Finally, the constant $\delta$ in (<ref>) can be taken equal to $1$. Indeed, if $\mathrm{Ret}_x$ is given by (<ref>) and $\Phi_x$ is given by (<ref>), then for $v \in T_x\mathrm{Gr}_{\scriptscriptstyle \mathbb{R}}(p\,,q)$, where $v = g\cdot \tilde{\omega}$ and $\omega$ has s.v.d. $\omega = ras^\dagger$, $\Phi_x(v) = g\cdot \tilde{\varphi}$ where $\varphi$ has s.v.d. $\varphi= r \arctan(a) s^\dagger$. Therefore,

\begin{equation} \label{eq:proofdeltaa1}
\Vert\Phi_x(v) - v \Vert_x = \Vert g\cdot\tilde{\varphi} - g\cdot\tilde{\omega}\Vert_x = \Vert \tilde{\varphi} - \tilde{\omega}\Vert_o
%\leq \delta\hspace{0.02cm}\Vert v\Vert^3_x
\end{equation}

If $k$ is given by (<ref>), then

\Vert \tilde{\varphi} - \tilde{\omega}\Vert_o =
\Vert k\cdot \arctan(\tilde{a}) - k \cdot \tilde{a}\Vert_o = \Vert \arctan(\tilde{a}) - \tilde{a}\Vert_o

By an elementary property of the $\arctan$ function, $\Vert \arctan(\tilde{a}) - \tilde{a}\Vert_o \leq \Vert \tilde{a}\Vert^3_o\hspace{0.03cm}$. Therefore,

\begin{equation} \label{eq:proofdeltaa2}
\Vert \tilde{\varphi} - \tilde{\omega}\Vert_o \leq \Vert \tilde{a}\Vert^3_o
\end{equation}

Replacing (<ref>) into (<ref>), and noting that $\Vert \tilde{a} \Vert_o = \Vert v \Vert_x\hspace{0.03cm}$, it follows that
$\Vert\Phi_x(v) - v \Vert_x \leq \Vert v \Vert^3_x\hspace{0.03cm}$. This is the second inequality in (<ref>), with $\delta = 1$. The first inequality in (<ref>) is obtained by an analogous reasoning, using once more the properties of the  $\arctan$ function.

Remark : it was claimed that the function $V$ has $2\Vert\Delta\Vert_{\scriptscriptstyle \mathrm{op}}$-Lipschitz gradient (this means $\mathrm{grad}\,V$ satisfies (<ref>), with $\ell =  2\Vert\Delta\Vert_{\scriptscriptstyle \mathrm{op}})$. To prove this claim, let
$c(t)$ be a geodesic, with $c(0) = x$ and $\dot{c}(0) = v$. In the notation of (<ref>), $
c(t) = \exp(t\, \hat{\omega}_{\scriptscriptstyle v})\cdot x$. From [10] (Theorem 3.3, Chapter IV),

\begin{equation} \label{eq:grass_parallel}
\Pi^{\scriptscriptstyle 1}_{\scriptscriptstyle 0}\left(\mathrm{grad}\,V(x)\right) = \exp(\hat{\omega}_{\scriptscriptstyle v})\cdot \mathrm{grad}\,V(x)
\end{equation}

But, $\mathrm{grad}\,V(x) = - \mathrm{grad}\,f(x)$, which is given by (<ref>). Therefore,

\begin{equation} \label{eq:grass_parallel1}
\Pi^{\scriptscriptstyle 1}_{\scriptscriptstyle 0}\left(\mathrm{grad}\,V(x)\right) = (\exp(\hat{\omega}_{\scriptscriptstyle v})g)\cdot \mathrm{P}_o(g^\dagger\cdot \Delta)
\end{equation}

On the other hand, letting $y = c(1)$, one has $y = (\exp(\hat{\omega}_{\scriptscriptstyle v})g)\cdot o$. Thus, from (<ref>),

\begin{equation} \label{eq:grass_parallel2}
\mathrm{grad}\,V(y) =
(\exp(\hat{\omega}_{\scriptscriptstyle v})g)\cdot \mathrm{P}_o((\exp(\hat{\omega}_{\scriptscriptstyle v})g)^\dagger\cdot \Delta)
\end{equation}

From (<ref>) and (<ref>),

\Vert \mathrm{grad}\,V(y)  -  \Pi^{\scriptscriptstyle 1}_{\scriptscriptstyle 0}\left(\mathrm{grad}\,V(x)\right)\Vert_y =
\Vert \mathrm{P}_o((\exp(\hat{\omega}_{\scriptscriptstyle v})g)^\dagger\cdot \Delta) - \mathrm{P}_o(g^\dagger\cdot \Delta) \Vert_o \leq
\Vert (\exp(\hat{\omega}_{\scriptscriptstyle v})g)^\dagger\cdot \Delta - g^\dagger\cdot \Delta \Vert_{\scriptscriptstyle F}

where the inequality holds since $\mathrm{P}_o$ is an orthogonal projection. Using the fact that

(\exp(\hat{\omega}_{\scriptscriptstyle v})g)^\dagger\cdot \Delta - g^\dagger\cdot \Delta = \int^1_0 \left(\Delta(t)\hspace{0.02cm}\hat{\omega}_{\scriptscriptstyle v} - \hat{\omega}_{\scriptscriptstyle v}\hspace{0.02cm}\Delta(t)\right) dt

where $\Delta(t) = (\exp(t\,\hat{\omega}_{\scriptscriptstyle v})g)^\dagger\cdot \Delta$, so $\Vert \Delta(t)\Vert_{\scriptscriptstyle op} = \Vert \Delta \Vert_{\scriptscriptstyle op}\hspace{0.02cm}$, it follows that

\Vert \mathrm{grad}\,V(y)  -  \Pi^{\scriptscriptstyle 1}_{\scriptscriptstyle 0}\left(\mathrm{grad}\,V(x)\right)\Vert_y \leq
\int^1_0 \Vert\Delta(t)\hspace{0.02cm}\hat{\omega}_{\scriptscriptstyle v} - \hat{\omega}_{\scriptscriptstyle v}\hspace{0.02cm}\Delta(t)\Vert_{\scriptscriptstyle F}\hspace{0.04cm} dt \leq 2\Vert \Delta\Vert_{\scriptscriptstyle op}\hspace{0.02cm}\Vert \hat{\omega}_{\scriptscriptstyle v}\Vert_{\scriptscriptstyle F}

By the remark at the end of <ref>, the right-hand side is $2\Vert \Delta\Vert_{\scriptscriptstyle op}\hspace{0.02cm}\Vert v\Vert_{x\hspace{0.03cm}}$. In other words,

\Vert \mathrm{grad}\,V(y)  -  \Pi^{\scriptscriptstyle 1}_{\scriptscriptstyle 0}\left(\mathrm{grad}\,V(x)\right)\Vert_y \leq
2\Vert \Delta\Vert_{\scriptscriptstyle op}\hspace{0.02cm}L(c)

This is equivalent to the required form of (<ref>), as can be seen by applying $\Pi^{\scriptscriptstyle 0}_{\scriptscriptstyle 1}$ under the norm.

§ A CENTRAL LIMIT THEOREM (CLT)

Here, the aim will be to derive a central limit theorem, describing the asymptotic behavior of certain constant-step-size exponential schemes, defined on Hadamard manifolds. This is a generalisation of the central limit theorem, which holds in Euclidean space, found in [54].

§.§ Geometric ergodicity

Consider the constant-step-size exponential scheme, defined on a Hadamard manifold $M$,

\begin{equation} \label{eq:cssexp}
x_{t+1} = \mathrm{Exp}_{x_t}\!\left(\mu\hspace{0.02cm}X_{y_{\scriptscriptstyle\hspace{0.02cm}t+1}}(x_t)\right)
\end{equation}

Since the observations $(y_t\,;t=1,2,\ldots)$ are independent and identically distributed, it follows that $(x_t\,;t=0,1,\ldots)$ is a time-homogeneous Markov chain with values in $M$. The following assumptions ensure that $(x_t)$ is geometrically ergodic, and therefore has a unique invariant distribution $\pi_\mu$.

e1. the noise vector $e_y(x)$ satisfies (<ref>).

e2. $e_y(x)$ is $P$-almost-surely a continuous function of $x$, and the distribution of $e_y(x)$ has strictly positive density, with respect to the Lebesgue measure on $T_xM$.

v1. there exists a positive function $V:M\rightarrow \mathbb{R}$, with compact sublevel sets, and $\ell$-Lipschitz gradient, which satisfies (<ref>).

v2. there exist $x^* \in M$ and $\lambda > 0$, such that

\begin{equation} \label{eq:attractive}
\langle \mathrm{grad}\,V,X\rangle_x \leq -\lambda\hspace{0.02cm}V(x)  \hspace{0.5cm} \text{for } x \neq x^*
\end{equation}

v3. $V(x) = 0$ if and only if $x = x^*$.

Consider the constant-step-size scheme (<ref>), on a Hadamard manifold $M$.Assume that e1, e2, v1, v2 hold. If $\mu \leq c\hspace{0.02cm}(2\ell(1+\sigma^{\scriptscriptstyle 2}_{\scriptscriptstyle 1}))^{\scriptscriptstyle -1}$, then the Markov chain $(x_t)$ is geometrically ergodic, with a unique invariant distribution $\pi_\mu$.

As the step-size $\mu$ goes to zero, the invariant distribution $\pi_\mu$ concentrates on the point $x^*$.

Under the same conditions as in Proposition <ref>, if v3 holds, then $\pi_{\mu}\,\Rightarrow\,\delta_{x^*}$ as $\mu \rightarrow 0$ (here, $\Rightarrow$ denotes weak convergence of probability measures).

§.§ A diffusion limit

Consider now the re-scaled sequence $(u_t\,;t=0,1,\ldots)$, with values in $T_{x^*}M$,

\begin{equation} \label{eq:re-scaledu}
u_t = \psi_\mu(x_t) \hspace{0.5cm} \text{where } \psi_\mu(x) = \mu^{-\frac{1}{2}}\mathrm{Exp}^{-1}_{x^*}(x)
\end{equation}

This is the image of $(x_t\,;t=0,1,\ldots)$, under the diffeomorphism $\psi_\mu:M\rightarrow T_{x^*}M$. It is therefore a time-homogeneous Markov chain with values in $T_{x^*}M$. The trasition kernels of $(x_t)$ and $(u_t)$ will be denoted $Q_\mu$ and $\tilde{Q}_\mu\hspace{0.03cm}$, respectively. Note that

\begin{equation} \label{eq:qtoqtilde}
\tilde{Q}_\mu\phi(u) = Q_\mu(\phi\circ \psi_\mu)(\psi^{\scriptscriptstyle -1}(u))
\end{equation}

for any measurable function $\phi:T_xM \rightarrow \mathbb{R}$.

The following assumptions ensure that, as $\mu$ goes to zero, $(u_t\,;t = 0,1,\ldots)$ behave like samples, taken at evenly spaced times $\tau_t = t\mu$, from a linear diffusion process $(U_\tau\,;\tau \geq 0)$.

d1. the (2,0)-tensor field $\Sigma$, defined by

\begin{equation} \label{eq:fieldsigma}
\Sigma(x) = \int_{Y}\, e_y(x) \otimes e_y(x)\hspace{0.03cm}P(dy) \hspace{0.5cm} \text{for } x\in M
\end{equation}

is continuous on $M$. d2. there exists a linear map $A:T_{x^*}M\rightarrow T_{x^*}M$, such that for $x \in M$,

\begin{equation} \label{eq:fieldA}
X(x) = \Pi^{\scriptscriptstyle 1}_{\scriptscriptstyle 0}\left(A\left(\mathrm{Exp}^{-1}_{x^*}(x)\right) + R(x)\right)
\end{equation}

where $\Pi^{\scriptscriptstyle 1}_{\scriptscriptstyle 0}$ denotes parallel transport along the unique geodesic $c:[0,1] \rightarrow M$, connecting $x^*$ to $x$,and $\Vert R(x) \Vert_{x^*} = o(d(x\hspace{0.02cm},x^*))$.

Now, let $(U_\tau\,:\tau \geq 0)$, be the linear diffusion process, with generator,

\begin{equation} \label{eq:generator}
\mathcal{L}\phi(u) = A^i_ju^j\hspace{0.02cm}\frac{\partial\phi}{\partial u^i}(u) + \frac{1}{2} \Sigma^{ij}_*\hspace{0.02cm}\frac{\partial^2\phi}{\partial u^i\partial u^j}(u)
\end{equation}

where $(A^i_j)$ and $(\Sigma^{ij}_*)$ are the matrices which represent the linear map $A$ and the tensor $\Sigma(x^*)$, in a basis of normal coordinates centred at $x^*$.

Consider the constant-step-size scheme (<ref>), on a Hadamard manifold $M$.Let $(u_t\,:t=0,1,\ldots)$ be given by (<ref>), and assume that e1, d1, d2 hold. For any compactly-supported, smooth function $\phi:T_xM \rightarrow \mathbb{R}$,

\begin{equation} \label{eq:functional}
\mu^{-1}\left[ \tilde{Q}_\mu\phi(u) - \phi(u)\right] =  \mathcal{L}\phi(u) \,+\, \varepsilon_{\mu}(u)
\end{equation}

where $\varepsilon_{\mu}(u) \rightarrow 0$ as $\mu \rightarrow 0$, uniformly on compact subsets of $T_{x^*}M$.

Remark : this proposition implies a functional central limit theorem, by application of [55] (Theorem 19.28). This says that the process $(U^\mu_\tau\,;\tau \geq 0)$, equal to $u_t$ for $t\mu \leq \tau < (t+1)\mu$, converges in distribution to the linear diffusion $U$, with generator (<ref>), in Skorokhod space. This functional central limit theorem can be used to study the asymptotic behavior of $(x_t)$, near a general critical point, which satisfies d2. Sadly, I have not yet had time to develop this idea.

§.§ The stable case

A central limit theorem can be derived, in the case where $x^*$ is a stable critical point of the mean field $X$, in the following sense.

t1. the linear map $A$ in (<ref>) has its spectrum contained in the open left half-plane.

In this case, the generator $\mathcal{L}$ in (<ref>) admits of a unique invariant distribution, which is multivariate normal with mean zero and covariance matrix $V$, the solution of the Lyapunov equation $AV + V\!\hspace{0.01cm}A^\dagger = \Sigma_*$ [56] ($A = (A^i_j)$ and $\Sigma_* = (\Sigma^{ij}_*)$). This will be denoted $\mathrm{N}(0,V)$.

Under the conditions of Proposition <ref>, the Markov chain $(x_t)$ has a unique invariant distribution $\pi_\mu$. Then, the same holds for the Markov chain $(u_t)$, which will have a unique invariant distribution $\tilde{\pi}_\mu$. This is $\tilde{\pi}_\mu(A) = \pi_\mu(\mathrm{Exp}_{x^*}(\mu^{1/2}A))$, for any measurable $A \subset T_{x^*}M$.

The following assumptions will be essential for the central limit theorem, which is stated in Proposition <ref>. Assumption t2 ensures tightness of the family $(\tilde{\pi}_\mu\,;\mu \leq c\hspace{0.02cm}(2\ell(1+\sigma^{\scriptscriptstyle 2}_{\scriptscriptstyle 1}))^{\scriptscriptstyle -1})$.

t2. for each $r > 0$ there exists $v(r) > 0$ such that $V(x) \geq v(r)$ if $d(x\hspace{0.02cm},x^*) > r$. Moreover, $v(r) \rightarrow \infty$ as $r \rightarrow \infty$ and $\left. a\middle/v(a^{\scriptscriptstyle 1/2}r)\right.$ is a non-descreasing function of $a > 0$, for any $r$.

t3. there exists $\alpha > 0$ such that

\begin{equation} \label{eq:extravariancecontrol}
\int_{Y}\,\Vert e_y(x)\Vert^{2+\alpha}_x\hspace{0.04cm}P(dy) \leq \tilde{\sigma}^2_{\scriptscriptstyle 0} + \tilde{\sigma}^2_{\scriptscriptstyle 1}\hspace{0.02cm}V(x)
\end{equation}

for some constants $\tilde{\sigma}^2_{\scriptscriptstyle 0}\hspace{0.02cm},\tilde{\sigma}^2_{\scriptscriptstyle 1}$.

Under the conditions of Propositions <ref> and <ref>, if t1, t2, t3 hold, then $\tilde{\pi}_\mu \Rightarrow \mathrm{N}(0,V)$ as $\mu \rightarrow 0$.

§ PROOF OF THE CLT

§.§ Proof of Proposition <ref>

The proof relies on the following two lemmas, which will be proved below.

Assume that e2 holds. Then, the Markov chain $(x_t)$ is Feller, and $|\mathrm{vol}|$-irreducible and aperiodic (where $|\mathrm{vol}|$ denotes the Riemannian volume measure on $M$).

Assume that e1, v1, v2 hold. If $\mu \leq c\hspace{0.02cm}(2\ell(1+\sigma^{\scriptscriptstyle 2}_{\scriptscriptstyle 1}))^{\scriptscriptstyle -1}$, then

\begin{equation} \label{eq:driftzero}
Q_\mu V(x) \leq (1-\lambda\mu/2)V(x) + (\ell\hspace{0.02cm}\sigma^2_{\scriptscriptstyle 0})\hspace{0.03cm}\mu^2
\end{equation}

for all $x \in M$.

Admitting these lemmas, the fact that the chain $(x_t)$ is geometrically ergodic follows from [51] (Theorem 16.0.1). Specifically, let $\tilde{V}(x) = V(x) + 1$. Then, by (<ref>),

Q_\mu \tilde{V}(x) \leq (1-\lambda\mu/2)\tilde{V}(x) + b \hspace{0.5cm} \text{where } b = (\ell\hspace{0.02cm}\sigma^2_{\scriptscriptstyle 0})\hspace{0.03cm}\mu^2 + \lambda\mu/2

Let $C = \lbrace x:V(x) \leq 4b/(\lambda\mu)\rbrace$. Clearly,

\begin{equation} \label{eq:drift1}
Q_\mu \tilde{V}(x) \leq (1-\lambda\mu/4)\tilde{V}(x) + b\hspace{0.02cm}\mathbf{1}_{\scriptscriptstyle C}(x)
\end{equation}

By v1, $\tilde{V}$ has compact sublevel sets, so $C$ is a compact subset of $M$. Therefore, since $(x_t)$ is Feller, $C$ is a small set for $Q_\mu$ [51] (Theorem 6.0.1). Then,  (<ref>) is a geometric drift condition towards the small set $C$. This is equivalent to $(x_t)$ being geometrically ergodic.

Proof of Lemma <ref> : let $f:M\rightarrow \mathbb{R}$ be a bounded continuous function. By a slight abuse of notation, let $y$ denote a random variable with distribution $P$. From (<ref>),

\begin{equation} \label{eq:qmuf}
Q_\mu f(x) = \mathbb{E}\left[f\!\left(\mathrm{Exp}_x\!\left(\mu\hspace{0.02cm}X(x) + \mu\hspace{0.02cm}e_y(x)\right)\right)\right]
\end{equation}

By e2, $e_y(x)$ is $P$-almost-surely a continuous function of $x$. By the dominated convergence theorem, $Q_\mu f(x)$ is a bounded continuous function of $x$. In other words, the transition kernel $Q_\mu$ is a Feller kernel, so the chain $(x_t)$ is Feller.

To show that $(x_t)$ is $|\mathrm{vol}|$-irreducible and aperiodic, it is enough to show that $Q_\mu(x,B) > 0$ whenever $\mathrm{vol}(B) > 0$, where $Q_\mu(x,B) = Q_\mu\mathrm{1}_{\scriptscriptstyle B}(x)$. By e2, if $w = e_y(x)$ then the distribution of $w$ is of the form $\gamma(w)\hspace{0.03cm}dw$, where $\gamma(w) > 0$, and $dw$ denotes the Lebesgue measure on $T_xM$. Therefore, from (<ref>),

Q_\mu(x,B) = \int_{T_xM} \mathbf{1}_{\scriptscriptstyle B}\!\left(\mathrm{Exp}_x\!\left(\mu\hspace{0.02cm}X(x) + \mu\hspace{0.02cm} w\right)\right)\,\gamma(w)\hspace{0.03cm}dw

Since $M$ is a Hadamard manifold, $\mathrm{Exp}_x$ is a diffeomorphism of $T_xM$ onto $M$. Accordingly,

Q_\mu(x,B) = (1/\mu)^{n}\hspace{0.05cm}\int_{B} \gamma\!\left((1/\mu)\mathrm{Exp}^{-1}_x(z) - X(x)\right)\!\left| J_x(z)\right|^{-1}\mathrm{vol}(dz)

where $n$ is the dimension of $M$, and $\mathrm{Exp}^*_x(\mathrm{vol})(dw) = (\left|J_x\right|\circ \mathrm{Exp}_x)(w)dw$, so that $|J_x(z)| > 0$.
Now, if $\mathrm{vol}(B) > 0$, it is clear that $Q_\mu(x,B) > 0$.

Proof of Lemma <ref> : for any $x_{\scriptscriptstyle 0} \in M$, it follows from (<ref>) that

\begin{equation} \label{eq:qmuV}
Q_\mu V(x_{\scriptscriptstyle 0}) = \mathbb{E}\left[V(x_{\scriptscriptstyle 1})\right] \hspace{0.5cm} \text{where } x_{\scriptscriptstyle 1} =
\mathrm{Exp}_{x_{\scriptscriptstyle 0}}\!\left(\mu\hspace{0.02cm}X(x_{\scriptscriptstyle 0}) + \mu\hspace{0.02cm}e_y(x_{\scriptscriptstyle 0})\right)
\end{equation}

where $y$ denotes a random variable with distribution $P$ (this is the same abuse of notation made in (<ref>)). However, using Lemma <ref>, it is possible to write, as in  (<ref>),
V(x_{\scriptscriptstyle 1})  \leq V(x_{\scriptscriptstyle 0})  + \mu\hspace{0.02cm}\langle\mathrm{grad}\,V,X_y\rangle_{x_{\scriptscriptstyle 0}} + \mu^2\ell\left(\Vert X \Vert^2_{x_{\scriptscriptstyle 0}} + \Vert e_{y}\Vert^2_{x_{\scriptscriptstyle 0}}\right)

By e1 and (<ref>), it follows after taking expectations,

\begin{equation} \label{eq:prooflemdrifto1}
Q_\mu V(x_{\scriptscriptstyle 0}) \leq V(x_{\scriptscriptstyle 0}) + \mu\hspace{0.02cm}\langle\mathrm{grad}\,V,X\rangle_{x_{\scriptscriptstyle 0}} +
\mu^2\ell(1+\sigma^2_{\scriptscriptstyle 1})\Vert X \Vert^2_{x_{\scriptscriptstyle 0}}
+ (\ell\hspace{0.02cm}\sigma^2_{\scriptscriptstyle 0})\hspace{0.03cm}\mu^2
\end{equation}

By v1, $V$ satisfies (<ref>), so that (<ref>) implies

\begin{equation} \label{eq:prooflemdrifto2}
Q_\mu V(x_{\scriptscriptstyle 0}) \leq V(x_{\scriptscriptstyle 0}) + \mu\hspace{0.02cm}(1 - \mu\hspace{0.02cm}
\ell(1+\sigma^2_{\scriptscriptstyle 1})/c)
\hspace{0.02cm}\langle\mathrm{grad}\,V,X\rangle_{x_{\scriptscriptstyle 0}} +
+ (\ell\hspace{0.02cm}\sigma^2_{\scriptscriptstyle 0})\hspace{0.03cm}\mu^2
\end{equation}

Since $\langle\mathrm{grad}\,V,X\rangle$ is negative, if $\mu \leq c\hspace{0.02cm}(2\ell(1+\sigma^{\scriptscriptstyle 2}_{\scriptscriptstyle 1}))^{\scriptscriptstyle -1}$, then (<ref>) implies

Q_\mu V(x_{\scriptscriptstyle 0}) \leq V(x_{\scriptscriptstyle 0}) + (\mu/2)
\hspace{0.02cm}\langle\mathrm{grad}\,V,X\rangle_{x_{\scriptscriptstyle 0}}
+ (\ell\hspace{0.02cm}\sigma^2_{\scriptscriptstyle 0})\hspace{0.03cm}\mu^2

Finally, by v2, this yields

\begin{equation} \label{eq:prooflemdrift3}
Q_\mu V(x_{\scriptscriptstyle 0}) \leq (1-\lambda\mu/2)V(x_{\scriptscriptstyle 0}) + (\ell\hspace{0.02cm}\sigma^2_{\scriptscriptstyle 0})\hspace{0.03cm}\mu^2
\end{equation}

which is the same as (<ref>), since $x_{\scriptscriptstyle 0}$ is arbitrary.

§.§ Proof of Proposition <ref>

Proposition <ref> implies that the chain $(x_t)$ has a unique invariant distribution, here denoted $\pi_\mu\hspace{0.02cm}$, for any $\mu \leq c\hspace{0.02cm}(2\ell(1+\sigma^{\scriptscriptstyle 2}_{\scriptscriptstyle 1}))^{\scriptscriptstyle -1}$. Integrating both sides of (<ref>) with respect to $\pi_\mu\hspace{0.02cm}$, it follows that

\int_M Q_\mu V(x)\hspace{0.02cm}\pi_\mu(dx) \leq (1-\lambda\mu/2)\int_M V(x)\hspace{0.02cm}\pi_\mu(dx) + (\ell\hspace{0.02cm}\sigma^2_{\scriptscriptstyle 0})\hspace{0.03cm}\mu^2

Since $\pi_\mu$ is an invariant distribution of the transition kernel $Q_\mu\hspace{0.02cm}$, this means

\int_M V(x)\hspace{0.02cm}\pi_\mu(dx) \leq (1-\lambda\mu/2)\int_M V(x)\hspace{0.02cm}\pi_\mu(dx) + (\ell\hspace{0.02cm}\sigma^2_{\scriptscriptstyle 0})\hspace{0.03cm}\mu^2

In other words,

\begin{equation} \label{eq:Vmoment}
\int_M V(x)\hspace{0.02cm}\pi_\mu(dx) \leq 2(\ell\hspace{0.02cm}\sigma^2_{\scriptscriptstyle 0}/\lambda)\hspace{0.02cm}\mu
\end{equation}

so, by Markov's inequality,

\begin{equation} \label{eq:Vmarkov}
\pi_{\mu}(V > v) \leq 2(\ell\hspace{0.02cm}\sigma^2_{\scriptscriptstyle 0}/\lambda)\hspace{0.02cm}\frac{\mu}{v} \hspace{0.5cm} \text{for all $v > 0$}
\end{equation}

By v1, $V$ has compact sublevel sets, so (<ref>) implies the family $(\pi_\mu\,;\mu \leq c\hspace{0.02cm}(2\ell(1+\sigma^{\scriptscriptstyle 2}_{\scriptscriptstyle 1}))^{\scriptscriptstyle -1})$ is tight. If $\pi_*$ is a limit point of this family at $\mu = 0$, then by the Portmaneau theorem, $\pi_*(V > v) = 0$ for all $v > 0$. In other words, $\pi_*(V = 0) = 1$. By v3, this is equivalent to $\pi_*(\lbrace x^*\rbrace) = 1$, or to $\pi_* = \delta_{x^*}\hspace{0.02cm}$.

§.§ Proof of Proposition <ref>

The proof exploits the relation (<ref>), between the transition kernels $Q_\mu$ and $\tilde{Q}_\mu\hspace{0.02cm}$, using the following Lemmas <ref>, <ref>, and <ref>.

In Lemma <ref>, $[H\!:\!T]$ will denote the contraction of a (0,2)-tensor $H$ with a (2,0)-tensor $T$.This is  $[H\!:\!T] = H_{ij}T^{ij}$, in any local coordinates. Moreover, if $f :M\rightarrow \mathbb{R}$ is compactly-supported and smooth, $A_f\hspace{0.02cm},B_f$ denote positive numbers such that

\begin{equation} \label{eq:AfBf}
|\mathrm{Hess}\,f_x(w,w)| \leq A_f\Vert w \Vert^2_x \hspace{0.25cm}\text{and}\hspace{0.2cm}
|\nabla\mathrm{Hess}\,f_x(w,w,w)| \leq B_f\Vert w \Vert^3_x
\end{equation}

for any $x \in M$ and $w \in T_xM$, where $\nabla\mathrm{Hess}\,f$ is the covariant derivative of the Hessian of $f$ (respectively, $\mathrm{Hess}\,f$ and $\nabla\mathrm{Hess}\,f$ are (0,2)- and (0,3)-tensor fields).

For any compactly-supported, smooth $f :M\rightarrow \mathbb{R}$,

\begin{equation} \label{eq:qtaylor}
Q_\mu f(x) = f(x) + \mu\hspace{0.02cm}Xf(x) + \frac{\mu^2}{2}[\mathrm{Hess}\,f\!:\!\Sigma + X \otimes X]_x + \mu^2\hspace{0.03cm}\mathcal{R}_x(f,\mu)
\end{equation}

where the remainder term $\mathcal{R}_x(f,\mu)$ satisfies

\leq 2A_f\hspace{0.03cm}\mathbb{E}\left[\mathbf{1}\lbrace \Vert e_y\Vert_x> K\rbrace\Vert e_y\Vert^2_x\right] + \hspace{8cm}

\begin{equation} \label{eq:qremainder}
\phantom{abcd}6B_f\hspace{0.03cm}
\mu\hspace{0.02cm}(2\Vert X \Vert^2_x + 2K^2)\hspace{0.03cm}\mathbb{E}\left[\mathbf{1}\lbrace \Vert e_y\Vert_x> K\rbrace\Vert e_y\Vert_x\right]+2B_f\hspace{0.03cm}\mu\hspace{0.02cm}(4\Vert X \Vert^3_x + 4K^3)
\end{equation}

for any (arbitrarily chosen) $K > 0$.