Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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$. 

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

The authors also perform several experiments: 
1. A simulation on the $d$-dimensional sphere, which has positive sectional curvature
2. A simulation on the space of $k\times k$ symmetric positive-definite matrices with the Rao-Fisher metrix, which has negative sectional curvature
3. 2D Statistical shape space analysis on the data of mid-sagittal slices of MRIs,

which demonstrate that the proposed method can be better utility compared to the previous DP algorithms on Riemannian manifolds.


strengths_and_weaknesses: # Strenghts

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

Small note: for any compact Riemannian manifold, the sectional curvature is bounded (and hence lower bounded), so it satisfies the assumption in Lemma 1.

# Weaknesses

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

Another 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).

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

References:
* Foulds, J., Geumlek, J., Welling, M. and Chaudhuri, K. 2016. On the Theory and practice of privacy-preserving Bayesian data analysis. UAI'16. 
* Shen, E. and Yu, T. 2013. Mining frequent graph patterns with differential privacy. KDD ’13. doi: 10.1145/2487575.2487601.
* Wang, Y.-X., Fienberg, S. E., and Smola, A. J. 2015. Privacy for free: Posterior sampling and stochastic gradient monte carlo. ICML’15.

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.

The data of MRIs is a public dataset, so there is no ethical concerns here.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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.

However, I feel there needs to be more examples of applications to motivate and broaden the scope of this work. 

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.

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


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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Pros:
1. 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.
2. The methodology and the manifold structure/sensitivity are well studied theoretically in the work, which improves the reliability for the usage.

Cons:
1. 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]).
2. 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.
questions: Some questions:
1. How is the sensitivity analysis combined with privacy analysis? Or just providing a global sensitivity for existing methods.
2. Can more detailed and local sensitivity analysis help a tight privacy analysis for KNG?  The sensitivity is global for all $x$ in the analysis. 
3. 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$.


Some suggestions:
1. The technical challenges can be clarified in the main context, especially compared with KNG and  Laplace mechanism in [Reimherr et al., 2021]). 
2. More detailed preliminaries should be given for Kendall’s experiments.
3. The experiments for the verification of the proposed magnitude can be conducted.

limitations: The authors show some limitations of their work with a clarification of the assumptions.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 


strengths_and_weaknesses: Geometrical interpretation will be very helpful especially for the first readers.


Section 2.2, I think the description of the first equation is not correct.






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:

Han, Andi, et al. "Differentially private Riemannian optimization." arXiv preprint arXiv:2205.09494 (2022).

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.
review_title: null

Meta-review: metareview: The reviewers agree that the paper should be accepted (albeit with a mix of the level of acceptance). I agree. The presentation of the paper could be better. 
confidence: Less certain
Decision: Accept