Approximate Differential Privacy of the $\ell_2$ Mechanism

Thanks for the review!

Some parameter ranges for the experiments could need more motivation, e.g. why $d=100$ everywhere?

Our experiments focus on the $d \leq 100$ setting to highlight the range where the $\ell_2$ mechanism offers the largest improvement over both Laplace and Gaussian noise. As noted at the end of Section 4.2, the gap between $\ell_2$ and Gaussian noise shrinks to $<1$% at $d=350$ (and essentially vanishes for larger $d$). If desired, we can add more language highlighting this behavior.

Connected to the preceding point, the improvement over the Gaussian/Laplace mechanism seems concentrated to moderately small $d$ for reasonable $(\varepsilon, \delta)$.

We agree that the $\ell_2$ mechanism's improvement is concentrated to moderate $d$ (e.g., $d < 500$, and most notably on $d < 100$). Regarding the privacy regime, we note that the curve in the left plot of Figure 1 looks essentially the same in higher ($(0.1, 10^{-7})$-DP) and lower ($(10,10^{-3})$-DP) privacy settings, as mentioned at the end of Section 4.2.

From the discussion in Section 4 regarding Figure 1, it seems as if the mean squared error of the $\ell_2$ mechanism approaches that of the Gaussian as $d$ increases for general settings of $(\varepsilon, \delta)$. Is this true in general, and if so, is there a simple argument for why that is? I think the improvement for small $d$ is interesting in its own right, but it would be useful to know if there is any benefit to using the mechanism for larger $d$.

Our experiments demonstrate that the $\ell_2$ mechanism error converges to Gaussian mechanism error as $d$ increases, irrespective of the $(\varepsilon, \delta)$ regime. However, we do not have a formal proof that this holds. A possible intuitive explanation is that the $(\varepsilon, \delta)$-DP $\ell_2$ mechanism ``spends its $\delta$'' violating $\varepsilon$-DP close to the origin, while the Gaussian mechanism continues doing so arbitrarily far into its tails (and thus can incur arbitrarily high privacy loss). The result is that the $\ell_2$ density peaks at a smaller $\ell_2$ distance than the Gaussian density at the same $(\varepsilon, \delta)$-DP guarantee, but this difference shrinks as $d$ grows. This partially explains why the $\ell_2$ mechanism error approaches the Gaussian mechanism error as $d$ grows, though it does not explain why the chosen $\sigma$s necessary for DP lead to this behavior.

Does the computation in Figure 5 meaningfully depend on $(\varepsilon, \delta)$? I could believe that $d$ has no influence, but it is not clear to me if the computation becomes prohibitive for certain regimes of $(\varepsilon, \delta)$.

We do not believe that the ($\sigma$) computation in Figure 5 meaningfully depends on the exact privacy parameters within typical ranges. We tested this computation at more extreme privacy levels ($(0.1, 10^{-7})$-DP and $(10,10^{-3})$-DP) and did not encounter numerical issues. However, this might change as $e^\varepsilon$ and $\delta$ near the limits of conventional floating point accuracy.

Thanks for the review!

One missing aspect is the composition of the L2 mechanism. The Gaussian mechanism is widely used in DP-SGD due to the availability of numerical composition analysis. To better demonstrate the practicality of the proposed L2 mechanism, its composition must be studied.

We agree that analyzing composition is the logical next step for studying the $\ell_2$ mechanism. A basic approach can use existing generic composition results for pure and approximate DP algorithms, but this is unlikely to obtain better error than the Gaussian mechanism beyond a very small number of compositions. Possible alternative approaches include:

1. Investigating advanced composition for mechanisms that satisfy simultaneous (and nontrivial) pure and approximate DP guarantees. For example, at $d=50$, at $\sigma \approx 0.5$ the $\ell_2$ mechanism is both $(1, 10^{-5})$-DP and $\approx 2$-DP. We are not aware of advanced composition bounds that can take advantage of both guarantees.

2. Analyzing the moment generating function of the privacy loss random variable. Such an analysis could provide better privacy accounting using CDP or RDP or FFT-based privacy accounting. As demonstrated in the paper, even deriving tail bounds for the privacy loss distribution is already involved, but it is possible that some kind of moment analysis can be done.

We suggest that results in this direction are a good candidate for future work.

In Figure 1, the L2 mechanism exhibits a similar error to the Gaussian mechanism when d >100. In DP-SGD, where the dimensionality often exceeds 1000, does this imply that the L2 mechanism has comparable error to the Gaussian mechanism? If so, what is the advantage of using the L2 mechanism? It appears that the L2 mechanism achieves lower error for moderate d, but this benefit may not be significant in applications like DP-SGD.

Yes, our experiments show that the $\ell_2$ mechanism's error converges to the Gaussian mechanism's error as $d$ grows, and at $d=1000$, the gap is essentially 0 (a short discussion of intuition for this effect appears in our response to Reviewer Vdrp). We therefore agree that the $\ell_2$ mechanism does not meaningfully improve over the Gaussian mechanism in very high-dimensional settings. However, we suggest that the moderate-$d$ setting covers many practical problems and is therefore still worth studying. If desired, we can add a short discussion highlighting this guidance for the dimension ranges where $\ell_2$ noise is most useful.

A related concern arises in Figure 6, where the sampling process for the L2 mechanism appears less stable. If d >1000, will the sampling time increase compared to the Gaussian mechanism? If so, this could be a notable limitation, as the additional computational overhead may not be negligible.

The $\ell_2$ mechanism is a constant factor (in $d$) slower in our implementation. However, we note that both the $\ell_2$ and Gaussian mechanism sampling algorithms are parallelizable, and the parallelized runtime is independent of $d$. The experiments provided here do not attempt this parallelization, which is why their runtime increases with $d$. As described in Section 3.2, in a parallel setting, the $\ell_2$ sampler adds one more map and combine step over the Gaussian sampler. In a parallelized system, we expect that this cost is mild.

Thanks for the review!

I checked some of the early lemmas and the results seemed sound. However, the communication of the theory I found to be unpleasant. I'm not sure I've ever seen so many lemmas without a single theorem. The bulk of the paper reads more like an appendix … [t]he theory of the paper is also very unpleasant to read. Major theorems should be organized and presented as the key results. Especially novel lemmas certainly can as well, but the rest should be in the appendix.

The paper's current presentation attempts to highlight the main conceptual ideas of the privacy analysis in the main body while deferring most of the calculations to the appendix. We chose this presentation because direct approximate DP analyses of additive noise mechanisms are rare in the existing literature, and we believe the form of the analysis is interesting. Since the overall analysis has a single end goal (an approximate DP guarantee), describing the constituent results as lemmas seemed appropriate. If it seems helpful, we can add an overall privacy theorem.

The related work section was quite lacking. 4 papers are mentioned in field that has existed for 20 years. I understand that the authors are working with approximate DP, where as a lot of related methods work on pure, but the authors should still do a better job placing their work within the context of the broader literature.

To the best of our knowledge, this section discusses all of the existing work on the $\ell_2$ mechanism, and the Laplace and Analytical Gaussian Mechanisms discussed elsewhere are the most relevant baselines. Do you have other references in mind?

While the mechanism looks like it is wrapped up in an exponential type mechanism, it can also be viewed as an additive perturbation where $\tilde T(X) = T(X) + Z$ where $Z$ is distributed as an "l2" random variable. In that sense, there are a lot of options available for pure/approximate DP that can be discussed.

The suggested additive noise perspective is also valid (and appears in the discussion of the $K$-norm mechanism in Lemma 2.4). We agree that other additive noise mechanisms exist, and as mentioned above, to the best of our knowledge the most common mechanisms in theory and practice for computing an $\ell_2$ sensitive statistic are the variants of Laplace and Gaussian noise featured in the paper (though additional references are welcome!).

In fact, the distribution used in the paper has been viewed as a multivariate version of the Laplace distribution (there are multiple extensions).

Can you elaborate on this? The multivariate Laplace distribution depends on $\ell_1$ distance to the true statistic, but the $\ell_2$ mechanism depends on $\ell_2$ distance. In what sense is the $\ell_2$ mechanism a multivariate version of the Laplace distribution?

In general the paper is a very narrow contribution as they study a very specific type of DP for a very specific mechanism that doesn't seem to be used much in the literature.

We agree that the $\ell_2$ mechanism is not currently common in the literature, in part because our paper is the first to prove a (nontrivial) approximate DP guarantee for it. As the results in the paper show, this approximate DP analysis enables the $\ell_2$ mechanism to obtain lower error than the Laplace and Gaussian baselines, which appear in most DP papers. Approximate DP is the most common notion of DP in the literature and in practice. For example, it is the primary definition used in usability studies of DP [1, 2] as well as industry deployments [3, 4, 5]. Can you elaborate on why it might be considered "a very specific type of DP"?

[1] https://arxiv.org/abs/2302.11775

[2] https://arxiv.org/abs/2406.12103

[3] https://journalprivacyconfidentiality.org/index.php/jpc/article/view/782

[4] https://arxiv.org/abs/1909.01917

[5] https://arxiv.org/abs/2201.11603