{'fraction_non_alphanumeric': 0.06259723923334105, 'fraction_numerical': 0.012016286537124698, 'mean_word_length': 3.7144194756554305, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Consistent Interpolating Ensembles via the Manifold-Hilbert Kernel

Recent research in the theory of overparametrized learning has sought to establish generalization guarantees in the interpolating regime. Such results have been established for a few common classes of methods, but so far not for ensemble methods. We devise an ensemble classification method that simultaneously interpolates the training data, and is consistent for a broad class of data distributions. To this end, we define the manifold-Hilbert kernel for data distributed on a Riemannian manifold. We prove that kernel smoothing regression using the manifold-Hilbert kernel is weakly consistent in the setting of Devroye et al. 1998. For the sphere, we show that the manifold-Hilbert kernel can be realized as a weighted random partition kernel, which arises as an infinite ensemble of partition-based classifiers.


Introduction
Ensemble methods are among the most often applied learning algorithms, yet their theoretical properties have not been fully understood [11]. Based on empirical evidence, Wyner et al. [40] conjectured that interpolation of the training data plays a key role in explaining the success of AdaBoost and random forests. However, while a few classes of learning methods have been analyzed in the interpolating regime [5,3], ensembles have not.
Towards developing the theory of interpolating ensembles, we examine an ensemble classification method for data distributed on the sphere, and show that this classifier interpolates the training data and is consistent for a broad class of data distributions. To show this result, we develop two additional contributions that may be of independent interest. First, for data distributed on a Riemannian manifold M , we introduce the manifold-Hilbert kernel K H M , a manifold extension of the Hilbert kernel [37]. Under the same setting as Devroye et al. [19], we prove that kernel smoothing regression with K H M is weakly consistent while interpolating the training data. Consequently, the classifier obtained by taking the sign of the kernel smoothing estimate has zero training error and is consistent.
Second, we introduce a class of kernels called weighted random partition kernels. These are kernels that can be realized as an infinite, weighted ensemble of partition-based histogram classifiers. Our main result is established by showing that when M = S d , the d-dimensional sphere, the manifold-Hilbert kernel is a weighted random partition kernel. In particular, we show that on the sphere, the manifold-Hilbert kernel is a weighted ensemble based on random hyperplane arrangements. This implies that the kernel smoothing classifier is a consistent, interpolating ensemble on S d . To our knowledge, this is the first demonstration of an interpolating ensemble method that is consistent for a broad class of distributions in arbitrary dimensions.

Problem statement
Consider the problem of binary classification on a Riemannian manifold M . Let (X, Y ) be random variables jointly distributed on M × {±1}. Let D n := {(X i , Y i )} n i=1 be the (random) training data consisting of n i.i.d copies of X, Y . A classifier, i.e., a mapping from D n to a function f (• D n ) : M → {±1}, has the interpolating-consistent property if, when X has a continuous distribution, both of the following hold: 1) f (X i D n ) = Y i , for all i ∈ {1, . . . , n}, and 2) Pr{f (X) = Y } in probability as n → ∞.
Our goal is to find an interpolating-consistent ensemble of histogram classifiers, to be defined below.
A partition on M , denoted by P, is a set of subsets of M such that P ∩ P = ∅ for all P, P ∈ P and M = P ∈P P . Given x ∈ M , let P[x] denote the unique element P ∈ P such that x ∈ P . The set of all partitions on a space M is denoted Part(M ). The histogram classifier with respect to D n over P is the sign of the function h(• D n , P) : M → R given by where I is the indicator function.
Definition 1.1. A weighted random partition (WRP) over M is a 3-tuple (Θ, P, α) consisting of (i) parameter space of partitions: a set Θ where P θ ∈ Part(M ) for each θ ∈ Θ, (ii) random partitions: a probability measure P on Θ, and (iii) weights: a nonnegative function α : Θ → R ≥0 . Below, WRPs will be denoted with 2-letter names in the sans-serif font, e.g., "rp" for a generic WRP, and "ha" for the weighted hyperplane arrangement random partition (Definition 5.1). The weighted random partition kernel associated to rp = (Θ, P, α) is defined as When α ≡ 1, we recover the notion of unweighted random partition kernel introduced in [18]. Note that the kernel is symmetric since I{x ∈ P θ [z]} = I{z ∈ P θ [x]}. If K rp M < ∞, then K rp M is a positive definite (PD) kernel. When K rp M can evaluate to ∞, the definition of a PD kernel is not applicable since the positive definite property is defined only for to kernels taking finite values [9].
Let sgn : R ∪ {±∞} → {±1} be the sign function. For a WRP, define the weighted infinite-ensemble Note that the equality on the right follows immediately from linearity of the expectation and the definition of h(• D n , P θ )] in Equation (2). Main problem. Find a WRP such that sgn( u(• D n , K rp M )) has the interpolating-consistent property.

Outline of approach and contributions
In the regression setting, we have (X, Y ) jointly distributed on M × R. Let m( 1 The "singular" modifier refers to the fact that K(x, x) = +∞ for all x ∈ M .
We note that Equation (5) is referred as the Nadaraya-Watson estimate in [7]. Now, we simply write m n (x) instead of m(x D n , K) when there is no ambiguity. Similarly, we write u n (x) instead of u(x D n , K) from earlier. Note that sgn( m n (x)) = sgn( u n (x)) if n j=1 K(x, X j ) > 0. Observe that m n is interpolating by construction. Let µ X denote the marginal distribution of X. The L 1 -error of m n in approximating m is J n := M | m n (x) − m(x)|µ X (dx). For M = R d and the Hilbert kernel Devroye et al. [19] proved L 1 -consistency for regression: J n → 0 in probability when Y is bounded and X is continuously distributed.
Our contributions. Our primary contribution is to demonstrate an ensemble method with the consistentinterpolating property. Toward this end, in Section 3, we introduce the manifold-Hilbert kernel K H M on a Riemannian manifold M . When show that when M is complete, connected, and smooth, kernel smoothing regression with K H M has the same consistency guarantee (Theorem 3.2) as K H R d mentioned in the preceding paragraph. In Section 5, we consider the case when M = S d , and show that the manifold-Hilbert kernel K H S d is a weighted random partition kernel (Proposition 5.2).
Devroye et al. [19,Section 7] observed that the L 1 -consistency of m n for regression implies the consistency for classification of sgn • u n . Furthermore, m n is interpolating for regression implies that sgn • u n is interpolating for classification. These observations together with our results demonstrate the existence of a weighted infinite-ensemble classifier with the interpolating-consistent property.

Related work
Kernel regression. Kernel smoothing regression, or simply kernel regression, is an interpolator when the kernel used is singular, a fact known to Shepard [37] in 1968. Devroye et al. [19] showed that kernel regression with the Hilbert kernel is interpolating and weakly consistent for data with a density and bounded labels. Using singular kernels with compact support, Belkin et al. [7] showed that minimax optimality can be achieved under additional distributional assumptions.
Random forests. Wyner et al. [40] proposed that interpolation may be a key mechanism for the success of random forests and gave a compelling intuitive rationale. Belkin et al. [5] studied empirically the double descent phenomenon in random forests by considering the generalization performance past the interpolation threshold. The PERT variant of random forests, introduced by Cutler and Zhao [17], provably interpolates in 1-dimension. Belkin et al. [6] pose as an interesting question whether the result of Cutler and Zhao [17] extends to higher dimension. Many work have established consistency of random forest and its variants under different settings [13,10,36]. However, none of these work addressed interpolation.
Boosting. For classification under the noiseless setting (i.e., the Bayes error is zero), AdaBoost is interpolating and consistent (see Freund and Schapire [23, first paragraph of Chapter 12]). However, this setting is too restrictive and the result does not answer if consistency is possible when fitting the noise. Bartlett and Traskin [4] proved that AdaBoost with early stopping is universally consistent, however without the interpolation guarantee. To the best of our knowledge, whether AdaBoost or any other variant of boosting can be interpolating and consistent remains open.
Random partition kernels. Breiman [14] and Geurts et al. [25] studied infinite ensembles of simplified variants of random forest and connections to certain kernels. Davies and Ghahramani [18] formalized this connection and coined the term random partition kernel. Scornet [35] further developed the theory of random forest kernels and obtained upper bounds on the rate of convergence. However, it is not clear if these variants of random forests are interpolating.
Previously defined (unweighted) random partition kernels are bounded, and thus cannot be singular. On the other hand, the manifold-Hilbert kernel is always singular. To bridge between ensemble methods and theory on interpolating kernel smoothing regression, we propose weighted random partitions (Definition 1.1), whose associated kernel (Equation 3) can be singular.
Learning on Riemannian manifolds. Strong consistency of a kernel-based classification method on manifolds has been established by Loubes and Pelletier [29]. However, the result requires the kernel to be bounded and thus the method is not guaranteed to be interpolating. See Feragen and Hauberg [22] for a review of theoretical results regarding kernels on Riemannian manifolds.
Beyond kernel methods, other classical methods for Euclidean data have been extended to Riemannian manifolds, e.g., regression [38], classification [41], and dimensionality reduction and clustering [42] [31]. To iii. iv. v. the best of our knowledge, no previous works have demonstrated an interpolating-consistent classifiers on manifolds other than R d . In many applications, the data naturally belong to a Riemannian manifold. Spherical data arise from a range of disciplines in natural sciences. See the influential textbook by Mardia and Jupp [30,Ch.1 §4]. For applications of the Grassmanian manifold in computer vision, see Jayasumana et al. [27] and the references therein. Topological data analysis [39] presents another interesting setting of manifold-valued data in the form of persistence diagrams [2,28].

Background on Riemannian Manifolds
We give an intuitive overview of the necessary concepts and results on Riemannian manifolds. A longer, more precise version of this overview is in the Appendix Section A.1.
A smooth d-dimensional manifold M is a topological space that is locally diffeomorphic 2 to open subsets of R d . For simplicity, suppose that M is embedded in R N for some N ≥ d, e.g., S d ⊆ R d+1 . Let x ∈ M be a point. The tangent space at x, denoted T x M , is the set of vectors that is tangent to M at x. Since linear combinations of tangent vectors are also tangent, the tangent space T x M is a vector space. Tangent vectors can also be viewed as the time derivative of smooth curves. In particular, let x ∈ M . If > 0 is an open set and γ : (− , ) → M is a smooth curve such that γ(0) = x, then dγ dt (0) ∈ T x M . A Riemannian metric on M is a choice of inner product ·, · x on T x M for each x such that ·, · x varies smoothly with x. Naturally, z x := z, z x defines a norm on T x M . The length of a piecewise smooth γ is a piecewise smooth curve from x to ξ}, which is a metric on M in the sense of metric spaces (see Sakai [34,

The Manifold-Hilbert kernel
Throughout the remainder of this work, we assume that M is a complete, connected, and smooth Riemannian manifold of dimension d.
Let λ M be the Riemann-Lebesgue volume measure of M . Integration with respect to this measure is denoted M f dλ M for a function f : M → R. For details of the construction of λ M , see Amann and Escher [1, Proposition 1.5]. When M = R d , λ M is the ordinary Lebesgue measure and R d f dλ R d is the ordinary Lebesgue integral. For this case, we simply write λ instead of λ R d .
We now state our first main result, a manifold theory extension of Devroye et al. [19,Theorem 1].
In words, the kernel smoothing regression estimate m n based on the manifold-Hilbert kernel is consistent and interpolates the training data, provided X has a density and Y is bounded. As a consequence, following the same logic as in Devroye et al. [19], the associated classifier sgn • u n has the interpolating-consistent property. Before proving Theorem 3.2, we first review key concepts in probability theory on Riemannian manifolds.  The function f is said to be a probability density function (PDF) of X.

Probability on Riemannian manifolds
Next, we recall the definition of conditional distributions, following Dudley [21, Ch. 10 §2]: Let P X (·) be the probability measure corresponding to the marginal distribution of X. A conditional distribution for Y given X is a collection of probability measures P Y |X (·|x) on R indexed by x ∈ M satisfying the following: . The existence of a conditional probability for a joint distribution (X, Y ) is guaranteed by Dudley [21, Theorem 10.2.2]. When (X, Y ) has a joint density f XY and marginal density f X , the above definition gives the classical formula

Lebesgue points on manifolds
Devroye et al. [19] proved Theorem 3.2 when M = R d and, moreover, that part 1 holds for the so-called Lebesgue points, whose definition we now recall. Definition 3.6. Let f : M → R be an absolutely integrable function and x ∈ M . We say that x is a Lebesgue For an integrable function, the following result states that almost all points are its Lebesgue points. For the proof, see Fukuoka [24,Remark 2.4].  The above result will be used in our proof of Theorem 3.2 below.

Proof of Theorem 3.2
The focal point of the first subsection is Lemma 4.1 which shows the Borel measurability of extensions of the so-called Riemannian logarithm. The second subsection contains two key results regarding densities of M -valued random variables transformed by the Riemannian logarithm. The final subsection proves Theorem 3.2 leveraging results from the preceding two subsections.

The Riemannian logarithm
Throughout, x is assumed to be an arbitrary point of M . Let U x M = {v ∈ T x M : v x = 1} ⊆ T x M denote the set of unit tangent vectors. Define a function τ x : U x M → (0, ∞] as follows 5 : The tangent cut locus is the setC The tangent interior set isĨ x := {tu : 0 ≤ t < τ x (u), u ∈ U x M } and the interior set is the set Consider the example where M = S 2 as in Figure 1.
, the open disc of radius π centered at the origin. When restricted toĨ x , the exponential map exp x |Ĩ x :Ĩ x → I x is a diffeomorphism. Its functional inverse, denoted by log x | Ix , is called the Riemannian Logarithm [8,43]. In previous works, log x | Ix is only defined from I x toĨ x . The next result shows that the domain of log x | Ix : I x →Ĩ x can be extended to log x : M →D x while remaining Borel-measurable. Proof sketch. The full proof of the lemma is provided in Section A.2 of the Appendix. Below, we illustrate the idea of the proof using the example when M = S 2 as in Figure 1.
Let x ∈ S 2 be the "northpole" (the blue point). The tangent cut locusC x is the dashed circle in the left panel of Figure 1. The exponential map exp x is one-to-one onD x except on the dashed circle, which all gets mapped to −x, the "southpole" (the orange point). A consequence of the measurable selection theorem 6 is that log x can be extended to be a Borel-measurable right inverse of exp x by selecting z point onC x such that log x (−x) = z.

Random variable transforms
In the previous subsection, we showed that log x : M → T x M is Borel-measurable. Now, recall that T x M is equipped with the inner product ·, · x , i.e., the Riemannian metric. Below, for each x ∈ M choose an orthonormal basis on T x M with respect to ·, · . Then T x M is isomorphic as an inner product space to R d with the usual dot product.
Our first result of this subsection is a "change-of-variables formula" for computing the densities of M -valued random variables after the log x transform. Recall that λ M is the Riemann-Lebesgue measure on M and λ is the ordinary Lebesgue measure on R d = T x M . (i) Let X be a random variable on M with density f X and let Z := log x (X). Then Z is a random variable Proof sketch. The full proof of the Proposition is in Appendix Section A.4. The idea is the same as in the proof of Proposition 4.2, except that the probability density f Z is replaced by an appropriate conditional probability density.

Finishing up the Proof of Theorem 3.2
Fix x ∈ M such that x is a Lebesgue point of f X and m Y |X · f X . Note that by Theorem 3.7, almost all x ∈ M has this property. Next, let Z = log x (X) and f Z be as in Proposition 4.2-(i). Then . Define Z i := log x (X i ), which are i.i.d copies of the random variable Z := log x (X), and letD n : where equations marked by (a) and (d) follow from Equation (5), (b) from Lemma 4.1, and (c) from the fact that the inner product space T x M with ·, · x is isomorphic to R d with the usual dot product. By Theorem 3.8, we have m(0 D n , K H R d ) → m Y |Z (0) in probability. In other words, for all > 0, converges in probability, proving Theorem 3.2 part 1. As noted in Devroye et al. [19, §2], part 2 of Theorem 3.2 is an immediate consequence of part 1.

Application to the d-Sphere
The d-dimensional round sphere is S d := {x ∈ R d+1 : x 2 1 + · · · + x 2 d+1 = 1}. Here, a round sphere assumes that S d has the arc-length metric: 1. The parameter space Θ = ∞ h=0 R (d+1)×h is the disjoint union of all (d + 1) × h matrices. Element of Θ are matrices θ = W ∈ R (d+1)×h where the number of columns h ∈ {0, 1, 2, . . . } varies. By convention, if h = 0, the partition P θ = P W is the trivial partition {S d }. If h > 0, P W is the partition induced by x → sgn(W x). 2. The probability P is constructed by the procedure where we first sample h ∼ p H (h), then sample the entries of W ∈ R d×h i.i.d according to Gaussian(0, 1).  When q = −d, we have K ha S d = K H S d where the right hand side is the manifold-Hilbert kernel. Proof of Theorem 5.2. Before proceeding, we have the following useful lemma: Lemma 5.3. Let rp = (Θ, P, α) be a WRP. Let H be a random variable. Let θ ∼ P. Suppose that for all x, z ∈ M , the random variables α(θ) and I{x ∈ P θ [z]} are conditionally independent given H. Then we have The lemma follows immediately from the Definition of K rp M (x, z) in Equation 3 and the conditional independence assumption. Now, we proceed with the proof of Theorem 5.2.
Let φ := ∠(x, z)/π. Let H ∼ p H and θ ∼ P be the random variables in Definition 5.1. Note that by construction, the following condition is satisfied: for all x, z ∈ M , the random variables α(θ) and I{x ∈ P θ [z]} are conditionally independent given H. In fact, α(θ) = π q p H (h) −1 (−1) h q h is constant given H = h. Hence, applying Lemma 5.3, we have is the trivial partition. In this case, we have Pr{x ∈ P θ [z]|H = h} = 1 = (1 − φ) 0 . When h > 0, we recall a result of Pinelis [33]: Let w ∈ R d+1 be a random vector whose entries are sampled i.i.d according to Let W = [w 1 , . . . , w h ] be as in Definition 5.1 where w j denotes the j-th column of W . Then by construction, w j is distributed identically as w in Lemma 5.4. Furthermore, w j and w j are independent for j, j ∈ [h] where j = j . Thus, the claim follows from where equality (a) follows from Definition 5.1, (b) from W ∈ R (d+1)×h having i.i.d standard Gaussian entries given H = h, and (c) from Lemma 5.4. Putting it all together, we have For the last step, we used the fact that for all q ∈ R the binomial series (1 + t) q = ∞ h=0 q h t h converges absolutely for |t| < 1 (when φ ∈ (0, 1]) and diverges to +∞ for t = −1 (when φ = 0).  4 for definition) has the interpolating-consistent property.
Proof. As observed in Devroye et al. [19,Section 7], for an arbitrary kernel K, the L 1 -consistency of m(• D n , K) for regression implies the consistency for classification of sgn( u(• D n , K)). Furthermore, m(• D n , K) is interpolating for regression implies that sgn( u(• D n , K)) is interpolating for classification. While the argument there is presented in the R d case, the argument holds in the more general manifold case mutatis mutandis.
Thus, by Theorem 3.2, we have sgn( u(• D n , K H S d )) is consistent for classification, i.e., Equation (1) holds. It is also interpolating since m(• D n , K) is interpolating. By Proposition 5.2, we have K ha is an ensemble method having the interpolating-consistent property.

Discussion
We have shown that using the manifold-Hilbert kernel in kernel smoothing regression, also known as Nadaraya-Watson regression, results in a consistent estimator that interpolates the training data on a Riemannian manifold M . Furthermore, when M = S d is the sphere, we showed that the manifold-Hilbert kernel is a weighted random partition kernel, where the random partitions are induced by random hyperplane arrangements. This demonstrates an ensemble method that has the interpolating-consistent property. A limitation of this work is that the random hyperplane arrangement partition is data-independent. Thus, the resulting ensemble method considered in this work are easier to analyze than popular ensemble methods used in practice. Nevertheless, we believe our work offers one theoretical basis towards understanding generalization in the interpolation regime of ensembles of histogram classifiers over data-dependent partitions, e.g., decision trees à la CART [15].

A.1 Basics of Riemannian Manifolds
In this section, we review the main concepts from Riemannian manifold theory essential to this work. Our main references are Sakai [34] and Do Carmo [20]. Throughout, d ∈ N denotes the dimension. We use the word smooth to mean infinitely differentiable. Manifolds. A smooth manifold M of dimension d is a Hausdorff, second countable topological space together with an atlas: a set Atlas := {(U α , ϕ α )} α∈A where 1). {U α } α∈A is an open cover of M , 2). for each α ∈ A, ϕ α : U α → ϕ α (U α ) ⊆ R d is a homeomorphism onto its image, and 3).
Although the above definition of a tangent vector is abstract, it can be concretely interpreted in terms of derivative along a curve. Let a < t 0 < b be real numbers. A curve through x is a smooth map γ : A Riemannian metric on M is a choice of an inner product ·, · x (and thus, a norm · x ) on T x M for each x ∈ M such that the function M → R given by x → V(x), U(x) x is smooth for all V, U ∈ Vf(M ). As shorthands, when x is clear from context, we drop the subscripts and simply write ·, · and · instead. Choosing an orthonormal basis for T x M with respect to ·, · x for each x, we can identify T x M with R d with the ordinary dot inner product. Let x ∈ M and (U, ϕ) be a chart such that x ∈ U . Define g ij (x) = ∂ i | x , ∂ j | x x . Denote by G(x) the d × d positive definite matrix [g ij (x)] ij . Below, we will refer to the function G : U → R d×d as the coordinate representation of the Riemannian metric. Define g ij (x) := [G(x) −1 ] ij . The Christoffel symbols with respect to (U, ϕ) are defined by Γ k ij := 1 Note that g k , g k , G, Γ k ij , and ∂ i | x g j are all functions with domain U .
Geodesics. Fix a chart (U, ϕ). Consider a smooth curve γ : [a, b] → U . Let ζ i (t) := [ϕ(γ(t))] i be the i-th component functions. The curve γ is a geodesic if ζ is a solution to the following system of second order ordinary differential equations (ODEs): Geodesics are minimizers of the so-called energy functional E(γ) = 1 2 b a γ(t) 2 γ(t) dt. The above system of ODEs are the analog of the "first derivative test" for local minimizers of E. Thus, geodesics are defined independently of the choice of the chart.
Exponential map. For x ∈ M and v ∈ T x M , there exists > 0 and a unique geodesic curve This follows from the existence and uniqueness of the solution to an ODE given initial conditions where the ODE is as discussed above. Note that although geodesics are previously defined in U where (U, ϕ) is a chart, they can be extended outside of U using additional charts.
Let While the following lemma is elementary, we provide a proof since we could not find one in the literature.
Since U x M is compact, we may assume that u * := lim i u i exists after passing to a subsequence if necessary. Furthermore, t i u i x = t i implies that t * := lim i t i exists as well (i.e., t * < ∞). Hence, v * = t * u * .
Consider the case that τ x (u * ) = ∞. Then 0 ≤ t * < τ x (u * ) implies that v * = t * u * ∈Ĩ x . For the other case that t(u) < ∞, we first note that t i u i ∈Ĩ x implies that t i < τ x (u i ). Taking the limit of both sides, we have t * = lim i t i ≤ lim i τ x (u i ) = τ x (u * ). Note that the last limit can be exchanged since τ x is continuous (Lemma A.1 part 6). Thus, either t * < τ For the "furthermore" part, note that where the last equality is Lemma A.1 part 2.

A2
As inner product spaces, T x M and R d are isomorphic (see Section A.1-Riemannian metric). Since, T x M and R d are homeomorphic as topological spaces, R d being locally compact implies T x M is locally compact as well. Thus, we can writeŨ = i∈NK i as a countable union of compact setsK i ⊆ T x M . Furthermore, D x ∩Ũ = i∈ND x ∩K i and so exp x (D x ∩Ũ ) = i∈N exp x (D x ∩K i ).
Since exp x is continuous, exp x (D x ∩K i ) is a compact subset of M , and hence closed and bounded by the Hopf-Rinow theorem ([20, Ch. 8, Theorem 2.8]). Thus, exp x (D x ∩Ũ ) = i∈N exp x (D x ∩K i ) is a countable union of closed sets, which is Borel. This proves the claim that ψ is weakly Borel measurable.
By the Kuratowski-Ryll-Nardzewski measurable selection theorem (see [12,Theorem 6.9.3]), there exists a Borel measurable function M → T x M , which we denote by log x , such that log x (ξ) ∈ ψ(ξ) = exp −1 x (ξ) for all ξ ∈ M , as desired. By construction, log x (ξ) ∈ exp −1 x (ξ) for all ξ ∈ M , and so exp x (log x (ξ)) = ξ is immediate. For the "furthermore" part, let ξ ∈ M be arbitrary and let z := log x (ξ) ∈D x . Let {z i } ⊆Ĩ x be a sequence such that lim i z i = z. By Equation (6), we have dist M (x, exp x (z i )) = z i x . By continuity of dist M and exp x ,

A.3 Proof of Proposition 4.2
Recall from Section A.1-Riemannian metric, given a chart (U, ϕ), one can define the matrix-valued function G : U → R d×d referred to earlier as the coordinate representation of the Riemannian metric. Now, Lemma A.1 part 3 states that I x is an open neighborhood of x. Furthermore,Ĩ x is an open subset of T x M , which is identified with R d using an orthonormal basis (see Section A.1-Riemannian metric). Hence, {(I x , log x | Ix )} x∈M is an atlas of M (see Section A.1-Manifolds).
Definition A.3. The chart (I x , log x | Ix ) is called a normal coordinate system at x. Let G : I x → R d×d be the coordinate representation of the Riemannian metric for this chart. To emphasize the dependency on x, The normal coordinate system has the property that G x (x) = G ⊥ x (x) is the identity matrix. This is the result of Sakai [34, Ch. II §2 Exercise 4]. Proof of Lemma A.4. We first show that ν x is Borel-measurable. Recall that G ⊥ x : M → R d×d is the zero extension of G x : I x → R, which is by definition smooth (see Section A.1-Riemannian metric). In particular, , which is ν x by definition, is Borel-measurable. Next, we prove the "Furthermore" part (i). Note that exp , as desired. For the "Furthermore" part (ii), we first note thatB = (B ∩Ĩ x ) ∪ (B ∩C x ) expressesB as a disjoint union. Thus, B = exp x (B) = exp x (B ∩Ĩ x ) ∪ exp(B ∩C x ) expresses B as a disjoint union as well. Moreover, exp(B ∩C x ) ⊆ exp(C x ) = C x , which has λ M -measure zero (Lemma A.1 part 5).
Recall that λ is the shorthand for the ordinary Lebesgue measure λ R d (see paragraph right after Defini-tion 3.1). Now, we directly compute to obtain the formula Since exp x :Ĩ x → I x is a diffeomorphism (Lemma A.1-part 4) with inverse log x , we have Finally, Pr(X ∈ C x ) = Cx f X dλ M = 0 since C x has λ M -measure zero (Lemma A.1-part 5).
Proof of Proposition 4.2 part (i). Recall that λ is the shorthand for the ordinary Lebesgue measure λ R d (see paragraph right after Definition 3.1). Let E = Ω in Proposition A.5. Then we have By assumption, f X is Borel-measurable. By Lemma A.4, ν x is Borel-measurable. Since exp x is continuous, we have that both f X • exp x and ν x • exp x are Borel-measurable. This proves that f Z is Borel-measurable. Hence, the integrand is Borel-measurable and a density function for Z.
Proof of Proposition 4.2 part (ii). Recall that λ is the shorthand for the ordinary Lebesgue measure λ R d (see paragraph right after Definition 3.1). By Lemma A.1 part 6, we have τ * x := inf u∈UxM τ x (u) > 0. Now, let r ∈ (0, τ * x ). By the definition of r, we have B x (r, M ) ⊆Ĩ x . Hence letting z = log x (ξ) for ξ ∈ B x (r, M ), by Equation (6) we have dist M (x, ξ) = dist M (x, exp x (z)) = z x .
Proof of Lemma A.6. Let ω d := π d/2 /Γ( d 2 + 1) be the volume of the unit ball in R d where Γ is the gamma function. Then λ(B 0 (r, T x M )) = ω d r d . Next, [34, Ch II.5 Exercise 3] states that where S x ∈ R is a constant that depends only on x (it is the scalar curvature of M at x). By simple algebra, the above yields In particular, we have lim Thus, 0 is a Lebesgue point of h, as desired.

A.4 Proof of Proposition 4.3
Recall that λ is the shorthand for the ordinary Lebesgue measure λ R d (see paragraph right after Definition 3.1). Let A ⊆ R andB ⊆ T x M be Borel subsets. Then This proves that P Y |Z (·|·) is a conditional probability for Y given Z.