Purifying Approximate Differential Privacy with Randomized Post-processing

Thank you for reviewing our paper and for raising the questions!

Major concern

Thank you for raising this thoughtful question. We will add a detailed discussion of this baseline in the revision.

The baseline you described—purifying a $(\epsilon, \delta)$-DP mechanism via discretization using a $\Delta$-net—is indeed interesting and shares some similarities with our method (e.g., dependence on $\delta$ and $d$). However, implementing this baseline efficiently is not straightforward in general domains.

A key difficulty is the explicit construction of the $\Delta$-net and efficient sampling from it. If the domain is a hypercube, then one can construct a uniform grid and sample efficiently; in that case, the utility of this baseline can be comparable to our method. However, when the domain is an $\ell_q$ ball with $q<\infty$ (e.g., $q=1,2$), explicitly constructing a $\Delta$-net and uniformly sampling from it with polynomial computation complexity in $d$ becomes more challenging.

One clue to the difficulty comes from the geometry of $\ell_q$ balls in high dimensions: most of the volume concentrates near the boundary. As a result, any sufficiently fine covering net must include many points near the surface. Furthermore, although uniform sampling is not strictly necessary—purification only requires a distribution with a lower-bounded PMF—this geometric property suggests that using an “enlarged” $\ell_q$ ball to simplify sampling would not help, since the ratio of the volumes of the original and enlarged balls becomes exponentially small in $d$. Alternatively, if one uses an enclosing hypercube ($\ell_\infty$ ball) to simplify the $\Delta$-net construction and sampling, this introduces a mismatch between the $\ell_q$ and $\ell_\infty$ norms. As a result, the expected $\ell_q$ error will carry an additional factor of $d^{1/q}$ due to the conversion between norms.

In contrast, our method is efficiently implementable for general domains with diameter $R$. In Algorithm 1, we purify over a set $\Theta$ that contains $\text{Range}(\mathcal{M})$ (specified in the input line of Algorithm 1). As discussed in Remark 3 (lines 134–135), $\Theta$ can be chosen as an $\ell_q$ ball that contains the range of the approximate DP algorithm. Its construction is simple: if $\text{Range}(\mathcal{M})$ has $\ell_q$ diameter $R/2$, we can take $\Theta$ to be an $\ell_q$ ball of diameter $R$ centered at any point in $\text{Range}(\mathcal{M})$. Uniform sampling from $\ell_1$, $\ell_2$, and $\ell_\infty$ balls can all be done with $O(d)$ time.

Regarding the parameters $r$ and $R$: if $\Theta$ is an $\ell_q$ ball of diameter $R$, then $r = R/2$. We include $r$ for flexibility—for example, $\Theta$ could be a thin rectangular band of width $2r$ and length $R$—but $r$ can be eliminated in the standard $\ell_q$-ball case.

Finally, we would like to emphasize that even if the $\Delta$-net method can be implemented efficiently on general domains, our paper remains significant, as the adaptation of approximate DP methods to achieve optimal utility under pure DP in various settings has not been previously studied. The $\Delta$-net discretization-based approach should be viewed as an alternative to the algorithm we proposed.

Thanks again for raising this question, and we will add a section in the appendix to discuss this approach thoroughly.

Minor concern

Thank you for your question. We did compare our results to baselines and lower bounds in Section 4-6 when we formally state the results for each problem in Table 1. We will make the comparisons with information-theoretic lower bounds more clearly tabulated in the final version. A quick summary below for your convenience.

Rows 1-2 (DP-ERM): Our results match the lower bounds from Table 1 in [BST14] (up to logarithmic factors).

Row 3 (DP-Frank Wolfe): our result matches a lower bound proved in Lemma 28 (up to logarithmic factors).

Row 4 (PTR type): To our knowledge, there isn’t a pure DP mechanism that works in this setting, so there isn’t a baseline. We can try constructing a packing lower bound and include it in the final version.

Row 5 (Margin-based Mode Release): It matches the lower bound in Proposition 1 of [CHS14] (up to logarithmic factors)

Row 6 (Linear Regression): Under the assumption of bounded data and parameter space, our result matches the lower bounds from Table 1 in [BST14]. To see this, For example, in the Convex Lipschitz case, the [BST-14] lower bound is $\Omega(L\|\Theta\|d/\epsilon n)$ when we choose $L$ to be an upper bound of the gradient norm $\|x(x^T\theta - y)\|$ (assume $|y| \leq \|\mathcal{X}\| \|\mathcal{\Theta}\|)$ we can take $L = \|\mathcal{X}\|^2 \|\mathcal{\Theta}\|$) this matches our upper bound. Similarly, in the strongly convex case, the [BST-14] lower bound is $\Omega(L^2d^2/\epsilon^2 n^2 \lambda)$, which also matches our upper bound when substituting the $L$ parameter above and choosing $\lambda = \lambda_{\min}$.

Row 7 (Query Release): Our result matches the utility upper bound of the SmallDB algorithm (and private multiplicative weights) up to logarithmic factors, which represents the state-of-the-art for pure DP query release. Whether this rate can be further improved is a well-known open question in the DP theory community.

Thank you for reviewing our paper and for raising the questions!

Q1: Mechanism Design

Designing pure DP mechanisms is more challenging than designing approximate DP mechanisms.

• While every $\varepsilon$-DP mechanism trivially satisfies $(\varepsilon, \delta)$-DP for any $\delta > 0$, the reverse is not true. Approximate DP mechanisms do not necessarily satisfy pure DP. This strict containment makes the design space for pure DP strictly smaller and harder to work with.

• From an algorithmic perspective, the set of known techniques for constructing pure DP mechanisms remains limited (we provide a more detailed discussion in the introduction). A key contribution of our paper is the purification technique, which offers a computationally efficient reduction from the design of pure DP mechanisms to that of approximate DP mechanisms. As shown in Section 4.1, for DP-ERM problems, existing pure DP mechanisms either suffer from computational inefficiency (e.g., the exponential mechanism; Table 2, Row 3) or suboptimal utility due to relying on basic composition (e.g., the Laplace mechanism; Table 2, Row 1). In contrast, our purification method achieves both computational efficiency and near-optimal utility under pure DP guarantees, through purification of DP-SGD using the Gaussian noise.

• Regarding the use of $\log(1/\delta) \approx d$, this approximation is used only to preserve utility guarantees when comparing with state-of-the-art pure DP mechanisms. Our purification algorithm can be applied to mechanisms with larger $\delta$, but in such cases, the resulting utility may no longer be (nearly) optimal.

Q2: Rate Discrepancies

In Table 1, Theorem 4 provides the utility guarantee for the DP Frank-Wolfe algorithm, which is designed to solve the DP-ERM problem under an $\ell_1$-ball constraint on parameter space. In contrast, Theorem 7 addresses DP linear regression under unconstrained parameter space (as described in Algorithm 13). These two problems have different constraint sets, objective functions, and are solved by different classes of algorithms, so it is not surprising that their convergence rates with respect to $n\varepsilon$ are not the same.

Q3: Norms

Thank you for this interesting question. To extend the conversion from TV distance to infinity-Wasserstein distance (Lemma 6) for a more general norm $\Vert \cdot \Vert_{gen}$, the key is that the Lebesgue measure of the unit ball $\\{x:\Vert x \Vert_{gen}<1\\}$ can be explicitly calculated or lower bounded. For a general norm, this may not be guaranteed. Please refer to the response to Reviewer tAS6 for the proof sketch: The Lebesgue measure of the unit ball, together with density (i.e., Radon–Nikodym derivative with respect to the Lebesgue measure) lower bound $p_{min}$ gives the lower bound of the $\nu$-measure of the small ball constructed in the expansion band.

We would also like to point out that the $\ell_q$ norm is already quite general. In fact, for obtaining pure DP mechanisms through adding Laplace noise, the $\ell_1$ version $W_{\infty}^{\ell_1} (\mu, \nu)$ is sufficient. In addition, for obtaining pure Gaussian DP mechanisms through adding Gaussian noise, the $\ell_2$ version $W_{\infty}^{\ell_2} (\mu, \nu)$ is sufficient.

Q4: Notation

Thank you for pointing this out. We will clarify the notation $O_p(\cdot)$ in the next version. It denotes stochastic boundedness—roughly speaking, the quantity is bounded with high probability. For a formal definition, please refer to Section 2.2 of [Va00]. In our context, $O_p(k / n\varepsilon)$ indicates that the Laplace query error is bounded by $k / n\varepsilon$ with high probability. The $p$ in $O_p ( \cdot )$ is unrelated to the $p$ used in the $L_p$ norm; it stands for "in probability".

Reference:

[Va00] Van der Vaart, Aad W. Asymptotic statistics. Vol. 3. Cambridge university press, 2000.

Regarding your comments on weakness

For many of the settings we consider, there are no known pure-DP mechanisms that achieve comparable utility or computational guarantees. For example: (1) there is no pure DP counterpart to the propose-test-release framework; and (2) existing pure DP methods for DP-ERM are either suboptimal in utility or incur computational overhead (see Table 2).

Regarding the concern that our “general theoretical framework is too abstract to yield meaningful practical benefits”: We would like to emphasize that our purification algorithm is easy-to-implement. In most cases, it involves adding properly calibrated Laplace noise to the output of an approximate DP algorithm. For discrete outputs, it may additionally include a straightforward binary encoding step. Both are computationally efficient. In addition, it leads to pure DP algorithms with strong utility guarantees across a variety of applications, as demonstrated by the near-optimal utility guarantee shown in Table 1. (Please also refer to our response to Reviewer XywD for further details.)

Thank you for your support and your question!

To prove Lemma 6, we use an equivalent definition of infinity-Wasserstein distance (see Lemma 12 in our manuscript for more details, or Proposition 5 of [GS84]):

where the $\alpha$-expansion of $U$ is denoted by $U^\alpha := \{x \in \Theta : \|x-U\|_q \leq \alpha\}$.

This definition does not involve the coupling, and gives a geometric interpretation by comparing the probability measures on open sets and their expansion. This makes it compatible with the TV distance because TV distance compares the probability measures on the same measurable sets: $TV(\mu, \nu) = \sup_{U \in \mathcal{F}} |\mu(U) - \nu(U)|.$

We summarize the key idea of the proof: Since $TV(\mu,\nu)<\xi$, by the definition of TV distance, we have $\mu(U)\leq \nu(U)+\xi$, for any measurable $U$. To prove $W_{\infty}^{\ell_q} (\mu, \nu)\leq \Delta$, by the above equivalent definition, we want to prove $\mu(U) \leq \nu(U^\Delta)$, for any open set $U$. Hence it suffices to prove $\nu(U)+\xi\leq\nu(U^\Delta).$

Rewriting the above inequality gives $\nu(U^\Delta \setminus U)\geq \xi$.

To prove this, we prove that there exists a small $l_q$ ball in the expansion band $U^\Delta \setminus U$ such that its $\nu$-measure is greater than $\xi$. We first prove that there exists a small $l_q$ ball of radius $O(\Delta)$ in the expansion band $U^\Delta \setminus U$ intersected with the domain $\Theta$. Then, we prove that its $\nu$-measure is lower bounded by the product of its Euclidean volume (Lebesgue measure) and the assumed $p_{min}$.

The coupling is not explicitly used in this proof. However, we believe it is interesting to explore what the optimal coupling of the infinity-Wasserstein distance looks like. To the best of our knowledge, this problem is solved for 1-D cases for $\rho$-Wasserstein distance for general $\rho$, see Remark 2.28 and Remark 2.30 of [GM19]: For empirical measures, the optimal transport is given by matching the ordered values. Thanks again for your question, and we will incorporate the discussion in our revision.

References:

[GS84] Givens, Clark R., and Rae Michael Shortt. "A class of Wasserstein metrics for probability distributions." Michigan Mathematical Journal 31.2 (1984): 231-240.

[GM19] Peyré, G., & Cuturi, M. (2019). Computational optimal transport: With applications to data science. Foundations and Trends® in Machine Learning, 11(5-6), 355-607.

Thank you for your support and your questions!

Figure 1: what is the dimension used?

The dimension (of the histogram) used is d = 100. The dashed line (labelled "1.0-DP w. Laplace Mech.") is given by fixing the variance at $2/\varepsilon^2=2$ for pure 1.0-DP, regardless of $\delta$. The solid line (labelled "(1.0, $\delta$)-DP w. Gaussian Mech.") is generated using the analytic Gaussian mechanism in [BW18]. The choice of $d$ does not matter and we omitted it in the main paper. Thank you for your question, and we will include more details in the revision to help readers better understand.

confusion: sometimes the term support is used instead of range.

Thank you for pointing this out. Our purification algorithm operates over the range. More specifically, the purification operates on a set $\Theta$ that contains the (output) range of $\mathcal{M}$. We will clarify this to avoid any confusion in the next revision.

In Remark 3, the transformation is applied to DP-SGD, but typically DP-SGD has unbounded range...

The bounded domain assumption is common in theoretical work. For example, in the paper by [BST14], with which we compare. We adopt the same assumption to ensure a fair comparison.

line 190: I don't think all of these papers need to be cited.

Thank you for your suggestion. We originally included these citations to provide a more complete picture of the DP-ERM literature for interested readers. Nevertheless, we agree with your point and will revisit the citation list and cite those are relevant.

References:

[BST14] Bassily, Raef, Adam Smith, and Abhradeep Thakurta. "Differentially private empirical risk minimization: Efficient algorithms and tight error bounds." arXiv preprint arXiv:1405.7085 (2014).

[BW18] Balle, Borja, and Yu-Xiang Wang. "Improving the Gaussian mechanism for differential privacy: Analytical calibration and optimal denoising." International conference on machine learning. PMLR, 2018.