Proof of Lemma 1. In all three cases, \(g\) is always in \(L^\infty( {\cal M})\), and then \[(Q_\epsilon g - g)(x) = \int_ {\cal M}{\cal H}_\epsilon( x,y) (g(y)-g(x)) dV(y).\] Thus, \[r(x)= \int_ {\cal M}(K_\epsilon(x,y) - {\cal H}_\epsilon( x,y)) (g(y)-g(x)) dV(y),\] and we aim to bound \(|r(x)|\) uniformly in \(x\). The proof consists of truncating the integral on a local (geodesic) ball around \(x\), and showing that the tail contributes negligibly to the integral, and then comparing \(K_\epsilon(x,y)\) to \({\cal H}_\epsilon(x,y)\) locally.

We proceed in a few steps, and we first introduce the local truncation ball. Denote by \(B_r(x)\) the local geodesic ball around \(x\) of radius \(r < \xi\). Let \(t_0 <1\) and \(\delta_0 < \xi\) be as in Lemma 6. Define \[\delta(\epsilon) := \sqrt{2(d + 4)\epsilon \log\frac{1}{\epsilon}}.\] Recall that \(\tau\) is the reach and \(\xi\) is the injective radius of \({\cal M}\), and let \(t_1'\) be the constant depending on \({\cal M}\) s.t. \[\label{eq:def-t1M} \epsilon < t_1' \Rightarrow 2 \delta(\epsilon) < \min \{ \tau/2, \delta_0, 1\}; \quad \text{let } t_1:= \min\{ t_0, t_1'\},\tag{6}\] then \(\epsilon < t_1\) also implies \(\epsilon < t_0 <1\). This allows us to apply Lemma 6 with \[m = \lceil d/2+3 \rceil\] and \(t= \epsilon\), and Lemma 6(i) gives that \(\forall x \in {\cal M}\), \(\forall y \in B_{2\delta (\epsilon)}(x) \subset B_{\delta_0}(x)\), \[\label{eq:heat-kernel-lemma-1} \begin{align} & {\cal H}_\epsilon (x,y) = G_\epsilon(x,y) \Big( u_0(x,y) + \epsilon u_1(x,y) + r_2^H(\epsilon, x,y) \Big) + r^H(\epsilon, x,y), \\ & |r_2^H(\epsilon, x,y)| \le C_2' \epsilon^2, \quad |r^H(\epsilon,x,y)| \le C_2 \epsilon^{4}, \end{align}\tag{7}\] where \(C_2'= \sum_{l=2}^m \| u_l\|_\infty\) is another constant depending on \({\cal M}\), and the uniform upper bound of \(|r^H|\) uses that \(m \ge d/2+3\). In addition, Lemma 6(ii) gives that \[\label{eq:heat-kernel-lemma-2} {\cal H}_\epsilon( x,y) \le C_3 \epsilon^{-d/2} e^{- d_ {\cal M}(x,y)^2/(5\epsilon)}, \quad \forall x, y \in {\cal M}.\tag{8}\]

Step 1. truncation to local ball.

We consider \(r(x)= I_1(x) + I_2(x)\), where \[I_1(x) = \int_{ {\cal M}\backslash B_{2\delta(\epsilon)}(x) }(K_\epsilon(x,y) - {\cal H}_\epsilon( x,y)) (g(y)-g(x)) dV(y),\] \[I_2(x) = \int_{ B_{2\delta(\epsilon)}(x) }(K_\epsilon(x,y) - {\cal H}_\epsilon( x,y)) (g(y)-g(x)) dV(y).\]

We first bound \(|I_1(x)|\). For any \(y \notin B_{2\delta(\epsilon)}(x)\), one can verify that \(\epsilon^{-d/2} e^{- { d_ {\cal M}( x,y)^2}/{( 5 \epsilon)}} \le \epsilon^6\). Then, by the upper bound 8 , we have \(0 \le {\cal H}_\epsilon(x,y) \le C_3 \epsilon^6\).

To upper bound \(K_\epsilon(x,y)\), we observe that \(y \notin B_{2\delta(\epsilon)}(x)\) implies that \(\| x - y\| \ge \delta(\epsilon)\): Suppose otherwise, \(\| x - y\| < \delta(\epsilon) < \tau/2\), and by Lemma 14, \(d_ {\cal M}(x,y) \le 2 \| x-y\| < 2 \delta(\epsilon)\), contradicting with \(y \notin B_{2\delta(\epsilon)}(x)\). As a result, \[0 \le K_\epsilon(x,y) = \frac{1}{(4\pi \epsilon)^{d/2}} e^{- \| x-y\|^2/(4\epsilon)} \le (4\pi)^{-d/2} \epsilon^2.\]

Putting together, we then have \[\begin{align} |I_1(x)| & \le \int_{ {\cal M}\backslash B_{2\delta(\epsilon)}(x)} (K_\epsilon(x,y) + {\cal H}_\epsilon(x,y) ) |g(y) - g(x)| dV(y) \\ & \le 2 \| g\|_\infty \mathrm{Vol}( {\cal M}) ( C_3 \epsilon^6 + (4\pi)^{-d/2} \epsilon^2 ) \\ & \le \| g\|_\infty C_{4,1} \epsilon^2, \quad C_{4,1} = 2 \mathrm{Vol}( {\cal M}) ( C_3 + (4\pi)^{-d/2} ), \end{align}\] where in the last inequality we used that \(\epsilon < 1\).

Step 2. expansion of \({\cal H}_\epsilon\) on local ball.

Restricting to \(y \in B_{2\delta(\epsilon)}(x)\), we focus for a moment on \({\cal H}_\epsilon(x,y)\) and recall the expansion 7 . We write \({\cal H}_\epsilon(x,y) = {\cal H}_{\epsilon}^H(x,y) + r^H(\epsilon, x,y)\), where \[{\cal H}_{\epsilon}^H(x,y) := G_\epsilon(x,y) \Big( u_0(x,y) + \epsilon u_1(x,y) + r_2^H(\epsilon, x,y) \Big).\] Then, \(I_2(x) = I_{2}^H(x)+I_3(x)\), where \[\begin{align} I_{2}^H(x) & = \int_{ B_{2\delta(\epsilon)}(x) }(K_\epsilon(x,y) - {\cal H}_{\epsilon}^H( x,y)) (g(y)-g(x)) dV(y), \\ I_3(x) & = - \int_{ B_{2\delta(\epsilon)}(x) } r^H( \epsilon, x,y) (g(y)-g(x)) dV(y). \end{align}\] We will handle \(I_{2}^H(x)\) in Step 3. Here, using that \(|r^H(\epsilon, x, y)| \le C_2 \epsilon^4\) uniformly, we have that \[\begin{align} |I_3(x)| & \le \int_{ B_{2\delta(\epsilon)}(x) } |r^H( \epsilon, x,y)| |g(y)-g(x)| dV(y) \\ & \le \| g\|_\infty C_{4,2} \epsilon^4, \quad C_{4,2} := 2 \mathrm{Vol}( {\cal M}) C_2 . \end{align}\]

Step 3. comparing \(K_\epsilon\) to \({\cal H}_{\epsilon}\) on local ball.

To analyze \(I_2^H(x)\), we revisit the expressions of \({\cal H}_\epsilon^H\) and \(K_\epsilon\). Since \(y \in B_{2\delta(\epsilon)}(x)\), we use normal coordinates at \(x\) and write \(y = \exp_x( s \theta)\), where \(s = d_ {\cal M}(x,y)\) and \(\theta \in S^{d-1} \subset T_x {\cal M}\cong \mathbb{R}^d\). We have \(s < 2\delta(\epsilon) < \delta_0 < \xi\). Recall that \[G_\epsilon(x,y) = \epsilon^{-d/2}h \Big( \frac{s^2}{\epsilon} \Big), \quad K_\epsilon(x,y) = \epsilon^{-d/2}h \Big( \frac{\| x-y\|^2}{\epsilon} \Big), \quad h(r) = \frac{1}{(4\pi)^{d/2}} e^{-r /4}.\] The comparison of \(K_\epsilon(x,y)\) to \({\cal H}_\epsilon^H(x,y)\) thus consists of handling

a) the difference \({\cal H}_\epsilon^H - G_\epsilon\) by controlling the remainder terms in the expansion of \({\cal H}_\epsilon^H\), and

b) the difference \(G_\epsilon - K_\epsilon\) by tracking the influence of using \(\|x-y\|\) instead of \(s=d_ {\cal M}(x,y)\) inside \(h\).

In this proof, we use big-O notation to indicate bound (instead of any asymptotic meaning): \(Y = O(Z)\) means \(|Y| \le C Z\) for some constant \(C\), and we will track the constant dependence. In all the cases, the big-O notation is used to bound the remainder terms in absolute value, and the constants will be depending on \({\cal M}\) and uniformly in \(x\) and \(\theta\).

We start with a). Because \(u_0\), \(u_1 \in C^{\infty}( {\cal M}\times {\cal M})\), and that \(u_0(x,y) = 1+O(s^2)\) by Lemma 6(i), we have \[{\cal H}_\epsilon^H(x,y) = \epsilon^{-d/2} h( \frac{s^2}{\epsilon})( 1 + O(s^2) + O(\epsilon) ).\] For b), by Lemma 15(ii), we have \(\|x- y\|^2= s^2 + O(s^4)\), and then by Taylor expansion \[h( \frac{ \| x-y\|^2}{\epsilon}) = h( \frac{s^2}{\epsilon}) +h'( \frac{ \tilde{r}}{\epsilon}) \frac{O(s^4)}{\epsilon},\] where \(\tilde{r}\) is between \(s^2\) and \(\|x-y\|^2\). Recall that we have \(\| x - y\|\le s < 2\delta(\epsilon) < \tau/2\), then by Lemma 14, \(s/2\le \| x-y \|\). Thus, \(\tilde{r} \ge s^2/4\). Recall that \(h'(r)=-h(r)/4)\), we have \(|h'( \frac{ \tilde{r}}{\epsilon})| \le \frac{1}{4} h( \frac{s^2}{ 4 \epsilon} )\). This gives that \[K_\epsilon(x,y) = \epsilon^{-d/2} h( \frac{s^2}{\epsilon}) + \epsilon^{-d/2} h( \frac{s^2}{ 4 \epsilon} ) \frac{O(s^4)}{\epsilon}.\] We then have \[K_\epsilon(x,y) - {\cal H}_\epsilon^H(x,y) = \epsilon^{-d/2} h( \frac{s^2}{4 \epsilon}) O(s^2 + \epsilon + \frac{s^4}{\epsilon}),\] where we used that \(h(r) \le h(r/4)\) to simplify the bound. This estimate would allow us to prove the cases (ii) and (iii) of \(g\), which has lower regularity.

Specifically, we always have \[\begin{align} | I_{2}^H(x) | \le \int_{ B_{2\delta(\epsilon)}(x) } | K_\epsilon(x,y) - {\cal H}_{\epsilon}^H( x,y))| | g(y)-g(x)| dV(y). \end{align}\] The volume form \(dV(\exp_x(s\theta)) = V(x,\theta,s) s^{d-1}ds d\theta\), and by Lemma 15(i), we know that \(0 \le V(x,\theta,s) \le b_V\) for some constant \(b_V\) depending on \({\cal M}\). As a result, when \(g \in L^\infty( {\cal M})\), we have \[\begin{align} | I_{2}^H(x) | & \le 2 \| g\|_\infty b_V \int_0^{2\delta(\epsilon)} \int_{S^{d-1}} | K_\epsilon(x,y) - {\cal H}_{\epsilon}^H( x,y))| s^{d-1}ds d\theta \\ & = 2 \| g\|_\infty b_V |S^{d-1}| \epsilon^{-d/2} \int_0^{2\delta(\epsilon)} h( \frac{s^2}{4 \epsilon}) O(s^{2} + \epsilon + \frac{s^4}{\epsilon}) s^{d-1} ds. \end{align}\] To bound the integral, we change the variable to \[u := s/\sqrt{\epsilon},\] and then \[\epsilon^{-d/2} \int_0^{2\delta(\epsilon)} h( \frac{s^2}{4 \epsilon}) O(s^{2} + \epsilon + \frac{s^4}{\epsilon}) s^{d-1} ds =O( \epsilon) \int_0^{ 2 \sqrt{ 2 (d+4) \log \frac{1}{\epsilon} } } h(\frac{u^2}{4}) (u^4+ u^2 + 1) u^{d-1} du.\] Suppose \(O(\epsilon)\) term is upper bounded in absolute value by \(c_{A,1}\epsilon\), the constant \(c_{A,1}\) only depends on \({\cal M}\) as it can be tracked to the expansions of \({\cal H}_\epsilon^H(x,y)\) and \(K_\epsilon(x,y)\). Now, \[\begin{align} & \int_0^{ 2 \sqrt{ 2 (d+4) \log \frac{1}{\epsilon} } } h(\frac{u^2}{4}) (u^4+ u^2 + 1) u^{d-1} du \le \int_0^{ \infty} h(\frac{u^2}{4}) (u^4+ u^2 + 1) u^{d-1} du \\ &~~~ = (4\pi)^{-d/2}\int_0^{ \infty} e^{-u^2/16} (u^4+ u^2 + 1) u^{d-1} du \\ &~~~ \le(4\pi)^{-d/2}\int_0^{ \infty} e^{-u^2/16} \sum_{l=0}^5 u^{l+d-1} du =: m_{d,1}. \end{align}\] Putting together, this shows that \[| I_{2}^H(x) | \le 2 \| g\|_\infty b_V |S^{d-1}| c_{A,1} m_{d,1} \epsilon.\] Let \(C_{5,3} = 2 b_V |S^{d-1}| c_{A,1} m_{d,1}\), then \(| I_{2}^H(x) | \le \| g\|_\infty C_{5,3} \epsilon\).

Putting together the bounds of \(|I_1|\), \(|I_2^H|\), \(|I_3|\), and note that \(\epsilon<1\), we have that \[\begin{align} |r(x)| & \le |I_1(x)| + |I_3(x)| + |I_2^H(x)| \\ & \le \| g\|_\infty C_{4,1} \epsilon^2 + \|g\|_\infty C_{4,2} \epsilon^4 + \| g\|_\infty C_{5,3} \epsilon \\ & \le \| g\|_\infty C_{5} \epsilon, \quad C_5 := C_{4,1} + C_{4,2} +C_{5,3}. \end{align}\] The constant \(C_5\) only depends on \({\cal M}\) (and \(d\)) and is uniform in \(x\). This proves case (iii) of the lemma.

For case (ii), \(g \in C^{0,\beta}( {\cal M})\). Since \(s = d_ {\cal M}(x,y) < 2\delta(\epsilon) < \delta_0 < \xi\), we have \[|g(y) - g(x)| \le L_{0,\beta}(g) s^\beta.\] Then, together with that \(dV(y) \le b_V s^{d-1} ds d\theta\), we have \[\begin{align} | I_{2}^H(x) | & \le L_{0,\beta}(g) b_V \int_0^{2\delta(\epsilon)} \int_{S^{d-1}} | K_\epsilon(x,y) - {\cal H}_{\epsilon}^H( x,y))| s^{\beta+d-1}ds d\theta \\ & = L_{0,\beta}(g) b_V |S^{d-1}| \epsilon^{-d/2} \int_0^{2\delta(\epsilon)} h( \frac{s^2}{4 \epsilon}) O(s^2 + \epsilon + \frac{s^4}{\epsilon}) s^{\beta+d-1}ds \\ & \le L_{0,\beta}(g) b_V |S^{d-1}| c_{A,1} \epsilon^{\beta/2+1} \int_0^{ 2 \sqrt{ 2 (d+4) \log \frac{1}{\epsilon} } } h(\frac{u^2}{4}) (u^4+ u^2 + 1) u^{\beta+d-1} du, \end{align}\] where in the last inequality we used the constant \(c_{A,1}\) to bound the big-O term again. To upper bound the integral in \(du\), we again relax to \(\int_0^\infty\), and note that since \(0<\beta \le 1\), we have \(u^{\beta} \le 1+ u\), \(\forall u \ge 0\). Then, \[\int_0^{ 2 \sqrt{ 2 (d+4) \log \frac{1}{\epsilon} } } h(\frac{u^2}{4}) (u^4+ u^2 + 1) u^{\beta+d-1} du \le \int_0^{ \infty} h(\frac{u^2}{4}) (u^4+ u^2 + 1) (1+u) u^{d-1} du \le m_{d,1}.\] This shows that \[| I_{2}^H(x) | \le L_{0,\beta}(g) b_V |S^{d-1}| c_{A,1} m_{d,1} \epsilon^{\beta/2+1} \le L_{0,\beta}(g) C_{5,3} \epsilon^{\beta/2+1}.\] Combined with the bounds of \(|I_1|\), \(|I_3|\) and that \(\epsilon<1\), \(0< \beta \le 1\), this gives that \[\begin{align} |r(x)|& \le \| g\|_\infty C_{4,1} \epsilon^2 + \|g\|_\infty C_{4,2} \epsilon^4 + L_{0,\beta}(g) C_{5,3} \epsilon^{\beta/2+1} \\ & \le \| g\|_{0,\beta} C_{5} \epsilon^{\beta/2+1}, \end{align}\] which proves case (ii) of the lemma.

To prove the case for \(g \in C^2( {\cal M})\), we need to refine the above estimates “to the next order”. Specifically, for the expansion of \({\cal H}_\epsilon^H\) in a), we have \[\begin{align} u_0(x,y) &= 1 + q_2^U(x,\theta)s^2 + O(s^3), \quad q_2^U(x,\theta) = \frac{1}{12} \texttt{Ric}_{x}(\theta,\theta),\\ u_1(x,y) &= u_1(x,x) + O(s), \end{align}\] Thus, \[{\cal H}_\epsilon^H(x,y) = \epsilon^{-d/2} h( \frac{s^2}{\epsilon}) ( 1 + q_2^U(x,\theta) s^2 + \epsilon u_1(x,x) + O(s^3 + \epsilon s +\epsilon^2)).\] In b), we also use the refined expansion of \(\| x-y\|^2\) in Lemma 15(ii): with \(q_4^M( x,\theta) = -\frac{1}{12} \|\mathrm{I}\!\mathrm{I}_x(\theta,\theta)\|^2\), \[\|x- y\|^2= s^2 +q_4^M(x,\theta) s^4 + r_5 =: s^2 + r_4,\] where \(r_5 = O( s^5)\), \(r_4 =O(s^4)\), and \(q_4^M(x,-\theta) = q_4^M(x,\theta)\).

Recall that \(h'(r) = -h(r)/4\), and \(h^{(2)}(r) = h(r)/16\). This gives the refined Taylor expansion \[h( \frac{s^2+ r_4}{\epsilon}) = h( \frac{s^2}{\epsilon}) + h'( \frac{s^2}{\epsilon}) \frac{r_4}{\epsilon} + \frac{1}{2} h^{(2)}( \frac{ \tilde{r}'}{\epsilon} ) (\frac{r_4}{\epsilon})^{2},\] where \(\tilde{r}'\) is again between \(s^2\) and \(\|x-y\|^2\). For the same reason as before, \(\tilde{r}' \ge s^2/4\), and then \(| h^{(2)}( \frac{ \tilde{r}'}{\epsilon} ) | = \frac{1}{16}h ( \frac{ \tilde{r}'}{\epsilon} ) \le \frac{1}{16}h ( \frac{ s^2 }{4 \epsilon} )\). Combined with the bounds of \(|r_4|\), \(|r_5|\), we have \[K_\epsilon(x,y) = \epsilon^{-d/2} h(\frac{s^2}{\epsilon}) \Big( 1 - \frac{1}{4} q_4^M (x,\theta) \frac{s^4}{\epsilon} \Big) + \epsilon^{-d/2} h( \frac{s^2}{4\epsilon} ) O( \frac{s^5}{\epsilon} + \frac{s^8}{\epsilon^2} ) ,\] where we used \(h(r) \le h(r/4)\) to simplify the big-O term. In both the expansions of \({\cal H}_\epsilon^H\) and \(K_\epsilon\), all the constants in big-O depend on \({\cal M}\) only and is uniform for \(x\), \(\theta\). Subtracting the two, and letting \(Q_0(x) = - u_1(x,x)\), \(Q_2 (x,\theta) = -q_2^U(x,\theta)\), \(Q_4(x,\theta) = -\frac{1}{4} q_4^M(x,\theta)\), we have \[\begin{align} K_\epsilon(x,y) - {\cal H}_\epsilon^H(x,y) & = J(\epsilon, x,y) + R_{A,2}(s , \theta )\\ J(\epsilon, x,y) & := \epsilon^{-d/2} h( \frac{s^2}{ \epsilon}) \Big(Q_4(x,\theta) \frac{s^4}{\epsilon} + Q_2 (x,\theta) s^2 + \epsilon Q_0(x) \Big)\\ |R_{A,2}(s , \theta)| & \le c_{A,2} \epsilon^{-d/2} h( \frac{s^2}{4\epsilon} ) ( \frac{s^8}{\epsilon^2} + \frac{s^5}{\epsilon} + s^3 + \epsilon s +\epsilon^2), \\ |J(\epsilon, x,y)| & \le c_{A,2} \epsilon^{-d/2} h( \frac{s^2}{4\epsilon} ) (\frac{s^4}{\epsilon} + s^2 + \epsilon), \end{align}\] where we used \(h(r) \le h(r/4)\) again to simplify the bound, and the constant \(c_{A,2}\) only depends on \({\cal M}\). In addition, \(Q_j\) for \(j=0,2,4\), are all even in \(\theta\), in the sense that \(Q_j(x, -\theta) = Q_j(x,\theta)\).

We now write \[\begin{align} I_2^H(x) & = I_4(x) + I_5(x), \\ I_4(x)& = \int_{ B_{2\delta(\epsilon)}(x) } J(\epsilon, x,y) (g(y)-g(x)) dV(y),\\ I_5(x)& = \int_{ B_{2\delta(\epsilon)}(x) } R_{A,2}(s , \theta) (g(y)-g(x)) dV(y). \end{align}\] By the same argument of bounding \(|I_2^H(x)|\) for \(g \in C^{0,\beta}( {\cal M})\) above, we can show that \[\begin{align} |I_5(x)| & \le \int_{ B_{2\delta(\epsilon)}(x) } | R_{A,2}(s , \theta) | | g(y)-g(x)| dV(y) \\ & \le \| \nabla g\|_\infty b_V \int_0^{2\delta(\epsilon)} \int_{S^{d-1}} | R_{A,2}(s , \theta) | s^{d} ds d\theta \\ & \le \| \nabla g\|_\infty b_V |S^{d-1}| c_{A,2} \int_0^{2\delta(\epsilon)} \epsilon^{-d/2} h( \frac{s^2}{4\epsilon} ) ( \frac{s^8}{\epsilon^2} + \frac{s^5}{\epsilon} + s^3 + \epsilon s +\epsilon^2) s^{d} ds, \end{align}\] and \[\begin{align} & \int_0^{2\delta(\epsilon)} \epsilon^{-d/2} h( \frac{s^2}{4\epsilon} ) ( \frac{s^8}{\epsilon^2} + \frac{s^5}{\epsilon} + s^3 + \epsilon s +\epsilon^2) s^{d} ds \le \int_0^{\infty} h( \frac{u^2}{4} ) ( \epsilon^2 (u^8+1) + \epsilon^{3/2} (u^5 + u^3 + u) ) \sqrt{\epsilon} u^{d} du \\ & \le \epsilon^2 \int_0^{\infty} h( \frac{u^2}{4} ) \sum_{l=1}^9 u^{l+d-1} du =: \epsilon^2 m_{d,2}, \end{align}\] where we used \(\epsilon <1\) in the last inequality. This shows that \[|I_5(x)| \le \| \nabla g\|_\infty b_V |S^{d-1}| c_{A,2} m_{d,2} \epsilon^2.\] Let \(C_{4,3} := (b_V + c_V) |S^{d-1}| c_{A,2} m_{d,2}\), which will also be used below to bound \(|I_{4}(x)|\), we have \(|I_5(x)| \le \| \nabla g\|_\infty C_{4,3} \epsilon^2\).

To bound \(|I_4(x)|\), we will also need to expand \(dV(y)\) and \(g(y)-g(x)\). By Lemma 15(i), we have \[dV(y)= (1+ r_V(s , \theta) )s^{d-1} ds d\theta, \quad |r_V(s , \theta)| \le c_V s^2.\] where \(c_V\) depends on \({\cal M}\) only and is uniform for \(x\), \(\theta\). Since \(g \in C^2( {\cal M})\), we have \[\label{eq:expansion-g-C2} g(y)= g(x) + \nabla_\theta g(x) s + r_2^F(s , \theta) , \quad |r_2^F(s , \theta)| \le \| \nabla^2 g\|_\infty s^2.\tag{9}\] Then, we have \[\begin{align} I_4(x) & = I_{4,1}(x) + I_{4,2}(x)+ I_{4,3}(x), \\ I_{4,1}(x) & = \int_0^{2\delta(\epsilon)} \int_{S^{d-1}} J(\epsilon, x,y) \nabla_\theta g(x) s^{d} ds d\theta, \\ I_{4,2}(x) & = \int_0^{2\delta(\epsilon)} \int_{S^{d-1}} J(\epsilon, x,y) \nabla_\theta g(x) r_V(s , \theta) s^{d} ds d\theta, \\ I_{4,3}(x) & = \int_{ B_{2\delta(\epsilon)}(x) } J(\epsilon, x,y) r_2^F(s , \theta) dV(y). \end{align}\] Observe that \[I_{4,1}(x) = \int_0^{2\delta(\epsilon)} \int_{S^{d-1}} \epsilon^{-d/2} h( \frac{s^2}{ \epsilon}) \Big(Q_4(x,\theta) \frac{s^4}{\epsilon} + Q_2 (x,\theta) s^2 + \epsilon Q_0(x) \Big) \nabla_\theta g(x) s^{d} ds d\theta,\] and recall that \(Q_0\), \(Q_2\), \(Q_4\) are even in \(\theta\), while \(\nabla_\theta g(x)\) is odd in \(\theta\). As a result, the integration of \(d\theta\) over \(S^{d-1}\) renders \(I_{4,1}(x)=0\).

The terms \(|I_{4,2}|\) and \(|I_{4,3}|\) will be bounded by the same argument as above: One can verify that \[\begin{align} |I_{4,2}(x)| & \le \int_0^{2\delta(\epsilon)} \int_{S^{d-1}} |J(\epsilon, x,y)| |\nabla_\theta g(x)| |r_V(s , \theta)| s^{d} ds d\theta \\ &\le \| \nabla g\|_\infty c_V |S^{d-1}| c_{A,2} \int_0^{2\delta(\epsilon)} \epsilon^{-d/2} h( \frac{s^2}{4\epsilon} ) (\frac{s^4}{\epsilon} + s^2 + \epsilon) s^{d+2} ds \\ & \le \| \nabla g\|_\infty c_V |S^{d-1}| c_{A,2} \epsilon^{5/2} \int_0^{\infty} h( \frac{u^2}{4} ) (u^4 + u^2 + 1) u^{d+2} du \\ & \le \| \nabla g\|_\infty c_V |S^{d-1}| c_{A,2} m_{d,2} \epsilon^{5/2}, \end{align}\] \[\begin{align} |I_{4,3}(x)| & \le \int_{ B_{2\delta(\epsilon)}(x) } |J(\epsilon, x,y)| |r_2^F(s , \theta)| dV(y) \\ & \le \| \nabla^2 g\|_\infty b_V |S^{d-1}| c_{A,2} \int_0^{2\delta(\epsilon)} \epsilon^{-d/2} h( \frac{s^2}{4\epsilon} ) (\frac{s^4}{\epsilon} + s^2 + \epsilon) s^{d+1} ds \\ & \le \| \nabla^2 g\|_\infty b_V |S^{d-1}| c_{A,2} \epsilon^2 \int_0^{\infty} h( \frac{u^2}{4} ) (u^4 + u^2 + 1)u^{d+1}du \\ & \le \| \nabla^2 g\|_\infty b_V |S^{d-1}| c_{A,2} m_{d,2} \epsilon^2. \end{align}\] Putting together, and by \(\epsilon < 1\), we have \[|I_4(x)| \le |I_{4,2}(x)| + |I_{4,3}(x)| \le (\| \nabla g\|_\infty + \| \nabla^2 g\|_\infty) C_{4,3} \epsilon^2.\] This then gives that \[|I_2^H(x)| \le |I_4(x)| + |I_5(x)| \le (2 \| \nabla g\|_\infty + \| \nabla^2 g\|_\infty) C_{4,3} \epsilon^2.\] Finally, we have \[\begin{align} |r(x)| & \le |I_1(x)| + |I_3(x)| + |I_2^H(x)| \\ & \le \| g\|_\infty C_{4,1} \epsilon^2 + \|g\|_\infty C_{4,2} \epsilon^4 + (2 \| \nabla g\|_\infty + \| \nabla^2 g\|_\infty) C_{4,3} \epsilon^2 \\ & \le \| g\|_{C^2} C_{4} \epsilon^2, \quad C_4 := C_{4,1} + C_{4,2} +2C_{4,3}. \end{align}\] This proves case (i) of the lemma. ◻

Proof of Lemma 2. For any \(t > 0\), we have that for any \(x \in {\cal M}\), \[\label{eq:Qtg-g-proof-1} (Q_t g-g)(x) = \int_ {\cal M}{\cal H}_t(x,y) (g(y) - g(x)) dV(y).\tag{10}\] Then, for \(g \in L^\infty( {\cal M})\), we have \[|(Q_t g-g)(x) |\le \int_ {\cal M}{\cal H}_t(x,y) |g(y) - g(x)| dV(y) \le 2 \| g\|_\infty,\] and this proves (iii).

When \(g \in C^2( {\cal M})\), we have \(Q_t g(x) = u(t,x)\) satisfies the manifold heat equation \(\partial_t u = \Delta u\) from initial condition \(u(0,x)=g(x)\). Then, \[u(t,x) - g(x) = \int_0^t \partial_t u(s, x) ds = \int_0^t \Delta u(s, x) ds.\] Meanwhile, \(\Delta u = \Delta Q_t g = Q_t \Delta g\), and then \[\int_0^t \Delta u(s, x) ds = \int_0^t (Q_s \Delta g)(x) ds.\] As a result, \[|\int_0^t \Delta u(s, x) ds | \le \int_0^t | (Q_s \Delta g)(x)| ds \le \int_0^t \|Q_s \Delta g\|_\infty ds \le \|\Delta g\|_\infty t,\] where the last inequality is by Lemma 12 applied to \(\Delta g\). Putting together, this gives that \[|(Q_t g - g)(x)| = |u(t,x) - g(x)| \le \|\Delta g\|_\infty t.\] Combined with that \(\Delta g = {\boldsymbol{T}r}\nabla^2 g\), which implies \(\| \Delta g \|_\infty \le d \| \nabla^2 g\|_\infty\), this proves (i).

To prove (ii), consider \(\epsilon < t_1\) as defined in 6 . Since \(\epsilon < t_1 \le t_0\), Lemma 6(ii) is applicable, which gives the Gaussian envelope ?? of \({\cal H}_\epsilon(x,y)\) globally on \({\cal M}\). Combined with the expression 10 , we have \[| (Q_\epsilon g-g)(x) | \le C_3 \int_{ {\cal M}} \epsilon^{-d/2} e^{- \frac{ d_ {\cal M}( x,y)^2}{ 5 \epsilon}} | g(y) - g(x) | dV(y).\] We again consider the truncation to the \(B_{2 \delta(\epsilon)}(x)\) geodesic ball as in the proof of Lemma 1.

For any \(y \notin B_{2 \delta(\epsilon)}(x)\), recall that \(\epsilon^{-d/2} e^{- { d_ {\cal M}( x,y)^2}/{( 5 \epsilon)}} \le \epsilon^6\), and then \[\int_{ {\cal M}\backslash B_{2 \delta(\epsilon)}(x)} \epsilon^{-d/2} e^{- \frac{ d_ {\cal M}( x,y)^2}{ 5 \epsilon}} | g(y) - g(x) | dV(y) \le 2 \|g\|_\infty \mathrm{Vol}( {\cal M}) \epsilon^6.\] For any \(y \in B_{2 \delta(\epsilon)}(x)\), since \(2 \delta(\epsilon) < \delta_0 < \xi\), use the normal coordinates at \(x\) and write \(y = \exp_x(s\theta)\). Again, because \(g \in C^{0,\beta}( {\cal M})\), we have \(|g(y) - g(x)| \le L_{0,\beta}(g) s^\beta\). Then, by the same argument as in the proof of Lemma 1 Step 3 for \(C^{0,\beta}\) function \(g\), using that \(dV(y) \le b_V s^{d-1} ds d\theta\), we have \[\begin{align} & \int_{ B_{2 \delta(\epsilon)}(x)} \epsilon^{-d/2} e^{- \frac{ d_ {\cal M}( x,y)^2}{ 5 \epsilon}} | g(y) - g(x) | dV(y) \\ & \le L_{0,\beta}(g) b_V |S^{d-1}| \int_0^{ 2 \delta(\epsilon) } \epsilon^{-d/2} e^{-s^2/(5 \epsilon)} s^{\beta + d-1} ds \\ & \le L_{0,\beta}(g) b_V |S^{d-1}| \epsilon^{\beta/2} \int_0^{ 2 \sqrt{ 2(d+4) \log \frac{1}{\epsilon} } } e^{-u^2/5 } u^{\beta+ d-1} du. \end{align}\] Observe that \[\begin{align} \int_0^{ 2 \sqrt{ 2 (d+4) \log \frac{1}{\epsilon} } } e^{-u^2/5 } u^{\beta+ d-1} du & \le \int_0^{\infty } e^{-u^2/5 } u^{\beta+ d-1} du \\ & \le \int_0^{\infty} e^{-u^2/5 } (1+u)u^{d-1} du =: m_{d,3}, \end{align}\] where the second inequality is by that \(u^{\beta} \le 1+ u\), \(\forall u \ge 0\), due to \(0<\beta \le 1\). Thus, \[\int_{ B_{2 \delta(\epsilon)}(x)} \epsilon^{-d/2} e^{- \frac{ d_ {\cal M}( x,y)^2}{ 5 \epsilon}} | g(y) - g(x) | dV(y) \le L_{0,\beta}(g) b_V |S^{d-1}| m_{d,3} \epsilon^{\beta/2}.\] The constant \(b_V\) depends on \({\cal M}\) and \(m_{d,3}\) depends on \(d\). Combining the bounds for integrals in and outside \(B_{2 \delta(\epsilon)}(x)\), we have \[\begin{align} | (Q_\epsilon g-g)(x) | & \le C_3 ( 2 \|g\|_\infty \mathrm{Vol}( {\cal M}) \epsilon^6 + L_{0,\beta}(g) |S^{d-1}| m_{d,3} \epsilon^{\beta/2}) \\ & \le C_3 ( 2 \mathrm{Vol}( {\cal M}) +b_V |S^{d-1}| m_{d,3} ) \| g\|_{0,\beta} \epsilon^{\beta/2}, \end{align}\] where we also use that \(\epsilon <1\). Let \(C_6 = C_3 ( 2 \mathrm{Vol}( {\cal M}) + b_V |S^{d-1}| m_{d,3} )\), this proves the bound for \(g \in C^{0,\beta}( {\cal M})\).

Finally, when \(g \in C^1( {\cal M})\), then \(g \in C^{0,1}( {\cal M})\), with \(L_{0,1}(g) \le \| \nabla g\|_\infty\). As a result, \(\| g\|_{0,1} \le \| g\|_{C^1}\), and the bound follows by the \(C^{0,\beta}\) case with \(\beta =1\). ◻

Proof of Lemma 3. Let \(\epsilon = \sigma^2\). By definition, \[\sum_{j=1}^N P_{ij} g(x_j) = g(x_i) + \frac{ \frac{1}{N-1} \sum_{j=1}^N W_{ij} ( g(x_j) - g(x_i))}{\frac{1}{N-1} \sum_{j=1}^N W_{ij}},\] and we analyze the numerator and denominator respectively.

Denominator: Define \(D_i := \sum_{j=1}^N W_{ij}\). We apply Lemma 16 which is based on concentration argument. Since \(p\) is uniform, Lemma 16(i) gives that, at large \(N\) under a good event \(E_1\) which happens w.p. \(>1- 2N^{-9}\), \(\frac{ D_i}{N} = p + O(\epsilon + \sqrt{ \frac{\log N}{N \epsilon^{d/2}} })\), \(i=1,\cdots, N\), and the constant in big-O depends on \({\cal M}\) and is uniform for all \(i\). Under Assumption 3, we know that \(O(\epsilon + \sqrt{ \frac{\log N}{N \epsilon^{d/2}} }) = o(1)\). As a result, \(\frac{ D_i}{N} = p + o(1) = O(1)\) uniform for all \(i\), and then \[\textcircled{2}_i := \frac{1}{N-1} \sum_j W_{ij} = ( 1+ \frac{1}{N-1} ) \frac{D_i}{N} = \frac{D_i}{N} + O(\frac{1}{N}) = p+ O( \epsilon + \sqrt{ \frac{\log N}{N \epsilon^{d/2}} } ),\] where in the last equality we used that \(1/N \ll \sqrt{ \frac{\log N}{N \epsilon^{d/2}} }\). Since \(p\) is a positive constant, we have \[\label{eq:degree-D-concen-rel} \textcircled{2}_i = p( 1+ \varepsilon^{D}_i), \quad \max_{1 \le i \le N} |\varepsilon^{D}_i| = O(\epsilon + \sqrt{ \frac{\log N}{N \epsilon^{d/2}} }),\tag{11}\] and recall that \(O(\epsilon + \sqrt{ \frac{\log N}{N \epsilon^{d/2}} }) = o(1)\), at large \(N\) we also have \(|\varepsilon_i^D| < 1/2\) for all \(i\). The needed large-\(N\) threshold for \(E_1\) and \(|\varepsilon_i^D| < 1/2\) only depends on \({\cal M}\).

Numerator: We want to analyze \[\textcircled{1}_i :=\frac{1}{N-1} \sum_{j, \, j \neq i} Y_j, \quad Y_j:= K_\epsilon( x_i, x_j) ( g(x_j) - g(x_i)).\] For each \(i\), conditioning on \(x_i\), this is an independent sum over \(j \neq i\). We have \[\begin{align} \mathbb{E}[ Y_j | x_i ] & = \int_ {\cal M}K_\epsilon( x_i, y) ( g(y) - g(x_i)) p dV(y). \end{align}\] We consider the three cases of \(g\) respectively.

\(\bullet\) Case (i), \(g \in C^{2}( {\cal M})\)

Recall the \(O(1)\) constant \(t_1\) as defined in 6 , which depends on \({\cal M}\). We assume large enough \(N\) s.t. \(\epsilon < t_1\) (due to that \(\epsilon = \sigma^2 \ll 1\)), and then by Lemma 1(i), \[\mathbb{E}[ Y_j | x_i ] = p ( (Q_{\epsilon} g - g)(x_i) + O( \| g\|_{C^2} \epsilon^2)).\]

To bound \(|\textcircled{1}_i - \mathbb{E}[ Y_j | x_i ] |\), we apply the classical Bernstein inequality Lemma 13. First, \[{\rm Var}( Y_j | x_i ) \le \mathbb{E}[Y_j^2 | x_i ] = \int_ {\cal M}\frac{1}{(4 \pi \epsilon)^{d}} e^{- { \|x_i - y \|^2}/{2 \epsilon}} ( g(y) - g(x_i))^2 p dV(y).\] Using the same technique as in proving Lemma 1(ii), namely by truncating inside and outside the \(B_{2\delta(\epsilon)}(x_i)\) ball, one can show that (with the \((4 \pi \epsilon)^{-d/2}\) normalization) \[\int_ {\cal M}\frac{1}{(4 \pi \epsilon)^{d/2}} e^{- { \|x- y \|^2}/{2 \epsilon}} ( g(y) - g(x))^2 dV(y) = \|g\|_\infty^2 O( \epsilon^{d/2+4}) + \|\nabla g\|_\infty^2 O( \epsilon) = \| g \|_{C^1}^2 O(\epsilon).\] This is because for \(y \notin B_{2 \delta(\epsilon)}(x)\), we have \(\| x - y\| \ge \delta(\epsilon)\), which implies \(e^{- { \|x- y \|^2}/{2 \epsilon}} \le \epsilon^{d+4}\), and then the outside-ball part of the integral can be bounded by \(\|g\|_\infty^2 O( \epsilon^{d/2+4})\); for \(y \in B_{2 \delta(\epsilon)}(x)\), writing \(y = \exp_x( s\theta)\), we have \(|g(y) - g(x)| \le \| \nabla g\|_\infty s\), and this leads to the inside-ball part of the integral bounded by \(\|\nabla g\|_\infty^2 O( \epsilon)\); the final bound is again by that \(\epsilon <1\). We then have \[{\rm Var}( Y_j | x_i ) = \frac{p}{(4 \pi \epsilon)^{d/2}} \| g \|_{C^1}^2 O (\epsilon) \le c_\nu \| g \|_{C^1}^2 \epsilon^{-d/2+1} =: \nu_Y,\] where the constant \(c_\nu\) depends on \({\cal M}\).

We also claim that, with large enough \(N\) s.t. \(\epsilon < t_1\), \[\label{eq:bounded-LY-goal} |Y_j | \le L_Y = c_L \| g\|_{C^1} \epsilon^{-d/2+1/2},\tag{12}\] where \(c_L\) is a constant depending on \({\cal M}\). The proof of 12 is postponed below.

With the variance upper bound \(\nu_Y\) and boundedness \(L_Y\) of \(Y_j | x_i\), we aim at deviation \(\tau =\sqrt{ 40 \frac{\log N}{N-1} \nu_Y}\). The needed condition \(\tau L_Y \le 3 \nu_Y\) reduces to \[\frac{\log N}{ N-1} \le \frac{9}{40} \frac{c_\nu}{c_L^2} \epsilon^{d/2},\] where the \(\| g\|_{C^1}\) factor cancels. Thus, the condition is satisfied with large enough \(N\) due to Assumption 3, and the large-\(N\) threshold is determined by \(c_\nu/c_L^2\), which only depends on \({\cal M}\) and is uniform for all \(g\). Then, w.p. \(> 1-2 N^{-10}\), we have that \[\textcircled{1}_i = \mathbb{E}[ Y_j | x_i ] + O( \| g\|_{C^1} \sqrt{\epsilon \frac{\log N}{N \epsilon^{d/2}} }).\] Taking union bound over \(i= 1, \cdots, N\), we have that, w.p. \(> 1-2 N^{-9}\), which we call a good event \(E_4\), \[\label{eq:numerator-circle1-prime} \textcircled{1}_i = p (Q_{\sigma^2} g - g)(x_i) + O \Big( \| g\|_{C^2} \sigma^4 + \| g \|_{C^1} \sigma \sqrt{\frac{\log N}{ N \sigma^d}} \Big).\tag{13}\]

Putting together 11 and 13 , and by that \(|\varepsilon_i^D| < 1/2\) for all \(i\), we have that, under \(E_1 \cap E_4\), \[\begin{align} \frac{\textcircled{1}_i }{\textcircled{2}_i } &= \frac{ p (Q_{\sigma^2} g - g)(x_i) + O \Big( \| g\|_{C^2} \sigma^4 + \| g \|_{C^1} \sigma \sqrt{\frac{\log N}{ N \sigma^d}} \Big) }{p( 1+ \varepsilon^{D}_i)} \\ &= (Q_{\sigma^2} g - g)(x_i) + O(|\varepsilon^{D}_i|) \| Q_{\sigma^2} g - g \|_\infty + O \Big( \| g\|_{C^2} \sigma^4 + \| g \|_{C^1} \sigma \sqrt{\frac{\log N}{ N \sigma^d}} \Big). \end{align}\] Note that \[O(|\varepsilon^{D}_i|) \| Q_{\sigma^2} g - g \|_\infty = O( \sigma^2) \| Q_{\sigma^2} g - g \|_\infty + O( \sqrt{ \frac{\log N}{N \sigma^{d}} } ) \| Q_{\sigma^2} g - g \|_\infty,\] and we bound the two terms respectively: Because \(g \in C^2( {\cal M})\), Lemma 2(i) gives that \(\| Q_{\sigma^2} g - g \|_\infty = O( \| \nabla^2 g\|_\infty \sigma^2)\); since \(g\) is also in \(C^1( {\cal M})\), Lemma 2(ii) gives that \(\| Q_{\sigma^2} g - g \|_\infty = O( \| g\|_{C^1} \sigma)\). Use the former to bound the first term, and the latter to the second term, we have that \[O(|\varepsilon^{D}_i|) \| Q_{\sigma^2} g - g \|_\infty = O \Big( \| \nabla^2 g\|_\infty \sigma^4 + \| g\|_{C^1} \sigma \sqrt{ \frac{\log N}{N \sigma^{d}} } \Big).\] The lemma follows by putting this back to the bound of \({\textcircled{1}_i }/{\textcircled{2}_i }\).

Proof of 12 : Consider two cases,

a) \(\| x_i - x_j\| \ge \delta(\epsilon)\), then by definition of \(\delta(\epsilon)\), we have \(\epsilon^{-d/2} e^{- { \|x- y \|^2}/{4 \epsilon}} \le \epsilon^2\), and then \[\epsilon^{-d/2} e^{- { \|x_i - x_j \|^2}/{4 \epsilon}} |g(x_j) - g(x_i)| \le 2\| g\|_\infty \epsilon^2;\]

b) \(\| x_i - x_j\| < \delta(\epsilon)\), then \(\| x_i - x_j\| < \tau /2\), and then by Lemma 14, \(d_ {\cal M}(x_i,x_j) \le 2 \| x_i - x_j\| < 2 \delta(\epsilon) < \xi\). In this case, \[|g( x_j )-g(x_i)|\le \| \nabla g \|_\infty d_ {\cal M}( x_i, x_j) \le 2 \| \nabla g \|_\infty \| x_i - x_j\|,\] and then \[e^{- { \|x_i - x_j \|^2}/{4 \epsilon}} |g(x_j) - g(x_i)| \le 2 \| \nabla g \|_\infty e^{- { \|x_i - x_j \|^2}/{4 \epsilon}} \| x_i - x_j\| \le 2 \| \nabla g \|_\infty c_0 \sqrt{\epsilon },\] where \(c_0\) is an absolute positive constant.

Combining both cases, since \(\epsilon < 1\), we always have that \[|Y_j | \le c_d \epsilon^{-d/2 + 1/2} (\| g\|_\infty + \| \nabla g \|_\infty),\] where \(c_d\) is a constant determined by \(d\). This proves the claim 12 .

This finishes case (i) of the lemma.

\(\bullet\) Case (ii), \(g \in C^{0,\beta}( {\cal M})\)

Following the same strategy, by Lemma 1(ii), \[\mathbb{E}[ Y_j | x_i ] = p (Q_{\epsilon} g - g)(x_i) + O( \| g\|_{0,\beta} \epsilon^{1 + \beta/2});\] By that \(|g(x_j) - g(x_i)| \le L_{0,\beta}(g) d_ {\cal M}( x_i, x_j)^\beta\) when \(x_j \in B_{2\delta(\epsilon)}(x_i)\), one can verify that \[{\rm Var}( Y_j | x_i ) \le \nu_Y = c_\nu' \| g \|_{0, \beta}^2 \epsilon^{-d/2+\beta},\] and \[|Y_j | \le L_Y = c_L' \| g\|_{0, \beta} \epsilon^{-d/2+\beta/2}.\] The good event \(E_1\) is about \(D_i\) for all \(i\) and same as before; the good event \(E_4\) is for the concentration of the summation \(\textcircled{1}_i\), and again holds w.p. \(>1-2N^{-9}\) for all \(i\). Putting together, under \(E_1 \cap E_4\) we have \[\begin{align} \frac{\textcircled{1}_i }{\textcircled{2}_i } &= \frac{ p (Q_{\sigma^2} g - g)(x_i) + \| g\|_{0,\beta} O \Big( \sigma^{2+\beta} + \sigma^\beta \sqrt{\frac{\log N}{ N \sigma^d}} \Big) }{p( 1+ \varepsilon^{D}_i)} \\ &= (Q_{\sigma^2} g - g)(x_i) + O(|\varepsilon^{D}_i|) \| Q_{\sigma^2} g - g \|_\infty + \| g\|_{0,\beta} O \Big( \sigma^{2+\beta} + \sigma^\beta \sqrt{\frac{\log N}{ N \sigma^d}} \Big) . \end{align}\] Lemma 2(ii) gives that \(\| Q_{\sigma^2} g - g \|_\infty = O( \| g\|_{0,\beta} \sigma^{\beta})\), and then \[O(|\varepsilon^{D}_i|) \| Q_{\sigma^2} g - g \|_\infty = \| g\|_{0,\beta} O(\sigma^{2+\beta} + \sigma^{\beta}\sqrt{ \frac{\log N}{N \sigma^{d}} }).\]

\(\bullet\) Case (iii), \(g \in L^{\infty}( {\cal M})\)

We use Lemma 1(iii) and Lemma 2(iii). The proof follows the same argument as that in case (ii) with \(|g(x_i) - g(x_j)| \le 2 \| g\|_\infty\), where setting \(\beta = 0\) and replacing \(\| g \|_{0,\beta}\) to be \(\| g\|_\infty\). In particular, one can verify that \(\nu_Y = c_\nu'' \| g \|_{\infty}^2 \epsilon^{-d/2}\), and \(L_Y = c_L'' \| g\|_{\infty} \epsilon^{-d/2}\).

Finally, the constants \(c_\nu\), \(c_\nu'\), \(c_\nu''\), and \(c_L\), \(c_L'\), \(c_L''\) may differ, while all only depend on \({\cal M}\). As a result, the large-\(N\) needed for (event \(E_4\) in) the three cases (i)(ii)(iii) may differ. The final threshold takes the maximum of those of the three cases. ◻

Proof of Theorem 1. We define \(f_0 : = f\) and \(f_m:= Q_{m \sigma^2} f\), \(m = 1, 2, \cdots, n\). We also denote by \(\vec{g} = \rho_X g\) for a function \(g\),   \(\vec{}\)  standing for the vector. Let \(N\) be large enough so that Lemma 3 applies, and the big-O bounds therein for all three cases involve a constant \(C_8\) that depends on \({\cal M}\) only.

Consider case (i). In the first multiplication of \(P\), we use Lemma 3(ii), which gives that w.p. \(>1-4N^{-9}\), \[P \vec{f}_0 = \vec{f}_1 + r_1, \quad \| r_1\|_\infty \le C_8 \| f\|_{0,\beta} \Big( \sigma^{2+\beta} + \sigma^\beta \sqrt{\frac{\log N}{ N \sigma^d}} \Big).\] If \(n=1\), this already proves the bound. If \(n \ge 2\), in the next \(n-1\) multiplications, \(f_m \in C^\infty( {\cal M})\), which allows us to use Lemma 3(i). Then, w.p. \(>1-4N^{-9}\) for each \(m=1, \cdots, n-1\), \[P \vec{f}_{m} = \vec{f}_{m+1} + r_{m+1}, \quad \| r_{m+1}\|_\infty \le C_8 ( \| f_m \|_{C^2} \sigma^4 + \| f_m \|_{C^1} \sigma \sqrt{\frac{\log N}{N \sigma^d}}).\] To bound \(\| f_m \|_{C^2}\) and \(\| f_m \|_{C^1}\), we use Lemma 4(i). For each \(m\), \(t = m\sigma^2 > 0\), then \[\begin{align} \| \nabla f_m \|_\infty \le C_7 (m\sigma^2)^{-1/2 + \beta/2} \| f\|_{0,\beta}, \quad \| \nabla^2 f_m \|_\infty \le C_7 (m\sigma^2)^{-1 + \beta/2} \| f\|_{0,\beta}. \end{align}\] Combined with that \(\| f_m\|_\infty \le \|f_0\|_\infty\) due to Lemma 12, we have \[\begin{align} \| f_m \|_{C^2} & = \|f_m\|_\infty + \| \nabla f_m\|_\infty + \| \nabla^2 f_m\|_\infty \\ & \le \|f_0\|_\infty + C_7 (m\sigma^2)^{-1/2 + \beta/2} \| f\|_{0,\beta} + C_7 (m\sigma^2)^{-1 + \beta/2} \| f\|_{0,\beta} \\ &\le 2(1+C_7) \| f\|_{0,\beta} ( 1 + (m\sigma^2)^{-1 + \beta/2} ), \end{align}\] where in the last inequality we used that \(t ^{-1/2 + \beta/2} \le 1 + t^{-1+\beta/2}\) for any \(t >0\); Meanwhile, \[\begin{align} \| f_m \|_{C^1} & = \|f_m\|_\infty + \| \nabla f_m\|_\infty \\ & \le \|f_0\|_\infty + C_7 (m\sigma^2)^{-1/2 + \beta/2} \| f\|_{0,\beta} \\ &\le (1+C_7) \| f\|_{0,\beta} ( 1 + (m\sigma^2)^{-1/2 + \beta/2} ). \end{align}\]

By construction, \[P^n \vec{f}_0 - \vec{f}_n = \sum_{m=1}^{n} P^{n-m} r_{m},\] and then, by triangle inequality, \[\| P^n \vec{f}_0 - \vec{f}_n \|_\infty \le \sum_{m=1}^{n} \| P^{n-m} r_{m}\|_\infty \le \| r_1\|_\infty + \sum_{m=1}^{n-1} \| r_{m+1}\|_\infty,\] where the 2nd inequality is by that \(P\) is contractive for vector \(\infty\)-norm (by that \(P\) is row-stochastic). Collecting the estimates above, we have \[\begin{align} \sum_{m=1}^{n-1} \| r_{m+1}\|_\infty \le C_8(1+C_7) \| f\|_{0,\beta} \Big( 2 \sigma^4 \sum_{m=1}^{n-1} ( 1 + (m\sigma^2)^{-1 + \beta/2} ) + \sigma \sqrt{\frac{\log N}{N \sigma^d}} \sum_{m=1}^{n-1} ( 1 + (m\sigma^2)^{-1/2 + \beta/2} ) \Big). \end{align}\] Note that, since \(0< \beta \le 1\), \[\sum_{m=1}^{n-1} m^{-1 + \beta/2} \le 1+\frac{2}{\beta} n^{\beta/2} \le \frac{4}{\beta} n^{\beta/2}, \quad \sum_{m=1}^{n-1} m^{-1/2 + \beta/2} \le \frac{2}{1+\beta} n^{1/2+\beta/2} \le 2 n^{1/2+\beta/2}.\] Writing \(n \sigma^2\) as \(t\), we then have \[\begin{align} \sum_{m=1}^{n-1} \| r_{m+1}\|_\infty \le C_8(1+C_7) \| f\|_{0,\beta} \Big( 2 \sigma^2 ( t + \frac{4}{\beta} t^{\beta/2} ) + \sqrt{\frac{\log N}{N \sigma^{d+2}}} ( t + 2 t^{(\beta+1)/2} ) \Big). \end{align}\] Combined with the bound of \(\| r_1\|_\infty\), we have \[\| P^n \vec{f}_0 - \vec{f}_n \|_\infty = \| f\|_{0,\beta} O \Big( \sigma^2 ( \sigma^\beta+ t + \frac{t^{\beta/2}}{\beta} ) + \sqrt{\frac{\log N}{N \sigma^{d+2}}} (\sigma^{\beta+1} + t + t^{(\beta+1)/2} ) \Big),\] and by that \(\sigma^2 \le t\), we have \(\sigma^{\beta} \le t^{\beta/2}\), and \(\sigma^{\beta+1} \le t^{(\beta+1)/2}\). This proves the bound when \(n\ge 2\), where the good event is the intersection of the \(n\) good events due to applying Lemma 3 for \(n\) times, and then the tail probability is \(4 n N^{-9} \ll N^{-7}\).

The proof of case (ii) follows the same strategy: in the first multiplication of \(P\) we use Lemma 3(iii), which proves the bound when \(n=1\); In the rest \(n-1\) multiplications we still use Lemma 3(i) because \(f_m \in C^{\infty}( {\cal M})\). We use Lemma 4(ii) to bound \(\| \nabla f_m \|_\infty\) and \(\| \nabla^2 f_m \|_\infty\). This leads to \[\begin{align} \sum_{m=1}^{n-1} \| r_{m+1}\|_\infty &\le C_8(1+C_7) \| f\|_{\infty} \Big( 2 \sigma^4 ( n-1 + \sum_{m=1}^{n-1} (m\sigma^2)^{-1} ) + \sigma \sqrt{\frac{\log N}{N \sigma^d}} ( n-1 + \sum_{m=1}^{n-1} (m\sigma^2)^{-1/2 } ) \Big) \\ &\le C_8(1+C_7) \| f\|_{\infty} \Big( 2 \sigma^2 ( t + 1+ \log n ) + \sqrt{\frac{\log N}{N \sigma^{d+2}}} ( t + 2 \sqrt{t} ) \Big), \end{align}\] where we use that \(\sum_{m=1}^{n-1} m^{-1} \le 1+ \log n\), \(\sum_{m=1}^{n-1} m^{-1/2} \le 2\sqrt{n}\). As a result, \[\| P^n \vec{f}_0 - \vec{f}_n \|_\infty = \| f\|_{\infty} O\Big( \sigma^2 ( t + 1+ \log n ) + \sqrt{\frac{\log N}{N \sigma^{d+2}}} ( \sigma + t + \sqrt{t} ) \Big),\] and the claimed bound follows by that \(\sigma \le \sqrt{t}\) since \(n \ge 1\). ◻

Proof of Lemma 5. The proof follows the strategy of Lemma 3, where we handle the \(1/D_j\) normalization with extra care. For the latter, we borrow the techniques used in [11].

Let \(\epsilon = \sigma^2\). By definition, \[\label{eq:Pij-ratio} \sum_{j=1}^N \tilde{P}_{ij} g(x_j) = g(x_i) + \frac{ \sum_{j=1}^N W_{ij} \frac{ g(x_j) - g(x_i) }{D_j} }{ \sum_{j=1}^N \frac{W_{ij}}{D_j}} = g(x_i) + \frac{\textcircled{1}_i}{\textcircled{2}_i}.\tag{14}\] By Lemma 16(ii), with large \(N\), under a good event denoted as \(E_{1,2}\) which happens w.p.\(> 1-4N^{-9}\), we have \[\textcircled{2}_i = \sum_{j=1}^N \frac{W_{ij}}{D_j} = 1 + \varepsilon^D_i, \quad \max_{1 \le i \le N} |\varepsilon^D_i | = O \Big( \epsilon + \sqrt{ \frac{\log N}{N \epsilon^{d/2}} } \Big).\] and recall that \(O(\epsilon + \sqrt{ \frac{\log N}{N \epsilon^{d/2}} }) = o(1)\), we also have \(|\varepsilon_i^D| < 1/2\) for all \(i\) with large \(N\). The needed large-\(N\) threshold for \(E_{1,2}\) and \(|\varepsilon_i^D| < 1/2\) depends on \(( {\cal M},p)\).

Meanwhile, the good event \(E_{1,2}\) is under the good event needed by Lemma 16(i), and then we also have \[\frac{1}{N} D_i = \tilde{p}_\epsilon (x_i) + O \Big( \epsilon^{3/2} + \sqrt{ \frac{\log N}{N \epsilon^{d/2}} } \Big), \quad \tilde{p}_\epsilon = p + \epsilon p_1,\] where \(p_1 = \omega p + \Delta p \in C^1( {\cal M})\). We introduce \[\eta: = p_1/ p = \omega + \Delta p /p, \quad \eta \in C^1( {\cal M}),\] and then \(p/\tilde{p}_\epsilon = (1+\epsilon \eta)^{-1}\). We assume \(\epsilon \| \eta \|_\infty < 1/2\), which can be guaranteed by large enough \(N\) (depending on \({\cal M}\) and \(p\)) since \(\epsilon = o(1)\). Then, uniformly over \({\cal M}\), \[1+\epsilon \eta(x) > 1/2, \quad \tilde{p}_\epsilon(x) = (1+ \epsilon \eta(x)) p(x) > p(x)/2 > p_{\rm min}/2 =: \tilde{p}_{\rm min} >0.\]

To proceed, note that as shown in the proof of Lemma 3, by Assumption 3, \(D_i/N = O(1)\), and we also have \(1/N \ll \sqrt{ \frac{\log N}{N \epsilon^{d/2}} }\). As a result, we have \[\frac{1}{N-1} D_i = \tilde{p}_\epsilon (x_i) (1 + \varepsilon_i), \quad \max_{1 \le i \le N} |\varepsilon_i | = O \Big( \epsilon^{3/2} + \sqrt{ \frac{\log N}{N \epsilon^{d/2}} } \Big), \quad \max_{1 \le i \le N} |\varepsilon_i| < 1/2,\] with large \(N\), and the threshold depends on \(( {\cal M}, p)\). This allows us to write \[\begin{align} \textcircled{1}_i & = \frac{1}{N-1}\sum_{j=1}^N W_{ij} \frac{ g(x_j) - g(x_i) }{ \tilde{p}_\epsilon(x_j) (1+ \varepsilon_j)} \\ & = \frac{1}{N-1}\sum_{j=1}^N W_{ij} \frac{ g(x_j) - g(x_i) }{ \tilde{p}_\epsilon(x_j) } (1+ \varepsilon_j') = \textcircled{1}_i' + \textcircled{3}_i, \end{align}\] where \[\begin{align} \textcircled{1}_i' & := \frac{1}{N-1}\sum_{j=1}^N W_{ij} \frac{g(x_j) - g(x_i)}{\tilde{p}_\epsilon(x_j)}, \\ \textcircled{3}_i & : = \frac{1}{N-1}\sum_{j=1}^N W_{ij} \frac{ g(x_j) - g(x_i) }{ \tilde{p}_\epsilon(x_j) } \varepsilon_j', \quad \max_{1 \le i \le N} |\varepsilon_i' | = O \Big( \epsilon^{3/2} + \sqrt{ \frac{\log N}{N \epsilon^{d/2}} } \Big), \end{align}\] by that \(\varepsilon_i' = - \varepsilon_i/(1+\varepsilon_i)\) and then \(|\varepsilon_i'| \le 2 |\varepsilon_i|\). We claim that, with large \(N\) and under a good event \(E_3\) which happens w.p. \(>1-2N^{-9}\), for all \(i=1,\cdots,N\), \[\label{eq:claim-E3-bound} \frac{1}{N-1}\sum_{j=1}^N W_{ij} |g(x_j) - g(x_i) | =\begin{cases} O(\sigma^{1}) \| g \|_{C^1}, & \quad g \in C^1( {\cal M}),\\ O(\sigma^{\beta }) \| g \|_{0,\beta}, &\quad g \in C^{0,\beta}( {\cal M}), \\ O(1) \| g\|_\infty, &\quad g \in L^\infty( {\cal M}). \\ \end{cases}\tag{15}\] If true, we then have \[\begin{align} |\textcircled{3}_i| & \le \frac{1}{N-1}\sum_{j=1}^N W_{ij} \frac{ |g(x_j) - g(x_i) |}{ \tilde{p}_\epsilon(x_j) } |\varepsilon_j'| \le \frac{ \max_{1 \le i \le N} |\varepsilon_i' |}{\tilde{p}_{\rm min}}\frac{1}{N-1}\sum_{j=1}^N W_{ij} |g(x_j) - g(x_i) | \\ & = \begin{cases} O \Big( \sigma^{4} + \sigma \sqrt{ \frac{\log N}{N \sigma^{d}} } \Big)\| g \|_{C^1}, & \quad g \in C^1( {\cal M}), \\ O \Big( \sigma^{3+\beta} + \sigma^{\beta}\sqrt{ \frac{\log N}{N \sigma^{d}} } \Big) \|g \|_{0,\beta}, &\quad g \in C^{0,\beta}( {\cal M}), \\ O \Big( \sigma^{3} + \sqrt{ \frac{\log N}{N \sigma^{d}} } \Big) \| g\|_\infty, &\quad g \in L^\infty( {\cal M}), \end{cases} \end{align}\] and the constants in big-O depend on \(( {\cal M}, p)\).

Next, we analyze the main term \(\textcircled{1}_i'\). Conditioning on \(x_i\), the summands \(Y_j := W_{ij} (g(x_j) - g(x_i))/\tilde{p}_\epsilon(x_j)\) for \(j \neq i\) are i.i.d., with \[\mathbb{E}[Y_j \mid x_i] = \int_ {\cal M}K_\epsilon(x_i, y)(g(y) - g(x_i))\frac{p(y)}{\tilde{p}_\epsilon(y)}\,dV(y).\] By definition of \(\eta\), we have that for any \(x\), \[\begin{align} & \int_ {\cal M}K_\epsilon(x, y)(g(y) - g(x))\frac{p(y)}{\tilde{p}_\epsilon(y)}\,dV(y) \\ & = \int_ {\cal M}K_\epsilon(x, y)(g(y) - g(x)) \frac{1}{1+\epsilon \eta} (y) \,dV(y) \\ & = \underbrace{\int_ {\cal M}K_\epsilon(x, y)(g(y) - g(x)) \,dV(y) }_{= (Q_\epsilon g - g)(x) + r(x) } + \tilde{r}_1(x) + \tilde{r}_2(x), \end{align}\] where \[\begin{align} \tilde{r}_1(x) & = \frac{- \epsilon \eta}{1+\epsilon \eta} (x) \int_ {\cal M}K_\epsilon(x, y)(g(y) - g(x)) \,dV(y), \\ \tilde{r}_2(x) & = \int_ {\cal M}K_\epsilon(x, y)(g(y) - g(x)) \big( \frac{1}{1+\epsilon \eta (y)}- \frac{1}{1+\epsilon \eta(x)} \big) \,dV(y). \end{align}\] We again assume large enough \(N\) s.t. \(\epsilon < t_1\), so that Lemma 1 applies. Then, \(\int_ {\cal M}K_\epsilon(x, y)(g(y) - g(x)) \,dV(y) = (Q_\epsilon g - g)(x) + r(x)\), and \(\|r\|_\infty\) is bound as therein for the three regularity classes. Together with that \(1 + \epsilon \eta \ge 1/2\) uniformly and Lemma 2 to bound \(\|Q_\epsilon g - g\|_\infty\), we have \[\| \tilde{r}_1 \|_\infty \le 2 \epsilon \| \eta \|_\infty ( \| Q_\epsilon g - g \|_\infty + \|r \|_\infty ) = \begin{cases} O( \epsilon^2) \| g\|_{C^2}, & g \in C^2( {\cal M}), \\ O( \epsilon^{1+\beta/2}) \| g\|_{0,\beta}, & g \in C^{0,\beta}( {\cal M}), \\ O( \epsilon) \|g\|_\infty, & g \in L^\infty( {\cal M}), \end{cases}\] noting that \(\| \eta\|_\infty\) is an \(O(1)\) constant depending on \(( {\cal M}, p)\) and we also use that \(\epsilon <1\).

To bound \(| \tilde{r}_2(x) |\), we adopt the same technique in proving Lemma 1 by truncating on the geodesic ball \(B_{2\delta(\epsilon)}(x)\). When \(y\) is within the ball, \(y = \exp_x (s\theta)\), then since \(\eta \in C^1( {\cal M})\), we have \[\big| \frac{1}{1+\epsilon \eta (y)}- \frac{1}{1+\epsilon \eta(x)} \big| \le 4 \epsilon \| \nabla \eta\|_\infty s,\] where we used that \(\nabla (1+\epsilon \eta)^{-1} = -\epsilon (1+\epsilon \eta)^{-2} \nabla \eta\) and \(1+\epsilon \eta > 1/2\) uniformly. This allows the bound the integral within the ball to be \(O(\epsilon^2) \| \nabla \eta\|_\infty \| \nabla g\|_\infty\) when \(g\) is \(C^1\), and \(O(\epsilon^{3/2}) \| \nabla \eta\|_\infty \| g\|_\infty\) when \(g \in L^{\infty}( {\cal M})\), including when \(g\) is in \(C^{0,\beta}( {\cal M})\). The integral outside \(B_{2\delta(\epsilon)}(x)\) can be bounded by \(O(\epsilon^2 \| g\|_\infty)\) by that \(K_\epsilon(x,y) \le (4\pi)^{-d/2} \epsilon^2.\) Thus, we have \[\| \tilde{r}_2 \|_\infty = \begin{cases} O( \epsilon^2) \| g\|_{C^1}, & g \in C^1( {\cal M}), \\ O( \epsilon^{3/2}) \|g\|_\infty, & g \in L^\infty( {\cal M}). \end{cases}\] Collecting the bounds, we have \[\int_ {\cal M}K_\epsilon(x, y)(g(y) - g(x))\frac{p(y)}{\tilde{p}_\epsilon(y)}\,dV(y) = (Q_\epsilon g - g)(x) + \tilde{r}(x), \quad \tilde{r} = r + \tilde{r}_1 + \tilde{r}_2,\] where \[\| \tilde{r} \|_\infty = \begin{cases} O( \epsilon^2) \| g\|_{C^2}, & g \in C^2( {\cal M}), \\ O( \epsilon^{1+\beta/2}) \| g\|_{0,\beta}, & g \in C^{0,\beta}( {\cal M}), \\ O( \epsilon) \| g\|_\infty, & g \in L^\infty( {\cal M}), \end{cases}\] with the constants in big-O now depending on \(( {\cal M}, p)\).

The variance and uniform bounds on \(Y_j\) follow the same arguments as in the proof of Lemma 3, modified by the bounded factor \(1/\tilde{p}_\epsilon \le 1/\tilde{p}_{\min}\): \[\mathrm{Var}(Y_j \mid x_i) \le \nu_Y, \quad |Y_j| \le L_Y,\] with \(\nu_Y\) and \(L_Y\) of the same orders as therein, and constants depending on \(( {\cal M}, p)\). By Bernstein (Lemma 13) with \(\tau = \sqrt{40 \log N\, \nu_Y / (N-1)}\), the condition \(\tau L_Y \le 3 \nu_Y\) reduces to a threshold on \(\log N/(N-1)\) depending only on \(( {\cal M}, p)\) and independent of \(g\), satisfied for large \(N\) by Assumption 3. Then, we have \(\textcircled{1}_i' = \mathbb{E}[Y_j \mid x_i] + v_i\), where, w.p. \(> 1 - 2N^{-10}\), \[|v_i| = \begin{cases} O\Big(\|g\|_{C^1}\,\sigma\sqrt{\frac{\log N}{N\sigma^d}}\Big), & g \in C^2( {\cal M}),\\[2pt] O\Big(L_{0,\beta}(g)\,\sigma^\beta\sqrt{\frac{\log N}{N\sigma^d}}\Big), & g \in C^{0,\beta}( {\cal M}),\\[2pt] O\Big(\|g\|_\infty\sqrt{\frac{\log N}{N\sigma^d}}\Big), & g \in L^\infty( {\cal M}), \end{cases}\] matching the deviation bound in Lemma 3 and all constants in big-O here also depend on \(p\). By union bound over \(i\), w.p. \(> 1 - 2N^{-9}\) uniformly in \(i\), and we call this event \(E_4\), \[\textcircled{1}_i' = (Q_\epsilon g - g)(x_i) + \tilde{r} (x_i) + v_i,\] with \(\| \tilde{r}\|_\infty\) and \(|v_i|\) uniformly bounded as above.

Combining 14 with \(\textcircled{1}_i = \textcircled{1}_i' + \textcircled{3}_i\) and \(\textcircled{2}_i = 1 + \varepsilon_i^D\), under \(E_{1,2} \cap E_3 \cap E_4\) (total tail \(\le 8N^{-9}\)), \[\frac{\textcircled{1}_i}{\textcircled{2}_i} = (Q_\epsilon g - g)(x_i) + O(|\varepsilon_i^D|)\|Q_\epsilon g - g\|_\infty + O( | \tilde{r} (x_i) | + |v_i | + |\textcircled{3}_i| ).\] The bound \(O(|\varepsilon_i^D|)\|Q_\epsilon g - g\|_\infty\) is handled same as in the proof of Lemma 3, splitting \(|\varepsilon_i^D|\) into its \(O(\sigma^2)\) and \(\sqrt{\log N/(N\sigma^{d})}\) parts and bounding \(\|Q_\epsilon g - g\|_\infty\) by Lemma 2(i) and (ii) respectively for the \(C^2\) case, and analogously for the other two cases. Together with the bound on \(| \textcircled{3}_i |\) from 15 , this yields the same final bounds as in Lemma 3 for the three cases of \(g\), with constants depending on \(( {\cal M}, p)\).

It remains to prove the claim 15 . For each \(i\), conditioning on \(x_i\), let \(Z_j := W_{ij}|g(x_j) - g(x_i)| \ge 0\) for \(j \neq i\), which are i.i.d.conditioning on \(x_i\). We can bound the expectation \[\mathbb{E}[ Z_j \mid x_i] = \int_ {\cal M}K_\epsilon(x_i, y)|g(y) - g(x_i)| p(y)\, dV(y)\] again via the \(B_{2\delta(\epsilon)}(x_i)\) truncation: outside the ball, \(K_\epsilon (x_i,y) \le (4\pi)^{-d/2}\epsilon^2\) contributes \(O(\|g\|_\infty p_{\max}\epsilon^2)\) in all cases; inside the ball, the change of variable \(u = s/\sqrt\epsilon\) together with \(|g(y) - g(x_i)| \le \|\nabla g\|_\infty s\), \(L_{0,\beta}(g)s^\beta\), or \(2\|g\|_\infty\) respectively yields \[\mathbb{E}[Z_j \mid x_i] = \begin{cases} O( \sigma) \| g\|_{C^1}, & g \in C^1( {\cal M}),\\ O( \sigma^{\beta}) \| g\|_{0,\beta}, & g \in C^{0,\beta}( {\cal M}),\\ O(1) \|g\|_\infty, & g \in L^\infty( {\cal M}), \end{cases}\] with constants depending on \(( {\cal M}, p)\) through \(p_{\max}\), \(b_V\), \(|S^{d-1}|\).

The variance \(\mathrm{Var}(Z_j \mid x_i) \le \mathbb{E}[Z_j^2 \mid x_i]\) and uniform bound \(|Z_j| \le L_Z\) follow same as in the proof of Lemma 3: \(\nu_Z \asymp \| g\|_{C_1}^2 \epsilon^{-d/2+1}\), \(L_Z \asymp \| g\|_{C^1} \epsilon^{-d/2+1/2}\) for the \(C^1\) case, and analogously for the other two cases. Note that \(\nu_Z/L_Z^2 \asymp \epsilon^{d/2}\) with the implicit constant depending only on \(( {\cal M}, p)\) and the \(g\)-norm factors cancel. Bernstein with \(\tau = \sqrt{40 \log N\, \nu_Z/(N-1)}\) then requires \(\log N/(N-1) \le (9/40) \nu_Z/L_Z^2 \asymp \epsilon^{d/2}\) for large \(N\), satisfied under Assumption 3 with threshold independent from \(g\). Then, w.p. \(> 1 - 2N^{-10}\), the deviation is at most \(O( \sigma \sqrt{\log N/(N\sigma^{d})}) \| g\|_{C_1}\) for \(g \in C^1\) and analogous for the other cases, and each dominated by the corresponding \(\mathbb{E}[Z_j \mid x_i]\) under Assumption 3.

By union bound over \(i\), w.p. \(> 1 - 2N^{-9}\) uniformly in \(i\), which we call the good event \(E_3\), the claim 15 holds. The large-\(N\) threshold only depends on \(( {\cal M}, p)\) and not on \(g\). ◻

Proof of Theorem 2. The proof much follows that of Theorem 1, replacing \(P\) with \(\tilde{P}\), and Lemma 3 with Lemma 5. In particular, the constant \(C_8\) in the proof, which absorbs all big-O terms, now depends on \(( {\cal M}, p)\). Because \(\tilde{P}\) is also row-stochastic, it contracts vector-\(\infty\) norm. The other parts of the proof are the same as before. The tail probability per step changes from \(4N^{-9}\) to \(8 N^{-9}\), giving total tail \(8 n N^{-9}\) which is still \(\ll N^{-7}\). ◻

Proof of Theorem 3. Recall that \(f_m = Q_{m \sigma^2} f\), and \(\vec{f}_m = \rho_X f_m\), \(f_0 = f\). Let \(\hat{f}_0 = \vec{f}\), then \(\hat{f}_{k+1} = \tilde{P} \hat{f}_{k}\), then \(\hat{f}_m = \tilde{P}^m \vec{f}\). We then have \[\hat{F}_n(z) = \frac{ \sum_{j=1}^N \frac{ K_\epsilon( z, x_j) }{D_j} ( \hat{f}_{n-1} )_j}{\sum_{j=1}^N \frac{ K_\epsilon( z, x_j) }{D_j}}.\] The bound for \(\|\hat{f}_{n-1} - \vec{f}_{n-1} \|_\infty\) inherits from Theorem 2, and we only need to bound the error in the last step. Specifically, for any \(z\), \[\hat{F}_n(z) - f_n(z) = \underbrace{\Big( \frac{ \sum_{j=1}^N \frac{ K_\epsilon( z, x_j) }{D_j} ( \vec{f}_{n-1} )_j}{\sum_{j=1}^N \frac{ K_\epsilon( z, x_j) }{D_j}} - f_n(z) \Big)}_{=: B(z)} + \frac{ \sum_{j=1}^N \frac{ K_\epsilon( z, x_j) }{D_j} ( \hat{f}_{n-1} - \vec{f}_{n-1} )_j}{\sum_{j=1}^N \frac{ K_\epsilon( z, x_j) }{D_j}},\] and thus \[| \hat{F}_n(z) - f_n(z) | \le |B(z)| + \| \hat{f}_{n-1} - \vec{f}_{n-1}\|_\infty.\] We claim that \[\label{eq:claim-Lip-generalization} \sup_{z \in {\cal M}} |B(z)| = O(\epsilon^2 ) \| f\|_\infty + \text{ the one-step error as in Lemma \ref{lemma:one-step-C2-pC3} applied tof_{n-1} },\tag{16}\] for both cases (i)(ii) of \(f\), with tail probability \(\ll N^{-4}\); Meanwhile, we can bound \(\| \hat{f}_{n-1} - \vec{f}_{n-1} \|_\infty \le \sum_{m=1}^{n-1} \| r_{m}\|_\infty\) same as before. This would add another \(O(\sigma^4 \| f\|_\infty)\) to the final bound, which is dominated by \(O(t \sigma^2 \| f\|_\infty)\) since \(n \ge 1\), for both cases of \(f\). This would prove the theorem.

We first consider the Lipschitz property of \(B(z)\) over \({\cal M}\). We write \(B = \bar F_n - f_n\), where \[\bar F_n(z) = \frac{ \sum_{j=1}^N \frac{ K_\epsilon( z, x_j) }{D_j} ( \vec{f}_{n-1} )_j}{\sum_{j=1}^N \frac{ K_\epsilon( z, x_j) }{D_j}}.\] First \(\| \vec{f}_{n-1}\|_\infty \le \| f_{n-1}\|_\infty \le \|f\|_\infty\) by Lemma 12. Again by the row normalization, we have \(| \bar F_n(z)| \le \| \vec{f}_{n-1}\|_\infty \le \| f \|_\infty\). By definition, one can verify that \[\nabla_z \bar F_n(z)= \frac{\sum_{j=1}^N \frac{ \nabla_z K_\epsilon( z, x_j) }{D_j} ( (\vec{f}_{n-1} )_j - \bar F_n(z))}{ \sum_{j=1}^N \frac{ K_\epsilon( z, x_j) }{D_j}},\] this gives \[\begin{align} \| \nabla_z \bar F_n(z) \|_{op} & \le 2 \| f\|_\infty \frac{\sum_{j=1}^N \frac{ \| \nabla_z K_\epsilon( z, x_j) \|_{op} }{D_j} }{ \sum_{j=1}^N \frac{ K_\epsilon( z, x_j) }{D_j}} \\ & \le 2 \| f\|_\infty \frac{\sum_{j=1}^N \frac{\| z - x_j\|}{2\epsilon}\frac{ K_\epsilon( z, x_j) }{D_j} }{ \sum_{j=1}^N \frac{ K_\epsilon( z, x_j) }{D_j}} = O(\epsilon^{-1})\| f\|_\infty, \end{align}\] where in the 2nd inequality used that \[\| \nabla_z K_\epsilon(z ,x_j) \|_{op} = \frac{\| {\rm Proj}_{T_z {\cal M}} (x_j-z) \| }{2\epsilon} K_\epsilon(z ,x_j) \le \frac{\| z - x_j\|}{2\epsilon} K_\epsilon(z ,x_j)\] by that \(K_\epsilon (z, x_j) = \frac{1}{(4\pi \epsilon)^{d/2}}e^{- \| z - x_j \|^2/4 \epsilon}\). This shows that \(\| \nabla \bar F_n \|_\infty = O(\epsilon^{-1})\| f\|_\infty\). A refined analysis can bound \(\| \nabla \bar F_n \|_\infty\) to be \(O(\epsilon^{-1/2})\) instead of \(O(\epsilon^{-1})\), but the latter suffices for our purpose. At the same time, Lemma 4(ii) gives that \(\| \nabla f_n \|_\infty \le C_7 (n \epsilon)^{-1/2} \| f\|_\infty = O(\epsilon^{-1/2}) \| f\|_\infty\) by that \(n \ge 1\). Putting together, we have \[\| \nabla B \|_\infty \le \| \nabla \bar F_n \|_\infty + \| \nabla f_n \|_\infty = O( \epsilon^{-1}) \| f\|_\infty.\]

We aim for \(O(\epsilon^2)\) control when comparing \(B(z)\) to an anchor point \(B(z')\), and thus we construct an \(\delta\)-net \(\mathcal{N}\) of \({\cal M}\) (under geodesic distance), where \(\delta = \epsilon^3\). The cardinal number of \(\mathcal{N}\) can be bounded to be \(O(\delta^{-d}) = O(\epsilon^{-3d})\). Under Assumption 3, we further have \[|\mathcal{N}| = O(\epsilon^{-3d}) \ll ({N}/{\log N})^6 \ll N^6.\] At every point \(z' \in \mathcal{N}\), one can prove the concentration \(\sum_{j=1}^N \frac{ K_\epsilon(z', x_j)}{ D_j} = 1+ O \Big( \epsilon + \sqrt{ \frac{\log N}{N \epsilon^{d/2}} } \Big)\) in the same way as Lemma 16(ii), and the analogue of Lemma 5 to bound \[|\bar F_n(z') - f_{n}(z')|= \Big| \frac{ \sum_{j=1}^N \frac{ K_\epsilon( z', x_j) }{D_j} g (x_j)}{\sum_{j=1}^N \frac{ K_\epsilon( z', x_j) }{D_j}} - Q_{\sigma^2} g (z') \Big|\] in the same way for \(g=f_{n-1}\) for all the three cases of \(g\), with tail probability \(O(N^{-10})\) at the point \(z'\). Specifically, when \(n \ge 2\), \(f_{n-1} \in C^\infty( {\cal M})\) and use the \(g \in C^2\) case; if \(n=1\), use the \(g \in C^{0,\beta}( {\cal M})\) or \(L^\infty( {\cal M})\) case. Take a union bound, we prove the uniform error bound in the last step with tail probability \(\ll N^{-4}\). This gives that \(\max_{z \in \mathcal{N}}|B(z')|\) satisfies the same one-step error bound as in Lemma 5. Then, \(\forall z \in {\cal M}\), \(\exists z' \in \mathcal{N}\) s.t. \(d_ {\cal M}(z, z') \le \delta\), and then \[|B(z) | \le |B(z')| + \|\nabla B\|_\infty \delta \le \max_{z \in \mathcal{N}}|B(z')| + O( \epsilon^2) \| f\|_\infty,\] that is, \(\sup_{z \in {\cal M}} |B(z)|\) is bounded with another added \(O( \epsilon^2) \| f\|_\infty\). This proves the claim 16 . The tail probability of the first \(n-1\) steps is bounded by \(N^{-7}\) same as before. The overall tail probability is thus bounded by \(N^{-4}\) with large \(N\). ◻

Proof. We only need to prove the case when \(l>0\) as \(\phi_0\) is a constant. Suppose that \(\mathcal{M}\) has a Ricci curvature lower bound \(\texttt{Ric} \geq -Kg\) with \(K>0\). By the Bochner’s formula and \(-\Delta \phi_l=\lambda_l \phi_l\), we have \[\begin{align} \frac{1}{2}\Delta |\nabla \phi_l|^2=&|\nabla^2\phi_l|^2+g(\nabla\phi_l, \nabla \Delta \phi_l)+ \texttt{Ric}(\nabla\phi_l, \nabla\phi_l) \\ =&|\nabla^2\phi_l|^2- \lambda_l | \nabla \phi_l(x)|^2+ \texttt{Ric}(\nabla\phi_l, \nabla\phi_l). \end{align}\] Hence, \[\begin{align} |\nabla^2\phi_l|^2=& \frac{1}{2}\Delta |\nabla \phi_l|^2+ \lambda_l| \nabla \phi_l(x)|^2- \texttt{Ric}(\nabla\phi_l, \nabla\phi_l)\leq \frac{1}{2}\Delta |\nabla \phi_l|^2+ \lambda_l| \nabla \phi_l(x)|^2+K g(\nabla\phi_l, \nabla\phi_l) \nonumber \\ =& \frac{1}{2}\Delta |\nabla \phi_l|^2+ (\lambda_l+K)| \nabla \phi_l|^2. \end{align}\] We conclude that \[\begin{align} \label{proof:32Bochner32bound322} |\nabla^2\phi_l|^2-(\lambda_l+K)| \nabla \phi_l|^2 \leq \frac{1}{2}\Delta |\nabla \phi_l|^2. \end{align}\tag{19}\] Moreover, by the product rule and \(-\Delta \phi_l=\lambda_l \phi_l\), \[\begin{align} \label{proof:32Bochner32bound323} \Delta (\phi_l^2) =2 \phi \Delta \phi_l +2 g( \nabla\phi_l , \nabla\phi_l)=-2\lambda_l \phi_l^2+2|\nabla\phi_l|^2. \end{align}\tag{20}\] Define \(u= |\nabla \phi_l|^2+ B \lambda_l \phi_l^2\) with the constant \(B\) to be chosen. Then, by 19 and 20 , we have \[\begin{align} \Delta u= \Delta |\nabla \phi_l|^2+ B \lambda_l \Delta (\phi_l^2) \geq& 2|\nabla^2\phi_l|^2-2 (\lambda_l+K)| \nabla \phi_l|^2+ B \lambda_l (-2\lambda_l \phi_l^2+2|\nabla\phi_l|^2) \\ =&2|\nabla^2\phi_l|^2+2 (B\lambda_l-\lambda_l-K)| \nabla \phi_l|^2-2B \lambda_l^2 \phi_l^2 \end{align}\] Since \(\mathcal{M}\) is compact, \(u\) achieves maximum at \(x_0 \in \mathcal{M}\) with \(\Delta u (x_0) \leq 0\). Hence, by the above inequality, \[\begin{align} 2|\nabla^2\phi_l|^2(x_0)+2 (B\lambda_l-\lambda_l-K)| \nabla \phi_l|^2(x_0)-2B \lambda_l^2 \phi_l^2(x_0)\leq \Delta u(x_0) \leq 0. \end{align}\] Since \(2|\nabla^2\phi_l|^2(x_0) \geq 0\), we have \[\begin{align} \label{proof:32Bochner32bound324} 2 (B\lambda_l-\lambda_l-K)| \nabla \phi_l|^2(x_0)-2B \lambda_l^2 \phi_l^2(x_0) \leq 0. \end{align}\tag{21}\] Since \(l>0\), \(\lambda_l >0\). We specify \(B>0\) so that \(B\lambda_l-\lambda_l-K = \frac{B\lambda_l}{2}>0\) which is equivalent to \(B =2( 1+\frac{K}{\lambda_l})\). By 21 , we have \(|\nabla \phi_l|^2(x_0) \leq \frac{ 2B\lambda_l^2 \phi_l^2(x_0)}{2 (B\lambda_l-\lambda_l-K)} \leq 2 \lambda_l \phi_l^2(x_0)\).

Since \(u\) achieves maximum at \(x_0\), for any \(x \in \mathcal{M}\) \[\begin{align} |\nabla \phi_l|^2(x) \leq |\nabla \phi_l|^2(x)+ B \lambda_l \phi_l^2(x) =u(x) \leq u(x_0)= |\nabla \phi_l|^2(x_0)+ B \lambda_l \phi_l^2(x_0) \leq 2 \lambda_l \phi_l^2(x_0)+ B \lambda_l \phi_l^2(x_0). \end{align}\] Hence, \(|\nabla \phi_l|(x) \leq \sqrt{2+B} \sqrt{\lambda_l} |\phi_l|(x_0)\leq \sqrt{2+B} \sqrt{\lambda_l} \|\phi_l\|_\infty\). Note that by Lemma 9, \[\sqrt{2+B}=\sqrt{2+2( 1+\frac{K}{\lambda_l})} \leq \sqrt{2 (2+\frac{K}{\lambda_1})} \leq \sqrt{2 (2+\frac{K}{c_2})} =c_4.\] This proves the lemma. ◻

Proof. We only need to prove the case when \(l>0\) as \(\phi_0\) is a constant. By applying the Bochner-Weitzenbock’s identity to \(\nabla^2 \phi_l\), we have \[\begin{align} \label{Weitzenbock32bound320} \Delta|\nabla^2 \phi_l|^2=2|\nabla( \nabla^2 \phi_l)|^2+2(\nabla^2 \phi_l, \Delta \nabla^2 \phi_l)=2| \nabla^3 \phi_l|^2+2(\nabla^2 \phi_l, \Delta\nabla^2 \phi_l). \end{align}\tag{22}\] A straight forward calculation shows that \[\begin{align} \label{Weitzenbock32bound3201} \Delta \nabla_i\nabla_j \phi_l= \nabla_i\nabla_j \Delta\phi_l +\sum_{p,k=1}^d(R_{jp}g_{ik}+R_{ip}g_{jk}-2R_{kipj})\nabla_k\nabla_p\phi_l+\sum_{p=1}^d(\nabla_i R_{jp}+\nabla_j R_{pi}-\nabla_p R_{ij})\nabla_p\phi_l. \end{align}\tag{23}\] where \(R_{kipj}\) is the curvature tensor and \(R_{pi}\) is the Ricci curvature tensor.

We define the following \(2\) tensor fields. Let \(S\) be a \(2\) tensor field depending on \(\nabla^2 \phi_l\) with \[S_{ij}=\sum_{p,k=1}^d(R_{jp}g_{ik}+R_{ip}g_{jk}-2R_{kipj})\nabla_k\nabla_p\phi_l.\] Let \(S'\) be a \(2\) tensor field depending on \(\nabla \phi_l\) with \[S'_{ij}=\sum_{p=1}^d(\nabla_i R_{jp}+\nabla_j R_{pi}-\nabla_p R_{ij})\nabla_p\phi_l.\] Substituting 23 into 22 and using \(-\Delta \phi_l=\lambda_l \phi_l\), we have

\[\begin{align} \Delta |\nabla^2 \phi_l|^2=& 2 |\nabla^3\phi_l|^2 +2(\nabla^2 \phi_l, \nabla^2\Delta\phi_l)+2(\nabla^2 \phi_l, S)+2(\nabla^2 \phi_l,S')\\ =& 2 |\nabla^3\phi_l|^2 - 2\lambda_l | \nabla^2 \phi_l|^2+ \mathcal{E}_1(\nabla^2 \phi_l, \nabla^2 \phi_l)+\mathcal{E}_2(\nabla^2 \phi_l, \nabla \phi_l), \end{align}\] where \(\mathcal{E}_1(\nabla^2 \phi_l, \nabla^2 \phi_l)=(\nabla^2 \phi_l, S)\) is a quadratic form on symmetric 2-tensor fields whose coefficients can be expressed by the curvature tensor and \(\mathcal{E}_2(\nabla^2 \phi_l, \nabla \phi_l)=(\nabla^2 \phi_l, S')\) is a bilinear form whose coefficients can be expressed by the covariant derivative of the Ricci curvature tensor. Since the sectional curvatures determine the curvature tensor, there are constants \(c'_1>0\) depending on \(d\) and the sectional curvature bounds and \(c'_2>0\) depending on \(d\) and the bounds of covariant derivative of the Ricci curvature such that \[\begin{align} \label{Weitzenbock32bound321} \Delta |\nabla^2 \phi_l|^2 \geq & 2 |\nabla^3\phi_l|^2 - 2\lambda_l | \nabla^2 \phi_l|^2-c'_1 |\nabla^2 \phi_l|^2-c'_2|\nabla \phi_l||\nabla^2 \phi_l| \nonumber \\ =& 2 |\nabla^3\phi_l|^2 - (2\lambda_l +c'_1)| \nabla^2 \phi_l|^2-c'_2|\nabla \phi_l||\nabla^2 \phi_l|. \end{align}\tag{24}\] Define \(u= |\nabla^2 \phi_l|^2+ B \lambda_l |\nabla\phi_l|^2\) with the constant \(B>0\) to be chosen. Suppose that \(\mathcal{M}\) has a Ricci curvature lower bound \(\texttt{Ric} \geq -Kg\) with \(K>0\). Since \(|\nabla^3\phi_l|^2 \geq 0\), by applying 19 and 24 , we have \[\begin{align} \Delta u \geq & 2 |\nabla^3\phi_l|^2 - (2\lambda_l +c'_1)| \nabla^2 \phi_l|^2 -c'_2|\nabla \phi_l||\nabla^2 \phi_l|+2 B \lambda_l (|\nabla^2\phi_l|^2-(\lambda_l+K)| \nabla \phi_l|^2) \\ \geq & (2 B \lambda_l-2\lambda_l-c'_1)|\nabla^2\phi_l|^2 -c'_2|\nabla \phi_l||\nabla^2 \phi_l|- 2 B \lambda_l(\lambda_l+K)| \nabla \phi_l|^2. \end{align}\] Since \(|\nabla \phi_l||\nabla^2 \phi_l| \leq |\nabla \phi_l|^2+|\nabla^2 \phi_l|^2\), we have \[\Delta u \geq (2 B \lambda_l-2\lambda_l-c'_1-c'_2)|\nabla^2\phi_l|^2- [2 B \lambda_l(\lambda_l+K)+c'_2]| \nabla \phi_l|^2.\] We will choose \(B>0\) so that \(2 B \lambda_l-2\lambda_l-c'_1-c'_2>0\) and we have \(2 B \lambda_l(\lambda_l+K)+c'_2>0\). Since \(\mathcal{M}\) is compact, \(u\) achieves maximum at \(x_0 \in \mathcal{M}\) with \(\Delta u (x_0) \leq 0\). Hence, by the above inequality, \[(2 B \lambda_l-2\lambda_l-c'_1-c'_2)|\nabla^2\phi_l|^2(x_0)- [2 B \lambda_l(\lambda_l+K)+c'_2]| \nabla \phi_l|^2(x_0)\leq \Delta u (x_0) \leq 0\] Then, we have \[\begin{align} \label{Weitzenbock32bound322} |\nabla^2\phi_l|^2(x_0) \leq \frac{2 B \lambda_l(\lambda_l+K)+c'_2}{2 B \lambda_l-2\lambda_l-c'_1-c'_2}| \nabla \phi_l|^2(x_0). \end{align}\tag{25}\] Therefore, by 25 , for any \(x \in \mathcal{M}\) we have \[\begin{align} |\nabla^2\phi_l|^2(x) \leq & |\nabla^2 \phi_l|^2(x)+ B \lambda_l |\nabla\phi_l|^2(x)=u(x) \leq u(x_0)= |\nabla^2 \phi_l|^2(x_0)+ B \lambda_l |\nabla\phi_l|^2(x_0) \nonumber\\ \leq& \Big ( \frac{2 B \lambda_l(\lambda_l+K)+c'_2}{2 B \lambda_l-2\lambda_l-c'_1-c'_2}+B \lambda_l \Big) | \nabla \phi_l|^2(x_0) .\label{Weitzenbock32bound323} \end{align}\tag{26}\] We choose \(B=\frac{c'_1+c'_2+2\lambda_l}{\lambda_l}>0\) so that \(2 B \lambda_l-2\lambda_l-c'_1-c'_2=B \lambda_l>0\). For \(l>0\), by Lemma 9, \(c_2 \leq \lambda_l\). Therefore, \[\begin{align} \frac{2 B \lambda_l(\lambda_l+K)+c'_2}{2 B \lambda_l-2\lambda_l-c'_1-c'_2}+B \lambda_l =& 2(\lambda_l+K)+\frac{c'_2}{c'_1+c'_2+2\lambda_l}+c'_1+c'_2+2\lambda_l \\ \leq &\lambda_l \left(4+\left(\frac{c'_2}{c'_1+c'_2+2\lambda_l}+c'_1+c'_2+2K\right)/c_2\right)\\ \leq &\lambda_l \left(4+\left(\frac{c'_2}{c'_1+c'_2}+c'_1+c'_2+2K\right)/c_2\right) \end{align}\] By the above simplification, 26 implies that \(\sup_{x \in \mathcal{M}}| \nabla^2 \phi_l | (x)\leq c_5 \sqrt{\lambda_l} \sup_{x \in \mathcal{M}} | \nabla \phi_l | (x)\) with \[c_5=\sqrt{ 4+\left(\frac{c'_2}{c'_1+c'_2}+c'_1+c'_2+2K\right)/c_2}.\] ◻

Proof of Lemma 7. Recall that for any \(x, y \in \mathcal{M}\) and any \(t>0\), \[\begin{align} \mathcal{H}_t(x, y)=\sum_{i=0}^{\infty}e^{-\lambda_i t} \phi_i(x)\phi_i(y). \end{align}\] Therefore for any \(t>0\), \[\begin{align} \label{proof:32spectral32series32bound321} \sup_{x, y \in \mathcal{M}} |\nabla^k_x \mathcal{H}_t(x,y) | \leq \sum_{i=0}^{\infty}e^{-\lambda_i t/2} e^{-\lambda_i t/2} \sup_{x \mathcal{M}} |\nabla^k \phi_i |(x) \|\phi_i\|_\infty=&\sum_{i=1}^{\infty}e^{-\lambda_i t/2} e^{-\lambda_i t/2} \sup_{x \mathcal{M}} |\nabla^k \phi_i |(x) \|\phi_i\|_\infty \nonumber \\ \leq& e^{-\lambda_1 t/2} \sum_{i=1}^{\infty}e^{-\lambda_i t/2} \sup_{x \mathcal{M}} |\nabla^k \phi_i |(x) \|\phi_i\|_\infty. \end{align}\tag{27}\] where we use that \(\phi_0\) is a constant in the second last step and \(e^{-\lambda_i t/2} \leq e^{-\lambda_1 t/2}\) for all \(i \geq 1\) in the last step.

If we prove that for \(t\geq t_2>0\) \[\begin{align} \label{proof:32spectral32series32bound323} \sum_{i=1}^{\infty}e^{-\lambda_i t/2} \sup_{x \in\mathcal{M}} |\nabla^k \phi_i |(x) \|\phi_i\|_\infty \leq C (t_2), \end{align}\tag{28}\] then the lemma is proved by substituting 28 into 27 .

Proof of eq. ¿eq:proof:32spectral32series32bound323? : By Lemma 8, Lemma 9, Lemma 10, and Lemma 11, \[\begin{align} & e^{-\lambda_i t/2} \leq e^{-\frac{1}{2}c_2t_2 i^{2/d}}; && \|\phi_i\|_\infty \leq c_1c_3^{\frac{d-1}{4}} i^{\frac{d-1}{2d}}; \\ & \sup_{x \mathcal{M}} |\nabla \phi_i |(x) \leq c_1c_3^{\frac{d+1}{4}}c_4 i^{\frac{d+1}{2d}}; & & \sup_{x \mathcal{M}} |\nabla^2 \phi_i |(x) \leq c_1c_3^{\frac{d+3}{4}} c_4c_5 i^{\frac{d+3}{2d}}. \end{align}\] Therefore, we have \[\begin{align} & \sum_{i=1}^{\infty}e^{-\lambda_i t/2} \sup_{x \mathcal{M}} |\nabla \phi_i |(x) \|\phi_i\|_\infty \leq c_1^2 c_3^{d/2} c_4 \sum_{i=1}^{\infty}e^{-\frac{1}{2}c_2t_2 i^{2/d}} i; \\ & \sum_{i=1}^{\infty}e^{-\lambda_i t/2} \sup_{x \mathcal{M}} |\nabla^2 \phi_i |(x)\|\phi_i\|_\infty \leq c_1^2 c_3^{(d+1)/2} c_4 c_5 \sum_{i=1}^{\infty}e^{-\frac{1}{2}c_2t_2 i^{2/d}} i^{(d+1)/d}; \end{align}\] By the integral test, we have \[\begin{align} \sum_{i=1}^{\infty}e^{-\frac{1}{2}c_2t_2 i^{2/d}} i^{(d+1)/d} \leq& e^{-\frac{1}{2}c_2t_2} +\int_{1}^\infty e^{-\frac{1}{2}c_2t_2 u^{2/d}} u^{(d+1)/d} du \leq 1+\int_{0 }^\infty e^{-\frac{1}{2}c_2t_2 u^{2/d}} u^{(d+1)/d} du \\ =& 1+\frac{d}{2}(c_2 t_2/2)^{-(2d+1)/2} \int_{0}^\infty e^{-v}v^{d-\frac{1}{2}}dv \quad\quad (\text{Let } v=\frac{c_2t_2 u^{2/d}}{2}.)\\ =& 1+\frac{d\Gamma(d+\frac{1}{2})}{2} (\frac{2}{c_2})^{(2d+1)/2} t_2^{-(2d+1)/2} =c'_2(t_2). \end{align}\] Similarly, \(\sum_{i=1}^{\infty}e^{-\frac{1}{2}c_2t_2 i^{2/d}} i \leq 1+ \frac{d}{2} \Gamma(d) (\frac{2}{c_2})^d t_2^{-d}=c'_1(t_2).\) Finally, let \[C(t_2)= \max(c_1^2 c_3^{d/2} c_4 c'_1(t_2), c_1^2 c_3^{(d+1)/2} c_4 c_5 c'_2(t_2))\] which proves 28 .

Based on the expression of \(C(t_2)\), \(C(t_2)\) depends on \(t_2\), \(d\), the diameter of \(\mathcal{M}\), the volume of \(\mathcal{M}\), the injectivity radius, bounds of the Ricci curvature and its covariant derivative, and the sectional curvature bounds of \(\mathcal{M}\). ◻

Proof. \(|Q_t f(x) | \le \int_ {\cal M}{\cal H}_t(x,y) |f(y)|dV(y) \le \| f\|_\infty \int_ {\cal M}{\cal H}_t(x,y) dV(y)\). ◻

Proof of Lemma 4. For case (i), observe that \(\int_ {\cal M}{\cal H}_t(x,y) dV(y)=1\), and thus \[\int_ {\cal M}\nabla_x {\cal H}_t(x,y) \, dV(y) = 0, \quad \int_ {\cal M}\nabla_x^2 {\cal H}_t(x,y)\, dV(y) = 0.\] As a result, for \(k=1,2\), \[\nabla^k Q_t f(x) = \int_ {\cal M}\nabla^k_x {\cal H}_t(x,y) f(y) dV(y) = \int_ {\cal M}\nabla^k_x {\cal H}_t(x,y) (f(y) - f(x))dV(y).\] Recall that \(| T(x)|\) stands for the Frobenius norm of the tensor \(T(x)\). Then, we have \[\label{eq:bound-der-Qtf-proof-1} | \nabla^k Q_t f(x) | \le \int_ {\cal M}| \nabla^k_x {\cal H}_t(x,y) | | f(y) - f(x)| dV(y), \quad k = 1,2.\tag{29}\] Recall the constant \(t_1\) as defined in 6 , \(t_1 \le t_0 < 1\). We will consider when \(t < t_1\) and \(t \ge t_1\) separately.

a) \(t < t_1\). By [15], there are constants \(D_1\), \(D_2\) that depend on \({\cal M}\) s.t. \[|\nabla_x^k {\cal H}_t(x,y)| \le D_k \big( \frac{d_ {\cal M}(x,y)}{t} + \frac{1}{\sqrt{t}} \big)^k {\cal H}_t(x,y), \quad \forall x, y \in {\cal M}, \, \forall 0< t \le 1, \quad k=1,2.\] Combined with the Gaussian bound of \({\cal H}_t\) in Lemma 6(ii), we have \[|\nabla_x^k {\cal H}_t(x,y)| \le D_k C_3 \big( \frac{d_ {\cal M}(x,y)}{t} + \frac{1}{\sqrt{t}} \big)^k t^{-d/2} e^{- \frac{ d_ {\cal M}( x,y)^2}{ 5 t}}.\] Using \((a+b)^2 \leq 2(a^2+b^2)\) and \(\sup_{u \geq 0} u^k e^{-u^2/30} = (15k)^{k/2}e^{-k/2} \leq 12\) for \(k=1,2\), one verifies that \(\big(\frac{s}{t}+\frac{1}{\sqrt{t}}\big)^k e^{-s^2/(5t)} \leq 25\, t^{-k/2} e^{-s^2/(6t)}\) for all \(s \geq 0\), \(t > 0\). As a result, let \(C_3':= 25 \max \{ D_1, D_2\} C_3\), we have \[\label{eq:gaussian-envelope-der-Ht-proof-1} |\nabla_x^k {\cal H}_t(x,y)| \le C_3' t^{-(d+k)/2} e^{- \frac{ d_ {\cal M}( x,y)^2}{ 6 t}}, \quad \forall x, y \in {\cal M}, \, \forall t \le t_0 < 1, \, k=1,2,\tag{30}\] where \(C_3'\) is a constant depending on \({\cal M}\).

Because \(t_1 \le t_0 < 1\), this holds when \(t < t_1\). Back to 29 , we then have \[| \nabla^k Q_t f(x) | \le C_3' \int_ {\cal M}t^{-(d+k)/2} e^{- \frac{ d_ {\cal M}( x,y)^2}{ 6 t}} | f(y) - f(x)| dV(y).\] By definition of \(t_1\), when \(t < t_1\), \(2 \delta(t) < \delta_0 < \xi\). We then decompose the integral into when \(y \in B_{2\delta(t)}(x)\) and \(y \notin B_{2\delta(t)}(x)\) and bound them respectively, as in the proof of Lemma 2(ii). Specifically, for any \(y \notin B_{2\delta(t)}(x)\), one can verify that \(t^{-d/2} e^{- { d_ {\cal M}( x,y)^2}/{( 6 t)}} \le t^5\), and then \[\int_{ {\cal M}\backslash B_{2 \delta(t)}(x)} t^{-d/2} e^{- \frac{ d_ {\cal M}( x,y)^2}{ 6 t}} | f(y) - f(x) | dV(y) \le 2 \|f\|_\infty \mathrm{Vol}( {\cal M}) t^5;\] In addition, similarly as before, \[\int_{ B_{2 \delta(t)}(x)} t^{-d/2} e^{- \frac{ d_ {\cal M}( x,y)^2}{ 6 t}} | f(y) - f(x) | dV(y) \le L_{0,\beta}(f) b_V |S^{d-1}| m_{d,4} t^{\beta/2},\] where \(m_{d,4}:= \int_0^{\infty} e^{-u^2/6} (1+u)u^{d-1} du\) is a constant determined by \(d\). Putting together, this gives \[\int_ {\cal M}t^{-d/2} e^{- \frac{ d_ {\cal M}( x,y)^2}{ 6 t}} | f(y) - f(x)| dV(y) \le C_{1,a} \| f\|_{0,\beta}(t^5 + t^{\beta/2}) \le 2 C_{1,a} \| f\|_{0,\beta} t^{\beta/2},\] since \(t<1\), where \(C_{1,a}\) is a constant depending on \({\cal M}\) (and \(d\)). This proves that \[| \nabla^k Q_t f(x) | \le 2 C_3' C_{1,a} \| f\|_{0,\beta} t^{-k/2 + \beta/2}, \quad \forall t < t_1, \quad k =1,2.\]

b) \(t \ge t_1\). We apply Lemma 7 with \(t_2= t_1\). Note that \(\lambda_1 > 0\) is a constant depending on \({\cal M}\). By that for any \(c>0\) and \(k=1,2\), \(\sup_{t > 0} t^{k/2} e^{- c t } \le c'\) for some \(c'\), we have \(\forall t \ge t_1\), \[\label{eq:upper-bound-der-Ht-proof-2} \left| \nabla_x^k {\cal H}_t(x, y) \right| \leq C_{b} t^{-k/2}, \quad \forall x, y \in {\cal M}, \quad k = 1, 2,\tag{31}\] where \(C_{b}\) is a constant depending on \({\cal M}\) (including the dependence on \(t_1\)). Then, back to 29 , we have \[| \nabla^k Q_t f(x) | \le 2 \mathrm{Vol}( {\cal M}) C_{b} \|f\|_\infty t^{-k/2}.\] Note that when \(t \ge t_1\), \(t^{-\beta/2} \le t_1^{-\beta/2} \le t_1^{-1/2}\), we then have \[| \nabla^k Q_t f(x) | \le 2 \mathrm{Vol}( {\cal M}) C_{b} t_1^{-1/2} \|f\|_\infty t^{-k/2+\beta/2}, \quad \forall t \ge t_1, \quad k = 1,2.\]

Combining a) and b), and by that the Frobenius norm upper bounds the operator norm of a tensor, we have that for any \(t>0\), \[\| \nabla^k Q_t f(x) \|_{op} \le | \nabla^k Q_t f(x) | \le C_{7,1} \| f\|_{0,\beta} t^{-k/2 + \beta/2}, \quad k=1,2,\] where \(C_{7,1} = 2 \max\{ C_3' C_{1,a} , \mathrm{Vol}( {\cal M}) C_{b} t_1^{-1/2} \}\) is a constant depending on \({\cal M}\) only.

For case (ii), by that \(\nabla^k Q_t f(x) = \int_ {\cal M}\nabla^k_x {\cal H}_t(x,y) f(y) dV(y)\), we have \[| \nabla^k Q_t f(x) | \le \| f\|_\infty \int_ {\cal M}| \nabla^k_x {\cal H}_t(x,y)| dV(y).\] Similarly as above, when a) \(t < t_1\), we have the Gaussian envelope of \(|\nabla_x^k {\cal H}_t(x,y)|\) as in 30 , and then \[\int_ {\cal M}| \nabla^k_x {\cal H}_t(x,y)| dV(y) \le C_3' \int_ {\cal M}t^{-(d+k)/2} e^{- \frac{ d_ {\cal M}( x,y)^2}{ 6 t}} dV(y),\] where by the \(B_{2 \delta(t)}\) ball truncation one can verify that \[\int_ {\cal M}t^{-d/2} e^{- \frac{ d_ {\cal M}( x,y)^2}{ 6 t}} dV(y) \le \mathrm{Vol}( {\cal M}) t^5 + C_{2,a}',\] and \(C_{2,a}'=b_V |S^{d-1}| m_{d,4}\) is a constant depending on \({\cal M}\) (and \(d\)). Putting together, and by that \(t < 1\), we have \[| \nabla^k Q_t f(x) | \le C_3' (\mathrm{Vol}( {\cal M})+ C_{2,a}') \| f\|_\infty t^{-k/2}, \quad \forall t < t_1;\] When b) \(t> t_1\), we still have 31 , and then \[| \nabla^k Q_t f(x) | \le \mathrm{Vol}( {\cal M}) C_{b} \| f\|_\infty t^{-k/2}, \quad \forall t \ge t_1.\] Putting together, we have that for any \(t>0\), \[\| \nabla^k Q_t f(x) \|_{op} \le | \nabla^k Q_t f(x) | \le C_{7,2} \| f\|_{\infty} t^{-k/2}, \quad k=1,2,\] where \(C_{7,2} = \max\{ C_3' (\mathrm{Vol}( {\cal M})+ C_{2,a}') , \mathrm{Vol}( {\cal M}) C_{b} \}\) is a constant depending on \({\cal M}\) only.

Finally, let \(C_7 = \max\{ C_{7,1}, C_{7,2} \}\) finishes the proof of the lemma. ◻

Proof of Lemma 16. For (i), the proof is the same as in that of [11] except that we use a different estimate for the integral \(\int_ {\cal M}K_\epsilon(x,y) p(y) dV(y)\): when \(p \in C^{3}( {\cal M})\) and thus is in \(C^{2,1}( {\cal M})\), and recall that \(h(r) = \frac{1}{(4\pi)^{d/2}} e^{-r /4}\), by [30], we have \[\int_{ {\cal M}} K_\epsilon(x, y) p(y) dV(y) = p(x) + \epsilon( \omega p + \Delta p)(x) + O(\epsilon^{3/2}) \| p\|_{C^3},\] where the constant in big-O depends on \({\cal M}\). This gives rise to the \(O(\epsilon^{3/2})\) error term in (i), replacing the \(O(\epsilon^2)\) error in [11].

The rest of the proof, including that of (ii) is the same as in [11]. In particular, (ii) uses that \(\frac{1}{N} D_i = p(x_i) ( 1+ O(\epsilon + \sqrt{ \frac{\log N}{N \epsilon^{d/2}} }))\) uniformly, which still follows from (i), since \(\tilde{p}_\epsilon(x) = p(x) + O(\epsilon)\) uniformly. The bound for uniform \(p\) in (i) follows as a special case. ◻