Differential Privacy Over Riemannian Manifolds
Authors: Matthew Reimherr
Karthik Bharath
Carlos J Soto
Venue: NeurIPS 2021 Poster (2021)
Keywords: Differential Privacy
Riemannian Manifolds
Fréchet Mean
Laplace Mechanism
K-Norm Mechanism

Abstract: In this work we consider the problem of releasing a differentially private statistical summary that resides on a Riemannian manifold.  We present an extension of the Laplace or K-norm mechanism that utilizes intrinsic distances and volumes on the manifold.  We also consider in detail the specific case where the summary is the Fr\'echet mean of data residing on a manifold.  We demonstrate that our mechanism is rate optimal and depends only on the dimension of the manifold, not on the dimension of any ambient space, while also showing how ignoring the manifold structure can decrease the utility of the sanitized summary.  We illustrate our framework in two examples of particular interest in statistics: the space of symmetric positive definite matrices, which is used for covariance matrices, and the sphere, which can be used as a space for modeling discrete distributions. 

Differential Privacy Over Riemannian Manifolds
Matthew Reimherr Department of Statistics Pennsylvania State University University Park, PA mreimherr@psu.cm edu
Karthik Bharath
School of Mathematical Sciences University of Nottingham
Nottingham, UK
Karthik haanbi..BBarrachhhottinnggnnn ac,
Carlos Soto Department of Statistics
Pennsylvania State University
University Park, PA cjs7363dpsu.ed edu
Abstract
In this work we consider the problem of releasing differentially private statistical summary that resides on Riemannian manifold. We present an extension of the Laplace or K-norm mechanism that utilizes intrinsic distances and volumes on the manifold. We also consider in detail the specific case where the summary is the Fréchet mean of data residing on a manifold. We demonstrate that our mechanism is rate optimal and depends only on the dimension of the manifold, not on the dimension of any ambient space, while also showing how ignoring the manifold structure can decrease the utility of the sanitized summary. We illustrate our framework in two examples of particular interest in statistics: the space of symmetric positive definite matrices, which is used for covariance matrices, and the sphere, which can be used space for modeling discrete distributions.
Introduction
Over the last decade we have seen a tremendous push for the development and application of methods in data privacy. This surge has been fueled by the production of large sophisticated datasets alongside increasingly complex data gathering technologies. One theme that has emerged with the proliferation of highly structured and dynamic data is the importance of exploiting underlying structures in the data or models to maximize utility while controlling disclosure risks. In this paper we consider the problem of achieving pure Differential Privacy, DP, when the statistical summary to be released takes values on a complete Riemannian manifold.
Riemannian manifolds used extensively in the analysis of data parameters that inherently nonlinear, meaning, either addition or scalar multiplication may cause the summary to leave the manifold, such operations spatio-temporal processes, covariance matrices, projections, rotations, compositional data, densities, and shapes. Traditional privacy approaches for handling such objects typically consist of utilizing an ambient or embedding space that is linear so that standard DP tools can be employed. For example, Karwa and Slavković [2016) considered the problem of releasing private degree sequences of graph which required them to project back onto a particular convex hull as post-processing step. Such an approach is natural starting point and reasonable long the space doesn't 't exhibit much curvature. However, there are several interrelated motivations for working with the manifolds directly. First, if one employs an ambient space (known as taking an extrinsic approach), then calculations such as the sensitivity may depend on the dimension of the ambient space, which will in turn impact
even well defined. Classic examples of such objects include
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

the utility of the private statistical summary. For example, minimax rates in DP typically scale polynomially in the dimension [e.g. |Hardt and Talwar 2010 Bun et al.] 2018 Kamath et al. 2019]. Second, the Whitney embedding theorem states that, in the worst case, to embed a manifold in Euclidean space requires a space that is twice the dimension of the manifold. Third, if the manifold exhibits substantial curvature, then even small distances in the ambient space may result in very large distances on the manifold. Lastly, the choice of the ambient space may be arbitrary and one would ideally prefer if this choice did not play a role in the resulting statistical analysis.
Related Literature: To the best of our knowledge, general manifolds have not been considered before in the DP literature. The closest works come from the literature on private covariance matrix estimation and principal components [Blum al. 2005 Awan et al. 2019 Amin et al., 2019 Kamath et al. 2019 Biswas et al. [2200] Wang and Xuj 2020J. While not always explicitly described in some works Wang et al. 2013 Wei et al. al.] these objects lie nonlinear manifolds, namely, the space of symmetric positive deñnite matrices (SPDM) and the space of projections matrices respectively. called the Stiefel manifold. For example, in Chaudhuri et al.] [2033] they consider the problem of generating synthetic PCA projection by using the matrix Bingham distribution, a distribution over the Stiefel manifold (Khatri and Mardia 1977. Hoff 2009). In contrast, producing private covariance matrix estimates usually involves adding noise in way that preserves symmetry, but does not use any deeper underlying manifold structure. A related problem comes from the literature on private manifold learning [Choromanska et al. [016)] Vepakomma et al. [022]] though this is entirely distinct from the present work, which assumes the underlying manifold is known, usually because of some physical constraints on the data or statistical summaries.
Contributions: In this paper we utilize tools from Differential Geometry that allow us to extend the Laplace mechanism for c-Differential Privacy to general Riemannian manifolds. Under this framework, we consider the problem of privately estimating the Fréchet mean of data lying on a d-dimensional manifold. We are able to bound the global sensitivity of the mean and provide bounds on the magnitude of the privacy noise, as measured using the distance on the manifold, that match the optimal rates derived in Euclidean spaces. However, we demonstrate the influence of curvature of the space in understanding the sensitivity of the mean, and how the situation becomes especially challenging on positively curved spaces. We conclude by providing two specific numerical examples that elucidate this phenomenon: the first considers data coming from the space of positive definite matrices equipped with geometry that results in negative curvature, while the second example considers data lying on the sphere, which has constant positive curvature.
Notation and Background
In this section we provide the basic notation, terminology, and mathematical concepts needed from differential geometry. For more detailed treatment of differential geometry and Shape Analysis there are many excellent classic texts, e.g.. Gallot et al. [1990), Lang 2002). Dryden [2014), Srivastava
and Klassen 2016
Lee 2018). while an overview of DP can be found in Dwork and Roth [2014).
Throughout the paper we let M denote a d-dimensional complete Riemannian manifold. For m E M, denote the corresponding tangent space as T, We assume M is equipped with Riemannian metric ().m))m m E M), which is collection of inner products over the tangent spaces MT : m E M) that vary smoothly in m.
Two quantities that will be used extensively in this work are that of the distance and volume induced from the Riemannian metric. Consider two points mi, m2 . and smooth path 7 [0, 1] - M such that 70) = my and 7(1) = m2. The derivative (t) represents the velocity of y as it passes through the point (t) and can thus be identified as element of the tangent space M. We
define the length of the curve as
I(7) : S( (1(t), (()))) dt.
The distance between my and mg is the infimum over all possible paths connecting the two points
p(m), m2) = inf I(y).
7=)(0)=m1 70)=m²
If this distance achieved by a particular path, 7, then we say that 7 is a geodesic. Geodesics generalize the concept of straight line to nonlinear spaces, and are thus natural tool to consider
2

---

when generalizing DP perturbation mechanisms. The distance p(:.-) defines a valid distance metric over M; we say that M is complete if is complete as a metric space. By the Hopf-Rinow Rinow theorem LLee 2018 Theorem 6.19], this is equivalent to saying that to every pair of points there exists minimizing geodesic, though if the points are far enough apart need not unique.
In the next section we will use the exponential map, expm T'M + M, which is means of moving between the manifold and tangent spaces. If there exists a unique geodesic, y, between between points (0) = m and 7(1) m2, then the exponential map is defined as the mapping expm, (0)) = m2. In other words, expm maps initial velocities to points on M through the use of geodesic curves. If the manifold is complete, then the exponential map is locally diffeomorphic, meaning that for any m E .M there exists an open neighborhood (m) of M that diffeomorphic to an open ball (0) centred at the origin of M. This ensures that the inverse expm : U, - (0) known as the evverse-xpponentie (also known as logarithm) map exists locally. The injectivity radius of m is the supremum of r - U, over all such radii r. The injectivity radius of M, denoted by inj.M, defined to be the infimum of the injectivity radii of all points m E .M.
The Riemannian metric can be used to define a notion of volume, called the Riemannian volume measure denoted as μ., which acts analogously to Lesbesgue measure in Euclidean space. To define the measure, it helps to employ chart, (U, 6). although the final definition will not depend on which chart we choose. Since Φ U - 6(U) C TR a homeomorphism, at each m E U the inverse Φ-1 induces a basis, azi...., Ora on M and corresponding dual basis dx ...., dxd on T'M', the dual space of M. Then the Riemannian volume form defined as Viggdx+ A... A dæd, where 9ij = (az, dz,)m and | is the absolute value of the determinant, which can be shown to be invariant to the choice of chart. This induces a volume over the set U and upon employing a partition of unity, one can define μ over the entire manifold M, equipped with the Borel o-algebra.
3 Manifold Perturbations and Differential Privacy
Denote the dataset as D (2....., Fn3 with the data coming from points z; collected from an arbitrary set X' We aim to release a statistical summary fDD which takes values on M. Defining differential privacy over a Riemannian manifold presents no major challenge since it is well defined concept over any measurable space [Wasserman and Zhou 2010 Awan et al.] (019). which includes Riemannian manifolds equipped with the Borel o-algebra. Denote the (random) sanitized version of f(D) as F(D). We can then define what it means for F(D) to satisfy c-D..
Definition 1. A family of randomized summaries, (J(D) E M D E X"), is said to be e- differentially private with >> O, if for any adjacent database D', denoted as D D', differing in only one record we have
P(((D) E E) A) SEP(((() A),
for any measurable set A.
In a similar fashion, we can extend the notion of sensitivity to Riemannian manifolds using the distance function. However, this definition is by no means canonical and intimately connected to the type of noise one intends use (Mirshani al. 2019]
Definition 2. A summary f is said to have a global sensitivity of A < oc, with respect to p(:))). if for any two adjacent databases D and D' we have
(((D),((D'))
With bounded sensitivity, it still isn't obvious how produce differentially private summary. In particular, we no longer have linear perturbations or classic noise mechanisms such as Laplace or Gaussian. However, the Riemannian structure allows us to use the volume measure as base measure, similar to the Lebesgue measure on Euclidean spaces. We can then define new distribution that can be viewed as a generalization of the Laplace distribution over manifolds [e.g. HHari et al. 2016 for SPDMJ. It is worth noting that this distribution is not equivalent to the multivariate Laplace appceee in
Euclidean settings, instead it is an instantiation of the K-norm distribution (Hardt and Talwar 2010
Definition 3. A probability measure P over M is called a Laplace distribution with with footpoint 1) E M and rate a > 0 if for any measurable set A we have
P(A) / Cyde e -lymm)) dp(m).
3

---

where 0 < Co < 30 is the normalizing constant and μ is the Riemannian volume measure over M.
Unlike with Euclidean distance, the normalizing constant might only be finite for certain values of a. The foot-point represents the center of the distribution but, in general, need not be equal to the mean of the distribution (which also might not exist). For data privacy, one often has to restrict the data or parameter space anyway, in which case the Laplace distribution can be restricted so that the normalizing constant, mean, etc are all finite and well defined. The advantage in using such a mechanism is that sensitivity can be readily transferred into differential privacy.
Theorem 1. Let f Xn + M be summary with global sensitivity A. Then the Laplace mechanism with footpoint f(D) and rate a 2 satisfies e-differential privacy. If the normalizing constant, Cojo does not depend on the footpoint, 1), then one can take o = D/C.
Proof. (Sketch) The proof follows from a direct verification via the triangle inequality.
In principle, it is possible to sample from the Laplace distribution using Markov Chain Monte Carlo (MCMC). One can start the chain at 7 and then make small proposed steps by randomly selecting a direction and radius the tangent space. The resulting tangent vector can be pushed to an element of M via the exponential map. Alternatively, if enough structure is known, as we illustrate in Section 5 one may be able to sample from the distribution directly or if the space is bounded then one can use rejection sampling.
An interesting alternative to our approach that is still inherently intrinsic is to instead generate the sanitised summary on a particular tangent space and then map it to the manifold using the exponential map. On the surface, this seems like reasonable idea, however there are some subtle technicalities that would have to be overcome. In particular, one has to choose which tangent space to work with. Ideally one would work with the tangent space at the summary of interest, but that isn't 't private. If another plane is used, then there is the chance for more serious distortions from the noise. Likely these issues could be overcome, but would require additional work.
4 Differentially Private Fréchet Means
As before, suppose the data consists of D = f.i,..., In), but now with x; E M. The sample Fréchet mean, I, is defined to be the global minimizer of the energy functional
n
Mar F2(x) = 2n Σ (xx,2;)
which is a natural generalization of the Euclidean mean manifolds. Conditions that ensure existence and uniqueness of J have been extensively studied since its inception in the 1970s (Karcher 1977 Kendall, 1990). Even when the mean is unique, the following example shows that the sensitivity need not decrease with the sample size, which produces sanitized estimates with low utility.
Example 1. Let 21,-.., Ty be points on the unit circle .M- = S = far E R2 ||>||| = 1} with arc-length distance p. represented as angles such that r; = a-
2mi = 1...., n 1 and x, = xy for
some i' E [n 1). Then minimizing F2 occurs when we take T = v.. So, we can make the mean any of the z; by shifting single point. If n is even, the furthest any two points can be is π and the resulting sensitivity is ग, which clearly does not decrease with n.
The above example illustrates that one must have some additional structure to ensure that the sample Fréchet mean as statistic is stable and that the sensitivity is properly decreasing with the sample size. The first requirement is that the sample Fréchet mean is unique; this imposes strong constraints on the spread of the data on M given by its curvature. Denote by (m) the open geodesic ball at m of radius in M. For a given dataset D with points in M we make the following assumption.
Assumption 1.
The data D C B, (mo) for some mg, where r < r == 1 min (injM, , -x-1/2) and 0 is upper bound on the sectional curvatures of M.
For flat and negatively curved manifolds, Assumption I only says that the data lies in some bounded ball. In that case k S and we can interpret x 1// to be +00. Furthermore, the injM can be arbitrarily large. Thus the radius of this ball only impacts the sensitivity, which is very common in
4

---

data privacy. However, it is, in general, difficult to relax Assumption for positively curved manifolds even when privacy isn't I concern. For example, suffices to use the slightly weaker assumption r < minfinjM, xx xx> } to ensure that (i) the closure B, (mo) is geodesically convex; (ii) exists and is unique; and (iii) I belongs to the closure of the convex hull of points in D [Afsari 2011]. For the unit sphere Sd-1 in Example I have injM = x and K 1, we require < \ so that dataset D lying within hemisphere on Sd-1 will have unique sample Fréchet mean only if D contains no point lying on the equator. However, we need the stronger Assumption to ensure that (ar, v) > (2r, y) is convex along geodesics for every x: and y inside B, (mo) required to determine the sensitivity of æ.
Le 2001 which is
In Theorem 2 we provide bound on the global sensitivity of the Fréchet mean. The bound depends on the sample size n, the radius r of the ball that contains the data, and a function h(r, k) which depends only on r and on the upper bound of the sectional curvatures of M. For flat negatively curved manifolds, we will see that h(r, k) = 1, which matches classical results for the Euclidean space, owing to the classical Hadamard-Carte theorem that states that a simply connected M with non-negative sectional curvatures is diffeomorphic to Rd, However, the situation is more subtle for positively eurved manifolds where h can no longer be ignored.
Theorem 2. Under Assumption | consider two dutasets D {ar..... En-1, 1 Fn) and D' (Z1..... In 1n-1, 1,,,,,,,, )'y) differing by only one element. If i and s' are the two sample Fréchet meuns of D and D' respectively, then
p(t,t)) 2r(2 - k)),k))
(rrK)){( 2r (tv/kooo(Vk2))
0; K 50
k)(r,K)
Proof. Consider the energy functionals Fg and F2 for the datasets D and D' with unique sample means E and H', respectively. Since M is complete the exponential map exp, T.M + M is surjective and under Assumption I the log map or inverse exponential map M 3 y + expx (v) e T.M is well-defined for every E (mo))
Here + p²(x, y) is twice continuously differentiable, and under Assumption D the function + p(., y) is strictly convex for all æ, E B, (mo) Karrhher 1977 Afsari [011]. Consider an are length parameterized, unit speed minimizing geodesic 7 between and x' such that r(0) = xb)) s' with b (() The composition, G2 == Fg y : b0, + R is now a twice continuously differential real-valued function with derivatives G2 and G2 and thus
(z(L) = (2) + ((,) = (aa))=p(a_=___0_ (')((t),,,
for some 0 S to S 6 since (0) 0.
To determine (2(4)), we need to calculate the second derivative of p(7(1o + 4)² evaluated at 6 = 0 and for an arbitrary q E (ma)), which equals
( d de
d² pl + 2), + 2p(7(to), 9) de ply +c), 13.4))
2
Let B, be the angle between (lo) and ár (f)) formed in T.M, where ag is minimizing geodesic from to ((o);; this implies that p((((to + +)), - (Vp(r(to), 9). ((to)) cos B... with V as the Riemannian gradient, since 4 ())( 1)1== = {p((,, a)) and y is unit-speed geodesic. As a consequence, with minimizing geodesics az from x;
7(to and corresponding angles Be..
d² Gz(to) dea Felr(to + c))
d² Σ cos" Br, + p(2, de plo + c), 20,
Note that if = = I; for any i, the angle 8z, is not well-defined, but regardless of the chosen path Oz. d² the contribution to the sum from the particular 2; will be one. The Hessian des p(>(to -),x;) of the distance function can be lower bounded using the Hessian comparison theorem [e.g. Lee 2018 Theorem 11.7] obtain
n cos? Br, + a(p(2, 2.), k) sin' Bz,)
G2((1) N
5

---

where
8 S/xcot( (Fo))
A. > 0:
a(s,
A = 0:
$ [x|] coth( v |k|s)
A < 0.
If > then (s, a(), s 1 and decreasing; the other hand if i. O, (s, + a(s, 2 and increasing. We hence have that
G2(10) 2 Mr,K) = 2r 2 /n2r) K > 0;
(I)
K K 0,
since for a(s, x) (2r)-1 and we choose 1/2 since it is effectively unconstrained in this setting. The lower bound (2(1n) thus depends whether M is positively non-negatively curved depending on the sign of x. This results in
(2(() M(,
(F.F')
(02(0) - G2))
h(r,
where 3. (2(b) = 0 since VF2(T') = 0. For any x E M, in normal coordinates, the gradients
Fx)(x) 1
exp2 (x:) + x
V22(x)
Σ exp + exp= (xxm)
belong to T.M. This leads to the desired result since
2r(2 - (h(r
p(a,z') S nh(r,
|exp (zn) exp (x
nh(rr K)
using Lemma the Supplemental based on Jacobi field estimates
Karcher 1977
In our next Theorem we provide a guarantee on the utility our mechanism. We demonstrate that, in general, the magnitude of the privacy noise added is O(r//ee) Classic results on c-DP [e.g. Hardt and Talwar 2010) in IRd typically do not calculate sensitivity based on a Euclidean ball, instead focusing on privatizing each coordinate separately, which case the optimal privacy noise (d ((n))))ne).. To reconcile the two, the classic rate can equivalently be thought of as calculating sensitivity using an foo ball. It is easy verify that it requires an & ball radius rvd to cover an foo ball of radius r, in which case the two rates agree, meaning that our mechanism is rate optimal.
Theorem 3. Let the Assumptions of hhold. Let E. denote a draw from the Laplace mechanism conditioned on being By Assume that and are such that - O. Then T is e-DP and furthermore
Z) =0
n2
Proof. First, ă conditioned on falling in B, (ma) guarantees the existence of the Laplace distribution (over (m())) since it clearly integrable. That 3 is DP follows from the same arguments as Theorem
Turning to our utility guarantee, first notice that was chosen such that there exists set A, C T such that the cxPm,, A, + B, (ma) is a diffeomorphism. Identifying T with Rd, we also have that A, ball centered with radius r (as measured using the inner product (mg)..
change-of vfriiaaaless exp... (7) H. implies that T has density equal to
f(v) F 1wll/
lol/o///// [J,]
with support on A,, where |Jal is the determinant of the Jacobian of exP This is not the K-norm distribution over Rd unless the Jacobian constant in Since the set A, compact, the determinant

---

of the Jacobian is bounded from above and from below (away from 0), we can find constants and C2. independent of o, satisfying
de l/-lo//a S Se-1o// |Jo1
S o2e 101//0
We can use this to bound the desired expected value
E. = T.o / lufee-lo//0 |ool du S
c1 /
e-lol/o du
o1le-lo1/0 du.
02
A.
A.
Using a change variables with u = o- v we
have that
Ep(T,z) < [ l-ul du
C20²
lu12e du. /
Arjo
A+/=
This, however, is simply /c1 multiplied by the expected squared norm of a Euclidean Laplace that is conditioned on falling within Arja. we remove the condition that the Laplace falls within Ar/o the value necessarily increases, thus we have that
620²
/ ---wu
l |u|2e-lu du.
E ETTT,
dus
R+
C1
Using a change of variables in both integrals to spherical coordinates and noting a = Orr/ne) as in Theorems D andd
2 we get that
C20² 2
l yotie-v dy c202d(d-1) =
d2
E Ep(
e dy
n2222
Our final Theorem focuses on the case of linear manifolds to highlight mathematically the benefit of constructing the privacy mechanism directly on the manifold as opposed to an ambient space and then projecting back onto the manifold. Practically, the variance the mechanism is inflated by factor of D/d where d and D are the dimensions of the manifold and ambient space respectively with d S D. Intuitively, the ambient space is of a higher dimension than the manifold, then one has to expend additional privacy budget to privatise the additional dimensions, which our approach avoids. Since the mechanism concentrates around a single point as the sample size grows (and thus one can single tangent space to parameterise the problem), more general manifolds, though for case of exposition we focus on the linear case.
should be able to extend this to
Theorem 4. Let M C RDD be d-dimensional linear subspace of RDD equipped with the Euclidean metric. Assume the ussumptions of Theorem hold. Let T. denote the private summary generated from the Laplace over R2 with scale o, in the sense of Desinition (equivalently, this is the K-norm mechanism with the E norm). Then
dDr n
BIPMTD =0
where PM is the projection operator onto M.
Proof. Choose { }D} as an orthonormal basis of D such that the matrix PM V is an orthogonal projector onto M, where V [UI,..., Fa] E R Dxd and VTV Ia. Let (:.)) be the usual inner product on IR" with norm || Note that Fn म + RRU, where R distributed Gamma D.1), U is uniform 8D-1 (i.e. (U,U) 1) independent of R, and x E M (see Supplemental 1.4 for details). Then
EIPMon - - P - E(R²) Σ EU
im1
Since U is uniform on the sphere, it follows that the vector ((U, v1 (U, vD) follows Dirichlet distribution with concentration parameters all equal 1. Thus, for each i, (U. is distributed as Beta(1, D 1). This completes the proof as
1 = (1))
PIPMã 2|I2 do (D D2) D
7

---

Examples
In this section we numerically explore two examples that are common in statistics. In the first example, consider the space of symmetric positive definite matrices (SPDM) equipped with the Rao-Fisher affine invariant metric, under which the space is a negatively curved manifold. In the second example we consider data lying on the sphere, which can be used model discrete distributions or compositional data, as an example of a positively curved manifold. In both cases demonstrate substantial gains in utility when privatizing the Fréchet mean using our proposed mechanism against using a more standard Fuclidean approach that utilizes an ambient space. Other examples of Riemannian manifolds that commonly arise in statisties include the Steifel manifold for PCA projections, quotient spaces for modeling shapes, and hyperbolic spaces for modelling phylogenetic structures. Simulations are done in Matlab desktop computer with Intel Xeon processor at 3.60GHz with 31.9 GB of RAM running Windows 10. Additional details on each example are also provided in the supplemental.
5.1 SPDM
Let F(A) denote the space of l: x k symmetric positive definite matrices. In addition to being used for modeling covariance matrices, this space is widely used in engineering of brain-computer interfaces
[Congedo et al. 2017), computer vision [Zheng et al. 2014), and radar signal processing [Arnaudon]
et al. 2013].
We consider P(k)) equipped with the Riemannian metric (v, u)p Tr(p upp'p)) known as the Rao-Fisher or Affine Invariant metric where u, u E T2,(() are symmetric matrices. The metric makes P(A)) into manifold with negative sectional curvature [e.g.. [Helgason] 2001). Under this metric exp,,() (v) = Exxp (p-1/2op-1/) 1/2) p1/² and exp, = g (q ppg 1/2)
1/2)/'1 g\/², where Exp and Log are matrix exponential and logarithm respectively. The (squared) distance between q, p E ((k) is given in closed form by (g. = Tr[Log(q-1/3) 1/2 1/23)_ these expressions are widely available [e.g., Hajm et al. [016 Said et al. 2017]. To calculate the Fréchet mean of sample we use gradient descent algorithm as proposed in Le [001] (Supplemental material 1.1).
We generate samples D = {.,,... In 1n-1, } from PP(k) using the Wishart distribution as discussed in the Supplemental material 1.2.1 In the first and second panels of Figure [ we show simulation results which illustrate Theorems and 3 and compare the utility of the EucTidean counterpart. In the first panel we illustrate the sensitivity by plotting (( for neighboring databases, as blue dots as well as the theoretical bound The blue line is the average distance at each sample size.
We compute the Fréchet mean 5 and then privatize the mean using two approaches: (i) we generate
the privatized mean by sampling using the Laplace distribution from Definition 3 defined directly on P(k) with footpoint ã using the algorithm in Hajri et al. [2016] (ii) we use the embedding of (P))
into the set of k x k symmetric matrices, isomorphic to I FT/+1 to represent Ā as vectorized matrix væch(i) in IR3 (i.e., & = 2) and obtain a privatized mean vech (Tg) by adding to vech(") ) a vector drawn from the standard Euclidean Laplace. Then Eg is obtained by reverting to the matrix representation, which is not guaranteed to stay in P(k) but is symmetric by construction.
In the second panel we plot the average, across repetitions, of the distances /vccc()) vech( (blue) and [)))) - vech(# [I (red). Since the Fuelidean summary need not belong to M, using the Fuclidean distance enables a common comparison between the two methods. The shaded regions around the lines correspond to 2SE, where SE is the standard error of the average distances.
Examining panel 2 in Figure I we see that our approach has better utility even when calculated using the Euclidean distance. Here, the ambient space approach does not increase the dimension of the statistic since P(k) and the space of symmetric matrices are of the same dimension, thus the gain in utility appears to be primarily due to respecting the geometry of the problem. Furthermore, as expected for smaller sample sizes, approach (ii) can produce summaries that are not positive definite, with about 25% not being in Plk) at sample sizes 20-40.
5.2 Spheres
Let S denote d-dimensional sphere of radius 6 1/2 parameterized such that the sectional curvature is constant > 0. Identifying the sphere as a subset of dd+1, the tangent space at p is T.SS%
8

---

109
Dirance
Dirance
10
10"
10
10"
100
230
300
400
500
10
103
230
300
400
500
10"
100
2000
400
500
100
200
303
500
Sample size
Sample siz0
Sample $220
9amp e 5220
Figure 1: For the first and second panel are for P(2), while the third and fourth for ST. First and third panel: The blue points are the manifold distance between the Fréchet means E and i' of D = {=1,- 2n-1, Zn and D' = {I1,.... 3f respectively. The blue line is the average distance at each sample size and the red line is the theoretical bound on the sensitivity from Theorem 2 Second and fourth panel: At each sample size generate several replicates (1000 for each P(2) and St) and compute the Fréchet mean I. We then separately privatize the Fréchet mean twice, first on the manifold which results in E and second embedding the mean onto Euclidean space, R in both cases, which results in 2 The blue bars represent the average of the Euclidean distances between and T with the bounds +2SE; the red bars represent the average of the Euclidean distances between I and Ee with the bounds 2SE. For further detail see sections 5.1 5.2 and the supplemental.
{u E Rd+1; (v.p) 0}. The exponential map, defined on all of T.S. given by expp(e) cos([|ol])y- - - -1/2 sin([/el])u/l /Ilel and ( = The inverse exponential map exp, S T,5%% is defined only within the ball of radius strictly smaller than x/2 around p and is given by exp,' (q) sin(e) (g cos(f)p) with q {p. (p). The corresponding distance function is p(p.9) 9) = A where = cos ((p. 9)) and p.q S.
In similar fashion Section 5. in the third and fourth panels of Figure [ we show simulation results which illustrate Theorems 2 and 3 and compare utility to its Euclidean counterpart. For our simulations fix d = and i 1. Consistent with Assumption on support of the data, choose a ball B, (ma) of radius r = 7/8 <r" = n/2 and take mn as the north pole. We generate random samples as shown in the Supplemental material I.3.1 The red line again corresponds to the theoretical bound from Theorem The (unique) Fréchet mean T is computed using a gradient descent algorithm.
In the last panel we compare utility of the privatized means, again obtained using two approaches: (i) exactly in approach (i) with SPDM: (ii) using the embedding of E into R3 (Cartesian coordinates) to represent & and obtaining a private Zg by adding to F draw from the Euclidean Laplace. We display the average Fuclidean distance between the mean and private mean +-2SE, where SE is the standard error of the distances at each sample size; we use 1000 replicates at each sample size. The blue band is obtained using approach (i) and the red band using approach (ii). While the contrast between (i) and (ii) is not as stark as with SPDM, our approach still produces about 15% less noise, with an average of 16.8% reduction in the smaller sample sizes and 12% reduction in the larger sample sizes. Furthermore, unlike in the SPDM case, the Euclidean private summary is never on the manifold since M a subset of pd++1 has measure zero
Conclusions and Future Work
In this paper we have demonstrated how to achieve pure differential privacy over Riemannian manifolds by relying on the intrinsic structure of the manifold instead of the structure induced by ligeer-dimensional ambient or embedding space. Practically, this ensures that the private summary preserves the same geometric properties the non-private one. Theorem 1astoremmshaer shows that our mechanism matches the known optimal rates for linear spaces for the Fréchet mean, while Theorem 4 Thighlights the benefit of the intrinsic approach in contrast projection-based ones using ambient space.
The benefits of directly working on the manifold come at the expense of more complicated mathematical and computational framework, challenges with which vary between different manifolds depending on availability of closed-form expressions for geometric quantities. Conversely, working in a linear ambient space is usually computationally simpler, although other issues abound: projecting onto the manifold may not be possible (e.g. SPDM under negative curvature), or the projection may lead to poor utility in high-curvature places the manifold.

---

As is well appreciated in the mathematics/statistisss literature, there are challenges that are unique to positively curved spaces, which we also encounter here. The central issue that the squared distance function need not be convex over large enough areas, and strong restrictions on the spread of the data are required to ensure that underlying summaries are unique and well defined. This phenomenon manifests in the form of a correction term h in our results, which impacts sensitivity of the statistics. Numerical illustrations in Section S that this is not just a technical oddity or gap in our proof' since our empirical sensitivity can be seen to be quite close to our theoretical bound.
As this is the first paper we are aware of in DP over general manifolds, there are clearly many research opportunities. A deeper exploration over positively curved spaces would be useful given how common they are in practice (e.g.. landmark shape spaces). A class of spaces unexplored in this paper, but well worth investigating, are Hadamard or (complete) CAT(() spaces. They are non- cossoiiiivlly curved metric spaces that need not be manifolds, on which geodesics and Fréchet means can be computed, and represent a natural geometric setting for graph and tree-structured data. One could also extend any number of privacy tools to manifolds including the Gaussian mechanism, exponential mechanism, objective perturbation, K-norm gradient mechanism, approximate DP, concentrated DP, and many others.
Acknowledgments and Disclosure of Funding
This work funded in part by NSF SES-1853209, the Simons Institute Berkeley and their 2019 program on Data Privacy to MR; and, NSF 2MS-2015374, NIH R37-CA214955 and EPSRC EP/V048104/I KB. We thank Huiling Le for helpful discussions.
References
B. Afsari. Riemannian L center of mass: existence, uniqueness and convexity. Proceedings of the American Mathematical Society, 139(2):655 673,, 2011.
K. Amin, T. Dick, A. Kulesza, A. M. Medina, and S. Vassilvitskii. Differentially private covariance estimation. In NeurlPS, pages 14190-14199, 2019.
M. Amaudon, F. Barbaresco, and Yang. Riemannian medians and means with applications to radar signal processing. IEEE Journal of Selected Topics in Signal Processing, 7(4):595-604, 2013.
J. Awan, A. Kenney, M. Reimherr, and A. Slavković. Benefits and pitfalls of the exponential mechanism with applications to hilbert spaces and functional pea. In International Conference on Machine Learning, pages 374-384. PMLR, 2019.
S. Biswas, Y. Dong, G. Kamath, and J. Ullman. Coinpress: Practical private mean and covariance estimation. Advances in Neural Information Processing Systems, 33, 2020.
A. Blum, C. Dwork, F. McSherry, and K. Nissim. Practical privacy: the SuLQ framework. In Proceedings of the twenty-fourth ACM SIGMOD-SIGACCTSSGARRT symposium on Principles of database systems, pages 128-138, 2005.
M. Bun, J. Ullman, and S. Vadhan. Fingerprinting codes and the price of approximate differential privacy. SIAM Journal on Computing, 47 2018.
K. Chaudhuri, A. D. Sarwate, and K. Sinha. near-optimal algorithm for differentialll- private principal components. Journal of Machine Learning Research, 14, 2013.
A. Choromanska, K. Choromanski. G. Jagannathan, and C. Monteleoni. Differentially- private learning of low dimensional manifolds. Theoretical Computer Science, 620:91-104, 2016.
M. Congedo, A. Barachant, and R. Bhatia. Riemannian geometry for bag-based brain-computer interfaces; primer and review. Brain-Computer Interfaces, 4(3):155-174, 2017.
I. Dryden. Shape analysis. Wiley StatsRef: Statistics Reference Online, 2014.
C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211-407 2014.
10

---

S. Gallot, D. Hulin, and J. Lafontaine. Riemannian geometry, volume 2. Springer, 1990.
H. Hajri, I. Ieaa, S. Said, L. Bombrun, and Y. Berthoumieu. Riemannian laplace distribution on the space of symmetric positive definite matrices. Entropy, 18(3)988, 2016.
M. Hardt and K. Talwar. On the geometry of differential privacy. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 705-714, 2010.
S. Helgason. Differential geometry, Lie groups, and symmetric spaces. American Mathematical Society, 2001.
P. D. Hoff. Simulation of the matrix bingham-von miscs-fisher distribution, with applications to multivariate and relational data. Journal of Computational and Graphical Statistics, 18(2):43--466, 2009.
G. Kamath, J. Li, V. Singhal, and J. Ullman. Privately learning high-dimensional distributions. In Conference on Learning Theory, pages 1853-1902. PMLR, 2019.
H. Karcher. Riemannian center of mass and mollifier smoothing. Communications on pure and applied mathematics, 30(5):509-544 1977.
V. Karwa and A. Slavković. Inference using noisy degrees: Differentially private 3-model and synthetic graphs. The Annals of Statistics, 44(1):87-112, 02 2016. doi: 10.1214/15-A0S1338 URL httpt:tttt.i.orrrgt/eeee/ otg:///oo.orr//////
W. S. Kendall. Probability, convexity, and harmonic maps with small image i: uniqueness and fine existence. Proceedings of the London Mathematical Society, 3(2):711-406, 1990.
C. Khatri and K. V. Mardia. The maises-fisher matrix distribution in orientation statistics. Journal of the Royal Statistical Society: Series B (Methodological), 39(1):95-106, 1977.
Lang. Introduction to differentiable manifolds. Springer Science & Business Media, 2002.
H. Le. Location Fréchet means with applications to shape spaces. Advances Applied Probability, 33(2):324-338, 2001.
J. M. Lee. Introduction to Riemannian manifolds. Springer, 2018.
A. Mirshani, M. Reimherr, and A. Slavković. Formal privacy for functional data with gaussian perturbations. In International Conference on Machine Learning. pages 4595-4604. 2019.
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.
A. Srivastava and E. P. Klassen. Functional and shape data analysis. Springer, 2016.
P. Vepakomma, J. Balla, and R. Raskar. Differentially private supervised manifold learning with applications like private image retrieval. arXiv preprint arXiv:2102. 10802, 2021.
D. Wang and Xu. Principal component analysis in the local differential privacy model. Theoretical Computer Science, 809:296-311 -126,,31222261 2020.
Y. Wang, X. Wu, and L. Wu. Differential privacy preserving spectral graph analysis. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 329-340. Springer, 2013.
L. Wasserman and S. Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):75--38, 2010.
L. Wei, A. D. Sarwate, J. Corander, A. Hero, and V. Tarokh. Analysis of a algorithm using random matrix theory. In 20/6 IEEE Global Conference Signal and Information Processing (GlobalStP), pages 1335-1339, IEEE, 2016.
pca
L. Zheng, G. Qiu, J. Huang, and J. Duan. Fast and accurate nearest neighbor search in the manifolds of symmetrie positive definite matrices. In 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3804-3808. IEEE, 2014.

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 6
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] The major assumptions are listed in Assumption while any additional assumptions are listed in Theorems and 3 needed.
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] All code and instructions provided
zipped folder.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] All training details are discussed in Section 5
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes] We plot the spread of repeated measurements Figure
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section [
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] See section
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material or as URL? [Yes]
All code is provided
zipped folder.
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "pz2MakF6lMl", "reviewer": "Reviewer_q1gp", "summary": "There are two main contributions in the paper:\n- First, the language of differential privacy is adapted to the framework of Riemannian manifolds. In particular, an adaption of the Laplace mechanism on manifolds is proposed.\n- Second, the Laplace mechanism is applied to produce differentially private Fréchet means on a manifold. The key result to do so is to provide a stability result for Fréchet means. The curvature of the manifold is shown to play a central role in this stability property.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The different ideas developed in this paper all feel very natural, while it seems they were missing from the literature so far. I particularly like the stability theorem (Theorem 2) that highlights the impact the geometry of the manifold (namely its curvature) has on the sensitivity of the Fréchet mean. What is gained by working directly on the manifold (instead of working in the ambient space) is also showcased by Theorems 3 and 4, both results being convincing. Even if the two numerical experiments are compelling, a supplementary experiment involving a non-synthetic dataset lying on a manifold would be welcome.\n\nMinor comments:\n\nl.93: is the supremum of... I do not understand this definition.\n\nl.133: define what the Laplace mechanism is\n\nl.145: to be A global minimizer \n\nl.151: I think it should be $x_i = 2\\pi i/(n-1)$ \n\nl.152: minimizing the ENERGY FUNCTIONAL $F_2$\n\nl.160: The data...\n\nl.162: \" it suffices for radius \"\n\nl.167: I could not find this assertion in [Le, 2001]\n\nl.173: depends only on $r$ and ON...\n\nl.181: for THE datasets\n\nl.183: \"under Assumption 1 the log map or inverse exponential map $y\\in M\\mapsto \\exp^{-1}(y)\\in T_xM$ is well-defined for every $x\\in M$\" -> the log map is defined on a geodesic ball.\n\nl.189: $G_2$ instead of $G$\n\nl.190: 0<t_0<b\n\nl.193: what is the definition of z?\n\nl.201: I think it should be $1$ for $\\kappa=0$.\n\nl.202: Replace with \"If $\\kappa>0$, the function $s\\mapsto a(s,\\kappa)$ is decreasing and upper bounded by $1$\" (or similar formulation)\n\nl.217: specify what is $\\sigma$ in the Laplace mechanism\n\nl.250: we want that the expected distance is larger than the quantity (and not a big O)\n\nl.256: I could not find the details in the supplementary material.\n\nl.264: THE Rao-Fisher metric", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "jhbFT7-dfdV", "reviewer": "Reviewer_62w6", "summary": "This paper is concerned with extending the Laplace mechanism (and its guarantees) beyond Euclidean spaces, in order to achieve pure differential privacy over manifolds without resorting to first embed the space into an Euclidean space. This seems like an interesting idea, which can lead to some savings in the parameters (by constant factors, see below) at the price of some computational issues and (as far as I can tell) a more restrictive assumption on the data (Assumption 1).\n\nThe authors specifically consider the question of bounding the sensitivity of the Frechet mean (Theorem 2), in order to compute privately (pure privacy) the Frechet mean of a dataset (Theorem 3) matching the corresponding guarantee for Euclidean spaces.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This generalization from Euclidean spaces to manifolds looks worth investigating to me, and the fact that in under the assumptions made the privacy overhead matches the special case of Euclidean spaces is appealing. However, I have some reservations about the paper, given that (besides the technical notions and proofs required to handle the more general setting) there isn't a lot of conceptually surprising content, as far as I can tell:\n- the generalizations of the Laplace mechanism, and sensitivity, are the direct and natural analogues of the Euclidean case\n- the savings compared to the naive embedding approach do not seem incredible (constant factors), at least for the example discussed (see below)\n- the computational aspects are evoked, but would gain to be explored in more detail\n- the future directions mentioned in ll 357-359 should, I believe, have been at least partly explored in this very paper: especially exponential and Gaussian mechanisms. Would the techniques required be that different?\n\nAs such, I don't believe the paper, as it stands, reaches the bar for NeurIPS, though it may be well suited for a less competitive venue.\n\n- How computationally easy is Assumption 1 to check (find the optimal r) given a manifold and a dataset?\n- If \"minimax rates in DP typically scale polynomially in the dimension\" and \"the Whitney embedding theorem states that, in the worst case, to embed a manifold in Euclidean space requires a space that is twice the dimension of the manifol\", then your approach here only saves constant factors, which is not a very strong motivation, especially given that you have to impose additional restricitions (Assumption 1) and may lose constant factors elsewhere (there are other motivations the authors put forward, but this saving is one of the ones put front and center, in p.1). \n\nMaybe look for a setting/estimation problem where the rate scales superpolynomially in the dimension? Then you would get a much clearer advantage.\n\nMinor points:\n\nTheorem 1: \"foot-point\" -> footpoint\n- Put the definition of h in Theorem 2 or closer to the statement theorem, not a page later. Also, maybe plot it to have a sense of its behavior? For instance, recalling in the theorem, after that, that sr sqrt(kappa) is < pi/2 by Assumption 1 might be helpful, since that's the thing that ensures h > 0\n\n====\nUpdated my score in view of the authors' response and reviewers' discussions.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I believe the authors did adequately address them. For a work of that theoretical nature, the societal impacts are very far down the line, and assessing them amounts (with a little hyperbole) to asking what Peano axioms might imply for the trolley problem.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "dJkHDxNI0fs", "reviewer": "Reviewer_f85U", "summary": "This paper studies differential privacy for the case of data and/or summary which consists of points in a Riemannian manifold.\nThe Laplace mechanism for DP is adapted to this case, basic results on its effectiveness are proven, and two examples are worked out.", "questions": "", "limitations": "", "rating": 9, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper studies differential privacy for the case of data and/or summary which consists of points in a Riemannian manifold.\nAfter pointing out that the standard definition generalizes, several simple and elegant results are proven:\n1. The Laplace mechanism for realizing DP generalizes straightforwardly.\n2. The sensitivity of the Frechet mean is bounded, so it can be used to produce a DP summary.\n3. The intrinsic definition is shown to work better than the definition by embedding the manifold.\n\nThen, two simple examples are studied numerically, one with negative curvature (symmetric positive definite matrices) and one with positive curvature (the sphere), illustrating the bounds and comparisons.\n\nThis is a very nice work and can also serve as an introduction to DP for non-experts (such as myself).\nI cannot judge the authors' claim that this is the first work on DP for manifolds, but granting it, \nthis seems quite suitable for NeurIPS.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Differential privacy is a topic which involves public purpose considerations.  \nBut the present work is abstract and does not directly touch on them.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "OVf66NBrhIC", "reviewer": "Reviewer_aauF", "summary": "This paper studies the problem of releases a differentially private statistic when the data and the statistic lie on a Riemannian manifold. They give a formulation of the Laplacian mechanism in this setting. They then consider the specific example of.a Frechet mean to display the benefits of using the manifold structure rather than adding noise in the ambient (higher dimensional) space, then projecting back to the manifold. \n\nThe authors show through specific examples and experiments the benefit of using the manifold structure rather than adding noise in the ambient space. As a first paper on the topic this seems like a nice proof of concept. I would have liked it to go deeper in discussing the complexity of actually sampling from the Laplace mechanism on a manifold. In particular, assumption 1 felt like it simplified the problem considerably.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Developing a toolbox for DP on manifolds is an interesting problem. There are many problems where some inherent structure is known (the authors give the examples of covariance matrices and discrete distributions) and previous papers in the DP literature have expended considerable effort to design algorithms with error scaling with the dimension of the problem, not the ambient dimension. The paper is largely well written (some additional comments on presentation can be found below). The authors do a good job of motivating DP on manifolds. \n\nAlthough there are papers in the DP literature that utilise the underlying manifold structure of a problem, I am not aware of any papers that attempt to give a general treatment or general purpose algorithms.\n\nOne of the main contributions is the definition of the Laplace distribution on a manifold. I thought this section needed more discussion. For example is the mean of this distribution the foot-print f(D)? What are the tails? What does it look like on different manifolds? \n\nMy biggest concern with the paper comes in assumption 1 in the Frechet mean section, which assumes all the data is contained in a set that is diffeomorphic to a compact subset of Euclidean space. The authors discuss why the radius r* is defined how it is, but I was still unsure about why simpler solutions are ineffective in this setting? In particular, why can’t one push the entire computation into the tangent plane at m_0 then just use the regular Laplace mechanism? This seems particularly pertinent given that the authors rely later on the fact that this assumption implies that the determinant of the Jacobian is a constant. \n\nThe baseline comparisons in the experiments seem a little strange since adding noise in the ambient space is not a state of the art DP algorithm for these problems.\n\n\n==== Minor Comments\n\nWhile I understand that an introduction to manifolds is outside the scope of this paper, I think the readership could be broadened by adding a simple graphic explaining the tangent plane, exponential map, geodesics and Riemannian volume intuitively. \n\nIt was a little unclear to me when reading assumption 1 whether (there exists r and m_0 such that for all databases D, D \\subset B_r(m_0)) or (for all databases D, there exists r and m_0…)\n\nSomething seems amiss about the second sentence of the proof of Theorem 2. Assumption 1 doesn’t seem to imply anything about the manifold itself.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not see any negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not have any ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "1E9wVSt0A2k", "reviewer": "Reviewer_MJ89", "summary": "In this paper, the authors consider the problem of releasing a differentially private statistical summary that resides on a Remannian manifold. They present an extension of the Laplace or K-norm mechanism that utilizes intrinsic distances and volumes on the manifold.", "questions": "", "limitations": "", "rating": 9, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "They consider in detail the specific case where the summary is the Fr\\'echet mean of data residing on a manifold and demonstrate that the mechanism is rate optimal and depends only on the dimension of the manifold, not on the dimension of any ambient space, while also showing how ignoring the manifold structure can decrease the utility of the sanitized summary.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. I think this paper is good.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work studies the question of extending private mechanisms to the case when the output is known to lie on a manifold in R^d. A natural approach in such settings is to add noise as if the output was in R^d, and then project back to the manifold. The authors propose a different noise mechanism that lives on the manifold and can be potentially better in certain settings.
The reviewers had several useful comments that the authors will do well to address. Some of the discussion in the rebuttal helped clarify the paper's contribution and including some of that in the paper will help improve the paper.
I think the paper pushes the research in DP mechanisms forward in an potentially fruitful direction and I recommend accepting it.
Decision: Accept (Poster)