Gaussian Differential Privacy on Riemannian Manifolds
Authors: Yangdi Jiang
Xiaotian Chang
Yi Liu
Lei Ding
Linglong Kong
Bei Jiang
Venue: NeurIPS 2023 poster (2023)
Keywords: Differential Privacy
Gaussian Differential Privacy
Differential Geometry
Riemannian Manifold
Homogeneous Riemannian Manifold
Frechet Mean
TL;DR: Extending Gaussian differential privacy framework to general Riemannian manifolds.

Abstract: 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 $\mu$ on any one-dimensional manifold and introduce a versatile Markov Chain Monte Carlo (MCMC)-based algorithm to calculate $\mu$ on any Riemannian manifold with constant curvature. Through simulations on one of the most prevalent manifolds in statistics, the unit sphere $S^d$, we demonstrate the superior utility of our Riemannian Gaussian mechanism in comparison to the previously proposed Riemannian Laplace mechanism for implementing GDP.

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 fyangdi, xchang4, yliu16, lding1, lkong, bei beil)@ualberta.co
Abstract
We develop 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 manifold settings, due to its central limit properties. By harnessing the power of the renowned Gromoo theorem 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 tangent space summaries. We provide simple algorithm to evaluate the privacy budget y on any one-dimensional manifold and introduce a versatile Markov Chain Monte Carlo (MCMC)-basse 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 comparison to the previously proposed Riemannian Laplace mechanism for implementing GDP.
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., [019 Dryden 2005 Dryden et al., 2009], signal processing [Barachant et al., 2010 Zanini et al. [0188. 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, does the imperative to safeguard data privacy. Differential Privacy (DP) [Dwork et al. (006bb has gained recognition as a prominent mathematical framework for quantifying privacy protection, and number of privacy mechanisms [McSherry 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 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. (202T], the intrinsic properties of such non-linear data enable to achieve better data utility while simultancously preserving data privacy. Therefore. it is imperative that privacy mechanisms adapt 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 (NcurIPS 2023).

---

Related Work Reimherr et al. [222 is the first to consider the general manifolds in the DP litera- ture. It extends the Laplace mechanism for s-DP from Euclidean spaces 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, [Soo et al. [2022) develops K-norm gradient mechanism for e-DP on Riemannian manifolds and shows that it outperforms the Laplace mechanism previously mentioned in the task privatizing Frechet mean. Similarly, Uipala et al. [203b) extends (s, 6 and its Gaussian mechanism but only one specific manifold, the space symmetric positive definite matrices (SPDM). Equipping the space of SPDM with the log Euclidean metric, it becomes geometrically flat space [Arsigny 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-valuee private summary, Haan et al. [2022).
Utpala et al. [2023a] focus on solving empirical risk minimization problems in a (e. d)-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 e-differential privacy (DP) and its Laplace mechanism have been ex- tended to general Riemannian manifolds in Reimheer 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 c-DP. Additionally, it's shown that all hypothesis testing-baase -based privacy definitions converge to the guarantees of GDP in the limit of composition [Dong et al. (022). Furthermore, when the dimension of the privatized data approaches infinity, large class of noise addition private mechanisms is shown to be asymptotically GDP [Dong et al. [202]]. 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 GDP- compliant 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 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 mechanism. Our results conclusively demonstrate that to achieve GDP, our Gaussian mechanism exhibits superior utility compared to the Laplace mechanism.
the Riemannian Laplace
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 202T for more detail.
2.1 Riemannian Geometry
Throughout this paper we let M denote a dddimensional complete Riemannian manifold unless stated otherwise. A Riemannian metric g is collection of scalar products (s))> on each tangent space TzM 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 (5 T.M x T.M + R.
Equipped with a Riemannian metric g. it grants us the ability to define length and distance on M. Consider curve rt) on M, the length of the curve is given by the integral
L(>) 1100 1100)aay) / ((50), di
where the (() is the velocity vector and norm [[]] 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 r, y E M is the infimum of the lengths of all piece- wise smooth curves from x to y, d(x, y) (0))=))))) ( In a similar fashion, we can introduce the notion of measure on M. The Riemannian metric g induces unique measure v on the
L(y).
Borel o-algebra of M such that in any chart U. du = dett gdx where g = (gi) ) the matrix of the Riemannian metric g in U, and À is the Lebesgue measure in U [Grigoryan] 2009].
Given point p E .M and tangent vector E Ty,,, there exists a unique geodesic Kp.e) (t) starting from p at, (0) with tangent vector = =xp.)) (0) defined in a small neighborhood of zero. It can then be extended to IR since we assume M is complete. This enables us to define the exponential map exp, .T.M +M . as exp; (v) T(p.))
(1). For any P E M, there is neighborhood V of the origin in T.MM and neighborhood U of p such that expp Iv : V U is a diffeomorphism. Such U is called a normal neighborhood of p. Locally, the straight line crossing the origin in T..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 E M is then defined as the maximal radius R such that (R) C CM is a normal neighborhood of p. and the injectivity radius of M is given by injm- inf inf(inj p E M).
2.2 Differential Privacy
We start this section with the definition of (e, DDDP.
Definition 2.1 ((woork et al. 2006a)
data-releasing mechanism M is said be (e, 0)- differentially private with E Z 0,0 I 8 < 1, if for any adjacent datasets, denoted as DD = D''
differing in only one record, we have Pr(M((D) A) S Pr Pr (M (D)) E A)+ 5 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. [217]. Given the outcome of a (s, 6DD mechanism and pair of neighbor- ing datasets D ~ D', consider the hypothesis testing problem with Ho: The underlying dataset is D and H1: The underlying dataset is DD". The smaller the and 5 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. (e, 8)-DP tells us the power (that is, 1 type II error) of any test at significance level a E [0. 1] is bounded above by e a + ò. Using this hypothesis testing interpretation, we can extend (s, 5)-DP to the notion of Gaussian differential privacy.
Let M(D), (D') denote the distributions of the outcome under Ho, H2 respectively. Let T (M(D), M (D'))= : [0, 1] + [0, 1). + T (D), M (D")) (a) denote the optimal tradeoff between type error and type II error. More specifically, T (M), (D') (a) is the smallest type II error when type I error equals a.
Definition 2.2 (Dong et al. 2022 D. A mechanism M is said to satisfy μ- y-Gaussian Differential Privacy (H-GDP) T (MM() M (D)) 2 G₁, for all neighboring datasets D ~ D' with G. ((N 1), (14, 1))-
Informally, μ-GDP states that it's harder to distinguish D from D' than to distinguish between NO, 1) and N(4,,) 1). Similar to the case of (c, d)dfifferet privacy, a smaller value of lu provides stronger privacy guarantees. As a privacy definition, μ-GDD enjoys several unique advantages over the (e. 8DPP definition. Notably, it has a tight composition property that cannot be improved in general. More importantly, crucial insight in Dong al. (2022) is that the best way to evaluate the privacy of the composition of many "highly private" mechanisms is through p-GDP, More specifically, gives a central limit theorem that states all hypothesis testing-based privacy definitions converge to the guarantees of G-GDP in the limit of composition. Furthermore, Dong et al.) [2021] shows that a large class of noise addition mechanisms asymptotic μ-- μ-GDP when the dimension of the privatized data approaches infinity. These distinct characteristics position H-GDP as the focal privacy definition
among different variants of DP definitions, and we will extend the μ-GDP framework 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 GDP-compliant manner. To this end, we first extend the GDP definition to general
3

---

Riemannian manifolds. In Definition 2.2 f L-GDPi is defined through the optimal trade-off function (D), (D))), which is challenging work with on Riemannian manifolds. We successfully resolve this difficulty by expressing μ--DDP as an infinite collection of (e, 5)-DP (Corollary 1 in Dong et al. 2022 Since (e, 6)-DP is a well-defined notion on any measurable space [Wasserman] and Zhou 20T0J, it readily extends to any Riemannian manifold equipped with the Borel o-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'ss (e, (c()))D for all & 2 0, where
6y(t)== (- (-) - ef
(-
and & denotes the cumulative distribution function of the standard normal distribution.
Similarly, we extend the notion of sensitivity to Riemannian manifolds well. Definition 3.2 (Reimherr et al. (021 ). A summary f is said to have global sensitivity of A < co, with respect to d(.,)) "), if we have d (D). (D')) S A for any two dataset D D
Following the extension of μ-GDP to Riemannian manifolds, it is crucial to develop private mechanism that is compliant with 4-GDP. Given that the Gaussian distribution satisfies H--DP on Euclidean space [Dong et al.) 2022]. we hypothesize that an analogous extension of the Gaussian distribution into Riemannian manifolds would yield similar adherence p-GDP. (e.g., [Reimherr al. 2021] for extending Laplace distribution to satisfy s-DP Riemannian manifolds). We introduce the Riemannian Gaussian distribution in the following definition.
Definition 3.3 (Section 2.5 in Pennec et al. (2119). Let (M,g) be Riemannian manifold such that
Z(7 = /
(())1)² =|m exp 20²
dd(l)) < co.
We define a probability density function wir.t du as
d (y,, n)²
Py.ar (v) O(1,0)
exp
(I)
20²
We call this distribution a Riemannian Gaussian distribution with footprint and rate and denote by Y (M(n),
The necessity for [(n, σ) 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 manifolds[]win lower- bounded sectional curvature 2021]. The distribution we introduce has been established maximize entropy given the first two moments [Pennee et al. 2019 Pennec 2006 and has already found applications in a variety of scenarios [Zhang and Fletcher [2033 Hall]HHubbegg lauberg 2018 Said et al.
2017 Cheng and Vemuri 2013 Zanini al. 2018 Chakraborty and Vemuri 2019). When M = R.
the Riemannian Gaussian distribution reduces to the multivariate Gaussian distribution with a mean
of r) and a variance of I²I.
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-wrapee
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 M-valued summary with global sensitivity A. The Riemannian Gaussian distribution with footprint (D) and rate a satisfies μ-GDP for some μ > O.
Proof. See Appendix A.I
A 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 (1) and the rate (o) undefined. The subsequence theorem establishes such a connection:
Theorem 3.2 (Riemannian Gaussian Mechanism). Lei M be a Riemannian manifold with lower bounded Ricci curvature and f be M-valued summary with global sensitivity A. The Riemannian Gaussian distribution with footprint f(D) and rate a > 0 is μ-GDP if and only if μ satisfies the following condition, VE 0,
sup / Pm. (v) du(y) Ee Prao(l)) duly) S 6,(e)
(2)
D=D
where A = ty M: Por (y) (1) 2 ) and 111 S(D), == I(D').
Proof. See Appendix A.2
Given the rate 0, Theorem provides us way of computing the privacy budget μ through the in-
equality 2 When M = F" the set A enjoys a tractable form, A {y E R (v 72, 772 2
(20 2g
/ 7 722l + |!!
1/21))], and the inequality (2) then reduces to,
oE
m/ 122l
(-1m DE
111 12ll S (c((E)
sup 4 D=
+
e
(T 72
m2
20
20
where the equality holds if and only if a = A/μ. 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 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 oie-dimensional manifold is diffeomorphic either to the unit circle S' or to some interval of R [Milnor and Weaver 1997). Therefore, we encompass all needdmennsioall cases by presenting the following result on
Corollary 3.2.1 (Riemannian Gaussian Mechanism on S²). Let f be a St-valued summary with global sensitivity A. The Riemannian Gaussian distribution NM (f(D), o²) is μ-GDP if and only if I satisfies the following condition, Ve E = (2o") "1 h(a, e, A) S 6,(() where
1
oE
A
h(o, 2)
C(a)
A
20
A
20
30 A
π
c
M0
A
C(a)
2g
0
20
0
85
2
A2
0
e
A2
cs
2n
with C(a)= = (TT/O) - 4 ( T/O).
Proof. See Appendix A.3
In summary, Corollary 3.2. provides us the analytical form for the integrals in 2 By specifyying the rate a and sensitivity A, becomes feasible to compute the privacy budget μ4, which is the smallest such that h(a, e, A) I (E) for all [0, A (2o²)). The systematic procedure is summarized in Algorithm [ It important to emphasize that the result in Corollary [ together with the existing
Euclidean space result covers all one-dimensional cases, and for manifolds with dimension d > we will tackle it in Section 4]
4 Numerical Approach
In Section we demonstrate that our proposed Riemannian Gaussian distribution can used to achieve GDP in Theorem 3.1 and 3.2 Furthermore, we document our method in Algorithm ] to compute the privacy budget y in St This and already existing Fuclidean results encompass all the one-dimensional Riemannian manifolds. However, for general Riemannian manifolds of dimension
5

---

Algorithm 1 Computing l 5²
Input: Sensitivity A E (0, π] rate a, number of & used Ye Output: Jr;
1: Set Emax = =
2: for each in {ki 2k...., ] where Emax /e do
3: Compute 1g h(o,,, E, A) as in Corollary 3.2. and through le tx(s).
4: end for
5: Compute maxe Me.
6: Return: J..
d 1, the integrals in inequality (2) are difficult to compute (see Section 3 for more explanation).
One of the central difficulties the dependence of the normalizing constant Z (1) a) on the footprint ?) makes the expression of A intractable. To avoid this dependence, we introduce the concept of homogencous Riemannian manifolds.
Definition 4.1 (Definition 4.6.1 in Berrestovkii 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.
Homogencous 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. [011 Hajri et al.] 2016), the Stiefel manifold [Chakraborty and Vemuri 2019 Turaga et al. 2008 and the Grassmann manifold
[Turaga et al. 20088. It's 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, 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 homogeneous Riemannian manifolds, then Z(m, y) Z 3) for any any 7h, 1/2 E M.
Therefore, on homogeneous Riemannian manifolds, to A = {y E M: d( y)² d(n,, y)² 2 2022). To further simplify ( we will need a much stronger assumption than homogeneous Riemannian manifolds. In particular, require the condition of constant curvature.
simplify the set A in Theorem 3.2
Theorem 4.1 (Riemannian Gaussian Mechanism on Manifolds with Constant Curvature). Let M be Riemannian manifold with constant curvature and f be M-valued summary with global sensitivity A. The Riemannian Gaussian distribution with footpoint f(D) and rate a > 0 is GDGD if and only if satisfies the following condition: 3m,, 7/2 such that d(m), 72) A and Ve 2 0
/ Pm)(()) du(y) - -e PPrao(l) duly) S 5n(e)
(3)
where A = { M: d(12. 2 d(mi,v) 20²E}.
Proof. See Appendix A.5
Theorem tells us that instead of evaluating the integrals of on every neighboring pairs 7 and 722 we only need check one such pair. Despite the convenience it provides us, evaluating the integrals remains a challenge, even for an elementary space like S with d > 1. To circumvent this challenge, we employ the MCMC technique for the integral computations. The main idea simple: Let Y1, Y2 Y, be independent and identically distributed random variables from N NM g²), and
denotes Z; 1 1 (-d(m, Y2) + d(12, Y2) 2 2e) }. By the strong law of large number Dudleyy 2002], we then have
2
Zi + / Pr. Proo (W) a.s.
n

---

By using 1 Ei=1 Zi as an approximation, we avoid the challenge of evaluating the integrals analyti- cally. The detailed algorithm is documented in Algorithm 2 It's known that any space of constant curvature is isomorphic to one of the spaces: Fuclidean space, sphere, and hyperbolic space (Vinberg) at.a.. 1993 Woods ].01]. Therefore, Algorithm ooffrss straightfowwrd and practical method for assessing the privacy budget μ on spheres and hyperbolic spaces. Furthermore, Algorithm can be extended to a more general class of Riemannian manifold by sampling more than one pair of 17, '/' 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 μ Manifolds with Constant Curvature
Input: Sensitivity A, rate o², Monte Carlo sample size n, number of used ntg, maximum & used max number of MCMC samples m
Output: privacy budget μc;
1: Sample a random point 7 on M and another point r/ on the sphere center ry with radius A.
2: for each j in 1, 1.2..... m do
3: Sample Vif. ................................ Mnj (1) σ²), By....................... payy ~ NM 02).
4: Compute d = d(n', y:1)²² d(n, vij) and d'j = d(r/: , 1k d(n, 111)² for i in ..2,...,?
5: for each in {k: .k...., ngk) ngkk where l = Emax/ng / do
6: Compute ( Ei= I(d; 2 20²8)/ e Ei= 1(d 2 20²2)/n.
7: end for
8: end for
9: Compute 1e = Eド 1000 1 m and Me via = 6x(=) for each e. Compute μ = max, Mec
10: Return: J.
4.1 Sampling from Riemannian Gaussian Distribution
The one crucial step in Algorithm 2 involves sampling from the two Riemannian Gaussian dis- tributions (n, and NM/ o²). Since their densities (1 are known up to a constant, a Metropolis-Hasting algorithm would be natural choice. In this section, describe a general Metropolis-Hastio 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-Hastinn bution q(-1z)). The acceptance probability of accepting y as the new state is a(x, y) = min 43y (x] ,, (w) ht))[(((///))/_/___. (x)]). A natural choice for the proposal distribution o(-1xr) could be an apponential-wrappee Informally, it's ss the distribution resulting from "wrapping" a Gaussian distribution tangent space back to the manifold using the exponential map. Given the current state x E M, we sample a tangent vector e NO, o²I) on the tangent space T.M. If ||v|] is less than the injectivity radius, we then accept the newly proposed state = exp,,v)) (v) with probability a(r, y). Please refer to Section 2.5 in Pennec et al. 2019] for the detailed algorithm.
algorithm involves sampling candidate y from proposal distri-
Gaussian distribution [Galaz-Garee Garcia et al. 2022 Chevallier et al. (022).
4.2 GDP on IR and S1
To evaluate the performance of Algorithm 2 we will conduct simulations on Euclidean space R and unit circle St as the relation between μ and a is established in Dong et al. 2022 and Corollary 3.2.1
We fix sensitivity A 1 and let o k/4 with 1 < S 16. For each a. we determine the privacy budget μ using two approaches: (i) using Algorithm I with ng set as 1000 for 5 and using f = 1/o for I; (ii) using Algorithm 2 with n 1000, n. 1000, m 100, Emax = T/ (/(2²²) for S and mmax = max 5/0 + 2 } for R. Since Algorithm 2 is a randomized algorithm, we generate 20 replicates for approach (ii) for each a. In Figure [ 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 jıss and the μ computed by approach (i) (in red with circular symbols). Additionally, as comparison, we also plot the μ 1/a for Euclidean space (in blue with triangular symbols) in the first plot. As we see from the first plot, the GDP results on S are almost exactly the same on ER for smaller o., This is expected as manifolds are locally Euclidean,
7

---

GDP s!
GDP on R
GDP on Sphere
Riemannian distance
True Euciidaan MCMC
Euciidaan
0.6
Laplace
2
1-
0.2
1
Figure 1: First and Second plots: Red lines with circular symbols represent the relation between privacy budget μ and rate o on the unit circle S². Blue lines with triangular symbols represent the relation in Euclidean space. Gray lines with rectangular symbols plot the sample mean of the μ4, across the 20 repeats, computed at a variety of a using Algorithm| 2 The error bar indicates the minimum and maximum of the pas.. 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( Naplaaee), while the red line with circular symbols indicates the sample mean of the Riemannian distances d(z, ganss). The error bands indicate the sample mean +SEE Refer to Section 5.2 for details.
and the smaller the a the closer the results will be. As the a gets larger, the privacy budget l gets smaller on S compared on R. This can be explained by the fact that S is 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 gives fairly accurate estimation for larger a. However, as a gets smaller, Algorithm 2 has tendency to generate estimates that exhibit 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 Bhattacharyal 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 cDP,, it's shown in Li et al. [002
any mechanism that satisfies eDDP can achieve μ-GDP with μ -00 (1/(1 + E)) I V VT/22 /2e. Our results show significant improvements in utility for the privatization of the Fréchet mean when using our proposed Gaussian mechanism, opposed the Laplace mechanism, in both examples. In Section[..I] we cover some basics on differentially private Fréchet mean. Section we discuss the numerical results the sphere. Simulations are done in R on Mac Mini computer with an Apple MI processor with 8 GB of RAM running MacOS 13. For more details on each simulation, please refer Appendix A.6 The R code is available in the GitHub repository: httts:://ggttiii Dia.iii-Digo7/aauussaee www.assininasaaeeaeeeeeeeee Differentiiiin Pww.--rrivacyyiaee on Riemann i an Manifolds
5.1 Differentially Private Fréchet Mean
For more details on Fréchet mean under the DP setting, please refer to Reimherr al. [2021) Consider a set of data 4 .1,..., NN 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 the data, J arg min.eM Σ/ d (3r, ar.) 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 C B, (ma) for some mg E M, where min {inj M, T (2/K)) /2 for k > 0 and r* = inj M/2 for K S O. Note k denotes an upper bound on the sectional curvatures of M.
r" with y"
we can then compute the sensitivity of the Fréchet mean RReimherr et al. 1 consider two datasets D ~ D'. If and E' are the two sample Fréchet means of D and D'
Under Assumption T
8

---

respectively, then
2r(2 - -((,,)))
2r 22r/icoolyR211 n: B>C S 0
d {2)
h(r, = {1
n)((,,k)
5.2
Sphere
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 S and identity it as subspace of Rd+1 as Sd {p E Rd+1 ||p||2 = 1}. Similarly, at each p E 5tt we identify the tangent space T,5 as T {o E Rd-1 : 0}. The geodesics cos(t)p + sin(t)e with -I < Et- S π where Tp.o denotes the geodesic starts at p with unit direction vector v. The exponential map exp, Tp + St is given by (0) = p and exp,(u)) = cos([|u|])p + sin(v)v/Ilel) for v # 0. The inverse of the exponential map log, : S (-p) - -Tp.dd has the expression log,(p) = 0 and logp(1) arccos(p g)lg (p 4)pl | (p q)a -1/2 for & p.-q. follows that the distance function is given by d(p. q) = arccos(p) T 4) E [0, m]. Therefore, 5t has an injectivity radius of π.
are the great circles, (t)
We initiate our analysis by generating sample data D = {II...., J from a ball of radius x/8 on S and subsequently computing the Fréchet mean E. To disseminate the private Fréchet mean, we implement two methods: (i) We first generate the privatized mean Tgauss by drawing from (M o²) employing the sampling method proposed by Hauberg (2018). The privacy budget then computed using Algorithm 2 (ii) Next, we convert μDGDP the equivalent e-DP using E = logll ( 2/2))/ (-(///))) and generate the privatized mean Tiaplace by sampling from the Riemannian Laplace distribution with footprint and rate A/s using the sampling method introduced
by You and Shung [2022].
10 maintain constant sensitivity A. With A held constant, we let the rate o = k/4 with 1 < k < 12. The objective here is to discern the difference between the two distances d(. Fgauus) and d(, #Iaalucee across varying privacy budgets u.. The third plot in Figure [ displays the sample mean of the Riemannian distances d(ī, Fganss) (in red with circular symbols) and d(T,, Staplace) (in blue with triangular symbols) across 1000 iterations with the error band indicating the sample mean +EESE. From observing the third plot, we see that our Gaussian mechanism achieves better urility, especially with smaller privacy budget μa. With larger μt, 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 a., Effectively, Fgans satisfies GDGDP with a smaller compared to Napplaee
Throughout these simulations, we fix the sample size
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 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 (e. 8DP to general Riemannian manifolds. There are several points of improvement around Algorithm| 2 as well. Although Algorithm [ 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 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 obtain a theoretical utility guarantee due to the lack of simple analytical relation between and rate a. Furthermore, although Algorithm requires the manifolds to have constant curvature, it's possible to extend Algorithm and Theorem 4 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 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 kemne on Riemannian manifolds (see Grigoryan 2009] for example). Incorporating the heat kernel in privacy mechanism presents ample potential for novel and noteworthy discoveries.
Acknowledgements
We would like express our greatest appreciation to Professor Xiaowei Wang of Rutgers Univer- sity 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 Al 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.
References
V. Arsigny, P. Fillard, X. Pennec, and N. Ayache. Geometric means in novel vector space structure on symmetric positive-definite matrices. SIAM Journal on Matrix Analysis and Applications, 29 (1):328-347, 2007. doi: 17.1137/050637999 httpsstts////. wtt..0//00.11770006//39999999990
10. 11..1.170550000
D. M. Asta. Kernel density estimation symmetrie spaces. In International Conference 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 httpss//pprcceeednngg mlr.press/ v80/ballee8a. 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 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 classifica- tion. Latent Variable Analysis and Signal Separation, 09 2010. doi: 10. 10.10077778-3-10 ---7788---4--1111 15995-4_ 78.
B. Barak, K. Chaudhuri. C. Dwork, S. Kale, F. McSherry, and K. Talwar. Privacy, accuracy, and consistency too: A holistic solution contingency table release. In Proceedings of the Twenty- Sixth ACM '07, page 273 282, New York, NY, USA, 2007. Association for Computing Machinery. ISBN 9781595936851. doi: 10.1145/126533..11 055511225530122555606 1265569. Utthstts:://oo1 org/ 10. 1145/1265530 1265569
Symposium on Principles of Database Systems, PODS
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. Jatt:////// http:///www...ooppppppp//////e//
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 9781 177109999
M. Bun and T. Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. 14th Theory of Cryptography Conference, 2016. URL https://axxiv http:///aaaxii..r//////0/00 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: 00.214/18-AOS166 URI. https
//doi //doi.org/10 org/10...... 1214/12111111 A0S1692
10

---

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 6(1):592-615 jan 2013. doi: 10.1137/110853376. URL
https://doi.ooe org.//o.oooooooooooooooooooooooo 10. 1137/110853376
E. Chevallier, D. Li, Y. Lu, and D. Dunson. Exponential-wrappped 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 riemannian symmetric spaces. Journal of the Royal Statistical Society. Series B (Stutistical Methodology), 4922)463-482, 2017. ISSN 13697412, 14679868. URL http: /tttp://www.rr jstor httg/stable//ee (ttaabee4448252) 44682521
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:: neurips cc/ cc/paper files cateeeefffleeppppprreeeee pttpp//ppp/p/////////// [cc4422224adff000455555550222222 Paper. paopprr.dff
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.
L. Dryden. Statistical analysis on high-dimensional spheres and shape spaces. The Annals of Statistics, 33(4):1643-166, 2005. ISSN 00905364. URL http: 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, 33)):102-1123,, 2009. ISSN 19326157, 19417330. URL hRL //ww: jstor. org/ httg//taabee3302222
R. M. Dudley. Real Analysis and Probability. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2nd edition, 2002. doi: 10.0017/CB097805
C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9:21 9:211-407, aug 2014. ISSN 1551-305X. doi: 10.1 1161/0400000044. URL https //doi 10. 10..115611400044040
C. Dwork, K. Kenthapadi, F. McSherry, Mironov, and M. Naor. Our data, ourselves: Privacy via distributed noise generation. In Proceedings of the 24th Anmual International Conference on The Theory and Applications of Cryptographic Techniques, EUROCRYPT'ON 06, page 486-50 503, Berlin, Heidelberg, 2006a. Springer- ISBN 3540345469. doi: 10. 10.1007/117616799 29, URL https://doi. orgooog//// 10. 1007/11761679..1
C. Dwork, F. McSherry, 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. arXiv preprint arXiv:2204.09799. 2022.
A. Grigoryan. Heat kernel and analysis on manifolds. American Mathematical Soc., 2009.
H. Hajri, I. Icaa, S. Said, L. Bombrun, and Y. Berthoumieu. Riemannian laplace distribution the space of symmetric positive definite matrices. Entropy, 18(3), 2016. ISSN 1099-4300. doi: 10.3390/e 10390//1800000 18030098. URL //www
A. Han, B. Mishra, P. Jawanpuria, and J. Gao. Differentially private riemannian optimization. arXiv preprint arXiv:2205.0949)) 2022.
S. Hauberg. Directional statistics with the spherical normal distribution. In 2018 2/st International Conference on Information Fusion (FUSION), pages 704-711, 2018. doi: 8455242.
Helgason. Differential geometry and symmetric spaces. New York and London: Academic Press, 1962.
11

---

P. Kairouz, S. Oh, and P. Viswanath. The composition theorem for differential privacy. IEEE Transactions on Information Theory, 63(6):437744049 2017, doi: 10.1109/TTT2211.268833
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 httpps://openreevee. net foreefofoummid UpNCpGvD96A
K. V. Mardia, P. E. Jupp, and K. Mardia. Directional statistics. Wiley, 2000.
McSherry and K. Talwar. Mechanism design via differential privacy. Proceedings Annual IEEE Symposium Foundations of Computer Science, FOCS, pages 94-103, 11 2007. doi: WLLLL0//FOCS2200..00
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):129--1250, 2013. URL http://jmmr org/papers/
v14/niyogi13a html
X. Pennec. Intrinsic statistics on riemannian manifolds: Basic tools for geometric measurements. Jour- nal of Mathematical Imaging and Vision, 25:127-154, 07 2006. doi: 10.10077/10851-006- -228-44.
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-norn gradient mechanism. In H. Wal- lach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Garnett, edi- tors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL htttss:/pproceedinnng htwp:/occeeiiinnn....e..o..e.e.e neurips cc/ cccpappr__aeeeeeeeeeeeeeeee files/ Faffeedf22Dcc2211077755a002222
pddf
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 httpps:/prooeeedingss www.rnngg....ui.....e........ www.neeercc.... www.wiis.c.cpppp.rrrrrpppppppp files wwtpppappppppppppp /00////////////////e/ee///
380060048850022220444044444444-8 Paper pdff
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. 1009//TT.011..26555
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. 1110//T.2221..2733322.
C. Soto, K. Bharath, M. Reimherr, and A. Slavković. Shape and structure preserving differential privacy. 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 As- sociates, Inc., 2022. URU//ttpss///rooeddiiiig mew.eeeeeddinneeeeeeeseeee newrips pappr_ffaffff fiwes/llepppll ptles//ppper/222// Slae968fe00saaeaa888883aaae000e0
12

---

P. Turaga, A. Veeraraghavan, and R. Chellappa. Statistical analysis on stiefel and grassmann manifolds with applications computer vision. In 2008 IEEE Conference on Computer Vision and Pattern Recognition, pages 1-8, 2008. doi: 10. 10.100999..2200.455555 45587333
P. K. Turaga and A. Srivastava. Riemannian Computing in Computer Vision. Springer Publishing Company, Incorporated, 1st edition, 2015. ISBN 3319229567.
S. Utpala, A. Han, Jawanpuria, and Mishra. Improved differentially private riemannian optimization: Fast sampling and variance reduction. Transactions Machine Learning Research, 2023a. ISSN 2835-8856. URL
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 httpss:/ ndd/formm??d
mAx8Qq214f
E. Vinberg, 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 the American Statistical Association, 105(489):375-38,, 2010. ISSN 01621459. URL http::////// //wt:: jstor org/stabble/9747003
F. S. Woods. Space of constant curvature. Annals of Mathematics, 3(1/4):71-112, 1901. ISSN 0003486X. URL
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/BBEE.227.2225555
M. Zhang and T. Fletcher. Probabilistic principal geodesic analysis. In C. Burges, L. Bottou,
M. Welling, Z. Ghahramani, and K. Weinherger, editors, Advances in Neural Information Process- ing Systems, volume 26. Curran Associates, Inc., 2013. URL http:hhttts::::ooeeeeeiiiii neurips pdf
/ ocgpoo//eaaaprec////aassosoaaaae
13

---

A
Appendix
A.1 Theorem 3.1
First, we need to introduce the notion of privacy profile [Balle et al. 2018
The privacy profile Λ of mechanism M is function associating to each privacy parameter = e bound on the a-divergence between the results of running the mechanism on two adjacent datasets, ie. (m((s)= supz=a' De (M(a)) (x') where the a-divergence (a 2 between two probability measures μA, μL is defined as
(2) -a du
du
Da (AllA() = sup (m(E) - aql(E))
dy'(z) = Σ (m(=)) - ax))) ZEZ
where E ranges over all measurable subsets of 7, [1+++ max(:00) Informally speaking, the privacy profile represents the set of all of the privacy parameters under which mechanism provides differential privacy. Furthermore, the privacy profile can computed using Theorem 5 of Balle and Wang [2018]
(E) = sup
Pr
D.D .M
>e - Pr D < <E
D-D'
where L D,D' D. is the privacy loss random variable of the mechanism M on inputs D = D' defined M
as L D.D' L log (du/dp") (z), where MMD), n' MM (D'), and z It follows that for our Riemannian Gaussian mechanism M, the privacy profile 8,M can be rewritten as
M sup / Pm.o (1) duly) e Pm) dv(y)
D=D'
where A = (y E M o o (v) 2 } and m == f(D), 72 = f(D'). This is exactly the left-hand side of (2).
The following theorem establishes connection between GDP and privacy profile:
22 Theorem A.1 (Theorem 3.3 of Liu et al. (2022).. Let po V /lime-+ac 22 8ale) A privacy
mechanism A with the privacy profile ó (E) μ-GDP and only if uo oo and is no smaller than po.
Theorem A. implies that a mechanism with finite μl is p-GDP for some privacy budget Note that Theorem 3.1 only tells that Riemannian Gaussian distribution can be used achieve μ-GDP for some μr. Therefore, to prove it, we only need to show that Ho is finite. We will show μo < co by demonstrate that log (x()) OE²2). To do so, we will need the Bishop-Grois Gromov comparison theorem:
Theorem A.2 (Bishop-Gromov; Lemma 7.1.4 Petersen (2006)). Let M be complete n- dimensional Riemannian manifold whose Ricci curvature satisfies the lower bound
Ric 2 (n - 1)K
for a constant K E R. Let MR 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,7 r) the ball of radius r around point p. defined with respect to the Riemannian distance function. Then, for any p M and PK Mg. the function
Vol B(p r)
Φ(r) = Vol (pk,r)
is non-increasing on (0, xo). As goes to zero, the ratio approaches one, so together with the monotonicity this implies that
Vol B(p,r) S B (pk,r).
Bishop-Gromov 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 global property in the sense that and px can be arbitrary points on the manifolds.
It is known that mechanism M is (e, DP if and only if D.s (M(D) (D')) < 5 for every D and D'' such that D ~ D'.
14

---

A.1.1
Proof of Theorem 3.1
Proof.
By A.1
we only need to show that for any 17 E M, when e + 00,
J, Po.o (v)de(v)) =e -0
where A is given by
A = (v E o > e Let's consider M ty E M P (V)/PPr (1) E We have
Pn.c(()
log
Pr),o(())
(d(1) y)² d(r', .y)²) +C
2x
A
(2d(1,, y) +1) + C, by triangular inequality,
20²
where C loo log(Z(n;
log ((1 0)). Thus we have,
d(n, 3) < 20 - -C) 2
Pn.o (1) Pe' (1)
S E
2A
Let 20 (c)) note that since (r) S M,A we have S (r),, Thus, we only need to prove the following:
24
J M,Br(() Pmoor (w) = =c-
when + One can easily show the following incquality,
(no (2r2)))B,(r))
S ((,, 0) e 5z (Vol B(n 2r) Vol B(n,))
(4)
By Theorem A.2 we have the following three cases:
1. > 0. Then the standard space MR is the n-sphere of radius 1/VK. (Vol B(n, Vol r)) is obviously less than the volume of the whole space MR Thus we have
f J Pno (y) s Z(n,o)
s(n)VK
(5)
where sn)) = 2nr 2
[(T) is constant relative to the dimension n. One can easily find that as - 00, B, will cover the Mg. and the right-hand side of inequality 5 will approach to 0 as e -0(e).
2. K = 0. Then the standard space Ma is the dimensional Euclidean space R", We have
f Jn, (u)d((()))) S o(n e π 7/2,m
(6)
T +1)
The same with above, when E + oc, (2r) will cover the R² and the right-hand side 6 will approach
-
3. K < 0. The standard space M, (K) is the hyperbolic n-space H", The hyperbolic volume Vol B(nk,r) with any 77 E H is given by
(sinh(( (sinh(V-Kt) (
Vol B r) s(n))
dt
V-K
where the hyperbolic function is given by sinh(æ) = (E" (E-)/=2//2 1/2. It's not hard to see that
(n 1)
sinh"(t) <
(8)
n
15

---

Plugging the 8 into 7
we have
Vol (T r)
S 8n
n
k(n-1)r
(9)
(n 1)2
K
Combining 9 and 4
we have
J R,((2r))BB.o)) Br,)) Pn. (v)dv(y) S c(n) ((n, 0) e -V--KK(n-))2
(10)
The principle part of the exponent of the right-hand side 10 is still -E? Thus. when g + oc, approaches as e-((e=)
A.2
Theorem 3.2
Proof. Follows directly from Definition 2.2 Theorem 3.1 and Theorem Balle and Wang 2018
A.3 Corollary 3.2.1
Proof. In this proof, we will parameterize points S using their polar angles.
On S the Riemannian Gaussian distribution with footprint 77 and rate a has the following density,
Pn.a (0) = -E
- (0-1 mod m)² Zo = 2
(-
Zo
Note that since 5t has constant curvature, we can use Theorem 4.1
instead of Theorem
3.2
WLOG assume 7/1 2x takes the following form,
& and 7/2
oे and thus d(m) 72)
A. Given arbitrary e, the set
π + 2 2x
A =
A
and it follows that must have
8 10, T// (2(22)
(1I)
Thus have
f
Pm, (v) duly) e S (V) du(y)
1
+ (v1-0 mod x)² d0 e0 / e uoz (m-0 mod nT) d0
Z
1
(1
mod x)²² d0 E= / (na-0 mod x²² d0
Z
Æ 22
1
2x
6
(1)
00/2
d0
e
2nd
(na-
mod mr d0
7
1
2T
171
$
σ8
20d (12
mad x)2 d0
7
A
0
A
1
90
π
20 (m2-8 mod a)? do
+
6
Z
A
2
A
25
A
16

---

We have evaluated the first integral, and now let's consider the second integral. For S
A² 27 we have
JA
2 (Ha-
mod m)²
d0
22c
2
20=10- 18 10-1
20
d8
20
(9- (2- de
P2+T
π
00
00
A
(-
π
v 2
+
+ $
+b
A
20
A
20
Thus for e < 2n
A
we have,
/ Pm) du(y)
Pin oin (1) du(y) c²
VITO
0E
A
DE
Z
A
+
20
-
e
+
A
20
(12)
VTTO
A
σ0
A
e
$
7
20
0
A
20
C.
Similarly, for 8 >
20 we have,
e
2.2 (w2-0
mud x)²
d8
2x a2e
20 (8- (2n++ d0
à
π
90
]
v 2xσ
$
+
A
20
0
A
2a
A Thus for have,
/
Pmi (v) duly) 6²
Pizzo (1) du(y)
V2TO
DE
A
E $
(13)
Zo
A
20
A
20
v V2Ta
09
A
O0
π
e
+
Z
A
2g
A
2
Put 11).
12
and
together with Theorem
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 Manifolds
In this section, will introduce some basic facts about group action which will be used 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 non-empty set G together with binary operation G x G G, (a, b) + a- such that the following three axioms are satisfied:
Associativity:
Va,b, G, (a. b) a(b.
17

---

Identity element: Be E G, Va E G,
Inverse element: Ya E G, =a- E a,
Definition A.2. Let G be a group and X be an arbitrary set. A left group action a map
G X + X, that satisfies the following axioms:
a(le =
alg, a(,, x)) = a(gh,z)
Note here we use the juxtaposition gl denote the binary operation in the group. If we shorten alg,z) x by n, it's equivalent to say that e x = n, and g (h- x) = (gh)
Note each g E G induces map Li : X + X, + x..
A.4.2 Homogeneous Riemannian manifolds, symmetric spaces and spaces of constant curvature
Let M be a Riemannian manifold and (MM be the set of all isometries of M, that is, given E I(M), d(g z, y) d(x, y). for all æ, E M. It is clear that I (MM forms group, and thus, for given g (M) and M.g + y, for some y MM is a group action. We call (MM the isometry group of M.
Consider E M,, and let H Stab(o) (h G o o}, that is, H is the Stabilizer of M. Given E I(M) its linear representation + d,.9 in the tangent space T.M is called the isotropy representation and the linear group d, Stab(x) is called the isotropy group the point x.
We say that G acts transitively on M, iff, given H, y E M, there exists a g M such that y gg.
Definition A.3 (Helgason) [962). 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 gH + 0,g G.
By definition, we have d(., y) d(g x. y) for any g E G and any x, y E M. More importantly, any integrable function f M - TR, we have Helgason 1962
[ f(x)dv(x) / flg x))(()))()))))))))))))))))))))))
This property leads Proposition 4.1
Definition A.4 ([Helgason] 1962 A Riemannian symmetric space is Riemannian manifold M such that for any æ E M, there exists 8, = I(M) such that sy x = I and d8g = -I. S2 is called symmetry
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 homogeneous Riemannian manifold, but the converse 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, space of constant curvature is symmetric space but the converse is not true.
A.5
Theorem
Proof. Let be the isometry group of M. Let m1 72 M arbitrary points such that d(m, 72)
A. By Corollary
4.1 the A reduces A {y M d(12, y)² d(m, . y)² > -20=}}
What we need to show is the following, for any points 1/ v/ E M such that d(1h 1/2) A.
f Pm (y) dv(y) - e (V) du(y) = / Pri (v) du(y) e (v) de(y)
18

---

where A' = E M: d( y)² 2 d(1/.. 20 2 20²e]. It's sufficient to show
S Pm
| Pij o (V) du(y),
S1 Pma = ./a Pi (v) dv(y).
(14)
We can separate the proof into three cases: (1) m/1 m1 + m2 (2) 1/1 + m.7/ v/1 + M1, 1/2 + 1/2-
7/2 (3)
Case (1): Ví = 71, 1/2 + 12:
It follows that 7/2 is in the sphere centered with radius A. (4) then follows from the rotational symmetry of the constant curvature spaces.
Case (2): v F ?,, 1/2 122
Same case (1).
Case (3): v/ + ", 1/2 + 1/2
For any 7/ # 7h1 there exists g E G. such that = 1// Denote 7/2 = 722, we have
gA (g y d(12 u)² d(mh, u)² 2 20 20²²}
= {g y d(1/2 g 8)² d(1/1 9 yy²² 2 20"
{y d(1/2. v)² d(m v)² 2 20²E}
=A A'.
Let F(y) = Pm (1)1 (2). we have
pmo (2) dv(y)
I Fo Lu (v) (v) dv(y)
M
= [ Poo 1)) d(L "(Lz))
vvy); change of variable formular,
M
[ Pm ())la(()) dv(y); is G-invariant measure,
J
e de dv(y)
Zo Jgd
e di
1 du(u)
Zo J9A
1
= dv(y)
Jg1
Pot ooh
gA
[ Pot (o)
For SA Pmm, (v) (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 (M, o²) on S (section 4.2 we first sample from truncated normal distribution with μ 0 and o² then embed the sample to IR and lastly counter-wise rotate the sample with degree 0.
For simulation on S2 (section 5.2). cos(A)² 2)/// 0). Though any pair 1).1)' E S with d(n,,'') = A 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].
choose the pair of n and n/ to be (1,0,0) and (cos(A),
19

---

A.6.1 R Codes
For simulations in section 4.2 space and sphere_functione functions. & sl simulation. R for unit circle S For simulations in section 5.2 refer to R files
refer to R files euclid funccffossniont & fuclid_simulationn R for Euclidean
R &
20


Reviews:
[{"review_id": "2tel2jYe5C", "reviewer": "Reviewer_j3sD", "summary": "This work studies an extension of a Gaussian privacy mechanism on Riemannian manifolds, so as to extend the notion of mu-GDP for estimators with given global sensitivity. The idea is to sample a random point on the manifold with a Gibbs density (wrt to the Riemannian volume) whose potential is proportional to the squared distance to the given estimator (that would simply be a Gaussian density on a Euclidean space). It is well known that in order for such a distribution to be well defined, it is enough to assume that the sectional (or, equivalenty, Ricci) curvature of the manifold is bounded from below. The main challenges, then, reside in : (1) tuning the temperature parameter of the Gibbs distribution so as to obtain mu-GDP, and (2) sample from such a distribution. \n\n\nWhile giving general formulae for the choice of the temperature parameter, the authors study the case of homogeneous manifolds, as well as model manifolds with constant curvature, also providing simulation studies. \n\nDifferential privacy on non-linear spaces, in particular Riemannian manifolds, has not been studied a lot yet, and this paper aims at providing new, simple insights. ", "questions": "See paragraph on weaknesses.", "limitations": "NA", "rating": 4, "confidence": 4, "soundness": 1, "presentation": 3, "contribution": 1, "strengths": "•\tThe question tackled in this paper is important, given the increasing need of dealing with non-linearity in data. \n•\tThe paper is written clearly and the main text is easy to follow.", "weaknesses": "•\tWhile the paper addresses an important question, the execution remains shallow. Laplace and Gaussian mechanisms can be very easily extended to Riemannian manifolds, and the computations that yield to determine the calibration of their parameters are very similar to the Euclidean case. One challenge that is barely addressed here (see the very brief remark just before Definition 4.1) is the understanding of the connexion between these parameters and the geometry (in particular, curvature bounds) of the ambient manifold. Instead, the authors choose to focus on very simple (and perhaps not realistic in most applications) manifolds, where everything becomes much simpler. Hence, I think that a big, if not essential, part of the picture is missing in this work.\n•\tThe presence of Definition 3.1 (mu-GDP mechanisms on manifolds) is obscure to me: A definition is already given in Definition 2.2, and I do not see why it should be different on manifolds. Should Definition 3.1 actually be a theorem? I mean that one should check that M is mu-GDP in the sense of Definition 2.2 if and only if it is (eps,delta(eps))-DP for all eps>0, with delta(eps) given by the formula that appears in Definition 3.1 (something similar to Theorem A.1).\n•\tSome proofs seem either wrong or incomplete to me, here are some pointers:\n\t\t- One line after Theorem A.1, this theorem is interpreted using the O(eps^2) notation, which completely forgets the dependence in mu. Hence, the whole proof of Theorem 3.1 forgets mu and is, therefore, imprecise/incomplete. \n\t\t- I did not understand the first line of the proof of Theorem 3.1. Also, there, what is x (it does not appear in the formula)?\n\t\t- In Equation 4, I think that the normalizing constant Z_{eta,sigma} is missing in the upper bound. \n\n\nSome minor remarks: \n•\tLine 92, there is a typo.\n•\tLine 99: « the » should be replaced with « a ».\n•\tLine 237: Remove « satisfies »\n•\tEvery citation should come to a pointer to a specific definition or result, especially when the citation refers to a whole book (e.g., Dudley, 2002)! \n•\tIn Theorem A.1, what is the ‘t’ in the subscript of mu_t?\n•\tAlso in Theorem A.1, « privacy profile » has not be defined anywhere. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nDear Reviewer,\n\nThank you for your thorough review and constructive feedback. We appreciate your insights, and we have addressed your concerns and questions in our response below:\n\n## Weakness\n> Laplace and Gaussian mechanisms can be very easily extended to Riemannian manifolds, and the computations that yield to determine the calibration of their parameters are very similar to the Euclidean case.\n\nWe have to disagree here. We agree that for the Laplace mechanism, the extension to Riemannian manifolds is straightforward as demonstrated in Reimherr et al. [2021]. However, for the Gaussian mechanism, it's difficult to calibrate the parameter due to the lack of inner product structure under the general manifold setting. The existing literature either focuses on a specific manifold with zero curvature or on tangent spaces instead. We improve on the existing literature by providing a way to extend the Gaussian mechanism to general manifolds for GDP in Theorem 3.2 and designing an easy-to-implement algorithm to calibrate the noise parameter $\\sigma$ in the case of constant curvature spaces.\n\n> One challenge that is barely addressed here (see the very brief remark just before Definition 4.1) is the understanding of the connexion between these parameters and the geometry (in particular, curvature bounds) of the ambient manifold.\n\nWe agree that this is indeed an important challenge to tackle. It is partially addressed as we establish the connection between the privacy parameter $\\mu$ and the underlying geometry implicitly by connecting $\\mu$ with the noise parameter $\\sigma$ of Riemannian Gaussian distribution in Theorem 3.2.\n\n> Instead, the authors choose to focus on very simple manifolds, where everything becomes much simpler. Hence, I think that a big, if not essential, part of the picture is missing in this work.\n\nAs mentioned previously, the calibration of $\\sigma$ is a difficult task without restricting a specific manifold with zero curvature or working on tangent space. Compared to previous works, the assumption of constant curvature is a significant improvement despite being simple. Additionally, it serves as a necessary stepping stone for future works where we plan to relax the assumption to symmetric space/homogeneous space, which includes many frequently used manifolds like SPD space.\n\n### Regarding the use of definition 3.1:\n> The presence of Definition 3.1 (mu-GDP mechanisms on manifolds) is obscure to me.\n\nThe original definition of GDP given in 2.2 is based on the hypothesis testing interpretation. If we were to extend to general manifolds, we should consider the hypothesis testing of distinguishing between Riemannian manifold generalization of Gaussian distribution. It would be a challenging task as obtaining the general manifold version of the optimal trade-off function $T(N(0,1), N(\\mu, 1))$ would be difficult due to the following reasons:\n1. There is no canonical way of extending Gaussian distribution to the general manifold. Different methods of extension (mentioned briefly after Definition 3.3) could lead to slightly different versions of GDP on manifolds.\n2. Common ways of constructing hypothesis testing are difficult to implement. For instance, computing the ratio between two likelihoods for the likelihood ratio test is a difficult task.\nTo bypass such difficulty, we introduce definition 3.1.\n\n> Should Definition 3.1 actually be a theorem?\n\nDefinition 3.1 is based on a known equivalence between GDP and approximate DP on Euclidean spaces. Since approximate DP is well defined on the general manifold, this connection provides us with a natural way of extending the notion of GDP to the general manifold.\n\n### Regarding the proof of Theorem 3.1:\n> In Theorem A.1, what is the $t$ in the subscript of $\\mu_t$?\n\nThe $t$ stands for \"tail\", we realized that the use of subscript $t$ is not appropriate here and causes confusion, and $\\mu_{tail}$ will be used instead in the revision.\n\n> privacy profile has not been defined anywhere.\n\nWe will add the definition of privacy profile in the revision. The privacy profile is a function associating to each privacy parameter $\\alpha = e^{\\varepsilon}$ bound on the $\\alpha$-divergence between the results of running the mechanism on two adjacent datasets. Note that for our Riemannian Gaussian mechanism, this is exactly the left-hand side of equation (2).\n\n> One line after Theorem A.1, this theorem is interpreted using the $O(\\varepsilon^2)$ notation, which completely forgets the dependence in $\\mu$. Hence, the whole proof of Theorem 3.1 forgets $\\mu$ and is, therefore, imprecise/incomplete\n\nTheorem A.1 implies a privacy mechanism with finite $\\mu_{tail}$ can achieve $\\mu$-GDP for some $\\mu$. The exact value of $\\mu$ is not the focus here as Theorem 3.1 simply says that the Riemannian Gaussian mechanism can achieve $\\mu$-GDP for some $\\mu > 0$. To determine the exact value of $\\mu$, we refer to Theorem 3.2 and Theorem 4.1. We will add more explanations in the appendix for better clarity.\n\n> Also, there, what is $x$ (it does not appear in the formula)?\n\nThis is a typo, it should be $\\eta$ instead.\n\n> I did not understand the first line of the proof of Theorem 3.1.\n\nThe key idea is to show $\\mu_{tail}$ is finite, which is implied if $-\\log(\\delta_{\\mathcal{A}}(\\varepsilon))$ is $O(\\varepsilon^{-2})$. Since the privacy profile $\\delta_{\\mathcal{A}}(\\varepsilon)$ can be represented by the left-hand side of equation (2), we have the first line of the proof.\n\n> In Equation 4, I think that the normalizing constant is missing in the upper bound.\n\nYes, it will be corrected in the revision. However, it will not affect the rest of the proof since it is finite and does not depend on $\\varepsilon$.\n\n> Every citation should come to a pointer to a specific definition or result.\n\nThank you for the suggestion. The citations will be adjusted to include specific definitions/results for better readability."}, {"review_id": "rdpo9ITrkP", "reviewer": "Reviewer_12f9", "summary": "To obtain manifold-value statistic with the Gaussian differential privacy (GDP), the authors extend the GDP from Euclidean spaces to general Riemannian manifolds. Then they proved that their proposed Riemannian Gaussian distribution make GDP tractable. Furthermore, they proposed an efficient numerical algorithm to compute the privacy budget μ on the manifolds of one dimension, especially on the manifolds with constant curvature. At last, they provided some simulation experiments to illustrate performance of their algorithms.\n\nDue to the importance of GDP among the variants of DP, it is meaningful to generalize GDP to Riemannian manifolds. They solved this question partially. Considering the importance of this question, the paper is worth to be accepted. Also, this paper is organized clearly except some typos. I have checked carefully some important details of proofs, so the results should be reliable.", "questions": "1.\tThis paper mentioned all hypothesis testing-based privacy definitions converge to the guarantees of GDP in the limit of composition and when the dimension of the privatized data approaches infinity, a large class of noise addition private mechanisms is shown to be asymptotically GDP. Are these results valid on Riemannian manifolds?\n2. \tIt is hard to solving the case of manifolds of dimension $d>1$, which make us use numerical methods to compute the integral. This work uses MCMC to approximate the integral, how about other numerical integration methods?\n  3.\tThey claimed that their work is the extension of an important variant of DP, so this work may be valuable in practice. Thus they should explain the point clearly in the introduction and provide some real world numerical examples.", "limitations": "See \"weakness\".", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.\tThey research the extension of an important variant of DP—GDP and prove that they can achieve GDP on Riemannian manifolds by using Riemannian Gaussian distribution.\n2.\tFollowing previous works, their results make sense.\n", "weaknesses": "Some typos influence the readability of this paper. For example, ‘compliant’, not ‘compliment’ in subsection Main Contributions; and $N_m(\\eta,\\sigma^2)$  is correct, not $N_m(\\mu,\\sigma^2)$.\n2. For the case of manifolds of dimension $d>1$, they make a too strong assumption that the manifold with constant curvature to design an efficient numerical algorithm. To the best of my knowledge, this assumption can’t encompass enough manifolds (I can only think of Euclidean space, the sphere and Lobachevskij space). The motivation of this assumption is not strong in practice.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you for your thorough review and constructive feedback. We appreciate your insights, and we have addressed your concerns and questions in our response below:\n\n## Weakness\n\n>  For the case of manifolds of dimension $d>1$, they make a too strong assumption that the manifold with constant curvature to design an efficient numerical algorithm. To the best of my knowledge, this assumption can’t encompass enough manifolds (I can only think of Euclidean space, the sphere and Lobachevskij space). The motivation of this assumption is not strong in practice\n\nWe agree the assumption of constant curvature space is restrictive. However, it serves as a necessary stepping stone for future works where we plan to relax the assumption to symmetric space/homogeneous space, which includes many frequently used manifolds like SPD space. \n\n## Questions\n\n> This paper mentioned all hypothesis testing-based privacy definitions converge to the guarantees of GDP in the limit of composition and when the dimension of the privatized data approaches infinity, a large class of noise addition private mechanisms is shown to be asymptotically GDP. Are these results valid on Riemannian manifolds?\n\nThe convergence to GDP on general manifolds is still an open question. Hopefully, we can address it in future works. \n\n> It is hard to solving the case of manifolds of dimension $d>1$, which make us use numerical methods to compute the integral. This work uses MCMC to approximate the integral, how about other numerical integration methods?\n\nWe haven't considered other integration methods. The MCMC method is a natural method to use here due to the appearance of the probability density $p_{\\eta, \\sigma}$ inside the integral. However, the Bayesian quadrature method could be useful here as it can quantify the uncertainty of the integral estimation. \n\n> They claimed that their work is the extension of an important variant of DP, so this work may be valuable in practice. Thus they should explain the point clearly in the introduction and provide some real-world numerical examples.\n\nOne of the practical importance of extending GDP to general manifolds is the better data utility it can achieve under some use cases (query composition and subsampling). The most notable example of nonlinear private data is in medical imaging. They reside in the space of SPD matrices. Although GDP can be extended to SPD space without issues, calibrating $\\sigma$ efficiently requires the assumption of constant curvature. Hopefully, we can relax the assumption of symmetric space, which includes SPD space, in the future."}, {"review_id": "UbA39GYdFi", "reviewer": "Reviewer_3t86", "summary": "The authors consider the problem of achieving Gaussian Differential Privacy (GDP) on Riemannian manifolds.  After defining what this concept means, they provide a mechanism capable of achieving GDP via a generalization of the Gaussian to manifolds.  The major challenge in implementing the approach is in finding a suitable scaling parameter, $\\sigma$, for the noise.  The authors define several equations that must be solved to find $\\sigma$, each which become more tractable as additional structural assumptions on the manifold are made.", "questions": "Def 3.1: I would emphasize that this is a known equivalence from the Dong et al paper.  I think the authors should also explain a bit more why this definition is easier to work with on manifolds than the original gaussian dp.  In general, I’m not convinced that it truly is.  The GDP definition is simply a statement about the tradeoff between type 1 and type 2 errors, it really has nothing to do with the underlying space.  So the central challenge isn’t defining GDP for manifolds, but defining a mechanism that achieves it. \n\n“In contrast to the task of releasing manifold-valued private summary, Han et al. [2022] considers a different scenario where the private summary resides on the tangent bundle of Riemannian manifolds and extends (ε, δ)-DP and its Gaussian mechanism to general manifolds.\"\nThis seems a bit inaccurate since their intention was not to privately release the gradient but rather use the private gradient for the private summary which resides on the manifold.  I think the wording here should be clarified.\n\nMinor— I don’t think the authors ever actually define $\\Phi$.", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is a timely paper as there has been an increased interest in manifolds in statistics/machine learning.  There have also been several recent works that consider privacy within these contexts as well.  The Gaussian mechanism is one of the most popular tools for achieving privacy, so it is quite natural to consider it in the context of manifolds.  The extension of the Gaussian mechanism to manifolds is much more challenging than the Laplace.", "weaknesses": "Implementing the mechanism seems quite challenging.  Just to find the scaling parameter $\\sigma$ is difficult in general, plus one must do something like MCMC to actually sample from the mechanism.  This limits the practical impact of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you for your thorough review and constructive feedback. We appreciate your insights, and we have addressed your concerns and questions in our response below:\n\n## Weakness\n> Implementing the mechanism seems quite challenging. Just to find the scaling parameter is difficult in general, plus one must do something like MCMC to actually sample from the mechanism. This limits the practical impact of the paper.\n \nYes, this is one of the difficulties when working under the general manifold setting. The utility gains from utilizing the intrinsic geometry of the data manifold come with the cost of computational complexity. It really depends on whether the end user is willing to make the trade-off for better utility, and hopefully, more end users will be willing to make the trade-off as computing technology advances.  \n\n## Questions\n\n> Def 3.1: I would emphasize that this is a known equivalence from the Dong et al paper. \n\nThank you for the suggestion. The emphasis will be added in the revision.\n\n> I think the authors should also explain a bit more why this definition is easier to work with on manifolds than the original gaussian dp. In general, I’m not convinced that it truly is. The GDP definition is simply a statement about the tradeoff between type 1 and type 2 errors, it really has nothing to do with the underlying space. \n\nI disagree partially here. In order to extend GDP to general manifolds using the hypothesis interpretation, the hypothesis test should reflect the underlying geometry. More specifically, in Euclidean spaces, $\\mu$-GDP relates to the hypothesis testing problem of distinguishing between $N(0, 1)$ and $N(\\mu, 1)$. If we were to extend to general manifolds, we should consider the hypothesis testing of distinguishing between Riemannian manifold generalization of Gaussian distribution. However, there are different ways of generalizing Gaussian distribution as mentioned briefly after Definition 3.3. Regardless of which extension to use, it is difficult to determine the optimal trade-off between type I and type II errors under this Riemannian manifold hypothesis testing setting. For instance, computing the ratio between two likelihoods for the likelihood ratio test is a difficult task. \n\n> So the central challenge isn’t defining GDP for manifolds, but defining a mechanism that achieves it.\n\nYes, the challenge lies in designing a mechanism that achieves GDP while utilizing as much of the privacy budget as possible (That is, we want the left-hand side of equation (2) to be as close to the right-hand side as possible). \n    \n> This seems a bit inaccurate since their intention was not to privately release the gradient but rather use the private gradient for the private summary which resides on the manifold. I think the wording here should be clarified.\n  \nThe wording regarding Han et al. [2022] will be adjusted to clarify that their focus is to solve empirical risk minimization problems in a $(\\varepsilon, \\delta)$-DP compliant manner by privatizing the gradient which resides on the tangent bundle of Riemannian manifolds.\n\n> Minor— I don’t think the authors ever actually define $\\Phi$.\n\nThank you for pointing it out. It accidentally got deleted during the adjustment process. It will be added in the revision. "}, {"review_id": "1IUBCZbiOV", "reviewer": "Reviewer_vrR5", "summary": "The paper extends definition of Gaussian DP to General Riemannian Manifolds and proposed Riemannian Gaussian mechanism that shows to achieve GaussianDP. Paper also develops MCMC procedure for Riemannian Manifolds with constant curvature. \n", "questions": "NA", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Extending GaussianDP to Riemannian Manifolds\n* MCMC procedure for Riemannian manifolds of constant curvature. ", "weaknesses": "The experimental setup is extremely limited.\n\n* **Baselines** The experiment compares the $\\epsilon$-differential privacy mechanism (Riemannian Laplace mechanism) with the $(\\epsilon, \\delta)$-differential privacy mechanism (GDP mechanism), but it fails to include baselines that use $(\\epsilon, \\delta)$-mechanisms. It is necessary to include comparison with the following:\n\n     *  DP-Riemannian Optimization ($\\epsilon, \\delta$)-differential privacy mechanism (source: https://arxiv.org/abs/2205.09494)\n \n     Additionally, it is recommended to compare with \n    *  Riemannian K-Norm Gradient mechanism ($\\epsilon$-DP) (source: https://arxiv.org/pdf/2209.12667.pdf).\n\n*  **Experiments used only one manifold and of max dimension 3 for n=10 samples:** Experiments were solely carried out on 2-dimensional ($S^1$) and 3-dimensional ($S^2$) manifolds. It is essential to extend the experimentation to include at least one additional manifold, such as a hyperbolic manifold, which represents another constant curvature manifold. Furthermore, it is advisable to introduce variations in the parameters $n$ and $d$ during the experiments.\n\nRelated work : \nAlso related work on DP-Optimization Improved Differentially Private Riemannian Optimization: Fast Sampling and Variance Reduction , TMLR 2023, (https://openreview.net/pdf?id=paguBNtqiO)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you for your thorough review and constructive feedback. We appreciate your insights, and we have addressed your concerns and questions in our response below:\n\n## Weakness\n\n> The experiment compares the $\\varepsilon$-differential privacy mechanism (Riemannian Laplace mechanism) with the $(\\varepsilon, \\delta)$-differential privacy mechanism (GDP mechanism), but it fails to include baselines that use -mechanisms. It is necessary to include comparison with the following: DP-Riemannian Optimization $(\\varepsilon, \\delta)$-differential privacy mechanism\n \nThe reason we are comparing to the Riemannian Laplace mechanism that satisfies $\\varepsilon$-DP is due to the fact any mechanism that achieves $\\varepsilon$-DP can achieve $\\mu$-GDP for some privacy budget $\\mu$ [Liu et al., 2022].  Therefore, our intention is to compare two mechanisms that both can achieve GDP. However, the same thing cannot be said for $(\\varepsilon, \\delta)$-DP mechanism. More specifically,  a mechanism that achieves $(\\varepsilon, \\delta)$-DP cannot guarantee $\\mu$-GDP for any privacy budget $\\mu$. \n\n> Additionally, it is recommended to compare with Riemannian K-Norm Gradient mechanism ($\\varepsilon$-DP) \n\nWe have considered the k-norm mechanism as part of the comparison but quickly dismissed it due to its uses of a different approach for sensitivity computation, so it could be an unfair comparison. However, on second thought, it could provide some insight regardless of its sensitivity computation. We will include the $k$-norm mechanism as a comparison for future works.  \n\n>  It is essential to extend the experimentation to include at least one additional manifold, such as a hyperbolic manifold, which represents another constant curvature manifold.\n\nYes, we do agree on more manifolds are needed. We only experiment on the sphere due to the sampling methods on it being well established. We will work to extend to more manifolds in the future. \n\n> Furthermore, it is advisable to introduce variations in the parameters $n$ and $d$ during the experiments.\n\nThe parameter $n$ will only affect the sensitivity calculation. A large $n$ will result in small sensitivity, which requires less noise perturbation in general. We choose a small $n$ to better illustrate the improvement in utility. \n\n> Related work: Also related work on DP-Optimization Improved Differentially Private Riemannian Optimization: Fast Sampling and Variance Reduction, TMLR 2023\n\nThank you for pointing it out. It will be added in the revision."}]

Author rebuttal:

Meta-review: This paper effectively explores Gaussian Differential Privacy in the context of Riemannian manifolds, addressing a significant topic in the current machine learning landscape. While the theoretical contribution is solid and timely, practical implementation appears challenging, potentially restricting its immediate impact. The meta-reviewer suggests accepting this work as a poster to facilitate further refinement.
Decision: Accept (poster)