Shape And Structure Preserving Differential Privacy
Authors: Carlos J Soto
Karthik Bharath
Matthew Reimherr
Aleksandra Slavkovic
Venue: NeurIPS 2022 Accept (2022)
Keywords: differential privacy
shape analysis
manifolds

Abstract: It is common for data structures such as images and shapes of 2D objects to be represented as points on a manifold. The utility of a mechanism to produce sanitized differentially private estimates from such data is intimately linked to how compatible it is with the underlying structure and geometry of the space. In particular, as recently shown, utility of the Laplace mechanism on a positively curved manifold, such as Kendall’s 2D shape space, is significantly influenced by the curvature. Focusing on the problem of sanitizing the Fr\'echet mean of a sample of points on a manifold, we exploit the characterization of the mean as the minimizer of an objective function comprised of the sum of squared distances and develop a K-norm gradient mechanism on Riemannian manifolds that favors values that produce gradients close to the the zero of the objective function. For the case of positively curved manifolds, we describe how using the gradient of the squared distance function offers better control over sensitivity than the Laplace mechanism, and demonstrate this numerically on a dataset of shapes of corpus callosa. Further illustrations of the mechanism’s utility on a sphere and the manifold of symmetric positive definite matrices are also presented.

Shape And Structure Preserving Differential Privacy
Carlos Soto Department of Statistics Pennsylvania State University
Karthik Bharath
School of Mathematical Sciences University of Nottingham Nottingham, UK Karthik haaaai..Baaaahhhottighaaaa ac. uk
University Park, PA cjs73638psu, edu
Matthew Reimherr Department of Statistics Pennsylvania State University University Park, PA mreinherr@psu.co edu
Aleksandra Slavkovic
Department of Statistics Pennsylvania State University
University Park, PA sesa@psu. edu
Abstract
It is common for data structures such as images and shapes of 2D objects to be represented points on a manifold. The utility of a mechanism to produce sanitized differentially private estimates from such data is intimately linked to how compatible it with the underlying structure and geometry of the space. particular, as recently shown, utility of the Laplace mechanism on positively curved manifold, such as Kendall's 2D shape space, is significantly influenced by the curvature. Focusing on the problem of sanitizing the Fréchet mean of a sample of points on a manifold, we exploit the characterisation of the mean as the minimizer of an objective function comprised of the sum of squared distances and develop K-norm gradient mechanism on Riemannian manifolds that favors values that produce gradients close to the the zero of the objective function. For the case positively curved manifolds, we describe how using the gradient of the squared distance function offers better control over sensitivity than the Laplace mechanism, and demonstrate this numerically on a dataset of shapes of corpus callosa. Further illustrations of the mechanism's 's utility sphere and the manifold of symmetric positive definite matrices are also presented.
Introduction
The amount of publicly available data has increased exponentially over the past decade and alongside with it the need for data privacy has emerged. As data gets increasingly more complex from scalar values to data on nonlinear manifolds, such as images, shapes and covariance matrices, there is need for data privacy algorithms to adapt to the nonlinearity in, and preserve the geometric structure of, the data or parameter space. Intuitively, when the geometry of the manifold significantly influences sensitivity bounds through curvature-dependent terms, one would expect structure- preserving privacy mechanism developed directly on manifolds have better utility than Fuclidean counterpart on higher-dimensional ambient spaces within which the manifold is embedded. This was observed in recent work on a Laplace mechanism on manifolds [Reimherr et al. 2021]. and especially for manifolds with positive curvature.
Apart from spherical, directional, data, an archetypal example of data on a positively curved manifold arises in statistical shape analysis of planar configurations representing 2D objects; the Kendall shape space of 2D points [Kendall] 1984] modulo shape- preppeeiner similarity transformations (e.g., rotations) is a Riemannian manifold with positive curvature. It is evident in this setting that
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the utility of a privacy mechanism will depend on how well it is compatible with shape preserving transformations of the data sanitize versions of shape summary of a 2D image of bird should "look' like a bird, impervious to (global) rotation, scaling and translation.
prrserine mechanisms within specific contexts have been considered before; see, for example et al. [2016] concerning covariance matrices; [mtiaz and Sarwate [2018) 2016). Gilad
Bachrach and Gonen 2017]. Awan et al. [2019], Chaudhuri et al. [2013] Biswas et al. [220 for
private principal component analysis; and Sheffee [2015] for private linear regression. A general structure- preetrrving Laplace mechanism on manifolds was considered by Reimherr et al. 2021 in
Awan and Slavković (202T) the relationship between the data space and the sensitivity was examined in sufficient generality, and a general Gaussian mechanism on Riemmanian manifolds for approximate differential privacy was considered by Han et al. (2022). However, research on privatizing shape summaries with theoretical guarantees is conspicuous in its absence within the privacy literature; the most relevant one we have found comes from computer vision which produces random faces but offers no differentially private guarantees [Karras et al. 2019].
The two-fold motivation for our paper is to a develop a privacy mechanism for statistical shape analysis. and more generally for data on manifolds, that compatible with the geometry of the underlying space, and further, offers better control on how the curvature influences global sensitivity bounds. To this end, our main contributions are as follows.
1. We develop an extension of the K-norm Gradient Mechanism (KNG) on Rd Reiimeerr and Awan 2019] for producing sanitized private estimates under the pure differential privacy framework to the setting of Riemannian manifolds, with a focus on mean estimation.
2. We derive a curvature-dependee of positively curved manifolds is smaller than the corresponding one arising from a recently proposed Laplace mechanism [Reimherr et al., 2021]. Our numerical examples verify that the KNG mechanism on manifolds shares the powerful utility of its counterpart on R and this is is tied to the curvature of the manifold and not to the dimension of the ambient space.
upper bound on global sensitivity, which for the important case
3. We introduce the first, to our knowledge, differentially private shape analysis under Kendall's
2D shape space framework, and favorably compare its performance to mechanisms designed for the higher-dimensional ambient space (and not directly on the manifold) on a dataset of corpus callosa obtained from MR images.
2 Background
In this section we introduce the necessary tools from differential geometry and differential privacy as well as the notation for this paper. For a thorough exposition of differential geometry and shape analysis we refer to Do Carmo| [1922], Srivastava and Klassen (2016) and for DP we refer to Dwork and Roth [2014].
2.1 Differential geometry
Let M be complete, connected Riemannian manifold of dimension d. Denote by M the tangent space at each point m E MM and by TM = {TmM : m E M) the collection of tangent spaces, known as the tangent bundle. On the tangent space T at each point m. we can define an inner product (., +)m M x T - IR with induced norm || mm the collection (6, m E .M} referred to as a Riemannian metric. The Riemannian metric varies smoothly along the manifold and allows us to measure distances, volumes, and angles.
For curve, path, [0, 1] + M, the vector a' (t) is its instantaneous velocity, and its length T()) is the value for (1)) 1/2 dt. A curve a is said to be arc-length parameterised if (oa'(())la = 1 and thus ((a()), atto)) to. Geodesic curves are those with zero acceleration for all t. The distance p between two points p and q is the length of the shortest path, a segment of a geodesic curve connecting the two known the minimal geodesic:
p(p.g) 9) = inf(Laa))a [0, 1] + (0) p, a1) q)- Given a point p and a geodesic a with (0) = p, a cut point of p is defined as the point (lo)) such that or is minimal geodesic on the interval 00, (o] but fails to be for 1. >> 4o. The set of all cut points of geodesics starting at p is its cut locus. The injectivity radius of p is the distance to its cut locus, and the injectivity radius inj M of M is the infimum of the injectivity radii of all points in M.

---

The next two tools are necessary for moving on the manifold, moving to and from the tangent spaces, and are particularly useful for sampling from distributions on manifolds, For geodesic a starting at p with initial velocity the exponential map exp(p. TT. - M is defined as exp(p, u) = a(1). From the Hopf-Rinow theorem, on a complete manifold the exponential map is surjective. On an open ball around the origin in M it is diffeomorphism onto its image outside of the cut locus of and a well-defined inverse exp (p. -) :M + T.M exists, known as the inverse exponential or logarithm map, that maps a point on M outside of the cut locus of p to T,M; thus for any outside of the cut locus of p. p(p,
exp -p (p:g)llp-
There are many notions of curvature of Riemannian manifold. We will mainly be concerned with sectional curvature at point p, defined to be the Gaussian curvature p of the two-dimensional surface swept out by the set of all geodesics starting at p with initial velocities lying in the two- dimensional subspace of Tp. M. spanned by two linear independent vectors.
Further, volumes of sets can be computed using the Riemannian volume form dp. local coordinates, the coordinate-independent Riemannian volume form defined as /det(g)d,; A dæ. A dr where 9ij (0z; 0r2) ) is the Riemannian metric tensor. A vector field on M is a differentiable mapping M -> TMM that assigns to each point m on M a tangent vector in M. Suppose we have smooth function h defined over M. the gradient Vh of h is the vector field defined by the relationship (Vh(p), u), (h) for p E M and v T.M.
2.2 Differential privaey
Let D = (-1,.... ,n C M denote a dataset of size n. In several statistical and machine learning problems, one of the most popular tools for releasing a sanitized version of minimizer
i argmax (x; D)
of utility function U over M is the exponential mechanism introduced by McSherry and Talwar 2007). based on density
[a;; D) x exp (o-' D)},
where the scale or rate parameter a is chosen to achieve desired level privacy and accounts for the sensitivity of U. If M is the Euclidean space, the density is with respect to the Lebesgue measure, and for finite or countable M, it is with respect to the counting measure.
A modification of the exponential mechanism is the K-norm Gradient Mechanism (KNG) introduced by Reeimherr and Awan [019], which turns out to have better utility quite generally. The idea is that the maximizer of Uz; D) is also the point at which its gradient is zero. On Riemannian manifold M, a KNG mechanism can be constructed using the gradient vector field VU (x; D), where the gradient is defined with respect to the Riemannian metric, with the (unnormalised) density
f(; D) x exp(-o-\I|VU
defined with respect to the volume measure [Reimherr et al. 2021), where || lla refers to the norm with respect to Riemannian metric at not be confused with the subscript k: as in k-norm. For general manifolds M, conditions on the sectional curvatures are typically needed to ensure that density is integrable with a finite normalizing constant. Under such conditions we can introduce definition of differential privacy similar to that of Blum et al. 20055.
Definition 1. For O, privacy mechanism satisfies d-differential privacy (pure differential
privacy, c-DP) if for any pair of adjacent databases D and D', denoted D', we have that
1 f(x; D)du S f(x;
for any measurable set S M.
To determine the rate parameter for the KNG mechanism, needs to quantify the robustness sensitivity, of the norm of gradient vector field for adjacent databases. Theorem 1. If for all neighboring D D' and almost all have
(v; D) (x; D' S A, then one can take a = 2A/e so that the KNG mechanism will be eDDP. Here A referred to as the global sensitivity.
3

---

The proof of Theorem follows directly from an application of the triangle inequality. The global sensitivity plays a crucial role determining the behavior of KNG about the optimizer of U. Thus far, U has been generic utility function however consideration needs to be taken for cases when U does not have global optimizer.
Differentially private Fréchet mean estimation theory
Possibly the most fundamental summary statistic is the average or mean. In a Euclidean setting, the mean has a closed form expression, which for general manifolds is rarely the case. Generalizing the notion of the Euclidean mean, the Fréchet mean defined as the minimizer of the variance functional
D) M R,, F)
Σ p(x,, 2m
1
where p is the Riemannian distance. In general, the minimizer may not exist, and may not be unique when it docs. Study of conditions that ensure existence and uniqueness has long history (see for e.g.. Karcher [977) and Afsari (2011), and we thus take some necessary precautions outlined in Assumption
Assumption 1. The dataset D C. Br(po), a geodesic ball centered at Po with finite radius with r << min M. 3 Kmmax) and Emax is an upper bound on the sectional curvatures of M.
For non-positively curved M, -1/2 is interpreted to,, and Assumption states that the data D must be bounded. That is, the data can lie a ball of any arbitrary size as long as we know how large the ball is as this directly affects the global sensitivity. The weaker requirement
1/2 min M, =xml/2) suffices to ensure existence and uniqueness of the Fréchet mean. However, the stronger Assumption 1 is required to ensure that (z, 3) + (2, y) is convex along geodesics (geodesically convex) within (po) Le [001]; for example, p² convex when restricted to a ball of radius smaller than и/ /4 on unit spheres since Kmax 1. For p² to be strong geodesically convex, an additional lower bound on sectional curvatures of M required (see Lemma
For mean estimation a natural utility function is Uz; D) = F D). The KNG mechanism makes use of the gradient of (x; D) at x and hence the (Riemannian) gradient of - Far; D), which in-turn is linked to the gradient of square-distance function æ + p(z;, 2 for fixed v;. Under Assumption 1, each v; lies within the injectivity radius of x. and the gradient Vp(a;, x)2 exp 1xx zz). Thus
VF(x;) = Σ exp (x,
The KNG mechanism then samples from the density (with respect the volume measure)
f(x; D) x exp
on Σ exp (x, x.;)
release a private statistical summary of the mean; note that when restricted to an open ball as per Assumption I the density f has finite normalising constant that depends on a.
In Theorem estimation on Riemannian manifolds. The bound is curvature-dependent in the sense that it depends on the radius of the ball in which the data lies, the sample size n, and function of r and Kmax- Specifically, the bound is equivalent to the bound obtained for Euclidean spaces for non-positively curved M but inflated for positively curved M.
provide bound for the the global sensitivity of the KNG mechanism for mean
Theorem 2. Under Assumption 7 let D (21, Fn and D' = (111, ... ,.h) be adjacent datasets. Then
Ind
(x; (U)x:'')l= 2r(2 Mmaxe (2r, kmmx))
where
n
hmax (s, kmax) == 8 8y/tmmax cot(s (oot(&//rmass (imax))
Kmax > 0
(I)
1,
Kmax S 0

---

Proof. For two adjacent databases D ~ D' that, without loss of generality, differ in the last element we have that
- [VF((;; - V (2; D') - llexp -xx xn) - exp ' 2nlll
exp
2r /mmx (2r, kimax))
based on Jacobi field estimates from Karcher 1977 see also (Reimherr et al. 2021, Lemma 1]. L
Remark 1.
For the Laplace mechanism M with density fa: D) e p((.m) for fixed point 1,.
whenever is chosen as per Assumption I the magnitude of inflation of global sensitivity due to
curvature was shown to be 2r(2 Amax (2r, (Kmax) ()
kmma)) in Reimherr et al. [2021).
The upper bound obtained by the KNG mechanism is thus strictly smaller for positively curved spaces since Mmax (2r, kmmax) < in experiments (see 4.1)) this difference in sensitivity appears to result in better utility. Although the densities for the KNG and the Laplace are not the same, they related the norm of vector in T. when r I. the Fréchet mean, since p(a, Ø) = onto M: the other hand, the KNG density uses the norm of the sample mean of data {ri} when projected onto T.M.
Il., the Laplace density uses the norm of the Fréchet mean I when projected
Our next theorem shows that the utility of KNG manifolds, measured by the intrinsic distance p( Ø) matches the optimal rate ((d/ne) )e) as in Euclidean space. For the theorem however we require the following Lemma, proof of which is available in the Supplemental materials.
Lemma 1. In addition to Assumption 7 assume that there exists Kmin E IR that lower bounds the sectional curvatures of M. Denote by the Fréchet mean of D. For every x (po)..
Byaxx (2r, Kmmax (( S (IV D) S Amin (2r, Kunin ((T,
where
Komin coth(s
(Fmial), Emin < 0
Nyin (s, Femin)
(2)
1,
Emin 2 0
Theorem 3. Assume the setting Lemma 7
Let ā denote a draw from the KNG mechanism restricted to B, (po), and & be the unique global optimizer of (x; D). We have that
[p({,,)) 0 d²
n2222
Proof. Recall that under Assumption malizing constant Cp!. Then
I f(x; D) = C-1 exp (-o-1 D) for finite nor-
C. 2
exp
{ o- -
(2r, Kmii (min)p(z, du(x),
B,(pa)
which due to Lemma results in the upper bound
E [p(t,))7] < SB.( pla,, B22e & tome (2r (2 du(xx)
SB.(ro) e & (2r Momm (0( (11(x)
2 MinjM, there exists unique Uz E exp exp-'(a (po)) B2)( such that U. exp- x), where B2r {r T&M : ||m|| < 2r} is the open ball of radius 2r centred at the origin in M. Denote by S the bounded subset exp (z. (po)) ) n B2r (ø) of T&M with
Since <
compact closure. With respect to the pushforward of du on to T.M under the inverse exponential map at H. the ratio in 33 equals
Ss. |l le Aman (2r la exp((..))
Js. Amii (2r, (mm)) li,, llx d(u exp(X, ()))
The induced measure d(u o exp(x. )) on T, can be extended to Rdd by settings its value on the complement of S₂ to be zero. It is then absolutely continuous with respect to the Lebesgue measure
5

---

yå on I' with a Jacobian determinant uniformly bounded above and below, respectively, by constants Cj and C2 on (the closure) of Sg. This ensures that the above ratio upper bounded by
c1 Sa |/uel : home (2r, (2r, II dd(wx)
Sga fgae- Rimin (2ri II dd(())
which, with a change of variables and using spherical coordinates, equals
C1 Muin (2r, Fomin)
[o -d za-le (e-le=ax(2))
Io e =d\()= =0 d²
C2 1max (2r, Emax)) )a
n2
since the curvature- curvature-dependent dependent terms Namin (2r, Nimin) and hmax (2r, Kmax) ) defined in ① and (2)
both positive and finite under Assumption [ σ is as in Theorems and 2 and the integrals in the numerator and denominator equal (d 1)1 and (d 1)1, respectively.
4 Examples
In this Section, we consider two simulated examples and a real data example on 2D shapes. For the former, we consider the positively curved unit d-sphere and the of symmetric positive definite matrices (SPDM), which when equipped with an affine invariant metric is negatively curved. Manifold valued data naturally emerges in statistical applications such as with SPDM matrices in computer vision Caseiro et al. [2012] and brain diffusion tensor data Niethammer et al. (2006), discrete distributions can be modeled on sphere, in network analysis Ginestet et [2017] for instance, and
we refer to Younes 2012) Kimmel [2003] as references with a more complete overview.
In each scenario sample from KNG via Metropolis- Heetropoli-Haasinnss. Monte Carlo Markov Chain method. This sampling method estimates our target distribution KNG and can incur a privacy loss. That is, KNG is an instantiation of the exponential mechanism and sampling from such mechanism via MCMC produces approximate DP samples rather than pure DP samples [hhnn and Yu (2013). Wang et al. 2015). The size of this cost is function of the chain length, however, and decreases to zero at a geometric rate, so sampling must be done in a careful manner. An exact sampler would be ideal, however even for some cases of well-behaved distributions sampling is not so simple [Seeman ctt al. [2021]. This issue is limitation of this work and we leave this as an open problem.
4.1 Spheres
Let St denote the d-dimensional sphere with radius k 11/2 The sphere equipped with the induced metric from Rd+1, the canonical metric, has constant positive curvature k. The tangent space at p Sy is then T. = (v E RR++1 p) 0). The exponential map, defined on all of T T, is given by exp(p, v) = cos([|u]])p + 1/2 sin((l//])//
and exp(p, 0) = p. The set of points at distance least from p constitutes its cut locus, which then is the singleton {-p]. With
0 = p(p. 9) = cos ((p. g) the inverse exponential map exp (p, q) = ((sin())) - (q cos(()p)) at is hence defined only within the open ball around p with radius π / 122)
Next, we consider the utility of KNG on a manifold and compare it to other sanitization techniques. We generate random samples D from S and compute the Fréchet mean ã. both as described in the Supplemental material. We set 1 and sanitize F with three separate methods; first with the proposed method KNG on manifolds to produce FKNG. NG. second with the Laplace on manifolds as in Reimherr et al. [2021] to produce æ, and lastly embedding F into R3 and privatizing with the Euclidean Laplace to produce Tg. The latter almost surely will not be on the sphere, however, since the privacy guarantees are invariant to post-processing, project the estimate back onto the sphere by normalizing as Eg + žg/ ||
We compute several such replicates at different sample sizes and display the utility comparison in the first (left) panel of [igure where the utility measured using the average Euclidean distance | ž|| such that ă is a the respective sanitized estimate. We see that adding noise in the ambient space with the Euclidean Laplace adds the most noise, which may be attributed to the need to sanitize over an extra dimension. After post-processing F by projecting onto the sphere, the Euclidean Laplace mechanism does have better utility than its manifold counterpart, but this is not unexpected since the sensitivity of the manifold Laplace for positively curved manifolds is inflated compared to

---

10
100
Euclidean Laplace
Euclddean Laplace
Eulidean Distance
Proj Euclidean Laplace
Eulclidean Distance
Manifold Laplace
Manifold Laplace
Manifold KNG
Manifold KNG
1
10
100
200
300
400
500
50
100
150
200
Sample size
Sample size
Figure 1: Utility measured using average Euclidean distance between the Fréchet mean ă and its sanitized version ă, when M is the unit sphere S in two dimensions (left) and l SPD matrices P(k) (right), under the following frameworks: (i) Manifold KNG; (ii) Euclidean Laplace by embedding into the ambient space: (iii) Manifold Laplace on the manifold; and additionally, with (iv) Projected Euclidean Laplace for the unit sphere. For the Euclidean Laplace H was embedded into R& for Sf and within k x & symmetric matrices for P(k).. For each sample size, 10000 replicates were used for S7. whereas 500 were used for P(k)). Shaded regions represent the average distance +2SE, where the Euclidean distance for ((k) is [|vech()) - vech(2)]|.
the Euclidean rate of 2r/n /n Reimherr et al. [022 Lastly, our proposed mechanism has the best utility in this comparison which may attributed its sensitivity being strictly less than the sensitivity of the Laplace on the manifold for positively curved manifolds. Further, our approach will always produce private summary which is on the manifold and does not require any post-processing.
4.2 Symmetric positive-definite matrices
Denote by PP()) the k(k + 11/2-dimensional manifold of A k symmetric positive-definite matrices equipped with the affine-invariant Rao-Fisher metric (v, u)p = Tr(p-tup v). where u,u E (,,P(k) Sym, are symmetric matrices. With this Riemannian metric IP(k) has negative sectional curvature everywhere with exponential map exp(p, 2) = px/ (p-1/2up-1//) p1/² and globally defined inverse exponential map exp=t(4,2) = = g//2 (q- (1-1/2pq-11 1 /2/2, where Exp(-) and Log(-) ) are the matrix exponential and logarithm, respectively, The distance between and p in ((a) thus p(g, p) = || exp (q,
11/2pq 1/23//////
For the simulations we set k = 2. We generate random samples D C P(k) by sampling from the Wishart distribution as discussed in the Supplemental materials. We compute the Fréchet mean and samitize it with three separate approaches: (i) we generate a private mean ~ NG by sanitizing on P(k) using the proposed approach KNG, (ii) we generate a private mean H on P(k) with the Laplace distribution as in Reiimeer et al. (22TT) Hajri et al. (2016), and (iii) we embed F into Sym: the space of symmetric matrices, represent F as vector vech( E R sanitize by sampling from the Euclidean Laplace to produce vech(@ ())), and lastly we revert the vectorization to obtain gg. There is no guarantee that Tg will remain in (P) and further without a unique projection to P(k) since is an open cone within IR (k++1)/2
Similarly to Section 4.1 in the second panel of Figure Twe we display an average utility comparison of the privatization techniques over 500 replicates with respect the distance ||vech()) - vech(ā)) where 7 is the sanitized estimate corresponding to one of the three approaches. We see that our approach has better utility compared the Euclidean approach and comparable utility the Laplace on P(k). The latter is not entirely surprising since the Laplace is equivalent to KNG for mean estimation in Euclidean space (Reimherr and Awan 2019). J. Sampling from the Laplace on P(k) is fairly simple since it was thoroughly studied by Hajri et al. (2016) and has nearly a closed form sampler; sampling from KNG on IP(k) however not as straightforward and we employed an Metropolis-Hasting algorithm which may account for its inconsistent behavior compared to the Laplace. However, our proposed method has better utility than the Fuclidean approach, which designed on the higher- dimensioi ambient space.
7

---

4.3 Kendall's 2D shape space
Statistical shape analysis is relatively recent field dating back to the seminal paper by TTompson and Thompson [9422] where shapes of animals, such as fish, were shown to differ in geometric trans- formations such as shear. Since this conception there have been many branches of shape analysis that have arisen such as Kendall's shape space [Kendall 1984). large deformation diffcomorphic metric mapping (LDDMM) [Grenander and Miller 2007]. and clastic shape analysis (Srivastava and Klassen 2016]. No matter the choice, shape analysis has demonstrated to be widely applicable the medical field (ERCAN et al. [002)) [i et al. (2014)), computer vision [Jimenez et al. 2000 Sharon
and Mumford 2006], and functional data analysis (Harris et al.] [02T]. [Zhang and Srivastava 2020D.
By "shape" of an object in two dimensions, we refer to the intrinsic geometric property of set of points on the plane (representing the object) that remains unchanged under similarity transformations such as translation, rotation and scale K (1984), and additionally on reparameterisations if an outline curve representation is used Srivastava and Klassen (2016). Of the many areas of shape analysis available (for c.g., the theory of deformable templates Trouvé and Younes| 2005) and Large deformation diffcomorphic metric mapping [Grenander and Miller (007]) we consider the Kendall shape space of woodimmenioonal landmark configurations Kendall 1984].
Consider a set x = {2,} E C* of labelled l points on a 2D object, known as landmarks, in the complex plane. If the object has been extracted from a densely sampled outline curve (for e.g., when extracted/segmented from 2D image), then the parameterisation of the curve induces the labelling through an ordering of the points. Labelling thus establishes correspondence between points on different objects, and is considered to be fixed.
The shape of x is what remains once translation, scaling and rotation variabilities are removed or d accounted for. Translation is removed by by transforming - t - Ij resulting in reduced space of the complex (k- - 1) dimensional hyperplane = far E Ch 1ol Σソ = 0}. Scaling and rotation of æ amounts to multiplying by a complex number re where r is the scaling factor and @ is the angle of rotation. The shape of x then can be considered the curve (- T, x] 9 O + e on the complex unit (k= 1)-dimensional sphere C in C, where u = /|= E C (or the real sphere of dimension 2k- - 3), || = Va*x and x² the complex conjugate of The shape space is thus identified with the compact complex projective space Cpk-2 of dimension k k- following the scaling - x//l ||=||| . E C. Therefore, the geodesic shape distance between landmark configurations x and y with corresponding centred and scaled versions p and q is p(x, v) infee(>,.) cos 1 (le-1pp"" pq" I): thus, the injectivity radius of the shape space is 7/2.
Let be a centred and scaled configuration. Minimizing unit- speed geodesics starting at x and initial velocity in the shape space are isometrically identified with unit-speed geodesics (-7/2, x/2] e + cos(s) + cos sin(s) on CS* wherein e satisfies v1, = 0 in addition to rv' = 0, and 1, is the vector of ones [Knddall et al. 1999 Chapter 6]: such geodesies are known as 'horizontal' geodesics. Consequently, the exponential map on the shape space is given by the corresponding one on the sphere with the additional condition on the velocity vectors. The inverse exponential map at exists within a ball of radius smaller than 2/2 in the shape space, and is thus given by exp (z. y) = 0lly - (x))l()))l where (r) == a(y" x:) is the projection of y onto and 0 = cos jxt y The (complex) holomorphic sectional curvature of the 2D Kendall's 's shape space is constant and equals 4 [Kendall et al. 1999].
As an application we consider the pre-processed corpus callosum data of Cornea et al. [001 from the Alzheimer's Disease Neuroimaging Initiative (ADNI). The data are from the mid mid-sagittal slices of MRIs (magnetic resonance images) and we refer to Cornnaa et al. [2177] on details of how the data was processed. Their data contains 409 total corpus callosa. The left portion of Figure 2 displays 10 sample corpus callosa where the parameterization is visually displayed as a color gradient from blue to yellow. In the middle we display the Fréchet mean of all 409 corpus callosa. Having computed the mean, we then sanitize the mean with three techniques: (i) using the proposed KNG mechanism (Right: top row); (ii) for comparison with (i), sanitize each landmark of the mean using the Laplace mechanism splitting the privacy budget (Right: middle row); (iii) sanitize each landmark as in (ii) without factoring in rotational alignment the corpus callosum. We expand on (ii) and (iii) in the Supplemental material.
8

---

C
C
Figure 2: Left panel: A sample of ten corpus callosa from the sample of 409. Middle: The Fréchet mean corpus callosum. Right, top row: Six sample private corpus callosa privatized under the KNG framework Kendall's ' 2D shape space. Right, middle row: Six sample private corpus callosa privatized point-wise with the Laplace mechanism. Right, bottom row: Six sample private corpus callosa privatized point-wise with the Laplace without accounting for rotational alignment. For more details, please refer to 4.3
Figure 3: Diffcrentially private corpus callosa estimates post-processed by using a first order local linear regression for smoothness. The left six are private under the proposed KNG framework while the right six are private under the point-wise Laplace as explained in Section 4.3
As we can observe in Figure 2 when one does not account for (rotations alignment this example), the shape of the corpus callosum is entirely destroyed during sanitization. Sanitization over the shape manifold (Right: top row) tends to retain the structure of corpus callosum when compared with sanitizing over each coordinate (Right: middle row), which appears more distorted; for example, we observe that the shape of the fifth corpus callosum (Right: middle row) has a contour with crossings. Further, we post-process to smooth the private estimates by first order local linear regression. Left panel of Figure g displays the post-processed KNG private estimates while the right panel shows point-wise Laplace private estimates, where rotational alignment has been carried out. We do not post-process the private estimates which do not consider rotational alignment as they appear to be non informative. Considering the mean shape in Figure 2 the "hook" the top is quite prominent and comparing this to the private corpus callosa of Figure we notice that the KNG estimates tend to preserve this structure. Even though all the private estimates processed in the same way, notice the Laplace estimates are only less smooth but can possess undesirable distortions, such as additional features such as loops.
transformations
Conclusions and future work
In this paper we demonstrate that versatility and powerful utility of the K-norm gradient mechanism on Idd carries over to the manifold setting. In particular, better control over global sensitivity when compared to the recently introduced manifold Laplace mechanism [Reimherr et al. 2021] for positively curved manifolds motivates the development of, our knowledge, the first privacy mechanism for statistical shape analysis of 2D point configurations. Gains in utility when working directly on the manifold, as opposed to the higher-dimensional ambient space, are observed in the numerical examples: in terms of utility, the KNG not only outperforms the Euclidean mechanism but also the manifold Laplace mechanism. Further, the Laplace on the manifold and our mechanism are intricately connected as they both are the exponential of norm in a particular tangent space

---

note in Remark [ this similarity in formulation and difference in sensitivity is tied to the better utility the case of positively curved manifolds.
Depending on the manifold, statistical utility gains enjoyed by working on the manifold can be tempered by expensive geometric computation. For example, in the of SPDM, the clear gains in utility are obtained within the context of computationally expensive sampling from the KNG (see also Supplemental material) owing to repeated computations of matrix inverses and square roots related to the exponential, inverse-exponentia maps and the geodesic distance, Indeed in practice, however, only a single instantiation suffices. contrast, sampling from the Laplace on manifolds is straightforward. and there is thus room for improvement in sampling from the KNG on manifolds.
Our work represents step in the right direction in developing privacy mechanisms for myriad of approaches to state-of-the-art statistical shape analysis on dimeni-ad manifolds of curves and surfaces [Srivastava and Klassen 2016], and diffeomorphisms [Grenander and Miller 2007). Moreover, our work opens up the possibility of developing geometry-driven privacy mechanisms for standard data analytic procedures used in various applications, such as principal component analysis (Grassmannian manifold of subspaces), rank-constrained matrix completion (quotient manifold of nonsingular matrices), and optimizing the Rayleigh quotient (Grassmannian), Procrustes problem (manifold of orthogonal matrices or frames), and pose estimation in computer vision (manifold of rotation matrices).
Acknowledgments and Disclosure of Funding
This work was funded in part by NSF SES-1853209 (to CS, MR, AS), NSF DMS-2015311 and EPSRC EP/VO48104/1 (to KB).
References
B. Afsari. Riemannian L center of mass: existence, uniqueness and convexity. Proceedings of the American Mathematical Sociery, 139(2):655 673, 2011.
Awan and A. Slavković. Structure and sensitivity in differential privacy: Comparing k-norm mechanisms. Journal of the American Statistical Association, 110i 116(534)93359544 2021.
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 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 STGMODD-IGGACT-SIGAAR' symposium on Principles of database systems, pages 128-138, 2005.
R. Caseiro, P. Martins, J. F. Henriques, and J. Batista. A nonparametric riemannian framework on tensor field with application foreground segmentation. Pattern Recognition, 4019 2012.
K. Chaudhuri, A. D. Sarwate, and K. Sinha. A near-optimal algorithm for differentially- principal components. Journal of Machine Learning Research, 14, 2013.
E. Cornea, H. Zhu, P. Kim, J. G. Ibrahim, and A. D. Initiative. Regression models riemannian symmetric spaces. Journal of the Royal Statistical Society: Series (Statistical Methodology), 79 (2):463-482) 2017.
M. P. Do Carmo. Riemannian geometry, volume 6. Springer, 1992.
C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211440) 2014.
í. ERCAN, G. OCAKOŚLUU SIGIRLI, and G. ŌZKAYA. Statistical shape analysis and usage in medical sciences. Turkiye Klinikleri Journal of Biostatistics, 4(1), 2012.
10

---

R. Gillad-Bachree and A. Gonen. Smooth sensitivity based approach for differentially private principal component analysis. arXiv preprint arXiv:1710.10556, 2017.
C. E. Ginestet, J. Li, P. Balachandran, S. Rosenberg, and E. D. Kolaczyk. Hypothesis testing for network data in functional neuroimaging. The Annals of Applied Statistics, pages 725-750, 2017.
U. Grenander and M. Miller. Pattern Theory: From Representation to Inference. Oxford University Press, 2007.
H. Hajri, L. llea, S. Said, L. Bombrun, and Y. Berthoumieu. Riemannian Laplace distribution on the space of symmetric positive definite matrices. Entropy, 18(3)998, 2016.
A. Han, B. Mishra, P. Jawanpuria, and J. Gao. Differentially private riemannian optimization. arXiv preprint ar Xrx:::2205.. X2v:22055009944 2022.
Harris, J. Tucker, B. Li, and L. Shand. Elastic depths for detecting shape anomalies functional data. Technometrics, 63(4):466-47) 2021.
H. Imtiaz and A. D. Sarwate. Symmetric matrix perturbation for differentially-prvvtee principal component analysis. In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2339-2343. IEEE, 2016.
H. Imtiaz and A. D. Sarwate. Differentially private distributed principal component analysis. In 2018 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pages 2206 2210. IEEE, 2018.
W. Jiang, C. Xie, and Z. Zhang. Wishart mechanism for differentially private principal components analysis. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
A. Jimenez, R. Ceres, and J. L. Pons. survey of computer vision methods for locating fruit on trees. Transactions of the ASAE, 13(6))1911, 2000.
H. Karcher. Riemannian center of mass and mollifier smoothing. Communications on pure and applied mathematics, 30(5):509-541, 1977.
T. Karras, S.
Laine, and T. Aila. A style-based generator architecture for generative adversarial networks. In Proceedings of the IEEÉ/CVF conference on computer vision and pattern recognition, pages 4401-4410, 2019.
D. G. Kendall. Shape manifolds, procrustean metrics, and complex projective spaces. Bulletin of the London mathematical society, 16(2):81-121, 1984.
D. G. Kendall, D. Barden, T. K. Carne, and H. Le. Shape and Shape Theory. Wiley, 1999.
R. Kimmel. Numerical geometry of images: Theory, algorithms, and applications. Springer Science & Business Media, 2003.
H. Le. Locating Fréchet means with applications to shape spaces. Advances in Applied Probability, 33(2):324-338, 2001.
S. J.
M. R. Tavares, et al. Shape Analysis in Medical Image Analysis. Springer, 2014.
F. McSherry and K. Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS-07) pages 94-103, 2007. doi: 10.1 10.1109/ FOCS.200P 2007.66.
M. Niethammer, R. S. Estepar, S. Bouix, M. Shenton, and C.-F. Westin. On diffusion tensor estimation. In 2006 International Conference of the IEEE Engineering in Medicine and Biology Society, pages 2622-2625. IEEF, 2006.
M. Reimherr and J. Awan. Kng: The k-norm gradient mechanism. In H. Wallach, Larochelle, A. Beygelzimer, F. ''Aché-Buuc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32, Curran Associates, Inc., 2019. URL https: //ppoc/ed/ggspsss
Paper. pdf

---

M. Reimherr, K. Bharath, and C. J. Soto. Differential privacy over riemannian manifolds. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL wtt..httss//oppeeeiiieeee wttp://wwww..eoooorr/dooooooeee/
J. Seeman, M. Reimherr, and A. Slavković. Exact privacy guarantees for markov chain imple- mentations of the exponential mechanism with artificial atoms. Advances in Neural Information Processing Systems, 34:1312: 13-13332221336 2021.
E. Sharon and D. Mumford. 2d-shape analysis using conformal mapping. International Journal of Computer Vision, 70(1):55-75, 2006.
O. Sheffet. Private approximations of the 2nd-moment matrix using existing techniques in linear regression. arXiv preprint arXiv: axxiv:1507.00056, 2015.
E. Shen and T. Yu. Mining frequent graph patterns with differential privacy. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 545-553, 2013.
A. Srivastava and E. P. Klassen. Functional and shape data analysis, volume 1. Springer, 2016.
D. W. Thompson and D. W. Thompson. On growth and form, volume 2. Cambridge university press Cambridge, 1942.
A. Trouvé and L. Younes. Local geometry of deformable templates. SIAM journal on mathematical analysis, 37(1):17-59, 2005.
Y.-X. Wang, S. Fienberg, and A. Smola. Privacy for free: Posterior sampling and stochastic gradient monte carlo. In International Conference on Machine Learning, pages 2493-2502. PMLR, 2015.
Younes. Spaces and manifolds of shapes computer vision: An overview. Image and Vision Computing, 3066-7):389-397, 2012.
R. Zhang and A. Srivastava. On shape analysis of functional data. In Riemannian Geometric Statistics in Medical Image Analysis, pages 417-438. Elsevier, 2020.
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]
(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 including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] The overall assumptions are outlined Assumption which we reference in each theorem along with any other necessary assumptions.
(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 exper- imental results (either in the supplemental material as URL)? [Yes] All code is provided as a zipped folder.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] This is mentioned in Section 4 and expanded on in the Supplemental materials.
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] In our Figure we display standard error bars from replications.
12

---

(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] This is included in the Supplemental materials.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section 4.3
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you 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 to participants and screenshots, applicable? [N/A]
(b) Did you deseribe 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 on participant compensation? [N/A]
13


Reviews:
[{"review_id": "uvsDhYQ_zJ7", "reviewer": "Reviewer_Z7Fo", "summary": "The paper provides a mechanism to achieve differential privacy of objects on a Riemannian manifold. By leveraging the connection between Riemannian distance and the exponential map on a manifold, the paper presents a novel generalization of the K Norm gradient mechanism for attaining DP extended to the scenario of Riemannian manifolds. The authors demonstrate an example of the utility of the low-rank preserving structure of their approach through a real-data experiment in shape-spaces by showing that a generic structure-unaware DP mechanism may be unable to capture the essential features of the objects in the dataset, while the methods developed in this paper succeed in doing so. The mechanism also allows for a potential computational gain in sampling because of its low-rank structure preserving nature.", "questions": "1. Can you provide more example areas of applications in terms of specific problems that can be addressed by this mechanism. Even though one such example is mentioned, I feel extending on the list of application areas can improve the visibility of the work beyond shape analysis.\n\n2. Can you give an intuition what issues non-existence or non-uniqueness of Frechet means may create? How would it affect the sensitivity of the mechanism? I am curious as to what could be an application example of such a case.\n\n", "limitations": "The authors have not addressed limitations and potential negative impacts of their work. However, I feel this is an important area and we should be mindful of any negative outcome.  Unfortunately, I am not an expert in the area and I would leave the precise explication of the limitations to experts.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In general, I feel the paper is well-motivated and its contribution is clearly-explained, the contributions are novel and have a wide range of applications for usage in various problems. The authors provide an example of one such application area, namely, that of shape-preserving transformations. Overall, I feel,  the authors have done a good job in clearly explaining the details of the paper in simple terms.\n\nHowever, I feel there needs to be more examples of applications to motivate and broaden the scope of this work. \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "rlgcz2tmxX5", "reviewer": "Reviewer_EM5Z", "summary": "This work proposes a privacy mechanism in the Riemannian manifold, where the output decided by the dataset is determined by the Fréchet mean estimation. The authors focus on the structure of the utility function and derive the sensitivity in the manifold. A KNG privacy mechanism is used for the problem and some theoretical analysis based on the KNG and manifold is provided in the paper. The examples of spheres, SPD matrix, and Kendall’s 2D shape space are proposed. The application in Kendall’s space is interesting and helpful in reality. It also gives us some insights to understand the practicality of the proposed method.", "questions": "Some questions:\n1. How is the sensitivity analysis combined with privacy analysis? Or just providing a global sensitivity for existing methods.\n2. Can more detailed and local sensitivity analysis help a tight privacy analysis for KNG?  The sensitivity is global for all $x$ in the analysis. \n3. How large $c_1$ and $c_2$ are in Theorem 3? Are they related to other constants? Some estimation or examples should be provided for some insight of the magnitude of $c_1$ and $c_2$.\n\n\nSome suggestions:\n1. The technical challenges can be clarified in the main context, especially compared with KNG and  Laplace mechanism in [Reimherr et al., 2021]). \n2. More detailed preliminaries should be given for Kendall’s experiments.\n3. The experiments for the verification of the proposed magnitude can be conducted.\n", "limitations": "The authors show some limitations of their work with a clarification of the assumptions.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n1. The proposed methods can solve the privacy problem in Fréchet mean estimation and reveal the influence of the curvature, which can be formulated as many problems in the real world.\n2. The methodology and the manifold structure/sensitivity are well studied theoretically in the work, which improves the reliability for the usage.\n\nCons:\n1. The technical challenges of the work are not clear. The novelty in techniques needs to be restated to show that the methodology/analysis is not a simple combination of existing methods (such as differences between KNG or Laplace mechanism in [Reimherr et al., 2021]).\n2. Some parts especially in Kendall’s experiments should be reorganized. Some preliminaries should be stated more clearly. It will be more friendly to some readers.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "ZdTY7rBt23", "reviewer": "Reviewer_gDXf", "summary": "This work studies a class of statistical estimation problems of sensitive data $D$ on Riemannian manifolds $\\mathcal{M}$, which can be formulated as minimizing a utility function $U(x; D)$ over $x\\in\\mathcal{M}$. To this end, the authors apply the K-norm Gradient Mechanism (KNG), proposed by Reimherr and Awan (2019), which applies the well-known exponential mechanism to the gradient norm $\\lVert \\nabla U(x; D) \\rVert_x$. \n\nThe authors focus on the problem of privately estimating the Fréchet mean, in which case the utility function that we want to minimize is the variance functional $F(x; D)$. With the KNG mechanism and an assumption that $D$ is contained in a geodesic ball with radius bounded by 1) the injectivity radius and 2) the inverse of the sectional curvature of $\\mathcal{M}$, they derive the sensitivity of the norm of gradient vector field $\\lVert \\nabla F(x; D) \\rVert_x$. Here, the sensitivity $\\Delta$ is dependent in the sectional curvature of $\\mathcal{M}$. This results in a differentially private algorithm for estimating the Fréchet mean via sampling from the density $f (x; D) \\propto \\exp(-\\epsilon\\lVert \\nabla F(x; D) \\rVert_x/2\\Delta )$. Assuming further that there is a lower bound for the sectional curvature of $\\mathcal{M}$, the authors show that the utility of this mechanism is $O\\left(\\frac{d}{n \\epsilon}\\right)$ which matches the lower bound in the Euclidean case.\n\nThe authors also perform several experiments: \n1. A simulation on the $d$-dimensional sphere, which has positive sectional curvature\n2. A simulation on the space of $k\\times k$ symmetric positive-definite matrices with the Rao-Fisher metrix, which has negative sectional curvature\n3. 2D Statistical shape space analysis on the data of mid-sagittal slices of MRIs,\n\nwhich demonstrate that the proposed method can be better utility compared to the previous DP algorithms on Riemannian manifolds.\n\n", "questions": "In Assumption 1, when the manifold has negative sectional curvature, it states that $r$ is unbounded. But we still have $r< \\frac{1}{2} \\text{inj }\\mathcal{M}$, right? So $r$ must not be unbounded, unless I am missing some fact about negatively curved manifolds.", "limitations": "The authors have addressed the limitation of the KNG mechanism in the Conclusions, including the difficulties of sampling from the KNG.\n\nThe data of MRIs is a public dataset, so there is no ethical concerns here.", "rating": 5, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strenghts\n\nThis paper provides a nice way of extending the differential privacy analysis of the exponential mechanism from the Euclidean spaces to Riemannian manifolds. It is interesting to see that using $-\\lVert \\nabla F(x; D) \\rVert_x$ as the score function in the exponential mechanism is better than using $- F(x; D)$ directly. I find the writing to be very clear and concise, given the complex subjects. I appreciate the authors' effort to include manifolds with both positive and negative sectional curvatures in the experiments, as well as an application on the real data.\n\nSmall note: for any compact Riemannian manifold, the sectional curvature is bounded (and hence lower bounded), so it satisfies the assumption in Lemma 1.\n\n# Weaknesses\n\nThis work seems to be quite incremental, as the proof of sensitivity bound (Theorem 2) is already given in the supplemental to Reimherr et al (2021). So the main contribution of this paper lies in the utility analysis and the experiments, which is quite lacking for a DP paper in my opinion.\n\nAnother issues is the non-trivial sampling from the exponential mechanism: $f (x; D) \\propto \\exp(-\\epsilon\\lVert \\nabla F(x; D) \\rVert_x/2\\Delta )$, which is done via Metropolis-Hastings (MH) in this paper. However, the sampling distribution of the MH is not exactly the same as that of the exponential mechanism, so there is no guarantee that MH satisfies $\\epsilon$-DP. Right now, the best we can do is $(\\epsilon,\\delta)$-DP, where $\\delta$ depends on the total variation between the MH and target distribution (see Shen & Yu, 2013, Lemma 2 and Wang et al., 2015, Proposition 3). With careful analysis, it is possible to obtain $\\epsilon$-DP in the case of Gibbs sampling (Foulds et al., 2016, Section 4.1).\n\nThe fact that sampling from $f (x; D)$ is non-trivial, and how one can resolve this issue, could have been mentioned in the earlier sections.\n\nReferences:\n* Foulds, J., Geumlek, J., Welling, M. and Chaudhuri, K. 2016. On the Theory and practice of privacy-preserving Bayesian data analysis. UAI'16. \n* Shen, E. and Yu, T. 2013. Mining frequent graph patterns with differential privacy. KDD ’13. doi: 10.1145/2487575.2487601.\n* Wang, Y.-X., Fienberg, S. E., and Smola, A. J. 2015. Privacy for free: Posterior sampling and stochastic gradient monte carlo. ICML’15.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4eo9Pn5VtGa", "reviewer": "Reviewer_sqTu", "summary": "The authors of this paper study the problem of computing Frechet mean on manifold with differentially privacy constraints. The problem is interesting and the results are promising for other related problems. \n\n", "questions": "It will be good to compare with an iterative based algorithm for manifold optimization (i.e., when you compute the Frechet mean), at least in the numerical section. See a related paper:\n\nHan, Andi, et al. \"Differentially private Riemannian optimization.\" arXiv preprint arXiv:2205.09494 (2022).\n", "limitations": "I suggest the authors to spend more effort on making the paper more clear to the first readers (especially Section 3). The reviewer believes that this paper can attract the community if written nicely. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Geometrical interpretation will be very helpful especially for the first readers.\n\n\nSection 2.2, I think the description of the first equation is not correct.\n\n\n\n\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept