Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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. 

The 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.
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. 

Although 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.

One 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? 

My 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. 

The 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.


==== Minor Comments

While 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. 

It 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…)

Something seems amiss about the second sentence of the proof of Theorem 2. Assumption 1 doesn’t seem to imply anything about the manifold itself.

limitations_and_societal_impact: I do not see any negative societal impact.
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: 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.
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.
limitations_and_societal_impact: Yes. I think this paper is good.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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).

The 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.
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:
- the generalizations of the Laplace mechanism, and sensitivity, are the direct and natural analogues of the Euclidean case
- the savings compared to the naive embedding approach do not seem incredible (constant factors), at least for the example discussed (see below)
- the computational aspects are evoked, but would gain to be explored in more detail
- 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?

As 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.

- How computationally easy is Assumption 1 to check (find the optimal r) given a manifold and a dataset?
- 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). 

Maybe look for a setting/estimation problem where the rate scales superpolynomially in the dimension? Then you would get a much clearer advantage.

Minor points:

Theorem 1: "foot-point" -> footpoint
- 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

====
Updated my score in view of the authors' response and reviewers' discussions.
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_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: There are two main contributions in the paper:
- 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.
- 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.
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.

Minor comments:

l.93: is the supremum of... I do not understand this definition.

l.133: define what the Laplace mechanism is

l.145: to be A global minimizer 

l.151: I think it should be $x_i = 2\pi i/(n-1)$ 

l.152: minimizing the ENERGY FUNCTIONAL $F_2$

l.160: The data...

l.162: " it suffices for radius "

l.167: I could not find this assertion in [Le, 2001]

l.173: depends only on $r$ and ON...

l.181: for THE datasets

l.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.

l.189: $G_2$ instead of $G$

l.190: 0<t_0<b

l.193: what is the definition of z?

l.201: I think it should be $1$ for $\kappa=0$.

l.202: Replace with "If $\kappa>0$, the function $s\mapsto a(s,\kappa)$ is decreasing and upper bounded by $1$" (or similar formulation)

l.217: specify what is $\sigma$ in the Laplace mechanism

l.250: we want that the expected distance is larger than the quantity (and not a big O)

l.256: I could not find the details in the supplementary material.

l.264: THE Rao-Fisher metric
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: This paper studies differential privacy for the case of data and/or summary which consists of points in a Riemannian manifold.
The Laplace mechanism for DP is adapted to this case, basic results on its effectiveness are proven, and two examples are worked out.
main_review: This paper studies differential privacy for the case of data and/or summary which consists of points in a Riemannian manifold.
After pointing out that the standard definition generalizes, several simple and elegant results are proven:
1. The Laplace mechanism for realizing DP generalizes straightforwardly.
2. The sensitivity of the Frechet mean is bounded, so it can be used to produce a DP summary.
3. The intrinsic definition is shown to work better than the definition by embedding the manifold.

Then, 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.

This is a very nice work and can also serve as an introduction to DP for non-experts (such as myself).
I cannot judge the authors' claim that this is the first work on DP for manifolds, but granting it, 
this seems quite suitable for NeurIPS.
limitations_and_societal_impact: Differential privacy is a topic which involves public purpose considerations.  
But the present work is abstract and does not directly touch on them.
review_title: null

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)