when $0<\eta<\frac{1}{D\left|\left|p\right|\right|_{\infty}^{(2)}}$. Using
this inequality and condition (A7), we derive that

$\displaystyle\sqrt{p(\bm{x}^{*})-p(\bm{x}^{(t+1)})}$
$\displaystyle=\sqrt{p(\bm{x}^{*})-p\left(\bm{x}^{(t)}+\eta\cdot
V_{d}(\bm{x}^{(t)})V_{d}(\bm{x}^{(t)})^{T}\nabla p(\bm{x}^{(t)})\right)}$
$\displaystyle\leq\sqrt{p(\bm{x}^{*})-p(\bm{x}^{(t)})-\frac{\eta}{2}\left|\left|V_{d}(\bm{x}^{(t)})^{T}\nabla
p(\bm{x}^{(t)})\right|\right|_{2}^{2}}$
$\displaystyle\stackrel{{\scriptstyle\text{(i)}}}{{\leq}}\sqrt{p(\bm{x}^{*})-p(\bm{x}^{(t)})}-\frac{\eta\left|\left|V_{d}(\bm{x}^{(t)})^{T}\nabla
p(\bm{x}^{(t)})\right|\right|_{2}^{2}}{4\sqrt{p(\bm{x}^{*})-p(\bm{x}^{(t)})}}$
$\displaystyle\stackrel{{\scriptstyle\text{(ii)}}}{{\leq}}\sqrt{p(\bm{x}^{*})-p(\bm{x}^{(t)})}-\frac{\eta\sqrt{2\beta_{3}}}{4}\left|\left|V_{d}(\bm{x}^{(t)})^{T}\nabla
p(\bm{x}^{(t)})\right|\right|_{2},$

where we use the inequality $\sqrt{a-b}\leq\sqrt{a}-\frac{b}{2\sqrt{a}}$ to
obtain (i) and apply condition (A7) in inequality (ii). Since
$\left|\left|\bm{x}^{(t+1)}-\bm{x}^{(t)}\right|\right|_{2}=\eta\left|\left|V_{d}(\bm{x}^{(t)})^{T}\nabla
p(\bm{x}^{(t)})\right|\right|_{2}$, some rearrangement of the above inequality
suggests that

$\sqrt{\frac{\beta_{3}}{8}}\left|\left|\bm{x}^{(t+1)}-\bm{x}^{(t)}\right|\right|_{2}\leq\sqrt{p(\bm{x}^{*})-p(\bm{x}^{(t)})}-\sqrt{p(\bm{x}^{*})-p(\bm{x}^{(t+1)})}.$

Therefore,

$\displaystyle\sum_{s=t}^{\infty}\left|\left|\bm{x}^{(s+1)}-\bm{x}^{(s)}\right|\right|_{2}$
$\displaystyle\leq\sqrt{\frac{8}{\beta_{3}}}\sum_{s=t}^{\infty}\left[\sqrt{p(\bm{x}^{*})-p(\bm{x}^{(s)})}-\sqrt{p(\bm{x}^{*})-p(\bm{x}^{(s+1)})}\right]$
$\displaystyle=\sqrt{\frac{8}{\beta_{3}}}\cdot\sqrt{p(\bm{x}^{*})-p(\bm{x}^{(t)})}$
$\displaystyle\stackrel{{\scriptstyle\text{(i)}}}{{\leq}}\sqrt{\frac{8}{\beta_{3}}}\cdot\sqrt{\frac{1}{2\beta_{3}}}\cdot\left|\left|V_{d}(\bm{x}^{(t)})^{T}\nabla
p(\bm{x}^{(t)})\right|\right|_{2}\quad\text{ by condition (A4)}$
$\displaystyle=\frac{2}{\beta_{3}}\left|\left|V_{d}(\bm{x}^{(t)})^{T}\nabla
p(\bm{x}^{(t)})-\underbrace{V_{d}(\bm{x}^{*})^{T}\nabla
p(\bm{x}^{*})}_{=0}\right|\right|_{2}$
$\displaystyle\stackrel{{\scriptstyle\text{(ii)}}}{{\leq}}\frac{2}{\beta_{3}}\left|\left|\sup_{\epsilon\in[0,1]}M(\bm{x}^{*}+\epsilon(\bm{x}^{(t)}-\bm{x}^{*}))^{T}\left(\bm{x}^{(t)}-\bm{x}^{*}\right)\right|\right|_{2}$
$\displaystyle\stackrel{{\scriptstyle\text{(iii)}}}{{\leq}}\frac{2}{\beta_{3}}\left(D\left|\left|p\right|\right|_{\infty}^{(2)}+\beta_{0}-\beta_{1}\right)\left|\left|\bm{x}^{*}-\bm{x}^{(t)}\right|\right|_{2}$
$\displaystyle\leq\frac{4D\left|\left|p\right|\right|_{\infty}^{(2)}}{\beta_{3}}\left|\left|\bm{x}^{*}-\bm{x}^{(t)}\right|\right|_{2},$

where we leverage condition (A7) again in (i). In addition, to obtain
inequalities (ii) and (iii), we recall from the proof of (d) for Lemma C.1
that $M(\bm{x})=\nabla\left[V_{d}(\bm{x})^{T}\nabla
p(\bm{x})\right]^{T}=V_{d}(\bm{x})\Lambda_{0}(\bm{x})+\sum_{i=1}^{d}T_{i}(\bm{x})V_{d}(\bm{x})\Lambda_{i}(\bm{x})$,
in which the singular values of $V_{d}(\bm{x})\Lambda_{0}(\bm{x})$ is bounded
by $D\left|\left|p\right|\right|_{\infty}^{(2)}$ and the singular values of
$\sum_{i=1}^{d}T_{i}(\bm{x})V_{d}(\bm{x})\Lambda_{i}(\bm{x})$ is bounded by
$\beta_{0}-\beta_{1}\leq D\left|\left|p\right|\right|_{\infty}^{(2)}$. The
result thus follows.

(b) This part of the proof is analogous to our arguments in (b) of Lemma E.2,
except that the SCGA sequence $\big{\\{}\bm{x}^{(t)}\big{\\}}_{t=0}^{\infty}$
is no longer self-contracted. For the completeness, we still repeat some
arguments and highlight the differences here. By Davis-Kahan theorem (Lemma
D.1 and (60) here) and conditions (A1-2), we have that for all $s\geq t$,

$\displaystyle\left|\left|V_{d}(\bm{x}^{(s)})V_{d}(\bm{x}^{(s)})^{T}-V_{d}(\bm{x}^{(t)})V_{d}(\bm{x}^{(t)})^{T}\right|\right|_{2}$
$\displaystyle\leq\frac{\sqrt{2}D\left|\left|\nabla\nabla
p(\bm{x}^{(s)})-\nabla\nabla p(\bm{x}^{(t)})\right|\right|_{2}}{\beta_{0}}$
$\displaystyle\leq\frac{\sqrt{2}D\left|\left|\nabla^{3}p(\bm{x}^{(t)})\right|\right|_{2}\left|\left|\bm{x}^{(s)}-\bm{x}^{(t)}\right|\right|_{2}}{\beta_{0}}+\frac{\sqrt{2}D^{3}\left|\left|p\right|\right|_{\infty}^{(4)}}{\beta_{0}}\left|\left|\bm{x}^{(s)}-\bm{x}^{(t)}\right|\right|_{2}^{2}$
$\displaystyle\stackrel{{\scriptstyle\text{(ii)}}}{{\leq}}\frac{4\sqrt{2}D^{2}\left|\left|p\right|\right|_{\infty}^{(2)}\left|\left|\nabla^{3}p(\bm{x}^{(t)})\right|\right|_{2}\left|\left|\bm{x}^{*}-\bm{x}^{(t)}\right|\right|_{2}}{\beta_{0}\beta_{3}}+\frac{16\sqrt{2}D^{5}\left|\left|p\right|\right|_{\infty}^{(4)}\left(\left|\left|p\right|\right|_{\infty}^{(2)}\right)^{2}}{\beta_{0}\beta_{3}^{2}}\left|\left|\bm{x}^{(t)}-\bm{x}^{*}\right|\right|_{2}^{2}$
$\displaystyle\stackrel{{\scriptstyle\text{(ii)}}}{{\leq}}\frac{8D^{\frac{7}{2}}\left|\left|p\right|\right|_{\infty}^{(2)}\left|\left|\nabla^{3}p(\bm{x}^{(t)})\right|\right|_{\max}\left|\left|\bm{x}^{*}-\bm{x}^{(t)}\right|\right|_{2}}{\beta_{0}\beta_{3}},$

where we possibly shrink the radius $r_{6}>0$ so that
$\left|\left|\bm{x}^{(t)}-\bm{x}^{*}\right|\right|_{2}\leq\frac{(\sqrt{2}-1)\beta_{3}\left|\left|\nabla^{3}p(\bm{x}^{(t)})\right|\right|_{\max}}{4D^{\frac{3}{2}}\left|\left|p\right|\right|_{\infty}^{(2)}\left|\left|p\right|\right|_{\infty}^{(4)}}$
to obtain inequality (ii). Notice also that, since
$\left|\left|\bm{x}^{(s)}-\bm{x}^{(t)}\right|\right|_{2}\leq\left|\left|\bm{x}^{*}-\bm{x}^{(t)}\right|\right|_{2}$
may not hold without the self-contractedness property, we use a looser bound

$\left|\left|\bm{x}^{(s)}-\bm{x}^{(t)}\right|\right|_{2}\leq\sum_{s=t}^{\infty}\left|\left|\bm{x}^{(s+1)}-\bm{x}^{(s)}\right|\right|_{2}\leq\frac{4D\left|\left|p\right|\right|_{\infty}^{(2)}}{\beta_{3}}\left|\left|\bm{x}^{(t)}-\bm{x}^{*}\right|\right|_{2}$

from (a) to derive inequality (i). Therefore, by (65) and the fact that

$\left|\left|\eta V_{d}(\bm{x}^{(s)})V_{d}(\bm{x}^{(s)})^{T}\nabla
p(\bm{x}^{(s)})\right|\right|_{2}=\left|\left|\bm{x}^{(s+1)}-\bm{x}^{(s)}\right|\right|_{2},$

we obtain that

$\displaystyle\left|\left|U_{d}^{\perp}(\bm{x}^{(t)})\left(\bm{x}^{*}-\bm{x}^{(t)}\right)\right|\right|_{2}$
$\displaystyle\leq\sup_{s\geq
t}\left|\left|V_{d}(\bm{x}^{(s)})V_{d}(\bm{x}^{(s)})^{T}-V_{d}(\bm{x}^{(t)})V_{d}(\bm{x}^{(t)})^{T}\right|\right|_{2}\cdot\sum_{s=t}^{\infty}\left|\left|\eta
V_{d}(\bm{x}^{(s)})V_{d}(\bm{x}^{(s)})^{T}\nabla
p(\bm{x}^{(s)})\right|\right|_{2}$
$\displaystyle\leq\frac{8D^{\frac{7}{2}}\left|\left|p\right|\right|_{\infty}^{(2)}\left|\left|\nabla^{3}p(\bm{x}^{(t)})\right|\right|_{\max}\left|\left|\bm{x}^{(s)}-\bm{x}^{(t)}\right|\right|_{2}}{\beta_{0}\beta_{3}}\cdot\frac{4D\left|\left|p\right|\right|_{\infty}^{(2)}}{\beta_{3}}\left|\left|\bm{x}^{(t)}-\bm{x}^{*}\right|\right|_{2}$
$\displaystyle=\frac{32D^{\frac{9}{2}}\left(\left|\left|p\right|\right|_{\infty}^{(2)}\right)^{2}\left|\left|\nabla^{3}p(\bm{x}^{(t)})\right|\right|_{\max}\left|\left|\bm{x}^{*}-\bm{x}^{(t)}\right|\right|_{2}^{2}}{\beta_{0}\beta_{3}^{2}},$

which implies the second bound in condition (A4) with
$\beta_{2}=\frac{32D^{\frac{9}{2}}\left(\left|\left|p\right|\right|_{\infty}^{(2)}\right)^{2}\left|\left|p\right|\right|_{\infty}^{(3)}}{\beta_{0}\beta_{3}^{2}}$.
Finally,

$\displaystyle\nabla
p(\bm{x}^{(t)})^{T}U_{d}^{\perp}(\bm{x}^{(t)})(\bm{x}^{*}-\bm{x}^{(t)})$
$\displaystyle\leq\left|\left|U_{d}^{\perp}(\bm{x}^{(t)})\nabla
p(\bm{x}^{(t)})\right|\right|_{2}\left|\left|U_{d}^{\perp}(\bm{x}^{(t)})\left(\bm{x}^{*}-\bm{x}^{(t)}\right)\right|\right|_{2}$
$\displaystyle\leq\frac{32D^{\frac{9}{2}}\left(\left|\left|p\right|\right|_{\infty}^{(2)}\right)^{2}\left|\left|U_{d}^{\perp}(\bm{x}^{(t)})\nabla
p(\bm{x}^{(t)})\right|\right|_{2}\left|\left|\nabla^{3}p(\bm{x}^{(t)})\right|\right|_{\max}\left|\left|\bm{x}^{*}-\bm{x}^{(t)}\right|\right|_{2}^{2}}{\beta_{0}\beta_{3}^{2}}.$

The results follow. ∎

The results in (b) of Lemma E.4 also imply condition (A4) with
$\beta_{2}=\frac{32D^{\frac{9}{2}}\left(\left|\left|p\right|\right|_{\infty}^{(2)}\right)^{2}\left|\left|p\right|\right|_{\infty}^{(3)}}{\beta_{0}\beta_{3}^{2}}$
whenever

$\frac{32D^{\frac{9}{2}}\left(\left|\left|p\right|\right|_{\infty}^{(2)}\right)^{2}\left|\left|U_{d}^{\perp}(\bm{x}^{(t)})\nabla
p(\bm{x}^{(t)})\right|\right|_{2}\left|\left|\nabla^{3}p(\bm{x}^{(t)})\right|\right|_{\max}}{\beta_{3}^{2}}\leq\frac{\beta_{0}^{2}}{4}.$
(67)

Once again, the choice of $\beta_{2}$ is feasible under condition (A1) and the
upper bound (67) can be viewed as a variant of the first inequality in
condition (A3). From this perspective, the subspace constrained Polyak-
Łojasiewicz inequality (A7) also leads to an alternative assumptions for
condition (A4) and the linear convergence of the SCGA algorithm.

######  Remark E.1.

Note that the results in Proposition E.4 can be generalized to the directional
or arbitrary manifold cases under conditions (A1-3). First, the subspace
constrained Polyak-Łojasiewicz inequality for the SCGA sequence
$\big{\\{}\underline{\bm{x}}^{(t)}\big{\\}}_{t=0}^{\infty}$ on $\Omega_{q}$ or
an arbitrary manifold can be modified as:

$\frac{1}{2}\left|\left|\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right|\right|_{2}^{2}\geq\underline{\beta}_{3}\left[f(\underline{\bm{x}}^{*})-f(\underline{\bm{x}}^{(t)})\right]\quad\text{
for some }\underline{\beta}_{3}>0\text{ and any }t\geq 0,$

where $f$ is the objective (density) function. Based on the proof of (a) in
Proposition 4.4 and our arguments in (a) of Lemma E.4, it follows that the
total length of the SCGA trajectory on $\Omega_{q}$ or an arbitrary manifold
is of the linear order, _i.e._ ,

$\sum_{s=t}^{\infty}d_{g}\left(\underline{\bm{x}}^{(s+1)},\underline{\bm{x}}^{(s)}\right)\leq\frac{4q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}}{\underline{\beta}_{3}}\cdot
d_{g}\left(\underline{\bm{x}}^{(t)},\underline{\bm{x}}^{*}\right)\quad\text{
for any }t\geq 0.$

Second, to establish the quadratic bounds for
$\left\langle\underline{U}_{d}^{\perp}(\underline{\bm{x}}^{(t)})\mathtt{grad}\,f(\underline{\bm{x}}^{(t)}),\,\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})\right\rangle$
and
$\left|\left|\underline{U}_{d}^{\perp}(\underline{\bm{x}}^{(t)})\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})\right|\right|_{2}$,
one can follow the arguments in the proof of (b) in Lemma E.4 and leverage the
two facts:

1\. The tangent vector
$\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})$ can be
decomposed into an infinite sum of SCGA updates (44) on $\Omega_{q}$ or an
arbitrary manifold as:

$\displaystyle\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})$
$\displaystyle=\sum_{s=t}^{\infty}\Gamma_{\underline{\bm{x}}^{(s)}}^{\underline{\bm{x}}^{(t)}}\left(\mathtt{Exp}_{\underline{\bm{x}}^{(s)}}^{-1}(\underline{\bm{x}}^{(s+1)})\right).$

See Figure 12 for a graphical illustration. This equation is valid because
parallel transports preserve inner products and are linear.

Figure 12: Decomposition of the vector
$\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})$ within
the tangent space $T_{\underline{\bm{x}}^{(t)}}$ into the summation
$\sum\limits_{s=t}^{\infty}\Gamma_{\underline{\bm{x}}^{(s)}}^{\underline{\bm{x}}^{(t)}}\left(\mathtt{Exp}_{\underline{\bm{x}}^{(s)}}^{-1}(\underline{\bm{x}}^{(s+1)})\right)$
of parallel transported SCGA iterative vectors. Here, the blue curves on
$\Omega_{q}$ are iterative paths of the SCGA algorithm, while the green
vectors are tangent vectors
$\mathtt{Exp}_{\underline{\bm{x}}^{(s)}}^{-1}(\underline{\bm{x}}^{(s+1)})\in
T_{\underline{\bm{x}}^{(s)}}$ after being parallel transported to
$T_{\underline{\bm{x}}^{(t)}}$.

2\. Under conditions (A1-2), we know that

$\displaystyle\left|\left|\underline{U}_{d}^{\perp}(\underline{\bm{x}}^{(t)})\cdot\sum_{s=t}^{\infty}\Gamma_{\underline{\bm{x}}^{(s)}}^{\underline{\bm{x}}^{(t)}}\left(\mathtt{Exp}_{\underline{\bm{x}}^{(s)}}^{-1}(\underline{\bm{x}}^{(s+1)})\right)\right|\right|_{2}$
$\displaystyle=\Bigg{\|}\sum_{s=t}^{\infty}\underline{U}_{d}^{\perp}(\underline{\bm{x}}^{(t)})\bigg{[}\Gamma_{\underline{\bm{x}}^{(s)}}^{\underline{\bm{x}}^{(t)}}\left(\underline{\eta}\underline{V}_{d}(\underline{\bm{x}}^{(s)})\underline{V}_{d}(\underline{\bm{x}}^{(s)})^{T}\underline{V}_{d}(\underline{\bm{x}}^{(s)})\underline{V}_{d}(\underline{\bm{x}}^{(s)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(s)})\right)$
$\displaystyle\hskip
56.9055pt-\underline{\eta}\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\underline{V}_{d}(\underline{\bm{x}}^{(s)})\underline{V}_{d}(\underline{\bm{x}}^{(s)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(s)})\bigg{]}\Bigg{\|}_{2}$
$\displaystyle\leq\sum_{s=t}^{\infty}\widetilde{A}\left|\left|\underline{V}_{d}(\underline{\bm{x}}^{(s)})\underline{V}_{d}(\underline{\bm{x}}^{(s)})^{T}-\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\right|\right|_{2}\cdot\left|\left|\underline{\bm{x}}^{(s)}-\underline{\bm{x}}^{(t)}\right|\right|_{2}$
$\displaystyle\leq\widetilde{A}\left|\left|\underline{\bm{x}}^{*}-\bm{x}^{(t)}\right|\right|_{2}\cdot\sum_{s=t}^{\infty}\left|\left|\underline{\bm{x}}^{(s)}-\underline{\bm{x}}^{(t)}\right|\right|_{2}$
$\displaystyle=O\left(\left|\left|\underline{\bm{x}}^{(s)}-\underline{\bm{x}}^{(t)}\right|\right|_{2}^{2}\right)$

for some constant $\underline{A}>0$, where we leverage the fact that the
vector field

$X(\gamma(t))=\underline{V}_{d}(\gamma(t))\underline{V}_{d}(\gamma(t))^{T}\underline{V}_{d}(\underline{\bm{x}}^{(s)})\underline{V}_{d}(\underline{\bm{x}}^{(s)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(s)})$

with $\gamma(0)=\underline{\bm{x}}^{(s)}$ and
$\gamma(1)=\underline{\bm{x}}^{(t)}$ has its variation
$\left|\left|X(\gamma(t_{1}))-X(\gamma(t_{2}))\right|\right|_{2}$ bounded by

$\left|\left|\underline{V}_{d}(\underline{\bm{x}}^{(s)})\underline{V}_{d}(\underline{\bm{x}}^{(s)})^{T}-\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\right|\right|_{2}=O\left(\left|\left|\underline{\bm{x}}^{(s)}-\underline{\bm{x}}^{(t)}\right|\right|_{2}\right)$

according to the Davis-Kahan theorem for any $0\leq t_{1},t_{2}\leq 1$.
However, we are not sure if the self-contractedness condition can also be
adaptive to the directional or general manifold cases, given that the
arguments in Theorem 15 of Gupta et al. (2021) are based on the Euclidean
geometry.

##  Appendix F Other Technical Concepts of Differential Geometry on
$\Omega_{q}$

$\bullet$ Taylor’s Theorem on $\Omega_{q}$. Given a smooth function $f$ on
$\Omega_{q}$, its Taylor’s expansion is often written as (Pennec, 2006):

$f(\mathtt{Exp}_{\bm{x}}(\bm{v}))=f(\bm{x})+\left\langle\mathtt{grad}\,f(\bm{x}),\bm{v}\right\rangle+\frac{1}{2}\bm{v}^{T}\mathcal{H}f(\bm{x})\bm{v}+o\left(\left|\left|\bm{v}\right|\right|_{2}^{2}\right)$
(68)

for any $\bm{v}\in T_{\bm{x}}$, where
$\mathtt{Exp}_{\bm{x}}:T_{\bm{x}}\to\Omega_{q}$ is the _exponential map_ at
$\bm{x}\in\Omega_{q}$. One may replace the exponential map with a more general
concept called the _retractions_ on an arbitrary manifold; see Section 4.1 and
Proposition 5.5.5 in Absil et al. (2008).

$\bullet$ Parallel Transport. When comparing vectors in two different tangent
spaces $T_{\bm{x}},T_{\bm{y}}$ on $\Omega_{q}$, we leverage the notion of
_parallel transport_ $\Gamma_{\bm{x}}^{\bm{y}}:T_{\bm{x}}\to T_{\bm{y}}$ to
transport vectors from one tangent space to another along a geodesic. In
addition, $\Gamma_{\bm{x}}^{\bm{y}}(\bm{v})$ is a tangent vector in
$T_{\bm{y}}$ after being parallel transported from $\bm{v}\in T_{\bm{x}}$
along a geodesic (or great circle) on $\Omega_{q}$. The parallel transport
mapping $\Gamma_{\bm{x}}^{\bm{y}}$ is a linear isometry along any smooth curve
on $\Omega_{q}$, _i.e._ ,
$\left\langle\Gamma_{\bm{x}}^{\bm{y}}(\bm{u}),\Gamma_{\bm{x}}^{\bm{y}}(\bm{v})\right\rangle=\langle\bm{u},\bm{v}\rangle$
for any $\bm{u},\bm{v}\in T_{\bm{x}}$; see Proposition 5.5 in Lee (2018) or
Proposition 1 in Section 4-4 of do Carmo (2016).

$\bullet$ Sectional Curvature. _Sectional curvature_ is the Gaussian curvature
of a two-dimensional submanifold formed as the image of a two-dimensional
subspace of a tangent space after exponential mapping; see Section 3-2 in do
Carmo (2016) for detailed discussions about the Gaussian curvature. It is
known that a two dimensional submanifold with positive, zero, or negative
sectional curvature is locally isometric to a two dimensional sphere, a
Euclidean plane, or a hyperbolic plane with the same Gaussian curvature (Zhang
and Sra, 2016).

$\bullet$ Geodesically Strong Concavity. A function
$f:\Omega_{q}\to\mathbb{R}$ is said to be _geodesically concave_ if for any
$\bm{x},\bm{y}\in\Omega_{q}$, it holds that

$f(\varphi(t))\geq(1-t)f(\bm{x})+f(\bm{y})$

for any $t\in[0,1]$, where $\varphi:[0,1]\to\Omega_{q}$ is a geodesic with
$\varphi(0)=\bm{x}$ and $\varphi(1)=\bm{y}$. When $f$ is differentiable, an
equivalent statement of the geodesic concavity is that (Theorem 11.17 in
Boumal 2020):

$f(\bm{y})-f(\bm{x})\leq\left\langle\mathtt{grad}\,f(\bm{x}),\mathtt{Exp}_{\bm{x}}^{-1}(\bm{y})\right\rangle.$

A function $f:\Omega_{q}\to\mathbb{R}$ is said to be _geodesically
$\mu_{g}$-strongly concave_ if for any $\bm{x},\bm{y}\in\Omega_{q}$, it holds
that

$f(\bm{y})\leq
f(\bm{x})+\left\langle\mathtt{grad}\,f(\bm{x}),\mathtt{Exp}_{\bm{x}}^{-1}(\bm{y})\right\rangle-\frac{\mu_{g}}{2}\cdot
d_{g}(\bm{x},\bm{y})^{2}.$

##  Appendix G Normal Space of Directional Density Ridge

Recall that we extend the directional density $f$ from its support
$\Omega_{q}$ to $\mathbb{R}^{q+1}\setminus\left\\{\bm{0}\right\\}$ by defining
$f(\bm{x})\equiv
f\left(\frac{\bm{x}}{\left|\left|\bm{x}\right|\right|_{2}}\right)$ for all
$\bm{x}\in\mathbb{R}^{q+1}\setminus\left\\{\bm{0}\right\\}$. As we will refer
to conditions (A1-3) frequently in the next three sections, we restate them
here:

  * •

(A1) (_Differentiability_) Under the extension (27) of the directional density
$f$, we assume that the total gradient $\nabla f(\bm{x})$, total Hessian
matrix $\nabla\nabla f(\bm{x})$, and third-order derivative tensor
$\nabla^{3}f(\bm{x})$ in $\mathbb{R}^{q+1}$ exist, and are continuous on
$\mathbb{R}^{q+1}\setminus\\{\bm{0}\\}$ and square integrable on $\Omega_{q}$.
We also assume that $f$ has bounded fourth order derivatives on $\Omega_{q}$.

  * •

(A2) (_Eigengap_) We assume that there exist constants $\underline{\rho}>0$
and $\underline{\beta}_{0}>0$ such that
$\underline{\lambda}_{d+1}(\bm{y})\leq-\underline{\beta}_{0}$ and
$\underline{\lambda}_{d}(\bm{y})-\underline{\lambda}_{d+1}(\bm{y})\geq\underline{\beta}_{0}$
for any
$\bm{y}\in\left(\underline{R}_{d}\oplus\underline{\rho}\right)\cap\Omega_{q}$.

  * •

(A3) (_Path Smoothness_) Under the same
$\underline{\rho},\underline{\beta}_{0}>0$ in (A2), we assume that there
exists another constant
$\underline{\beta}_{1}\in\left(0,\underline{\beta}_{0}\right)$ such that

$\displaystyle\sqrt{2}\cdot
q^{\frac{3}{2}}\left|\left|\underline{U}_{d}^{\perp}(\bm{y})\mathtt{grad}\,f(\bm{y})\right|\right|_{2}\left|\left|\nabla^{3}f(\bm{y})\right|\right|_{\max}$
$\displaystyle\leq\frac{\underline{\beta}_{0}^{2}}{2},$ $\displaystyle d\cdot
q^{\frac{3}{2}}\left|\left|\nabla
f(\bm{x})\right|\right|_{2}\cdot\left|\left|\nabla^{3}f(\bm{x})\right|\right|_{\max}$
$\displaystyle\leq\underline{\beta}_{0}\left(\underline{\beta}_{0}-\underline{\beta}_{1}\right)$

for all
$\bm{y}\in\left(\underline{R}_{d}\oplus\underline{\rho}\right)\cap\Omega_{q}$
and $\bm{x}\in\underline{R}_{d}$.

Recall that an order-$d$ density ridge of a directional density $f$ on
$\Omega_{q}=\left\\{\bm{x}\in\mathbb{R}^{q+1}:\left|\left|\bm{x}\right|\right|_{2}=1\right\\}$
is the set of points defined as:

$\underline{R}_{d}=\left\\{\bm{x}\in\Omega_{q}:\underline{G}_{d}(\bm{x})=\bm{0},\underline{\lambda}_{d+1}(\bm{x})<0\right\\}=\left\\{\bm{x}\in\Omega_{q}:\underline{V}_{d}(\bm{x})^{T}\mathtt{grad}\,f(\bm{x})=\bm{0},\underline{\lambda}_{d+1}(\bm{x})<0\right\\}.$
(69)

Lemma G.1 below shows that under conditions (A1-3), the Jacobian matrices
$\nabla\left[\underline{V}_{d}(\bm{x})^{T}\mathtt{grad}\,f(\bm{x})\right]\in\mathbb{R}^{(q-d)\times(q+1)}$
and
$\left(\bm{I}_{q+1}-\bm{x}\bm{x}^{T}\right)\nabla\left[\underline{V}_{d}(\bm{x})^{T}\mathtt{grad}\,f(\bm{x})\right]^{T}\in\mathbb{R}^{(q+1)\times(q-d)}$
(_i.e._ , projecting the columns of
$\nabla\left[\underline{V}_{d}(\bm{x})^{T}\mathtt{grad}\,f(\bm{x})\right]^{T}$
onto the tangent space $T_{\bm{x}}$) both have rank $q-d$ at every point on
$\underline{R}_{d}$, and $\underline{R}_{d}$ will be a $d$-dimensional
submanifold on $\Omega_{q}$ by the implicit function theorem (Rudin, 1976;
Lee, 2012). Analogous to the discussion about the normal space of a Euclidean
density ridge in Appendix C, we define

$\displaystyle\underline{M}(\bm{x})=\nabla\left[\underline{V}_{d}(\bm{x})^{T}\mathtt{grad}\,f(\bm{x})\right]^{T}$
$\displaystyle=\nabla\left[\underline{V}_{d}(\bm{x})^{T}\nabla
f(\bm{x})\right]^{T}$
$\displaystyle=\left(\underline{\bm{m}}_{d+1}(\bm{x}),...,\underline{\bm{m}}_{q}(\bm{x})\right)\in\mathbb{R}^{(q+1)\times(q-d)}.$

Different from the Euclidean density ridge case, it is the column space of

$\underline{M}_{E}(\bm{x})=\left(\nabla\left[\underline{V}_{d}(\bm{x})^{T}\nabla
f(\bm{x})\right]^{T},\bm{x}\right)=\left(\underline{\bm{m}}_{d+1}(\bm{x}),...,\underline{\bm{m}}_{q}(\bm{x}),\bm{x}\right)\in\mathbb{R}^{(q+1)\times(q+1-d)}$
(70)

that spans the normal space of $\underline{R}_{d}$ within the ambient space
$\mathbb{R}^{q+1}$. It can be seen from our Remark 4.1 that the rows of

$\nabla\Psi(\bm{x})=\begin{pmatrix}\nabla\left[\underline{\bm{v}}_{d+1}(\bm{x})^{T}\nabla
f(\bm{x})\right]\\\ \vdots\\\
\nabla\left[\underline{\bm{v}}_{q}(\bm{x})^{T}\nabla f(\bm{x})\right]\\\
2\bm{x}\end{pmatrix}$

spans the normal space of the solution manifold $\underline{R}_{d}$; see also
Lemma 1 in Chen (2020). Consequently, the column space of
$\left(\bm{I}_{q+1}-\bm{x}\bm{x}^{T}\right)\underline{M}(\bm{x})=\left(\bm{I}_{q+1}-\bm{x}\bm{x}^{T}\right)\nabla\left[\underline{V}_{d}(\bm{x})^{T}\mathtt{grad}\,f(\bm{x})\right]^{T}$
spans the normal space of $\underline{R}_{d}$ within the tangent space
$T_{\bm{x}}$ at each $\bm{x}\in\underline{R}_{d}\subset\Omega_{q}$. The
technique in pages 60-63 of Eberly (1996) is still valid to argue that

$\displaystyle\begin{split}&\underline{\bm{m}}_{k}(\bm{x})\\\
&=\left[\underline{\lambda}_{k}(\bm{x})\bm{I}_{q+1}+\sum_{i=1}^{d}\frac{\underline{\bm{v}}_{i}(\bm{x})^{T}\nabla
f(\bm{x})}{\underline{\lambda}_{k}(\bm{x})-\underline{\lambda}_{i}(\bm{x})}\cdot\underline{\bm{v}}_{i}(\bm{x})^{T}\nabla^{3}f(\bm{x})+\frac{\bm{x}^{T}\nabla
f(\bm{x})}{\underline{\lambda}_{k}(\bm{x})}\cdot\bm{x}^{T}\nabla^{3}f(\bm{x})\right]\underline{\bm{v}}_{k}(\bm{x})\\\
&=\left[\underline{\lambda}_{k}(\bm{x})\bm{I}_{q+1}+\sum_{i=1}^{d}\frac{\underline{\bm{v}}_{i}(\bm{x})^{T}\nabla
f(\bm{x})}{\underline{\lambda}_{k}(\bm{x})-\underline{\lambda}_{i}(\bm{x})}\cdot\underline{\bm{v}}_{i}(\bm{x})^{T}\nabla^{3}f(\bm{x})\right]\underline{\bm{v}}_{k}(\bm{x})\end{split}$
(71)

for $k=d+1,...,q$, where we use the fact that $\bm{x}^{T}\nabla
f(\bm{x})=\bm{x}^{T}\mathtt{grad}\,f(\bm{x})=0$ on $\Omega_{q}$ under the
extension of $f$ as in (A1). Let

$\displaystyle\underline{\Lambda}_{0}(\bm{x})$
$\displaystyle=\mathtt{Diag}\left[\underline{\lambda}_{d+1}(\bm{x}),...,\underline{\lambda}_{q}(\bm{x})\right],$
$\displaystyle\underline{\Lambda}_{i}(\bm{x})$
$\displaystyle=\mathtt{Diag}\left[\frac{1}{\underline{\lambda}_{d+1}(\bm{x})-\underline{\lambda}_{i}(\bm{x})},...,\frac{1}{\underline{\lambda}_{q}(\bm{x})-\underline{\lambda}_{i}(\bm{x})}\right],$
$\displaystyle\underline{T}_{i}(\bm{x})$
$\displaystyle=\left[\underline{\bm{v}}_{i}(\bm{x})^{T}\nabla
f(\bm{x})\right]\cdot\underline{\bm{v}}_{i}(\bm{x})^{T}\nabla^{3}f(\bm{x})$

for $i=1,...,d$. Then,

$\underline{M}(\bm{x})=\underline{V}_{d}(\bm{x})\underline{\Lambda}_{0}(\bm{x})+\sum_{i=1}^{d}\underline{T}_{i}(\bm{x})\underline{V}_{d}(\bm{x})\underline{\Lambda}_{i}(\bm{x}).$
(72)

As in the Euclidean data case, the columns of
$\underline{M}_{E}(\bm{x})=\left[\underline{M}(\bm{x}),\bm{x}\right]\in\mathbb{R}^{(q+1)\times(q+1-d)}$
are not orthonormal, and we again leverage the orthonormalization technique in
Chen et al. (2015) to construct $\underline{N}(\bm{x})$ that shares the same
column space with $\underline{M}_{E}(\bm{x})$ but has orthonormal columns.
That is, under the condition that $\underline{M}_{E}(\bm{x})$ has full column
rank $q-d$ at every point $\bm{x}\in\underline{R}_{d}$ (see Lemma G.1),

$\underline{N}(\bm{x})=\underline{M}_{E}(\bm{x})\left[\underline{J}(\bm{x})^{T}\right]^{-1}$
(73)

with the Cholesky decomposition
$\underline{M}_{E}(\bm{x})^{T}\underline{M}_{E}(\bm{x})=\underline{J}(\bm{x})\underline{J}(\bm{x})^{T}$,
where $\underline{J}(\bm{x})\in\mathbb{R}^{(q+1-d)\times(q+1-d)}$ is a lower
triangular matrix whose diagonal elements are positive. Finally, the non-
uniqueness of $\underline{M}_{E}(\bm{x})$ will not affect our subsequent
discussions about the properties of directional density ridges.

######  Lemma G.1.

Assume conditions (A1-3). Given that $\underline{M}(\bm{x})$,
$\underline{M}_{E}(\bm{x})=\left[\underline{M}(\bm{x}),\bm{x}\right]$, and
$\underline{N}(\bm{x})$ are defined in (72) and (73), we have the following
properties:

  1. (a)

$\underline{M}_{E}(\bm{x})$ and $\underline{N}(\bm{x})$ have the same column
space. In addition,

$\underline{N}(\bm{x})\underline{N}(\bm{x})^{T}=\underline{M}_{E}(\bm{x})\left[\underline{M}_{E}(\bm{x})^{T}\underline{M}_{E}(\bm{x})\right]^{-1}\underline{M}_{E}(\bm{x})^{T}.$

That is, $\underline{N}(\bm{x})\underline{N}(\bm{x})^{T}$ is the projection
matrix onto the columns of $\underline{M}_{E}(\bm{x})$.

  2. (b)

The columns of $\underline{N}(\bm{x})$ are orthonormal to each other.

  3. (c)

For $\bm{x}\in\underline{R}_{d}$, the column space of $\underline{N}(\bm{x})$
is normal to the (tangent) direction of $\underline{R}_{d}$ at $\bm{x}$.

  4. (d)

For $\bm{x}\in\underline{R}_{d}$, the smallest eigenvalue
$\lambda_{\min}(\underline{M}(\bm{x})^{T}\underline{M}(\bm{x}))=\lambda_{\min}(\underline{M}(\bm{x})^{T}(\bm{I}_{q+1}-\bm{x}\bm{x}^{T})\underline{M}(\bm{x}))\geq\underline{\beta}_{1}^{2}>0$,
and

$\mathtt{rank}(\underline{M}(\bm{x}))=\mathtt{rank}\left((\bm{I}_{q+1}-\bm{x}\bm{x}^{T})\underline{M}(\bm{x})\right)=q-d.$

Moreover, all the nonzero singular values of $\underline{M}_{E}(\bm{x})$ are
greater than $\min\left\\{\underline{\beta}_{1},1\right\\}>0$, and

$\mathtt{rank}(\underline{N}(\bm{x}))=\mathtt{rank}(\underline{M}_{E}(\bm{x}))=q+1-d.$

Therefore, $\underline{R}_{d}$ is a $d$-dimensional submanifold that contains
neither intersections and nor endpoints on $\Omega_{q}$. Namely,
$\underline{R}_{d}$ is a finite union of connected and compact submanifolds on
$\Omega_{q}$.

  5. (e)

For all $\bm{x}\in\underline{R}_{d}$,

$\left|\left|\left[\underline{M}(\bm{x})^{T}\left(\bm{I}_{q+1}-\bm{x}\bm{x}^{T}\right)\underline{M}(\bm{x})\right]^{-1}\right|\right|_{2}\leq\frac{1}{\underline{\beta}_{1}^{2}}\quad\text{
and
}\quad\left|\left|\left[\underline{J}(\bm{x})^{T}\right]^{-1}\right|\right|_{2}\leq\max\left\\{\frac{1}{\underline{\beta}_{1}},1\right\\}.$

  6. (f)

When $\left|\left|\bm{x}-\bm{y}\right|\right|_{2}$ is sufficiently small and
$\bm{x},\bm{y}\in\left(\underline{R}_{d}\oplus\underline{\rho}\right)\cap\Omega_{q}$,

$\left|\left|\underline{N}(\bm{x})\underline{N}(\bm{x})^{T}-\underline{N}(\bm{y})\underline{N}(\bm{y})^{T}\right|\right|_{\max}\leq\underline{A}_{0}\left(\left|\left|f\right|\right|_{\infty}^{(3)}+\left|\left|f\right|\right|_{\infty}^{(4)}\right)^{2}\left|\left|\bm{x}-\bm{y}\right|\right|_{2}$

for some constant $\underline{A}_{0}>0$.

  7. (g)

Assume that another directional density function $g$ also satisfies conditions
(A1-3) after the extension $g(\bm{x})\equiv
g\left(\frac{\bm{x}}{\left|\left|\bm{x}\right|\right|}\right)$ in
$\mathbb{R}^{q+1}\setminus\\{\bm{0}\\}$, and
$\left|\left|f-g\right|\right|_{\infty,3}^{*}$ is sufficiently small. Then,

$\left|\left|\underline{N}_{f}(\bm{x})\underline{N}_{f}(\bm{x})^{T}-\underline{N}_{g}(\bm{x})\underline{N}_{g}(\bm{x})^{T}\right|\right|_{\max}\leq\underline{A}_{1}\cdot\left|\left|f-g\right|\right|_{\infty,3}^{*}$

for some constant $\underline{A}_{1}>0$ and any $\bm{x}\in\underline{R}_{d}$,
where $\underline{N}_{f}(\bm{x})$ is the matrix defined in (73) with
directional density $f$.

  8. (h)

The reach of $\underline{R}_{d}$ satisfies

$\mathtt{reach}(\underline{R}_{d})\geq\min\left\\{\underline{\rho}/2,\frac{\min\left\\{\underline{\beta}_{1},1\right\\}^{2}}{\underline{A}_{2}\left(\left|\left|f\right|\right|_{\infty}^{(3)}+\left|\left|f\right|\right|_{\infty}^{(4)}\right)}\right\\}$

for some constant $\underline{A}_{2}>0$.

This lemma is a direct extension of Lemma C.1 to the directional data
scenario; thus, its proof is similar to the proof of Lemma C.1.

###### Proof of Lemma G.1.

The proofs of properties (a), (b), and (c) can be inherited from the
corresponding ones in Lemma C.1 with mild modifications and we thus omit them.

(d) We will prove that the $(q-d)$ nonzero singular values of
$\underline{M}(\bm{x})$ and
$\left(\bm{I}_{q+1}-\bm{x}\bm{x}^{T}\right)\underline{M}(\bm{x})\in\mathbb{R}^{(q+1)\times(q-d)}$
are bounded away from 0. Recall that

$\underline{M}(\bm{x})=\underline{V}_{d}(\bm{x})\underline{\Lambda}_{0}(\bm{x})+\sum_{i=1}^{d}\underline{T}_{i}(\bm{x})\underline{V}_{d}(\bm{x})\underline{\Lambda}_{i}(\bm{x})$

with

$\displaystyle\underline{\Lambda}_{0}(\bm{x})$
$\displaystyle=\mathtt{Diag}\left[\underline{\lambda}_{d+1}(\bm{x}),...,\underline{\lambda}_{q}(\bm{x})\right]$
$\displaystyle\underline{\Lambda}_{i}(\bm{x})$
$\displaystyle=\mathtt{Diag}\left[\frac{1}{\underline{\lambda}_{d+1}(\bm{x})-\underline{\lambda}_{i}(\bm{x})},...,\frac{1}{\underline{\lambda}_{q}(\bm{x})-\underline{\lambda}_{i}(\bm{x})}\right]$
$\displaystyle\underline{T}_{i}(\bm{x})$
$\displaystyle=\left[\underline{\bm{v}}_{i}(\bm{x})^{T}\nabla
f(\bm{x})\right]\cdot\underline{\bm{v}}_{i}(\bm{x})^{T}\nabla^{3}f(\bm{x})$

for $i=1,...,d$. Under condition (A2),

$\displaystyle\left|\left|\left(\bm{I}_{q+1}-\bm{x}\bm{x}^{T}\right)\cdot\sum_{i=1}^{d}\underline{T}_{i}(\bm{x})\underline{V}_{d}(\bm{x})\underline{\Lambda}_{i}(\bm{x})\right|\right|_{2}$
$\displaystyle\leq\left|\left|\sum_{i=1}^{d}\underline{T}_{i}(\bm{x})\underline{V}_{d}(\bm{x})\underline{\Lambda}_{i}(\bm{x})\right|\right|_{2}\quad\text{
since }\left|\left|\bm{I}_{q+1}-\bm{x}\bm{x}^{T}\right|\right|_{2}=1$
$\displaystyle\leq\sum_{i=1}^{d}\left|\left|\underline{T}_{i}(\bm{x})\right|\right|_{2}\cdot\left|\left|\underline{V}_{d}(\bm{x})\right|\right|_{2}\cdot\frac{1}{\underline{\beta}_{0}}\quad\text{
by (\text@underline{A2})}$
$\displaystyle\leq\sum_{i=1}^{d}\left|\left|\underline{\bm{v}}_{i}(\bm{x})^{T}\nabla
f(\bm{x})\right|\right|_{2}\cdot\left|\left|\underline{\bm{v}}_{i}(\bm{x})^{T}\nabla^{3}f(\bm{x})\right|\right|_{2}\quad\text{
since }\left|\left|\underline{V}_{d}(\bm{x})\right|\right|_{2}=1$
$\displaystyle\leq\frac{d\left|\left|\nabla f(\bm{x})\right|\right|_{2}\cdot
q^{\frac{3}{2}}\left|\left|\nabla^{3}f(\bm{x})\right|\right|_{\max}}{\underline{\beta}_{0}}$
$\displaystyle\leq\underline{\beta}_{0}-\underline{\beta}_{1}.$

It shows that all the singular values of
$\left(\bm{I}_{q+1}-\bm{x}\bm{x}^{T}\right)\sum\limits_{i=1}^{d}\underline{T}_{i}(\bm{x})\underline{V}_{d}(\bm{x})\underline{\Lambda}_{i}(\bm{x})$
or simply
$\sum\limits_{i=1}^{d}\underline{T}_{i}(\bm{x})\underline{V}_{d}(\bm{x})\underline{\Lambda}_{i}(\bm{x})$
are less than $\underline{\beta}_{0}-\underline{\beta}_{1}$. Moreover, under
condition (A2) again, all the $(q-d)$ singular values of

$\left(\bm{I}_{q+1}-\bm{x}\bm{x}^{T}\right)\underline{V}_{d}(\bm{x})\underline{\Lambda}_{0}(\bm{x})=\underline{V}_{d}(\bm{x})\underline{\Lambda}_{0}(\bm{x})$

are greater than $\underline{\beta}_{1}$.
By Theorem 3.3.16 in Horn and Johnson (1991), we know that all the singular
values of $\underline{M}(\bm{x})$ and
$\left(\bm{I}_{q+1}-\bm{x}\bm{x}^{T}\right)\underline{M}(\bm{x})$ are greater
than

$\sigma_{i}\left(\underline{V}_{d}(\bm{x})\underline{\Lambda}_{0}(\bm{x})\right)-\sigma_{1}\left(\sum_{i=1}^{d}\underline{T}_{i}(\bm{x})\underline{V}_{d}(\bm{x})\underline{\Lambda}_{i}(\bm{x})\right)\geq\underline{\beta}_{0}-(\underline{\beta}_{0}-\underline{\beta}_{1})=\underline{\beta}_{1}>0,$

where $\sigma_{i}(A),i=1,...,q-d$ are singular values of a matrix
$A\in\mathbb{R}^{(q+1)\times(q-d)}$ in their descending order. Therefore, the
minimum eigenvalue of $\underline{M}(\bm{x})^{T}\underline{M}(\bm{x})$
satisfies

$\lambda_{\min}\left(\underline{M}(\bm{x})^{T}\underline{M}(\bm{x})\right)=\lambda_{\min}\left(\underline{M}(\bm{x})^{T}(\bm{I}_{q+1}-\bm{x}\bm{x}^{T})\underline{M}(\bm{x})\right)\geq\underline{\beta}_{1}^{2}>0.$
(74)

Now, given
$\underline{M}_{E}(\bm{x})=\left[\underline{M}(\bm{x}),\bm{x}\right]\in\mathbb{R}^{(q+1)\times(q+1-d)}$
and $\bm{x}\in\Omega_{q}$, we know that

$\underline{M}_{E}(\bm{x})^{T}\underline{M}_{E}(\bm{x})=\begin{pmatrix}\underline{M}(\bm{x})^{T}\underline{M}(\bm{x})&\underline{M}(\bm{x})^{T}\bm{x}\\\
\bm{x}^{T}\underline{M}(\bm{x})&1\end{pmatrix}.$

If we denote the orthonormal eigenvectors of
$\underline{M}(\bm{x})^{T}\underline{M}(\bm{x})$ by
$\bm{v}_{\underline{M},1}(\bm{x}),...,\bm{v}_{\underline{M},q-d}(\bm{x})\in\mathbb{R}^{q-d}$,
then

$\begin{pmatrix}\bm{v}_{\underline{M},1}(\bm{x})\\\
0\end{pmatrix},...,\begin{pmatrix}\bm{v}_{\underline{M},q-d}(\bm{x})\\\
0\end{pmatrix},\begin{pmatrix}\bm{0}\\\ 1\end{pmatrix}\in\mathbb{R}^{q+1-d}$

are the orthonormal eigenvectors of
$\underline{M}_{E}(\bm{x})^{T}\underline{M}_{E}(\bm{x})$, whose eigenvalues
are thus lower bounded by $\min\left\\{\underline{\beta}_{1},1\right\\}$ due
to (74). Hence,
$\mathtt{rank}(\underline{N}(\bm{x}))=\mathtt{rank}(\underline{M}_{E}(\bm{x}))=q+1-d$.
By the implicit function theorem and the extra constraint
$\underline{R}_{d}\subset\Omega_{q}$, $\underline{R}_{d}$ is a $d$-dimensional
submanifold on $\Omega_{q}$. It also implies that $\underline{R}_{d}$ cannot
have intersections, because otherwise the intersected points will violate the
rank condition.
Finally, we argue by contradiction that $\underline{R}_{d}$ has no endpoints.
Assume, on the contrary, that $\underline{R}_{d}$ has an end point
$\bm{x}_{0}$. Our preceding argument has shown that $\underline{M}(\bm{x})$,
the derivative of $\underline{V}_{d}(\bm{x})^{T}\nabla f(\bm{x})$, is bounded.
In addition, $\bm{x}_{0}\in\underline{R}_{d}$. However, this contradicts to
the implicit function theorem indicating that $\underline{R}_{d}$ is a
$d$-dimensional submanifold on $\Omega_{q}$, because at the end point
$\bm{x}_{0}\in\underline{R}_{d}$, there exists no local coordinate chart for
$\underline{R}_{d}$ defined on an open set in $\underline{R}_{d}$. The results
follow.

(e) By the proof of (d), we already know that all the $(q-d)$ nonzero singular
values of $\underline{M}(\bm{x})$ and
$\left(\bm{I}_{D}-\bm{x}\bm{x}^{T}\right)\underline{M}(\bm{x})$ are greater
than $\underline{\beta}_{1}>0$. Also, all the $(q+1-d)$ nonzero singular
values of $\underline{M}_{E}(\bm{x})$ are greater than
$\min\left\\{\underline{\beta}_{1},1\right\\}$. Thus, the results follow
easily from the argument of (e) in Lemma C.1.

Finally, the proofs of properties (f), (g), and (h) are essentially the same
as the corresponding claims in Chen et al. (2015). We thus omitted them. For
(h), the reader should be aware that we have extended the directional density
$f$ from $\Omega_{q}$ to $\mathbb{R}^{q+1}\setminus\\{\bm{0}\\}$. In addition,
it is the columns of $\underline{M}_{E}(\bm{x})$ that span the normal space of
$\underline{R}_{d}$ in the ambient space, whose nonzero singular values are
lower bounded by $\min\left\\{\underline{\beta}_{1},1\right\\}$. The proof of
(h) can also be found in Theorem 3 of Chen (2020). ∎

##  Appendix H Stability of Directional Density Ridge

###  H.1 Subspace Constrained Gradient Flows

This subsection is modified from Section 4 in Genovese et al. (2014) for
directional densities and their ridges on $\Omega_{q}$. A map
$\varpi:\mathbb{R}\to\Omega_{q}$ is a subspace constrained gradient flow with
the principal Riemannian gradient $\underline{G}_{d}$ if
$\varpi(0)=\bm{x}\in\Omega_{q}$ and

$\varpi^{\prime}(t)=\underline{G}_{d}(\varpi(t))=\underline{U}_{d}(\varpi(t))\cdot\mathtt{grad}\,f(\varpi(t))=\underline{V}_{d}(\varpi(t))\underline{V}_{d}(\varpi(t))^{T}\nabla
f(\varpi(t)),$ (75)

where the last equality follows from (30). Given the definition of the
directional density ridge $\underline{R}_{d}$ in (69), it consists of the
destinations of the subspace constrained gradient flow $\varpi$, _i.e._ ,
$\bm{y}\in\underline{R}_{d}$ if $\lim\limits_{t\to\infty}\varpi(t)=\bm{y}$ for
some $\varpi$ satisfying (75). It will be convenient to parametrize the
subspace constrained gradient ascent path with $\varpi$ by arc length. Let
$s\equiv s(t)$ be the arc length from $\varpi(t)$ to $\varpi(\infty)$:

$s(t)=\int_{t}^{\infty}\left|\left|\varpi^{\prime}(u)\right|\right|_{2}du.$

Denote the inverse of $s(t)$ by $t\equiv t(s)$. Note that

$t^{\prime}(s)=\frac{1}{s^{\prime}(t)}=-\frac{1}{\left|\left|\varpi^{\prime}(t(s))\right|\right|_{2}}=-\frac{1}{\left|\left|\underline{G}_{d}\left(\varpi(t(s))\right)\right|\right|_{2}}.$

With $\gamma(s)=\varpi(t(s))$, we have that

$\gamma^{\prime}(s)=-\frac{\underline{G}_{d}\left(\gamma(s)\right)}{\left|\left|\underline{G}_{d}\left(\gamma(s)\right)\right|\right|_{2}},$
(76)

which is a reparametrization of (75) by arc length. Note that $\gamma$ always
lies on $\Omega_{q}$ because its velocity is within the tangent space
$T_{\gamma(s)}$ for every $s\in[0,\infty)$. Lemma 2 in Genovese et al. (2014)
justifies the uniqueness of $\gamma$ passing through any particular point
$\bm{x}\in\left((\underline{R}_{d}\oplus\underline{\rho})\setminus\underline{R}_{d}\right)\cap\Omega_{q}$
under conditions (A1-3). The (reversed) subspace constrained gradient flow
$\gamma$ can be lifted onto the directional function $f$, as we may define

$\xi(s)=f(\varpi(\infty))-f(\varpi(t(s)))=f(\gamma(0))-f(\gamma(s)).$ (77)

Sometimes, we may add the subscript $\bm{x}$ to the curves
$\varpi_{\bm{x}},\gamma_{\bm{x}},\xi_{\bm{x}}$ if we want to emphasize that
$\varpi,\gamma,\xi$ start from or pass through the specific point $\bm{x}$.

To analyze the behavior of the subspace constrained gradient flow $\xi$ lifted
on $f$, we need the derivative of the projection matrix
$\underline{U}(\bm{x})\equiv\underline{U}_{d}(\bm{x})$ along the path
$\gamma$. Recall that
$\underline{U}(\bm{x})\equiv\underline{U}_{d}(\mathcal{H}f(\bm{x}))=\underline{V}_{d}(\bm{x})\underline{V}_{d}(\bm{x})^{T}$.
The collection $\left\\{\underline{U}(\bm{x}):\bm{x}\in\Omega_{q}\right\\}$
defines a matrix field: there is a matrix $\underline{U}(\bm{x})$ attached to
each point $\bm{x}$. As mentioned earlier, there is a unique path $\gamma$ and
unique $s>0$ such that $\bm{x}=\gamma(s)$ for any
$\bm{x}\in\left(\underline{R}_{d}\oplus\underline{\rho}\right)\setminus\underline{R}_{d}$.
Define

$\underline{\dot{U}}_{\gamma(s)}\equiv\lim_{\epsilon\to
0}\frac{\underline{U}(\mathcal{H}f(\gamma(s+\epsilon)))-\underline{U}(\mathcal{H}f(\gamma(s)))}{\epsilon}=\lim_{t\to
0}\frac{\underline{U}(\mathcal{H}f(\gamma(s))+tE_{s})-\underline{U}(\mathcal{H}f(\gamma(s)))}{t},$
(78)

where
$E_{s}=\frac{d}{ds}\mathcal{H}f(\gamma(s))=\bar{\nabla}_{\gamma^{\prime}(s)}\mathcal{H}f(\gamma(s))$
with $\bar{\nabla}$ being the Riemannian connection on $\Omega_{q}$. Under
conditions (A1-3), $\xi$ has a quadratic-like behavior near the directional
ridge $\underline{R}_{d}$, analogous to Lemma 3 in Genovese et al. (2014).

######  Lemma H.1.

Assume that conditions (A1-3) holds. For all
$\bm{x}\in\left(\underline{R}_{d}\oplus\underline{\rho}\right)\cap\Omega_{q}$,
we have the following properties:

  1. (a)

$\xi(0)=0$,
$\xi^{\prime}(s)=\left|\left|\underline{G}_{d}(\gamma(s))\right|\right|_{2}$,
and $\xi^{\prime}(0)=0$. Thus, $\xi(s)$ is non-decreasing in $s$.

  2. (b)

The second derivative of $\xi$ satisfies
$\xi^{\prime\prime}(s)\geq\frac{\underline{\beta}_{0}}{2}$.

  3. (c)

$\xi(s)\geq\frac{\underline{\beta}_{0}}{4}\left|\left|\gamma(0)-\gamma(s)\right|\right|_{2}^{2}$.

###### Proof of Lemma H.1.

The proof is adopted from Lemma 3 in Genovese et al. (2014).

(a) The first property $\xi(0)=0$ is obvious from the definition (77). Then,

$\displaystyle\xi^{\prime}(s)=-\mathtt{grad}\,f(\gamma(s))^{T}\gamma^{\prime}(s)$
$\displaystyle=\frac{\nabla
f(\gamma(s))^{T}\underline{G}_{d}(\gamma(s))}{\left|\left|\underline{G}_{d}(\gamma(s))\right|\right|_{2}}\quad\text{
by \eqref{arc_length_deri}}$ $\displaystyle=\frac{\nabla
f(\gamma(s))^{T}\underline{V}_{d}(\gamma(s))\underline{V}_{d}(\gamma(s))^{T}\nabla
f(\gamma(s))}{\left|\left|\underline{G}_{d}(\gamma(s))\right|\right|_{2}}$
$\displaystyle=\left|\left|\underline{G}_{d}(\gamma(s))\right|\right|_{2},$

since
$\underline{V}_{d}(\gamma(s))^{T}\underline{V}_{d}(\gamma(s))=\bm{I}_{q-d}$
for all $\gamma(s)\in\Omega_{q}$. By the definition of $\underline{R}_{d}$ in
(69), $\underline{G}_{d}(\gamma(s))=0$ when $\gamma(s)\in\underline{R}_{d}$.
Thus, $\xi^{\prime}(0)=0$ and $\xi(s)$ is non-decreasing in $s$.

(b) Note that

$\displaystyle\left(\xi^{\prime}(s)\right)^{2}=\left|\left|\underline{G}_{d}(\gamma(s))\right|\right|_{2}^{2}$
$\displaystyle=\nabla
f(\gamma(s))^{T}\underline{V}_{d}(\gamma(s))\underline{V}_{d}(\gamma(s))^{T}\nabla
f(\gamma(s))$
$\displaystyle=\left[\mathtt{grad}\,f(\gamma(s))\right]^{T}\underline{U}(\gamma(s))\left[\mathtt{grad}\,f(\gamma(s))\right].$

Differentiating both sides of the equation, we have that

$\displaystyle 2\xi^{\prime}(s)\xi^{\prime\prime}(s)$
$\displaystyle=2\gamma^{\prime}(s)^{T}\mathcal{H}f(\gamma(s))\underline{U}(\gamma(s))\left[\mathtt{grad}\,f(\gamma(s))\right]$
$\displaystyle\quad+\left[\mathtt{grad}\,f(\gamma(s))\right]^{T}\underline{\dot{U}}(\gamma(s))\left[\mathtt{grad}\,f(\gamma(s))\right].$

Since
$\underline{U}(\gamma(s))\cdot\underline{U}(\gamma(s))=\underline{U}(\gamma(s))$
(idempotent), we have that
$\underline{\dot{U}}(\gamma(s))=\underline{U}(\gamma(s))\underline{\dot{U}}(\gamma(s))+\underline{\dot{U}}(\gamma(s))\underline{U}(\gamma(s))$,
and hence the second term on the right-hand side of the above equation becomes

$\displaystyle\left[\mathtt{grad}\,f(\gamma(s))\right]^{T}\underline{\dot{U}}_{\gamma(s)}(\gamma(s))\left[\mathtt{grad}\,f(\gamma(s))\right]$
$\displaystyle=\nabla
f(\gamma(s))^{T}\underline{U}(\gamma(s))\underline{\dot{U}}_{\gamma(s)}(\gamma(s))\nabla
f(\gamma(s))+\nabla
f(\gamma(s))^{T}\underline{\dot{U}}_{\gamma(s)}(\gamma(s))\underline{U}(\gamma(s))\nabla
f(\gamma(s))$ $\displaystyle=2\nabla
f(\gamma(s))^{T}\underline{\dot{U}}(\gamma(s))\underline{G}_{d}(\gamma(s))$

Thus,

$2\xi^{\prime}(s)\xi^{\prime\prime}(s)=2\gamma^{\prime}(s)^{T}\mathcal{H}f(\gamma(s))\underline{G}_{d}(\gamma(s))+2\nabla
f(\gamma(s))^{T}\underline{\dot{U}}(\gamma(s))\underline{G}_{d}(\gamma(s)).$

By (a) and (76), we conclude that

$\xi^{\prime\prime}(s)=-\frac{\underline{G}_{d}(\gamma(s))^{T}\mathcal{H}f(\gamma(s))\cdot\underline{G}_{d}(\gamma(s))}{\left|\left|\underline{G}_{d}(\gamma(s))\right|\right|_{2}^{2}}+\frac{\nabla
f(\gamma(s))^{T}\underline{\dot{U}}(\gamma(s))\underline{G}_{d}(\gamma(s))}{\left|\left|\underline{G}_{d}(\gamma(s))\right|\right|_{2}}.$
(79)

Now, we will bound the two terms in (79), respectively. As for the first term
$-\frac{\underline{G}_{d}(\gamma(s))^{T}\mathcal{H}f(\gamma(s))\cdot\underline{G}_{d}(\gamma(s))}{\left|\left|\underline{G}_{d}(\gamma(s))\right|\right|_{2}^{2}}$,
we notice that $\underline{G}_{d}(\gamma(s))$ is in the column space of
$\underline{V}_{d}(\gamma(s))$. Hence,

$\underline{G}_{d}(\gamma(s))^{T}\mathcal{H}f(\gamma(s))\cdot\underline{G}_{d}(\gamma(s))=\underline{G}_{d}(\gamma(s))^{T}\left[\underline{V}_{d}(\gamma(s))\Lambda_{\underline{R}_{d}}(\gamma(s))\underline{V}_{d}(\gamma(s))^{T}\right]\underline{G}_{d}(\gamma(s)),$

where
$\Lambda_{\underline{R}_{d}}(\gamma(s))=\mathtt{Diag}\left[\underline{\lambda}_{d+1}(\gamma(s)),...,\underline{\lambda}_{q}(\gamma(s))\right]$.
Therefore, from condition (A2),

$\displaystyle\frac{\underline{G}_{d}(\gamma(s))^{T}\mathcal{H}f(\gamma(s))\cdot\underline{G}_{d}(\gamma(s))}{\left|\left|\underline{G}_{d}(\gamma(s))\right|\right|_{2}^{2}}$
$\displaystyle=\frac{\underline{G}_{d}(\gamma(s))^{T}\left[\underline{V}_{d}(\gamma(s))\Lambda_{\underline{R}_{d}}(\gamma(s))\underline{V}_{d}(\gamma(s))^{T}\right]\underline{G}_{d}(\gamma(s))}{\left|\left|\underline{G}_{d}(\gamma(s))\right|\right|_{2}^{2}}$
$\displaystyle\leq\lambda_{\max}\left[\underline{V}_{d}(\gamma(s))\Lambda_{\underline{R}_{d}}(\gamma(s))\underline{V}_{d}(\gamma(s))^{T}\right]\leq-\underline{\beta}_{0}$

and consequently,

$-\frac{\underline{G}_{d}(\gamma(s))^{T}\mathcal{H}f(\gamma(s))\cdot\underline{G}_{d}(\gamma(s))}{\left|\left|\underline{G}_{d}(\gamma(s))\right|\right|_{2}^{2}}\geq\underline{\beta}_{0}.$

As for the second term $\frac{\nabla
f(\gamma(s))^{T}\underline{\dot{U}}_{\gamma(s)}\underline{G}_{d}(\gamma(s))}{\left|\left|\underline{G}_{d}(\gamma(s))\right|\right|_{2}}$,
we notice that
$\underline{U}(\gamma(s))+\underline{U}^{\perp}(\gamma(s))=\bm{I}_{q+1}$,
where $\underline{U}^{\perp}\equiv\underline{U}_{d}^{\perp}$, and
$\underline{U}(\gamma(s))\cdot\underline{G}_{d}(\gamma(s))=\underline{G}_{d}(\gamma(s))$.
Then,

$\displaystyle\nabla
f(\gamma(s))^{T}\underline{\dot{U}}(\gamma(s))\underline{G}_{d}(\gamma(s))$
$\displaystyle=\nabla
f(\gamma(s))^{T}\underline{U}(\gamma(s))\underline{\dot{U}}(\gamma(s))\underline{G}_{d}(\gamma(s))+\nabla
f(\gamma(s))^{T}\underline{U}^{\perp}(\gamma(s))\underline{\dot{U}}(\gamma(s))G_{d}(\gamma(s))$
$\displaystyle=\nabla
f(\gamma(s))^{T}\underline{U}(\gamma(s))\underline{\dot{U}}(\gamma(s))\underline{U}(\gamma(s))\cdot\underline{G}_{d}(\gamma(s))$
$\displaystyle\quad+\nabla
f(\gamma(s))^{T}\underline{U}^{\perp}(\gamma(s))\underline{\dot{U}}(\gamma(s))\underline{U}(\gamma(s))\cdot\underline{G}_{d}(\gamma(s)).$

However, $\left|\nabla
f(\gamma(s))^{T}\underline{U}(\gamma(s))\underline{\dot{U}}(\gamma(s))\underline{U}(\gamma(s))\cdot\underline{G}_{d}(\gamma(s))\right|=0$.
To see this, note that
$\underline{U}(\gamma(s))\cdot\underline{U}(\gamma(s))=\underline{U}(\gamma(s))$
and it implies that

$\displaystyle\quad\underline{U}(\gamma(s))\underline{\dot{U}}(\gamma(s))+\underline{\dot{U}}(\gamma(s))\underline{U}(\gamma(s))=\underline{\dot{U}}(\gamma(s))$
$\displaystyle\implies\underline{U}(\gamma(s))\underline{\dot{U}}(\gamma(s))\underline{U}(\gamma(s))+\underline{\dot{U}}(\gamma(s))\underline{U}(\gamma(s))=\underline{\dot{U}}(\gamma(s))\underline{U}(\gamma(s)),$

showing that
$\underline{U}(\gamma(s))\underline{\dot{U}}_{\gamma(s)}\underline{U}(\gamma(s))=\bm{0}$.
To bound $\nabla
f(\gamma(s))^{T}\underline{U^{\perp}}(\gamma(s))\underline{\dot{U}}(\gamma(s))\underline{U}(\gamma(s))\cdot\underline{G}_{d}(\gamma(s))$,
we proceed as follows. As before, we let
$E_{s}=\frac{d}{ds}\mathcal{H}f(\gamma(s))=\bar{\nabla}\mathcal{H}f(\gamma(s))\cdot\gamma^{\prime}(s)$.
Then, by the Davis-Kahan theorem (Lemma D.1 here),

$\displaystyle\left|\nabla
f(\gamma(s))^{T}\underline{U}^{\perp}(\gamma(s))\underline{\dot{U}}(\gamma(s))\underline{U}(\gamma(s))\cdot\underline{G}_{d}(\gamma(s))\right|$
$\displaystyle=\lim_{t\to 0}\frac{\Big{|}\nabla
f(\gamma(s))^{T}\underline{U}^{\perp}(\gamma(s))\left[\underline{U}(\mathcal{H}f(\gamma(s))+tE_{s})-\underline{U}(\mathcal{H}f(\gamma(s)))\Big{]}\underline{U}(\gamma(s))\cdot\underline{G}_{d}(\gamma(s))\right|}{t}$
$\displaystyle\leq\left|\left|\underline{U}^{\perp}(\gamma(s))\nabla
f(\gamma(s))\right|\right|_{2}\cdot\lim_{t\to
0}\frac{\left|\left|\underline{U}(\mathcal{H}f(\gamma(s))+tE_{s})-\underline{U}(\mathcal{H}f(\gamma(s)))\right|\right|_{2}}{t}\cdot\left|\left|\underline{G}_{d}(\gamma(s))\right|\right|_{2}$
$\displaystyle\leq\frac{\sqrt{2}\left|\left|\underline{U}^{\perp}(\gamma(s))\nabla
f(\gamma(s))\right|\right|_{2}\cdot\left|\left|E_{s}\right|\right|_{F}\cdot\left|\left|\underline{G}_{d}(\gamma(s))\right|\right|_{2}}{\underline{\beta}_{0}}.$

Note that
$\left|\left|E_{s}\right|\right|_{F}\leq\left|\left|\bar{\nabla}\mathcal{H}f(\gamma(s))\right|\right|_{\max}\cdot\left|\left|\gamma^{\prime}(s)\right|\right|_{2}\leq
q^{\frac{3}{2}}\left|\left|\nabla^{3}f(\gamma(s))\right|\right|_{\max}$,
because $\left|\left|\gamma^{\prime}(s)\right|\right|_{2}=1$. Thus, from
condition (A3),

$\frac{\left|\nabla
f(\gamma(s))^{T}\underline{\dot{U}}(\gamma(s))\underline{G}_{d}(\gamma(s))\right|}{\left|\left|\underline{G}_{d}(\gamma(s))\right|\right|_{2}}\leq\frac{\sqrt{2}q^{\frac{3}{2}}\left|\left|\nabla^{3}f(\gamma(s))\right|\right|_{\max}\left|\left|\underline{U}^{\perp}(\gamma(s))\nabla
f(\gamma(s))\right|\right|_{2}}{\underline{\beta}_{0}}\leq\frac{\underline{\beta}_{0}}{2}.$

Therefore,
$\xi^{\prime\prime}(s)\geq\underline{\beta}_{0}-\frac{\underline{\beta}_{0}}{2}=\frac{\underline{\beta}_{0}}{2}$.

(c) For some $0\leq\widetilde{s}\leq s$,

$\xi(s)=\xi(0)+s\xi^{\prime}(0)+\frac{s^{2}}{2}\xi^{\prime\prime}(\widetilde{s})=\frac{s^{2}}{2}\xi^{\prime\prime}(\widetilde{s})\geq\frac{\underline{\beta}_{0}s^{2}}{4}$

by (a) and (b). As $\gamma$ is parametrized by arc length, we conclude that

$\xi(s)-\xi(0)\geq\frac{\underline{\beta}_{0}}{4}s^{2}\geq\frac{\underline{\beta}_{0}}{4}\left|\left|\gamma(0)-\gamma(s)\right|\right|_{2}^{2}.$

The result follows. ∎

The statement (c) in Lemma H.1 is known as the quadratic growth condition in
the optimization literature (Anitescu, 2000; Drusvyatskiy and Lewis, 2018).
Under conditions (A1-3), such a quadratic growth of the subspace constrained
gradient flow $\xi$ lifted onto the directional density $f$ enables us to
quantify the stability of directional ridges under small perturbations on the
directional density and develop the linear convergence of the (directional)
SCGA algorithms on $\Omega_{q}$.

###  H.2 Proof of Theorem 4.1

We now show that if two directional densities $f$ and $\widetilde{f}$ are
close, their corresponding ridges $\underline{R}_{d}$ and
$\underline{\widetilde{R}}_{d}$ are also close. We will use, for instance,
$\underline{\widetilde{G}}_{d}$ and $\underline{\widetilde{U}}_{d}$, to refer
to the principal (Riemannian) gradient and projection matrix with its columns
as the eigenvectors corresponding to the smallest $q-d$ eigenvalues of the
(Riemannian) Hessian $\mathcal{H}\widetilde{f}$ with the tangent space of
$\Omega_{q}$ defined by $\widetilde{f}$.

######  Theorem 4.1.

Suppose that conditions (A1-3) hold for the directional density $f$ and that
condition (A1) holds for $\widetilde{f}$. When
$\left|\left|f-\widetilde{f}\right|\right|_{\infty,3}^{*}$ is sufficiently
small,

  1. (a)

conditions (A2-3) holds for $\widetilde{f}$.

  2. (b)

$\mathtt{Haus}(\underline{R}_{d},\underline{\widetilde{R}}_{d})=O\left(\left|\left|f-\widetilde{f}\right|\right|_{\infty,2}^{*}\right)$.

  3. (c)

$\mathtt{reach}(\underline{\widetilde{R}}_{d})\geq\min\left\\{\underline{\rho}/2,\frac{\min\left\\{\underline{\beta}_{1},1\right\\}^{2}}{\underline{A}_{2}\left(\left|\left|f\right|\right|_{\infty}^{(3)}+\left|\left|f\right|\right|_{\infty}^{(4)}\right)}\right\\}+O\left(\left|\left|f-\widetilde{f}\right|\right|_{\infty,3}^{*}\right)$
for a constant $\underline{A}_{2}>0$.

###### Proof of Theorem 4.1.

Our arguments are modified from the proof of Theorem 4 in Genovese et al.
(2014) as well as Proposition 4 and Theorem 5 in Chen (2020).

(a) We write the spectral decompositions of $\mathcal{H}f$ and
$\mathcal{H}\widetilde{f}$ as

$\mathcal{H}f=V\Lambda V^{T}\quad\text{ and
}\quad\mathcal{H}\widetilde{f}=\widetilde{V}\widetilde{\Lambda}\widetilde{V}.$

By Weyl’s Theorem (Theorem 4.3.1 in Horn and Johnson (2012)), we know that

$|\lambda_{j}-\widetilde{\lambda}_{j}|\leq\left|\left|\mathcal{H}f-\mathcal{H}\widetilde{f}\right|\right|_{2}\leq
q\left|\left|f-\widetilde{f}\right|\right|_{\infty,2}^{*},$

where we recall that there are at most $q$ nonzero eigenvalues of the
Riemannian Hessian $\mathcal{H}f(\bm{x})$ on $\Omega_{q}$. Thus,
$\widetilde{f}$ satisfies condition (A2). Moreover, since condition (A3)
depends only on the first and third order derivative of $f$, they hold for
$\widetilde{f}$ when
$\left|\left|f-\widetilde{f}\right|\right|_{\infty,3}^{*}$ is small enough.

(b) We present two methods based on two different flows to prove this
statement and comment their pros and cons in Remark H.1.
Method A: By the Davis-Kahan theorem (Lemma D.1 and (60)),

$\displaystyle\left|\left|\underline{U}_{d}(\bm{x})-\underline{\widetilde{U}}_{d}(\bm{x})\right|\right|_{2}$
$\displaystyle=\left|\left|\underline{V}_{d}(\bm{x})\underline{V}_{d}(\bm{x})^{T}-\underline{\widetilde{V}}_{d}(\bm{x})\underline{\widetilde{V}}_{d}(\bm{x})^{T}\right|\right|_{2}$
$\displaystyle\leq\frac{\sqrt{2}\left|\left|\mathcal{H}f(\bm{x})-\mathcal{H}\widetilde{f}(\bm{x})\right|\right|_{F}}{\underline{\beta}_{0}}$
$\displaystyle\leq\frac{\sqrt{2}q\left|\left|f-\widetilde{f}\right|\right|_{\infty,2}^{*}}{\underline{\beta}_{0}}$

for any $\bm{x}\in\Omega_{q}$. Then, given that
$\left|\left|\underline{\widetilde{V}}_{d}(\bm{x})\underline{\widetilde{V}}_{d}(\bm{x})^{T}\right|\right|_{2}=1$,

$\displaystyle\left|\left|\underline{G}_{d}(\bm{x})-\underline{\widetilde{G}}_{d}(\bm{x})\right|\right|_{2}$
$\displaystyle=\left|\left|\underline{V}_{d}(\bm{x})\underline{V}_{d}(\bm{x})^{T}\nabla
f(\bm{x})-\underline{\widetilde{V}}_{d}(\bm{x})\underline{\widetilde{V}}_{d}(\bm{x})^{T}\nabla\widetilde{f}(\bm{x})\right|\right|_{2}$
$\displaystyle\leq\left|\left|\left[\underline{V}_{d}(\bm{x})\underline{V}_{d}(\bm{x})^{T}-\underline{\widetilde{V}}_{d}(\bm{x})\underline{\widetilde{V}}_{d}(\bm{x})^{T}\right]\nabla
f(\bm{x})\right|\right|_{2}+\left|\left|\underline{\widetilde{V}}_{d}(\bm{x})\underline{\widetilde{V}}_{d}(\bm{x})^{T}\left[\nabla
f(\bm{x})-\nabla\widetilde{f}(\bm{x})\right]\right|\right|_{2}$
$\displaystyle\leq\frac{\sqrt{2}q\left|\left|f-\widetilde{f}\right|\right|_{\infty,2}^{*}}{\underline{\beta}_{0}}\cdot\left|\left|\nabla
f(\bm{x})\right|\right|_{2}+\sqrt{q}\left|\left|f-\widetilde{f}\right|\right|_{\infty,1}^{*}.$

Therefore, by the differentiability of $f$ from (A1) and the compactness of
$\Omega_{q}$, we obtain from the above calculations that

$\sup_{\bm{x}\in\Omega_{q}}\left|\left|\underline{G}_{d}(\bm{x})-\underline{\widetilde{G}}_{d}(\bm{x})\right|\right|_{2}\leq
C_{1}\left|\left|f-\widetilde{f}\right|\right|_{\infty,2}^{*}$

for some constant $C_{1}>0$ that only depends on the dimension $q$.
Now, let $\widetilde{\bm{x}}\in\underline{\widetilde{R}}_{d}$. Then,
$\left|\left|\underline{\widetilde{G}}_{d}(\widetilde{\bm{x}})\right|\right|_{2}=0$,
and $\left|\left|\underline{G}_{d}(\widetilde{\bm{x}})\right|\right|_{2}\leq
C_{1}\left|\left|f-\widetilde{f}\right|\right|_{\infty,2}^{*}$. Let $\gamma$
be the subspace constrained gradient ascent flow through $\widetilde{\bm{x}}$
as defined in Section H.1 so that $\gamma(s)=\widetilde{\bm{x}}$ for some $s$.
Note that $\gamma(0)\in\underline{R}_{d}$. From property (a) of Lemma H.1, we
have that
$\xi^{\prime}(s)=\left|\left|\underline{G}_{d}(\widetilde{\bm{x}})\right|\right|_{2}$.
Moreover, by Taylor’s theorem,

$C_{1}\left|\left|f-\widetilde{f}\right|\right|_{\infty,2}^{*}\geq\left|\left|\underline{G}_{d}(\widetilde{\bm{x}})\right|\right|_{2}=\xi^{\prime}(s)=\xi^{\prime}(0)+s\xi^{\prime\prime}(u)$

for some $u$ between $0$ and $s$. Since $\xi^{\prime}(0)=0$, from property (b)
of Lemma H.1,

$C_{1}\left|\left|f-\widetilde{f}\right|\right|_{\infty,2}^{*}\geq
s\xi^{\prime\prime}(u)\geq\frac{s\underline{\beta}_{0}}{2},$

and consequently, $d_{g}(\gamma(0),\widetilde{\bm{x}})\leq
s\leq\frac{2C_{1}}{\underline{\beta}_{0}}\left|\left|f-\widetilde{f}\right|\right|_{\infty,2}^{*}$,
where $d_{g}(\bm{x},\bm{y})$ denotes the geodesic distance between $\bm{x}$
and $\bm{y}$ on $\Omega_{q}$. Therefore,

$d_{E}(\widetilde{\bm{x}},\underline{R}_{d})\leq\left|\left|\gamma(0)-\widetilde{\bm{x}}\right|\right|_{2}\leq
d_{g}(\gamma(0),\widetilde{\bm{x}})\leq\frac{2C_{1}}{\underline{\beta}_{0}}\left|\left|f-\widetilde{f}\right|\right|_{\infty,2}^{*}.$

Now let $\bm{x}\in\underline{R}_{d}$. The same argument shows that
$d_{E}(\bm{x},\underline{\widetilde{R}}_{d})\leq\frac{2C_{1}}{\underline{\beta}_{0}}\left|\left|f-\widetilde{f}\right|\right|_{\infty,2}^{*}$
for some constant $C_{2}>0$ because conditions (A1-3) hold for
$\widetilde{f}$.
As a result,
$\mathtt{Haus}(\underline{R}_{d},\underline{\widetilde{R}}_{d})\leq\frac{2C_{1}}{\underline{\beta}_{0}}\left|\left|f-\widetilde{f}\right|\right|_{\infty,2}^{*}=O\left(\left|\left|f-\widetilde{f}\right|\right|_{\infty,2}^{*}\right)$.

Method B: Since we are only required to bound the maximum Euclidean distance
between $\underline{R}_{d}$ and $\underline{\widetilde{R}}_{d}$, _i.e._ ,
$\mathtt{Haus}(\underline{R}_{d},\underline{\widetilde{R}}_{d})$, we may view
$\underline{R}_{d}$ and $\underline{\widetilde{R}}_{d}$ as solution manifolds
in $\mathbb{R}^{q+1}$ and tentatively ignore the manifold constraint
$\underline{R}_{d},\underline{\widetilde{R}}_{d}\subset\Omega_{q}$. Define
$h(\bm{x})=\left|\left|\underline{V}_{d}(\bm{x})^{T}\nabla
f(\bm{x})\right|\right|_{2}=\sqrt{\nabla
f(\bm{x})^{T}\underline{V}_{d}(\bm{x})\underline{V}_{d}(\bm{x})^{T}\nabla
f(\bm{x})}$. Given that
$\underline{M}(\bm{x})=\nabla\left[\underline{V}_{d}(\bm{x})^{T}\nabla
f(\bm{x})\right]^{T}$, the gradient of $h(\bm{x})$,

$\nabla h(\bm{x})=\frac{\nabla\left[\underline{V}_{d}(\bm{x})^{T}\nabla
f(\bm{x})\right]^{T}\underline{V}_{d}(\bm{x})^{T}\nabla
f(\bm{x})}{\left|\left|\underline{V}_{d}(\bm{x})^{T}\nabla
f(\bm{x})\right|\right|_{2}}=\frac{\underline{M}(\bm{x})\underline{V}_{d}(\bm{x})^{T}\nabla
f(\bm{x})}{\left|\left|\underline{V}_{d}(\bm{x})^{T}\nabla
f(\bm{x})\right|\right|_{2}},$ (80)

is a vector in $\mathbb{R}^{q+1}$. Let
$\bm{z}\in\underline{\widetilde{R}}_{d}$. We define a flow
$\phi_{\bm{z}}:\mathbb{R}\to\mathbb{R}^{q+1}$ such that

$\phi_{\bm{z}}(0)=\bm{z},\quad\phi_{\bm{z}}^{\prime}(t)=-\nabla
h(\phi_{\bm{z}}(t)).$

It can be argued by Theorem 7 in Chen (2020) that
$\phi_{\bm{z}}(\infty)\in\underline{R}_{d}$ when
$\bm{z}\in\underline{R}_{d}\oplus\delta_{0}$ for some small $\delta_{0}>0$. In
addition, we can always choose
$\left|\left|f-\widetilde{f}\right|\right|_{\infty,3}^{*}$ to be small enough
so that
$\underline{\widetilde{R}}_{d}\subset\underline{R}_{d}\oplus\delta_{0}$. By
Theorem 3.39 in Irwin (2001), $\phi_{\bm{z}}(t)$ is uniquely defined because
the gradient $\nabla h(\bm{z})$ is well-defined for all
$\bm{z}\notin\underline{R}_{d}$. We can also reparametrize $\phi_{\bm{z}}(t)$
by arc length as:

$\gamma_{\bm{z}}(0)=\bm{z},\quad\gamma_{\bm{z}}^{\prime}(s)=-\frac{\nabla
h(\gamma_{\bm{z}}(s))}{\left|\left|\nabla
h(\gamma_{\bm{z}}(s))\right|\right|_{2}}.$

Let
$\mathcal{S}_{\bm{z}}=\inf\left\\{s>0:\gamma_{\bm{z}}(s)\in\underline{R}_{d}\right\\}$
be the terminal time/arc-length point and
$\gamma_{\bm{z}}(\mathcal{S}_{\bm{z}})\in\underline{R}_{d}$ be the destination
of $\gamma_{\bm{z}}$ on $\underline{R}_{d}$. The above argument also
demonstrates that the flows $\phi_{\bm{z}}$ or $\gamma_{\bm{z}}$ converge to
the manifold $\underline{R}_{d}$ from the normal direction of
$\underline{R}_{d}$, because we can write

$\displaystyle\gamma_{\bm{z}}^{\prime}(\mathcal{S}_{\bm{z}})=-\frac{\nabla
h(\gamma_{\bm{z}}(\mathcal{S}_{\bm{z}}))}{\left|\left|\nabla
h(\gamma_{\bm{z}}(\mathcal{S}_{\bm{z}}))\right|\right|_{2}}=\sum\limits_{k=d+1}^{q}\bm{a}_{k}\cdot\underline{\bm{m}}_{k}(\gamma_{\bm{z}}(\mathcal{S}_{\bm{z}}))$
$\displaystyle\quad\text{ with
}\quad\bm{a}_{k}=-\frac{\bm{e}_{k-d}^{T}\underline{V}_{d}(\gamma_{\bm{z}}(\mathcal{S}_{\bm{z}}))\nabla
f(\gamma_{\bm{z}}(\mathcal{S}_{\bm{z}}))}{\left|\left|\underline{M}(\gamma_{\bm{z}}(\mathcal{S}_{\bm{z}}))\underline{V}_{d}(\gamma_{\bm{z}}(\mathcal{S}_{\bm{z}}))\nabla
f(\gamma_{\bm{z}}(\mathcal{S}_{\bm{z}}))\right|\right|_{2}}$

and the column space of $\underline{M}(\gamma_{\bm{z}}(\mathcal{S}_{\bm{z}}))$
spans the normal space of $\underline{R}_{d}$ at
$\gamma_{\bm{z}}(\mathcal{S}_{\bm{z}})\in\underline{R}_{d}$.
The goal now is to bound $\mathcal{S}_{\bm{z}}$ because its length must be
greater or equal to
$\left|\left|\bm{z}-\pi_{\underline{R}_{d}}(\bm{z})\right|\right|_{2}$. We
then define
$\vartheta_{\bm{z}}(s)=h(\gamma_{\bm{z}}(s))-h(\gamma_{\bm{z}}(\mathcal{S}_{\bm{z}}))=h(\gamma_{\bm{z}}(s))$.
Differentiating $\vartheta_{\bm{z}}(s)$ with respect to $s$ leads to

$\displaystyle\begin{split}\vartheta_{\bm{z}}^{\prime}(s)=\frac{d}{ds}h(\gamma_{\bm{z}}(s))&=\left[\nabla
h(\gamma_{\bm{z}}(s))\right]^{T}\gamma_{\bm{z}}^{\prime}(s)\\\
&=-\left|\left|\nabla h(\gamma_{\bm{z}}(s))\right|\right|_{2}\\\
&=-\frac{\left|\left|\underline{M}(\gamma_{\bm{z}}(s))\underline{V}_{d}(\gamma_{\bm{z}}(s))^{T}\nabla
f(\gamma_{\bm{z}}(s))\right|\right|_{2}}{\left|\left|\underline{V}_{d}(\gamma_{\bm{z}}(s))^{T}\nabla
f(\gamma_{\bm{z}}(s))\right|\right|_{2}}\\\
&\leq-\lambda_{\min}\left(\underline{M}(\gamma_{\bm{z}}(s))^{T}\underline{M}(\gamma_{\bm{z}}(s))\right)\leq-\widetilde{\beta}_{1}\end{split}$
(81)

by (d) in Lemma G.1. (Note that
$0<\widetilde{\beta}_{1}\leq\underline{\beta}_{1}$ because
$\lambda_{\min}(\underline{M}(\bm{x})^{T}\underline{M}(\bm{x}))\geq\underline{\beta}_{1}$
and by the continuity of
$\lambda_{\min}(\underline{M}(\bm{y})^{T}\underline{M}(\bm{y}))$, we can
always choose $\delta_{0}>0$ such that
$\lambda_{\min}(\underline{M}(\bm{y})^{T}\underline{M}(\bm{y}))\geq\widetilde{\beta}_{1}$
for all $\bm{y}\in\underline{R}_{d}\oplus\delta_{0}$.) As
$\bm{z}\in\underline{\widetilde{R}}_{d}$, by the proof of Method A, we know
that

$\displaystyle
C_{1}\left|\left|f-\widetilde{f}\right|\right|_{\infty,2}^{*}\geq\left|\left|\underline{G}_{d}(\bm{z})\right|\right|$
$\displaystyle=\left|\left|\underline{V}_{d}(\bm{z})^{T}\nabla
f(\bm{z})\right|\right|_{2}$
$\displaystyle=h(\gamma_{\bm{z}}(0))-h(\gamma_{\bm{z}}(\mathcal{S}_{\bm{z}}))\quad\text{
since }h(\gamma_{\bm{z}}(\mathcal{S}_{\bm{z}}))=0$
$\displaystyle=\vartheta_{\bm{z}}(0)-\vartheta_{\bm{z}}(\mathcal{S}_{\bm{z}})\quad\text{
since }\vartheta_{\bm{z}}(\mathcal{S}_{\bm{z}})=0\text{ and
}\vartheta_{\bm{z}}(0)=h(\gamma_{\bm{z}}(0))$
$\displaystyle=-\mathcal{S}_{\bm{z}}\vartheta_{\bm{z}}^{\prime}(\mathcal{S}_{\bm{z}}^{*})\quad\text{
by the mean value theorem}$
$\displaystyle\geq\mathcal{S}_{\bm{z}}\widetilde{\beta}_{1}\quad\text{ by
\eqref{zeta_bound}},$

where $\mathcal{S}_{\bm{z}}^{*}$ is some value between $0$ and
$\mathcal{S}_{\bm{z}}$. Hence,
$\mathcal{S}_{\bm{z}}\leq\frac{C_{1}}{\widetilde{\beta}_{1}}\left|\left|f-\widetilde{f}\right|\right|_{\infty,2}^{*}=O\left(\left|\left|f-\widetilde{f}\right|\right|_{\infty,2}^{*}\right)$,
which is independent of $\bm{z}\in\underline{\widetilde{R}}_{d}$. This implies
that

$\sup_{\bm{z}\in\underline{\widetilde{R}}_{d}}d_{E}(\bm{z},\underline{R}_{d})\leq\frac{C_{1}}{\widetilde{\beta}_{1}}\left|\left|f-\widetilde{f}\right|\right|_{\infty,2}^{*}=O\left(\left|\left|f-\widetilde{f}\right|\right|_{\infty,2}^{*}\right).$

We can exchange the role of $\underline{R}_{d}$ and
$\underline{\widetilde{R}}_{d}$ and apply the same argument to show that

$\sup_{\bm{x}\in\underline{R}_{d}}d_{E}(\bm{x},\underline{\widetilde{R}}_{d})=O\left(\left|\left|f-\widetilde{f}\right|\right|_{\infty,2}^{*}\right).$

In total, this leads to the conclusion that
$\mathtt{Haus}(\underline{R}_{d},\underline{\widetilde{R}}_{d})=O\left(\left|\left|f-\widetilde{f}\right|\right|_{\infty,2}^{*}\right)$.

(c) By (h) in Lemma G.1, the reach of $\underline{R}_{d}$ has a lower bound,
$\min\left\\{\underline{\rho}/2,\frac{\min\left\\{\underline{\beta}_{1},1\right\\}^{2}}{\underline{A}_{2}\left(\left|\left|f\right|\right|_{\infty}^{(3)}+\left|\left|f\right|\right|_{\infty}^{(4)}\right)}\right\\}$.
Note that $\underline{\rho}$ and $\underline{\beta}_{1}$ depend on the first
three order derivatives of $f$. Thus, the lower bound for the reach of
$\underline{\widetilde{R}}_{d}$ will be identical to the one for
$\underline{R}_{d}$ with an error rate
$O\left(\left|\left|f-\widetilde{f}\right|\right|_{\infty,3}^{*}\right)$. ∎

Note that for the stability of directional ridges, one can relax the condition
(A1) by requiring $f$ to be $\beta$-Hölder with $\beta\geq 3$.

######  Remark H.1.

We apply two different methods to establish the stability theorem of
directional density ridges. Method A utilizes the subspace constrained
gradient flow constructed in Section H.1 and its quadratic behavior (Lemma
H.1), while Method B defines a normal flow to the ridge $\underline{R}_{d}$
induced by the column space of $\underline{M}(\bm{x})$. Each of these two
flows has its pros and cons. The subspace constrained gradient flow aligns
more coherently with our directional SCMS algorithm (Algorithm 2) to identify
the (estimated) directional ridge from data, because it relies only on the
first and second order derivatives of the (estimated) density $f$.
Nevertheless, the subspace constrained gradient flow does not necessarily
converge to $\underline{R}_{d}$ in the optimal direction, that is, the normal
direction to $\underline{R}_{d}$. This can be seen from the explicit formula
(72) of $\underline{M}(\bm{x})$, which spans the normal space of
$\underline{R}_{d}$. The normal flow

$\phi_{\bm{z}}(0)=\bm{z},\quad\phi_{\bm{z}}^{\prime}(t)=-\frac{\underline{M}(\phi_{\bm{z}}(t))\underline{V}_{d}(\phi_{\bm{z}}(t))^{T}\nabla
f(\phi_{\bm{z}}(t))}{\left|\left|\underline{V}_{d}(\phi_{\bm{z}}(t))^{T}\nabla
f(\phi_{\bm{z}}(t))\right|\right|_{2}}$

defined in Method B, however, converges to $\underline{R}_{d}$ in its normal
direction by construction. In general, the normal flow tends to the ridge
$\underline{R}_{d}$ faster than the subspace constrained gradient flow, but it
may be complicated to compute in any practical ridge-finding task due to its
involvement with third order derivatives of the (estimated) density $f$.
Recently, Qiao and Polonik (2021) presented explicit formulae for finding
density ridges via such a normal flow and its discrete gradient descent
approximation. Additionally, they defined a smoothed version of the ridgeness
function that also circumvents the computations of third order derivatives of
$f$.

##  Appendix I Proofs of Proposition 4.3, Proposition 4.4, and Theorem 4.6

######  Proposition 4.3.

Assume that the directional kernel $L$ is non-increasing, twice continuously
differentiable, and convex with $L(0)<\infty$. Given the directional KDE
$\widehat{f}_{h}(\bm{x})=\frac{c_{L,q}(h)}{n}\sum\limits_{i=1}^{n}L\left(\frac{1-\bm{x}^{T}\bm{X}_{i}}{h^{2}}\right)$
and the directional SCMS sequence
$\big{\\{}\underline{\widehat{\bm{x}}}^{(t)}\big{\\}}_{t=0}^{\infty}\subset\Omega_{q}$
defined by (39) or (40), the following properties hold:

  1. (a)

The estimated density sequence
$\left\\{\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right\\}_{t=0}^{\infty}$
is non-decreasing and thus converges.

  2. (b)

$\lim\limits_{t\to\infty}\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}=0$.

  3. (c)

If the kernel $L$ is also strictly decreasing on $[0,\infty)$, then
$\lim\limits_{t\to\infty}\left|\left|\underline{\widehat{\bm{x}}}^{(t+1)}-\underline{\widehat{\bm{x}}}^{(t)}\right|\right|_{2}=0$.

###### Proof of Proposition 4.3.

(a) The sequence
$\left\\{\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right\\}_{t=0}^{\infty}$
is bounded if the kernel $L$ is non-increasing with $L(0)<\infty$. Hence, it
suffices to show that it is non-decreasing. The convexity and
differentiability of kernel $L$ imply that

$L(x_{2})-L(x_{1})\geq L^{\prime}(x_{1})\cdot(x_{2}-x_{1})$ (82)

for all $x_{1},x_{2}\in[0,\infty)$. Then, with
$\nabla\widehat{f}_{h}(\bm{x})=-\frac{c_{L,q}(h)}{nh^{2}}\sum\limits_{i=1}^{n}\bm{X}_{i}L^{\prime}\left(\frac{1-\bm{x}^{T}\bm{X}_{i}}{h^{2}}\right)$
and the iterative formula (40) in the main paper, we derive that

$\displaystyle\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t+1)})-\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})$
$\displaystyle=\frac{c_{L,q}(h)}{n}\sum_{i=1}^{n}\left[L\left(\frac{1-\bm{X}_{i}^{T}\underline{\widehat{\bm{x}}}^{(t+1)}}{h^{2}}\right)-L\left(\frac{1-\bm{X}_{i}^{T}\underline{\widehat{\bm{x}}}^{(t)}}{h^{2}}\right)\right]$
$\displaystyle\geq\frac{c_{L,q}(h)}{nh^{2}}\sum_{i=1}^{n}L^{\prime}\left(\frac{1-\bm{X}_{i}^{T}\underline{\widehat{\bm{x}}}^{(t)}}{h^{2}}\right)\bm{X}_{i}^{T}\left(\underline{\widehat{\bm{x}}}^{(t)}-\underline{\widehat{\bm{x}}}^{(t+1)}\right)$
$\displaystyle=\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\left(\underline{\widehat{\bm{x}}}^{(t+1)}-\underline{\widehat{\bm{x}}}^{(t)}\right)$
$\displaystyle=\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\left[\frac{\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})+\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}\cdot\underline{\widehat{\bm{x}}}^{(t)}}{\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})+\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}\cdot\underline{\widehat{\bm{x}}}^{(t)}\right|\right|_{2}}-\underline{\widehat{\bm{x}}}^{(t)}\right]$
$\displaystyle\stackrel{{\scriptstyle\text{(i)}}}{{=}}\frac{\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}}{\sqrt{\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}+\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}}}$
$\displaystyle\quad+\frac{\left[\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}-\sqrt{\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}+\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}}\right]\cdot\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\underline{\widehat{\bm{x}}}^{(t)}}{\sqrt{\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}+\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}}}$
$\displaystyle\stackrel{{\scriptstyle\text{(ii)}}}{{=}}\frac{\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}}{\sqrt{\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}+\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}}}$
$\displaystyle\quad\times\frac{\left[\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}+\sqrt{\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}+\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}}-\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\underline{\widehat{\bm{x}}}^{(t)}\right]}{\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}+\sqrt{\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}+\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}}}$
$\displaystyle\stackrel{{\scriptstyle\text{(iii)}}}{{\geq}}\frac{\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}}{\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}+\sqrt{\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}+\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}}}$
$\displaystyle\stackrel{{\scriptstyle\text{(iv)}}}{{\geq}}\frac{\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}}{\left(1+\sqrt{2}\right)\cdot\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}}$
$\displaystyle\geq 0,$

where we use the orthogonality between
$\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}$
and $\underline{\widehat{\bm{x}}}^{(t)}$ in (i), multiply
$\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}+\sqrt{\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}+\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}}$
to both the numerators and denominators of the two summands to obtain (ii),
leverage the fact that
$\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}\geq\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\underline{\widehat{\bm{x}}}^{(t)}$
in (iii), use the inequality
$\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}\leq\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}$
in (iv). It thus completes the proof of (a).

(b) Our derivation in (a) already shows that

$\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}\leq\sqrt{\left(1+\sqrt{2}\right)\cdot\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}\cdot\left[\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t+1)})-\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right]}.$

Notice that, on the one hand, the differentiability of kernel $L$ and the
compactness of $\Omega_{q}$ imply that
$\left|\left|\nabla\widehat{f}_{h}(\bm{x})\right|\right|_{2}\leq B_{h,L}$ for
all $\bm{x}\in\Omega_{q}$, where $B_{h,L}>0$ only depends on the bandwidth $h$
and kernel $L$. On the other hand, our argument in (a) already proves the
convergence of
$\left\\{\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right\\}_{t=0}^{\infty}$.
Therefore,

$\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}\leq\sqrt{\left(1+\sqrt{2}\right)B_{h,L}\cdot\left[\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t+1)})-\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right]}\to
0$

as $t\to\infty$. The result follows.

(c) Given the iterative formula (40) in the main paper, we deduce that

$\displaystyle\left|\left|\underline{\widehat{\bm{x}}}^{(t+1)}-\underline{\widehat{\bm{x}}}^{(t)}\right|\right|_{2}^{2}$
$\displaystyle=\left|\left|\frac{\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})+\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}\cdot\underline{\widehat{\bm{x}}}^{(t)}}{\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})+\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}\cdot\underline{\widehat{\bm{x}}}^{(t)}\right|\right|_{2}}-\underline{\widehat{\bm{x}}}^{(t)}\right|\right|_{2}^{2}$
$\displaystyle\stackrel{{\scriptstyle\text{(i)}}}{{=}}\frac{\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})+\left[\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}-\sqrt{\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}+\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}}\right]\underline{\widehat{\bm{x}}}^{(t)}\right|\right|_{2}^{2}}{\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}+\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}}$
$\displaystyle\stackrel{{\scriptstyle\text{(ii)}}}{{=}}\frac{2\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}}{\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}+\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}}$
$\displaystyle\quad+\underbrace{\frac{2\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}-2\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}\cdot\sqrt{\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}+\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}}}{\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}+\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}}}_{\leq
0}$
$\displaystyle\leq\frac{2\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}}{\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}+\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}},$

where we leverage the orthogonality between
$\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})$
and $\underline{\widehat{\bm{x}}}^{(t)}$ to obtain (i) and (ii). Under the
assumption that the kernel $L$ is strictly decreasing and (twice) continuously
differentiable, we know that
$\left|\left|\nabla\widehat{f}_{h}(\bm{x})\right|\right|_{2}$ is lower bounded
away from 0 on $\Omega_{q}$. Therefore, with the result in (b), the above
calculation indicates that

$\left|\left|\underline{\widehat{\bm{x}}}^{(t+1)}-\underline{\widehat{\bm{x}}}^{(t)}\right|\right|_{2}\leq\frac{\sqrt{2}\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}}{\sqrt{\left|\left|\widehat{\underline{V}}_{d}(\underline{\widehat{\bm{x}}}^{(t)})^{T}\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}+\left|\left|\nabla\widehat{f}_{h}(\underline{\widehat{\bm{x}}}^{(t)})\right|\right|_{2}^{2}}}\to
0$

as $t\to\infty$. The result follows. ∎

######  Remark I.1.

The conditions imposed on kernel $L$ in Proposition 4.3 is satisfied by some
commonly used kernels, such as the von Mises kernel $L(r)=e^{-r}$. However,
they can be further relaxed. On the one hand, it is sufficient to assume that
the kernel $L$ is twice continuously differentiable except for finitely many
points on $[0,\infty)$. On the other hand, as long as the kernel $L$ satisfies
$C_{L,q}=-\frac{\int_{0}^{\infty}L^{\prime}(r)r^{\frac{q}{2}-1}dr}{\int_{0}^{\infty}L(r)r^{\frac{q}{2}-1}dr}>0$
and the true directional density $f$ is positive almost everywhere on
$\Omega_{q}$, Lemma 4.2 demonstrates that
$\left|\left|\nabla\widehat{f}_{h}(\bm{x})\right|\right|_{2}\to\infty$ with
probability tending to 1 when $h\to 0$ and $nh^{q}\to\infty$. Therefore, our
upper bound on
$\left|\left|\underline{\widehat{\bm{x}}}^{(t+1)}-\underline{\widehat{\bm{x}}}^{(t)}\right|\right|_{2}$
in our proof of (c) will be asymptotically valid for all $t\geq 0$, even
without the strict decreasing property of kernel $L$. Under such relaxation,
our conclusions in Proposition 4.3 are applicable to directional SCMS
algorithms with other kernels that have bounded supports on $[0,\infty)$.

######  Proposition 4.4 (Convergence of the SCGA Algorithm on $\Omega_{q}$).

For any SCGA sequence
$\big{\\{}\underline{\bm{x}}^{(t)}\big{\\}}_{t=0}^{\infty}\subset\Omega_{q}$
defined by (44) with
$0<\underline{\eta}<\frac{2}{q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}}$,
the following properties hold:

  1. (a)

Under condition (A1), the objective function sequence
$\big{\\{}f(\underline{\bm{x}}^{(t)})\big{\\}}_{t=0}^{\infty}$ is non-
decreasing and thus converges.

  2. (b)

Under condition (A1),
$\lim_{t\to\infty}\left|\left|\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right|\right|_{2}=\lim_{t\to\infty}d_{g}\left(\underline{\bm{x}}^{(t+1)},\underline{\bm{x}}^{(t)}\right)=0$.

  3. (c)

Under conditions (A1-3),
$\lim_{t\to\infty}d_{g}\left(\underline{\bm{x}}^{(t)},\underline{R}_{d}\right)=0$
whenever $\underline{\bm{x}}^{(0)}\in\underline{R}_{d}\oplus\underline{r}_{1}$
with the convergence radius $\underline{r}_{1}$ satisfying

$0<\underline{r}_{1}<\min\left\\{\underline{\rho}/2,\frac{\min\left\\{\underline{\beta}_{1},1\right\\}^{2}}{\underline{A}_{2}\left(\left|\left|f\right|\right|_{\infty}^{(3)}+\left|\left|f\right|\right|_{\infty}^{(4)}\right)},2\sin\left(\frac{\underline{\beta}_{1}}{2\underline{A}_{4}(f)}\right)\right\\},$

where $\underline{A}_{2}$ is a constant defined in (h) of Lemma G.1 while
$\underline{A}_{4}(f)>0$ is a quantity depending on both the dimension $q$ and
the functional norm $\left|\left|f\right|\right|_{\infty,4}^{*}$ up to the
fourth-order (partial) derivatives of $f$.

###### Proof of Proposition 4.4.

The proof is similar to our arguments in Proposition 3.3. For the
completeness, we still delineate the detailed steps because the proof requires
some nontrivial techniques, such as parallel transports and line integrals, on
general Riemannian manifolds.

(a) We first derive the following property of the objective function $f$
supported on $\Omega_{q}$, which is a counterpart of _Fact 1_ in the proof of
Proposition 3.3.

$\bullet$ _Property 1_. Given (A1), the function $f$ is
$q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}$-smooth on
$\Omega_{q}$, that is, $\mathtt{grad}\,f$ is
$q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}$-Lipschitz.
This property follows easily from the differentiability of $f$ guaranteed by
condition (A1) and Theorem 4.34 in Lee (2018) that

$\displaystyle\begin{split}\left|\left|\mathtt{grad}\,f(\bm{y})-\Gamma_{\bm{x}}^{\bm{y}}\left(\mathtt{grad}\,f(\bm{x})\right)\right|\right|_{2}&\leq\left|\left|\mathcal{H}f(\widetilde{\bm{y}})\right|\right|_{2}\cdot\left|\left|\mathtt{Exp}_{\bm{y}}^{-1}(\bm{x})\right|\right|_{2}\\\
&\leq
q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}\cdot\left|\left|\mathtt{Exp}_{\bm{y}}^{-1}(\bm{x})\right|\right|_{2}\end{split}$
(83)

for any $\bm{x},\bm{y}\in\Omega_{q}$, where $\widetilde{\bm{y}}$ lies on the
geodesic curve $\varphi:[0,1]\to\Omega_{q}$ with
$\varphi(0)=\bm{x},\varphi(1)=\bm{y}$, and
$\varphi^{\prime}(0)=\mathtt{Exp}_{\bm{x}}^{-1}(\bm{y})$. Then,

$\displaystyle\begin{split}&\left|f(\bm{y})-f(\bm{x})-\langle\mathtt{grad}\,f(\bm{x}),\mathtt{Exp}_{\bm{x}}^{-1}(\bm{y})\rangle\right|\\\
&\stackrel{{\scriptstyle\text{(i)}}}{{=}}\left|\int_{0}^{1}\langle\mathtt{grad}\,f(\varphi(t)),\varphi^{\prime}(t)\rangle
dt-\langle\mathtt{grad}\,f(\bm{x}),\mathtt{Exp}_{\bm{x}}^{-1}(\bm{y})\rangle\right|\\\
&\stackrel{{\scriptstyle\text{(ii)}}}{{=}}\left|\int_{0}^{1}\left\langle\Gamma_{\varphi(t)}^{\bm{x}}\left(\mathtt{grad}\,f(\varphi(t))\right),\Gamma_{\varphi(t)}^{\bm{x}}\left(\varphi^{\prime}(t)\right)\right\rangle
dt-\langle\mathtt{grad}\,f(\bm{x}),\mathtt{Exp}_{\bm{x}}^{-1}(\bm{y})\rangle\right|\\\
&\stackrel{{\scriptstyle\text{(iii)}}}{{=}}\left|\int_{0}^{1}\left\langle\Gamma_{\varphi(t)}^{\bm{x}}\left(\mathtt{grad}\,f(\varphi(t))\right)-\mathtt{grad}\,f(\bm{x}),\mathtt{Exp}_{\bm{x}}^{-1}(\bm{y})\right\rangle\right|\\\
&\leq\int_{0}^{1}\left|\left|\Gamma_{\varphi(t)}^{\bm{x}}\left(\mathtt{grad}\,f(\varphi(t))\right)-\mathtt{grad}\,f(\bm{x})\right|\right|_{2}\cdot\left|\left|\mathtt{Exp}_{\bm{x}}^{-1}(\bm{y})\right|\right|_{2}dt\\\
&\stackrel{{\scriptstyle\text{(iv)}}}{{\leq}}q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}\left|\left|\mathtt{Exp}_{\bm{x}}^{-1}(\bm{y})\right|\right|_{2}\int_{0}^{1}d_{g}(\varphi(t),\bm{x})\,dt\\\
&\leq
q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}\left|\left|\mathtt{Exp}_{\bm{x}}^{-1}(\bm{y})\right|\right|_{2}\int_{0}^{1}\left|\left|t\cdot\mathtt{Exp}_{\bm{x}}^{-1}(\bm{y})\right|\right|_{2}\,dt\\\
&=\frac{q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}}{2}\left|\left|\mathtt{Exp}_{\bm{x}}^{-1}(\bm{y})\right|\right|_{2}^{2},\end{split}$
(84)

where the equality (i) follows from the fundamental theorem for line integrals
(Theorem 11.39 in Lee 2012), equality (ii) utilizes the isometric property of
parallel transports, and inequality (iv) follows from (83). Moreover, since
the velocity of the geodesic $\varphi$ is always constant, we deduce that
$\Gamma_{\varphi(t)}^{\bm{x}}\left(\varphi^{\prime}(t)\right)=\varphi^{\prime}(0)=\mathtt{Exp}_{\bm{x}}^{-1}(\bm{y})$
and the equality (iii) follows. We will make use of the following direction of
the inequality (84):

$f(\bm{y})-f(\bm{x})-\left\langle\mathtt{grad}\,f(\bm{x}),\mathtt{Exp}_{\bm{x}}^{-1}(\bm{y})\right\rangle\geq-\frac{q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}}{2}\left|\left|\mathtt{Exp}_{\bm{x}}^{-1}(\bm{y})\right|\right|_{2}^{2}.$
(85)

Moreover, when
$0<\underline{\eta}<\frac{2}{q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}}$,

$\displaystyle f(\underline{\bm{x}}^{(t+1)})-f(\underline{\bm{x}}^{(t)})$
$\displaystyle=f\left(\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}\left(\underline{\eta}\cdot\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right)\right)-f(\underline{\bm{x}}^{(t)})$
$\displaystyle\geq\left\langle\mathtt{grad}\,f(\underline{\bm{x}}^{(t)}),\,\eta\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right\rangle$
$\displaystyle\quad-\frac{q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}}{2}\cdot\eta^{2}\left|\left|\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right|\right|_{2}^{2}$
$\displaystyle=\underline{\eta}\left(1-\frac{q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}\underline{\eta}}{2}\right)\left|\left|\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right|\right|_{2}^{2}\geq
0,$

showing that the objective function $f$ is non-decreasing along the SCGA path
$\big{\\{}\underline{\bm{x}}^{(t)}\big{\\}}_{t=0}^{\infty}$ on $\Omega_{q}$.
Given the compactness of $\Omega_{q}$ and the differentiability of $f$, we
know that the sequence
$\left\\{f(\underline{\bm{x}}^{(t)})\right\\}_{t=0}^{\infty}$ is bounded.
Thus, it converges.

(b) From (a), we know that when
$0<\underline{\eta}<\frac{2}{q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}}$,

$\displaystyle f(\underline{\bm{x}}^{(t+1)})-f(\underline{\bm{x}}^{(t)})$
$\displaystyle\geq\underline{\eta}\left(1-\frac{q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}\underline{\eta}}{2}\right)\left|\left|\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right|\right|_{2}^{2}$
$\displaystyle=\left(\frac{2-q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}\underline{\eta}}{2\underline{\eta}}\right)d_{g}\left(\underline{\bm{x}}^{(t+1)},\underline{\bm{x}}^{(t)}\right)^{2}.$

Since the sequence
$\left\\{f(\underline{\bm{x}}^{(t)})\right\\}_{t=0}^{\infty}$ converges, it
follows that

$\lim_{t\to\infty}\left|\left|\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right|\right|_{2}=0\quad\text{
and
}\quad\lim_{t\to\infty}d_{g}\left(\underline{\bm{x}}^{(t+1)},\underline{\bm{x}}^{(t)}\right)=0.$

Recall from (6) that
$\left|\left|\underline{\bm{x}}^{(t)}-\underline{\bm{x}}^{(t+1)}\right|\right|_{2}=2\sin\left(\frac{d_{g}\left(\underline{\bm{x}}^{(t+1)},\underline{\bm{x}}^{(t)}\right)}{2}\right)$,
so
$\lim_{t\to\infty}\left|\left|\underline{\bm{x}}^{(t)}-\underline{\bm{x}}^{(t+1)}\right|\right|_{2}=0$
as well.

(c) Given condition (A2) and the fact that
$\underline{r}_{1}<\underline{\rho}/2$, we know that

$\bm{x}\in(\underline{R}_{d}\oplus\underline{r}_{1})\cap\Omega_{q}\text{ and
}\left|\left|\underline{V}_{d}(\bm{x})^{T}\mathtt{grad}\,f(\bm{x})\right|\right|_{2}=0\quad\text{
if and only if }\quad\bm{x}\in\underline{R}_{d}.$

Let
$\underline{\bm{z}}^{(t)}=\pi_{\underline{R}_{d}}(\underline{\bm{x}}^{(t)})$
be the projection of $\underline{\bm{x}}^{(t)}\in\Omega_{q}$ in the SCGA
sequence onto the directional ridge $\underline{R}_{d}$. Since
$\underline{r}_{1}\leq\mathtt{reach}(\underline{R}_{d})$ by (h) of Lemma G.1,
$\underline{\bm{z}}^{(t)}$ is well-defined when
$\underline{\bm{x}}^{(t)}\in\left(\underline{R}_{d}\oplus\underline{r}_{1}\right)\cap\Omega_{q}$.
Recall from (71) that the column space of

$\displaystyle\left(\bm{I}_{q+1}-\bm{z}^{(t)}\left(\bm{z}^{(t)}\right)^{T}\right)\underline{M}(\underline{\bm{z}}^{(t)})$
$\displaystyle=\left(\bm{I}_{q+1}-\bm{z}^{(t)}\left(\bm{z}^{(t)}\right)\right)^{T}\nabla\left[\underline{V}_{d}(\underline{\bm{z}}^{(t)})^{T}\nabla
f(\underline{\bm{z}}^{(t)})\right]^{T}\in\mathbb{R}^{(q+1)\times(q-d)}$

coincides with the normal space of $\underline{R}_{d}$ within the tangent
space $T_{\underline{\bm{z}}^{(t)}}$. We define a geodesic
$\varphi:[0,1]\to\Omega_{q}$ with
$\varphi(0)=\underline{\bm{z}}^{(t)},\varphi(1)=\underline{\bm{x}}^{(t)},\varphi^{\prime}(0)=\mathtt{Exp}_{\underline{\bm{z}}^{(t)}}^{-1}(\underline{\bm{x}}^{(t)})$
and calculate that

$\displaystyle\left|\left|\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\nabla
f(\underline{\bm{x}}^{(t)})\right|\right|_{2}$
$\displaystyle=\left|\left|\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\nabla
f(\underline{\bm{x}}^{(t)})-\underbrace{\underline{V}_{d}(\underline{\bm{z}}^{(t)})^{T}\nabla
f(\underline{\bm{z}}^{(t)})}_{=0}\right|\right|_{2}$
$\displaystyle=\left|\left|\int_{0}^{1}\left\langle\nabla\left[\underline{V}_{d}(\underline{\bm{z}}^{(t)})^{T}\nabla
f(\underline{\bm{z}}^{(t)})\right]^{T},\varphi^{\prime}(\epsilon)\right\rangle
d\epsilon\right|\right|_{2}\quad\text{ by Theorem 11.39 in
\cite[cite]{\@@bibref{Authors
Phrase1YearPhrase2}{Lee2012}{\@@citephrase{(}}{\@@citephrase{)}}}}$
$\displaystyle\stackrel{{\scriptstyle\text{(i)}}}{{=}}\left|\left|\left\langle\underline{M}(\varphi(0)),\varphi^{\prime}(0)\right\rangle+\int_{0}^{1}\left[\left\langle\underline{M}(\varphi(\epsilon)),\varphi^{\prime}(\epsilon)\right\rangle-\left\langle\Gamma_{\varphi(0)}^{\varphi(\epsilon)}\left(\underline{M}(\varphi(0))\right),\Gamma_{\varphi(0)}^{\varphi(\epsilon)}\left(\varphi^{\prime}(0)\right)\right\rangle\right]d\epsilon\right|\right|_{2}$
$\displaystyle\stackrel{{\scriptstyle\text{(ii)}}}{{\geq}}\left|\left|\underline{M}(\underline{\bm{z}}^{(t)})^{T}\mathtt{Exp}_{\underline{\bm{z}}^{(t)}}^{-1}(\underline{\bm{x}}^{(t)})\right|\right|_{2}-\left|\left|\int_{0}^{1}\left\langle\underline{M}(\varphi(\epsilon))-\Gamma_{\varphi(0)}^{\varphi(\epsilon)}\left(\underline{M}(\varphi(0))\right),\varphi^{\prime}(\epsilon)\right\rangle
d\epsilon\right|\right|$
$\displaystyle\geq\left|\left|\underline{M}(\underline{\bm{z}}^{(t)})^{T}\left(\bm{I}_{q+1}-\underline{\bm{z}}^{(t)}\left(\underline{\bm{z}}^{(t)}\right)^{T}\right)\cdot\mathtt{Exp}_{\underline{\bm{z}}^{(t)}}^{-1}(\underline{\bm{x}}^{(t)})\right|\right|_{2}$
$\displaystyle\quad-\int_{0}^{1}\left|\left|\underline{M}(\varphi(\epsilon))-\Gamma_{\varphi(0)}^{\varphi(\epsilon)}\left(\underline{M}(\varphi(0))\right)\right|\right|_{2}\cdot\left|\left|\varphi^{\prime}(\epsilon)\right|\right|_{2}d\epsilon$
$\displaystyle\geq\left|\left|\left[\left(\bm{I}_{q+1}-\underline{\bm{z}}^{(t)}\left(\underline{\bm{z}}^{(t)}\right)^{T}\right)\underline{M}(\underline{\bm{z}}^{(t)})\right]^{T}\mathtt{Exp}_{\underline{\bm{z}}^{(t)}}^{-1}(\underline{\bm{x}}^{(t)})\right|\right|_{2}$
$\displaystyle\quad-\left|\left|\mathtt{Exp}_{\underline{\bm{z}}^{(t)}}^{-1}(\underline{\bm{x}}^{(t)})\right|\right|_{2}\int_{0}^{1}\sup_{\epsilon\in[0,1]}\left|\left|\bar{\nabla}\underline{M}\left(\varphi(\epsilon)\right)\right|\right|_{2}\cdot\epsilon\cdot\left|\left|\mathtt{Exp}_{\underline{\bm{z}}^{(t)}}^{-1}(\underline{\bm{x}}^{(t)})\right|\right|_{2}d\epsilon$
by Theorem 4.34 in Lee (2018)
$\displaystyle\stackrel{{\scriptstyle\text{(iii)}}}{{\geq}}\underline{\beta}_{1}\cdot
d_{g}\left(\underline{\bm{x}}^{(t)},\underline{\bm{z}}^{(t)}\right)-\frac{\underline{A}_{4}(f)}{2}\cdot
d_{g}\left(\underline{\bm{x}}^{(t)},\underline{\bm{z}}^{(t)}\right)^{2}$
$\displaystyle=d_{g}\left(\underline{\bm{x}}^{(t)},\underline{\bm{z}}^{(t)}\right)\left(\underline{\beta}_{1}-\frac{\underline{A}_{4}(f)}{2}\cdot
d_{g}\left(\underline{\bm{x}}^{(t)},\underline{\bm{z}}^{(t)}\right)\right)$
$\displaystyle\stackrel{{\scriptstyle\text{(iv)}}}{{\geq}}\frac{\underline{\beta}_{1}}{2}\cdot
d_{g}\left(\underline{\bm{x}}^{(t)},\underline{\bm{z}}^{(t)}\right)$

where we utilize the isometric properties of parallel transports in (i), note
that the velocity of geodesic is constant, _i.e._ ,
$\varphi^{\prime}(0)=\varphi^{\prime}(\epsilon)$ for any $\epsilon\in[0,1]$ to
obtain (ii), leverage (d) of Lemma G.1 to deduce (iii) and use the fact that
$d_{g}\left(\underline{\bm{x}}^{(t)},\underline{\bm{z}}^{(t)}\right)\leq\frac{\underline{\beta}_{1}}{\underline{A}_{4}(f)}$
when
$\underline{\bm{x}}^{(t)}\in\left(\underline{R}_{d}\oplus\underline{r}_{1}\right)\cap\Omega_{q}$
in the inequality (iv). In particular for the inequality (iii),
$\left(\bm{I}_{q+1}-\underline{\bm{z}}^{(t)}\left(\underline{\bm{z}}^{(t)}\right)^{T}\right)\underline{M}(\underline{\bm{z}}^{(t)})$
is a full column rank matrix and
$\mathtt{Exp}_{\underline{\bm{z}}^{(t)}}^{-1}(\underline{\bm{x}}^{(t)})$ lies
within the column space of
$\left(\bm{I}_{q+1}-\underline{\bm{z}}^{(t)}\left(\underline{\bm{z}}^{(t)}\right)^{T}\right)\underline{M}(\underline{\bm{z}}^{(t)})$.
Since the nonzero singular values of
$\left(\bm{I}_{q+1}-\underline{\bm{z}}^{(t)}\left(\underline{\bm{z}}^{(t)}\right)^{T}\right)\underline{M}(\underline{\bm{z}}^{(t)})$
are lower bounded by $\underline{\beta}_{1}>0$, it follows that

$\left|\left|\left[\left(\bm{I}_{q+1}-\underline{\bm{z}}^{(t)}\left(\underline{\bm{z}}^{(t)}\right)^{T}\right)\underline{M}(\underline{\bm{z}}^{(t)})\right]^{T}\mathtt{Exp}_{\underline{\bm{z}}^{(t)}}^{-1}(\underline{\bm{x}}^{(t)})\right|\right|_{2}\geq\underline{\beta}_{1}d_{g}\left(\underline{\bm{x}}^{(t)},\underline{\bm{z}}^{(t)}\right).$

In addition, we also know that $\underline{A}_{4}(f)>0$ comes from the
supremum norm of $\bar{\nabla}\underline{M}(\bm{x})$ over the geodesic
connecting $\underline{\bm{x}}^{(t)}$ and $\underline{\bm{z}}^{(t)}$ with
$\bar{\nabla}$ being the Riemannian connection, which in turn depends on the
uniform functional norm $\left|\left|f\right|\right|_{\infty,4}^{*}$ of the
partial derivatives of $f$ up to the fourth order. By (b), we deduce that

$\lim_{t\to\infty}d_{g}\left(\underline{\bm{x}}^{(t)},\underline{\bm{z}}^{(t)}\right)=d_{g}\left(\underline{\bm{x}}^{(t)},\underline{R}_{d}\right)=0.$

The results follow. ∎

The nonzero curvature structure of the unit (hyper-sphere) $\Omega_{q}$, on
which the objective function (or density) $f$ lies, induces an extra challenge
in establishing the linear convergence of population and sample-based SCGA
algorithms. Some useful techniques used in analyzing non-asymptotic
convergence of first-order methods in $\mathbb{R}^{q+1}$, such as the law of
cosines and linearizations of the objective function, would fail on
$\Omega_{q}$ (Zhang and Sra, 2016). Therefore, we first introduce a practical
trigonometric distance bound for the Alexandrov space (Burago et al., 1992)
with its sectional curvature bounded from below.

######  Lemma I.1 (Lemma 5 in Zhang and Sra (2016); see also Bonnabel (2013)).

If $a,b,c$ are the sides (_i.e._ , side lengths) of a geodesic triangle in an
Alexandrov space with sectional curvature lower bounded by $\kappa$, and $A$
is the angle between sides $b$ and $c$, then

$a^{2}\leq\frac{\sqrt{|\kappa|}c}{\tanh(\sqrt{|\kappa|}c)}b^{2}+c^{2}-2bc\cos(A).$
(86)

The sketching proof of Lemma I.1 can be founded in Lemma 5 of Zhang and Sra
(2016). Note that the sectional curvature $\kappa=1$ on $\Omega_{q}$. We
inherit the notation in Zhang and Sra (2016) and denote
$\frac{\sqrt{|\kappa|}c}{\tanh(\sqrt{|\kappa|}c)}$ by $\zeta(\kappa,c)$ for
the curvature dependent quantity in the inequality (86). One can show by
differentiating $\zeta(\kappa,c)$ with respect to $c$ that $\zeta(\kappa,c)$
is strictly increasing and greater than 1 for any $c>0$ and fixed $\kappa\neq
0$. With Lemma I.1 in hand, we are able to state a straightforward corollary
indicating an important relation between two consecutive points in the SCGA
sequence $\big{\\{}\underline{\bm{x}}^{(t)}\big{\\}}_{t=0}^{\infty}$ on
$\Omega_{q}$ defined by (44):

$\underline{\bm{x}}^{(t+1)}=\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}\left(\underline{\eta}\cdot\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right).$
(87)

######  Corollary I.2.

For any point $\bm{y},\underline{\bm{x}}^{(t)}$ in a geodesically convex set
on $\Omega_{q}$, the update in (87) satisfies

$\displaystyle
2\underline{\eta}\left\langle\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\nabla
f(\underline{\bm{x}}^{(t)}),\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\bm{y})\right\rangle$
$\displaystyle\leq
d_{g}\left(\underline{\bm{x}}^{(t)},\bm{y}\right)^{2}-d_{g}\left(\underline{\bm{x}}^{(t+1)},\bm{y}\right)^{2}+\zeta\left(1,d_{g}(\underline{\bm{x}}^{(t)},\bm{y})\right)\cdot\underline{\eta}^{2}\left|\left|\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right|\right|_{2}^{2},$

where
$d_{g}(\bm{x},\bm{y})=\sqrt{\left\langle\mathtt{Exp}_{\bm{x}}^{-1}(\bm{y}),\mathtt{Exp}_{\bm{x}}^{-1}(\bm{y})\right\rangle}=\left|\left|\mathtt{Exp}_{\bm{x}}^{-1}(\bm{y})\right|\right|_{2}$
is the geodesic distance between $\bm{x}$ and $\bm{y}$ on $\Omega_{q}$.

###### Proof of Corollary I.2.

Recall that the (population) SCGA iterative formula on $\Omega_{q}$ is given
by
$\underline{\bm{x}}^{(t+1)}=\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}\left(\underline{\eta}\cdot\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right)$.
Note that for the geodesic triangle
$\triangle\underline{\bm{x}}^{(t)}\underline{\bm{x}}^{(t+1)}\bm{y}$ with
$\bm{y}\in\Omega_{q}$, we have that

$d_{g}(\underline{\bm{x}}^{(t)},\underline{\bm{x}}^{(t+1)})=\underline{\eta}\left|\left|\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right|\right|_{2}=\underline{\eta}\left|\left|\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right|\right|_{2}$

and

$\displaystyle d_{g}(\underline{\bm{x}}^{(t)},\underline{\bm{x}}^{(t+1)})\cdot
d_{g}(\underline{\bm{x}}^{(t)},\bm{y})\cdot\cos\left(\angle\underline{\bm{x}}^{(t+1)}\underline{\bm{x}}^{(t)}\bm{y}\right)$
$\displaystyle=\underline{\eta}\left\langle\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)}),\,\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\bm{y})\right\rangle.$

By letting
$a=\overline{\underline{\bm{x}}^{(t+1)}\bm{y}},b=\overline{\underline{\bm{x}}^{(t+1)}\underline{\bm{x}}^{(t)}},c=\overline{\underline{\bm{x}}^{(t)}\bm{y}}$,
and $A=\angle\underline{\bm{x}}^{(t+1)}\underline{\bm{x}}^{(t)}\bm{y}$ in
Lemma I.1, we obtain that

$\displaystyle d_{g}(\underline{\bm{x}}^{(t+1)},\bm{y})^{2}$
$\displaystyle\leq\zeta\left(1,d_{g}(\underline{\bm{x}}^{(t)},\bm{y})\right)\cdot\underline{\eta}^{2}\left|\left|\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right|\right|_{2}^{2}$
$\displaystyle\quad+d_{g}(\underline{\bm{x}}^{(t)},\bm{y})^{2}-2\underline{\eta}\left\langle
V_{d}(\underline{\bm{x}}^{(t)})V_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)}),\,\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\bm{y})\right\rangle.$

Some rearrangements will yield the final display. ∎

Note that $\left(\underline{R}_{d}\oplus\underline{\rho}\right)\cap\Omega_{q}$
in our conditions (A2-3) is a geodesically convex set, where the minimal
geodesic between two points in the set
$\left(\underline{R}_{d}\oplus\underline{\rho}\right)\cap\Omega_{q}$ always
lies within the set. Hence, Corollary I.2 is applicable to our interested SCGA
algorithm initialized within
$\left(\underline{R}_{d}\oplus\underline{\rho}\right)\cap\Omega_{q}$.

######  Theorem 4.6 (Linear Convergence of the SCGA Algorithm on
$\Omega_{q}$).

Assume conditions (A1-4) throughout the theorem.

  1. (a)

Q-Linear convergence of
$d_{g}(\underline{\bm{x}}^{(t)},\underline{\bm{x}}^{*})$: Consider a
convergence radius $\underline{r}_{2}>0$ satisfying

$\displaystyle 0<\underline{r}_{2}$
$\displaystyle\leq\min\Bigg{\\{}\underline{\rho}/2,\frac{\underline{\beta}_{1}^{2}}{\underline{A}_{2}\left(\left|\left|f\right|\right|_{\infty}^{(3)}+\left|\left|f\right|\right|_{\infty}^{(4)}\right)},\frac{\underline{\beta}_{1}}{\underline{A}_{4}(f)},$
$\displaystyle
2\sin\Bigg{[}\frac{3\underline{\beta}_{0}}{8q\left(12\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}\underline{\beta}_{2}^{2}\arcsin\left(\underline{\rho}/2\right)+\sqrt{q}\left|\left|f\right|\right|_{\infty}^{(3)}\right)}\Bigg{]}\Bigg{\\}},$

where $\underline{A}_{2}>0$ is the constant defined in (h) of Lemma G.1 and
$\underline{A}_{4}(f)>0$ is a quantity defined in (c) of Proposition 4.4 that
depends on both the dimension $q$ and the functional norm
$\left|\left|f\right|\right|_{\infty,4}^{*}$ up to the fourth-order (partial)
derivatives of $f$. Whenever
$0<\underline{\eta}\leq\min\left\\{\frac{4}{\underline{\beta}_{0}},\frac{1}{q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}\cdot\zeta(1,\underline{\rho})}\right\\}$
and the initial point
$\underline{\bm{x}}^{(0)}\in\text{Ball}_{q+1}(\underline{\bm{x}}^{*},\underline{r}_{2})\cap\Omega_{q}$
with $\underline{\bm{x}}^{*}\in\underline{R}_{d}$, we have that

$d_{g}(\underline{\bm{x}}^{(t)},\underline{\bm{x}}^{*})\leq\underline{\Upsilon}^{t}\cdot
d_{g}(\underline{\bm{x}}^{(0)},\underline{\bm{x}}^{*})\quad\text{ with
}\quad\underline{\Upsilon}=\sqrt{1-\frac{\underline{\beta}_{0}\underline{\eta}}{4}}.$

  2. (b)

R-Linear convergence of $d_{g}(\underline{\bm{x}}^{(t)},\underline{R}_{d})$:
Under the same radius $\underline{r}_{2}>0$ in (a), we have that whenever
$0<\underline{\eta}\leq\min\left\\{\frac{4}{\underline{\beta}_{0}},\frac{1}{q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}\cdot\zeta(1,\underline{\rho})}\right\\}$
and the initial point
$\underline{\bm{x}}^{(0)}\in\text{Ball}_{q+1}(\underline{\bm{x}}^{*},\underline{r}_{2})\cap\Omega_{q}$
with $\underline{\bm{x}}^{*}\in\underline{R}_{d}$,

$d_{g}(\underline{\bm{x}}^{(t)},\underline{R}_{d})\leq\underline{\Upsilon}^{t}\cdot
d_{g}(\underline{\bm{x}}^{(0)},\underline{\bm{x}}^{*})\quad\text{ with
}\quad\underline{\Upsilon}=\sqrt{1-\frac{\underline{\beta}_{0}\underline{\eta}}{4}}.$

We further assume (D1-2) in the rest of statements. Suppose that $h\to 0$ and
$\frac{nh^{q+4}}{|\log h|}\to\infty$.

  1. (c)

Q-Linear convergence of
$d_{g}(\widehat{\underline{\bm{x}}}^{(t)},\underline{\bm{x}}^{*})$: Under the
same radius $\underline{r}_{2}>0$ and
$\underline{\Upsilon}=\sqrt{1-\frac{\underline{\beta}_{0}\underline{\eta}}{4}}$
in (a), we have that

$d_{g}(\widehat{\underline{\bm{x}}}^{(t)},\underline{\bm{x}}^{*})\leq\underline{\Upsilon}^{t}\cdot
d_{g}(\widehat{\underline{\bm{x}}}^{(0)},\underline{\bm{x}}^{*})+O(h^{2})+O_{P}\left(\sqrt{\frac{|\log
h|}{nh^{q+4}}}\right)$

with probability tending to 1 whenever
$0<\underline{\eta}\leq\min\left\\{\frac{4}{\underline{\beta}_{0}},\frac{1}{q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}\cdot\zeta(1,\underline{\rho})}\right\\}$
and the initial point
$\widehat{\underline{\bm{x}}}^{(0)}\in\text{Ball}_{q+1}(\underline{\bm{x}}^{*},\underline{r}_{2})\cap\Omega_{q}$
with $\underline{\bm{x}}^{*}\in\underline{R}_{d}$.

  1. (d)

R-Linear convergence of
$d_{g}(\widehat{\underline{\bm{x}}}^{(t)},\underline{R}_{d})$: Under the same
radius $\underline{r}_{2}>0$ and
$\underline{\Upsilon}=\sqrt{1-\frac{\underline{\beta}_{0}\underline{\eta}}{4}}$
in (a), we have that

$d_{g}(\widehat{\underline{\bm{x}}}^{(t)},\underline{R}_{d})\leq\underline{\Upsilon}^{t}\cdot
d_{g}(\widehat{\underline{\bm{x}}}^{(0)},\underline{\bm{x}}^{*})+O(h^{2})+O_{P}\left(\sqrt{\frac{|\log
h|}{nh^{q+4}}}\right)$

with probability tending to 1 whenever
$0<\underline{\eta}\leq\min\left\\{\frac{4}{\underline{\beta}_{0}},\frac{1}{q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}\cdot\zeta(1,\underline{\rho})}\right\\}$
and the initial point
$\widehat{\underline{\bm{x}}}^{(0)}\in\text{Ball}_{q+1}(\underline{\bm{x}}^{*},\underline{r}_{2})\cap\Omega_{q}$
with $\underline{\bm{x}}^{*}\in\underline{R}_{d}$.

###### Proof of Theorem 4.6.

The proof is similar to our argument in Theorem 3.6, except that the objective
function $f$ is supported on a nonlinear manifold $\Omega_{q}$ here. The key
arguments are credited to Corollary I.2. We first recall the following two
properties.
$\bullet$ _Property 1_. Given (A1), the function $f$ is
$q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}$-smooth on
$\Omega_{q}$, that is, $\mathtt{grad}\,f$ is
$q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}$-Lipschitz.
$\bullet$ _Property 2_. Given conditions (A1-3), we know that
$\left|\left|\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right|\right|_{2}>0\text{
for any
}\underline{\bm{x}}^{(t)}\in\big{(}\text{Ball}_{q+1}(\underline{\bm{x}}^{*},\underline{r}_{2})\cap\Omega_{q}\big{)}\setminus\underline{R}_{d}$
and

$f(\underline{\bm{x}}^{*})-f\left(\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}\left(\frac{1}{q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}}\cdot\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right)\right)\geq
0$

for any
$\underline{\bm{x}}^{(t)}\in\text{Ball}_{q+1}(\underline{\bm{x}}^{*},\underline{r}_{2})\cap\Omega_{q}$
with $\underline{\bm{x}}^{*}\in\underline{R}_{d}$.

_Property 1_ has been established in the proof of Proposition 4.4, indicating
that the objective function sequence
$\left\\{f(\underline{\bm{x}}^{(t)})\right\\}_{t=0}^{\infty}$ is non-
decreasing when
$0<\underline{\eta}<\frac{2}{q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}}$.
_Property 2_ is a natural corollary by Proposition 4.4, because
$\underline{\bm{x}}^{(t)}\in\text{Ball}(\underline{\bm{x}}^{*},\underline{r}_{2})\cap\Omega_{q}$
and

$f\left(\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}\left(\frac{1}{q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}}\cdot\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right)\right)$

is the objective function value after one-step SCGA iteration on $\Omega_{q}$
with step size
$\frac{1}{q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}}$. The
iteration will move $\underline{\bm{x}}^{(t)}$ closer to the directional ridge
$\underline{R}_{d}$. With the help of these two properties, we start the
proofs of (a-d).

(a) We first prove the following claim using Lemma E.1: for all $t\geq 0$ and
$\underline{\bm{x}}^{(0)}\in\text{Ball}_{q+1}(\underline{\bm{x}}^{*},\underline{r}_{2})\cap\Omega_{q}$,

$\displaystyle\begin{split}f(\underline{\bm{x}}^{*})-f(\underline{\bm{x}}^{(t)})&\leq\left\langle\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)}),\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})\right\rangle-\frac{\underline{\beta}_{0}}{4}\cdot
d_{g}(\underline{\bm{x}}^{*},\underline{\bm{x}}^{(t)})^{2}+\underline{\epsilon}_{t},\end{split}$
(88)

where
$\underline{\epsilon}_{t}=\left[2q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}\underline{\beta}_{2}^{2}\arcsin\left(\underline{\rho}/2\right)+\frac{q^{\frac{3}{2}}\left|\left|f\right|\right|_{\infty}^{(3)}}{6}\right]=o\left(d_{g}(\underline{\bm{x}}^{*},\underline{\bm{x}}^{(t)})^{2}\right)$.
By the differentiability of $f$ ensured by condition (A1) and Taylor’s theorem
on $\Omega_{q}$, we deduce that

$\displaystyle f(\underline{\bm{x}}^{*})-f(\underline{\bm{x}}^{(t)})$
$\displaystyle\leq\left\langle\mathtt{grad}\,f(\underline{\bm{x}}^{(t)}),\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})\right\rangle+\frac{1}{2}\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})^{T}\left[\mathcal{H}f(\underline{\bm{x}}^{(t)})\right]\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})$
$\displaystyle\quad+\frac{q^{\frac{3}{2}}\left|\left|f\right|\right|_{\infty}^{(3)}}{6}\cdot\left|\left|\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})\right|\right|_{2}^{3}$
$\displaystyle\stackrel{{\scriptstyle\text{(i)}}}{{=}}\left\langle\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)}),\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})\right\rangle+\left\langle\underline{U}_{d}^{\perp}(\underline{\bm{x}}^{(t)})\mathtt{grad}\,f(\underline{\bm{x}}^{(t)}),\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})\right\rangle$
$\displaystyle\quad+\frac{1}{2}\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})^{T}\left(\underline{V}_{\diamond}(\underline{\bm{x}}^{(t)}),\underline{V}_{d}(\underline{\bm{x}}^{(t)})\right)\begin{pmatrix}0&&&\\\
&\underline{\lambda}_{1}(\underline{\bm{x}}^{(t)})&&\\\ &&\ddots&\\\
&&&\underline{\lambda}_{q}(\underline{\bm{x}}^{(t)})\end{pmatrix}\begin{pmatrix}\underline{V}_{\diamond}(\underline{\bm{x}}^{(t)})\\\
\underline{V}_{d}(\underline{\bm{x}}^{(t)})\end{pmatrix}\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})$
$\displaystyle\quad+\frac{q^{\frac{3}{2}}\left|\left|f\right|\right|_{\infty}^{(3)}}{6}\cdot
d_{g}(\underline{\bm{x}}^{*},\underline{\bm{x}}^{(t)})^{3}$
$\displaystyle\stackrel{{\scriptstyle\text{(ii)}}}{{\leq}}\left\langle\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)}),\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})\right\rangle+\frac{\underline{\beta}_{0}}{4}\cdot
d_{g}\left(\underline{\bm{x}}^{(t)},\underline{\bm{x}}^{*}\right)^{2}$
$\displaystyle\quad+\frac{\max\left\\{0,\underline{\lambda}_{1}(\underline{\bm{x}}^{(t)})\right\\}}{2}\left|\left|\underline{U}_{d}^{\perp}(\underline{\bm{x}}^{(t)})\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})\right|\right|_{2}^{2}-\frac{\underline{\beta}_{0}}{2}\left|\left|\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})\right|\right|_{2}^{2}$
$\displaystyle\quad+\frac{q^{\frac{3}{2}}\left|\left|f\right|\right|_{\infty}^{(3)}}{6}\cdot
d_{g}(\underline{\bm{x}}^{*},\underline{\bm{x}}^{(t)})^{3}$
$\displaystyle\stackrel{{\scriptstyle\text{(iii)}}}{{\leq}}\left\langle\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)}),\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})\right\rangle+\frac{\underline{\beta}_{0}}{4}\cdot
d_{g}\left(\underline{\bm{x}}^{(t)},\underline{\bm{x}}^{*}\right)^{2}$
$\displaystyle\quad+\frac{\left(\underline{\beta}_{0}+\max\left\\{0,\underline{\lambda}_{1}(\underline{\bm{x}}^{(t)})\right\\}\right)}{2}\left|\left|\underline{U}_{d}^{\perp}(\underline{\bm{x}}^{(t)})\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})\right|\right|_{2}^{2}-\frac{\underline{\beta}_{0}}{2}\left|\left|\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})\right|\right|_{2}^{2}$
$\displaystyle\quad+\frac{q^{\frac{3}{2}}\left|\left|f\right|\right|_{\infty}^{(3)}}{6}\cdot
d_{g}(\underline{\bm{x}}^{*},\underline{\bm{x}}^{(t)})^{3}$
$\displaystyle\stackrel{{\scriptstyle\text{(iv)}}}{{\leq}}\left\langle\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)}),\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})\right\rangle-\frac{\underline{\beta}_{0}}{4}\cdot
d_{g}\left(\underline{\bm{x}}^{(t)},\underline{\bm{x}}^{*}\right)^{2}$
$\displaystyle\quad+\frac{\left(\underline{\beta}_{0}+\max\left\\{0,\underline{\lambda}_{1}(\underline{\bm{x}}^{(t)})\right\\}\right)}{2}\cdot\underline{\beta}_{2}^{2}\cdot
d_{g}\left(\underline{\bm{x}}^{(t)},\underline{\bm{x}}^{*}\right)^{4}+\frac{q^{\frac{3}{2}}\left|\left|f\right|\right|_{\infty}^{(3)}}{6}\cdot
d_{g}(\underline{\bm{x}}^{*},\underline{\bm{x}}^{(t)})^{3}$
$\displaystyle\stackrel{{\scriptstyle\text{(v)}}}{{\leq}}\left\langle\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)}),\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})\right\rangle-\frac{\underline{\beta}_{0}}{4}\cdot
d_{g}(\underline{\bm{x}}^{*},\underline{\bm{x}}^{(t)})^{2}$
$\displaystyle\quad+\left[2q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}\underline{\beta}_{2}^{2}\arcsin\left(\underline{\rho}/2\right)+\frac{q^{\frac{3}{2}}\left|\left|f\right|\right|_{\infty}^{(3)}}{6}\right]d_{g}(\underline{\bm{x}}^{*},\underline{\bm{x}}^{(t)})^{3},$

where we leverage the equality
$\bm{I}_{q+1}=\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}+\underline{U}_{d}^{\perp}(\underline{\bm{x}}^{(t)})$
in (i) and (iii), use conditions (A2) and (A4) that
$\underline{\lambda}_{q}(\underline{\bm{x}}^{(t)})\leq\cdots\leq\underline{\lambda}_{d+1}(\underline{\bm{x}}^{(t)})<-\underline{\beta}_{0}$
and

$\left\langle\underline{U}_{d}^{\perp}(\underline{\bm{x}}^{(t)})\mathtt{grad}\,f(\underline{\bm{x}}^{(t)}),\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})\right\rangle\leq\frac{\underline{\beta}_{0}}{4}\cdot
d_{g}\left(\underline{\bm{x}}^{(t)},\underline{\bm{x}}^{*}\right)^{2}$

in (ii), apply the quadratic bound for
$\left|\left|\underline{U}_{d}^{\perp}(\underline{\bm{x}}^{(t)})\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})\right|\right|_{2}$
in condition (A4) to obtain (iv), and leverage the facts that
$\max\left\\{\underline{\beta}_{0},0,\underline{\lambda}_{1}(\underline{\bm{x}}^{(t)})\right\\}\leq
q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}$ and
$d_{g}(\underline{\bm{x}}^{*},\underline{\bm{x}}^{(t)})\leq
2\arcsin\left(\underline{\rho}/2\right)$ when
$\left|\left|\underline{\bm{x}}^{(t)}-\underline{\bm{x}}^{*}\right|\right|_{2}\leq\underline{\rho}$
in (v); recall (6). Our claim (88) is thus proved.

In addition, given _Property 2_ and any
$\underline{\bm{x}}^{(t)}\in\underline{R}_{d}\oplus\underline{r}_{2}$, we
derive that

$\displaystyle f(\underline{\bm{x}}^{(t)})-f(\underline{\bm{x}}^{*})$
$\displaystyle\leq
f(\underline{\bm{x}}^{(t)})-f(\underline{\bm{x}}^{*})+f(\underline{\bm{x}}^{*})-f\left(\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}\left(\frac{1}{q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}}\cdot\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right)\right)$
$\displaystyle=-\left[f\left(\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}\left(\frac{1}{q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}}\cdot\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right)\right)-f(\underline{\bm{x}}^{(t)})\right]$
$\displaystyle\leq-\Bigg{[}\left\langle\mathtt{grad}\,f(\underline{\bm{x}}^{(t)}),\,\frac{1}{q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}}\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right\rangle$
$\displaystyle\quad\quad-\frac{q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}}{2}\cdot\left|\left|\frac{1}{q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}}\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right|\right|_{2}^{2}\Bigg{]}$
$\displaystyle=-\frac{1}{2q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}}\left|\left|\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right|\right|_{2}^{2},$

where we apply (84) to obtain the inequality. This indicates that

$\left|\left|\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right|\right|_{2}^{2}\leq
2q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}\left[f(\underline{\bm{x}}^{*})-f(\underline{\bm{x}}^{(t)})\right]$
(89)

for any $\underline{\bm{x}}^{(t)}\in\underline{R}_{d}\oplus\underline{r}_{3}$.
Therefore, by Corollary I.2, we obtain that

$\displaystyle d_{g}(\underline{\bm{x}}^{(t+1)},\underline{\bm{x}}^{*})$
$\displaystyle\stackrel{{\scriptstyle\text{(i)}}}{{\leq}}d_{g}(\underline{\bm{x}}^{(t)},\underline{\bm{x}}^{*})-2\underline{\eta}\left\langle\underline{V}_{d}(\underline{\bm{x}}^{(t)})\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)}),\mathtt{Exp}_{\underline{\bm{x}}^{(t)}}^{-1}(\underline{\bm{x}}^{*})\right\rangle$
$\displaystyle\quad+\zeta\left(1,\underline{\rho}\right)\cdot\underline{\eta}^{2}\left|\left|\underline{V}_{d}(\underline{\bm{x}}^{(t)})^{T}\mathtt{grad}\,f(\underline{\bm{x}}^{(t)})\right|\right|_{2}^{2}$
$\displaystyle\stackrel{{\scriptstyle\text{(ii)}}}{{\leq}}d_{g}(\underline{\bm{x}}^{(t)},\underline{\bm{x}}^{*})^{2}+2\underline{\eta}\Bigg{[}f(\underline{\bm{x}}^{(t)})-f(\underline{\bm{x}}^{*})-\frac{\underline{\beta}_{0}}{4}\cdot
d_{g}(\underline{\bm{x}}^{*},\underline{\bm{x}}^{(t)})^{2}$
$\displaystyle\hskip
99.58464pt+\left(2q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}\underline{\beta}_{2}^{2}\arcsin\left(\underline{\rho}/2\right)+\frac{q^{\frac{3}{2}}\left|\left|f\right|\right|_{\infty}^{(3)}}{6}\right)d_{g}(\underline{\bm{x}}^{*},\underline{\bm{x}}^{(t)})^{3}\Bigg{]}$
$\displaystyle\quad+\zeta\left(1,\underline{\rho}\right)\cdot\underline{\eta}^{2}\cdot
2q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}\left[f(\underline{\bm{x}}^{*})-f(\underline{\bm{x}}^{(t)})\right]$
$\displaystyle\stackrel{{\scriptstyle\text{(iii)}}}{{\leq}}\left(1-\frac{\underline{\beta}_{0}\underline{\eta}}{4}\right)\cdot
d_{g}(\underline{\bm{x}}^{*},\underline{\bm{x}}^{(t)})^{2}-2\underline{\eta}\left[1-\underline{\eta}\cdot\zeta\left(1,\underline{\rho}\right)\cdot
q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}\right]\cdot\underbrace{\left[f(\underline{\bm{x}}^{*})-f(\underline{\bm{x}}^{(t)})\right]}_{\geq
0}$
$\displaystyle\leq\left(1-\frac{\underline{\beta}_{0}\underline{\eta}}{4}\right)\cdot
d_{g}(\underline{\bm{x}}^{*},\underline{\bm{x}}^{(t)})^{2}$

whenever
$0<\underline{\eta}\leq\min\left\\{\frac{4}{\underline{\beta}_{0}},\frac{1}{q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}\cdot\zeta\left(1,\underline{\rho}\right)}\right\\}$,
where we utilize Corollary I.2 and the monotonicity of $\zeta(1,c)$ with
respect to $c$ in (i), apply (88) and (89) to obtain (ii), and use the choice
of $\underline{r}_{2}$ to argue that

$\displaystyle\left(2q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}\underline{\beta}_{2}^{2}\arcsin\left(\underline{\rho}/2\right)+\frac{q^{\frac{3}{2}}\left|\left|f\right|\right|_{\infty}^{(3)}}{6}\right)d_{g}(\underline{\bm{x}}^{*},\underline{\bm{x}}^{(t)})^{3}$
$\displaystyle\leq\left(2q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}\underline{\beta}_{2}^{2}\arcsin\left(\underline{\rho}/2\right)+\frac{q^{\frac{3}{2}}\left|\left|f\right|\right|_{\infty}^{(3)}}{6}\right)d_{g}(\underline{\bm{x}}^{*},\underline{\bm{x}}^{(t)})^{2}\cdot
2\arcsin\left(\underline{r}_{2}/2\right)$
$\displaystyle\leq\frac{\underline{\beta}_{0}}{8}\cdot
d_{g}(\underline{\bm{x}}^{*},\underline{\bm{x}}^{(t)})^{2}$

in (iii). By telescoping, we conclude that when
$0<\underline{\eta}\leq\min\left\\{\frac{4}{\underline{\beta}_{0}},\frac{1}{q\left|\left|\mathcal{H}f\right|\right|_{\infty}^{(2)}\cdot\zeta\left(1,\underline{\rho}\right)}\right\\}$
and $\underline{\bm{x}}^{(0)}\in\underline{R}_{d}\oplus\underline{r}_{2}$,

$d_{g}(\underline{\bm{x}}^{*},\underline{\bm{x}}^{(t)})\leq\left(1-\frac{\underline{\beta}_{0}\underline{\eta}}{4}\right)^{\frac{t}{2}}d_{g}(\underline{\bm{x}}^{*},\underline{\bm{x}}^{(0)}).$

The result follows.

(b) The result follows obviously from (a) and the fact that
$d_{g}(\underline{\bm{x}}^{(t)},\underline{R}_{d})\leq
d_{g}(\underline{\bm{x}}^{(t)},\underline{\bm{x}}^{*})$ for all $t\geq 0$.

(c) The proof is logically similar to the proof of (c) in Theorem 3.6. We
write the spectral decompositions of $\mathcal{H}f(\bm{x})$ and
$\mathcal{H}\widehat{f}_{h}(\bm{x})$ as:

$\mathcal{H}f(\bm{x})=\underline{V}(\bm{x})\underline{\Lambda}(\bm{x})\underline{V}(\bm{x})^{T}\quad\text{
and
}\quad\mathcal{H}\widehat{f}_{h}(\bm{x})=\widehat{\underline{V}}(\bm{x})\widehat{\underline{\Lambda}}(\bm{x})\widehat{\underline{V}}(\bm{x})^{T}.$

By Weyl’s theorem (Theorem 4.3.1 in Horn and Johnson 2012) and uniform bounds
(32),

$\displaystyle|\underline{\lambda}_{j}(\bm{x})-\widehat{\underline{\lambda}}_{j}(\bm{x})|$
$\displaystyle\leq\left|\left|\mathcal{H}f(\bm{x})-\mathcal{H}\widehat{f}_{h}(\bm{x})\right|\right|_{2}$
$\displaystyle\leq
q\left|\left|f(\bm{x})-\widehat{f}_{h}(\bm{x})\right|\right|_{\infty}^{(2)}$
$\displaystyle=O(h^{2})+O_{P}\left(\sqrt{\frac{|\log h|}{nh^{q+4}}}\right).$

Thus, $\widehat{f}_{h}$ will satisfy conditions (A2) with high probability
when $h$ is sufficiently small and $\frac{nh^{q+4}}{|\log h|}$ is sufficiently
large. According to Davis-Kahan theorem (Lemma D.1 here), uniform bounds (32),
and the continuity of exponential maps, we have that

$\displaystyle
d_{g}\left(\mathtt{Exp}_{\bm{y}}\left(\underline{\eta}\cdot\widehat{\underline{V}}_{d}(\bm{y})\widehat{\underline{V}}_{d}(\bm{y})^{T}\mathtt{grad}\,\widehat{f}_{h}(\bm{y})\right),\,\mathtt{Exp}_{\bm{y}}\left(\underline{\eta}\cdot\underline{V}_{d}(\bm{y})\underline{V}_{d}(\bm{y})^{T}\mathtt{grad}\,f(\bm{y})\right)\right)$
$\displaystyle\leq\underline{\eta}C_{3}\left|\left|\widehat{\underline{V}}_{d}(\bm{y})\widehat{\underline{V}}_{d}(\bm{y})^{T}\mathtt{grad}\,\widehat{f}_{h}(\bm{y})-\underline{V}_{d}(\bm{y})\underline{V}_{d}(\bm{y})^{T}\mathtt{grad}\,f(\bm{y})\right|\right|_{2}$
$\displaystyle\leq\underline{\eta}C_{3}\left|\left|\widehat{\underline{V}}_{d}(\bm{y})\widehat{\underline{V}}_{d}(\bm{y})^{T}\left[\mathtt{grad}\,\widehat{f}_{h}(\bm{y})-\mathtt{grad}\,f(\bm{y})\right]\right|\right|_{2}$
$\displaystyle\quad+\underline{\eta}C_{3}\left|\left|\left[\widehat{\underline{V}}_{d}(\bm{y})\widehat{\underline{V}}_{d}(\bm{y})^{T}-\underline{V}_{d}(\bm{y})\underline{V}_{d}(\bm{y})^{T}\right]\mathtt{grad}\,f(\bm{y})\right|\right|_{2}$
$\displaystyle\stackrel{{\scriptstyle\text{(i)}}}{{\leq}}\underline{\eta}C_{3}\left|\left|\mathtt{grad}\,\widehat{f}_{h}(\bm{y})-\mathtt{grad}\,f(\bm{y})\right|\right|_{2}+\underline{\eta}C_{3}\cdot\frac{\left|\left|\mathcal{H}f(\bm{y})-\mathcal{H}\widehat{f}_{h}(\bm{y})\right|\right|_{2}\cdot\left|\left|\mathtt{grad}\,f(\bm{y})\right|\right|_{2}}{\underline{\beta}_{0}}$
$\displaystyle\leq\underline{\eta}C_{3}\sqrt{q}\left|\left|\widehat{f}_{h}-f\right|\right|_{\infty}^{(1)}+\underline{\eta}C_{3}\cdot\frac{q\left|\left|\widehat{f}_{h}-f\right|\right|_{\infty}^{(2)}\sqrt{q+1}\left|\left|f\right|\right|_{\infty}^{(1)}}{\underline{\beta}_{0}}$
$\displaystyle\equiv\underline{\epsilon}_{n,h}=O(h^{2})+O_{P}\left(\sqrt{\frac{|\log
h|}{nh^{q+4}}}\right)$

for any
$\bm{y}\in\text{Ball}_{q+1}(\underline{\bm{x}}^{*},\underline{r}_{2})\cap\Omega_{q}$,
where we utilize the Davis-Kahan theorem and
$\left|\left|\widehat{\underline{V}}_{d}(\bm{y})\widehat{\underline{V}}_{d}(\bm{y})^{T}\right|\right|_{2}=1$
in (i). Hence, when $h\to 0$ and $\frac{nh^{q+4}}{|\log h|}\to\infty$,

$\displaystyle\begin{split}&d_{g}\left(\mathtt{Exp}_{\bm{y}}\left(\underline{\eta}\cdot\widehat{\underline{V}}_{d}(\bm{y})\widehat{\underline{V}}_{d}(\bm{y})^{T}\mathtt{grad}\,\widehat{f}_{h}(\bm{y})\right),\,\mathtt{Exp}_{\bm{y}}\left(\underline{\eta}\cdot\underline{V}_{d}(\bm{y})\underline{V}_{d}(\bm{y})^{T}\mathtt{grad}\,f(\bm{y})\right)\right)\\\
&\leq\underline{\epsilon}_{n,h}=O(h^{2})+O_{P}\left(\sqrt{\frac{|\log
h|}{nh^{q+4}}}\right)\leq(1-\Upsilon)\cdot
2\arcsin\left(\underline{r}_{2}/2\right)\end{split}$ (90)

with probability tending to 1.
We now claim that
$d_{g}(\widehat{\underline{\bm{x}}}^{(t)},\underline{\bm{x}}^{*})\leq
2\arcsin\left(\underline{r}_{2}/2\right)$ and

$d_{g}(\widehat{\underline{\bm{x}}}^{(t+1)},\underline{\bm{x}}^{*})\leq\Upsilon\cdot
d_{g}(\widehat{\underline{\bm{x}}}^{(t)},\underline{\bm{x}}^{*})+\underline{\epsilon}_{n,h}$
(91)

for all $t\geq 0$. We again prove this claim by induction on the iteration
number. Note that when $t=1$, we derive that

$\displaystyle
d_{g}(\widehat{\underline{\bm{x}}}^{(1)},\underline{\bm{x}}^{*})$