Purifying Approximate Differential Privacy with Randomized Post-processing
Authors: Yingyu Lin
Erchi Wang
Yian Ma
Yu-Xiang Wang
Venue: NeurIPS 2025 spotlight ()
Keywords: Differential Privacy
approximate DP to Pure DP conversion
Empirical Risk Minimization
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: Statistically and computationally efficient reduction from approximate DP to pure DP.

Abstract: We propose a framework to convert $(\varepsilon, \delta)$-approximate Differential Privacy (DP) mechanisms into $(\varepsilon', 0)$-pure DP mechanisms under certain conditions, a process we call ``purification.'' This algorithmic technique leverages randomized post-processing with calibrated noise to eliminate the $\delta$ parameter while achieving near-optimal privacy-utility tradeoff for pure DP. It enables a new design strategy for pure DP algorithms: first run an approximate DP algorithm with certain conditions, and then purify. This approach allows one to leverage techniques such as strong composition and propose-test-release that require $\delta>0$ in designing pure-DP methods with $\delta=0$. We apply this framework in various settings, including Differentially Private Empirical Risk Minimization (DP-ERM), stability-based release, and query release tasks. To the best of our knowledge, this is the first work with a statistically and computationally efficient reduction from approximate DP to pure DP. Finally, we illustrate the use of this reduction for proving lower bounds under approximate DP constraints with explicit dependence in $\delta$, avoiding the sophisticated fingerprinting code construction.

Purifying Approximate Differential Privacy with Randomized Post-processing
Yingyu Lin, Erchi Wang, Yi-An Ma, Yu-Xiang Wang University of California, San Diego (yi1208, erw011, yianma, yuxiangs) edu
Abstract
We propose framework to convert (c, 5) approxxittee Differential Privacy (DP) mechanisms into (c',0)-pure DP mechanisms under certain conditions, process we call "purification." This algorithmic technique leverages randomized post- processing with calibrated noise to eliminate I parameter while achieving near- optimal privacy-utility tradeoff for pure DP. It enables new design strategy for pure algorithms: first run an approximate DP algorithm with certain conditions, and then purify. This approach allows one to leverage techniques such strong composition and propose-test-relaat that require > designing pure-DP methods with 5 O. We apply this framework in various settings, including Differentially Private Empirical Risk Minimization (DP-ERM), stability- -based release, and query release tasks. To the best of our knowledge, this is the first work with a statistically and computationally efficient reduction from approximate DP pure DP. Finally, illustrate the use of this reduction for proving lower bounds under approximate DP constraints with explicit dependence ô, avoiding the sophisticated fingerprinting code construction.
1 Introduction
Differential privacy (DP), in its original form [DMNS06, Definition 11. has only one privacy parameter Over the two decades research in DP. many have advocated that DP too stringent to be practical and have proposed several relaxations. Among them, the most popular is arguably the approximate DP [DKM 066, which introduces a second parameter 5.
Definition (Differential privacy [DMNS06, DR* (R]) A mechanism M satisfies (c, 6)- differential privacy for all neighboring datasets and for any measurable set S S Range(M). it holds that:
D' (datasets differing in most one entry)
P(M(DD) E S] S P(M( S]
When 8 0. the definition is now fondly referred to E-pure DP. Choosing 8 significantly weakens the protection, as it could leave any event with probability smaller than å completely unprotected.
Two common reasons why DP researchers adopt this relaxation are: Utility gain: approximate DP perceived to be more practical, as it allows for larger utility: 2. Flexible algorithm design: Many algorithmic tools (such as advanced composition and Propose-Test- Release)lees)) support approximate DP but not pure DP, which enables more flexible (and often more efficient) algorithm design when 8 > 0 is permitted. For these two reasons, it is widely believed that the relaxation is a necessary evil.
We argue that the claim of "worse utility for pure-DP" is oftentimes myth. In some applications of DP, a pure-DP mechanism has both stronger utility and stronger privacy. For example, in low- dimensional private histogram release, the Laplace mechanism enjoys smaller variance in almost all
"Egual Alphabetical
70th Conforence Noural Information Processing Systems (NeurIPS 2025).

---

regimes except when ò is too large to be meaningful (see Figure 1). In other cases, the poor utility is sometimes not caused by an ttoooatton-tteorrticc theoretic barrier, but rather due to the second issue often much harder to design optimal pure-DP mechanisms.
In the problem of privately releasing k linear queries of the dataset in [0,1)a, may appear that pure- DP mechanisms are much worse if we only consider composition- based methods. The composition of the Gaussian mechanism enjoys an expected worst-case er-
Variance for Private Histogram Release
1.0-PP w. Laplace Mech.
11.0, 5).DP w. Gaussian
On the other hand, we wish to achieve pure DP, the composition of the Laplace mecha-
ror of Op THE
Variance
6
nism's 's error bound becomes Op( (t) However, the bound
4
can be improved to Op( Vkdy when we use a more ad- vanced pure-DP algorithm known as the K-norm mech- anism [HT10] that avoids composition.
nz
10a 10c
1.0
10*
In the problem of private empirical risk minimization (DP-ERM) [BST14], the optimal excess empirical risk of
Figure 1: Per-coordinate variance private histogram release under pure-DP and approx- imate DP with the same parameter. The dashed line is given by Laplace mechanism with pure 1. 1.0-DP, regardless
Vdlog(1/0) under approximate DP is achieved by ne
the ntisy-stochastic gradient descent (NoisySGD) mech- anism and its full-batch gradient counterpart. These methods are natural and are by far the strongest ap- proaches for differentially private deep learning as well [ACG+ 16, DBH+22) 22]. The optimal rate of O a for pure DP, on the contrary. cannot be achieved by Laplace noise version of NoisySGD, as advanced composition is not available for pure DP. Instead, requires exponential mechanism that demands delicate method to deal with the mixing rate and sampling error of certain Markov chain Monte Carlo (MCMC) sampler [LMW 24].
The solid line is generated using the analytic Gaussian mechanism in [BW18).
The issue with the lack of algorithmic tools for pure DP becomes more severe in data-adaptive DP mechanisms. For example, all Propose-Test Rest-Reaaee (PTR) style methods [DL09] involve privately testing certain properties of the input dataset, which inevitably incurs a small failure probability that requires choosing O. While sewoots-ensttiiity--eeee they require adding heavy- tailed noise, which causes the utility to deteriorate exponentially as the dimension increases.
methods [NRS07] can achieve pure DP,
1.1 Summary of the Results
In this paper, we develop new algorithmic technique called "purification" that takes any 6)- approximate DP mechanism and converts it into an (c + e')- DP mechanism, while still enjoying similar utility guarantees of the original algorithm.
The contributions of our new technique for achieving pure DP are as follows.
1. It simplifies the design of the near-optimal pure DP mechanism by allowing the use of tools reserved for approximate DP.
2. It enables an O -tyk))type composition without compromising the DP guarantee with > 0. where l is the number of composition.
3. It shows that PTR-like mechanisms with pure DP are possible! To the best of our knowledge, method is the only pure DP method for such purposes.
4. In DP-ERM and private selection problems, we show that, up to a logarithmic factor, the resulting pure DP mechanism enjoys an error rate that matches the optimal rate for pure DP, i.c., replacing the log(1/6) term with the dimension or (og((OuuuutSpace)...
Technical summary. The main idea of the "purification" technique is to use randomized post- processing approach to "smooth" out the d part of (c, 6D-.. To accomplish this, we proceed as follows. We leverage distance from a pair of hypothetical distributions that are e-indistinguishable. Next, we develop a method to convert the total variation distance to the co- Wasserstein distance. Finally, we leverage
equivalent definition of (s, 8D- that interprets 6 as the total variation

---

Table 1: Summary of applications of our purification technique for constructing new pure-DP mechanisms from existing approximate DP mechanisms. The resulting pure-DP mechanisms are either optimal or match the results of the best-known pure-DP mechanisms for the task (we include more discussion in Appendix G). DP-ERM (SC) refers to DP-ERM with a strongly convex objective function, where À denotes the strong convexity parameter of the individual loss function. DP-ERM (&1) refers to DP-ERM with an & constraint. Amin in linear regression is the smallest eigenvalue of the sample covariance matrix, x X/n. All results are presented up to logarithmic factor (in n and other parameters, but not in 1/8. We note that in the table log(1 (gg(1/0) /5) is proportional to d, the effective dimension.)
Problem
6)-P Mechanism
Utility (before purification)
Utility (after)
DP-ERM
Noisy-SGD [BST14]
Vdllgg 1/8)/
[C]2 (Thm 3)
nC dlog(1/8)
ne
DP-ERM (SC)
Noisy-SGD [BST14]
(Thm 3)
An e
An
DP-ERM (6)
DP-Frunk-VV Wolfe [TTZ14)
(log(
log nZ
(Thm 4)
(1 3213
Bounding Ajocal
PTR-type [KNRSI3, DRE 20]
1/2 Litert (L/81///
Ateral
+
(Thm 5)
Mode Release
Distance to Instability [TS13]
(o/(1
lox MXl
(Thm 6)
Linear Regression
AdaSSP [Wan 18]
min( [o6(1/6)
min d
me Amt (Thm 7)
Amii o
Query Release
MWEM [HLMI2]
(lo
Ong BJ 2/
(Thm 8)
Vnz
(nz)
the Approximate Sample Perturbation (ASAP) technique from [LMW 24] that achieves pure DP by adding Laplace noise proportional to the co- xo-Wasserstein distance. A challenge arises because the output distribution of generic (e, 8DP mechanism is not guaranteed be supported on the entire output space, which may invalidate a tight TVV distance to W 0c conversion. We address this by interlacing a very small uniform distribution over a constraint set. Another challenge is that, unlike in [LMW 24], where the e-indistigguisablle distributions correspond to pure DP mechanisms on neighboring datasets, here the hypothetical distribution may depend on both neighboring datasets rather than just one. This prevents the direct application of the standard DP analysis of the Laplace mechanism and the composition theorem. To address this, we formulate our analysis in terms of the indistinguishabiiity of general distributions rather than Dp-spccific language. We use Laplace perturbation lemma and the weak triangle inequality, leading to a clean and effective analysis. Moreover, we show how the dimensionnredduction technique can be used so the purification technique can be applied to discrete outputs and to sparse outputs, which ensures only logarithmic dependence in the output-space cardinality or dimension.
1.2 Related Work
The idea of using randomized post-processing to enhance privacy guarantees has been explored in prior work [FMTT18, MV22, LMW+ [FMTT18] focus on Rényi differential privacy, while [MV22, L4 study the implementation of the exponential mechanism, specifically perturbing Markov chain Monte Carlo (MCMC) samples to obtain pure DP guarantees. Our work builds on [LMW+24]], where we generalize the domain assumption of [LMW 24, Lemma 8] and extend the approach to more general upstream approximate DP mechanisms, such as DP-SGD [ACG* 16, DBH 22]. We also discuss the connection to the classical statisties literature randomized post- processing given by [B+51, Theorem 10] in Appendix B.
Previous works have investigated the purification of approximate differential privacy into pure DP, but limited to settings with finite output space. A straightforward uniform mixing method can purify approximate DP mechanisms with finite output spaces, as summarized in [HC22], and we further discuss it in Appendix C. [BGH+23] first transform an approximate DP mechanism into a replicable one, and then apply pure DP selection procedure obtain pure DP mechanism at the cost of increased sample complexity.
2 Algorithm: Converting Approximate DP to Pure DP
In this section, we propose the purification algorithm (Algorithm 1) which converts (s, d)) d'-apppoxee DP mechanisms with continuous output spaces into c'purre DP mechanisms under certain conditions. The algorithm consists of two steps: (1) mixing the approximate DP output with uniform distribution
Presented |BGH* Algorithm 1I, algorithm can achieve a pure DP guarantee by replacing the appeusimate DP selection step a pure DP alternatvee.
3

---

(Line 3), and (2) adding Laplace noise calibrated to 8' (Line 4.) Intuitively, the first step is to enforce bound on the oo- So-Wasserstein distance (Definition 5), which can be loosely interpreted a randomized analogue of & sensitivity. The second step adds Laplace noise proportional to this Wasserstein bound to guarantee pure DP. This step hased on techniques from [SWC17, LMW+24), and can be viewed as the generalization of the Laplace mechanism. The privacy and utility guarantee of Algorithm I are provided in Theorem 1.
Algorithm 1: Apure (Tapx: O, 6, w): Purification of Approximate Differential Privacy
1 Input: Privacy parameters E, 6, additional privacy budget e', an output Tapx of an (e, 6)-DP algorithm M satisfying Assumption I, an Eg ball e as Assumption 1, the mixture level
2 Set A -2d--=
Lemma 6.
2w
3 With probabilityy 1 w, x Tapsi otherwise, sample Uni Uniform Mixing
Tuur f- x + Laplace (2A/E')
5 Output: Zpure
Notations. Let X' be the space of data points, X == Un be the space of the data set. For
1/9 For
vector y = (U1,..., va) E Rd and q 2 1, we define its nnrm as ||u||g = Ed M:
set S C CRd, we denote its l nn-norm diameter Diam, := sup,, xess s || - ullg- For a (randomized) function M : X' + Rdd we denote its range as Range(M) = (M(D): D E X²
Assumption 1. The (e, DDP algorithm M satisfies Diam, (Range(M) S R. Specifically, it lies in an bg ball of radius R. denoted by O.
Theorem Define pure Taps as Algorithm 1 uunder Assumption 1. The output of Algorithm I satisfies (e + DDP with utility guarantee
4Rd 8
E purre Tepelli 11 S SRR+ +
2w
The detailed proofs are deferred to Appendix E and Appendix For clarity, Theorem presents the utility guarantee in the & norm. Extensions to general Ep norms follow directly from bounding the expected l, norm of the Laplace noise (see Equation (5)).
When applying Algorithm to various setlings shown in Table 1, the utility bounds either match the known cooomatiiontthoreee mechanisms for the task. By the parameter setting given in Line of Algorithum 1, the log(1/5) factor in the utility bounds can be replaced by d, omitting the logarithmic factors. In Section 4.2, we further show how dimension-reduction techniques can be used when applying purification to settings with sparsity conditions.
Remark 2
lower bounds for pure DP or the best-known pure-DP
Remark 3 Parameter choices of Algorithm 1 for different setlings are provided in later sections. For example, parameters for the purified DP-SGD are given in Corollary 4, Note that in Algorithm 1, we only require the range of M be a subset of the ba-ll O where O can be selected as & balls (g = L), l balls (q = 2), or hypercubes (q 20), which admits simple O(d)-runtime uniform sampling oracles.
Corollary 4 (Parameters of Algorithm 1 for DP-SGD) Let M: + O be an (E, 6DD mech- anism, where O C Rdd is an & ball with E2-diameter C. Let Vaps be the output of M. Set the mixture level parameter as w = n2 and set (16Cdn2'a-- Then, Apure (Tap.. O, = E, 5, w) satisfies 2e-DP
2n
guarantee with utility bound [B[[ xxpx S - C.
The purification algorithm can be applied to finite output spaces. The key idea is to embed the elements in the finite output space into hypercube using the binary representation. Given a finite output space )' (1,2, 3, ..... 2dd = []
first map each element its binary representation in (0, 1 Id Then, we apply Algorithm on the cube [0, 1]d in the Euclidean Space RR.. The procedure outlined in Algorithm with DP and utility guarantees provided in Theorem 2, and the proof deferred to Appendix F.

---

Algorithm 2:
Apure discrete (c, 6, Mapx: 3): Binary Embedding Purification for Finite Spaces
Input: privacy parameters E, binary representation mapping BinMap [2d] + {0, 10.
output Uapx from (s, 6)-DP mechanism M X +
[2n].
2 Zhin BinMap(
b Binary embedding
Apure (Ahin: O [0, 1,,1), = & = 2 2-4) Purify the embedding by Algorithm I
3 Epure f-
4 Zround f- Round (0.1)" (Spare)
> Round (o.)<((())) = (1 2 0.5))
5 Upare <- BinMap (2round)
Decode index back to decimal integer index
6 Output: Upure
Theorem If 8 < (2d)aá then Algorithm 2 satisfies (2e, -)-uue DP with utility guarantee
[Mapx
Upwre] > 2 ge-d
Technical Lemma: from TV distance to oo- Wasserstern distance
In this section, we present technical lemma that proofs the uniform mixing step in Algorithm 1 (Line 3) can enforce an oc-Wasserstein distance bound, as mentioned in Section 2. This oo- Wasserstein bound is key step our analysis, enabling the subsequent addition of Laplace noise calibrated to this bound to ensure pure DP. See Figure 4 for a summary of the privacy analysis. We define the oo- Wasserstein distance below. Additional discussion can be found in Appendix A.
Definition The oc- Wasserstein distance between distributions and v is on a separable Banach space (θ, || (1l) is defined as
Whs (H,, == inf sus | ylly TETc(u.)) (u.u)>>
inf {a ((aa))>> [|l - yll, S a] = =1}, velc(u.))
where [e(u,, v) is the sel of all couplings of and v. The expression ess (2,()) denotes the essential supremum with respect to the measure 7/-
By the equivalent characterization of approximate DP (Lemma 14), we can derive TV distance bound between the output distributions of the (c, 6)-P mechanism on neighboring datasets and pair of distributions that are e-indistinguishable. Our goal is to translate this TV distance bound into a W 8o distance bound. In general, the total variation distance bound does not imply bound for the Wo distance. However, when the domain is bounded, we have the following result.
Lemma (Converting drv to Woe) Let q 2 and let diameter R and containing an ba-ball of radius Let μ and v be two probability measures on θ Suppose v the sum of two measures, V vo + 1/, where Vi is absolutely continuous with respect to the Lebesgue measure and has density lower-bounded by constant Puin over Q while vo is an arbitrary measure. Define the W distance with respect to lg (Definition 5.) The following holds.
Rd be a convex set with norm
If (fv((H, v) < Pmin Vol(BB (1))
( Ad, then W (p, S
(1)
2d where Vol(B] (1) r(++ IT r(1+ is the Lebesgue measure the Ey noor unit ball, with T r(1+;)
being the Gamma function. E.g., VoI(IRd (1)) ((2+)) and Vol(BA (1)) = F[a+Tj In particular, the domain θ an Eq-ball, then the term ( Eq. (1) can be improved 4.
2//2
2d
This result builds on [LMW+22] while generalizing its domain assumption from the f2-balls to more general convex sets. In the proof provided in Appendix F, instead of relying on [LMW+24, Lemma 24], which applies only to balals,, construct convex hull that extends more general convex sets. We provide the proof sketch as follows.
Proof sketch of Lemma 6 To prove Lemma 6, we use an equivalent, con-coupling-basee definition of the infinity- Wasserstein distance:
Lemma ([GS84), Proposition 5) Define μ, v and Woo as Definition 5. Then,
W'x (1,, v) inf 0: m(U) S vUU)), for all open subsets U (C)), where the a-expansion of U is denoted by U = {a E θ |z Ull, a).
5

---

This definition provides geometric interpretation of W (1,, u) by comparing the measure of set to the measure of a-expansion U
We summarize the key idea of the proof. Suppose (V v) Ç. By the definition of total variation distance, this implies u(U) & v(U) + ę for any mcasurable set U. To prove that W (n, v) I (for the A given in the lemma), suffices, by Lemma 7, to show that yu()) v(U for any open set U.
Given that (t)) v (t)) + E, our goal thus reduces to proving ((U) + S v(UA). Rewriting this inequality, suffices to prove:
(UAA
To establish this, we show that the "expansion band" U \ U must contain sufficient mass. We use the convexity of θ to argue that this band must contain a small e, ball of specific radius (related to A). We then use the minimum density Pmin and the Lebesgue measure of this E ball to lower-bound its y-measure. The value of in the lemma statement is chosen precisely so that this lower bound (and thus v(U \ U)) is at least E, which completes the sketch.
The conversion lemma requires one of the distributions to satisfy a minimum density condition (the "Pmia"") "-) This motivates the uniform mixing step in Algorithm 1, which ensures that the mixed distribution meets this requirement. Combining the TV bound implied by (c, 5)-DP, the effect of uniform mixing, and the conversion lemma from TV distance Woo distance, we obtain a bound on the oo- Wasserstein distance after the uniform mixing step in Algorithm 1.
Example 8 (Tightness of the Conversion) Ler Å E (0,1), 1). Consider the probability distributions = Á Adspirac + (1 - Uni (BE,
(1) By (A)) and v = Unif [RC (1)) where &Dirac is the Dirac measure O, and Uni denotes the uniform distribution over the set Then, by Definition 12 and Lemma 7, we have drv (H,v) = Ad. and W (p,
This shows that the bound in Lemma is tight up to a constant. In this case, we have Pmin = (Vol(B)) (1)))= and R = 2r, so Lemma 6 gives the bound W < 82, which matches the exact value Wha Á up to constant.
Figure 2: Illustration of Example 8 on the metric space (It?, l12)
4 Empirical Risk Minimization with Pure Differential Privacy
In this section, we apply purification technique develop pure differentially private algorithms for the Differential Private Empirical Risk Minimization (DP-ERM) problem, which has been extensively studied by the differential privacy community [CMS11, BST14, KJ16, WYX17, FKT20, KLL21, GHSGT23J.
We consider the conver formulation of the DP-ERM problem. where the objective is to design differentially private algorithm that minimizes the empirical risk L(0; D) = Σ ((0; given dataset D {.1,..., Znn C Xn, convex feasible set C C Rd, and a convex loss function f x X - R. Algorithm performance measured by the expected excess empirical risk Ex(C(0) - L*, where L minsec L()).
4.1 Purified DP Stochastic Gradient Descent
The Differential Private Stochastic Gradient Descent (DP-SGD) mechanisms [BST14, ACG 16) are
the most popular algorithms for DP-ERM. These mechanisms are inherently iterative and heavily rely on (1) advanced privacy accountin/coompostionn techniques [BS16, Mir17, DRS22) and (2) amplification by subsampling for Gaussian mechanisms [BBG18, BDRS18, WBK19 19, ZW19, KJH20J.

---

Either of these two techniques results in (s, 6)-DP guarantee with ò > O. In contrast, directly using the Laplace mechanism to release gradients fails to achieve a competitive utility rate.
While the exponential mechanism [MT07, BST14] achieves optimal utility rates under (e. 0)-pure DP. this comes at the expense of increased computational complexity. Specifically, [BST14, Algorithm 2] implements the exponential mechanism via random walk over the grid points of a cube that contains C, ensuring convergence terms of max-divergence. This approach constitutes zero-order method that does not leverage gradient information. To design a fast, pure DP algorithm with nearly optimal utility, we propose pure DP-SGD method that transforms the output of an (z. 8)-DP SGD algorithm into a (s, -pure DP solution using Algorithm 1. Implementation details are provided in Algorithm 4 in Appendix H. Theoretical guarantees on utility, privacy, and computational efficiency are stated in Theorem 3.
Theorem (Utillity privaey, and runtime for purified DP-SGD) Let C. Rd be a convex set with la diameter C, and suppose that f(;z) is L-Lipschitz for every I E X. Set the parameters as specified in Corollary 4. Algorithm 4 guarantees 2e-pure differential privacy. Furthermore, using O f " incremental gradient calls, the resulting output 8 pure satisfies:
1. If f(;z) is convex for every x E X, then E [C(0pure)] 6 ------0- (CTd//c). (C(Tad())))))))
2. (+;a) is X-strongly convex every x E X, then A [C (0pure)) - S (012%/2)))
The total runtime of Algorithm 4 is (n2 + d). where each incremental gradient computation incurs cost of (dd) gradient operations, and the purification (Algorithm 1) executes in (d) time. Table 2 presents a comparison of utility and computational efficiency. Notably, the purified DP-SGD attains near-optimal utility rate, matching that of the exponential mechanism [BST14), while substantially reducing computation complexity by improving the dependence on both n and d.
Table 2: Comparison of utility and computational complexity in the la Lipschitz and convex setting under &-pure differential privacy. For simplicity, assume the data domain C has Eg diameter and the Lipschitz constant 7=1 All results are stated up logarithmic factors.
Mechanism
Reference
Utility
Runtime n²ee n² + d d'n't v d'ntt
Laplace Noisy GD
Lemma 19
d=13 (me)1/2
Purified DP-SGD (Algo. 4)
Theorem
8/ns 4/ns
Exponential mechanism
[BST14, Theorem 3.4]
4.2 Purified DP Frank-Wolf Algorithm
As noted in Section 2, applying Algorithm yields the relation log(1/6) log(e/A)) introducing an extra (d) factor due to the Laplace noise scale 4/s. While optimal in low dimensions, this factor can degrade utility for algorithms with dimension-inndeeeedenn convergence, such as the Frank-Wolfe algorithm and its DP variants [FW*5 56, TTZ14, AFKT21, BGN21]. To address this, we integrate dimenssion-rdduction and sparse recovery techniques (Algorithm 8) into our purification method (Algorithm 1). Applied to the (e, dD Frank-Wolfe algorithm from [TGTZ15, Algorithm 2), which uses the exponential mechanism and advanced composition, approach preserves dimension- independent convergence rates.
To obtain a pure-DP estimator from the approximate DP output Órw, we first apply dimension reduction, exploiting the problem's 's sparsity to project Opw into a lower-dimensional space. We then apply the purification Algorithm 1 in this space and recover the estimate in the original ambient space. The full procedure is given in Algorithm 7, with the proof of Theorem 4 deferred to Appendix I.3. Our method achieves pure differential privacy while matching the best known utility rate O(n 1/2g-1/2) as in [AFKT21, Theorem 6).
Theorem Let the domain C be an Ey-ball centered at O. Let & be the pure differential privacy parameter. Assume that the function x):x) is corvex, -y-Liscchitz, and 3-smooth with respect to the l norm for all x E X. Algorithm satisfies 28-pure differential privacy and achieves the following utility bound:
7

---

1 1 /
A [C((ppr))] -
- s
(nz)1/2
The runtime is (dd plus a single call to a LASSO solver.
The upper bound is tight with respect to n and E. We provide a lower bound in Lemma 30, which is derived using packing argument. We defer proof details to Appendix 1.4.
5 Pure DP Data-dependent Mechanisms
This section shows that our purification technique offers systematic approach for designing data-
dependent pure DP mechanisms. We present three examples: (1) the Propose- Propose-Test-Reee Test-Release (PTR) mechanism and its variant with privately released local sensitivity [DL09, KNRS13, DRE+ 20]; (2) stable value release methods, such as frequent item identification [TS13, Vad17]; and (3) linear regression algorithm using adaptive perturbation of sufficient statisties [Wan18].
5.1 Propose- Propose-Test-Relee Test-Release with Pure Differential Privacy
Given dataset D E x and query function q= X IR, the Proposs-Test-RRlaaane (PTR) framework proceeds in three steps: (1) Propose an upper bound on Locaa (D), the local sensitivity of q
(as defined in Definition 33); (2) Privately test whether D is sufficiently distant from any dataset that violates this bound; (3) If the test succeeds, assume the sensitivity is bounded by b, and use differentially private mechanism, such as the Laplace mechanism with scale parameter bys, release a slightly perturbed query response. However, due to the failure probability of the testing step, PTR provides only approximate differential privacy. By applying the purification technique outlined in Algorithm 10 in Appendix J.1, PTR can be transformed into pure DP mechanism.
Next, examine variant of the PTR framework, presented in Algorithm 11, where the output space of the query function has dimension d, and the local sensitivity ALoca(()) is assumed to have bounded global sensitivity. In this approach, Algorithm 11 first privately constructs high-probability upper bound on the local sensitivity. The query is then released with additive noise proportional to this bound, and the purification technique is applied ensure pure DP release. This method enables an adaptive utility upper bound that depends on the local sensitivity, as established in Theorem 5. The proof is provided in Appendix J.2.
Theorem Algorithm satisfies 3e-DP. Moreover, the output Opure from Algorithm 11 satisfies
(ocall
d3/2)
Ellle (D)1aa s Ō
E
E2
5.2 Pure DP Mode Release
We address the problem of privately releasing the most frequent item, commonly referred to as mode release, argmax release, or voting [DR 14]. Our approach follows the distance- to to-instabiliity algorithm, Adist, introduced in [TS and further outlined in Section 3.3 of [Vad17]. Let X' denote finite data universe, and let D E X" be a dataset. We define the mode function f f X - X. where f(D) returns the most frequently occurring element in the dataset D.
Theorem Let D E X be a dataset. Algorithm 12 satisfies 2e-DP and runs time O(n log ). Furthermore, if the gap between the frequencies of the two most frequent items exceeds Q (log [x] log(log (x1/e\/s), Algorithm 12 returns the mode of D with probability at least O1//xi).
The proof is provided in Appendix J.3. Consider the standard Laplace histogram approach, which releases the element with the highest noisy count. To ensure that the correct mode is returned with high probability, the gap between the largest and second- largest counts must exceed O (log /x))s) [Vad17, Proposition 3.4]. Our result matches this bound up log log X factor.
5.3 Pure DP Linear Regression
We conclude this section by presenting pure DP algorithm for the linear regression problem. Given fixed design matrix X E X C Randd and a response variable E y R², we assume the existence of 8" E θ such that Y = X0" The non-private ordinary least squares estimator (X XXX requires computing the two sufficient statistics: X XTX X and X Y. These can be privatized using Sufficient Statisties Perturbation (SSP) [VS09, FGWC16) or its adaptive variant, AdaSSP [Wan18], to achieve improved utility.
8

---

To facilitate the purification procedure, we first localize the output of AdaSSP by deriving high- probability upper bound. This bound is then used clip the output of AdaSSP, after which the purification technique is applied. Implementation details are provided in Algorithm 13, and the corresponding utility guarantee is stated in Theorem The proof is deferred Appendix J.4.
Theorem Assume X' X is positive definite and || X the output pure of Algorithm 13 satisfies:
|| 11 Then, with high probability,
(d) [ (
d
P1
MSE((ppur)) S Ô
(2)
EZn² Xmin
mE
Here, Amin denotes the normalized minimum eigenvalue, defined Amin (X (xT X/n), and MSE denotes the mean squared error, given by MSE(0) = I -00E
We note that [AD20] also proposes an D-DP mechanism for linear regression using the approximate inverse sensitivity mechanism, which has an excess mean squared error of O (dE tr( x//)/n==>). where I, is the Lipschitz constant of the individual mean squared error loss function. We make two comparisons: (1) compared to the utility bound in [AD20, Proposition 4.3], Theorem7 avoids dependence on the Lipschitz constant, which in turn relies on the potentially unbounded quantity ||+||: (2) both algorithms exhibit a computational complexity of O(d + d²). Nonetheless, the inverse sensitivity mechanism entails further computational overhead due to the rejection sampling procedure ([AD20, Algorithm 3)).
6 Pure DP Query Release
We study the private query release problem, where the data universe is defined as X' = {0, 1)d and the dataset is represented as a histogram D E Nl satisfying || n. We consider linear query functions q X' + [0, 1]. where q E Q. and the workload Q consists of K distinct queries. For convenience, define QDD) := ( - 91 (d.)..... A (x())) Our goal is to release privatized version of QDD) that minimizes the fx error.
E
Our algorithm, described in Algorithm 16, proceeds in three steps: (1) the multiplicative weights exponential mechanism [HLM12] is used to release synthetic dataset; (2) subsampling is applied to this synthetic dataset to further reduce its size; (3) the subsampled dataset encoded into binary representation and then passed through the purification procedure (Algorithm 2). The subsampling step necessary to balance the additional error introduced by purification, which depends on the size of the output space. The privacy and utility guarantees are formalized in Theorem 8, with the proof deferred to Appendix K.2.
Theorem 8 Algorithm 16 satisfies 2a-DP, and the outpul Dprre of the following utility guarantee:
dl/3
B[I[(()) - Q(D Ô
1/3
Moreover, the runtime of the algorithm is Ö(nK + |X + 2/3 /3/3
We emphasize that our algorithmic framework (Algorithm 16) is flexible. The upstream approximate instantiated using MWEM [HLMI2]- be
differential privacy query release algorithm- replaced with other (s, DDP algorithms, such as the Private Multiplicative Weights method [HRI0] or the Gaussian mechanism. Our approach achieves the tightest known utility upper bound for pure DP, as provided by the Small Database mechanism [BLR13), while offering improved runtime.
7 Purification as a Tool for Proving Lower Bounds
In this section, we demonstrate that the purification technique can be leveraged to establish utility lower bounds for (e, 6) -iifferretiill private algorithms. Lower bounds for pure differential privacy mechanisms are often more straightforward to derive, commonly relying on packing arguments [HT10, BBKN14]. In contrast, establishing lower bounds for approximate DP mechanisms typically requires more intricate constructions, such as those based on fingerprinting codes [BUV14, DSS + 15, BSU17, LLL21, SU16].
We begin by providing the intuition behind how the purification technique can be used to prove lower bounds for approximate DP. Suppose there exists (E,8)- DDP mechanism with ó within appropriate

---

range such that log(1/6) ~ ((d) and an error bound of O (d log (1/05=))))mme)) for some constant E (0, 1), and we assume the output space is bounded set in R. Then, Theorem I and Remark 2 imply that it is possible to construct 2r-DP mechanism with an error bound of O (4/e), where O omits logarithmic factors. This provides new approach to proving lower bounds for (c, (C algorithms via contrapositive argument:
If no D(ee-DD mechanism exists with an error bound Ô ( ((e), then no (e, 5)D mechunism can achieve an error bound of O (1 tog' =(16)/ac) for all appropriate 6, for any e E (0, 1).
We apply this approach derive the lower bound for (e, d)-P mean estimation task. Specifi-
cally, let the data universe be 'D == {-1/va, 1/vaz" and consider dataset D = --...... Fn S
1/va, 1/vaja a The objective is to privately release the column-wise wise empirical mean D 24 [-1/va, 1/vaj" For pure DP we have the following lower bound:
Lemma (Lemmaa 5.1 in [BST14], simplified) For any E-pure DP mechanism M, there exists a dataset D {-1/va, //aaaaa such that with probability at least 1/2 over the randomness of M, have [IM DI12 Ω (.))
By applying the purification technique with an appropriately chosen and contrapositive argument based on Lemma 9, we obtain the following (c, dddfiferren privacy lower bound, as stated in Theorem 9. We defer proof to Appendix L..
2d ) For any (E, DDD mechanism M, there exist a dataset D {-1/va, 1/vajaxd such that with probability at least 1/4 over the randomness of M. we have
Theorem 9 Let E S O(1), and ö E (exp(-4d log(d) log² (nd)), (nnd)) 4n 4n
[M((D) - D112= 5
y /loo(1188)
En
Here, 51(+) hides all polylogarithmic factors, except those with respect to 8.
Remark 10 For mean estimation under (s, S)DP with exponentially small 8, we can also establish ((d)) lower bound via packing argument, detailed in Appendix L.3.
Additional examples illustrating the use of the purification trick derive lower bounds is provided in Appendix L.2, which includes bounds for one-way marginal release and private selection.
8 Conclusion and Limitation
In this paper, we introduced novel purification framework that systematically converts approximate DP mechanisms into pure DP mechanisms via randomized post-processing. Our approach bridges the flexibility of approximate DP and the stronger privacy guarantees of pure DP, Our purification technique has broad upplicability across several fundamental DP problems. In particular, a faster pure DP algorithm for the DP-ERM problem that achieves near-optimal utility rates for pure DP. We also show that method can be applied to design pure-DP PTR algorithms. A limitation of our approach is that when applying this continuous purification framework to mechanisms with a finite output space, the utility bound incurs additional log log | factor compared to prior work, where | is the output space cardinality. Nonetheless, to our knowledge, this is the first systematic purification result applicable to continuous domains. Future work includes extending framework to more adaptive settings and refining its applicability to high-dimensional problems.
propose
Acknowledgments
The research partially supported by NSF Awards #2048091, CCF-21 (TILOS), DARPA AIE program, the U.S. Department of Energy, Office of Science, and EDC-REF-FTT-2--OO from the CDC's Center for Forecasting and Outbreak Analytics. We thank helpful discussion with Abrahdeep Thakurta, who pointed us towards proving the packing lower bound pure-DP DP-ERM under the LI constraints (Lemma 30). We also thank anonymous reviewers from TPDP'25 for the reference to the folklore that mixing a uniform distribution alone suffices for "purifying" approximate DP in the discrete output space regime, as well as the anonymous reviewer from Neurips 2025 for a simple purification approach for Euclidean spaces that extends this discrete-set purification folklore (Appendix C and D). Finally, we thank Xin Lyu for pointing out simple alternative proof of Theorem 9 based on a packing argument (Remark 10).
10

---

References
(ACG+16] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
[AD20] Hilal Asi and John Duchi. Instance-opimmality in differential privacy via approximate inverse sensitivity mechanisms. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 14106-14117. Curran Associates, Inc., 2020.
[AFKT21] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in geometry. In Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 393-403. PMLR, 18-24 Jul 2021.
[B+5]] David Blackwell al. Comparison of experiments. In Proceedings of the second Berkeley symposium on mathematical statistics and probability, volume 1, page 26, 1951.
[BBG18] Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsam- pling: Tight analyses via couplings and divergences. Advances in neural information processing systems, 31, 2018.
[BBKN14] Amos Beimel, Hai Brenner, Shiva Prasad Kasiviswanathan, and Kobbi Nissim. Bounds on the sample complexity for private learning and private data release. Machine learning, 94:401-437, 2014
[BDRS18] Mark Bun, Cynthia Dwork, Guy N Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated cdp. In ACM Symposium on the Theory of Computing, 2018.
[BGH+23] Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell. Stability is stable: Connections between replicability, privacy, and adaptive generalization. In Proceedings of the 55th Annual ACM Symposium Theory of Computing, pages 520-527, 2023.
[BGN21] Raef Bassily, Cristóbal Guzmán, and Anupama Nandi. Non-euclidean differentially private stochastic convex optimization. Conference on Learning Theory, pages 474.499. PMLR, 2021.
[BLRI3] Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to noninter- active database privacy. Journal of the ACM (JACM), 60(2):1-25, 2013.
[BS16] Mark Bun and Thomas Steinke. Concentrated differrnniall privacy: Simplifications, extensions, and lower bounds. In Theory of cryptography conference, pages 635-658. Springer, 2016.
[BST14] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimiza- tion: Efficient algorithms and tight error bounds. In 55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014, pages 464-473. IEEE Computer Society, 2014.
[BSU17] Mark Bun, Thomas Steinke, and Jonathan Ullman. Make up your mind: The price of online queries in differential privacy. In Proceedings of the twenty-eighth annual ACM-SIAM SIAM symposium on discrete algorithms, pages 1306-1325. SIAM, 2017.
[BVV14] Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approximate differential privacy. In Proceedings of the forty-sixth annual ACM symposium Theory of computing, pages 1-10, 2014.
[BW18] Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. International conference on machine learning, pages 394-403. PMLR, 2018
11

---

[CHS14] Kamalika Chaudhuri, Daniel Hsu, and Shuang Song. The large margin mechanism for differentially private maximization. Advances in Neural Information Processing Systems, 2014.
[CMS11] Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(29):1069 1109, 2011.
[CTO5] Emmanuel J Candes and Terence Tao. Decoding by linear programming. IEEE Iransactions information theory, 51(12))2203-4215 2005.
[DBH+22] Soham De, Leonard Berrada, Jamie Hayes, Samuel Smith, and Borja Balle. Unlocking high-accuracy differentially private image classification through scale. arXiv preprint 1355, 2022.
[DKM+06] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryplology-EURRCCRYYY pages 486-503. Springer, 2006.
[DL09] Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 371-380, 2009.
[DMNS06] Cynthia Dwork, Frank McSherr, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[DR+ + 14] Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):21 1-407, 2014.
[0R++20] Chris Decarolis, Mukul Ram, Seyed Esmaeili, Yu-Xiang Wang, and Furong Huang. An end-to-end differentially private latent Dirichlet allocation using a spectral algorithm. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 2421 -431. PMLR, 13-18 Jul 2020.
[DRS22] Jinshuo Dong, Aaron Roth, and Weijie Su. Gaussian differential privacy. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 84(1):3-37, 2022.
[DRV10] Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. 2010 JEEE 51st annual symposium on foundations of computer science, pages 51-60. IEEE, 2010.
[DSS+ + 15] Cynthia Dwork, Adam Smith. Thomas Steinke, Jonathan Ullman, and Salil Vadhan. Robust traceability from trace amounts. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 650 669. IEEE, 2015.
[TTZZ44] Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Analyze gauss: principal component analysis. In Proceedings of
optimal bounds for the forty-sixth annual ACM symposium on Theory of computing, pages 11-20, 2014.
[FGCC66] James Foulds, Joseph Geumlek, Max Welling, and Kamalika Chaudhuri. On the theory and practice of privacy-preserving bayesian data analysis. arXiv preprint arXiv:1603.00 /603.07294, 2016.
[FKT20] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimiza- tion: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, page 439 449. Association for Computing Machinery, 2020.
[MMTT18] Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplifi- cation by iteration. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 521-532. IEEE, 2018.
12

---

[FTS17] Kazuto Fukuchi, Quang Khai Tran, and Jun Sakuma. Differentially private empirical risk minimization with input perturbation. In Discovery Science: 20th International Conference, DS 2017, Kyoto, Japan, October 15-17, 2017, Proceedings 20, pages 82-90. Springer, 2017.
[FW+56] Marguerite Frank, Philip Wolfe, et al. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2)995-1 10, 1956.
[GG23] Guillaume Garrigos and Robert M Gower. Handbook of convergence theorems for (stochastic) gradient methods. arXiv preprint arXiv:2301.11235, 2023.
[GHSGT23] Arun Ganesh, Mahdi Haghifam, Thomas Steinke, and Abhradeep Guha Thakurta. Faster differentially private convex optimization via second-order methods. In Advances in Neural Information Processing Systems, volume 36, pages 19426-79438, 2023.
[GLL22] Sivakanth Gopi, Yin Tat Lee, and Daogao Liu. Private convex optimization via ex- ponential mechanism. In Conference on Learning Theory, pages 1948-1989, PMLR, 2022.
[GS84] Clark R Givens and Rae Michael Shortt. A class of wasserstein metrics for probability distributions. Michigan Mathematical Journal, 31(2):231-24) 1984.
[GTU22] Arun Ganesh, Abhradeep Thakurta, and Jalaj Upadhyay. Differentially private sampling from rashomon sets, and the universality of langevin diffusion for convex optimization. arXiv preprint urXiv:2204.0/2: 225501 2022.
[HC22] Yiyang Huang and Clément L Canonne. Lemmas of differential privacy. arXiv preprint arXiv:2211.11 2022.
[HLM12] Moritz Hardt, Katrina Ligett, and Frank McSherry. A simple and practical algorithm for differentallly private data release. Advances in neural information processing systems, 25, 2012.
[HR10] Moritz Hardt and Guy N Rothblum. A multiplicative weights mechanism for privacy- preserving data analysis. In 2010 IEEE 51st annual symposium on foundations of computer science, pages 61-70. IEEE, 2010.
[HT10] Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 705-714, 2010.
IIN 19] Roger Iyengar, Joseph P. Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang. Towards practical differentially private convex optimization. In 2019 IEEE Symposium on Security and Privucy (SP), pages 299-316, 2019.
[KJ16] Shiva Prasad Kasiviswanathan and Hongxia Jin. Efficient private empirical risk min- imization for high-dimensional learning. Proceedings of the 33rd International Conference on International Conference Machine Learning Volume 48, ICML' 16, page 488-497. 497. JMLR.org, 2016
[KJH20] Antti Koskela, Joonas Jälkö, and Anti Honkela. Computing tight differential privacy guarantees using fft. In International Conference Artificial Intelligence and Statistics, pages 2560-2569. PMLR, 2020.
[KLL21] Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu. Private non-smooth erm and sco in subquadratic steps. In Advances in Neural Information Processing Systems, volume 34, pages 4053-4064, 2021.
[KLT24] Guy Kornowski, Daogao Liu, and Kunal Talwar. Improved sample complexity for private nonsmooth nonconvex optimization. arXiv preprint arXiv:2410.0565 10.08880, 2024.
KNRS13] Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Analyzing graphs with node differential privacy. In Theory of Cryptography: 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings, pages 457-476. Springer, 2013.
13

---

[LJSB12] Simon Lacoste-Julient Mark Schmidt, and Francis Bach. A simpler approach to obtaining an o (I/t) convergence rate for the projected stochastic subgradient method. arXiv preprint arXiv: 1212.0002 2012.
(LLL21] Yin Tat Lee, Daogao Liu, and Zhou Lu. The power of sampling: Dimension-free risk bounds in private erm. arXiv preprint WrXiv:2105.13633 2021.
[44 Yingyu Lin, Yian Ma, Yu-Xiang Wang, Rachel Emily Redberg, and Zhiqi Bu. Tractable MCMC for private learning with pure and gaussian differential privacy. In The Twelfth International Conference on Learning Representations, 2024.
[LSS14] Adeline Langlois, Damien Stehlé, and Ron Steinfeld. Gghlite: More efficient multi- linear maps from ideal lattices. In Annual international conference on the theory and applications of cryptographic techniques, pages 239-256 256.. Springer, 2014.
[MBST22] Paul Mangold, Aurélien Bellet, Joseph Salmon, and Marc Tommasi. Differentially private coordinate descent for composite empirical risk minimization. In International Conference on Machine Learning, pages 14948-14978. PMLR, 2022.
[Mir17] Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pages 263-275. IEEE, 2017.
[MMR12] Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Multiple source adaptation and the rényi divergence. arXiv preprint arXiv: 1205.2688, 2012.
[MT07] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) pages 94-103. IEEE, 2007.
[MV22] Oren Mangoubi and Nisheeth Vishnoi. Sampling from log-concave distributions with infinity-distance guarantees. Advances in Neural Information Processing Systems, 35: 35:12633-126444 2022.
[NRS07] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sam- pling private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 75-84, 2007.
[NS21] Aleksandar Nikolov and Thomas Steinke. release for pure differential privacy. sttps://differretiaaliii. 2021.
Open problem optimal query
org/
[RBHTI2] Benjamin IP Rubinstein, Peter L Bartlett, Ling Huang, and Nina Taft. Learning in large function space: Privacy and Confidentiality, 4(1), 2012.
mechanisms for svm learning. Journal of
[RKW23] Rachel Redberg, Antti Koskela, and Yu-Xiang Wang. Improving the privacy and practicality of objective perturbation for differentially private lincar learners. Advances Neural Information Processing Systems, 36: 16:11389-13853, 2023.
[SSTT21] Shuang Song, Thomas Steinke, Om Thakkar, and Abhradeep Thakurta. Evading the curse of dimensionality in unconstrained private glms. In International Conference on Artificial Intelligence and Statistics, pages 2638-2646. PMIR, 2021.
[SU16] Thomas Steinke and Jonathan Ullman. Between pure and approximate differential privacy. Journal of Privacy and Confidentiality, 7(2), 2016.
[SWC17] Shuang Song, Yizhen Wang, and Kamalika Chaudhuri. Pufferfish privacy mechanisms for correlated data. In Proceedings of the 2017 ACM International Conference on Management of Data, pages 1291-1306, 2017.
[TGTZ15] Kunal Talwar, Abhradeep Guha Thakurta, and Li Zhang. Nearly optimal private lasso. In Advances in Neural Information Processing Systems, volume 28, 2015.
[Ta24]] Kevin Tian. 3s395t: Continuous algorithms, part ix, sparse recovery, 2024.
14

---

[TS13] Abhradeep Guha Thakurta and Adam Smith. Differentially private feature selection via stability arguments, and the robustness of the lasso. Conference on Learning Theory, pages 819-850. PMLR, 2013.
[TTZ14) Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Private empirical risk minimization beyond the worst case: The effect of the constraint set geometry. arXiv preprint wrXiv:141.55411 2014.
[Vad17] Salil Vadhan. The Complexity of Differential Privacy, pages 347-450. Springer, Yehuda Lindell, ed., 2017.
[Vai89] Pravin M Vaidya. Speeding-up linear programming using fast matrix multiplication. In 30th annual symposium on foundations of computer science, pages 332-337. IEEE Computer Society, 1989.
[VEH14] Tim Van Erven and Peter Harremos. Rényi divergence and kullback-leible divergence. IEEE Transactions on Information Theory, 60(7):3797-338 2014.
[VS09] Duy Vu and Aleksandra Slavkovic. Differential privacy for clinical trial data: Prelimi- nary evaluations. In 2009 JEEE International Conference Data Mining Workshops, pages 133-143. IEEE, 2009.
[Wa174] Alastair Walker. New fast method for generating discrete random numbers with arbitrary frequency distributions. Electronics Letlers, 10(8):127-128, 1974.
[Wan18] Yu- Xi-Xiang Wang. Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain. arXiv preprint
2018.
[WBK19] Yu- Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled rényi differential privacy and analytical moments accountant. In The 22nd international conference artificial intelligence and statistics, pages 1226-1235. PMLR, 2019.
[Wu16] Yihong Wu. Ece598: Information- methods in high-dimensional statisties, 2016.
[WYX17] Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. In Advances in Neural Information Processing Systems, volume 30, 2017.
[WZ10] Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):375-388 2010.
[ZW19] Yuqing Zhu and Yu-X Yu-Xiang Wang. Poission subsampled rényi differential privacy. In International Conference on Machine Learning, pages 7634-7642. PMLR, 2019.
15

---

Contents
1 Introduction
1.1 Summary of the Results
1.2
Related Work
2 Algorithm: Converting Approximate DP to Pure DP
3
Technical Lemma: from TV distance to o<-asssesteiin distance
Empirical Risk Minimization with Pure Differential Privacy
4.1
Purified DP Stochastic Gradient Descent
4.2
Purified DP Frank-Wolfe Algorithm
5 Pure DP Data-dependent Mechanisms
5.1
Poppoe--Tes-RRlesee with Pure Differential Privacy
5.2
Pure DP Mode Release
5.3
Pure DP Linear Regression
6 Pure DP Query Release
7 Purification as Tool for Proving Lower Bounds
8 Conclusion and Limitation
10
A Preliminaries
18
A.1 Definitions on Distributional Discrepancy
18
A.2 Lemmas for DP Analysis of Algorithm
18
B Supplementary Discussion on Randomized Post-P fost-Processing
19
C Discussion: Purification on Finite Output Spaces
19
Discussion: Extending the Purification on Finite Output Spaces to the Euclidean Space
20
Privacy Analysis: Proof Sketch of Theorem
Deferred Proofs Section 2 and Appendix A
22
F.1
Proof of Lemma 6
22
F.2
Proof of Lemma
23
F33
Proof of Lemma 16
24
F.4
Proof of Theorem and Corollary
24
F.5
Proof of Theorem 2
25
G Further Discussion of the Optimality of Our Purification Results
26
H Deferred Proofs for DP-SGD
26
H.1
Algorithms and Notations
26
H.2
Noisy Gradient Descent Using Laplace Mechanism
Moca............................
27
H.3 Analysis of DP-SGD
28
H.3.1 Privacy Accounting Results
28
H.3.2 Convex and Lipschitz case
29
H.3.3 Strongly Convex and Lipschitz case
30
H.4 Analysis of Purified DP-SGD
31
H.4.1 Proof of Theorem
I Deferred Proofs for DP-Frank- Wolfe
31
I1
Approximate DP Frank- Wolfe Algorithm
31
1.2 Pure DP Frank-Wolfe Algorithm
1.3 Proof of Theorem 4
33
16

---

1.4
Proof of Lemma 30
34
J
Deferred Proofs for Data-dependent DP mechanism Design
35
J.1
Pure DP Propose Test Release
35
J.2
Privately Bounding Local Sensitivity
36
J.3
Private Mode Release
37
J.4
Private Linear Regression Through Adaptive Sufficient Statistics Perturbation
37
Deferred Proofs for Private Query Release
40
K.1
Problem Setting
40
K.2 Private Multiplicative Weight Exponential Mechanism
40
Deferred Proofs for Lower Bounds
42
L.1
Proof of Theorem 9
42
L.2
More Examples of Lower Bounds via the Purification Trick
................................
44
L.2.1 One-Way Marginal Release
44
L.2.2 Private Selection
46
L.3 An alternative proof for Theorem 9
47
M Technical Lemmas
48
M.1
Supporting Results Sparse Recovery
48
M.2 A Concentration Inequality for Laplace Random Variables
49
17

---

A Preliminaries
This section provides definitions of max divergence, total variation distance, and co- Wasserstein distance, and the lemmas that will be used in the privacy analysis of Theorem 1.
Notations. Let be the space of data points, X == t the space of the data set. For an integer n, let [n] {1. (l......1) n2). A subgradient of convex function at æ, denoted Of is the set vectors g such that f(y) 2 f(x + (g. y - z), for all y in the domain. For simplicity, we assume the functions are differentiable in this paper and consider the gradient Vf. The operators V and A denote the maximum and minimum of the two inputs, respectively. We use || llg to denote by norm. For set A, || suPzeA ||Allg represents the by radius of set A and Diam, := Σx,cc || - vlla represent the bg diameter of set A. For a finite set S, we denote its cardinality by |S). Throughout this paper, we use EA|-] to denote taking expectation over the randomness of the algorithm.
A.1 Definitions on Distributional Discrepancy
Definition 11 ([VEH14), Theorem 6; [DTTZ14), Definition 3.6) The Rényi divergence of order oo (also known as Max Divergence) between two probability measures I and on measurable space F) is defined as:
((S)
(xo(u) In sup
v(S)
SEF, M(S)S
In this paper, we say that and are e-indistinguishable if Doo (ullp) I e, and Doo (vlll) S s.
mechanism M is e-differentially private if and only if for every two neighboring datasets and D', we have Dx (M(D)))M((')) S e, and D (M(())))M()) S.. e.
Definition 12 The total variation (TV) distance between two probability measures μ and on measurable space (9, F) is defined as:
drv(p, = suup (u(S) - v(S)
SEF
The oo- c-Wasserstein distance between distributions captures the largest discrepancy between samples with probability/ under the optimal coupling. Unlike other Wasserstein distances that consider expected transport costs, it offers a worst-case perspective. Though the xo- eesaseerstnin distance can
be defined with general metric, for clarity, focus its by nnrm version in this paper.
Definition (Restatement of Definition 5) The so-Wasserstein distance between distributions μ and v separable Banach space (o, 1lg) is defined as
W'' (H,
inf ess sup | - Ullg = inf 7EIclu.))
{a P ((ay)>>> [| - yll, S aa]= =
TEIc(H,) (x.w))>
where I (e( ) the set of all couplings of and v. i.e., the set of all joint probability distributions ? with marginals and respectively. The expression ess sup denotes the essential supremum with respect to measure 7,. By [GS84, Proposition 1], the infimam in this definition is attainable, i.e..
there exists > E -e(u,, such that 3 (p, v) ess suspsu
|| 3/lg-
For Laplace perturbation (Lemma 15), we require bound on W the Wasserstein distance defined by the foomm, i.e., for = 1. A bound for W can be derived from W using the incquality || 1 d² d ll. which gives W (v.) d² d'- (..)).
A.2 Lemmas for DP Analysis of Algorithm
We now introduce the three lemmas for the privacy analysis: the equivalence definition of (e, 8D- (Lemma 14), the Laplace perturbation (Lemma 15), and the weak triangle inequality for oe-Rényi divergence (Lemma 16).
Lemma 14 (Lemma 3.17 of [DR* + 14J) A randomized mechanism M satisfies (e, 8)-D) if and only if for all neighboring datasets D ~ D', there exist probability measures P such that (rv(M(D), P) I 2.4 drv(M(DD), P') S e141 Dxo P') I and D (P' S) Se.
18

---

Lemma 15 (Laplace perturbation, adapted from Theorem 3.2 of [SWC17]) Let and be probability distributions on R. Ler Laplace (b) denote the distribution of R where
zi Laplace(b). W (1, S A, then have
Ltd.
Doo (1 Laplace add ( || Laplace 3d ( S 6, and
Doo (v Laplace od ( || Laplace sd ( S.
The proof is provided in Appendix F for completeness. The Laplace mechanism is a special case of Lemma 15 by setting μ and v to Dirac distributions at (D) and f(D"), respectively. Lemma 15 can also be derived from the limit case of [FMTT18, Lemma 20] as the Rényi order approaches infinity.
Lemma 16 (Weak Triangle Inequality, adapted from [LSS14),, Lemma 4.1) Let nt U, π. be prob- ability measures on measurable space (Q, If (so(p))) < and Doo (T|(U) < oc, then Do (elpp) & ( (p][T) + Do ( (T||P).
The proof is deferred to Appendix F. This lemma generalizes [LSS14, Lemma 4.1], which focuses on discrete distributions. Additionally, Lemma 16 corresponds to the infinite Rényi order limit of [Mir17, Proposition 11] and [MMR12 12, lemma 12).
B Supplementary Discussion Randomized Post-Processing
In this section,we we clarify the distinction between our "purification" process and the randomized post-processing in [B+ [1, Theorem 10). Define the following function
fa,((a) = max (0, - eaa, -(1 8- a))
By [WZ10], mechanism M is (s, 5) if and only if M is f--DP.
51, Theorem 10] [DRS22, Theorem 2.10] establish the existence of (randomized) post- processing method that transforms pair of distributions into another pair with a dominating trade-off function. Specifically, they show that if T(P, Q) T(P',Q") then there exists a randomized algorithm Proc such that Proc(P) = P' and Proc(Q) = Q', where T denotes the trade-off function [DRS22, Definition 2.1]. Their proof constructs sequence of transformations and takes the limit. In contrast, our "purification" process provides a computationally efficient post-processing method for different problem. Given that fe.s S f(cte'),o (see Figure 3) and that T(M(D), M(D')) Z fe,s for all neighboring datasets D ~ D', seek randomized post-processing procedure Apure such that T T(Apue M(D), Apure o M(D')) 2 ((e+e'), ).o while maintaining utility guarantee.
Typol..om
Typel
Figure 3: Trade-off functions for (s, 5)-D, (s. 0)-D, and (s + s', -D. Our method provides solution to post-process the (e, 5DP distribution pair (in blue) the (e + e", DP- pair (in red).
C Discussion: Purification on Finite Output Spaces
This section diseusses a "folklore" method for converting approximate DP mechanisms into pure DP when the output space is finite, and explains why this method fails in the continuous case. Given an
19

---

(e, 6)-DP mechanism M: X" + 3 with finite output space V. one can construct a new mechanism by mixing M with uniform distribution over V:: Amix (M) (1 w. + ()). The resulting mechanism Amix (M) satisfies (s + In(1 + -للي - )-pure DP [HC22, Lemma 3.2]. However, this strategy does not yield pure DP when the output space is continuous, as the following counterexample shows.
Example 17 Let f - [0, 1] be a statistic computed on dataset D X" Consider the following mechanism: with probability 6, output the true value fDD) with probability 1- 6, output a value uniformly from [0, 11. That is, M(D) = 8 &Dirrc
( + (1 - 811nf 1[), where & denotes (
the Dirac measure at fDD) Then M satisfies (0, (0.8)-DP Now, consider applying the uniform mixture strategy:
Amix (M()) = (1-w)M(D) + wUnif((O,1)
= -wjō 1000-pppe Pirra + 5 Uw)Unii([0,) 1])-
This new mechanism satisfies (0, (1 -DD) but not pure DP unless w 1, which is the trivial mixture.
D Discussion: Extending the Purification on Finite Output Spaces to the Euclidean Space
A natural approach for purification on Euclidean space is to quantize the continuous output space into a finite discrete set, and apply the folklore purification for finite sets. Specifically, to purify the (c, 5DDP mechanism M X θ S Rd one could first cover the range G by A-net, round the output of M to the nearest grid point, and then purify it using the finite range folklore method. We thank anonymous NeurlPS 2025 reviewer for suggesting this approach. The main challenge of this approach is the explicit construction of the A-net and the efficient uniform sampling from it. When constructing the A-net by the cubes (as detailed below), this natural method achieves similar utility
bound Algorithm 1, the bottleneck of both bounds is the term (5) The bound is different in the non-dominating terms: if θ is an &o ball, this quantization- -aaee method has tighter bound; if θ is an ball, it yields worse bound.
Construction of A-net. We first note that a naive approach, sampling from an & ball (or f ball) and then rounding to the nearest grid point, does not yield a uniform distribution on the grid points. This non-uniformity arises from boundary effects. To illustrate, consider the l ball of radius R and take the point (R, 0, .0........ 0) on its surface. That the volume of the intersection:
{2 || - R, || - æ|11 S r). only za fraction of the ball {= || 0|11 < r).
We now provide the derivation. Writing the intersection in coordinates:
2
< R,
21 - R
2 Sr,
get R R 21 S R, and for such 21, the other coordinates must satisfy
d
Σ
a S min R - 21, R 21}
Therefore, the intersection volume is J R- SR | |al (R-21.-- 1d(22.... za)d21. 2d
Sn-rSaISR (d-1)) (min 21, R + 21
= (d-1)) UR- R
d=) + Sn- Sn-T/25= (R =1) )d1
(ύ- 2)(5)d Ird which is z portion of
24-1
the volume of the ball (2: ||2 =x/11 S r).
We also note that the above intersection volume can be lower bounded for & norm, see Lemma 24 in [LMW+24].
Given these challenges with non-uniformity, we instead consider constructing the A-net by tiling a large cube O 2 O with smaller cubes.
20

---

Cube-Based A-net Construction and Analysis. Without loss of generality, assume O' = |0, RJ
Take A
2R
(
2w
log d, and K -- Construct the nent using cubes of the form
IIk==
iRR (6++1)
By the folklore purification, this algorithm satisfies
( + In(1 + 5K e 9
K
K
pure DP. We have
d
6
R logd
+ In(1 + 5K
8Kd - s e S +
R( +
e
S 2E.
When = 0c, this method achieves the utility bound of E || Tapx 2o
S wl +
4R logg
This bound is tighter than the bound by directly applying Algorithm in the dependence in For comparison, directly extending the proof of Theorem (Appendix F.4) to the fo norm yields:
E pure p
Fapxll
S wR + 1Rd(log d+1)
(2) which is derived as follows:
E pppre Tapx
IP(u > w)lE
||
Kapx
u > w| + P(u S w)B [||x Tapx ll oo I S w
E max [ii|
+wR
(2: Laplace (22) (22))
24
+ wR
k
e
24
S (log + 1)
+ w.
5¹
4Rd(log 1)
+ wR.
2w
When g = applying the standard conversion
1111 S dll |l,o. this method achieves the utility
bound of Puuue Taps d.
11 S wdR 4fgdlogd
which worse than Theorem 1 by a factor of 2
E Privacy Analysis: Proof Sketch of Theorem 1
The proof sketch of Theorem is illustrated in Figure 4. Let D and D' be neighboring datasets, and let M be an ()-D mechanism. We aim to show that Apure (M(D)) and Apure (M(D')) the post-processed outputs of M(D) and M(D') after applying Algorithm 1-are are e-indistinguishable. By sketching the proof, we also provide the intuition the design of Algorithm
First, by the equivalent definition of approximate DP (Lemma 14), there exists a hypothetical s- indistinguishable distribution pair P and p', such that M(D) and M(D') are (0))close P and P', respectively, in total variation distance. Note that P and p' can both depend on D and D', i... P P(D, D') and p' P'(DDD', rather than simply P P(D) and p' P'(D'. This dependence complicates the direct application of standard DP analysis. To address this, we transition to distributional perspective.
To show that Apure (M(D)) and Apure (M(D')) are e-indistinguishable distributions, by the weak triangle inequality of Ré-Rényi divergence (Lemma 16), it suffices to show that Apure (M(D)) and Apure (P) are s-indistinguishable (in terms of Re-ééy divergence), and that Apure (M(D') and Apure (P') are e-indistinguishable well. Now the problem reduces to: given two distributions with total variation distance bound, how to post-process them (with randomness) to obtain the Ro-Rényi divergence bound?
natural way to establish the oc-Renyi bound is via the Laplace mechanism. which perturbs deterministic variables with Laplace noise according to the {1-sensitivity. To generalize the Laplace mechanism to perturbing random variables, we develop the Laplace perturbation (Lemma 15), which achieves the Rényé bound by convolving Laplace noise according to the W distance. The W distance can be viewed as a randomized analog the fiddistance. The remaining step is to derive 20 bound from the TV distance bound, and this motivates Lemma 6, drv to W conversion
21

---

drv <
5
Doe S
drv
<
8
M(D)
P
p
M(D')
(Lemma 14)
(Lemma 14)
(Lemma 14)
wUnif
wUnif
wUnif
wUnif
W <A (Lemma 6)
Doo Se
W (Lemma
U(M(D))
U(P)
U(P)
U(M(D'))
*Lap( 22)
*Lap( 22
+Lap(
*Lap
Doo S
Doo Se
Doo S
Apure (M(D))
Apure (P)
Apure (P))
Apuro (M((())
(Lemma 15)
(Lemma 13)
Doo S 25
Weak triangle inequality (Lemma 16)
Figure 4: Flowchart illustrating the proof sketch of Theorem and the intuition behind Algorithm The notation Dos I E is an abbreviation for the pair of inequalities Do (4 [p]] Σ e and D (Vila) S e. where and / correspond to the two end nodes of the respective edges (e.g.. I and P'). The symbol w wUnif represents a mixture with the uniform distribution (Algorithm I, Line 3), where 2((-) (1 w) +wUnni(@@). The notation al. refers the convolution with the Laplace distribution, in Algorithm 1, Lime 4.
lemma that generalizes 24M Lemma 8]. A small mixture of uniform distribution ensures that the conditions of Lemma hold. Therefore, Algorithm consists of two key steps: mixture with the uniform distribution (Line 3), and the Laplace perturbation calibrated to ó (Line 4.) The formal proof of Theorem 1, along with proofs of the key lemmas, is deferred to Appendix
F Deferred Proofs in Section 2 and Appendix A
F1 Proof of Lemma 6
Proof of Lemma Denote dist(2, y) = || -lg.- Denote Bcc,, r) the ball with center c, and r.-radius r. Assume B(c,r) Q Without loss of generality, assume A < R.
Fix A and set { Piin Vol [B/ (1) (i
Ad, so that drv(u, v) < <.
Pinin
To prove the result that Wo S A, we use the equivalent definition of Wo Lemma 7. By this definition, to prove W (n, v) < A, it suffices to show that
p(A) < v(A-), for all open set A O
where we re-define 4 == fu E Rd dist(r, A) < A}. Note that by this definition, A might extend beyond θ. However, still have v ( ( n @), since is supported O.
Note that ( = 1, obvious that ((A) < v(A²). When an empty set, the proof is trivial. So we only consider nonempty open set A θ with v(A4) 1.
Note that for an arbitrary open set A C θ, we have
((A) S ((() + drv (1, v) v(A)
Thus to prove p(A) < v(A-), suffices to prove v(A) + v v(A i.e., v(4 (A) E.
To prove v(AA A) 2 E. construct ball K Rd of radius _ satisfying the properties:
Property 1 K is contained in the set A i... K A A, and
Property 2 K contained θ, i.e., C θ. This guarantees that v(K) = v(K n 2 Pmin Vol(K) c.
To construct the above ball K, we adopt the following strategy:
Step 1 First, select point e θ such that dist(y, A) A/2.
22

---

Step 2 Then, construct the ball K with center = we + (1 - w)y, radius wr, where A ie.. K ((r,,wr)). We will later show that this ball contained in the convex hull of B(c,r) (v). This construction is inspired by [MV22].
We first prove such point in Step I exists, that is, the set θ n {- E ddIdiss(r, A) = A/2] is nonempty. (Note that only consider nonempty open set A C θ with (AA-) 1.)
We prove it by contradiction. If instead è {æ IR dist(x, (z,ttzz,44) A) A/2] 0, then for all e. dist(a, A) * A/2. Due to the continuity of dist and the convexity of θ, we know that only one of these two statements holds:
di < A/2, for all x E e.
* dist(x,AA) A/2, for all e.
Since @ き A C θ, there exist x' E A E o, such that (ist((", A) = 0. Therefore, the first statement holds. Thus C A C A which contradicts v(AA) < 1.
Therefore, there exist O such that dist A) A/2, making Step valid. Next, we show that the K we construct in Step 2 satisfies Property and Property 2. To prove K S AA A. 1et K B(ci, wr). We show that x E A and & A. We have dist(x, v) S dist(x, e1) + dist(c1, y)
| ci || + llwe + (1 - -wyy vll,
| C1 l1g + w|lc y/1v
S wr + w R
A
(r R)
4R
A/2
É A). If E A, since is an open set and dist A) = A/2, we have that dist y) >
2/2, which contradicts to (3). Therefore r & A.
(x E A). We have dist(x, A) < dist(r, v) + dist(y, A) < A, implying that x E A To prove K C θ, take any x E = B(c,, we show that O. Write x = c1 + wrV, where
||vll, < 1. We have
== wc + (1 w)y + wrv w(c + w)y.
Since + rv B(c,T) C y O and 0 < w 4R which completes the proof.
1, by the convexity of θ we have θ
In particular, an ba-b centered at e, say c B (r). then the in Step 2 can be chosen
//
as A T by:
which similarly follows, since ||c [|c-=10 æ11p < r for any E O. This improves the conversion
If drv(u,)) v) Pmin Vol(BB (1)) (1)
Ad then Wo,(u, SA.
F22 Proof of Lemma 15
Proof of Lemma 15 denote P = μ Laplace ( = v* Laplace ( Then, P and Q are absolutely continuous with respect to the Lebesgue measure. This is because for any Lebesgue zero measure set S, P(S) = ʃr (S r)dp(z), where S - x= [ylr y E 5), and Laplace denotes the probability measure of Ed (è). Since
zero measure for all æ E Rd and P Lapplace absolutely continuous w.r.t. the Lebesgue measure, we have IP Ptaplacee (S - x:) for all
"We note that the symbol Section F.1 distinct from the rsed in other of the paper. This distinction is an intentional abuse notation for clarity within
specific contexts.
23

---

E R.. Therefore, P(S) = 0. Thus P is absolutely continuous w.r.t. the Lebesgue measure, and Q similarly follows.
Denote and q the probability density function of P and Q respectively. Since W (H, v) < A.
by [GS84, Proposition 1]. there exists 7" Fe(p, v),, such that (u,,)>>'' [||u 8/ ]
y fllu u|| > } 0. By the definition of the max divergence (Theorem 6 of [VEH14]), we have
p(x)
(x(()))) css sup
([VEH14, Theorem 6])
x~P
g(x)
Jxe
du(u)
I ess sup x-P
(Convolution theorem, PDF of Laplace)
1 de(u)
Sadxza
11-=11 dy u)
I ess sup P~P
(y E (e(,,))
SRUXR
1x-
dy (u,
JRAXR 11-=ell1 -M-0 dy (u, v)
I ess sup p
(triangle's incquality)
SRAXRA E Iomvily dy vu)
=1a-v01,5A Ilamll دلي dy (u, v) + fiu-ool, >1 6
Iumeily NIw-elli
dy (u, v)
< ess sup x~P
SK'XR' e
le-"/1 (u,
ls wh rh d7,
Jau- =1n-v11,sA e
I css sup x~P
(7" fllu u/11 > {} = 0)
JREXR
Im-olly
bo (u,
11-=lly (u,
J|l-vol, SA
ess sup x>P
SReERe e Io-elly dy (u,
SRUXRR e- الييe dr (u, v)
I ess sup x~P
JREXRI c الليعع dr (u, v)
F33 Proof of Lemma 16
Proof of Lemma 16 Since Doo (ull < cc, for any measurable set S F. such that v(S) > 0,
have π (S) > 0. That is, {S E F ((S) > 0} C [S x(S) > 0}. By Definition 11,
(u(S]
Doo v) = In
sup SEF, p(S)20 ((S)
(S))((S) (S))((S)
= In sup
SEF, ((S)>0, (8)>0
((S)
x(S) ((S)
In
sup
+ In
sup
SEF, pS))0 [TS)
SEF, (3))
= (ul[T) + Doo (TTII).
E4 Proof of Theorem 1 and Corollary 4
We first provide proof of the privacy guarantee by reorganizing the proof sketch in Section E, as illustrated in Figure 4.
Let D and D' be neighboring datasets, and let M an (e, 8)-DP mechanism as in Section E. By the cquivalence definition of approximate DP (Lemma 14), there exists hypothetical distribution pair
24

---

P. P' such that
dTv(M(D), e +1 (Tv(TD)(((D)), p)
e +1 : s and (P S
Note that P and P' can both depend on D and D', i... P P(D, and P (D), rather than simply P = P(D) and P -
Denote u() = (1 w) +wUnif(@) After the uniform mixture step (Line 3), the distributions ((M(D)) (P), all satisfy the assumption in Lemma with
Pmin
Vol(e)
(R/2)dVol (B (1)
Therefore, by Lemma 6 (with the case of θ is an bg ball) and the fact that ||- S d' 11.. we have
(MM) < A, and w (((M(D)). - A. where A is defined in Line in Algorithm 1. Therefore, by Lemma 15, we have
Doc (U(M(D)) Laplace Sd [K((P) Laplace 3d (2)) S
Doc (M(P) * Laplace od
24 [K(M(D) Laplace 3d
(22)) $6//2.
Doo (U(M(D') Laplace
24 [[M(())) * Laplace od
(2+)) E2/22
Do (U(P') Laplace
(2
[U(M(D))) Laplace od ( 6//2
Finally, with the weak triangle incquality (Lemma 16), conclude that the output of Algorithm 1 satisfies (e + e')-DP.
Next, we provide the utility bound. Let Unif 1) in Line 3 of Algorithm 1.
Tapxll, = P(u w)B |Iaxpre Tapxll, ll, u> w| P(u W)B || Tapxll
S w
(5)
d
E
Σ
1
+wR
(z: Laplace (2
34
<
E
|
+ WR
(Jensen's 's inequality)
2A
(qT + 1))
R.
(6)
E'
RdqR
1/2
+ wR
(7)
2w
Remark 18 We can remove the dependence on q in the above bound by controlling || via concentration inequalities for sub-exponential random vectors.
Eapx ||
Proof of Corollary Since θ is an É, ball, we have 2r = C.. The proof follows directly from
Theorem by taking g = 2.
F.5
Proof of Theorem 2
Notice that BinMap is a data-independent deterministic function, thus by post- processing, 2bin BinMap (Mapx) maintains (c, DDP
Proof of Theorem
We consider the é norm, i.e., q 1. Let By (t) C [0, C + By (4). That is, 1]d satisfies Assumption with R 5. 3. and q = Therefore, by Theorem 1, zpure satisfies (2s, OD-D. After the post-processing, the output of Algorithm 2 maintains (2s, -DP
(.....,) 1). For unit cube [o, 1]4, we have
25

---

For the utility, by d <
a (2dyau
and Line 2 of Algorithm 1, we have A
<
47'
Laplace iid.
Let y/1
Laplace(2A/e"), be the noise added in Line in Algorithm 1. Then for any i,
P(u
Laplace 2 21)
=6 237E
_
1
2dh
2
2
Thus,
IP
Laplace 1/
0.5, Vi = 1,..., 1..,Vii ze
=
1
-d 2
d 2
(8)
where the last inequality is by Bernoulli's inequality.
Since the rounding function is defined as (o. Thin Surr if and only the following conditions hold simultaneously:
(1(r; 2 0.5)) observe that
1. x Un) is sampled in Line 3 of Algorithm 1.
2. For all i [d]. if Pbin 0, then yj Lap < 0.5.
(8)
3. For all i E [d]. if bin = 1, then y, Lap > -0.5.
(t)
By the symmetry of Laplace noise, applying Eq. (8), and using the union bound, we obtain
(Zbin = 2pure) 2 d z = 2-
G Further Discussion of the Optimality of Our Purification Results
In this section, examine the optimality of the utility guarantees achieved by our purified algorithm, as summarized in Table 1. We compare our results against known information-theored lower bounds and the best existing upper bounds, discussing each setting in turn.
For the DP-ERM setting (Rows and 2), our bounds (Theorem 3) match the lower bounds reported in [BST14, Table 1, Rows and 3], up to logarithmic factors.
In the DP-Frank- Wolfe setting (Row 3), our guarantee matches with the lower bound established in Lemma 30, again up to logarithmic terms.
For the PTR-rype setting (Row 4), to the best of our knowledge, no PP mechanism has previously been developed this regime, and thus no direct baseline available for comparison.
For the Mode Release task (Row 5), our result (Theorem 6) matches the lower bound from [CHS14, Proposition 1], up logarithmic factors.
For Regression (Row 6), assuming bounded data and parameter domains, our result (Theorem 7) agrees with the lower bounds in [BST14, Table 1] with respect to d, e, and X, up to logarithmic factors and constants depending on the data and parameter radii.
Finally, for Query Release (Row 7), our utility guarantee (Theorem 8) matches that of the SmalIDB and Private Multiplicative Weights algorithms up logarithmic factors [DR+14 14, BLR13), which represent the current state of the art for pure-DP query release. Whether this rate can be further improved remains an open question [NS2I].
H Deferred Proofs for DP-SGD
The study of DP-ERM is extensive; for other notable contributions, see, e.g., [RBHT12, FTS17, INS 19, SSTT21, MBST22, GTU22, GLL22, RKW23, KLT24].
H.1 Algorithms and Notations
Let f6; represent the individual loss function. L(0) := Σd 2(0:2;) and L min L(A). Rec We also denote F(0)= == Σ/= f(0: 24) and F min F(B). L-Lipschitz, 3-smooth, or X-strongly BEC
convex are w.r.t. individual the loss function f. The parameter space in Algorithm selected as the ball with diameter C' that contains C.
26

---

Algorithm 3: Differentially Private SGD [ACG+16)
2 Input: Dataset D {.1,..., vnJ, loss function f C x D + R, parameters: learning rate
noise scale subsampling rate Lipschitz constant L, parameter space C E R Initialize Og randomly
6 for & E (T) do
Sample subset Se by selecting a a fraction of the dataset without replacement
Compute gradient: for each E St do
12
L gr(zz) f (oe(
Aggregate and add noise: Øs + (EiEs, -N
14
16
Descent: 0c+1 4- Projc (0z m(rtt)
Output: Pout Σ. 0e if f convex; aout T(*+1) Et 10, if f strongly convex.
Algorithm 4: Pure DP SGD
2 Input: Output from DP-SGD Algorithm 3 Oapas parameter space O privacy parameter e' and 6, mixture level
4 0 pure & Apure ( app O,,,
Algorithm I
6 Output: Ppre
H.2 Noisy Gradient Descent Using Laplace Mechanism
Lemma 19 (Laplace Noisy Gradient Descent) Let the loss function f X - Rd be convex and L-Lipschitz with respect to || ||2 and maxx-x' [V S Å1. Suppose the parameter space C Rd is convex with an lg diameter of at most C. Running full-batch noisy gradient descent number of iterations T enL and Laplace noise with DiVa
with learning rate 1)
C
ArT satisfies E-DP. Moreover,
parameter
EA (c(0)- 00
n//2g1/2
and the total number of gradient calculation is pdeLvd A1
Without further assumptions on V f. we
have:
CLd 1/2
E (C(0)- - L*) s
Proof Suppose we run iterations and the final privacy budget is e. Then, the privacy budget per iteration is Eo $, and the parameter of the additive Laplace noise is = A1/Eo = A,T/e. By [GG23, Theorem 9.6], we have
T
C + nn22 2do
E
8
F
S
T
Tn
1m
CnL. Covd VT VT
CnL CAIVAT
VT
1/2
0
el/2
where the second inequality obtained by choosing learning rate /T(n2L2+2dd and the fact Va Na+b< Va + vb for any positive a and b. The last inequality is by setting T snn Divide
Aivd
27

---

both sides by we have:
(/2
E (2(0) oo
n2/2g1/2
Without additional information, the best upper bound for A is vdD2 = VdL. Plugging this bound Eq. (9) yields:
CLa
E - -
-+) so
n2//2/1/2
H.3 Analysis of DP-SGD
H.3.1 Privacy Accounting Results
Our privacy accounting for DP-SGD is based on Rényi differential privacy [Mir17], Before stating the privacy accounting result (Corollary 24), we define Rényi Differential privacy and its variant, zero concentrated Differential Privacy [BS16].
Definition 20 (Rényi differential privacy) A randomized mechanism M satisfies (a,, ((,)))))Reén)) Differential Privacy (RDP) if for all neighboring datasets D, D' and for all a 2 1,
Dc(M(D))M((") S =(a),
where D& (P(l)) denotes the a-Rényi divergence when > 1; Kullback-Leibler divergence when 1; max-divergence when 3c. We refer the readers to [Mir17, Definition 3] for a complete description.
Zero Concentrated Differential Privacy is special case of Rényi differential privacy when Rényi divergence grows linearly with a, e.g., Gaussian Mechanism.
Definition 21 (Zero Concentrated Differential Privacy (zCDP)) A randomized mechanism M satisfies p-2CDP for all neighhoring datasets D, D) and for all a >
Da(M(D))M(('') S pc,
where (P((Q) the Rényi divergence of order a.
Lemma 22 (p-zCDP to (e, 8)DD) If mechanism M satisfies p-zCDP, then for any ō E (0,1), M satisfies (p + 2 (1g()))) S).D.
Proof Since M satisfies p-zCDP, M also satisfies (a,, pa) RDDP for any 1. By [Mir17, Proposi-
tion 3], for any 8 E (0, 1), M satisfies (pa + log(1/8) 8D- The remaining proof is by minimizing a-1
f(a) = pa + log(1/8) for a 1. The minimum is + 2 log((10))) by choosing minimizer
[18(1/8)
a-
P
We now introduce RDP accounting results DP-SGD. We first demonstrate RDP guarantee for one- step DP-SGD (i.e. sub-sampled Gaussian mechanism, Lemma 23) then show the privacy guarantee for multi-step DP- through RDP composition (Corollary 24).
Lemma 23 (RDP guarantee for subsampled Gaussian Mechanism, Theorem 11 in [BDRS18) Let M be p-cCDP Gaussian mechanism, and S., be subsampling procedure the dataset with subsampling rule y, then the subsampled Gaussian mechanism M o S,, satisfies (a, ((o)) with:
log(1/7)
E(a) 2 13?2par pa, for any a S
(10)
4p
Corollary 24 (RDP guarantee for DP-SGD) Let M be Gaussian mechanism satisfying Po-zCDP and S., be a subsampling procedure on the dataset with subsampling rale 7, then T T-fold (adaptive) composition of subsampled Gaussian mechanism, Mr := (Mo o...... (M S.y.. satisfies
Times
(a,e(a))-RRD -DDP with
s(a) 2 13-2po'''s for any 5 log(1/7)
(11)
4po
28

---

Denote = 13 PoT for shorthand, further Po - 1o/(1/>)
the composed mechanism
4(1+V loc
Mr satisfies (p + p ( for any å E (0,1).
Proof By RDP accounting subsampled gaussian mechanisms Lemma 23 and the composition
theorem for RDP ([Mirl7, Proposition IJ), we have Mr satisfies (a, 13 PoTa)o for any
(1, ) Denote p 13y² PoT. By Lemma 22, if 1 log(1/6) log(1/>) (i.e., the
4po
optimal a² I ) we have My satisfies (p + plogl//1///) 6)-DP.
1pu
H.3.2 Convex and Lipschitz case
In this section, we analyze the convergence of DP-SGD in convex and Lipschitz settings.
Lemma 25 (Convergence of DP-SGD in convex and L-LLipschizz setting) Assume that the indi- vidual loss function is convex and L- L-Lipschitz. Running DP-SGD with parameters 2
nvE
o2 4161. (18(1/8) T
d'log(1/8) 11
2²
1122124001122000
C²
satisfies (e, (3,8)-DP for any
8 S (d ((A8)log log(1/0). Moreover,
E [Fr( F
with 0r being the averaged estimator. addition, the number of incremental gradient calls is 9
2n2
(lg((1/))
Proof We first state the privacy guarantee. Since each gaussian mechanism satisfies 12/20"-2000 -CDP, by Corollary 24, the composed mechanism satisfies p-zCDP with p (s, appproxxiie DP.
,3
2 16 (og(())))) and thus
Let 9: be the output from noisy gradient oracle with variance o² and subsampling rate y (line 7 of Algorithm 3). The variance of the gradient estimator can be upper bounded by:
d +
nL
ف (9))
72
By [GG23, Theorem 9.6], have:
F(..) - Fr)
5 C
1 T
do
nT?
E
+ m
[F((1))
+1
+
T
Tn
T
7/2
1=1
2
do nL?
+ 11
n2 22
Tn
73
c
dg²
nd²
1212
T
72 7
=0
(VOL
n
d
n
=
T + +-+
Tx
where the third inequality by choosing 1
and the forth line is by p
T( 12
do miz
7
13T-213/202. By the choice of I and have
2 max
{ T T
This implies:
(F(0.) F*) so (
n T Tppt Th
n
0
CLa'/2) (CIL'
T
p1/2
29

---

Since the target approximate DP privacy budget = 4 4 we have vp 4v1oR(1/8) Plugging this into the bound above, have:
CC 1oo21oo""" 10g (1/6))
[[(OT]] - F S T Σ (F((:)
0o
8
For the number of incremental gradient calls (denoted as 9), we have
g = m²T 2
Vdlog(1/8)
H.3.3 Strongly Convex and Lipschitz case
Lemma 26 (Convergence of DP-SGD in strongly convex and L-Lipschitz setting) Assume indi- vidual loss function X-strongly convex and L-Lipschitz. Running DP-SGD with parameters
(oogg1(1/ o² 4161 log(1/6)
a²c²
T
Zlog(1/8)) mA(++I] satisfies (e, DDD for any
n/e
s (d 8) (10()/)). Moreover,
T
t0 ]
dI.2 [d12
log(1/0) nde²
E
Σ
F so
T(T
+ 1)
and the number of incremental gradient calls is
2m22
g
/llog(1/0)
Proof The derivation of privacy guarantee follows the same procedure Lemma 25. By Corollary 24,
2 and apply convergence the total zCDP guarantee p 1312"211 Choosing learning rate 7) π[е+1ī
2n
result from [LJSB12], where A = nW be strong convex parameter of F, we have:
T
21 [
ge 12
E
lart
F*
T(T + 1)
A(T
+1)
2 L22
do
nI?
+
AT
PT
ArT
L
n
d
n
0
A
T
P
TT
where in the last line we use the fact that p
13T,
By the choice of T and 7 we have
2² > max T }. This implies:
T
dL' dL' o
dL log(1/8)
Σ 1ot
Fr
so
T(T +
Ap
nde²
where the last equality is using the fact that the target privacy budget e = 4 Alopoogl11 (1/8).
For the number of incremental gradient calls (denote 9), we have the same result as in Lemma 25:
2n/233/2
G / llgg(1//))
30

---

H.4 Analysis of Purified DP-SGD
Lemma 27 (Error from Laplace perturbation) Suppose Rd and 5 x Lap then
E||| =1|2]
2db.
Proof
B|I ]||2] E
V ||00 E|3
Blll =1
22db
H.4.1 Proof of Theorem 3
Theorem (Restatement of Theorem 3) Let the domain C. Bd be a convex set with &g diam- eter C, and let f(:x) be L-Lipschitz for all x X. Algorithm 4 satisfies 22 2e-pure DP and with 2/2 1-11) incremental gradient calls, the output Bon satisfies:
1. If f(xx) is convex for all x E X, then E [[((oou)] C S (CLd/nE).
2. If f(;x) is X-strongly convex for all x E X, then E [ (fout)) -
2w Proof Setting = 3/2 8 2 = -2 21-4d d nn 2d 2d- 2 we have
log(1/6) O (dlog(2) + d (log(n) n2) + d log d) + +d (l)g(()) = ((d)
(12)
Applying Corollary with defined above and choose e' the additional error from purification can be upper bounded by - + S.
(When f is Convex and L-Lischhit::: By Lemma 25 and dividing both sides by m:
L
CL
C2d 2ool//1oo'' 1/2 (1/8)
E [[((6ou)) L*
+
+0
n²e
n²
mE
L
CL
CLd
①
n2E
n
ne
(When is X-strongly Convex and L-Lipschitz): By Lemma 26 and dividing both sides by
L
CL
doL'log(1/))
E [[((tt))t]] )] L-
+
+0
n2g
n²
n²X=2
CL
d2
= Ö
+ n
n
x²
The number of incremental gradient calls for both cases:
2n2 Ô =
/ /dlog(1/8)
I Deferred Proofs for OP-Frank-Wolfe
L11 Approximate DP Frank- Wolfe Algorithm
Given a dataset = Ti..... In and a parameter space C, we denote the individual loss function by f:CxA
X X + R. We define the average empirical loss as follows:
L()) = 1
(0:a
(13)
For completeness, we state the Frank- Wolfe algorithm [FW* 56] as follows.
The differential private version of Algorithm 5 is modified by using the exponential mechanism to select coordinates in each update. We follow the setting in [TGTZ15) with initialization point
zero.
31

---

Algorithm 5: Frank-Woor algorithm (Non-Private)
2 Input: C C IRdd loss function L C -> IR, number of iterations T, stepsizes f/--
4 Choose an arbitrary 0, from C
6 for f 1 to T do
8 Compute 0g = arg mingee (VL(0)) - 0t)
Set 0++1 0: + (0 0()
Output Or
Algorithm 6: Approximate DP Frank Wolfe Algorithm [TGTZI5]
2 Input: Dataset D {di,.... d, I. loss function f defined in Eq. (13) with & Li-Lisschitz constant L1. privacy parameters (e, 6). convex set = conv(S), ||C||| = max.es ||s||]- Initialize 0g <- E C.
6 for to
L.llCll log(1/6)
E (s, VL((;;)) Lap
where
ne
Lap(A) ~ 1a1//
10
0, + arg min.es as
0++1 (1 - ne
, (1-1))0s neO where T/-
-12
i+2
Output priv Or
Lemma 28 (Equation 21 of [TT7114)
Running Algorithm 6 for T iterations yields:
E [((r:: min [(0; D) O
Tc
I log(1/ loL [S])
+
#EC
T
nE
where Dc is the curvature parameter [TGTZI5, Definition 2.1], which can be upper bounded by 3|[CI? if the loss function f is 3-smooth [TTZI4].
The sparsity of Or is given in the following lemma.
Lemma 29 (Sparsity of DP Frank-Wolfe Suppose S C fxr Rd nnz(x) S s). After running Algorithm 6 for I iterates, the output OT is T's A d-sparse.
Proof From Line and of Algorithm 6, we know nnz (ft+1) S mnz +s. Since nnz(60) = we have (fr) < Ts. Since fr E R.d., we have nnz(Or) S d. Therefore, mnz(fr) S Ts A d.
1.2 Pure DP Frank-Wolfe Algorithm
Algorithm Pure DP Frank-Wolfe Algorithm
2 Input:
Dataset D, loss function L defined in Eq. (13), DP parameter convex polytope CSn where is the vertices set, number of iterations T, a Gaussian random matrix T E TD xxd constructed by Lemma 44 satisfying (1/4, RRC with high probability.
Set parameters T -
[ L1
k
+ (T log 4
log n). w 1.
2
[nkje
Opw +- Algorithm 6
P O) FW
O O +- x0rw Rk
Dimension reduction
O Opurc-k Apure (Maps Clipzjcc1, (0apx:*); 0 (2(((((())) 6, Algorithm 8, with & defined in Eq. (14)
Algorithm 1
f puree-d -roo 100000pppre (ppureek, 2)
Oout = Clipfie11, (Opuro-t)
Output: Ovut
32

---

Algorithm 8: Sparse Vector Recovery Mrec (b, Φ
2 Input: Noisy measurement b, design matrix 4, noise tolerant magnitude &
4 Define the feasible set U := {0 E I 10 b - {}
Solve Ô = arg mingeu |0||
8 Output: 0
1.3 Proof of Theorem 4
Proof of Theorem The privacy analysis follows by Theorem and the post poss-posssssing property of DP. The utility analysis follows by bounding the following (a) and (b):
B[ D) [(Frw: D) E[C(0pw: D) C(#"; D)]
(0)
(b)
For (a): Since C is an fi-ball with center 0 and é, radius ||C]|,, the vertices set is S = {or |
[[C]], nnz(x) = 1}. We note that Oww, the output of Algorithm is T -psparee by Lemma 29.
Denote the "failure" events follows: F1 {u S in Line 3 of Algorithm 1}, where the uniform sample is accepted Algorithm I; F2 == { not (e. RWWC), where the randomly sampled not (e, -eettreet well-conditioned (RWC); and F3 == {|z||| i > E). where the Laplace noise added in Line 4 of Algorithm exceeds the tolerance threshold. We first bound the failure probability P(Fi U F2 U F2), and then analyze the utility under the "success" event Ff Fg n Fý, followed by an expected overall utility bound.
Since +. we have P(F1) 1
Set the distortion rate i. and h = @ (Tlog (+) + log Constructing & following Lemma 44, and by Lemma 45, & E Rixd is (4T, RRWCC with probability least 1 ie.. P(F2) < 1.
Set
4A (I: + logn),
{
(14)
where A SV (4) 1/k
8|C
Then by Lemma with taking 2A and
nvk
b(k + log have (((3)) <
Under the "success" event M n F5 n Pg. consider the variables in Algorithm 7, we have
Oparo-k = Apure (aapx Clip (Ompx-x), e B (2((CT)) - =,,
(Line 10 of Algorithm 7)
= Apure (Qapx-k:
= B (211(1))) =,,,ww) (Under Eý. |10 ll S (1 + e)[[Cll1)
O + Taplace od 22
=
(Under Ff)
500w + w, where ||00|| S g.
(Under FG)
By Lemma 46 and pare-d = Mreo (1 (ppurckk 4, since OFw is 7 T'sparse, we have
4VT
110 10pare-d Orwll < V1 S.
Since |10pare*x @0pwll1 = || < E, i.c., Pew is the feasible set, we have |10purc-ll1 < ||@ww [la < ||C]],, therefore, by Line 14 in Algorithm 7, dout Clipfie1, (Apure-d) = 6 pure-d (under event FJ.)
33

---

Since L is L1 Lippschiz with respect to & norm, we get upper bound on (a):
[[[((oou; D) [(0rw; D) Ff F
[3]
T, Oont Orwll
4vT
- 1 VI - 5
(15)
64 L1 || (A: + logn)
3
ne
For (b): by Lemma 28, we have:
T4 +
Li |C[|
87 log(1/6) log(To) ((())
E [(0ow; D) min L(0; D)
Ff
F3
= 0
BEC
T
I 87 log
log (TL1 [T [S])
0
T
Therefore,
E
C(oouti D) min L(0: D)
Pf n
F n
P3
DEC
// (k + log m)
3 B|
LI
87 (1/() (Tg(LL)))))) ||||] |S|)
0
T
LIICCITT
BICR T
L
(6
2
[nk]*
nE
BIICIR
L CIICCIITT
T
ns
@(V neB Cl1l
By setting T
have
(BL, 1211)1111)1/32
E
C(Oouti D)
min L(0:
FT
P3 F
<ó Ö
(16)
DEC
(nE)
By Line 14 in Algorithm we have ||0oue l1a < ||C|]1 Therefore,
E
[(Oouti D) min C(0; D) F U F2 F
< Lil1out - -0 S 22,1|C1h.
dec
E
L(fout D) min L(0; D) AEC
5 (BL) (C
3
211 221111C111
(nE)
(BL, (BL,|IC1)) (C
(nE)
For the computation cost, each iteration, the full-batch gradient is calculated; therefore, the cost for calculating few is Ind (n33/2d). The computation cost for Algorithm is O(d). Therefore, the computation cost (n d), plus one call of the LASSO solver.
1.4 Proof of Lemma 30
Lemma 30 Let A be any E-DP ERM algorithm. For every parameter d. There is DP- ERM problem with a convex, 1-Lipschitz, 1-smooth loss function, a constrained parameter space (0 TR. | 1} and a dataset Data {.1...., In 2 that gives rise to the empirical 5>x iil E(0; I.)), such that with probability at least 0.5, the excess empirical risk
risk ((A)
log(d + 11
C ((A(Data)) min L(0) > #i
+ log(4) A1
34

---

Definition 31 ((a, a-ccurate ERM algorithm) Given parameter space Q dataspace X, and risk function R, we say an ERM algorithm M X + is (a, 3) accuuraeeee for any dataset E X", with probability al least over the randomness of algorithm:
R(M(D); D) -mnn R(0: D) Sa BEB
Lemma 32 (Restatement of Lemma 30) There exists a hard instance with samples over Bi and 1-Lipschitz loss function L such that any E-pure differential private (a,, 1ia,)///accuttte ERM algorithm M must have:
log(d + 1) aK 2 nE + log(4) A1
Proof Lemma We proof by the standard packing argument. Consider Bf and an a-packing over it: [0] with K being packing number (a, By l12). For any E [K], let E, = (0
θ | 0 0:112 at) and X; ( }.)-
copies
We define the error function is (i);X,) = E 10 xx,0)ll2. Notice that:
2 ((M(X,) & >
Σ P(M(X)) E E
jE[K]
Σ exp(-ne) x P(M(X,) E F.y)
(17)
jE[K]\s K <eep(-nss
4
Taking log of both sides, we have
nE + (4) 2 log(())
(18)
It remains caleulate the packing number K. Notice that M(a, By || (122) N(a, Bi, ll (12)
exp ( lo)( where assume
Va [Wul6, Equation 15.4]. This implies:
2
V Vd
(19)
nEE + log(4)
where 52 hides universal constant and logarithmic terms w.r.t. d. We conclude the proof by observing that C(0; X,) S 1, which implies that S 1.
J Deferred Proofs for Data-dependent DP mechanism Design
J.1 Pure DP Propose Test Release
Definition 33 (Local Sensitivity) The local sensitivity of query q on a dataset X defined
as
Alocal (X) = max (la(X) q(X")
X"=X
where X = X denotes that X' is neighhoring dataset of X.
We first present the original version of PTR in Algorithm 9. The pure DP version, obtained via the purification trick, given Algorithm 10. Their privacy guarantees are stated as follows:
Lemma 34 Algorithm 9 satisfies (2 8D-DP and its purified version, Algorithm 10 satisfies (2s E', 2'PP)-DP
Proof The privacy guarantec for Algorithm is based on [Vad17, Proposition 7.3.2]. For Algo- rithm 10, the privacy guarantee follows from the post-pre post-processing property of differential privacy and the privacy guarantee of Algorithm 1.
N covering
35

---

Algorithm 9: MXTR(X, q. 6) Propose-Test-Releeee [DL09]
2 Input: Dataset X; privacy parameters E, ô: proposed bound 3; query function X -
4 Compute: (X) = min dammingg (X, X A Locall (X') > 8}
X²
+ 6 (X) Lap ( log(1/6) then
8
Output 1
else
Release f(X) + Lap
Algorithm 10: Pure DP Propose-Tese Test-Relase
2 Input: Dataset X; privacy parameters e, e', d; proposed bound 3; query function q X O level of uniform smoothing w
A MPTR (Xe,R((X90)) E, 6, 6)
6 if 0 == then
Unif(e)
0 4
12 Oont + Apure (0, 0 (,,,,,)), Output: Oout
b. Algorithm
J.2 Privately Bounding Local Sensitivity
We assume query function X + θ with θ C Rd being convex set and Diamz(0) = R. Assume the global sensitivity of local sensitivity upper bounded by 1: max
X-x"
LLocal (X)) < 1. The purified version of PTR based on privately releasing local sensitivity is stated in Algorithm 11 and its utility guarantee included in Theorem 11.
Algorithm 11:
2 Input: Dataset D; privacy parameters e, 8 proposed bound 33 query function x + O c Rd with De) = R. level of uniform smoothing w
3 A Local (D) + Lap (1/s) + log(2/6)/=
Capx f (roje(((D)
Lap @d (3/e))
Ypure Apure ( ww, R)
Algorithm
10 Output: 9pure
Theorem (Restatement of theorem 5) Algorithm 11 satisfies (3e, 0)-DP. Moreover,
E Iou (D) ((D) 5 d Loral D))
d3/2
Proof First notice that 9 satisfies c-DP by the privacy guarantee from Laplace mechanism and the assumption that global sensitivity of ALocai( is upper bounded by 1. Second, we notice that P(. Ai (D)) P(Lap(1/E) log (8/2)/))
8. This implies (DD) + Lap @d (3/=) satisfies (s, d) prrobabbilistic DP ([DRV 10, Definition 2.2]), thus satisfies (s, dD- By post-processing and simple composition, Qapz satisfies (2e, 0D. Finally, using Apure under appropriate choice of 6,
we have Spure satisfies (3e, OD by Theorem 1.
We now prove the utility guarantee. For notational convenience, we denote 20 Lap (1/e), Z1 Lap @d (ß/e) and Z2 ~ Lap @d (A/e). By definition of Jpure. have:
Ipuuree - (D) = E [|| Aapx - ((D) + Z2|12] + wC
E Proje (q(D) + Z1) q Zella] +WC
(20)
< E [|| ||2] + + [1] + WC
36

---

Notice that:
[1 S E 11
(Z11 denotes first element 21)
A Local ()) + logg(2/0)//
1 E [10ll
E
Vd(aL (D) 111022210088)
Now, set
100 A 0e
and (16dCe)a By Corollary 4, we have:
+wC wC S g²
Also notice that l2g(2/6) (cd). Thus,
E Ipare {(D)lla) VdA
Locai()) d3/2
+
E2
J.3 Private Mode Release
The mode release algorithm discussed in Section 5.2 is provided in Algorithm 12.
Algorithm 12: Pure DP Mode Release
2 Input: Dataset D. pure DP parameter
4 Set: log (1/8) = log (2d /E), where = loga |x
6 Compute the mode J(D) and its frequency oce,, as well as the frequency 0002 of the second most frequent item.
Compute the gap: (DD) + 1000 -000
(D)
10 if (D)) + Lap (t) S
(8g(1/8) then
12
Mapa <-
else
16
Uapx < S(D)
Upure f Algorithm 2 with inputs e, 6, Uppa, y X, and Index id, the identity map.
Output: Upure
Proof of Theorem By [Vad17, Proposition 3.3] and that dist(D, (D' f(D") & f(D)))
Toccy -00c we know Vaps satisfies (e, DD. By [Vad17, Proposition 3.4], when ocC1 - 0002 >
[[nn[1 ( /1/ s].
Uapx is the exact mode, i.e., Uapx fDD, with probability least 8. Choosing
8 [2djaz by Theorem and the union bound, we have IP (Upare S(D)) 2 1 - 5 2 2-d $
1
J.4 Private Linear Regression Through Adaptive Sufficient Statistics Perturbation
We investigate the problem of differentially private linear regression. Specifically, consider fixed design matrix E IR xxd and a response variable Y RR", which represent a collection of data points (Ii, y1 ))){_ where 2; Rd and yı E R. Assuming that there exists 0* E O such that = XO", our goal is to find a differentially private estimator that minimizes the mean squared enror:
1
MSE(O) = Y X
2n
We assume prior knowledge of the magnitude of the dataspace: || := sup || and ||>||| == sup,ey l| Our algorithm operates under the same parameter settings as [Wan Algorithm 2].
To enable our purification procedure, first derive high-probability upper bound on ||0||,, where
37

---

Algorithm 13: Mpure-AdaSS
2 Input: Data X, ys privacy parameters c, ,', 6, Bounds: ||]] [Di]], level of smoothing w
0 Oapz AdaSSP X, y, e, 6, ||-1| ([D)
& [Wan18, Algorithm 2]
6 Propose a high probability upper bound = Ô (1+te//)DD1/)1x11)
8 Construct trust region e = _ (R)
Norm clipping Oapa <- Proje (Oapur
Qure f- Apure Oapar e',,,,,))
Output: 0pre
i is the output AdaSSP. Subsequently, we clip the output of AdaSSP and apply the purification procedure. The implementation details are provided in Algorithm 13.
Theorem 12 (Restatement of theorem 7) Assume X X is positive definite and ||C||| S ||
With probability C 1/n²,, the output pure. from Algorithm 13 satisfies:
1211 62
d
MSE(Opure) - MSE((0)) SO
(21)
2nn Amin
where Amin = Amin Amin(X (XTT/))..
Proof First, we introduce utility Lemma from [Wan18]
Lemma 35 (Theorem 3 from [Wan18)) Under the setting of [Wan18, Algorithum 2J, AdaSSP satis- fies (s, 8)-DP. Assume ||>|| & | then with probability 1 Ç.
dllog da
11
| | 10 (X
MSE - MSE
(22)
nc/
log (9)
nc? /log log
de
Now, we prove the utility guarantee for our results. order to operate the purification technique, we need to estimate the range |0|| in order to apply the uniform smoothing technique. Notice that
|10| < |[X + Ala + E1) 21
X + Ealla
(23)
(a)
(b)
with Fgg y /
(O, Ta) and FA Y \1
Z, where Z RRdxd a symmetric
8/3
E/3
matrix, and each entry in its upper-triangular part (including the diagonal) is independently sampled from NO, 1). Under the high probability event in Lemma 35, we upper bound (a) and (b) separately:
For (a):
1
X A F1)
Amiin (XTX + Ala + En)
By the choice of À and concentration of 112, have (x X + Pla + Ei) 1 Ala). which allows lower bound on Amin (X X + AI Ei):
20min (X X Ala + E1) > Amin (X + ATa)
2 Amin X (XT + À
Amin (TT)) + /
X
e/3
/ ddlog 66/8) (2gg(22//))) /292
e/3
38

---

V (6/6)6666) log(2d) /C1|
where the third inequality is by setting max 0,
Amin f where
c/3
Xmin high probability lower bound on Amiu (XT Thus,
1
| X + Ala + Fill2 = Amin(XT0 + Ala + E1)
2
Amin (X TTXx + Xla)
28
5
3/ ad log (1o0()/0) log 2nd2 /c)
=
/dlog(6/8)12213
For (b), by triangle inequality
(b) = || y + F2ll2 S || vll2 + | S x + F|
Apply [Wan18 8, Lemma 6], we have w.p. at least 1 - 3:
Vdl log(l///////////// 66 log d/3)
| 0
Thus, w.p. at least
3 over the randomness of Eg,
+ vdl X / (og(6/0 log log(d//) (d/3)
(b) 5 |1||X||1|>||
VdI. (
+
Putting everything together under the high probability event:
||01|a <
|
1+ /
nE
||
||3/|
(1+ NE
= F
||
d
Now, we apply purification Algorithm with θ = B (7). w 12. 8 parameter configuration implies log(1/6) = O(d) and Wasserstein-oc distance A Infa (Line 2 of Algorithm 1)
2w
This
(16d9/"Pn2)d-
Finally, it remains to bound the estimation error for 0pare. Let's denote the additive Laplace noise from purification by Zz Lap (AE),, and the purified estimator 0pure Ø + Zz. Under the event that the purification algorithm doesn't 't output uniform noise, which happens w.p. at least 1 - w:
(Ap
1 1l 2n
MSE (00ur))) - MSE
|1y X0 0pareel2
X x0
2n
1
X X
1
Amaxe (XT X) 12
<
||
39

---

where the last inequality holds w.p. 1 1/n² by Lemma 48, we derived below:
2/A
2A
|| v
log(n")
E
Ô
8T12
Under the high probability event of Lemma 35 and Algorithm 1, which happens with probability at least 1 - --11/m2 1/n?
MSE MSE(Opure) MSE((") MSE pprr)) MSE + MSE(O) M))
11
11 d 1 tx (x( 1
82nd
nE
(24)
||
1|
0012 TE min (X x)
< Ō
E2n
x
By denoting Amin
Amin
we have:
n
|2
|| 81101111101112
MSE(Opprd) - MSF((0) S S
(25)
c2nd
en xmin
n1
K
Deferred Proofs for Private Query Release
K.1
Problem Setting
Let data universe X 10 1]dd and denote N = X The dataset, D E X is represented
histogram D Nolx1 with || n. We consider bounded linear query function X - [0, 1] and workload Q with size K. For shorthand, we denote:
Q(D) (D) - . (D))
Σ (d.)
Σ (x((e) iE(m)
REIM]
K.2 Private Multiplicative Weight Exponential Mechanism
We first introduce private multiplicative weight exponential algorithm (MWEM):
Algorithm 14: Multipliative Weight Exponential Mechanism MWEM( D, P,T,P) [HLM12]
2 Input: Data set D E NIXI, set Q of linear queries; Number of iterations T E N; ZCDP Privacy parameter p > 0.
Set: number of data points
||]|,, initial distribution Po
1 [x]
privacy budget for
each mechanism En / P/
Define: Score( :; = (1,p)) (t.p))
for to T' do
10
+ ExpoMech 50, Score(: :P)1.)))
m, t (qt, X) Laplaco( (/naa)))////))))))))))))))))))
14
Multiplicative weights update: let P++1 be the distribution over X' with entries satisfy:
(x))) x (z)) exp(q((x) (m, - q. (pt- Vz e X
Output: Dout 7. ET-1 Pt-
40

---

Algorithm 15: Pwwportiooaallaanneee.n Proppprtttonnll1mmmmigg.////
Input: Dataspace X, Probability vector p E R sample size
4 for to m do
-ubortaaerroopttoollllsmmaning X) D e.g., Alias method [Wal74]
Output: {mmm
Algorithm 16: Pure DP Multiplicative Weight Exponential Mechanism
2 Input: Dataset D E N with size |D = n, Query set Q, privacy parameters c, 6,
accuracy parameter
Set: Number of iterations T
size of subsampled dataset
2 2 2-3/3, zCDP budget p =² log((1)))
Score p) = kg. p) (g. 4g Q
Initilize: P1 [ p
1
1
D MWEM D, Q, T.
Algorithm 14 Algorithm 16
10 Y + Sampliing D/n,m) Y < dpure-discrete (E, x")
14 Output:
Lemma 36 (Privacy and Utility of MWEM (HLM12)) Algorithm 14 instantiated as
KWEM D. Q, e2 (1610g(1666) satisfies (e, 6)-P. With probability - 233,, PMW and the outpul Q> such that:
- - so 50 VTlog(1 (1/) log (/B3)
(26)
nE
Proof We first state the privacy guarantee. Since each iteration satisfies zCDP guarantee p/T-zCDP, the total zCDP guarantee for T iterations is p. By Lemma 22, the whole algo- rithm satisfies (4g/log(1//), 6D-DP. Plugging in the choice of p log110)(1//), we have MWEM(D, "/11////////1////// satisfies 8)-D. The utility guarantee follows (HLM12, Theorem 2.2]. Specifically, we choose adderr HTTT//log(K//)) this yields the utility guarantee stated in Theo- rem with probability 2,T..
Lemma 37 (Sampling bound, Lemma 4.3 in [DR-14) 14)) Let data X
(a), aN) with
EN a 1 and a; 2 0. Y Multinomial(m,.X X). Then we have:
PY) Q(x)l 2 a| S 2/Q)
Proof The proof follows the proof of [DR+14, Lemma 4.3]. Since we have Y= (Vi,..,, Ym)) with
Y, iid Multinomial(1, X), for any 7 Q. we have q(Y) Th En ((Y)) and Elg(Y)) ((X).
By the Chernoff bound and a union bound over all queries in Q, we have PIIIQ(Y)- Q(x) a] 2[Q] exp(-2ma²).
Theorem 13 (Restatement of Theorem 8) Algorithm 16 satisfies 2s-DP. Moreover, the output Ý satisfies
((D)-Q(('114) 20 d1/3
1//3g//3
and the runtime is Ö(nK + 2/3 /3 +N).
Proof We first state the privacy guarantee. By Lemma 36, the output from multipicattive weight exponential mechanism, D, satisfies (s, 6D- By post-processing, Y is also (s. (DDP). Thus, apply Theorem 2, the purified Y satisfies 2s-DP.
41

---

The utility guarantee is via bounding the following terms:
[I(()) 1z [Q(()) - -11)) Q(0)l
(a)
(6)
(c)
For (c): Since the output space ) = xm if use binary encoding, the length of code is loga (13)) =
md == d. Thus, by Theorem 2, we choose (2djad this implies log(1/6) (md log 2md/=)
and failure probability 3o 2 +
rdd exp(md)
For (a): In order to minimize upper bound in Equation 26, we choose T
11 (8) log( (K/9)* this
d=12n5
implies [[Q(D) [x S
d//4 (1/6) log (K/8)) O [1/2 1/4 1/ (2mdd/3 / l (KK/8)
(ns)
(ns)1/²
For (6): using Sampling bound (Lermaa 37) and setting failure probability 81 2K exp( - 2maa) we have IIQ(D) l S O log" (2K//))
m477
Finally, we choose (ns/d)2/3 to balance the error between (a) and (b). This implies: d1/3
[Q( - Q 0 (ne)1/3 (logl/2 (2(2/33)))))))))))) log // (K/B) log (2d -1138
2(m5)2/3/1/3
Set 1 and 31 = n; and by Bo
= o( we have
2/nc)2/3
d//3
B[][Q(D) 1om) < 0
(log (2nk/ + log (2gg//((Kd)) (x ( (2d --13)
(nE) 1/3
+ (T + 81 + Sb)
d/3
=
1n3)
The computational guarantee follows: (1) Since T
d:/2
2/ The
(/1 (og(K/a)
runtime for MWEM is ÖnK 2/3 [HLM12]; (2) For subsampling, by runtim analysis of Alias method [Wal74], the preprocessing time is O(N) and the query time is (m)) for generating m samples. Thus, total runtime is O(N + (n=))/3 (3) Finally, note that the query time for Algorithm 2 is ((d) = (adl/33(3))) 2/3)) We conclude that the runtime for Algorithm 16 is Ö(nK~ + 2/3 / NK N).
L Deferred Proofs for Lower Bounds
L.1 Proof of Theorem 9
Lemma 38 (Lemma 5.1 in [BST14]) Let n, E N and > O. There is number M P (min(n, d/e)) such that for every e-differentially private algorithm A, there dataset
{ZI...,, C. (-1/v,, 1/v3"* with || E Tzll2 E [M M + 1] such that, with probability at least 1/2 (taken over the algorithm random coins), we have
A(D) - D11 = = min (1, en (1,m)
where D =
Theorem 14 (Restatement of Theorem 9) Denote D == (-VaV, Let S O(L), and E exp(tdlog(d) log"(nd)) And log2"(5d) For any (e, 6)D mechanism M, there exist a dataset D e D such that w.p. at least 1/4 over the randomness of M:
[IM(D) - D112 δ /dlog(1/0)
(
En
Here, (1-) hides all polylogarithmic factors, except those with respect 8.
42

---

Proof Suppose there exists an (e, 8)diifferentially private mechanism M such that with probability least 3/4 over the randomness of M, for any
[IM(D) Dl12 V
nea
/ /lg((1/)) nea
where a a term involving n and d, to be specified later. Let
implies:
1/2
8 >> exp(-a"t) log(d))
(27)
We execute Algorithm to purify M directly the output space -iVaa, Y denote the output of Algorithm I and U ~ Unif([-I/va 1/Vā(). The remainder of the proof involves bounding additional errors introduced during the purification process, By triangle inequality we have
|| 1 $ D - M(D) [IM(D)
||MD))) Yil2.
(n)
(bi
Notice that under the event that Line 3 of Algorithm 1 doesn't 't return the uniform random variable, which happens with probability 1- have Y .M() Laplace (d (2A/E), (2A// term (b) equals
the 2-norm of the Laplace perturbation.
For the remaining proofs, choose the mixing level 1/8 in Algorithm 1. We now justify the choice of 8:
Observe that since Y M(X) Laplace (acaicee*2222 (2A/e), term (b), which accounts for the error intro- duced by Laplace noise. With probability at least 7/8 by the concentration the L.2 norm of Laplace vector:
(b) S 2vds log(8d)
Thus, without loss of generality, we require
2/dA log(8d)
16d this implies
(8dj
8
A
log 18g)
Notice that:
2R2
8 1/d
A = d=
2w
Choosing q oc (corresponding the use of to norm in W-oo distance), and noticing R 2/vd and 1/va, we obtain the condition:
8
8
A = 8vd
2w
n log 2 (8d)
which further implies:
8 85 4nd logllog 2d (8d)
(28)
By Eq. (32) and Eq. (33), we have:
8 E (xx((_a²d) log(d)),
(29)
4nd log 2d (8()
The constrained above yields lower bound a² after relaxation for simplicity (and assume z log(8d) and d log(n) > log(4)):
a > 2 log (d) log(nd)
(30)
43

---

Thus, we set a 2 d) log(nd) to satisfy the constraint stated in Eq. (35), and now
8 E exp Ad log(d) log (nd))
(31)
4nd log (8d)
When d is within the range above, we have:
log(1/8) < 4d ldgo)( log" (nd)
This implies that, w.p. at least 1/2 over the randomness of M and purification algorithm:
d
16d
|| 1l1 S
ns log (d) ne log (1))
which violates the lower bound stated in Lemma 38. Thus, for any (s, 6)-DP mechanism M with being in the range of Eq. (36), there exists dataset D D, such that with probability greater than 1 /4 over the randomness of M:
v Volog(110)) IM(D) - DDl22 2nd log(d) log(nd)
V Vdlog(1/0)
Here, (2(.) hides all polylogarithmic factors, except those with respect 5.
L.2
More Examples of Lower Bounds via the Purification Trick
In this section, we present an extended result for Theorem 9. Additionally, we establish lower bound for the discrete setting, as stated in Theorem 16, thereby demonstrating that the purifying recipe for proving lower bound remains applicable the discrete case.
L.2.1 One-Way Marginal Release
We establish a stronger version of Theorem 9, as stated in Theorem 15, which strengthens Theorem by establishing that the lower bound holds for any (0, 1), rather than being restricted to 1/2.
Let < O(1), for any c E (0, 1), and 8 (matga,, In Ino For any (e, 8DD mechanism M, there exist dataset D E D such that with probability least 1/4 over the randomness of M:
Theorem 15 (Restatement of Theorem 9) Denote = (-1/va,
log' ((15)
ILM(D) - DIl2 2
max (E(0.1)
ETI
Here, 51(-) hides all polylogarithmic factors, except those with respect to
Proof Suppose for some E (0, 1), there exists an (e, ddifferrenny private mechanism M such that with probability at least 3/4 over randomness of M, for any D E D,
[MM(D) D112 d log (0000((100)
where a is term involving and d, be specified later. For the purpose of causing contradiction. we let:
d log 1 ((1/8)
d
nea
nE log (d)
This implies:
8> cxpp-ar-paappp log(d))
(32)
We execute Algorithm to purify M directly over the output space 1-1/v,,1/V Let Y denote the output of Algorithm and ~ Unif([-I/Va, 1/vajd). The remainder of the proof involves bounding the additional errors introduced during the purification process. By triangle inequality have
| 2
D M(D) IM(D) Y|12
(4)
44

---

Notice that under the event that Line 3 of Algorithm 1 doesn't 't return the uniform random variable, which happens with probability - -w, we have Y = .M(X) Laplace @d (24 (2) so term (b) equals the 2-norm of the Laplace perturbation.
For the remaining proofs, we choose the mixing level 1/8 in Algorithm 1. We now justify the choice of 8:
Observe that since Y M(X) + Laplace * (2A/s), term (b), which accounts for the error intro- duced by Laplace noise. With probability at least 7/8 by the concentration the L2 norm of Laplace vector:
(b) 2vdA log(8d)
Thus, without loss of generality, we will require
2 da log(8d)
16d
ne (8d)
This implies:
8vd
A
n logg Log2((0)) (8d)
Notice that:
2R
8
1/d
A d
2w
Choosing q oo (corresponding the use of &o norm in the Wassertain- distance), and noticing R = 2/va and r = 1/vā, we obtain the condition:
8
1/d
8Vd n log (8d)
A 8vd
2w
which further implies:
8 4nd log (8d)
(33)
By Eq. (32) and Eq. (33), we have:
8 E exp (-atted log(d),
1
And log 2d (8d)
(34)
The constrained above yields lower bound on after some relaxation for simplicity (and assume d > log(Sd) and dllog(n) log(4)):
T- > 2 log(d) log(nd)
(35)
Thus, set (2log(d) log(nd)) 1-c to satisfy the constraint stated in Eq. (35), and now
exp (2 4n log (B0))
1
8
(
4nd log (8())
(36)
When is within the range above, we have:
log(1/8) < 2d log(nd)
This implies that, w.p. at least 1/2 over the randomness of M and purification algorithm:
d
16d
|| Yll2
ns log (d) ns log(8d)
45

---

which violates the lower bound stated in Lemma 38. Thus. for any (E, 6D mechanism M with being in the range of Eq. (36), there exists dataset D. such that with probability greater than 1 1/4 over the randomness of .N:
d' log8 ne (2 (2log(d) (og(())))
d" log (oggt((1//) (1/6) =
[MM(D D112 2
nE
Here, .?(-) hides all polylogarithmic factors, except those with respect to 6. Since the above derivation holds for arbitraty e (0, 1), this implies with probability at least 1/4 over the randomness of the algorithm M, we have:
d' "og""((1/0)
IIM(D) D112 2
max
cE(0.1)
me
L.2.2 Private Selection
We begin by stating a lower bound for pure differential privacy in the selection setting, as established [CHS14].
Lemma 39 (Proposition in [CHS14) Let e E (0, n 2 2 and denote item set to be U. For any E-DP mechanism A, there exist domain X and function f(i, which is (1/n)- -iipschiit for all item E such that the following holds with probability at least 1/2 over the randomness of the algorithm:
log(K)
max TEU
20
Theorem 16 (Lower bound for private selection) Let & E (0,1), 5
gdd ed
(2djaa (2dj3a
and [ where is the item set. For any (s, 8)-DP mechanism A, there exist domain X and a function f(i,) () which is (1/n)) Liisshiip for all item i U such that the following holds with probability at least 1/2 over the randomness of the algorithm:
log" K logg' loogg-=(11 =(1/6)
max D( SELl
maxx (E(0.1)
En
Proof Without loss generality, we set = [loga K7, we have that log K = (d). For any c E (0, 1), assume there exists an (e, 6)DP algorithm such that with probability at least 1 +- dd eexp(d)
for any D E Xm have max f(i, D) f(A(D), D) Ω log ((1/5"(1/8)) with being some NEM
Ena
term involved with n, d which will be specified later.
First, to ensure the quality of purification, we need to set 8 < (2d) 3d this ensures with probability at least 1 - 2-d exp((-l over the randomness of purification algorithm, we have Apurified (D) A(D). Further, order fulfill contrast argument, without loss of generality, we require
d d' log''-(11/0) En log (
sna
which implies:
8 > exp(-ar-a d/ log(d))
Thus, to ensure the lower bound of ā doesn't exceed the upper bound 5, we require:
8d
a log
So, set a dhe log(() log 2d this implies
8 exp(3d log (2g(s))))
(2d)3d
46

---

This implies with probability at least 1/2,
d
Di - f(Apuuitiod (D): D) S 0 iEWl
max
En log loog--1 (d)
Observe that, under the assumption of [ 2 which implies 2 exp(1), the inequality above contradicts Lemma 39, Since E (0, 1) was chosen arbitrarily, this completes the proof of the stated theorem.
L.3 An alternative proof for Theorem 9
A (dd) lower bound for mean estimation under (e, 6)-DP can also be proved using a packing argument when 8 exponentially small, as detailed in the theorem below.
Theorem 17 (Packing lower bound for (e, mean estimation) Fix constants > 0 and a E
1]. Let the data domain be X' = [--,, I]a, and let p(D) = Ei= 24 for D E X", Suppose mechanism M x IRd is ()P under the replace-one neighboring relation and, for every
dataset D, satisfies
F[IMM(D) p(D) S sa] 2 2/3.
If 8 s 1 ne, then 6
2 log 2 (d- - 1).
Proof For each {+1]d, set Mn == 0 [-1, j and define D(v) (Moy...,,o)) po) E D Then ((D(v)) My. For u # v. I1 Pell2 2 j[j uy + 1 2 2, so the a-balls
A, = (u E b |y M 1 a)
are pairwise disjoint for any < 1. By the accuracy assumption, for all we have
P(M((()) E Aul N 2/3.
(37)
If two datasets differ in most h positions, then for any measurable S, by the group privacy, we have
the -1 S 8 de
P[M(D) E S] 2 e the (P(M((D))) - 8n
-n):
Σ ie
-
Notice that in setting, dist(D(w). D( = (when every coordinate is substituted), hence for Avs
P P(M(D()) E Ao] 2 -nE (PMM((DO))) e Ao] 6m) c -ne_
2 5,
(38)
3
where we used 6n s ne so E n 5.
For fixed u, by the disjointness of the A,'s, we have:
2 Σ P(M(D(") E An] = P[M(D(") E Au] + ΣM(M(D E A.]
2//3 (37)
Ze-nez 3 b (38)
which implies:
2 3 + (2d 1) -1) (zc
1/3 e-- 8
1
2d
3
If 8 < te-- nne then the denominator is at least 3 -", and
1/3
2d S 1 +
x n5
-n
Taking logrithm on both sides yields d dlog 2 < ne + log 2, i.e., n 2 log? (d - 1).
47

---

M
Technical Lemmas
M.1 Supporting Results on Sparse Recovery
For completeness, introduce the results from sparse recovery [Tia24] that is used in Section 4.2 and Appendix I.
Definition 40 (Numerical sparsity) vector is s-mumerically sparse if
Numerical sparsity extends the traditional notion of sparsity. By definition, an s-sparse vector also s-numerically sparse. A notable property of numerical sparsity is that the difference between a sparse vector and a numerically sparse vector remains numerically sparse, as stated the following lemma.
Lemma 41 (Difference of numerically sparse vectors) Let x: E TRd be an 8-sparse vector. For any vector x! E Rdd satisfying | || || the difference x' is 4s-numerically sparse.
Proof Let S = {i E [d] x[|]] * 0} and denote v := x' We have
||>'|| | ||| | +|lss=ll | velli-llo |0s +| |lss=l1 || || -1 || +| ||
which implies ||ıs||1 || Therefore.
||u|| = ||ul|l1 + ||us=111
$ 2|||us||z
$ 2 Usll2
- / u|/2
which implies ||-|ß < 4s/]e/]2- Thus, by Definition 40, satisfies 4s-numerically sparse.
If the vector æ is s-sparse, we can reduce its dimension while preserving the & norm using matrices that satisfy the Restricted Isometry Property.
Definition 42 ((e,s) Restrrietd isometry property (RIP)) A matrix & E gkxd satisfies the (e, 8)- Restricted Isometry Property (RIP) if. for any s-sparse vector x E Rd and some e E (0,1). the following holds:
- 1x:1| || s (1 e)11=
For numerically sparse vectors, we can reduce the dimension while preserving utility by matrices satisfying related condition the Restricted well-conditioned (RWC).
Definition 43 ((e, -eettriieee well-conditioned (RWC) ([Tia24), Definition 4)) A matrix & e R (c, 8) Restrictee well-conditioned (RWC) if. for any s-numerically sparse vector x E Idd and some (0, 1). we have
(1 e) |21| |x (1 e)11=
Lemma 44 ([Tia24), Lemma 2; [CT05], Theorem 1.4) Let T E Rkxd whose entries are indepen- dent and identically distributed Gaussian with mean zero and variance N(0,, 1). For e, Ç E (0, 1), if
$ log (+) + log )
k C2C-
6²
for appropriate constant C, then & satisfies s)-II with probability 2
There connection between RIP and RWC matrices:
Lemma 45 ([Tia24], Lemma 5) For jpmXn and e E (0,1), (e, RRCC.
25 RIP, then & is also
Finally, we provide the following guarantee for Algorithm
Lemma 46 (L, error guarantee from sparse recovery) Let E Rm and 0, E R Given
noisy observation b = $0,, + t with bounded E, norm of noise, i.e. || S. consider the following noisy sparse recovery problem:
i arg min |00|1
s.t. 10000 bll S E
48

---

where Ç >> O is the constraint of the noise magnitude. Suppose that O is an s-sparse vector in IR" and that a (4s, e)-RWC matrix. Then, the following { estimation error bound holds:
4/s
10-111115
vI
Moreover, the problem can be solved in ( + 4n - 1) (2n + m) m)prcc) arithmetic operations in the worst case, with each operation being performed precision of (pprec) bits.
Proof For utility guarantee: By || S ç. 0. a feasible solution. Thus, we have ||0]] S ||0. 111. which implies := 0 0, is numeeriiyall sparse by Lemma 41. Since (e, 4s)-C we have:
(1 -> = 1 S (1 + c)
(39)
Now remains to bound |Ab|i:
|1bl/2 S v ///l/1|12
S V4s | 12
2/3
(40)
(1/00 - b111 + 1100, 6111)
v1
4
where the last inequality is by feasibility of and the structure of b. Now we prove the runtime guarantee. We first reformulate this problem to Linear Programming:
(P)
min 0, ,u
(ut + ui
subject to:
0 u u7 ut, u, 2 0, Vi = n,
$ bj < 1/j
Vj = 1,... m,
(0, bj) $ Uj Vj = 1, m,
Σ Uj S 1=1
Vj . m.
The problem (P) has 2n + m variables and 2m + 2n constraints. By [Vai89], this can be solved in O(33m + 4n + 1)2.5 (2n + m) B)) arithmetic operations in the worst case, with each operation being performed to precision of O(B) bits.
M.2 A Concentration Inequality for Laplace Random Variables
Definition 47 (Laplace Distribution) X Lap(b) if its probability density function satisfies
fx)
1 26 exp
Lemma 48 (Concentration of the & norm Laplace vector) Let X (x1,..., xrk) with each x; independently identically distributed as Lap(b). Then, with probability at least - C.
X < 2kb + 2b 2blog(1/C).
Proof
[xy] follows the Gamma distribution r'k,, b), with probability density function f(x) ITKjU= x 5. Applying the Chernoff's tail bound of Gamma distribution [[k: b), we
||X|||
have
X|| 2 t) S
k- t for > kb.
kb
49

---

Taking = 2kb + bblog(//)), we have
|| 2 2kb + 26 2olog(1/()) -
2kb + 26 log(l//))
ch
2
kb
1+ log(1/()
k
2t
222
h
2
k
2²
e
$ 5.
50

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how answer these questions. For each question in the checklist:
You should answer [Yes], [No] [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist one of the factors in their evaluation.
While "[Yes] " generally preferable to "[No] ", is perfectly acceptable to answer "[No] providedd a proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). "[No] " or "[NA] is not grounds for rejection. While the questions are phrased in binary way, acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification elaborate. All supporting evidence can appear either in the main paper the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
general, answering
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
All claims are well supported.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
51

---

Justification:
We provided limitations.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
We provide complete assumptions and proofs.
Guidelines:
The answer NA means that the paper does include thcoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
52

---

Answer:
[NA]
Justification: NA.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution
specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g., in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky some cases, in which case authors are welcome describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: NA.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm http://giieee//eueeiiiinee/eeeee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
53

---

The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: // //nips. wwwpblii/gguide//oeeeuuuuuuu soo.oiiiiiisioooooioioc.c for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: NA.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: NA.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
54

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: NA.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:://aorr....c/////////////t
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: NA.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
55

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: NA.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (c.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: NA.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
56

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: NA.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details the datasct/code/mooell as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: NA.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: NA.
Guidelines:
57

---

The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
Only for editing purposes.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: /ttpaa:///eupp...eee https////ccooeeeecce/2///////// for what should or should not be described.
58


Reviews:
[{"review_id": "OVcsGwj06l", "reviewer": "Reviewer_JJ6e", "summary": "The paper studies a question that sounds, when you hear it the first time, shocking. Is it possible to convert an algorithm with weak privacy guarantees to an algorithm with stronger privacy guarantees using some black-box approach. \nThe answer is surprisingly yes when the weak privacy guarantee means the mechanism is approx DP and the stronger prviacy guarantee means pure DP (with comparable epsilon).\n\nThe paper describes the transformation and uses it to give the best known mechanism for ERM and some other problems.", "questions": "1. I am not sure I am able to understand Figure 1: what is the dimension used? \n2. I think there is a confusion and sometimes the term support is used instead of range. \n3. In Remark 3, the transformation is applied to DP-SGD, but typically DP-SGD has unbounded range...\n4. line 190: I don't think all of these papers need to be cited.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Approx DP, while loved by specialists, has multiple issues in practice: e.g., it is not clear whether any delta is acceptable for real-life solutions operating with sensitive data. \n\nHence, the ability to construct pure DP mechanisms with performance similar to approx-DP counterparts is opening a lot of new directions. In addition, this method could simplify proofs of lower bounds for approx-DP algorithms since proving pure-DP bounds is usually not too hard.", "was_revised": true, "final_justification": "I agree that the main contribution here is the possibility of purification and it is fine if the approach is not giving optimal guarantees.\n\nThe possibility of a simpler algorithm is a bit concerning, but considering that it would require solving some (potentially non-trivial) issues, I think it doesn't lower the quality of this pape.", "rebuttal": "Thank you for your support and your questions!\n\n> Figure 1: what is the dimension used?\n\nThe 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.\n\n> confusion: sometimes the term support is used instead of range.\n\nThank 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.\n\n> In Remark 3, the transformation is applied to DP-SGD, but typically DP-SGD has unbounded range...\n\nThe 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. \n\n> line 190: I don't think all of these papers need to be cited.\n\nThank 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.\n\nReferences:\n\n[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).\n\n[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."}, {"review_id": "0ZRIxElc58", "reviewer": "Reviewer_tAS6", "summary": "This paper offers an efficient generic method to take an arbitrary approximate DP algorithm $M \\colon X \\rightarrow Y$ (i.e., $(\\varepsilon,\\delta)$-DP with $\\delta>0$) with bounded $Y \\subseteq R^d$ (Namely, that $Y$ is contained by an $\\ell_q$ ball of radius $R$ and contains an $\\ell_q$ ball of radius $r$), and transform it into a pure $\\varepsilon’$-DP algorithm, where the resulting $\\ell_q$ error is a function of all parameters (and more additional parameters like the internal mixture parameter $\\omega \\in [0,1]$). For finite output spaces, this was already known (mentioned in Appendix C): Given a dataset $D$ and an approximate DP algorithm $M \\colon X \\rightarrow Y$, output $M(D)$ with probability $1-\\omega$ (for some parameter $\\omega$), and otherwise output a uniform element in the range $Y$. But when $Y$ is infinite, the authors show that this method simply does not work. The first step of their solution is essentially the same, but this alone is not enough in the infinite $Y$ case and requires an additional step: They show that under some conditions on the parameters, for any neighboring datasets $D,D’$, an $\\omega$-mixure of $M(D)$ with $Unif(Y)$ (denote by $\\mu$) and an $\\omega$-mixure of $M(D’)$ with $Unif(Y)$ (denote by $\\mu’$) has a small enough TV distance that enables coupling in a way the ensures that if we draw $(x,x’) \\sim (\\mu,\\mu’)$ then almost surely the $\\ell_q$ distance between $x$ and $x’$ is bounded (this is called the $\\infty$-Wasserstain distance). Given that, they simply add an additional step of Laplace noise per coordinate to guarantee that the final outputs are purely indistinguishable. \n\nThey illustrate the applicability of their method by presenting new pure-DP algorithms for Stochastic Gradient Descent, Frank-Wolfe Algorithm, Propose-Test-Release, Linear Regression, and Query Release. In all (or most of) these examples, they match state-of-the-art accuracy results, but sometimes with improved running time, like in Stochastic Gradient Descent and Query Release. \n\nIn addition to all of that, they show that their method is even useful for proving lower bounds for approximate DP algorithms, because for some problems, it is easier to provide pure DP lower bound, so if an accuracy guarantee for approximate DP is translated (using their method) to an pure DP accuracy that violates the lower bound, then we conclude that the approximate DP accuracy guanatee is impossible. They apply this method to the problem of estimating the average of points in the $d$-dimensional cube, and prove, using their method, a lower bound that is almost as the fingerprinting lower bound (but without the need to use the fingerprint machinery).", "questions": "I’d appreciate it if you could provide a high-level intuition for the proof of Lemma 6 (converting TV distance to $W_{\\infty}$) under simplified assumptions like d=1 or 2 (and maybe using more relaxations). I just want to get the feeling of how the coupling between $\\mu$ and $\\nu$ looks.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "The statements and proofs are not easy to read, and I believe it is possible to simplify them and make them more accessible. But besides that, this paper is one of the most interesting and significant papers that I have reviewed for NeurIPS, and therefore, I support acceptance. \n\nIn general, I’m not a fan of pure-DP. I think it is too stringent, and I don’t think that allowing a small $\\delta$ loss should be considered as a real privacy concern. But I do appreciate the improved pure DP upper bounds, especially since they have been achieved using a simple and generic method. Furthermore, even for someone like me, this paper offers a new method to prove approximate DP lower bounds, and I really like that.", "was_revised": true, "final_justification": "The authors answered my question. I agree with the final justification of Reviewer JJ6eI.  I will keep my positive score.", "rebuttal": "Thank you for your support and your question!\n\nTo 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]):\n$$\n    W_{\\infty}^{\\ell_q} (\\mu, \\nu) = \\inf\\{ \\alpha > 0 : \\mu(U) \\leq \\nu(U^\\alpha), \\  \\textrm{for all open subsets } \\ U \\subset \\Theta\\},\n$$\nwhere the $\\alpha$-expansion of $U$ is denoted by $U^\\alpha := \\{x \\in \\Theta : \\|x-U\\|_q \\leq \\alpha\\}$.\n\nThis 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:\n$$TV(\\mu, \\nu) = \\sup_{U \\in \\mathcal{F}} |\\mu(U) - \\nu(U)|.$$\n\nWe 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$. \nTo 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).$$\n\nRewriting the above inequality gives $\\nu(U^\\Delta \\setminus U)\\geq \\xi$.\n\nTo 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}$.\n\nThe 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.\n\n\nReferences:\n\n[GS84] Givens, Clark R., and Rae Michael Shortt. \"A class of Wasserstein metrics for probability distributions.\" Michigan Mathematical Journal 31.2 (1984): 231-240.\n\n[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."}, {"review_id": "8FZu3yHN87", "reviewer": "Reviewer_nLKU", "summary": "The paper presents a novel \"purification\" framework built on randomized post-processing techniques. This framework transforms mechanisms with $(\\epsilon, \\delta)$-approximate differential privacy into $(\\epsilon + \\epsilon', 0)$-pure differential privacy mechanisms, albeit with additional utility costs. The authors demonstrate the framework's versatility by applying it to differentially private empirical risk minimization (DP-ERM), stability-based data release mechanisms, and query processing tasks. \n\nAnother theoretical contribution of this framework is its use of purification to derive lower bounds for approximate differential privacy that explicitly depend on $\\delta$. This provides a novel proof methodology that serves as an alternative to traditional fingerprinting approaches.", "questions": "1. **Mechanism Design**: Doesn't designing approximate DP mechanisms typically present greater challenges than pure DP mechanisms? Given that smaller $\\delta$ values bring us closer to pure DP guarantees, does the purification algorithm consistently select $\\log(1/\\delta) \\approx d$ as its operating parameter?\n\n2. **Rate Discrepancies**: In Table 1, why do Theorems 4 and 7 yield different convergence rates with respect to $n\\epsilon$ ? What accounts for this theoretical difference?\n\n3. **Norms**: The domain assumptions appear to be tailored for $\\ell_p$ norms. What represents the primary obstacle in extending this framework to more general norm spaces?\n\n4. **Notation**: In the introduction, you use the notation $\\mathcal{O}_p$. Should we interpret this as $p = q$ throughout the analysis?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The paper is well written and presents an intellectually compelling approach to bridging approximate and pure differential privacy paradigms. The quest for a unified theoretical framework that can transform approximate DP solutions into pure DP guarantees represents an ambitious and potentially valuable research direction.\n\nHowever, my main concern is about the practical relevance of this work. General theoretical frameworks of this nature often suffer from being too abstract to yield meaningful practical benefits. To better evaluate the contribution, I would appreciate a comparative analysis showing how existing pure DP solutions from the literature (as referenced in Table 1) perform relative to their purified approximate DP counterparts. A clearer articulation of when purification offers advantages versus when direct pure DP methods are preferable would substantially strengthen the paper.", "was_revised": true, "final_justification": "The authors answered my qestions by underlying the theoretical contribution and the practical relevence of their work.", "rebuttal": "Thank you for reviewing our paper and for raising the questions!\n\n> Q1: Mechanism Design\n\nDesigning pure DP mechanisms is more challenging than designing approximate DP mechanisms. \n\n* 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. \n\n* 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.\n\n* 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.\n\n> Q2: Rate Discrepancies\n\nIn 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.\n\n>Q3: Norms\n\nThank you for this interesting question.\nTo 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.\n\nWe 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.\n\n> Q4: Notation\n\nThank 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\".\n\nReference:\n\n[Va00] Van der Vaart, Aad W. Asymptotic statistics. Vol. 3. Cambridge university press, 2000.\n\n\n>  Regarding your comments on weakness\n\nFor 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).\n\nRegarding 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.)"}, {"review_id": "acJ7gTk8uM", "reviewer": "Reviewer_XywD", "summary": "Differential privacy (DP) can be viewed as a bound on the difference between mechanism output distributions induced by neighboring datasets. This difference is measured in terms of the log probability ratio (privacy loss) between the two distributions. The two main variants of DP are pure-DP (the privacy loss is bounded by $\\epsilon$ a.s.), and approximate-DP (roughly speaking, the privacy loss exceeds $\\epsilon$ w.p. $\\approx\\le\\delta$).\n\nIt is considered folklore that approx-DP mechanisms $\\mathcal{M}$ with finite range can be turned into pure-DP by a simple random post-process, which w.p. $\\omega$ samples uniformly at random some output and w.p. $1-\\omega$ returns the output of $\\mathcal{M}$. Scaling $\\omega$ one can balance the degradation in privacy ($\\epsilon$) and utility. Intuitively speaking, this process trades the low probability event of a large privacy loss for the low probability event of large utility loss.\n\nThis works moves beyond finite range, and prove that if in the $1-\\omega$ case the post processing adds a small amount of Laplace noise, this result extends to any range contained in a $q$-norm ball in $\\mathbb{R}^{d}$. This is achieved by converting TV distance to a variant of Wasserstein distance, thus using the known result which converts $(\\epsilon, \\delta)$-approx-DP to \"$\\delta$-TV distance away from $\\epsilon$-pure-DP\".", "questions": "Please address my two concerns.", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n1. While approx-DP is typically treated as sufficiently private for most use cases, pure-DP is a much cleaner and natural definition, so the ability to convert nearly any approx-DP mechanism to pure-DP is an important contribution.\n2. From the theoretical perspective, this work is even more valuable, since lower bounds for pure-DP are generally tighter than those known for approx-DP. Using the proposed conversion, these lower bounds can be extended in some cases.\n3. The authors survey a large range of classical approx-DP mechanisms, and analyze how purifying them affects their utility.\n\n**Weaknesses**\n\nI have two concerns regarding this work, which - if satisfactory addressed can affect my score.\n\n*Main concern*\n\nThe authors do not consider a natural baseline, which - at first glance - seems to provide similar utility guarantees in slightly more general setting, without the need for complex proofs. It might very well be the case that this baseline has some limitations or is inferior in some other way, but without a direct comparison it is hard for me to assess the contribution of this work.\n\nThe proposed alternative is simple. Cover the range by a $\\Delta$-net, round the output of the approx-DP mechanism to the nearest grid point, then purify using the finite range method. The utility error will be the sum of the low probability event of random output and the rounding error. Using this technique, one can purify a $(\\epsilon, \\delta)$-DP mechanism into a $2 \\epsilon$-DP mechanism by bounding the number of grid points by $e^{\\epsilon} (e^{\\epsilon}-1)\\frac{\\omega}{\\delta}$. The number of $\\Delta$-net points required to cover a $q$-norm $d$ ball is $\\approx \\left(\\frac{R}{\\Delta}\\right)^{d}\\cdot\\frac{1}{\\Gamma(1+d/q)}$ (its volume divided by $\\Delta^{d}$). Combining the two we get $\\Delta \\approx R \\left(\\Gamma(1+d/q) e^{\\epsilon} (e^{\\epsilon}-1)\\frac{\\omega}{\\delta} \\right)^{1/d}$ which can be further simplified using Stirling's approximation.\n\nThis expression shares many similarities with the one proposed in this work (Algorithm 1), in particular the relation of $\\delta$ and $d$, while differing in others (which might be lower order effects). Besides it simplicity, this method does not depend on the inner radius $r$, which makes this result more general. In fact, it does not depend on the diameter either, only on the range's volume. \n\n*Minor gaps*\n\nThe list of utility comparisons for the various purifying techniques mostly lacks the results for the SOTA pure-DP mechanisms. The method proposed in this work is of significant importance, even if the approx-DP -> purify route is sub-optimal relative to the directly pure algorithm in some cases, but this comparison is crucial for a honest analysis of this method.", "was_revised": true, "final_justification": "The authors have provided detailed response to my concerns.\n\nThe existence of a relatively simple alternative algorithm with a simple analysis somewhat reduces the importance of this work, but it's contribution remains solid and important.", "rebuttal": "Thank you for reviewing our paper and for raising the questions!\n\n> Major concern\n\nThank you for raising this thoughtful question. We will add a detailed discussion of this baseline in the revision.\n\nThe 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.\n\nA 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.\n\nOne 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.\n\nIn 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.\n\nRegarding 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.\n\n\nFinally, 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.\n\nThanks again for raising this question, and we will add a section in the appendix to discuss this approach thoroughly.\n\n\n\n> Minor concern\n\nThank 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.\n\nRows 1-2 (DP-ERM): Our results match the lower bounds from Table 1 in [BST14] (up to logarithmic factors).\n\nRow 3 (DP-Frank Wolfe): our result matches a lower bound proved in Lemma 28 (up to logarithmic factors).\n\nRow 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.\n\nRow 5 (Margin-based Mode Release): It matches the lower bound in Proposition 1 of [CHS14] (up to logarithmic factors)\n\nRow 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}$. \n\nRow 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."}]

Author rebuttal:

Meta-review: This paper develops a nice and simple method for converting any approximate differentially private algorithm into a pure DP algorithm. This is a nice contribution, both in terms of algorithms and upper bounds for pure DP, but also for the possibility of simpler lower bound proofs for the approximate DP setting via pure DP lower bounds.

All the reviewers are positive and found these contributions to be valuable. Therefore I recommend accepting this paper.

However, the authors should address the issues mentioned in the reviews, especially the following two:

1. Discussing the simpler approach of Reviewer XywD for purifying DP algorithms in the paper, and comparing it to their method.

2. Adding and discussing the rates they get in their applications compared to existing DP SOTA rates.
Decision: Accept (spotlight)