# gaussian_differential_privacy_on_riemannian_manifolds__2e3db56e.pdf

Gaussian Differential Privacy on Riemannian Manifolds

Yangdi Jiang, Xiaotian Chang, Yi Liu, Lei Ding, Linglong Kong, Bei Jiang* Department of Mathematical and Statistical Sciences University of Alberta {yangdi, xchang4, yliu16, lding1, lkong, bei1}@ualberta.ca

We develop an advanced approach for extending Gaussian Differential Privacy (GDP) to general Riemannian manifolds. The concept of GDP stands out as a prominent privacy definition that strongly warrants extension to manifold settings, due to its central limit properties. By harnessing the power of the renowned Bishop-Gromov theorem in geometric analysis, we propose a Riemannian Gaussian distribution that integrates the Riemannian distance, allowing us to achieve GDP in Riemannian manifolds with bounded Ricci curvature. To the best of our knowledge, this work marks the first instance of extending the GDP framework to accommodate general Riemannian manifolds, encompassing curved spaces, and circumventing the reliance on tangent space summaries. We provide a simple algorithm to evaluate the privacy budget µ on any one-dimensional manifold and introduce a versatile Markov Chain Monte Carlo (MCMC)-based algorithm to calculate µ on any Riemannian manifold with constant curvature. Through simulations on one of the most prevalent manifolds in statistics, the unit sphere Sd, we demonstrate the superior utility of our Riemannian Gaussian mechanism in comparison to the previously proposed Riemannian Laplace mechanism for implementing GDP.

1 Introduction

As technological advancements continue to accelerate, we are faced with the challenge of managing and understanding increasingly complex data. This data often resides in nonlinear manifolds, commonly found in various domains such as medical imaging [Pennec et al., 2019, Dryden, 2005, Dryden et al., 2009], signal processing [Barachant et al., 2010, Zanini et al., 2018], computer vision [Turaga and Srivastava, 2015, Turaga et al., 2008, Cheng and Vemuri, 2013], and geometric deep learning [Belkin et al., 2006, Niyogi, 2013]. These nonlinear manifolds are characterized by their distinct geometric properties, which can be utilized to extract valuable insights from the data.

As data complexity grows, so does the imperative to safeguard data privacy. Differential Privacy (DP) [Dwork et al., 2006b] has gained recognition as a prominent mathematical framework for quantifying privacy protection, and a number of privacy mechanisms [Mc Sherry and Talwar, 2007, Barak et al., 2007, Wasserman and Zhou, 2010, Reimherr and Awan, 2019] have been devised with the aim of achieving DP. Conventional privacy mechanisms, while effective for dealing with linear data, encounter difficulties when handling complex non-linear data. In such cases, a common approach, referred to as the extrinsic approach, is to embed the non-linear data into the ambient Euclidean space, followed by the application of standard DP mechanisms. However, as exemplified in the work of Reimherr et al. [2021], the intrinsic properties of such non-linear data enable us to achieve better data utility while simultaneously preserving data privacy. Therefore, it is imperative that privacy mechanisms adapt to the complexity of non-linear data by employing tools from differential geometry to leverage the geometric structure within the data.

37th Conference on Neural Information Processing Systems (Neur IPS 2023).

Related Work Reimherr et al. [2021] is the first to consider the general manifolds in the DP literature. It extends the Laplace mechanism for ε-DP from Euclidean spaces to Riemannian manifolds. Focusing on the task of privatizing Frechet mean, it demonstrates that better utility can be achieved when utilizing the underlying geometric structure within the data. Continuing its work, Soto et al. [2022] develops a K-norm gradient mechanism for ε-DP on Riemannian manifolds and shows that it outperforms the Laplace mechanism previously mentioned in the task of privatizing Frechet mean. Similarly, Utpala et al. [2023b] extends (ε, δ)-DP and its Gaussian mechanism but only to one specific manifold, the space of symmetric positive definite matrices (SPDM). Equipping the space of SPDM with the log Euclidean metric, it becomes a geometrically flat space [Arsigny et al., 2007]. This allows them to simplify their approach and work with fewer complications, although at the expense of generality. In contrast to the task of releasing manifold-valued private summary, Han et al. [2022], Utpala et al. [2023a] focus on solving empirical risk minimization problems in a (ε, δ)-DP compliant manner by privatizing the gradient which resides on the tangent bundle of Riemannian manifolds. Working on tangent spaces instead of the manifold itself, they could bypass many of the difficulties associated with working under Riemannian manifolds.

Motivations Although the ε-differential privacy (DP) and its Laplace mechanism have been extended to general Riemannian manifolds in Reimherr et al. [2021], there are other variants of DP [Dwork et al., 2006a, Mironov, 2017, Bun and Steinke, 2016, Dong et al., 2022]. Each of them possesses unique advantages over the pure DP definition, and therefore their extensions should be considered as well. As one such variant, GDP offers superior composition and subsampling properties to that of ε-DP. Additionally, it s shown that all hypothesis testing-based privacy definitions converge to the guarantees of GDP in the limit of composition [Dong et al., 2022]. Furthermore, when the dimension of the privatized data approaches infinity, a large class of noise addition private mechanisms is shown to be asymptotically GDP [Dong et al., 2021]. These traits establish GDP as the focal privacy definition among different variants of DP definitions and therefore make it the most suitable option for generalizing to Riemannian manifolds.

Main Contributions With the goal of releasing manifold-valued statistical summary in a GDPcompliant manner, we extend the GDP framework to general Riemannian manifolds, establishing the ability to use Riemannian Gaussian distribution for achieving GDP on Riemannian manifolds. We then develop an analytical form to achieve µ-GDP that covers all the one-dimensional cases. Furthermore, we propose a general MCMC-based algorithm to evaluate the privacy budget µ on Riemannian manifolds with constant curvature. Lastly, we conduct numerical experiments to evaluate the utility of our Riemannian Gaussian mechanism by comparing it to the Riemannian Laplace mechanism. Our results conclusively demonstrate that to achieve GDP, our Gaussian mechanism exhibits superior utility compared to the Laplace mechanism.

2 Notation and Background

In this section, we first cover some basic concepts from Riemannian geometry. The materials covered can be found in standard Riemannian geometry texts such as Lee [2006], Petersen [2006], Pennec et al. [2019], Said [2021]. Then we review some definitions and results on DP and GDP, please refer to Dwork and Roth [2014], Dong et al. [2022, 2021] for more detail.

2.1 Riemannian Geometry

Throughout this paper we let M denote a d-dimensional complete Riemannian manifold unless stated otherwise. A Riemannian metric g is a collection of scalar products , x on each tangent space Tx M at points x of the manifold that varies smoothly from point to point. For each x, each such scalar product is a positive definite bilinear map , x : Tx M Tx M R.

Equipped with a Riemannian metric g, it grants us the ability to define length and distance on M. Consider a curve γ(t) on M, the length of the curve is given by the integral

L(γ) = Z γ(t) γ(t)dt = Z γ(t), γ(t) γ(t) 1

where the γ(t) is the velocity vector and norm γ(t) is uniquely determined by the Riemannian metric g. Note we use to denote the l2 norm throughout this paper.

It follows that the distance between two points x, y M is the infimum of the lengths of all piecewise smooth curves from x to y, d(x, y) = infγ:γ(0)=x,γ(1)=y L(γ). In a similar fashion, we can introduce the notion of measure on M. The Riemannian metric g induces a unique measure ν on the Borel σ-algebra of M such that in any chart U, dν = det gdλ where g = (gij) is the matrix of the Riemannian metric g in U, and λ is the Lebesgue measure in U [Grigoryan, 2009].

Given a point p M and a tangent vector v Tp M, there exists a unique geodesic γ(p,v)(t) starting from p = γ(p,v)(0) with tangent vector v = γ(p,v)(0) defined in a small neighborhood of zero. It can then be extended to R since we assume M is complete. This enables us to define the exponential map expp : Tp M M as expp(v) = γ(p,v)(1). For any p M, there is a neighborhood V of the origin in Tp M and a neighborhood U of p such that expp |V : V U is a diffeomorphism. Such U is called a normal neighborhood of p. Locally, the straight line crossing the origin in Tp M transforms into a geodesic crossing through p on M via this map. On the normal neighborhood U, the inverse of the exponential map can be defined and is denoted by logp. The injectivity radius at a point p M is then defined as the maximal radius R such that Bp(R) M is a normal neighborhood of p, and the injectivity radius of M is given by inj M = inf{inj M(p), p M}.

2.2 Differential Privacy

We start this section with the definition of (ε, δ)-DP. Definition 2.1 ([Dwork et al., 2006a]). A data-releasing mechanism M is said to be (ε, δ)- differentially private with ε 0, 0 δ 1, if for any adjacent datasets, denoted as D D , differing in only one record, we have Pr(M(D) A) eε Pr (M (D ) A)+δ for any measurable set A in the range of M.

Differential privacy can be interpreted from the lens of statistical hypothesis testing [Wasserman and Zhou, 2010, Kairouz et al., 2017]. Given the outcome of a (ε, δ)-DP mechanism and a pair of neighboring datasets D D , consider the hypothesis testing problem with H0: The underlying dataset is D and H1: The underlying dataset is D . The smaller the ε and δ are, the harder this hypothesis testing will be. That is, it will be harder to detect the presence of one individual based on the outcome of the mechanism. More specifically, (ε, δ)-DP tells us the power (that is, 1 - type II error) of any test at significance level α [0, 1] is bounded above by eεα+δ. Using this hypothesis testing interpretation, we can extend (ε, δ)-DP to the notion of Gaussian differential privacy.

Let M(D), M(D ) denote the distributions of the outcome under H0, H1 respectively. Let T (M(D), M (D )) : [0, 1] [0, 1], α 7 T (M(D), M (D )) (α) denote the optimal tradeoff between type I error and type II error. More specifically, T (M(D), M (D )) (α) is the smallest type II error when type I error equals α. Definition 2.2 ([Dong et al., 2022]). A mechanism M is said to satisfy µ-Gaussian Differential Privacy (µ-GDP) if T (M(D), M (D )) Gµ for all neighboring datasets D D with Gµ := T(N(0, 1), N(µ, 1)).

Informally, µ-GDP states that it s harder to distinguish D from D than to distinguish between N(0, 1) and N(µ, 1). Similar to the case of (ε, δ)-differential privacy, a smaller value of µ provides stronger privacy guarantees. As a privacy definition, µ-GDP enjoys several unique advantages over the (ε, δ)-DP definition. Notably, it has a tight composition property that cannot be improved in general. More importantly, a crucial insight in Dong et al. [2022] is that the best way to evaluate the privacy of the composition of many "highly private" mechanisms is through µ-GDP. More specifically, it gives a central limit theorem that states all hypothesis testing-based privacy definitions converge to the guarantees of µ-GDP in the limit of composition. Furthermore, Dong et al. [2021] shows that a large class of noise addition mechanisms is asymptotic µ-GDP when the dimension of the privatized data approaches infinity. These distinct characteristics position µ-GDP as the focal privacy definition among different variants of DP definitions, and we will extend the µ-GDP framework to general Riemannian manifolds in Section 3.

3 Gaussian Differential Privacy on General Riemannian Manifolds

Our primary objective in this study is to disclose a M-valued statistical summary while preserving privacy in a GDP-compliant manner. To this end, we first extend the GDP definition to general

Riemannian manifolds. In Definition 2.2, µ-GDP is defined through the optimal trade-off function T(M(D), M(D )), which is challenging to work with on Riemannian manifolds. We successfully resolve this difficulty by expressing µ-GDP as an infinite collection of (ε, δ)-DP (Corollary 1 in Dong et al. [2022]). Since (ε, δ)-DP is a well-defined notion on any measurable space [Wasserman and Zhou, 2010], it readily extends to any Riemannian manifold equipped with the Borel σ-algebra. Following this methodology, we define µ-GDP on general Riemannian manifolds as follows. Definition 3.1. A M-valued data-releasing mechanism M is said to be µ-GDP if it s (ε, δµ(ε))-DP for all ε 0, where

δµ(ε) := Φ ε

and Φ denotes the cumulative distribution function of the standard normal distribution.

Similarly, we extend the notion of sensitivity to Riemannian manifolds as well. Definition 3.2 (Reimherr et al. [2021]). A summary f is said to have a global sensitivity of < , with respect to d( , ), if we have d (f(D), f (D )) for any two dataset D D .

Following the extension of µ-GDP to Riemannian manifolds, it is crucial to develop a private mechanism that is compliant with µ-GDP. Given that the Gaussian distribution satisfies µ-GDP on Euclidean space [Dong et al., 2022], we hypothesize that an analogous extension of the Gaussian distribution into Riemannian manifolds would yield similar adherence to µ-GDP. (e.g., [Reimherr et al., 2021] for extending Laplace distribution to satisfy ε-DP on Riemannian manifolds). We introduce the Riemannian Gaussian distribution in the following definition. Definition 3.3 (Section 2.5 in Pennec et al. [2019]). Let (M, g) be a Riemannian manifold such that

Z(η, σ) = Z

We define a probability density function w.r.t dν as

pη,σ(y) = 1 Z(η, σ) exp

We call this distribution a Riemannian Gaussian distribution with footprint η and rate σ and denote it by Y NM(η, σ2).

The necessity for Z(η, σ) to be finite is generally of little concern, as it has been shown to be so in any compact manifolds [Chakraborty and Vemuri, 2019] or any Hadamard manifolds1 with lower-bounded sectional curvature [Said, 2021]. The distribution we introduce has been established to maximize entropy given the first two moments [Pennec et al., 2019, Pennec, 2006], and has already found applications in a variety of scenarios [Zhang and Fletcher, 2013, Hauberg, 2018, Said et al., 2017, Cheng and Vemuri, 2013, Zanini et al., 2018, Chakraborty and Vemuri, 2019]. When M = Rd, the Riemannian Gaussian distribution reduces to the multivariate Gaussian distribution with a mean of η and a variance of σ2I.

However, it is critical to highlight that this extension is not the only possible method for integrating the Gaussian distribution into Riemannian manifolds. Other approaches are available, such as the heat kernel diffusion process articulated by Grigoryan [2009], or the exponential-wrapped Gaussian introduced by Chevallier et al. [2022]. For an in-depth exploration of sampling from the Riemannian Gaussian distribution defined above, we refer readers to Section 4.1.

Furthermore, the subsequent theorem underscores the ability of the Riemannian Gaussian distribution, as defined herein, to meet the requirements of Gaussian Differential Privacy. Theorem 3.1. Let M be a Riemannian manifold with lower bounded Ricci curvature and f be a M-valued summary with global sensitivity . The Riemannian Gaussian distribution with footprint f(D) and rate σ satisfies µ-GDP for some µ > 0.

Proof. See Appendix A.1.

1A Hadamard manifold is a Riemannian manifold that is complete and simply connected and has everywhere non-positive sectional curvature.

While Theorem 3.1 confirms the potential of the Riemannian Gaussian distribution to achieve GDP, it leaves the relationship between the privacy budget (µ) and the rate (σ) undefined. The subsequence theorem establishes such a connection: Theorem 3.2 (Riemannian Gaussian Mechanism). Let M be a Riemannian manifold with lower bounded Ricci curvature and f be a M-valued summary with global sensitivity . The Riemannian Gaussian distribution with footprint f(D) and rate σ > 0 is µ-GDP if and only if µ satisfies the following condition, ε 0,

A pη1,σ(y) dν(y) eε Z

A pη2,σ(y) dν(y) δµ(ε) (2)

where A := {y M : pη1,σ(y)/pη2,σ(y) eε} and η1 := f(D), η2 := f(D ).

Proof. See Appendix A.2.

Given the rate σ, Theorem 3.2 provides us a way of computing the privacy budget µ through the inequality (2). When M = Rd, the set A enjoys a tractable form, A = {y Rd : y η2, η1 η2 1 2(2σ2ε/ η1 η2 + η1 η2 )}, and the inequality (2) then reduces to,

sup D D Φ σε η1 η2 + η1 η2

eεΦ σε η1 η2 + η1 η2

where the equality holds if and only if σ = /µ, which reduces to the Gaussian mechanism on Euclidean spaces in Dong et al. [2022]. It s worth pointing out that on Rd, the Pythagorean theorem allows us to reduce the integrals to one-dimensional integrals resulting in a simple solution for any dimension d. Unfortunately, the lack of Pythagorean theorem on non-Euclidean spaces makes it difficult to evaluate the integrals on manifolds of dimensions greater than one. It s known that any smooth, connected one-dimensional manifold is diffeomorphic either to the unit circle S1 or to some interval of R [Milnor and Weaver, 1997]. Therefore, we encompass all one-dimensional cases by presenting the following result on S1. Corollary 3.2.1 (Riemannian Gaussian Mechanism on S1). Let f be a S1-valued summary with global sensitivity . The Riemannian Gaussian distribution NM f(D), σ2 is µ-GDP if and only if µ satisfies the following condition, ε [0, π /(2σ2)], h(σ, ε, ) δµ(ε) where

h(σ, ε, ) = 1 C(σ)

with C(σ) = Φ(π/σ) Φ( π/σ).

Proof. See Appendix A.3.

In summary, Corollary 3.2.1 provides us the analytical form for the integrals in (2). By specifying the rate σ and sensitivity , it becomes feasible to compute the privacy budget µ, which is the smallest µ such that h(σ, ε, ) δµ(ε) for all ε [0, π /(2σ2)]. The systematic procedure is summarized in Algorithm 1. It is important to emphasize that the result in Corollary 3.2.1 together with the existing Euclidean space result covers all one-dimensional cases, and for manifolds with dimension d > 1, we will tackle it in Section 4.

4 Numerical Approach

In Section 3, we demonstrate that our proposed Riemannian Gaussian distribution can be used to achieve GDP in Theorem 3.1 and 3.2. Furthermore, we document our method in Algorithm 1 to compute the privacy budget µ in S1. This and already existing Euclidean results encompass all the one-dimensional Riemannian manifolds. However, for general Riemannian manifolds of dimension

Algorithm 1 Computing µ on S1

Input: Sensitivity (0, π] , rate σ, number of ε used nε Output: µ;

1: Set εmax = π /(2σ2). 2: for each ε in {k, 2k, . . . , nεk} where k = εmax/nε do 3: Compute lε = h(σ, ε, ) as in Corollary 3.2.1 and µε through lε = δµ(ε). 4: end for 5: Compute µ = maxε µε. 6: Return: µ.

d > 1, the integrals in inequality (2) are difficult to compute (see Section 3 for more explanation). One of the central difficulties is the dependence of the normalizing constant Z(η, σ) on the footprint η makes the expression of A intractable. To avoid this dependence, we introduce the concept of homogeneous Riemannian manifolds. Definition 4.1 (Definition 4.6.1 in Berestovskii and Nikonorov [2020]). A Riemannian manifold (M, g) is called a homogeneous Riemannian manifold if a Lie group G acts transitively and isometrically on M.

Homogeneous Riemannian manifolds encompass a broad class of manifolds that are commonly encountered in statistics such as the (hyper)sphere [Bhattacharya and Bhattacharya, 2012, Mardia et al., 2000], the space of SPD Matrices[Pennec et al., 2019, Said et al., 2017, Hajri et al., 2016], the Stiefel manifold [Chakraborty and Vemuri, 2019, Turaga et al., 2008] and the Grassmann manifold [Turaga et al., 2008]. It s a more general class than Riemannian symmetric space, which is a common setting used in geometric statistics [Cornea et al., 2017, Asta, 2014, Said et al., 2018, Said, 2021, Chevallier et al., 2022]. Please refer to Appendix A.4 for more detail.

Informally, a homogeneous Riemannian manifold looks geometrically the same at every point. The transitive property required in the definition implies that any homogeneous Riemannian manifold M only has one orbit. Therefore, we have the following proposition. Proposition 4.1. If M is a homogeneous Riemannian manifolds, then Z(η1, y) = Z(η2, y) for any η1, η2 M.

Therefore, on homogeneous Riemannian manifolds, we can simplify the set A in Theorem 3.2 to A = y M : d(η2, y)2 d(η1, y)2 2σ2ε . To further simplify (2), we will need a much stronger assumption than homogeneous Riemannian manifolds. In particular, we require the condition of constant curvature. Theorem 4.1 (Riemannian Gaussian Mechanism on Manifolds with Constant Curvature). Let M be a Riemannian manifold with constant curvature and f be a M-valued summary with global sensitivity . The Riemannian Gaussian distribution with footpoint f(D) and rate σ > 0 is µ-GDP if and only if µ satisfies the following condition: η1, η2 such that d(η1, η2) = and ε 0 Z

A pη1,σ(y) dν(y) eε Z

A pη2,σ(y) dν(y) δµ(ε) (3)

where A = y M : d(η2, y)2 d(η1, y)2 2σ2ε .

Proof. See Appendix A.5.

Theorem 4.1 tells us that instead of evaluating the integrals of 2 on every neighboring pairs η1 and η2, we only need to check one such pair. Despite the convenience it provides us, evaluating the integrals remains a challenge, even for an elementary space like Sd with d > 1. To circumvent this challenge, we employ the MCMC technique for the integral computations. The main idea is simple: Let Y1, Y2, . . . , Yn be independent and identically distributed random variables from NM(η, σ2), and denotes Zi = 1 1

2σ2 d(η1, Yi)2 + d(η2, Yi)2 ε . By the strong law of large number [Dudley, 2002], we then have 1 n

A pη,σ(y)dν(y) a.s..

n Pn i=1 Zi as an approximation, we avoid the challenge of evaluating the integrals analytically. The detailed algorithm is documented in Algorithm 2. It s known that any space of constant curvature is isomorphic to one of the spaces: Euclidean space, sphere, and hyperbolic space [Vinberg et al., 1993, Woods, 1901]. Therefore, Algorithm 2 offers a straightforward and practical method for assessing the privacy budget µ on spheres and hyperbolic spaces. Furthermore, Algorithm 2 can be extended to a more general class of Riemannian manifold by sampling more than one pair of η, η in step 1. The determination of the number of pairs being sampled and the selection method to ensure sufficient dissimilarity among the sampled pairs is an aspect that requires further investigation.

Algorithm 2 Computing µ on Manifolds with Constant Curvature Input: Sensitivity , rate σ2, Monte Carlo sample size n, number of ε used nε, maximum ε used εmax, number of MCMC samples m Output: privacy budget µ;

1: Sample a random point η on M and another point η on the sphere center at η with radius . 2: for each j in 1, 2, . . . , m do 3: Sample y1j, . . . , ynj NM(η, σ2), y 1j, . . . , y nj NM(η , σ2). 4: Compute dij = d(η , yij)2 d(η, yij)2 and d ij = d(η , y ij)2 d(η, y ij)2 for i in 1, 2, . . . , n. 5: for each ε in {k, 2k, . . . , nεk} where k = εmax/nε do

6: Compute l(j) ε = Pn i=1 1(dij 2σ2ε)/n eε Pn i=1 1(d ij 2σ2ε)/n. 7: end for 8: end for 9: Compute lε = Pm j=1 l(j) ε /m and µε via lε = δµ(ε) for each ε. Compute µ = maxε µε. 10: Return: µ.

4.1 Sampling from Riemannian Gaussian Distribution

The one crucial step in Algorithm 2 involves sampling from the two Riemannian Gaussian distributions NM(η, σ2) and NM(η , σ2). Since their densities (1) are known up to a constant, a Metropolis-Hasting algorithm would be a natural choice. In this section, we describe a general Metropolis-Hasting algorithm for sampling from a Riemannian Gaussian distribution on an arbitrary homogeneous Riemannian manifold [Pennec et al., 2019]. However, there are more efficient sampling algorithms that are tailored to specific manifolds (e.g., [Said et al., 2017, Hauberg, 2018]).

The Metropolis-Hasting algorithm involves sampling a candidate y from a proposal distribution q( |x). The acceptance probability of accepting y as the new state is α(x, y) = min{1, q(y|x)pη,σ(y)/[q(x|y)pη,σ(x)]}. A natural choice for the proposal distribution q( |x) could be an exponential-wrapped Gaussian distribution [Galaz-Garcia et al., 2022, Chevallier et al., 2022]. Informally, it s the distribution resulting from "wrapping" a Gaussian distribution on tangent space back to the manifold using the exponential map. Given the current state x M, we sample a tangent vector v N(0, σ2I) on the tangent space Tx M. If v is less than the injectivity radius, we then accept the newly proposed state y = expx(v) with probability α(x, y). Please refer to Section 2.5 in Pennec et al. [2019] for the detailed algorithm.

4.2 GDP on R and S1

To evaluate the performance of Algorithm 2, we will conduct simulations on Euclidean space R and unit circle S1 as the relation between µ and σ is established in Dong et al. [2022] and Corollary 3.2.1.

We fix sensitivity = 1 and let σ = k/4 with 1 k 16. For each σ, we determine the privacy budget µ using two approaches: (i) using Algorithm 1 with nε set as 1000 for S1 and using µ = 1/σ for R; (ii) using Algorithm 2 with n = 1000, nε = 1000, m = 100, εmax = π/(2σ2) for S1 and εmax = max{10, 5/σ + 1/(2σ2)} for R. Since Algorithm 2 is a randomized algorithm, we generate 20 replicates for approach (ii) for each σ. In Figure 1, the first panel plots the sample means of the µ generated by approach (ii) (in grey with rectangular symbols) with error bars indicating the minimum & the maximum of the µ s and the µ computed by approach (i) (in red with circular symbols). Additionally, as a comparison, we also plot the µ = 1/σ for Euclidean space (in blue with triangular symbols) in the first plot. As we see from the first plot, the GDP results on S1 are almost exactly the same as on R for smaller σ. This is expected as manifolds are locally Euclidean,

Figure 1: First and Second plots: Red lines with circular symbols represent the relation between privacy budget µ and rate σ on the unit circle S1. Blue lines with triangular symbols represent the relation in Euclidean space. Gray lines with rectangular symbols plot the sample mean of the µ, across the 20 repeats, computed at a variety of σ using Algorithm 2. The error bar indicates the minimum and maximum of the µ s. Refer to Section 4.2 for details. Third plot: Blue line with triangular symbols indicates the sample mean, across 100 repeats, of the Riemannian distances d( x, xlaplace), while the red line with circular symbols indicates the sample mean of the Riemannian distances d( x, xgauss). The error bands indicate the sample mean 4SE. Refer to Section 5.2 for details.

and the smaller the σ the closer the results will be. As the σ gets larger, the privacy budget µ gets smaller on S1 compared to on R. This can be explained by the fact that S1 is a compact space while R is not. For the second panel, we plot the exactly same things for Euclidean spaces. As we can observe from both panels, our Algorithm 2 gives a fairly accurate estimation for larger σ. However, as σ gets smaller, Algorithm 2 has a tendency to generate estimates that exhibit a higher degree of overestimation.

5 Simulations

In this section, we evaluate the utility of our Riemannian Gaussian mechanism by focusing on the task of releasing differentially private Fréchet mean. Specifically, we conduct numerical examples on the unit sphere, which is commonly encountered in statistics [Bhattacharya and Bhattacharya, 2012, Mardia et al., 2000]. As a comparison to our Riemannian Gaussian mechanism, we use the Riemannian Laplace mechanism implemented in Reimherr et al. [2021] to achieve GDP. Although the Riemannian Laplace mechanism is developed originally to achieve ε-DP, it s shown in Liu et al. [2022] any mechanism that satisfies ε-DP can achieve µ-GDP with µ = 2Φ 1 (1/(1 + eε)) p

π/2ε. Our results show significant improvements in utility for the privatization of the Fréchet mean when using our proposed Gaussian mechanism, as opposed to the Laplace mechanism, in both examples. In Section 5.1, we cover some basics on differentially private Fréchet mean. In Section 5.2, we discuss the numerical results on the sphere. Simulations are done in R on a Mac Mini computer with an Apple M1 processor with 8 GB of RAM running Mac OS 13. For more details on each simulation, please refer to Appendix A.6. The R code is available in the Git Hub repository: https://github. com/Lei-Ding07/Gaussian-Differential-Privacy-on-Riemannian-Manifolds

5.1 Differentially Private Fréchet Mean

For more details on Fréchet mean under the DP setting, please refer to Reimherr et al. [2021]. Consider a set of data x1, . . . , x N on M. The Euclidean sample mean can be generalized to Riemannian manifolds as the sample Fréchet mean, which is the minimizer of the sum-of-squared distances to the data, x = arg minx M PN i=1 d (x, xi)2. To ensure the existence & uniqueness of the Fréchet mean and to determine its sensitivity, we need the following assumption.

Assumption 1. The data D Br (m0) for some m0 M, where r < r with r = min {inj M, π/(2 κ)} /2 for κ > 0 and r = inj M/2 for κ 0. Note κ denotes an upper bound on the sectional curvatures of M.

Under Assumption 1, we can then compute the sensitivity of the Fréchet mean [Reimherr et al., 2021]. consider two datasets D D . If x and x are the two sample Fréchet means of D and D

respectively, then

d ( x, x ) 2r(2 h(r, κ))

nh(r, κ) , h(r, κ) = 2r κ cot( κ2r) κ > 0 1 κ 0

First, we revisit some background materials on spheres, refer to Bhattacharya and Bhattacharya [2012], Reimherr et al. [2021] for more details. We denote the d-dimensional unit sphere as Sd and identify it as a subspace of Rd+1 as Sd = {p Rd+1 : p 2 = 1}. Similarly, at each p Sd, we identify the tangent space Tp Sd as Tp Sd = {v Rd+1 : v p = 0}. The geodesics are the great circles, γp,v(t) = cos(t)p + sin(t)v with π < t π where γp,v denotes the geodesic starts at p with unit direction vector v. The exponential map expp : Tp Sd Sd is given by expp(0) = p and expp(v)) := cos( v )p + sin(v)v/ v for v = 0. The inverse of the exponential map logp : Sd \ { p} Tp Sd has the expression logp(p) = 0 and logp(q) =

arccos(p q)[q (p q)p] 1 (p q)2 1/2 for q = p, q. It follows that the distance function is given by d(p, q) = arccos(p q) [0, π]. Therefore, Sd has an injectivity radius of π.

We initiate our analysis by generating sample data D = {x1, . . . , xn} from a ball of radius π/8 on S2 and subsequently computing the Fréchet mean x. To disseminate the private Fréchet mean, we implement two methods: (i) We first generate the privatized mean xgauss by drawing from NM( x, σ2) employing the sampling method proposed by Hauberg [2018]. The privacy budget µ is then computed using Algorithm 2. (ii) Next, we convert µ-GDP to the equivalent ε-DP using ε = log[1 Φ( u/2))/Φ( u/2)], and generate the privatized mean xlaplace by sampling from the Riemannian Laplace distribution with footprint x and rate /ε using the sampling method introduced by You and Shung [2022].

Throughout these simulations, we fix the sample size at n = 10 to maintain a constant sensitivity . With held constant, we let the rate σ = k/4 with 1 k 12. The objective here is to discern the difference between the two distances d( x, xgauss) and d( x, xlaplace) across varying privacy budgets µ. The third plot in Figure 1 displays the sample mean of the Riemannian distances d( x, xgauss) (in red with circular symbols) and d( x, xlaplace) (in blue with triangular symbols) across 1000 iterations with the error band indicating the sample mean 4SE. From observing the third plot, we see that our Gaussian mechanism achieves better utility, especially with a smaller privacy budget µ. With larger µ, the gain in utility is less pronounced. One obvious reason is that there are much fewer perturbations with larger µ for both approaches, so the difference is subtle. The other reason is that Algorithm 2 has a tendency to overestimate µ with smaller σ. Effectively, xgauss satisfies µ-GDP with a smaller µ compared to xlaplace.

6 Conclusions and Future Directions

In this paper, we extend the notion of GDP over general Riemannian manifolds. Then we showed that GDP can be achieved when using Riemannian Gaussian distribution as the additive noises. Furthermore, we propose a general MCMC-based algorithm to compute the privacy budget µ on manifolds with constant curvature. Lastly, we show through simulations that our Gaussian mechanism outperforms the Laplace mechanism in achieving µ-GDP on the unit sphere Sd.

There are many future research directions. First of all, the framework established in this paper can be used for extending (ε, δ)-DP to general Riemannian manifolds. There are several points of improvement around Algorithm 2 as well. Although Algorithm 2 provides us a general method of computing the privacy budget µ, it lacks an error bound on its estimation. Furthermore, due to the random nature of Algorithm 2, a variance estimator of the output is desirable and can better inform the end user. Though we demonstrate the utility of our mechanism through simulation in Section 5, it s difficult to obtain a theoretical utility guarantee due to the lack of simple analytical relation between µ and rate σ. Furthermore, although Algorithm 1 requires the manifolds to have constant curvature, it s possible to extend Algorithm 1 and Theorem 4.1 to a slightly more general class of manifolds. Additionally, the Riemannian Gaussian distribution defined in this paper is not the only way of extending Gaussian distribution to Riemannian manifolds as mentioned in Section 3. Potentially, the two other approaches, the wrapped distribution approach, and the heat kernel approach can also be

used to achieve GDP on Riemannian manifolds as well. In particular, there are many rich results around heat kernel on Riemannian manifolds (see Grigoryan [2009] for example). Incorporating the heat kernel in a privacy mechanism presents ample potential for novel and noteworthy discoveries.

Acknowledgements

We would like to express our greatest appreciation to Professor Xiaowei Wang of Rutgers University and Professor Xi Chen from the University of Alberta for their invaluable guidance, support, discussion, and expertise throughout the course of this research. This work was supported by the Canada CIFAR AI Chairs program, the Alberta Machine Intelligence Institute, the Natural Sciences and Engineering Council of Canada (NSERC), the Canada Research Chair program from NSERC, and the Canadian Statistical Sciences Institute. We also thank Qirui Hu from Tsinghua University and all the constructive suggestions and comments from the reviewers.

V. Arsigny, P. Fillard, X. Pennec, and N. Ayache. Geometric means in a novel vector space structure on symmetric positive-definite matrices. SIAM Journal on Matrix Analysis and Applications, 29 (1):328 347, 2007. doi: 10.1137/050637996. URL https://doi.org/10.1137/050637996.

D. M. Asta. Kernel density estimation on symmetric spaces. In International Conference on Geometric Science of Information, 2014.

B. Balle and Y.-X. Wang. Improving the Gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 394 403. PMLR, 10 15 Jul 2018. URL https://proceedings.mlr.press/ v80/balle18a.html.

B. Balle, G. Barthe, and M. Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS 18, page 6280 6290, Red Hook, NY, USA, 2018. Curran Associates Inc.

A. Barachant, S. Bonnet, M. Congedo, and C. Jutten. Riemannian geometry applied to bci classification. Latent Variable Analysis and Signal Separation, 09 2010. doi: 10.1007/978-3-642-15995-4_ 78.

B. Barak, K. Chaudhuri, C. Dwork, S. Kale, F. Mc Sherry, and K. Talwar. Privacy, accuracy, and consistency too: A holistic solution to contingency table release. In Proceedings of the Twenty Sixth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 07, page 273 282, New York, NY, USA, 2007. Association for Computing Machinery. ISBN 9781595936851. doi: 10.1145/1265530.1265569. URL https://doi.org/10.1145/1265530. 1265569.

M. Belkin, P. Niyogi, and V. Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. Journal of Machine Learning Research, 7(85): 2399 2434, 2006. URL http://jmlr.org/papers/v7/belkin06a.html.

V. Berestovskii and Y. Nikonorov. Riemannian manifolds and homogeneous geodesics. Springer, 2020.

A. Bhattacharya and R. Bhattacharya. Nonparametric Inference on Manifolds: With Applications to Shape Spaces. IMS monograph. Cambridge University Press, 2012. ISBN 9781107019584.

M. Bun and T. Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. 14th Theory of Cryptography Conference, 2016. URL https://arxiv.org/abs/1605. 02065.

R. Chakraborty and B. C. Vemuri. Statistics on the Stiefel manifold: Theory and applications. The Annals of Statistics, 47(1):415 438, 2019. doi: 10.1214/18-AOS1692. URL https: //doi.org/10.1214/18-AOS1692.

G. Cheng and B. C. Vemuri. A novel dynamic system in the space of spd matrices with applications to appearance tracking. SIAM J. Img. Sci., 6(1):592 615, jan 2013. doi: 10.1137/110853376. URL https://doi.org/10.1137/110853376.

E. Chevallier, D. Li, Y. Lu, and D. Dunson. Exponential-wrapped distributions on symmetric spaces. SIAM Journal on Mathematics of Data Science, 4(4):1347 1368, 2022.

E. Cornea, H. Zhu, P. Kim, and J. G. Ibrahim. Regression models on riemannian symmetric spaces. Journal of the Royal Statistical Society. Series B (Statistical Methodology), 79(2):463 482, 2017. ISSN 13697412, 14679868. URL http://www.jstor.org/stable/44682521.

J. Dong, W. Su, and L. Zhang. A central limit theorem for differentially private query answering. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 14759 14770. Curran Associates, Inc., 2021. URL https://proceedings.neurips.cc/paper_files/paper/2021/file/ 7c2c48a32443ad8f805e48520f3b26a4-Paper.pdf.

J. Dong, A. Roth, and W. J. Su. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3 37, 2022.

I. L. Dryden. Statistical analysis on high-dimensional spheres and shape spaces. The Annals of Statistics, 33(4):1643 1665, 2005. ISSN 00905364. URL http://www.jstor.org/stable/ 3448620.

I. L. Dryden, A. Koloydenko, and D. Zhou. Non-euclidean statistics for covariance matrices, with applications to diffusion tensor imaging. The Annals of Applied Statistics, 3(3):1102 1123, 2009. ISSN 19326157, 19417330. URL http://www.jstor.org/stable/30242879.

R. M. Dudley. Real Analysis and Probability. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2nd edition, 2002. doi: 10.1017/CBO9780511755347.

C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9:211 407, aug 2014. ISSN 1551-305X. doi: 10.1561/0400000042. URL https: //doi.org/10.1561/0400000042.

C. Dwork, K. Kenthapadi, F. Mc Sherry, I. Mironov, and M. Naor. Our data, ourselves: Privacy via distributed noise generation. In Proceedings of the 24th Annual International Conference on The Theory and Applications of Cryptographic Techniques, EUROCRYPT 06, page 486 503, Berlin, Heidelberg, 2006a. Springer-Verlag. ISBN 3540345469. doi: 10.1007/11761679_29. URL https://doi.org/10.1007/11761679_29.

C. Dwork, F. Mc Sherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In S. Halevi and T. Rabin, editors, Theory of Cryptography, pages 265 284, Berlin, Heidelberg, 2006b. Springer Berlin Heidelberg.

F. Galaz-Garcia, M. Papamichalis, K. Turnbull, S. Lunagomez, and E. Airoldi. Wrapped distributions on homogeneous riemannian manifolds. ar Xiv preprint ar Xiv:2204.09790, 2022.

A. Grigoryan. Heat kernel and analysis on manifolds. American Mathematical Soc., 2009.

H. Hajri, I. Ilea, S. Said, L. Bombrun, and Y. Berthoumieu. Riemannian laplace distribution on the space of symmetric positive definite matrices. Entropy, 18(3), 2016. ISSN 1099-4300. doi: 10.3390/e18030098. URL https://www.mdpi.com/1099-4300/18/3/98.

A. Han, B. Mishra, P. Jawanpuria, and J. Gao. Differentially private riemannian optimization. ar Xiv preprint ar Xiv:2205.09494, 2022.

S. Hauberg. Directional statistics with the spherical normal distribution. In 2018 21st International Conference on Information Fusion (FUSION), pages 704 711, 2018. doi: 10.23919/ICIF.2018. 8455242.

S. Helgason. Differential geometry and symmetric spaces. New York and London: Academic Press, 1962.

P. Kairouz, S. Oh, and P. Viswanath. The composition theorem for differential privacy. IEEE Transactions on Information Theory, 63(6):4037 4049, 2017. doi: 10.1109/TIT.2017.2685505.

J. M. Lee. Riemannian manifolds: an introduction to curvature. Springer Science & Business Media, 2006.

Y. Liu, K. Sun, B. Jiang, and L. Kong. Identification, amplification and measurement: A bridge to gaussian differential privacy. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https://openreview.net/forum?id= Up NCp Gv D96A.

K. V. Mardia, P. E. Jupp, and K. Mardia. Directional statistics. Wiley, 2000.

F. Mc Sherry and K. Talwar. Mechanism design via differential privacy. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 94 103, 11 2007. doi: 10.1109/FOCS.2007.66.

J. Milnor and D. W. Weaver. Topology from the differentiable viewpoint. Princeton university press, 1997.

I. Mironov. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pages 263 275. IEEE, 2017.

P. Niyogi. Manifold regularization and semi-supervised learning: Some theoretical analyses. Journal of Machine Learning Research, 14(37):1229 1250, 2013. URL http://jmlr.org/papers/ v14/niyogi13a.html.

X. Pennec. Intrinsic statistics on riemannian manifolds: Basic tools for geometric measurements. Journal of Mathematical Imaging and Vision, 25:127 154, 07 2006. doi: 10.1007/s10851-006-6228-4.

X. Pennec, S. Sommer, and T. Fletcher. Riemannian geometric statistics in medical image analysis. Academic Press, 2019.

P. Petersen. Riemannian geometry. Springer, 3rd edition, 2006.

M. Reimherr and J. Awan. Kng: The k-norm gradient mechanism. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https://proceedings.neurips.cc/paper_files/paper/2019/file/ faefec47428cf9a2f0875ba9c2042a81-Paper.pdf.

M. Reimherr, K. Bharath, and C. Soto. Differential privacy over riemannian manifolds. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 12292 12303. Curran Associates, Inc., 2021. URL https://proceedings.neurips.cc/paper_files/paper/2021/file/ 6600e06fe9350b62c1e343504d4a7b86-Paper.pdf.

S. Said. Statistical models and probabilistic methods on riemannian manifolds, 2021.

S. Said, L. Bombrun, Y. Berthoumieu, and J. H. Manton. Riemannian gaussian distributions on the space of symmetric positive definite matrices. IEEE Transactions on Information Theory, 63(4): 2153 2170, 2017. doi: 10.1109/TIT.2017.2653803.

S. Said, H. Hajri, L. Bombrun, and B. C. Vemuri. Gaussian distributions on riemannian symmetric spaces: Statistical learning with structured covariance matrices. IEEE Transactions on Information Theory, 64(2):752 772, 2018. doi: 10.1109/TIT.2017.2713829.

C. Soto, K. Bharath, M. Reimherr, and A. Slavkovi c. Shape and structure preserving differential privacy. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 24693 24705. Curran Associates, Inc., 2022. URL https://proceedings.neurips.cc/paper_files/paper/2022/ file/9c84feb75eae1ef6389f31b3ef050b6a-Paper-Conference.pdf.

P. Turaga, A. Veeraraghavan, and R. Chellappa. Statistical analysis on stiefel and grassmann manifolds with applications in computer vision. In 2008 IEEE Conference on Computer Vision and Pattern Recognition, pages 1 8, 2008. doi: 10.1109/CVPR.2008.4587733.

P. K. Turaga and A. Srivastava. Riemannian Computing in Computer Vision. Springer Publishing Company, Incorporated, 1st edition, 2015. ISBN 3319229567.

S. Utpala, A. Han, P. Jawanpuria, and B. Mishra. Improved differentially private riemannian optimization: Fast sampling and variance reduction. Transactions on Machine Learning Research, 2023a. ISSN 2835-8856. URL https://openreview.net/forum?id=pagu BNtqi O.

S. Utpala, P. Vepakomma, and N. Miolane. Differentially private fréchet mean on the manifold of symmetric positive definite (SPD) matrices with log-euclidean metric. Transactions on Machine Learning Research, 2023b. ISSN 2835-8856. URL https://openreview.net/forum?id= m Ax8Qq Z14f.

E. B. Vinberg, V. Minachin, D. Alekseevskij, O. Shvartsman, and A. Solodovnikov. Geometry II: spaces of constant curvature. Springer, 1993.

L. Wasserman and S. Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):375 389, 2010. ISSN 01621459. URL http://www.jstor. org/stable/29747034.

F. S. Woods. Space of constant curvature. Annals of Mathematics, 3(1/4):71 112, 1901. ISSN 0003486X. URL http://www.jstor.org/stable/1967636.

K. You and D. Shung. On the spherical laplace distribution, 2022.

P. Zanini, M. Congedo, C. Jutten, S. Said, and Y. Berthoumieu. Transfer learning: A riemannian geometry framework with applications to brain computer interfaces. IEEE Transactions on Biomedical Engineering, 65(5):1107 1116, 2018. doi: 10.1109/TBME.2017.2742541.

M. Zhang and T. Fletcher. Probabilistic principal geodesic analysis. In C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. URL https://proceedings.neurips. cc/paper_files/paper/2013/file/eb6fdc36b281b7d5eabf33396c2683a2-Paper.pdf.

A.1 Theorem 3.1

First, we need to introduce the notion of privacy profile [Balle et al., 2018]:

The privacy profile δM of a mechanism M is a function associating to each privacy parameter α = eε a bound on the α-divergence between the results of running the mechanism on two adjacent datasets, i.e. δM(ε) = supx x Deε (M(x) M (x ) where the α-divergence (α 1) between two probability measures µ, µ is defined as

Dα (µ µ ) = sup E (µ(E) αµ (E)) = Z

+ dµ (z) = X

z Z [µ(z) αµ (z)]+ ,

where E ranges over all measurable subsets of Z, [ ]+ = max{ , 0}. 2 Informally speaking, the privacy profile represents the set of all of the privacy parameters under which a mechanism provides differential privacy. Furthermore, the privacy profile can be computed using Theorem 5 of Balle and Wang [2018]: δM(ε) = sup D D

M > ε i eε Pr h LD ,D M < ε i

M is the privacy loss random variable of the mechanism M on inputs D D defined as LD,D

M = log (dµ/dµ ) (z), where µ = M(D), µ = M (D ), and z µ. It follows that for our Riemannian Gaussian mechanism M, the privacy profile δM can be rewritten as

δM = sup D D

A pη1,σ(y) dν(y) eε Z

A pη2,σ(y) dν(y)

where A := {y M : pη1,σ(y)/pη2,σ(y) eε} and η1 := f(D), η2 := f(D ). This is exactly the left-hand side of (2).

The following theorem establishes a connection between GDP and privacy profile:

Theorem A.1 (Theorem 3.3 of Liu et al. [2022]). Let µ0 := q

limε + ε2 2 log δA(ε). A privacy mechanism A with the privacy profile δA(ε) is µ-GDP if and only if µ0 < and µ is no smaller than µ0.

Theorem A.1 implies that a mechanism with finite µ0 is µ-GDP for some privacy budget µ. Note that Theorem 3.1 only tells us that Riemannian Gaussian distribution can be used to achieve µ-GDP for some µ. Therefore, to prove it, we only need to show that µ0 is finite. We will show µ0 < by demonstrate that log δA(ε) = O(ε2). To do so, we will need the Bishop-Gromov comparison theorem: Theorem A.2 (Bishop-Gromov; Lemma 7.1.4 in Petersen [2006]). Let M be a complete ndimensional Riemannian manifold whose Ricci curvature satisfies the lower bound

for a constant K R. Let M n K be the complete n-dimensional simply connected space of constant sectional curvature K (and hence of constant Ricci curvature (n 1)K ). Denote by B(p, r) the ball of radius r around a point p, defined with respect to the Riemannian distance function. Then, for any p M and p K M n K, the function

ϕ(r) = Vol B(p, r) Vol B (p K, r)

is non-increasing on (0, ). As r goes to zero, the ratio approaches one, so together with the monotonicity this implies that Vol B(p, r) Vol B (p K, r) .

Bishop-Gromov comparison theorem not only gives us the control of volume growth of certain manifolds but also gives a rough classification by sectional curvature. Besides, this is a global property in the sense that p and p K can be arbitrary points on the manifolds.

2It is known that a mechanism M is (ε, δ)-DP if and only if Deε (M(D) M (D )) δ for every D and D such that D D .

A.1.1 Proof of Theorem 3.1

Proof. By A.1, we only need to show that for any η M, when ε , Z

A pη,σ(y)dν(y) = e O(ε2)

where A is given by A = {y M|pη,σ(y)/pη ,σ(y) > eε} Let s consider M\A = {y M : pη,σ(y)/pη ,σ(y) eε}. We have

log pη,σ(y)

2σ2 (d(η, y)2 d(η , y)2) + C

2σ2 (2d(η, y) + ) + C, by triangular inequality,

where C = log(Z(η, σ)) log(Z(η , σ)). Thus we have,

d(η, y) 2σ2(ε C) 2

2 = pη,σ(y) pη ,σ(y) eε

Let r = 2σ2(ε C) 2

2 , note that since Bη(r) M\A, we have A M\Bη(r). Thus, we only need to prove the following: Z

M\Bη(r) pη,σ2(y)dν(y) = e O(ε2)

when ε . One can easily show the following inequality, Z

Bη(2r)\Bη(r) pη,σ(y)dν(y) Z(η, σ) e r2

σ2 (Vol B(η, 2r) Vol B(η, r)) (4)

By Theorem A.2, we have the following three cases:

1. K > 0. Then the standard space M n K is the n-sphere of radius 1/

K. (Vol B(η, 2r) Vol B(η, r)) is obviously less than the volume of the whole space M n K. Thus we have Z

Bη(2r)\Bη(r) pη,σ(y)dν(y) Z(η, σ) e r2

where s(n) = 2π n 2 Γ( n

2 ) is a constant relative to the dimension n. One can easily find that as ε , Bη(2r) will cover the M n K, and the right-hand side of inequality 5 will approach to 0 as e O(ε2).

2. K = 0. Then the standard space M n K is the n dimensional Euclidean space Rn. We have Z

Bη(2r)\Bη(r) pη,σ(y)dν(y) Z(η, σ) e r2

2 + 1). (6)

The same with above, when ε , Bη(2r) will cover the Rn and the right-hand side of 6 will approach to 0 as e O(ε2).

3. K < 0. The standard space Mn(K) is the hyperbolic n-space Hn. The hyperbolic volume Vol B(ηK, r) with any ηk Hn is given by

Vol B(ηK, r) = s(n) Z r

where the hyperbolic function is given by sinh(x) = (ex e x)/2. It s not hard to see that

sinhn(t) (n + 1)ent

Plugging the 8 into 7, we have

Vol B(ηK, r) sn n

K n e K(n 1)r. (9)

Combining 9 and 4, we have Z

Bη(2r)\Bη(r) pη,σ(y)dν(y) c(n) Z(η, σ) e r2

σ2 + K(n 1)2r. (10)

The principle part of the exponent of the right-hand side of 10 is still ε2. Thus, when ε , it approaches to 0 as e O(ε2).

A.2 Theorem 3.2

Proof. Follows directly from Definition 2.2, Theorem 3.1 and Theorem 5 in Balle and Wang [2018].

A.3 Corollary 3.2.1

Proof. In this proof, we will parameterize points on S1 using their polar angles.

On S1, the Riemannian Gaussian distribution with footprint η and rate σ has the following density,

pη,σ(θ) = 1

Zσ e 1 2σ2 (θ η mod π)2, Zσ =

Note that since S1 has constant curvature, we can use Theorem 4.1 instead of Theorem 3.2

WLOG we assume η1 = 2π

2 and thus d(η1, η2) = . Given an arbitrary ε, the set A takes the following form,

A = π + σ2ε

and it follows that we must have

ε [0, π /(2σ2)]. (11)

Thus we have Z

A pη1,σ(y) dν(y) eε Z

A pη2,σ(y) dν(y)

A e 1 2σ2 (η1 θ mod π)2dθ eε Z

A e 1 2σ2 (η2 θ mod π)2dθ

e 1 2σ2 (η1 θ mod π)2dθ eε Z

A e 1 2σ2 (η2 θ mod π)2dθ

e 1 2σ2 (η1 θ)2dθ eε Z

A e 1 2σ2 (η2 θ mod π)2dθ

A e 1 2σ2 (η2 θ mod π)2dθ

A e 1 2σ2 (η2 θ mod π)2dθ .

We have evaluated the first integral, and now let s consider the second integral. For ε 2

2σ2 , we have Z

A e 1 2σ2 (µ2 θ mod π)2dθ

e 1 2σ2 (θ µ2)2dθ + Z 2π σ2ε

µ2+π e 1 2σ2 (θ (2π+µ2))2dθ

Thus for ε 2

2σ2 we have, Z

A pη1,σ(y) dν(y) eε Z

A pη2,σ(y) dν(y)

Similarly, for ε > 2

2σ2 , we have, Z

A e 1 2σ2 (µ2 θ mod π)2dθ

e 1 2σ2 (θ (2π+µ2))2dθ

Thus for ε > 2

2σ2 we have, Z

A pη1,σ(y) dν(y) eε Z

A pη2,σ(y) dν(y)

Put (11), (12) and (13) together with Theorem 4.1, we have proved Corollary 3.2.1.

A.4 Homogeneous Riemannian Manifolds

For more detailed treatment on homogenous Riemannian manifolds and related concepts, refers to Helgason [1962], Berestovskii and Nikonorov [2020], Lee [2006] for details and Chakraborty and Vemuri [2019] for a more concise summary.

A.4.1 Group actions on Manifolds

In this section, we will introduce some basic facts about group action which will be used to introduce homogeneous Riemannian manifolds in later section. The materials covered in this section can be found in any standard Abstract Algebra texts. Definition A.1. A group (G, ) is a non-empty set G together with a binary operation : G G G, (a, b) 7 a b such that the following three axioms are satisfied:

Associativity: a, b, c G, (a b) c = a(b c)

Identity element: e G, a G, a e = e a = a.

Inverse element: a G, a 1 G, a a 1 = a 1 a = e. Definition A.2. Let G be a group and X be an arbitrary set. A left group action is a map α : G X X, that satisfies the following axioms:

α(e, x) = x

α(g, α(h, x)) = α(gh, x)

Note here we use the juxtaposition gh to denote the binary operation in the group. If we shorten α(g, x) by g x, it s equivalent to say that e x = x, and g (h x) = (gh) x

Note each g G induces a map Lg : X X, x 7 g x.

A.4.2 Homogeneous Riemannian manifolds, symmetric spaces and spaces of constant curvature

Let M be a Riemannian manifold and I(M) be the set of all isometries of M, that is, given g I(M), d(g x, g y) = d(x, y), for all x, y M. It is clear that I(M) forms a group, and thus, for a given g I(M) and x M, g x 7 y, for some y M is a group action. We call I(M) the isometry group of M.

Consider o M, and let H = Stab(o) = {h G | h o = o}, that is, H is the Stabilizer of o M. Given g I(M), its linear representation g 7 dxg in the tangent space Tx M is called the isotropy representation and the linear group dx Stab(x) is called the isotropy group at the point x.

We say that G acts transitively on M, iff, given x, y M, there exists a g M such that y = g x.

Definition A.3 ([Helgason, 1962]). Let G = I(M) act transitively on M and H = Stab(o), o M (called the "origin" of M ) be a subgroup of G. Then M is called a homogeneous Riemannian manifold and can be identified with the quotient space G/H under the diffeomorphic mapping g H 7 g o, g G.

By definition, we have d(x, y) = d(g x, g y) for any g G and any x, y M. More importantly, any integrable function f : M R, we have [Helgason, 1962] Z

M f(x)dν(x) = Z

M f(g x)dν(x)

This property leads to Proposition 4.1. Definition A.4 ([Helgason, 1962]). A Riemannian symmetric space is a Riemannian manifold M such that for any x M, there exists sx G = I(M) such that sx x = x and dsx|x = I. Sx is called symmetry at x.

That is, a Riemannian symmetric space is a Riemannian manifold M with the property that the geodesic reflection at any point is an isometry of M. Note that any Riemannian symmetric space is a homogeneous Riemannian manifold, but the converse is not true. Definition A.5 ([Vinberg et al., 1993]). A simply-connected homogeneous Riemannian manifold is said to be a space of constant curvature if its isotropy group (at each point) is the group of all orthogonal transformations with respect to some Euclidean metric.

Once again, a space of constant curvature is a symmetric space but the converse is not true.

A.5 Theorem 4.1

Proof. Let G be the isometry group of M. Let η1, η2 M be arbitrary points such that d(η1, η2) = . By Corollary 4.1, the set A reduces to A = y M : d(η2, y)2 d(η1, y)2 2σ2ε .

What we need to show is the following, for any points η 1, η 2 M such that d(η 1, η 2) = , Z

A pη1,σ(y) dν(y) eε Z

A pη2,σ(y) dν(y) = Z

A pη 1,σ(y) dν(y) eε Z

A pη 2,σ(y) dν(y)

where A = y M : d(η 2, y)2 d(η 1, y)2 2σ2ε . It s sufficient to show Z

A pη1,σ(y) = Z

A pη 1,σ(y) dν(y), Z

A pη2,σ(y) = Z

A pη 2,σ(y) dν(y). (14)

We can separate the proof into three cases: (1) η 1 = η1, η 2 = η2; (2) η 1 = η1, η 2 = η2; (3) η 1 = η1, η 2 = η2.

Case (1): η 1 = η1, η 2 = η2:

It follows that η2 is in the sphere centered at η with radius . (14) then follows from the rotational symmetry of the constant curvature spaces.

Case (2): η 1 = η1, η 2 = η2:

Same as case (1).

Case (3): η 1 = η1, η 2 = η2:

For any η 1 = η1, there exists g G, such that g η1 = η 1. Denote η 2 = g η2, we have g A :={g y : d(η2, y)2 d(η1, y)2 2σ2ε}

={g y : d(η 2, g y)2 d(η 1, g y)2 2σ2ε}

={y : d(η 2, y)2 d(η 1, y)2 2σ2ε}

=A . Let F(y) := pη1,σ(y)1A(y), we have Z

A pη1,σ(y) dν(y)

M F L 1 g (y) dν(y)

M pη1,σ(g 1 y)1g A(y) d(L 1 g ) ν(y); change of variable formular,

M pη1,σ(g 1 y)1g A(y) dν(y); ν is a G-invariant measure,

g A e 1 2σ2 d(g 1 y,η1)2 dν(y)

g A e 1 2σ2 d((gg 1) y,g η1)2 dν(y)

g A e 1 2σ2 d(y,η 1)2 dν(y)

g A pη 1,σ(y)dν(y)

A pη 1,σ(y)dν(y).

A pη2,σ(y)dν(y), the proof is the same. Combine with the result of case (1), we have finished the proof for case (3).

A.6 Simulation Details

For sampling from Riemannian Gaussian distribution NM(θ, σ2) on S1 (section 4.2), we first sample from truncated normal distribution with µ = 0 and σ2, then embed the sample to R and lastly counter-wise rotate the sample with degree θ.

For simulation on S2 (section 5.2), we choose the pair of η and η to be (1, 0, 0) and (cos( ), (1 cos( )2)1/2, 0). Though any pair η, η S2 with d(η, η ) = works, we simply choose this specific pair for convenience. For Fréchet mean computation, we use a gradient descent algorithm described in Reimherr and Awan [2019].

A.6.1 R Codes

For simulations in section 4.2, refer to R files euclid_functions.R & euclid_simulation.R for Euclidean space and sphere_functions.R & s1_simulation.R for unit circle S1. For simulations in section 5.2, refer to R files sphere_functions.R & sphere_simulation.R.