Exponential-Wrapped Mechanisms for Differential Privacy on Hadamard Manifolds

Question

Could the authors provide specific examples? Also, what is the motivation for considering Hadamard manifolds in this paper? What considerations led the authors to naturally introduce Hadamard manifolds into differential privacy?

The key motivation behind considering Hadamard manifolds centers around the space of SPDM. As mentioned, it's one of the most important manifolds in statistics and machine learning. In particular, it's commonly used in biomedical data such as brain imaging. Brain imaging data, such as MRI and fMRI scans, often contain highly detailed and unique features that could inadvertently reveal identities or medical conditions. Developing differential privacy mechanisms on Hadamard manifolds (and thus SPDM space) allows us to protect sensitive patient information while enabling valuable research and analysis.

Additionally, is this related to the stronger divergence of the Laplace mechanism and the better behavior of its solution, such as better convergence of its inverse?

Can you provide a bit more explanation on this particular comment? We are a little unsure on what are the meanings of "divergence of the Laplace mechanism" and "better convergence of its inverse".

References

[1]: Matthew Reimherr, Karthik Bharath, and Carlos Soto. Differential privacy over Riemannian manifolds. In Advances in Neural Information Processing Systems, volume 34, pp. 12292–12303. Curran Associates, Inc., 2021.

[2]: Yangdi Jiang, Xiaotian Chang, Yi Liu, Lei Ding, Linglong Kong, and Bei Jiang. Gaussian differential privacy on Riemannian manifolds. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023.

[3]: Saiteja Utpala, Praneeth Vepakomma, and Nina Miolane. Differentially private fr'echet mean on the manifold of symmetric positive definite (SPD) matrices with log-euclidean metric. Transactions on Machine Learning Research, 2023.

[4]: Peter J. Basser, James Mattiello, Denis Le Bihan, MR diffusion tensor spectroscopy and imaging, Biophysical Journal 66 (1994) 259–267.

[5]: Denis Le Bihan, Jean-François Mangin, Cyril Poupon, C.A. Clark, S. Pappata, N. Molko, H. Chabriat, Diffusion tensor imaging: concepts and applications, Journal of Magnetic Resonance Imaging 13 (4) (2001) 534–546.

[6]: Pierre Fillard, Vincent Arsigny, Xavier Pennec, Paul M. Thompson, Nicholas Ayache, Extrapolation of sparse tensor fields: application to the modelling of brain variability, in: Gary Christensen, Milan Sonka (Eds.), Proc. of Information Processing in Medical Imaging 2005 (IPMI’05), Glenwood Springs, Colorado, USA, in: LNCS, vol. 3565, Springer, July 2005, pp. 27–38, PMID: 17354682.

[7]: Pierre Fillard, Vincent Arsigny, Xavier Pennec, Kiralee M. Hayashi, Paul M. Thompson, Nicholas Ayache, Measuring brain variability by extrapolating sparse tensor fields measured on sulcal lines, NeuroImage 34 (2) (January 2007) 639–650, also as INRIA Research Report 5887, April 2006, PMID: 17113311.

[8]: Gérard Medioni, Mi-Suen Lee, Chi-Keung Tang, A Computational Framework for Segmentation and Grouping, Elsevier, 2000.

[9]: Thomas Brox, Johachim Weickert, Bernhard Burgeth, Pavel Mrázek, Nonlinear structure tensors, Image and Vision Computing 24 (1) (2006) 41–55.

[10]: Johachim Weickert, Thomas Brox, Diffusion and regularization of vector- and matrix-valued images, in: M.Z. Nashed, O. Scherzer (Eds.), Inverse Problems, Image Analysis, and Medical Imaging, in: Contemporary Mathematics, vol. 313, AMS, Providence, 2002, pp. 251–268.

[11]: Joachim Weickert, Hans Hagen (Eds.), Visualization and Processing of Tensor Fields. Mathematics and Visualization, Springer, 2006.

[12]: Xavier Pennec, Stefan Sommer, and Tom Fletcher. Riemannian geometric statistics in medical image analysis. Academic Press, 2019.

[13]: Maximillian Nickel and Douwe Kiela. Poincare embeddings for learning hierarchical representations. Advances in neural information processing systems, 30, 2017.

[14]: Benjamin P Chamberlain, James Clough, and Marc P Deisenroth. Neural embeddings of graphs in hyperbolic space. arXiv preprint arXiv:1705.10359, 2017.

[15]: Rik Sarkar. Low distortion delaunay embedding of trees in hyperbolic plane. In International Symposium on Graph Drawing, pp. 355–366. Springer, 2011.

[16]: Edoardo Cetin, Benjamin Paul Chamberlain, Michael M. Bronstein, and Jonathan J Hunt. Hyperbolic deep reinforcement learning. In The Eleventh International Conference on Learning Representations, 2023.

Thank you for your thorough review and constructive feedback. We appreciate your insights, and we have addressed your concerns and questions in our response below:

Weakness

The paper lacks comparison with previous results. There is no clear comparison within the sections to evaluate the proposed method against existing methods, making it difficult for readers to assess whether the proposed approach truly represents an improvement.

For our Exponential-Wrapped (EW) Laplace mechanism, we conducted a comparison with the Riemannian Laplace mechanism proposed in [1] on SPDM spaces. Our results show that the EW Laplace mechanism achieves comparable performance overall. As the dimension $d$ increases, its performance declines relative to the Riemannian Laplace mechanism, which is expected since the utility benefits of our mechanism are designed for non-homogeneous manifolds. Specifically, the EW Laplace mechanism uses a sensitivity parameter of $\Delta/\varepsilon$ instead of the $2\Delta/\varepsilon$ used by the Riemannian mechanism. However, this trade-off leads to a substantial computational advantage: the EW Laplace mechanism is nearly 400 times faster. This makes it highly practical for applications requiring computational efficiency.

1. Performance Metrics: Please see the top three plots in Figure 1.
2. Computational Time Comparison: Refer to the first two columns of Table 1.

For our Exponential-Wrapped (EW) Gaussian mechanism, we focused on achieving GDP on SPDM spaces. To our knowledge, this is the first mechanism to achieve GDP (or any variant of DP definition other than pure-DP) on SPDM spaces with commonly used metrics, such as the affine-invariant metric. Existing works are limited: [2] supports GDP only on constant curvature spaces, and [3] achieves $(\varepsilon,\delta)$-DP for SPDMs but is restricted to the log-Euclidean metric. Our EW Gaussian mechanism generalizes [3], working for any Riemannian metric, and reduces to the tangent Gaussian mechanism under the log-Euclidean metric.

In the absence of comparable GDP mechanisms for SPDM spaces, we evaluated the EW Gaussian mechanism against the Riemannian Laplace mechanism [1]. Our Gaussian mechanism demonstrates superior utility at smaller privacy budgets $\mu$.

1. Performance Metrics: Please see the bottom three plots in Figure 1.
2. Computational Time Comparison: Refer to the last column of Table 1.

The practical applications are limited, only valid on Hadamard manifolds. This does not differ significantly from cases on $\mathbb{R}^n$ but has greater limitations. After all, when do people operate in a space of negative curvature?

We believe there are many practical applications in Hadamard manifolds. Hadamard manifolds contain two of the most encountered manifolds in statistics/machine learning, the hyperbolic space and the space of SPD matrices.

SPD matrices play a significant role in medical imaging and are often called tensors when modelling the covariance matrix of water's Brownian motion in Diffusion Tensor Imaging [4, 5]. They have also been used in shape analysis to capture joint variability across different locations [6, 7]. Furthermore, SPD matrices are widely applied in computer vision and image analysis tasks, including segmentation, grouping, and motion analysis [8, 9, 10, 11]. For a summary of the practical applications of SPDM space, refer to Chapter 3 of [12].

Hyperbolic spaces have gained considerable attention in machine learning for their ability to enhance performance and efficiency, particularly in learning representations of hierarchical structures and graph data [13, 14]. A key characteristic of hyperbolic space is its exponential volume growth, which allows tree-like hierarchical data to be embedded with low distortion while requiring only a few dimensions [15]. It leads to lower complexity, fewer parameters, and less overfitting. For more details, refer to [16].

Thank you for your thorough review and constructive feedback. We appreciate your insights, and we have addressed your concerns and questions in our response below:

Weakness

Paper only uses the SPD manifold in experiments, but it would benefit from a more extensive empirical evaluation across different types of Hadamard manifolds and real-world applications. My main suggestion would be to extend the experiments to Hyperbolic spaces, which have a ton of interesting applications. \end{zitat}

We agree that extending the experiments to hyperbolic spaces would be interesting as in recent years, hyperbolic space has been explored in many machine-learning areas such as hyperbolic reinforcement learning and hyperbolic neural networks. It's a direction we will for sure explore in future works.

We have added a new experiment on a biomedical dataset, MedMNIST, as a real-world example of data in the SPDM space. See Appendix A.3.1 in the updated pdf for more details. We focus on outputting fr'echet mean and achieving the GDP privacy guarantee. Similar to the simulation study, our EW Gaussian mechanism can achieve better utility for smaller privacy budgets.

Questions

If the selected footpoint is kept secret, only revealing the final perturbed result in the manifold, will there be a higher privacy risk if the choice of footpoint is influenced by the data? Could the authors give an example to help me see why the design of their mechanism fixes $p_0$ a-priori was necessary as opposed to setting $p_0$ to be the same as the unperturbed outcome?

Yes, there will be a higher privacy risk if the footpoint is selected based on the data. To understand why the footpoint needs to be selected a-priori, let's consider the EW Laplace mechanism where the footpoint is chosen to be the unperturbed outcome $f(\mathcal{D})$. The density of the mechanism is then given below,

$

g(y) \propto \frac{1}{J_{f(\mathcal{D})}(\log_{f(\mathcal{D})}(y))} \exp \left(-\frac{||\log_{f(\mathcal{D})}(y)||_{f(\mathcal{D})}}{\sigma} \right),
$

To show it satisfies pure DP, it amounts to show the ratio of the two densities (one density corresponding to 1 neighbouring dataset) is smaller than $e^\varepsilon$. The ratio will have the following form,

$

\frac{J_{f(\mathcal{D}^{\prime})}(\log_{f(\mathcal{D}^{\prime})}(y))}{J_{f(\mathcal{D})}(\log_{f(\mathcal{D})}(y))} \exp \left(\frac{||\log_{f(\mathcal{D}^{\prime})}(y)||_{f(\mathcal{D}^{\prime})} - ||\log_{f(\mathcal{D})}(y)||_{f(\mathcal{D})}}{\sigma} \right),
$

This ratio is difficult to evaluate because: 1) the Jacobian terms can no longer be cancelled out, making them challenging to compute, and 2) the two norms within the $\exp$ are defined on different (tangent) spaces, meaning the usual triangle inequality cannot be applied. However, if we select the footpoint a priori, these two issues can be avoided.

Could the authors describe the technical reason behind the dependence on dimension size for the EW-Gaussian mechanism in equation (3)? In lines 417-419, authors mention something about the volume distortions being more pronounced in higher dimensions, but I don't quite understand the magnitude of such distortions. Can they be avoided?

As mentioned above, the dependence of the dimension $d$ can be seen from the following equation

$

\int |x - \eta| f(x; \eta, \sigma^2) , dx = \sqrt{2} \sigma^2 d \frac{\Gamma((d+1)/2)}{\Gamma((d+2)/2)}.
$

The volume distortions can be reduced if a good footpoint is selected. It can be avoided if the footpoint is selected to be exactly the unperturbed outcome, but this is not possible as I explained above.

References

[1]: Matthew Reimherr, Karthik Bharath, and Carlos Soto. Differential privacy over Riemannian manifolds. In Advances in Neural Information Processing Systems, volume 34, pp. 12292–12303. Curran Associates, Inc., 2021.

[2]: Yann Thanwerdas and Xavier Pennec. $O(n)$-invariant Riemannian metrics on spd matrices. Linear Algebra and its Applications, 661:163–201, 2023. ISSN 0024-3795. doi: https://doi.org/10.1016/j.laa. 2022.12.009.

Unlike Gaussian mechanism whose utility guarantee remains dimension independent, it's exponentially-wrapped counterpart proposed seem to be somehow dependent in the dimension size (eqn. (3)). I'm not certain if this dependence helps or hurts when dimension $d$ is large.

The utility guarantee of the Gaussian mechanism on $\mathbb{R}^d$ would still depend on its dimension $d$. This can be seen as
$

\int |x - \eta| f(x; \eta, \sigma^2) , dx = \sqrt{2} \sigma^2 d \frac{\Gamma((d+1)/2)}{\Gamma((d+2)/2)}
$

where $f(x; \eta, \sigma^2)$ denotes the multivariate gaussian density with mean $\eta$ and variance $\sigma^2 \mathbf{I}_d$ and $\Gamma$ denotes the gamma function. Similarly, for the Laplace mechanism, the dependence on $d$ can not be avoided either, see page 6 of [1].

The simulation results suggest that Riemannian Laplace mechanism proposed in the prior works performs better than this paper's EW Laplace in higher dimensions or in reasonable privacy regimes (1 $>$ eps $>$ 0.5). In lines 415-417, the authors acknowledge that this is expected as the utility advantage of their mechanism are reserved for non-homogeneous manifolds. Most manifolds we see in practice however are homogeneous---spheres, Torus, Grassmannian, etc.

We agree that many manifolds encountered in practice are homogeneous. However, the homogeneity of a manifold is tied to its Riemannian metric. When a different Riemannian metric is applied to the same manifold, it may no longer remain homogeneous. For example, when the SPDM space is equipped with the Wasserstein/Procrustes metric, it is no longer homogeneous [2].

Thank you for your thorough review and constructive feedback. We appreciate your insights, and we have addressed your concerns and questions in our response below:

Weakness

The main drawback of this approach is the cost that seems to be associated with the choice of the footpoint around which the mechanism is wrapped. More specifically, in equation (2) and (3), the utility for Frechet mean via the proposed mechanisms is closely tied to the choice of footpoint $p_0$ chosen on the manifold. Even when $p_0$ is set to be the center of the ball $B_r(m)$ in which all data-points lie, the utility upper bound is as high as $r$, which is of the same order as a random guess within the ball. This seems to be true for both the proposed EW Gaussian and EW Laplace mechanisms.

We agree that the performance of the mechanism depends on the choice of the footpoint. However, there are ways to mitigate its impact. As you mentioned, one option is to allocate part of the privacy budget to identify a good footpoint. Alternatively, if prior information about the private data is available, it could be used to determine a suitable footpoint.

Authors mention that the footpoint $p_0$ for their proposed mechanisms must be selected a priori without looking at the data. But, it isn't obvious to me why this footpoint can't be data-dependent. I suspect the utility of the mechanisms can significantly improve if some of the privacy budget is spent to privately determine a good footpoint for the mechanism first.

The footpoint $p$ determines the specific tangent space $T_p\mathcal{M}$ from which the push-forward distribution is applied. %Two Exponential-Wrapped Gaussian distributions with different footpoints indicate that they are the push-forward distribution of the (Euclidean) Gaussian distributions on two different tangent spaces. Demonstrating a mechanism satisfying some variant of differential privacy involves computing the ratio of two probability densities of the mechanism under two neighbouring datasets. If the footpoint is data-dependent, the ratio would be between two exponential-wrapped distributions with different footpoints. This makes the computation much more involved as it involves computing the ratio of the Jacobians and dealing with two norms on two different tangent spaces.

Two Exponential-Wrapped Gaussian distributions with different footpoints represent the push-forward distributions of (Euclidean) Gaussian distributions on two distinct tangent spaces. To demonstrate that a mechanism satisfies a DP privacy guarantee, it is necessary to compute the ratio of the probability densities under two neighbouring datasets. If the footpoint is data-dependent, this ratio involves two Exponential-Wrapped distributions with different footpoints. This significantly complicates the computation, as it requires calculating the ratio of the Jacobians and managing two norms on two different tangent spaces. For more details, please refer to our response to the question section below.

Spending part of the privacy budget to select a good footpoint can indeed improve utility in certain scenarios. Specifically, when there is no prior information about the data and the geodesic ball $B_r(m)$ containing the data has a large radius $r$, blindly choosing the center of the geodesic ball may not be ideal. In such cases, allocating a portion of the privacy budget to determine a suitable footpoint is the better approach. In fact, this is what we did in the newly added experiment on the real-world biomedical dataset, MedMNIST, as detailed in Appendix A.3.1.

Questions

Are there any practical problems in the real world such that the values have fallen into Hadamard Manifolds?

As mentioned above, the two prominent Hadamard manifolds—hyperbolic space and SPDM spaces—have plenty of real-world applications.

Thank you for your thorough review and constructive feedback. We appreciate your insights, and we have addressed your concerns and questions in our response below:

Weakness

From a technical point of view, the biggest concern is that the paper made a strong assumption that the values of the function fall into a manifold with good properties. With these properties, one can directly apply sampling techniques via Exponential-Wrapped Probability to achieve DP or approximate DP. The techniques become a bit straight-forward.

SPD matrices play a significant role in medical imaging and are often called tensors when modelling the covariance matrix of water's Brownian motion in Diffusion Tensor Imaging [1, 2]. They have also been used in shape analysis to capture joint variability across different locations [3, 4]. Furthermore, SPD matrices are widely applied in computer vision and image analysis tasks, including segmentation, grouping, and motion analysis [5, 6, 7, 8]. For a summary of the practical applications of SPDM space, refer to Chapter 3 of [9].

Hyperbolic spaces have gained considerable attention in machine learning for their ability to enhance performance and efficiency, particularly in learning representations of hierarchical structures and graph data [10, 11]. A key characteristic of hyperbolic space is its exponential volume growth, which allows tree-like hierarchical data to be embedded with low distortion while requiring only a few dimensions [12]. It leads to lower complexity, fewer parameters, and less overfitting. For more details, refer to [13].

We will include more background materials like the above in the paper for the reader's information.

The simulation is only for synthetic data, it is not clear whether there are any real use cases / problems that fall in the case that value functions are in such a good manifold.

We have added a new experiment on a real-world biomedical dataset, MedMNIST. Please refer to Appendix A.3.1 in the updated pdf for more details. This experiment focuses on computing the Fréchet mean while ensuring a GDP privacy guarantee. Similar to the simulation study, our Exponential-Wrapped Gaussian mechanism demonstrates better utility for smaller privacy budgets.

References

[1]: Peter J. Basser, James Mattiello, Denis Le Bihan, MR diffusion tensor spectroscopy and imaging, Biophysical Journal 66 (1994) 259–267.

[2]: Denis Le Bihan, Jean-François Mangin, Cyril Poupon, C.A. Clark, S. Pappata, N. Molko, H. Chabriat, Diffusion tensor imaging: concepts and applications, Journal of Magnetic Resonance Imaging 13 (4) (2001) 534–546.

[3]: Pierre Fillard, Vincent Arsigny, Xavier Pennec, Paul M. Thompson, Nicholas Ayache, Extrapolation of sparse tensor fields: application to the modelling of brain variability, in: Gary Christensen, Milan Sonka (Eds.), Proc. of Information Processing in Medical Imaging 2005 (IPMI’05), Glenwood Springs, Colorado, USA, in: LNCS, vol. 3565, Springer, July 2005, pp. 27–38, PMID: 17354682.

[4]: Pierre Fillard, Vincent Arsigny, Xavier Pennec, Kiralee M. Hayashi, Paul M. Thompson, Nicholas Ayache, Measuring brain variability by extrapolating sparse tensor fields measured on sulcal lines, NeuroImage 34 (2) (January 2007) 639–650, also as INRIA Research Report 5887, April 2006, PMID: 17113311.

[5]: Gérard Medioni, Mi-Suen Lee, Chi-Keung Tang, A Computational Framework for Segmentation and Grouping, Elsevier, 2000.

[6]: Thomas Brox, Johachim Weickert, Bernhard Burgeth, Pavel Mrázek, Nonlinear structure tensors, Image and Vision Computing 24 (1) (2006) 41–55.

[7]: Johachim Weickert, Thomas Brox, Diffusion and regularization of vector- and matrix-valued images, in: M.Z. Nashed, O. Scherzer (Eds.), Inverse Problems, Image Analysis, and Medical Imaging, in: Contemporary Mathematics, vol. 313, AMS, Providence, 2002, pp. 251–268.

[8]: Joachim Weickert, Hans Hagen (Eds.), Visualization and Processing of Tensor Fields. Mathematics and Visualization, Springer, 2006.

[9]: Xavier Pennec, Stefan Sommer, and Tom Fletcher. Riemannian geometric statistics in medical image analysis. Academic Press, 2019.

[10]: Maximillian Nickel and Douwe Kiela. Poincare embeddings for learning hierarchical representations. Advances in neural information processing systems, 30, 2017.

[11]: Benjamin P Chamberlain, James Clough, and Marc P Deisenroth. Neural embeddings of graphs in hyperbolic space. arXiv preprint arXiv:1705.10359, 2017.

[12]: Rik Sarkar. Low distortion delaunay embedding of trees in hyperbolic plane. In International Symposium on Graph Drawing, pp. 355–366. Springer, 2011.

[13]: Edoardo Cetin, Benjamin Paul Chamberlain, Michael M. Bronstein, and Jonathan J Hunt. Hyperbolic deep reinforcement learning. In The Eleventh International Conference on Learning Representations, 2023.

Thank you for your detailed review and constructive feedback. We are confident that our response has addressed your concerns. If there are any additional points requiring clarification or refinement, please let us know. We would greatly value any additional thoughts you may have on our submission.

Thank you for your thorough review and constructive feedback. We appreciate your insights, and we have addressed your concerns and questions in our response below:

Weakness

To me the major issue is the writing of the paper. It could be that my geometry is simply rusty, but I'm not sure how familiar the general community for this venue are with the math concepts used in this paper. In light of that, I think this paper sort of takes it for granted that people know all these things (such as Exponential mapping, push-forward, etc.) already. I find the preliminary section to be unsatisfying and insufficient of the crucial math concepts used later in the deduction of the mechanisms in general. My (biased) opinion is that some of these things deserve more explanation before we go deeper into the weeds.

We agree that the differential geometry stuff can be hard to get into without a proper introduction. We will reorganize the background material section for Riemannian geometry and provide more intuitive explanations to help the readers grasp these concepts better.

I was also slightly surprised that when $\varepsilon$ is about [0.2, 0.6], the benchmark algorithm performs better than the proposed algorithm. I think in Euclidean spaces at least for pure DP the Laplace mechanism should be pretty close to being optimal for such small $\varepsilon$ values?

For pure DP, both our proposed algorithm and the benchmark algorithm can be viewed as variants of the Laplace mechanism. The benchmark algorithm adapts the Laplace distribution from Euclidean spaces to manifolds by replacing the $l_1$ -norm with the Riemannian distance function. In contrast, our Exponential-Wrapped Laplace mechanism extends the Laplace distribution to manifolds by leveraging the push-forward distribution of the (Euclidean) Laplace distribution on a tangent space $T_p\mathcal{M} \simeq \mathbb{R}^d$.

The key advantage of our algorithm over the benchmark lies in its significantly faster computational performance. Additionally, for non-homogeneous manifolds, our mechanism uses a reduced rate of $\Delta/\varepsilon$ compared to the benchmark's $\Delta/\varepsilon$. On homogeneous manifolds, however, both algorithms operate with a rate of $\Delta/\varepsilon$. Given that the SPDM space in the simulation study is homogeneous, we do not expect our algorithm to provide better utility than the benchmark in this scenario.

There isn't much theoretical characterization of how good such generalization mechanisms are, even in the pure DP case. But perhaps that's because the community simply don't know much in this more complicated context. \end{zitat}

In Theorem 4.1, we provide upper bounds on the expected distance between the output of our Exponential-Wrapped mechanisms and the unperturbed outcome. While these bounds are not tight due to the reliance on the triangle inequality, they offer valuable insights into how the mechanism's performance depends on various parameters, including $n, d, \mu, r$.

Minor

Thanks for pointing out the typos. The typos have been fixed in the updated pdf.

In line 108 the sentence seems incomplete: In line 108 the sentence seems incomplete: "There exists a unique [???] starting from..."

It should be "There exists a unique geodesic $\gamma_{(p, v)}(t)$ starting from..."

The notion $p_0$ abruptly appeared in line 188.

It should be $p$ instead of $p_0$.

Questions

Do you have any insights into if there could be similar extensions for other traditional mechanisms such as the K-norm mechanism (Laplace is a special case of K-norm using the $l_1$-norm)?

The $K$-norm mechanism has been extended to general manifolds in [1].

I'm not very familiar with Riemannian Geometry and Manifolds, to me it is surprising that the extended version of Laplace has additional parameter $p_0$ (the footprint) compared to the Euclidean space version. I thought the Hardamard Manifold is basically a warped version of Euclidean space, but then in principle why do we need to use an additional $p_0$ to define the Laplace Mechanism? To help the understanding, can the authors recast the results back into Euclidean space and show the value of all these parameters given $\varepsilon$ for pure DP budget?

Intuitively, a manifold is a space that is locally Euclidean. In other words, if we focus on a small region of the manifold, it behaves like an Euclidean space. However, when we zoom out and observe the manifold as a whole, its characteristics can differ significantly from those of Euclidean space. For example, on a sphere, parallel lines converge and eventually meet, while in hyperbolic space (a Hadamard manifold), they diverge and spread apart.

As mentioned above, our Exponential-Wrapped Laplace mechanism extends the Laplace mechanism to manifolds by leveraging the push-forward distribution of the (Euclidean) Laplace distribution on a tangent space $T_p\mathcal{M} \simeq \mathbb{R}^d$. However, each point $p$ on the manifold has a corresponding tangent space $T_p\mathcal{M}$ and the footpoint $p$ indicates the specific tangent space $T_p\mathcal{M}$ from which the push-forward distribution is applied.

Our Exponential-Wrapped Laplace mechanism (similarly for the Gaussian mechanism) can be described through the following steps:

1. Select a footpoint $p_0$.
2. Use the $\log_{p_0}$ function to project the unperturbed outcome $f(\mathcal{D}) \in \mathcal{M}$ to the tangent space $T_{p_0}\mathcal{M}$ to obtain $\log_{p_0}(f(\mathcal{D})) \in T_{p_0}\mathcal{M} \simeq \mathbb{R}^d$.
3. Perturb $\log_{p_0}(f(\mathcal{D}))$ use the usual Euclidean Laplace mechanism to obtain $v = \log_{p_0}(f(\mathcal{D})) + \text{Laplace}(0, \sigma)$ where $\sigma = \Delta / \varepsilon$.
4. Use the $\exp_{p_0}$ to project $v$ back to the manifold to obtain the final perturbed outcome $\exp_{p_0}(v)$. \end{enumerate}

Hopefully, this helps you better understand our mechanisms.

References:

[1]: C. Soto, K. Bharath, M. Reimherr, and A. Slavkovic. Shape and structure preserving differential privacy. In Advances in Neural Information Processing Systems, volume 35, pages 24693–24705. Curran Associates, Inc., 2022.

[2]: Matthew Reimherr, Karthik Bharath, and Carlos Soto. Differential privacy over Riemannian manifolds. In Advances in Neural Information Processing Systems, volume 34, pp. 12292–12303. Curran Associates, Inc., 2021.

Thank you for your detailed review and constructive feedback. We are confident that our response has addressed your concerns. If there are any additional points requiring clarification or refinement, please let us know. We would greatly value any additional thoughts you may have on our submission.