Differentially Private Equivalence Testing for Continuous Distributions and Applications
Authors: Or Sheffet
Daniel Omer
Venue: NeurIPS 2024 poster (2024)
Keywords: Differential Privacy
Equivalence Tester
Continuous Distributions
Primary area: privacy
TL;DR: The first paper to give a DP equivalence tester for continuous distrbiutions

Abstract: We present the first algorithm for testing equivalence  between two continuous distributions using differential privacy (DP). Our algorithm is a private version of the algorithm of Diakonikolas et al. 
The algorithm of Diakonikolas et al uses the data itself to repeatedly discretize the real line so that --- when the two distributions are far apart in ${\cal A}_k$-norm --- one of the discretized distributions exhibits large $L_2$-norm difference; and upon repeated sampling such large gap would be detected. Designing its private analogue poses two difficulties. First, our DP algorithm can not resample new datapoints as a change to a single datapoint may lead to a very large change in the descretization of the real line. In contrast, the (sorted) index of the discretization point changes only by $1$ between neighboring instances, and so we use a novel algorithm that set the discretization points using random Bernoulli noise, resulting in only a few buckets being affected under the right coupling. Second, our algorithm, which doesn't resample data, requires we also revisit the utility analysis of the original algorithm and prove its correctness w.r.t. the original sorted data; a problem we tackle using sampling a subset of Poisson-drawn size from each discretized bin. Lastly, since any distribution can be reduced to a continuous distribution, our algorithm is successfully carried to multiple other families of distributions and thus has numerous applications.

Differentially Private Equivalence Testing for Continuous Distributions and Applications
Daniel Omer
Or Sheffet Faculty of Engineering
Math. Dept.
Bar-Ilan University
Bar-Ilan University or wweffet@biu.....mmmmm ac.
omerdan@biu.ace
Abstract
We present the first algorithm for testing equivalence between two continuous distributions using differential privacy (DP). Our algorithm is private version of the algorithm of Diakonikolas et al [16]. The algorithm of [16] uses the data itself to repeatedly discretize the real line so that - when the two distributions are far apart in As-norm one of the discretized distributions exhibits large L2-norm difference; and upon repeated sampling such large gap would be detected. Designing its private analogue poses two difficulties. First, our DP algorithm not resample new datapoints as a change to a single datapoint may lead to a very large change in the descretization of the real line. In contrast, the (sorted) index of the discretization point changes only by between neighboring instances, and so novel algorithm that set the discretization points using random Bernoulli noise, resulting in only a few buckets being affected under the right coupling. Second, algorithm, which doesn't resample data, requires also revisit the utility analysis of the original algorithm and prove its correctness w.r.t. the original sorted data; a problem tackle using sampling subset of Poisson-drawn size from each discretized bin. Lastly, since any distribution can be reduced to a continuous distribution, our algorithm is successfully carried to multiple other families of distributions and thus has numerous applications.
Introduction
Differential privacy (DP), mathematically rigorous notion that bounds the effect of any single datum on the output distribution, the current (de facto) gold-standard of privacy preserving data analysis. By we have myriad of -laalgorithms for learning and for various tasks of statistical inference. Indeed, the design of DP-hypothesis testers is crucial for the dissipation DP into other data-centric fields such economics, education and health that analyze sensitive data in massive quantities. However, by and large the design of DP-hypothesis testing is confined to distributions over finite (and thus discrete) domains rather than contiunuous distributions.
Hypothesis testing over continuous distributions poses a special challenge due to infinitesimally small perturbations two continuous distributions can have say, exponentially many intervals each with an exponentially small shift of probability mass, which clearly cannot be detected with polynomially-size sample. Luckily, this issue resolved in the works of [10, 15, 16] who restricted the TV-distance to using k- k-intervals. Formally, these works measure distance in A Ag-norm: where for any two distributions P and we have that | Ql sup Σ (P(T,) - @(T,) where I is partition of the real-line R into intervals 71, J2, Tk.
distance of a using,
But the fact remains that continuous distributions pose a special challenge for DP-algorithm designers. In fact, releasing even simple statistics like the median is impossible over infinite domains [6, 7].
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

And yet, as we show in this work, is possible to compare (samples from) two continuous distributions while preserving differential privacy and discern whether the two are identical or far-apart in A&- distance. This suggests a sharp contrast between the task of learning from a (single) continuous distribution and the task of statistical inference based on two continuous distributions.
Baseline. This sharp contrast may seem striking at first, yet on second thought, it is known that any statistical inference task that only has two possible outputs (in our case "accept / identical" vs "reject/ / far-apart") can easily be made private using the simply run ( /e)-times the non-private equívalence tester of Diakonikolas al [16] and return the most prevalent output using simple noisy count. This gives simple e-DP equivalence tester with O(K4470 66/5 + k-1/2a -))c) sample complexity with two clear drawbacks: (1) its large sample complexity bound and (2) its decision to accept or reject is explained
aaannnleeann-Agggggaaaa framework [26] -
'in the majority of the runs of the tester it decided so'. The algorithm we present in this work improves on both aspects: it has
a sample complexity of Ô (max/ k1/S 21/2 k2/3 11/3 vK
60/5: a² 1 //3/ 0//3,2/31 ae }) and it is capable of producing numerical estimators directly from the data that explain its accept/reject decision.
Our Algorithm. The difference that makes learning substantially more difficult from equivalence testing is that when having two distributions we are capable of "pitting one against the other": roughly speaking, we can partition the real line into intervals based on points from one distribution and see whether this partition acts as a random partition for the batch of examples that come from the second distribution. This involves only sorting all points from our sample on the real line and dealing with the order statistics. Our algorithm is based on privatizing the equivalence tester of [16], which operates over the continuous real line. This algorithm works in two stages: In the first stage, it looks at autocorrelation statistics that involve all (s - 1) pairs of adjacent (post-sorting) data points. In the second stage, it equipartitions the data using into m bins using random draw of m points and repeatedly runs the following operation: run a closeness L2-norm based tester on the discretized m--bins distribution that draws N new points, and should it not reject - merge every pair of adjacent bins to create a m 2-bins discretization and continue.
Our De-version of this tester also works in similar stages. The first stage is almost trivially privatized (the statistics estimated in the first stage exhibits small global sensitivity) but numerous difficulties arise in the privatization of the second stage. Most notably - the fact we use datapoints to define a partition into bins. To that end, we replace it so that we use corted-indices, implying that a bin is composed of all datapoints in sorted indices from index x; to index æ;=1 (not including). This asserts that any single bin changes by at most two datapoints between neighboring samples. Combining this with the fact that under the null-hypothesis the difference between the number of points from P and Q in each bin is proportional to the square-root of the bin size, we can bound the sensitivity in Propose-Test Tese-Teet-Rleless fashion [20] for any single bin. However, the approach of fixing sorted indices raises two concerns. The first is that we have to revisit the utility analysis of [16] because we no longer use re-sample new points to estimate the Ig-morm difference of the two discretized distributions but rather re-visit the same dataset from which the bin-defining datapoints are taken. We bypass this difficulty by sampling ourselves Poisson-drawe subsample of each bin, and by focusing our analysis on single iteration that should cause us to reject
The second concern lies in the privacy analysis, and it is the observation that change to a single bin isn't It enough to bound the sensitivity of our statistical estimator. The algorithm computes an L2 approooxiinaioon of the norm- com-difference using all bins, and in the extreme case of two neighboring datasets that differ on the very first (sorted) datapoint that ends up as the very last datapoint in the neighboring dataset we have that all bins shift. To that end we use the following novel idea: we add Ber(1/2)-randon) variable to each of the bin-defining indices. On the one hand, this possible shift by changes very little in terms of the analysis; on the other hand, allows us to argue that within log, (2/8) random shifts we can correlate these Bernoulli random variables so that the bins identify. Full details of our algorithm and its analysis appear in Section 3.
Applications. Having designed our private equivalence tester for continuous distributions under Az-norm, we can now apply it to test equivalence between two distributions from a family C of distributions which, under suitable partition, yield large enough A&. -isttanec The following fact is immediate.
2

---

Fact 1. Given univariate distribution family C and a, let k the smallest integer such that for any J1, E C it holds that II5i f2ll1 S fl At + aa22. Then there exists a (e, equivalence testing algorithm for C using Ö (max { (140 jatto, k2 /ai/// 112 Ja², k/8/ /a112219 vF/ae)) samples.
a(CC,a) be
In Section 4 detail, much like [16], variety of such hypothesis- faaiilesisffamilles and the sample complex- ities we obtain for their respective DP-equivalence testers.
1.1 Related Work
Over the past twenty years, significant progress has been made in distribution property testing. Initially, research focused on the sample sizes required to assess properties of arbitrary distributions with a specific support size. Goldreich and Ron [23] introduced uniformity testing, proposing an
algorithm using collision statistics with sample complexity of v a Batu al [5] studied closeness testing, evaluating whether two distributions are close in total variation. Paninski [27] established
the first lower bound for the sample complexity of uniformity testing at S2( ym 2 and proposed new uniformity test using unique element statistics. The works of [1, 10, 29] explored optimal bounds for identity testing, focusing on b testers. They established lower bound for closeness testing at
V with [10] providing matching upper bounds for La closeness testing under certain
conditions. [14]. introduced technique reducing distribution norms to O (1) by expanding the domain size, demonstrating an efficient Lg tester for closeness testing. Recent works [11, 15, 16) have leveraged structural assumptions for more efficient testers in various settings, including continuous cases. These studies used the A& metric, aligning with the Kolmogorov distance for k = 2 and total variation distance for k being the domain size. Goldreich [22] showed that identity tests could be reduced to uniformity testing. While earlier testers relied on proxy measures like L2 and x². and [12, 13] demonstrated efficient sample complexity using direct Li metric testers due low sensitivity. We refer the interested reader to Cannone's 's excellent survey [9].
Several recent papers have examined hypothesis testing problems under the framework of differ- ential privacy. Cai et al [8] used x2 statistic for identity testing, achieving a sample complexity
/n /n 1/3 a0//E" 05333373 log(1/3))- Aliakbarpour al [4] proposed three algorithms for differentially private uniformity and closeness testing. They privatized unique element algo- rithms, collision-bar based testers. and x² tests, each with specific sample complexities and limitations. Acharya et al [2] established a lower bound for private identity testing, suggesting that small expected Hamming distances might compromise privacy guarantees. They proposed a sample complexity con- cerning privacy and distance parameters by privatizing an T, statistic- based algorithm. Aliakbarpour et [3] also examined closeness testing between distributions with unequal sample sizes, introducing new technique to privatize the 'flattening' method through data permutation. Zhang [30] derived an upper bound for closeness testing by privatizing an empirical total variation method, demonstrating
of Ô maxx a
small sensitivity and sample complexity of O
2/3
/ 1/3
avE
aE
Comparison to Existing Lower Bounds. The well- lower bound for Ar, closeness testing in the non-private regime is given in [16). It is equal O
4/4/0 vT
As far we know, there is no known lower bound for the private regime in that task. In [2], lower bound for the private regime in identity testing is presented as size), which is simpler task than closeness testing. Additionally, [30] provided an upper bound equal to the lower bound of the closeness testing also in the private regime when he crucially relies on the T tester that is known with low sensitivity. We have established upper bound that is asymptotically 1/3 close to the lower bound, given by Ô (max ( /4/7///1 /2/3 /ae// k2/2/2 /a², k-/3/ //11/,255 vkfae)) The /a/%/ae"
+
6575
a
2/2/3 2 avE + 0./5.77
2/a/a
+ ore (where n = k is the domain
k2/S difference between upper bound and the lower bound lies in specific terms: vk and ag The first term is a result of the high sensitivity in our algorithm due to the use of Ly norm testing, which was selected to ensure the utility proof. Additionally, we did not focus on optimizing the term log ( &
3

---

2 Preliminaries
Equivalence (Closeness) Testing. We assume oracle access to two distributions P, Q which gives an i.i.d. example from the resp. distribution. We also use P(S) (resp. Q(S)) denote the total probability mass assigned by P (resp. Q) to a set S. We assume the two distributions are continuous with discrete point mass, which can always be obtained by concatenating each sample with uniformly drawn number En [0. I]. An equivalence tester between the two distributions should return NULL w.p. 2 2/3 if it holds that P Q and return ALT w.p. 2 2/3 if it holds that ||P 2ll 2 a.
Differential Privacy. Two databases D and D' are considered neighboring databases they differ by exactly one record, noted d(D, D') 1, where d(-,)) represents the Hamming distance. Given a domain X, two multi-sets S, C X' are called neighbors if they differ on a single entry. An algorithm (alternatively, mechanism) M is said be (e, didifferrentllll private (DP) [21, 19] if for any two neighboring S, S" and any set O of possible outputs we have: Pr(M(S) E O] S e Pr(M(S)) 0] + ö. If 8 O then we say the algorithm M is e-DP.
The Global Sensitivity of function f X + Rdd is defined as the maximal difference maxs,s [[ f()) is known that adding Lap(GS(f)/c) to each coordinate of f(S) is c-DP; where Lap(A) denotes the Laplace Distribution with parameter X, whose PDF is PDF(2) x e =l/> It is known [19] that if A and A₂ are (e1 61 >DDP and (+2, 52) resp., then their composition is (2,+ + 62) It also known [18] that the k-fold composition of & algorithms, each is (c, d)) is 8') (c",kō+
JDD for any 8' > O and CM ke(E" - 1) + 2c k log(1 [1 /8"). Lastly, it is also known that if there exists an event & such that under & holding, algorithm M satisfies that for any two neigh- boring S and 5" and any set of outputs O we have that Pr(M E Ol 8| < e &rr[M(S") E 0 + then algorithm M is (e, + PrD-E
kō
Poisson Distribution. The Poisson distribution Poi(A) a discrete distribution over the Naturals which satisfies Pr[kk] = = >* /kl. It has multiple properties that make easy to work with.
Proposition 2.
TTe sum of two ind. Poisson Poi(X1) and Poi()2) is Poi(>1 + A2).
Let X1, X2,... be i.i.d. Bernoulli rvss. with parameter p: then drawing t Poo((), it holds that Ei= X; is distributed like Poi(Xp).
If X Poi(>²) and Y ~ Poi()y) are two ind. Poisson E.v., then the distribution of X conditioned on the event that X + Y n. is Binomial Bin(n, xa
>x..).
If X; Poi(A) then Pr[lX A > k] S exp
122 for any 33 0, setting
2(*+8)
k= = 2 log((//)) we get Pr[JX - X| > 2 A llg(2/0))
< 3B provided X > 4 log(2//)
Misc. We use Ô (resp. Q)) to denote big-O (resp. big-S?) up to poly-log factors. We made no effort to minimize constants or the degree of the poly-log.
3 Private Equivalence Testing for Continuous Distributions
In this section, we present our DP-tester for equivalence between two distributions with large As distance and give both its formal privacy guarantee and its sample complexity bounds. The tester is detailed in Algorithm (which in turn invokes Algorithm 2), where Caken denotes a large enough constant detailed in [16].
The algorithm consists of two parts. In terms of the non-private algorithm, both parts function similarly the algorithm presented by [16]. Our main contribution is the privatization of this algorithm. In the first part the main objective is to compute the estimator Z (line I.5) which is privatized using a straightforward approach since it has low sensitivity we merely add is some Laplace noise. The second part is more complex, as it involves discretizing the domain based on the data itself, resulting in high sensitivity. We addressed this issue by creating the initial partition of the domain and adding Bernoulli random variable to each index position (line II.5). Consequently, the algorithm can iteratively run ja iterations of the Tagtesserr TestCloseness on based on the randomized partition, where in each invocation of TestCloseness sample a Poisson-size batch

---

from each partition (line II.11). If the L2-tester doesn't reject, then merge adjacent partition cells (line II.15) and move on to the next iteration. either invocations TestCloseness (or the estimator has high of value) then we reject; but if all test pass return NULL.
Algorithm Private Equivalence Tester
Input: 2 continuous distributions P. Q. distance parameter a, privacy parameter e, 8. Output: "NULL" if Q; "ALT" if IP Al 2 a
1: Part I:
(b#/a8 k$ k
Set 100cakn
2.
Draw Poi(m) points from (PP Q).
Label each æ; drawn from P with (xx:) = 1 and label each æy drawn from a ((x,) -1. Sort the sample, denote the outcome as =(()) < (22) I(s).
= Σi=l (()6)))((
6. Draw X Lap(6/e).
7. Z - Z + X
Z
m²aa 21
then return ALT
2: Part II:
1. Set N < 107
k//3 04/32273
+ vk
+
VI a²
log (M/acs) and assert divides N.
2. Draw sp Poi (+) and S, Poi ( ind. Set s + Sp + Sq.
3. S <- sample of 8p i.i.d. examples from P and 8, i.i.d. examples from Q.
4. Sort S. Denote the outcome I(1) x22))
T(a)-
5. For each 1 S i
set H. + i N + B, for ind. drawn B, Ber(1/2). Also set no + O, Tm+11 f- s + 1.
6. Form the Partition 17 (TH)) nV no where II; = {x())) m < 1' < T for every
1 1sis m.
Set ju 1 + [og (m/ 1:) and m +- m.
for j = 0, Jo
do:
9.
for = 1, 2,,,.... m² do:
10.
Draw NY ~ Poi( Imf ).
11.
Pick u.a.r. subset C. of N points from II.. (If (IN [Ie] then special points.)
12.
Set X (resp. Y?") #points from P (resp. Q) in Cy
13.
if TestCloseness
Σ NY.m. m², (X(), (X,"), Hog 8 log(3/s) 27
ALT then
14.
return ALT
15.
Merge cells: Set m1+1 &- mm//2J, and for each S i S mi+1 set:
11 12 U (I(TT)) UIL
D i'=the separating index of the two bins
3: return NULL
3.1 Privacy Proof
In this subsection, our goal is to proof the following theorem.
Theorem 3. Algorithm is (2e, 2DP
The proof of Theorem shows that Part of Algorithm is e-DP which is very straight forward, whereas Part II of the algorithm is (e, DDP which involves more intricate arguments. In fact, all that is required regarding the DP of Part I the following claim. Its proof, as well as most proofs in this section, is deferred to Appendix A. Claim 4. The estimator = Ei= (((())))))))) in Part of Algorithm (Line 5) has global senstivity 6 6.
5

---

Algorithm 2 TestCloseness (N, m, X, Y, ,,,'','''
1: Set Ramax - m || }:
2: Set Pemax -- maxx Lap($/e)
3: Set Z f + (Xi - Yi)² - X; Y,, E; Xx; - Y.I² - (X,+ +.).
4: Set t /
6.N log (800N) + 16 16 +1
5: Set Z t Z Lap( (1844/22///0m/////
6: if (Amax <
6N
log (800N) + $lm(1/0") and 2 < N2 then return NULL
m
7: else return ALT
We thus focus for now on Part of Algorithm In Part II our output the (2jo)-long tuple (Aimaxo 201 which we may return from the jo invocations of TestCloseness. Thus, we denote
8v (3/() 8' 5 and note that each invocation of TestCloseness is with these parameters. Throughout our analysis of Part we assume that the Poisson random variables are known to us, but leave the Bernoulli and the Laplace random variables unknown.
2jo
Each invocation of TestCloseness releases statistics: approximation of Tmmax and approxi- mation of Z. The next two claims bounds their sensitivity (w.h.p.).
Claim 5. The Global Sensitivity of D'max is at most 4.
Lemma 6. There exists event & where Pr[-E] < 36/2, and under & it holds that the sensitivity of 7. at any iteration j is at most 1og4/3(2/0)
6.N m
log (800) + 161n(1/8") 1).
Proof. Denote &o as the event that there exists an invocation of TestCloseness with m balls and log (800m) + 8lm(1/8") It follows that there must exists an invocation of TestCloseness in which the noise added to 7mmax (drawn from Lap(8/e')) must be smaller than 8lm(1/6') This holds w.p. 8' 8'/2, and from the Union Bound it follows that Pr(Eo]
bins in which mmax 2
V 6i n
log (800m) 161m(1/8") yet Amax V n
1u =
We now turn to the Bernoulli random variables. Fix S and 5' to be two neighboring inputs, and again, assume that the changed point appears in place (1) in S and in place (s) in S (Otherwise, analysis is only simpler.) follows that the changed point falls in II and in II, in S'.
We now specify the coupling of the Bernoulli random variables between S and S' which is the following. We draw B1, By- B2, By and so on, u.a.r. and independently, and apply B,-s to invocation on S and B'-s to the invocation on S", until the first occurrence of B = 0. B = from which we give B441, B,-2 and so on to both invocation. This depicted in Figure 1.
Denote Ej as the event that the first occurrence of B, = 0, B 1 is at the j-th draw. Clearly (o54))(2/5)
Pr[E;] (3/1)5-1 1/4. Thus, from the disjointness of events, it follows that Pr [ Jo (2/6) (3/4)--1 Σ j==
E
(3/4)
12/8)
- -/22. Symmetrically, we apply the same coupling
3/4
S:
(1 (2) (3
(m))
S¹:
(17
(2)
20 fm
Figure 1:
Two neighboring inputs that differ on one datapoint, appearing first in S and last in S¹.
In this example, the index defining the first bin, Ti is such that for we go B 0 and for S' have B = 0: but the index defining the 2nd bin, л2 it does hold that B2 = 0, B 1 so the indices starting from bin onwards align.

---

align the last bins, those affected by ((s)) in the last position. We the coupling that provides Bms By Bm-1; B'm Bm- B'm 2 and
until the first occurrence of (1, 0) then it switches to the same variable Bj. Denoting E as the event that the first occurrence of B, 1, B = 0 is at the
loga; (2/6)
m j-th draw, we have that Pr [U=-
Eg] = - 6/2.
(2/6) We thus denote = Eo U (E)) and have that Pr[-E]= =36/]=33-2000 36/2. Note, under follows
j=1
that at most 2 logg//2 (2/6) bins have a change in their X; Yil-value, which due to Claim 5 - is at most 4. (Observe that in the case where S and S' are such that there are fewer than 2 2 (2/6) bins between the locations of the changed point then this statement holds w.p. 1.)
It follows that under & we have that the value of Z is affected by most 2 2loa//32//) (2/6) bins, where for each bin Xx Yi| changes by at most 4. It follows that Z can change by most (V GN log (800N) + 16 + 1).
2 logg// (2/6) 4 mm + 1) s 8 12///3(2/0)
m
Completing the Proof of Theorem 3 is simple, and is deferred to Appendix A.
3.2 Utility Proof
In this subsection, our goal is to proof the following theorems. Theorem 7. W.p. 2 2/3, Algorithum returns NULL when P = Q. Theorem 8. W.p. 2/3, Algorithm I returns ALT when || QllA,
The proof of Theorem In fact, in order to argue the correctness of theorems we need to argue that both Parts I & II of the algorithm are correct w.p. 2 5/6. Proving that Part I is correct is very straight- due to claims from [16). And so we focus on the correctness of Part II. Its correctness requires that we first assert few rudimentary propositions and claims.
fairly simple, but the proof of Theorem 8 requires some preliminaries.
3.2.1 Rudimentary Claims
Similarly to the analysis in [16] our goal is to compare the two continuous distributions to their resp. discretizations that were forms under the various IP. However, we do not have the luxury of resampling the points from P and Q and so our argument diverges from theirs as we fix one particular j and then argue from first principles that under large A₁ -ifffferee the specific partition Ip" cause to reject. (Arguing that when = we return null is also fairly straight-forward.) Our intermediate goal is to argue that the points from P (the X-s) and the points from Q (the Y-s) are distributed like independent Poisson random variables. Thus, for the remainder of the diseussion we fix some particular iteration and examine solely it, without considering the previous iterations.
Due to space constraint, defer nearly all the claims in this section Appendix B, but they all lead to towards the following main lemma.
Lemma 9. Fix index j. For each index denote by 1 as the interval (T()))) ) which the interval defining bin in the partition 113, Then the estimator Z computed by TestCloseness satisfies that B [ = Em (p= g:)² where
NP(L))
NQ(L) 4. 4m(((()) QU.)
Pi (P(I) + 2(4))
and that Vari = Emi 4(p; + (p: 4x + 2(p, + 2
In Lemma 9 established the expectation and variance of our estimator using the notation p: which in turn is defined as (m(((())+((]) (and qi similarly). The following claim going to assist us in bounding the denominators of p; and qu.
NP(1)
Claim 10. If N > 3000m 12m() then with probability of 1 1, any I that forms bin 11. in 2(1+
II, has that 1.01m
1.01
7

---

Unfortunately, due space constraints, defer proof of Claim 10 well the entire proof of Theorem 7 to Appendix B.
3.2.2 Proof of Theorem 8
We now turn our attention to proving Theorem 8, however, need one more technical lemma, whose proof - like all proofs this section - deferred to Appendix B. Then we can proof Theorem 8. Lemma 11. Fix E 1). Suppose there exists n non-negative random variables X1, X2,x..... , such that for each i it holds that for some fixed number have Pr|X;- 2 a,) 2 p. Then, given constant C > 0 there exists another constant C > such that with a probability at least it holds that Σ 1 i= X1 2 ci
Proof of Theorem 8. In the alternative case, where |P Qlla, 2 a, we know that there exists k intervals I E I such that Eiez IP(1) 2(1) 2 a. We denote for each interval r(1)
[P(I) - 2()) For the sake of analyze we use two different kinds of interval, small and large.
Definition 12. Interval I E I is called small if there exists subinterval J C such that P(J)
2(J) < 1/ 1/m and [P(J) Q(J)) 2 (TT)/0, and large otherwise.
Note that a < 1 = half of the discrepancy comes from either small or large intervals. We consider first the case where half of the discrepancy comes from small intervals. In this case, Lemma 9 in [14] states that the expectation of statistic Z in Line of Part is bounded by [E[]] 2 c a² for some constant c > Just like we did in the soundness case, Proposition 21 gives that the variance Var 2| S 9m. Therefore
small (T) + EIEZ, large (T), so
for some large constant Cakn. setting m = 100cakn
kT
then by Chebyshev's inequality
a
ac
we get that with probability - holds that Ž 2 E[Z] random noise sampled in Line 6 of Part I of the algorithm).
10ym m
X
maa (with X being the 2
Now consider the case where ΣrEZ, lurge IP(T) 2(T) > g. We prove that Part II of Algorithm 1 must return ALT on at least one invocation of TestCloseness. show that the discretization of the domain with m samples preserves most of the A--dittncce Take any interval E I that gives the Ag, distance, and denote
order to do this, we first need to
aa, as its boundaries.
Now, consider the total probability mass between a and ;, then the first datapoint selected for the partition that is greater than a. Since the total number of points is taken from Poisson distribution, it is known that the mass from one point to the next has Exponential distribution Exp(N) [28]; and so the total mass from Gamma- caama-distribution with mean < N N m and variance - N (+)² mN 3000m log(mn) It
distributed like the sum of Exponential random variables, namely,
follows that w.p. & 0.01 we have that (Pla, n. + n.l) > 1.01 A similar analysis shows that for TJ, the last datapoint selected for the partition before b, we also have P([TT, b)) + Q(TTT, bl) < 2.02 Note that a large interval must have a total probability mass P()) + Q(1) 2 10 and so w.p. 2 0.98 we have formed the subinterval I' = [T, my5 C I. Moreover, by the subinterval property of large intervals, we have that because P([a, x.]) + Q((a, + P([ 6)) + Q( b]) 101 then
((') 7())
5x(1) 22)/22. 10
Therefore, denote N, as the indicator of the event that (P(1)- >
? and we denote pi1" and Qur as the reduced discretized distribution formed by the partition point. We show it preserves most of the total variation | - = || = Σr IP(I') - Q(I') 2 ΣiEz .2 N2, 2 ΣIET, I large N2 a( We have established that if is large interval then Pr[Nr] 2 0.98, and so, for the random variables, NG x(I) )-s (one for each large interval) where for each variable with probability 0.98 it holds 2
((1)
that N1 20)) x(1) we apply Lemma 11 with c 0.36 and have that there for the constant
if a = -oo or b- = oo our analysis is even simpler, as we take To and t as the respective partition point.
8

---

C
0.98( 0.98(1-0.900 (-008)
0.95 such that with probability C
0.95
-1..3(-
Σ
7(
2(1)
a
2
0.36
2
2
12
ZEI, 7 large
IEZ, large
Therefore, with probability > 0.95, l Q
11
Observe that the TV-distance follows from finding suitable subintervals inside large intervals with large discrepancy. Thus, each of the k large intervals now gives (at most) points that form I', so these I 2k points partition the real line to $ 2k + intervals where the various I'-s are part this
partition. It follows that || 11 2 T2
Now, to complete the proof, need to show that Part I of the algorithm detects the discrepancy. We deploy the following lemma from [16] where for a vector u the notation ||u||a,1 refers to the sum of the largest & bins/coordinates of v.
Lemma 13. For any two distributions P and Q on [m] such that ||P 1P-Qlea Qll > a, there iteration j E (m/)) such that I|pu' Q"" || > a/ log(m/k).
So since li
QTh
12 know that by Lemma 13, there exists some j [log(m/ []]] (// and therefore by Cauchy-Schwarz inequality
such that pu QUF
1,24+1
pTT
QTI
We know that | - QQ"
De-
11/22+1lgg(m/2)
1,2441
12log("/A)
note the of indices of these 2k + intervals as S, we get from Lemma 9 that
E|Z] = Σ Pp:
m
4:)²
(ov (pv--1 9x)2 PES
San.ch. 2
(Eves (u)-
2k+1
2
2k+1
1
Σ
4m (mvl)(()--(1))
NPPU))
iEES
Also from Lemma we can infer that
IZ - B|2]| - 1 |E12
16
1==1 64(p, + 9:)(p; 9.)² + 32(p: + 9
Pr
E|Z|2
EE (pi 232
Ees 64( ((P(1)+(1))
Am (P(1)+Q(1) (p: 91)2 + 32(
N(P(I)
2N /m3
16N 16N/mi mm
Ami (P(D+QU))
+ >m (pr - 9,)2
1 (p: - 41)3)2
i= (p: - -g))22
m 6 5-5882 (2k + 1) log (m/k) (m/k)
28224 log(m/k)
< 0.01
N2 when N 106 Vl log" (m/k) Now we assert that the noise added is also proportional to at most with ((Z) as defined in Line
2
a²
E] and indeed if we draw random variable R Lap
A(Z)
of TestCloseness, then we get Pr R
2500 [og(m/k)
2²02
exp
2r 2500 I)A())
S 0.01.
which holds if
>> 10 V (
105
N
16 ln log (10N),
k: 16 logg/a(//)) max
ave
ave'
2h
e'
get N = à gi/3
vI
Combining it all together, have that w.p. 5/6 Part II of
04/52773
the algorithm also returns ALT.
4 Applications
Our algorithm is designed continuous distributions, but it can also be used discrete distributions. The process is simple: for given discrete distribution P. for each example x; P we draw number ig En [0, 1). and then sort all the examples ((ry, k))) using lexicographic order. This process gives a simple privatization of the "Flattening method" proposed by Diakonikolas al [14],

---

it does without looking the example drawn. Our algorithm method is quite simple: draw m samples from 1 2 (P + 2), then calculate the autocorrelation to identify discrepancies within small intervals. Next, use min(m, n) for flatting test for total variation distance. It's important to remember that if 7 = k, where n is the size of the domain, then A& distance is equal to L1 However, the sample complexity of the first part, which involves finding discrepancies in small intervals using 4/5 the analysis of [16], requires 2/755 Fact indicates however that the size of the domain is not always the most suitable parameter for distribution testing. Having knowledge about the structure of the distribution enables more efficient testing, as we illustrate below. In Table 1, we give brief summary of the various statistical inference tasks that can be conducted using our algorithm.
Table Private equivalence testers derived from our algorithm for continuous distributions
Distrib. Family
Num of Intervals
Private upper bound
t
Ö max
Ltt 04/5,273
0976
a
piecewise
constant
Eld + 1)
Ô
max
(Md+1)
(641)
(14+1)
4473,275
piecewise degree-d
log- concave
Va
max 975 477
63273
a5742
k--
&
max
w8/T
6975
04/3,173
k273
6975
g4/2
03,2731
vk
mixture of log-
concave
(-model
log(n)
max
(t (og(()))
02
(og((n)
874,4/3
( (og(n)))
a5/2
(elg(n))
a5/3,275
y Fog((n) 3/44
over [n]]
MHRR over [1]]
log(n/o)
max
(log()/o)) 4/5
a²
log(n/o) 2/3
673.777
flog(w/o))
a572
(log(//o)) 1/3
a973,27
(lo((r/o)
3732.
Acknowledgments and Disclosure of Funding
O.S. is supported by the BIU Center for Research in Applied Cryptography and Cyber Security in conjunction with the Israel National Cyber Bureau in the Prime Minister's s Office, and by ISF grant no. 2559/20. Both authors thank the anonymous reviewers for their suggestions and advice on improving this paper.
10

---

References
[1] Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath. Optimal testing for properties of distributions. Advances Neural Information Processing Systems, 28, 2015.
[2] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private testing of identity and closeness of discrete distributions. Advances in Neural Information Processing Systems, 31, 2018.
[3] Maryam Aliakbarpour, Ilias Diakonikolas, Daniel Kane, and Ronitt Rubinfeld. Private testing of distributions via sample permutations. Advances in Neural Information Processing Systems, 32, 2019.
[4] Maryam Aliakbarpour, Ilias Diakonikolas, and Ronitt Rubinfeld. Differentially private identity and closeness testing of discrete distributions. CoRR, abs/1707.05493 2017.
[5] Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D Smith, and Patrick White. Testing that distributions are close. In Proceedings 41 Annual Symposium on Foundations of Computer Science, pages 259-269. IEEE, 2000.
[6] Amos Beimel, Kobbi Nissim, and Uri Stemmer. Characterizing the sample complexity of private learners. In ITCS, pages 97-110. ACM, 2013.
[7] Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. Differentially private release and learning of threshold functions. FOCS, pages 634-649, IEEE Computer Society, 2015.
[8] Bryan Cai, Constantinos Daskalakis, and Gautam Kamath. Priv'it: Private and sample efficient identity testing. In International Conference on Machine Learning, pages 635-644. PMLR, 2017.
[9] Clément L. Canonne al. Topics and techniques in distribution testing: A biased but rep- resentative sample. Foundations and Trends@ in Communications and Information Theory, 1966):0032-1198, 2022.
[10] Siu-On Chan, Ilias Diakonikolas, Paul Valiant, and Gregory Valiant. Optimal algorithms for testing closeness of discrete distributions. In Proceedings of the twenty-fitth annual ACM-SIAM symposium on Discrete algorithms,, pages 1193-1203. SIAM, 2014.
[11] Constantinos Daskalakis, Ilias Diakonikolas, Rocco Servedio, Gregory Valiant, and Paul Valiant. Testing k-modal distributions: Optimal algorithms via reductions. In Proceedings of the twenty-fourhh annual ACM-SIAM symposium on Discrete algorithms, pages 1833-1852. SIAM, 2013.
[12] Ilias Diakonikolas, Themis Gouleakis, Daniel M Kane, John Peebles, and Eric Price. Optimal testing of discrete distributions with high probability. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 542-555, 2021.
[13] Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price. Sample-optimal identity testing with high probability. Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx. and Donald Sannella, editors, 45th International Colloquium Automata, Languages, and Programming, ICALP 2018, July 13, 2018, Prague, Czech Republic, volume 107 of LIPles, pages 41:1-41:14, Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2018.
[14] Ilias Diakonikolas and Daniel M Kane. A new approach for testing properties of discrete distributions. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 685-694 IEEE, 2016.
[15] Ilias Diakonikolas, Daniel M Kane, and Vladimir Nikishkin. Testing identity of structured distributions. Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 1841-1854, SIAM, 2014.

---

[16] Ilias Diakonikolas, Daniel M Kane, and Vladimir Nikishkin. Optimal algorithms and lower bounds for testing closeness of structured distributions. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1183-1202. IEEE, 2015.
[17] Ilias Diakonikolas, Daniel M. Kane, and Vladimir Nikishkin. Near-optimal closeness testing of discrete histogram distributions. In ICALP, volume 80 of L/Plcs, pages 8: 8.1-8:15, 2017.
[18] C. Dwork, G. Rothblum, and S. Vadhan. Boosting and differential privacy. In FOCS, 2010.
[19] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, llya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, 2006.
[20] Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In STOC, pages 371-380. ACM, 2009.
[21] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265-284. Springer, 2006.
[22] Oded Goldreich. The uniform distribution is complete with respect to testing identity to fixed distribution. Electron. Colloquium Comput. Complex., volume 23, page 15, 2016.
[23] Oded Goldreich and Dana Ron. On testing expansion in founded-degres graphs. Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation: In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman, pages 08875,25 2011.
[24] Svante Janson. Tail bounds for sums of geometric and exponential variables. Statistics & Probability Letters, 135:1-6, 2018.
[25] S. Mane. Moments of the poisson distribution of order k, 2023.
[26] Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. Smooth sensitivity and sampling in private data analysis. In STOC, pages 75-84. ACM, 2007.
[27] Liam Paninski. coincidence-based test for uniformity given very sparsely sampled discrete data. IEEE Transactions Information Theory, 54110):455-4475,, 2008.
[28] H. Pishro-Nik. Introduction to Probability, Statistics, and Random Processes. Kappa Research, LLC,, 2014.
[29] Gregory Valiant and Paul Valiant. An automatic inequality prover and instance optimal identity testing. SIAM Journal Computing, 46(1):429-45 455, 2017.
[30] Huanyu Zhang, Statistical inference in the differential privacy model. CoRR, abs/2108. 108.0000 2021.
12

---

A Missing Proofs - Privacy
Claim 14 (Claim 4 restated). The estimator Z = Ei= ((()) in Part I of Algorithm I (Line 5) has global senstivity of
Proof. Consider omitting single datapoint, ((()- It is easy to check cases and see that when ((((--))) = (() ((((()) then before omitting 2()) the three entries contributed -2 to Z andafter the omittance they contribute to Z. Thus the change is 3. Considering 5 and 5' that are
different single entry, we have that this change to triplet of consecutive datapoints occurs twice, hence the global senstivity of Z is 2 3 6.
Claim 15 (Claim 5 restated). The Global Sensitivity of Tmax is at most 4.
Proof. Fix S and S" to be two neighboring inputs that differ single point, and assume that the changed point appears in first place in and the last (s-th) place in S Now, it is simple to see that each bin changes by most two points (its first and last), shown in Figure 1. However, since may not know the beginning-pon points and end-points added to each, then in the extreme case the bin from S has addition a point. This sums to points that may belong to one bin and not the other, shifting the value of X, Y; by at most 4.
cach bin due to the Bernoulli random noise point and from S' missed
Proof of Theorem 3. First, we discuss Part I. In this part we only release the noisy estimator (E= (((()))( + X. Due Claim 4 we know that adding Lap(%/e) to this estimator is DD... We now move to Part II of the algorithm.
In this part release jo-times pair of outputs: (i) noisy estimator of Rmax and (ii) a noisy estimator of Z. Assume the event from Lemma holds. Adding Lap($/e))- noise to Runax which has global sensitivity of 4 (Claim 5) is </2-DD. Adding noise of
Lap (161og//a(2/0) (v 6m log (800m) 161m(1/8)) + +1)/d) is <'/2-DP. It follows that under &, so it follows from Advanced each pair of outputs preserves e' eDDD. Note that we set e' 8/10 log(2/6)
n
Composition, that overall we preserve (e,6/2)-DP under E.
Summing both Parts together, Algorithm 1 preserves (2e, 4/2)-DP under an event that holds w.p. 1 36/2; so overall Algorithm 1 is 25)
B Missing Proofs - Utility
B.1 Proof of Utility Rudimentary Claims
Recall that in Part II we partition the domain into bins by using list of sorted samples, and see if the examples in those bins pass our L2 test - TestCloseness. Moreover should TestCloseness return NULL we unify bins, using the same sets of points. Throughout the analysis we assume that we know the endpoint of each bin, namely that the result of the Bernoulli r.v.s have been disclosed. Now that each bin II has 4 points we argue that the distribution of the number of points following binomial distribution from P (resp. Q).
Claim 16. Fix index j. Fix index i. Denote I as the interval (#( which is some interval defining a bin in the partition IT, which contains i points overall. Then the number of points in an interval II coming from P follow Bin (t4, ((1)+(T) Moreover, for any two disjoint bins IP; and I1, it holds that the number of points from P (resp. Q) in each bin is independent of the other.
P(I)
Proof. We draw s from a Poisson distribution with parameter N, representing the number of samples we take from 1 {PP + Q). As result, we can determine that within any fixed interval, including the interval J, the number of points we denote as X, follows a Poisson distribution with parameter (P)).. However, know that the number of points within interval / is exactly t,
13

---

So now, conduct thought experiment, where re-sample S until precisely points from S fall in J. Replacing our original & points in IT with the new points is indistinguishable as they are distributed precisely the same. Denote X; (resp. Yi) as the number of points from P (resp. Q) in our repeated thought experiment that fall I, and define X, (resp. Y1) as the number of points from (resp. Q) that fall within interval I in the draw where precisely t, points fall in from both distributions together. Therefore
X, ~ Xr (X,+ 81 - -4)
We recall that by the definition of our sampling from Poisson distribution, we get that X, Poi (TT).. V, ~ Poi ( N Q(T)). hence by Proposition 2 it follows that X, Bin(ts, P(T)+ Note also that X, and Xy are independent for every / and I'. This is due to the fact that the number of points in any given interval, taken from the set P. follows a Poisson distribution. As a result, the number of points in any two disjoint intervals I and I' are independent.
P())
We now prove that our new selection of points in each bin follows a Poisson distribution.
Claim 17. For each interval 1 defining a bin II, as in Clain 16, it holds that x! Poi
NP(T) and Y? ~ Poi Im(P()+QII) (P(())))(
No(
Proof. Using the same notation as in Claim 16 - we know that for each interval I defining a bin II, the following holds: X, is distributed according to binomial distribution with parameters t, and P(T) Now, let us take a subset of points C of size N from I, where N/ is Poisson random
p())+()))
variable with parameter
N Ama and denote X² as the sum Bernoulli i.idd. random variables by, P())
such that each is distributed according Bernoulli distribution Ber( P(T)+((T)) In other words, X? = Em' by. Based on Proposition the preliminaries, holds that X is distributed like P())
Poisson r.v. with parameter X P(++ The proof for Y? is symmetrical. To prove independence
of X E Ber(y) and Y? = Σi x=1 Ber(1 p), and we have
Pr[X, = a Y = b] = Pr[X, = a X; + Y, = a b]
Pr[[X, = a X, +Y, = a b] Pr[X, +
a b
- NM
a+b
(a+b) p" (1 - -p)²
dm
(a + b)!
N )o
x (1-p)
pp)
N (Maaa a+b
a!b!" a!TI!'1 D0 (1 -p)b
e
4m
(a b)!
x )r 4m p) -
N
(N (1 - p)) e
N (1-p)
Pr[X; a] Pr[Y, C
Moreover, need to ensure that each selection of subset of points does not require more points than we already have, which is no more than N. for each bin, meaning no bin holds any 1 points.
Claim 18. If > 32/3 m (n())), then with probability of the chosen subset C₁ is no greater than N 1.
1 holds that for each bin i, the size 2m.
Proof. The proof follows from standard tail bounds of the Poisson distribution. Given random variable X Poi(A), we have
(3x)²
31 (-4)
Pr[X > A+ S exp
exx
3-
+1A
14

---

Therefore, if we want each of the m² + m² + m² doesn't exceed exceed mJ we get
+ md < 2m bins have a subset size that
Pr Vi,Vi, 10
N
2 Σ
Pr[Ay
<
4
N
2
Σ m² exp
3N 16m
mi
4m
2 1 2m exp
3N
1 2mm 21n(2m)
1 2m
16m
Lemma 19 (Lemma restated). Fix index j. For each index denote by I3 as the interval (Z)) (xl4))) which is the interval defining bin in the partition IP. Then the estimator Z
computed by TestCloseness satisfies that E|Z] Ex (ps 9²)² where
NP(4)
p: Am((P(1: 2(1.))
Qi
+
and that Variz] = Em'h mm 4(p; + q:: q;)²² 2(p; + 9:)².
Proof. For brevity, denote X X, and the same for Y, We want to calculate the expectation of the statistic Z E, (X; Y X; Y, Therefore
m²
ml
Z = E
(X, Y.)² - X, - Y,
Σ
E[X? - 2X,Y, X, -Y
1=1
1=1
mi
Σ
+ vr
2p:'i + qi + 03 Di qi = > (pi - qi)²
We now want to calculate the variance of Z En' Ei=i (X, Yi)2 Xx;- Y,. Therefore
n² Exx, -
n²
Var [] = Var
2 2,)=- X; - Y = Σ
Var [X, - Yi)² - x; Y.] Y.]
1=1
Let's denote 7, = (X; Y.)2 - X; - Yú and calculate E. [Z?]]
| = E [((x Y.)2 X; - Y.) -X)+ - Y.)(, - YY) (X, + Y
We analyze the expectations of each term separately, based on known first to fourth moments of the Poisson distribution [25] and the independence of X; and Y,, we know that
E [X, - y1 = - E
4xxxx - 4X,Y+ + Y;*1
+ -x + q)) + 6(p, + pp))g + q;)
Aq:(p?++33) +,) + +9g
7 +
+p) - q:) + 6ptg: + 6.:q + 4pp79
-4q +
(p: -1=a)=+(pp.-))++6600 p. 9: p:d + 93) p: + q: + 12p:9:
It is to see that [E[(X; + = = 2p.g: (p: + 9:)² + p: q. so now
2p:g:
E ([(x++)) - = - +YX?
-2,,, + Y
+p - + oe + 3g +
=p - - - + 4 + 4p.4
15

---

Combining all three terms, get
E [ = (p. - 9:)²* + (p: 6(p - p.q:
p. + + + + q + 12p:9:
2(p - q.pp p: + 9. + 3(p: -)) + p: q. 4p.)) + (p: + q.) + p: 9:
(px -1)= 4 p.% pal 9 (p: 10-00 a²)² 2 (p. xz)² 2 4prqi
(p--
13.-9)) (.:))* + + qpp q: 2 2(p + +
And so we get that
Var[Z:] || - E = (p:-000000 q1)² + 4(p; + (:)(1: =2))² + 2(p + q:)² - (pi + 9:))
4(p + (p - =:)² + +p; + 4))
So overall by independence we get
Var Z Var Z,| Σ
4(p: + qps -;:)² + q:)²
Claim 20 (Claim 10 restated). If > 3000m log (2m), then with a probability of 1 m any I that
forms bin II in IT", has that 1.01m 2 <
P(1++())
101 m
Proof. Let be an interval determining a bin IP. and denote S₁ = 2 2(1)) From our process of partitioning the domain and creating the intervals, we know that S₁ Em Exp (N). Therefore, the sum of independent Exponential r.v.s can conclude that S, Gamma (N/m, )). Using the tail bound of the sum of the exponential distribution [24], we get the following inequality:
Vt > 0, Pr[Sy > [E[ < min
1 expp(-aff - log(t)))
t
where a
our case, we have E[S,] the following result:
E[Sy]
1/v
N/m
so
By setting 1.01, we arrive at
Pr
S
1.01
Pr
1.01N
1
1 10100---00((10))
P.OBOIRN
1
m
ma
m
1.01
2m2
And now if
1
S 1, then we get
1.01
Pr S S
1
Se 1/L00------ooo
Se
0.00040X
1.01m
2m
So by the Union-Bound, we get that Pr[3,, S 1.1/m or S < 1/1.01m] S mm 2m 111)
B.1.1 Proof of Theorem
Having acquired the rudimentary tools, now prove Theorem 7.
Proof of Theorem 7. We can see that in the Part of the algorithm, we have s ~ Poi(m) samples such that for all < i < f(x,)) (1. with equal probability and independent from each other, therefore, by linearity of expectation we get that for the estimator Z from Line 5 of Part of Algorithm 1 have E [ Σ, E(((())((
We can bound the variance of Z using ((m) by the Effron Stein inequality Jackknife principle.
E,
Proposition 21. |ar[Z] 9m.
Proof of Proposition 21. Denote our points X = (I1, 22.,....... Di, Pi,..., x.) E {1, -1]", and it clear to see that if we change one of the points independently ( = (21, ,2, 2/,.... .......... I.) then
1
((x))2(x10)) 27
Var [|s)
E
2
i=1
1
1
E
(()))(((41)))) ((()) +(xx) - - S 16s 8s
2
16

---

And know that Var [[[]]s]] < Var(s) m. Therefore we get
Varl - = [ar 2 + Var[ [ - E[Ss] + m = 9m
Therefore by Chebyshev's inequality, it follows that
9m
Pr[Z S 10 2 1 - Pr|1 [[Z
10ym)
2 0.91.
100m
Now we prove that our Laplace noise does not exceed
provided m 2 100k /
/act.
SK
1 am²a3
6
m
a
a
Pr| Z|
4 2k = Pr Lap
S exp
S
0.01
(1)
4 2k
48h.2
And so
with probability 2 0.9 holds that 2 s 10 +
m
m 26
provided m Z
28
40 ke + 100 AJ
It follows that Part I of Algorithm 1 returns NULL. cc
at
In Part II, we also need to argue that all invocations of TestClosennesrretun NULL. Fix an iteration j and observe that for any it holds that X and Y are distributed like Poi( N 8m3 as the labeling
of points coming from P Q is completely random Ber(1/2). We next bound |X - Y and EX )² using known tail bounds on Poisson random variables (Proposition2).
Proposition 22. Assume that for all j we have N/sm² 4 4l0g0000m). Then with probability 0.99 it holds that for any j and any we have
6N
X
Y
log (800m)
m
Proof. We have that NY Poi Am ). Poi( Sm
and Y; = N X². Therefore, |X| Y! =
|2x] NYi < 2| - E + IN E[N || + 2 [ E[N Seeing as 2 [ B[N
we bound the other two terms using known tail bounds on the Poisson distribution from Proposition
Pr[[X/ - E|X]]| 2 N N/sm' log log(800m))
< 400m
Pr[[N - E[N 2 N/4m log(800m)) < 400m
Provided N/sm² > 4 18000)0 And so, w.p. 2 200m 4 N//mm smm log( (0g(800m) + 2 N//mm log (800m)] S / /6 log Applying the Union Bound on all m² + m² + + m < 2m bins, we have the required.
it follows that X Y? <
We now can complete the proof that Part II also returns NULL. Note that in each invocation of TestClosenesswe use E, NZ points over m² bins. It was already established in the proof
of Lemma 6 that the probability that there exists an invocation where Dmaa
Bm log (800m)
yet due to the Laplace noise Amax
V 6m
log (800m) 8log(2/ao5) is upper bounded by $. We
show a similar result for the difference of 2 Z. which we denote as random variable logg1y (Paa)m/ee)) Standard properties of the Laplace distribution give that the probability that exists even a single invocation of TestCloseness where is greater than log (10)o) 16 lo is at most 0.01. Lastly, we argue that Z isn't too large. Based on Lemma 9 we know that at any iteration j we have E|Z] (
N 8m = and Var[Z] < 2 (N/sm² + N/emm) P = 8m
N²
Using the Chebyshev Inequality and the Union Bound that Pr[3j. Z > 10N /Tog(//a)/8i))
jo 100 0.01.
17

---

And so, w.p. 0.97 8' 0.96 get that
16 (610())) logy/a(7 (2/a)1=
2 = 2+ R 10N /log(/a))8mm
e'
)2
10N llg(( 1/a////8// 3/8m/
12v22+1-log(/
16
(w) 12v log(2/))
N2
22
12vk+TlooRy/a
N2
(xxx)
1
Σ NP)
16
16
S
2
TestCCoseness
Where inequality (+) holds when
log()0)o) (og((()))))g)::3(77)) (V log (800m) + 256 256//o (2(66)))
(n(2)o/6)
N2
22 (/a)
16
Jo jo log(3/6)
1MA/oacV/))oox11)))c(00 log(10 log()))) 19/6)
I2N log(800m)+ 258 258y/log /a) lox (78) In(2ip md
N2 6912k log'
(1/a
which in turn holds when N 2 52(
k4/3
and N 2 ÿx( k2/22)
(373
inequality (**) holds when
log(/a)
log(Va)
2
10N
I 10N
8m2
8k
6912k log (1/a)
which in turn holds when N 2 2 1/22 log(1/)) and inequality (* +) holds due to Proposition 22 when
ΣN m² 2 2//2//// N/mm log(800m) 2 N/2
when N 2 3000m log (800m).
B.2 Proof of Theorem 8
Lemma 23 (Lemma 11 restated), Fix (0.1). Suppose there exists n non-negative random
variables X1, X2.,,...., Xn. such that for each it holds that for some fixed number ag we have Pr|X, 2 a,] 2 p. Then, given constant O there exists another constant C' 0 such that with probability at least C it holds that Σi= X; E Og.
Proof. Define the random variables Y; = {o az with probability
with probability 1 1-p" We can see that PE and that the variance is Var EΣ:=1 Y) Σ Var[Y,] i== af Fix 0. Using Chebyshev's inequality, we bound the probability of being far from their expectation.
E
p(1 p) Ei=
Pr Σ
Y
C.c.E.
E
Σv
Y
< Pr
Y;
E
Σv
Yi
2 (1 - c)E Y
i=1
Var
iiml YJ]
p1 p) > 7t
a
p(1 p) p² c)²
(1 c)2 E EE Y.
c1 (E a?)
Now, since we have Pr[X; 2 0:] for each i, it easy to see that Pr
2 p = Pr|y, = a.
and Pr[X, (0, a:) 11-p= Pr(Y; = 0)
X; 2 Pr Y 2 al for any a. Hence
n
n
n
p p1
Pr
Σ
X
e
Σ
04
> Pr
Σ Y220 e
Σ a
21 (1-c)2
1=1
1=1
Lemma 24. [17) For any two distributions P and Q on (m), let P' and Q' be the merged distributions, Then,
P || - 11'''-C'IA C'lla 2| 1
18

---

Proof. Let Z be the partition of [m]] into i intervals that - E - 2() Let I' be obtained from Z by rounding each upper endpoint of each interval (except for the last) down to the nearest even integer, and rounding the lower endpoint of each interval up to the nearest odd integer. Note that
Σ - = E 2'1112)-- IEZ'
Q'IlAx
IEI
seeing the partition I' is obtained from I by taking at most à points and moving them from one interval to another. Therefore, the difference Eier (P(7) - 2(7) Eier (P(T) (())
at most twice the sum [P(t) - 2(i) over these points, and therefore at most 2| 211 L.k Combining this with the above gives our result.
O
Lemma 25 (Lemma 13 restated). [17] For any two distributions P and Q on [m]] such that
||P Q, a, there iteration j E [log(m/k)] such that lip QT 11 > a/ log(m/k).
Proof. Lemma asserts that
| Al S ||P" - 11 + +211p11 QT 11
a <
We apply this recursively when we know that in the final level jo log( m//( we get that | QT' Il.. = ||p QTT' 1 because the distribution there has at most k bins. Thus
log(m/k)
| QTT
111,1
Therefore, by the average principle one of the j [log(m/k)] must satisfy || QUr l|1, 2 a/ lmg(m/s); which, by Cauchy-Schwee gives || QT ll2 2 a/ (Vkllogm//s)).
19

---

1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract and introduction ensure that the paper focuses on adapting the algorithm tester provided by [16] to preserve differential privacy. It also discusses the difficulties that arise and how they will be addressed.
Justification:
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: see [1]
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
6. Experimental Setting/Details
Question: 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?
Answer: [NA]
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [NA]
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the
NeurlPS Code of Ethics
Answer: [Yes]
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
20

---

Justification: We briefly state the positive importance of using tester way for differential privacy to dissipate into other fields in the first paragraph.
11. 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]
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
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 to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
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 the requirements of your country or institution) were obtained?
Answer: [NA]
21


Reviews:
[{"review_id": "bWWBTroUPK", "reviewer": "Reviewer_aFH2", "summary": "This paper talks about differentially private mechanism for property testing -- testing if two continuous distributions are equivalent. The main contribution of this paper is to develop DP versions of the algorithm in [16], which does not support DP. The algorithms in [16] uses discretization and when two distributions are sufficiently different the discretized version has large L2 norms. \n\nTo support DP, there are challenges of developing the bucketing scheme. Instead of using a fixed bin size, the authors use sorted indices to define bins. This reduces data sensitivity. This requires new analysis of utility and privacy.", "questions": "See above", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "First the problem of DP equivalence testing is an interesting one. The algorithm is performing DP for the algorithm in [16]. Thus it is building on top of [16]. The algorithm makes sense and has merit.", "weaknesses": "There are a few issues that can be addressed to improve the paper.\n\nIt will be nice if the authors can present the algorithm 1 using plain English, instead of just presenting the pseudo code. \n\nOne thing that this paper can do better is to improve the discussion and comparison with the prior literature. In section 1.1 there are prior work on DP methods for identity testing and closeness testing. How does the algorithm in this paper compare with those? \n\nTogether with the issues above, it will be good to highlight the significance of contribution. \n\nLine 45, what is alpha?\n\nLine 58, the data using into -- drop either into or using\n\nLine 72, use re-sample -- remove one of them", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. We tried to describe our algorithm prior to presenting it formally in lines 50-84. We would highly appreciate suggestions as to improving said description. \n\n2. See above discussion as to lower bound comparison.\n\n3. Alpha is the distance parameter. In our case is used for bound below the $\\mathcal{A}_k$ distance under $\\mathcal{H}_1$. (Theorem 8, line 209)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7NZmT3eO5m", "reviewer": "Reviewer_XXUu", "summary": "This paper considers the sample complexity of the problem of equivalence testing for continuous distributions under approximate differential privacy. Mathematically, given two distributions $P$ and $Q$ how many samples is required to have an algorithm that outputs $\\texttt{yes}$ or $\\texttt{no}$ such that\n\n- if $P$ and $Q$ are equal, the algorithm outputs $\\texttt{yes}$  with probability at least $2/3$, and\n- if $P$ and $Q$ have distance at least $\\alpha$ in $\\mathcal{A}_k$-norm, the algorithm outputs $\\texttt{no}$ with probability at least $2/3$.\n\nMoreover, the algorithm must satisfy $(\\varepsilon, \\delta)$ differential privacy.\n\n${\\mathcal{A}} _ k$ norm restricts TV distance to using $k$-intervals:  $\\lVert P - Q \\rVert_{\\mathcal{A} _ k} =  \\sup{\\mathcal{I}} \\sum_{j=1}^k | P[I_j] - Q[I_j]|$, where $\\mathcal{I}$ is a partition of $\\mathbb{R}$ into $k$ intervals.\n\nThe sample complexity this paper obtains is \n\n$$\n\\tilde{O} \\left( \\max \\left\\\\{ \\frac{k^{4/5}}{\\alpha^{6/5}}, \\frac{k^{1/2}}{\\alpha^2}, \\frac{k^{1/3}}{\\alpha^{4/3} \\varepsilon^{2/3}}, \\frac{k^{1/2}}{\\alpha \\varepsilon} \\right\\\\} \\right).\n$$\n\nThe first two terms are the non-private cost that matches the upper and lower bound of [1].\n\nTechnically this paper build upon the techniques of [1]. [1] considers the problem in the non private setting. This paper presents a privatization of the algorithm in [1], through a modification of the second phase of the algorithm in [1] to ensure low sensitivity.\n\n[1] Ilias Diakonikolas, Daniel M Kane, and Vladimir Nikishkin. Optimal algorithms and lower bounds for testing closeness of structured distributions. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1183–1202. IEEE, 2015.", "questions": "For the non-private part, [1] provides matching upper and lower bounds. Are lower bounds under privacy known for this problem? If not, what should we expect the correct bounds to be? It is mentioned that Acharya et al. provide lower bounds in the discrete setting. A comparison with those lower bounds might be helpful to demonstrate this.\n\nIn the main result, logarithmic factors are omitted, but I believe that in the privacy literature, $\\log(1/\\delta)$ is typically considered a polynomial factor. What is the dependence on $\\delta$ in the sample complexity provided in this paper?\n\nMy understanding is that the binning of samples aids in the sensitivity analysis, while Poisson sampling facilitates the analysis from [1]. However, it is not clear which parts of the analysis are based on proofs from [1] and which parts are novel contributions.\n\nWriting and clarity suggestions:\nI think the description of [1]'s algorithm in 'our algorithm' section could be more detailed. I found understanding this paragraph a bit difficult, and I expect that a reader who is not familiar with [1] would benefit from a more comprehensive description of the algorithm. Since the rest of the algorithm relies on this part, and this is the only place it is explained in the text, it is crucial to provide a clear explanation, especially for lines 57-61.\n\nI think there might be a typo on line 104. Another typo on line 161.", "limitations": "Yes, the authors have addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Identity testing is a fundamental and conceptually important problem, and this paper presents the first algorithm for it in the continuous setting.\n\nThe paper modifies the algorithm from [1] to ensure low sensitivity, though further changes and analysis are required to ensure that these modifications do not cause issues for the analysis in [1].", "weaknesses": "The quality of writing and clarity could be improved at some parts. See questions, for some suggested changes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. We made no effort to minimize the polylog$(1/\\delta)$ factor. The sample complexity is given in Line 1 of Part II of our algorithm: $N \\gets 10^7\\left(\\frac{k^{1/3}}{\\alpha^{4/3}\\epsilon^{2/3}} + \\frac {\\sqrt k}{\\alpha\\epsilon}+\\frac{\\sqrt{k}}{\\alpha^2}\\right)\\log^6(\\frac k {\\alpha\\epsilon\\delta})$.\n\n2. ``My understanding is that the binning of samples aids in the sensitivity analysis, while Poisson sampling facilitates the analysis from [1].'' That understanding is spot-on.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Qizc4sBZKm", "reviewer": "Reviewer_ZYiV", "summary": "This paper introduces a novel algorithm for equivalence testing between two continuous distributions under the framework of differential privacy. The proposed method adapts the algorithm by Diakonikolas et al. to a differentially private version, using various clever constructions and privacy mechanisms. The authors derive a theoretical guarantee for the algorithm in terms of a lower bound rate on the number of samples needed to correctly discern the null hypothesis that two distributions are equal versus the alternative that they are $\\alpha$ apart in $\\mathcal{A}_k$-norm. The bound is under the model characteristics $\\alpha$, $k$ and the privacy parameter $\\epsilon$.", "questions": "Remarks / suggestions / questions:\n\n* The notation $n$ is unexplained in the \"Related Work\" section. This should be the cardinality of the sample space when discussing [26] and others. Maybe $n$ is also a poor choice here, as this is typically used to denote sample size, where here it is more similar to dimensionality, or the role of $k$ in this article.\n\n* When presenting the rate in the introduction (i.e. Fact 1) there seems to be some typos: $k^{4/5}/\\alpha^{6/5}$ instead of $k^{4/5}/\\alpha^{5/6} $ following the proof of Section 3. Same seems to be the case for the factor $k^{1/3}/(\\alpha^{4/3} \\epsilon^{2/3})$ in Fact 1; where the sample complexity of Algorithm 1 is of the order $k^{2/3}/(\\alpha^{4/3} \\epsilon^{1/3})$ following Section 3?\n\n* The authors mention in the introduction that one could in principle run the private tester of Diakonikolas $O(1/\\epsilon)$-times to attain the rate $\\sqrt{k}/(\\epsilon \\alpha^2)$. This is however, only a lower bound, and for that quite a loose one. I do not see why noisy count would necessarily give this rate; it seems to be highly dependent on the power calculation used for each of the individual tests. Could this not be $\\sqrt{k}/(\\sqrt{\\epsilon} \\alpha^2)$, for example, considering how Binomial concentration?", "limitations": "What is missing limitations wise is a discussion of optimality, or of implementation of the algorithm in practice (e.g. computational complexity, practical range for $\\epsilon$ for which the privacy constraints are impactful, choices of constants). Otherwise, the article does not have glaring limitations unless one goes beyond its current scope.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* The authors present a novel and creative algorithm tackling an interesting general hypothesis testing problem.\n* The exposition of the algorithm is clear and its logic is well explained, which is a feat considering its complexity.\n* The authors provide a theoretical guarantee with sound proofs that are well-explained.\n* The method provided by the authors should be rate optimal in most high dimensional, large sample applications, in which case the state of the art nonprivate rate of $\\sqrt{k}/\\alpha^2$.\n* I enjoyed reading the article.", "weaknesses": "* The article lacks a broader discussion of the rate attained by the method. The rate attained by the algorithm consists of the maximum of 4 terms, where $\\alpha$ should be considered small (e.g. decreasing as the sample size increases), and $k$ perhaps (very) large. The authors consider a large sample regime. In the current formulation, privacy in most cases, comes at no cost (e.g. the maximum is typically just taken in $\\sqrt{k}/\\alpha^2$)? Furthermore, do the phase transitions have any meaning specifically? Can anything be said about optimality here? To truly make this a strong contribution, I think an optimality result of some sorts is desirable. \n\n* Related to the earlier point: How do the rates compare to those established for continuous distributions belonging to parametric families under DP? In particular, I would like to see mention/discussion of the works of for example: Private Identity Testing for High-Dimensional Distributions -- Canonne et al. (2020) or Private Identity Testing for High-Dimensional Distributions -- S. Narayanan (2022). Although the aforementioned papers consider a different setting, they have accompanying optimality results and provide grounds for assessment of the method of this paper as well. The authors also mention that the method applies to discrete distributions as well. How does the rate compare to those derived in discrete settings such as [2]?\n\nMinor points:\n\n* The way sampling is considered is somewhat ambiguously outlined, whilst this is key in any setting considering privacy. This seems to be a consequence of how the algorithm is designed / how its guarantees are shown. In a privacy setting, most naturally in my opinion, samples are fixed and given. Of course the formulated setting extends naturally to such a formulation for large enough samples, but I personally find the current formulation unnatural considering the privacy angle. \n\n* Imprecision in keeping track of constants in the definition of the algorithm. Many constants are giving (ambiguously large) values (i.e. 10^7 in the algorithm itself). If one were to implement this algorithm, what values should one choose? Which ones are necessarily large in practice, and which are artifacts of the proof?\n\n* The paper could use another thorough proofread for spelling and punctuation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Weakness question \\#1: \nThe constant $c_{dkn}$, which represents their list of inequality of the expectation with $\\Omega$ notation in Diakonikolas et al, does not specify the exact value of this constant. In our second algorithm, we used $10^7$ because in their proof, Diakonikolas et al used the value $10^6$ for the constant for the analysis.\n\nQuestion \\#1: In most of the papers referenced in the related work, $n$ is commonly used to denote the size of the domain. However, in our case, we do not have a specific size for the domain in the continuous regime. Instead, we use $k$ to represent the domain size that we intend to partition in the continuous distribution.\n\nQuestion \\#2: Indeed, throughout the paper the true coefficient should be $\\alpha^{-6/5}$. Similarly, the second term is indeed $k^{1/3}\\alpha^{-4/3}\\epsilon^{-2/3}$.\n\nQuestion \\#3: \nWhen using the Subsample-and-Aggregate framework, running the non-private algorithm $O(1/\\epsilon)$ times is an na\\\"ive upper bound which we haven't delved deeply into. Afterall, it is a baseline --- how'd I approach the problem had I not known how to privatize the algorithm of Diakonikolas et al. It might be the case that a tighter analysis of S\\&A exists for Hypothesis Testing, but we are unaware of it.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LQNeQHaMLM", "reviewer": "Reviewer_3bTx", "summary": "This paper studies closeness (equivalent) testing between two continous distributions under approximate differential privacy. In particular, they propose a private version of the equivalent testing algorithm in [Diakonikolas et al.], which discerns whether the two are identical or far-apart in terms of the $\\mathcal{A}_k$ distance. The structure of the DP algorithm in this paper basically follows that of the algorithm in [Diakonikolas et al.]. The first stage is a simple testing algorithm that counts the difference between pairs of successive samples coming from the same distribution and pairs of successive samples from different distributions. In the second stage, the algorithm divides data points into $m$ intervals to take sufficient advantage of these intervals. In particular, it repeatedly runs a closeness tester based on $\\ell_2$ norm, and merge the bins after each iterations.\n\nTo privatize the above algorithm, there are two main technical obstacles. First is that the private algorithm no longer be able to re-sample new points to estimate the $\\ell_2$ distances. To adress this, the algorithm in this paper uses Poisson-drawn subsamples of each bin and revisit the utility analysis of [Diakonikolas et al.]. The second obstacle is that changing a datapoint might shift all bins in the worst case. To bypass this issue, this paper uses a simple coupling argument. In particular, their algorithm \"randomizes\" the size of each bin by an independent Bernoulli random variable to \"correct\" such shifting.\n\nThis paper also gives the applications of their algorithm on multiple families of distributions. Their approach can be easily applied to discrete distributions.", "questions": "Compared to designing DP-equivalence testers for discrete distributions, what is the most fundamental technical challenge in doing so for continuous distributions? Is this challenge inherited from the corresponding non-private algorithms?", "limitations": "This paper discusses several limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper continues the line of work on designing DP-hypothesis testers, and give the first algorithm on privately testing the equivalence for continous distributions. Although the construction of tester in this paper basically follows the structure in [Diakonikolas et al.], but I appreciate that the authors repeatdly and accurately elaborate on which part of their proof technique deviates from that in [Diakonikolas et al.]. In particular, the coupling argument on the Bernoulli random variables to bound the sensitivity of shifts is simple but sweet. All theorems are clearly stated and the proofs are correct.", "weaknesses": "I have a bit concern about the presentation of this paper. For example, the authors do not introduce their privacy notion (that is, the definition of \"neighboring datasets\") at all. I believe it is important to clarify this because, at first glance, it appears that the input to the algorithm is distributions rather than datasets, and I feel frustated that I have to guess what is the definition of \"neighboring\" by reading the proof the Theorem 3.\n\nSome typos:\n1. In line 10 and line 11 of Algorithm 1, should the letter 'j' be lowercase?\n2. In line 188, a comma was mistakenly written as a period.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. The main challenge in transitioning a non-private algorithm to a private one in a continuous setting is using the \\emph{data itself} to divide the domain. As far as we know, there is no known algorithm for the continuous case in distribution testing that does not in some way partition the domain.  It is well-known that the problem of finding an interior point (outputting a point from a distribution within an interval) in general, without any assumptions, is impossible in the continuous case. Our solution to this is to alter the index of partitioning using Bernoulli rvs.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
First we wish to thank all reviewers for their thoughtful remarks and some spot-on comments. 

In broad brushstrokes, all reviews agree the paper and the algorithm has merit, but the presentation is lacking. We ourselves agree with the reviewer's feedback. In our defense we can only say that (1) the current version is far better then our initial draft; (2) we promise to use the additional page of the camera-ready version to implement the reviewers' suggestions and substantially improve the paper's presentation. In fact, some of the reviewers' comments are the direct result of brevity: we shrunk the Related Work section by removing lower bounds comparison and mentioning Identity Testing, and omitted the definition of Equivalence Testing and of neighboring instances from the Preliminaries hoping the reader knows it already. 

Specifically, regarding a lower bound / comparison to existing works: It is currently not clear what the lower bound is for closeness testing with the $\mathcal{A}_k$ distance or for the continuous case of the privacy parameter regime. However, the paper mentioned in the related work -- of Acharya et al (2018) --- provides a lower bound for identity testing, which is a simpler task than closeness testing. The lower bound they present is $O\left(\frac{\sqrt{n}}{\alpha^2}+\frac{\sqrt{n}}{\alpha\sqrt{\epsilon}} + \frac{n^{1/3}}{\alpha^{4/3}\epsilon^{2/3}}  + \frac{1}{\alpha\epsilon} \right)$ (when $n$ is the size of the domain). Additionally, the paper of Diakonikolas et al (2015) proves that the lower bound for the non-private parameter is $O\left(\frac{\sqrt{k}}{\alpha^2}+\frac{k^{4/5}}{\alpha^{6/5}}\right)$. It can be concluded that the lower bound is at least $\left(\frac{\sqrt{k}}{\alpha^2}+\frac{k^{4/5}}{\alpha^{6/5}}+\frac{\sqrt{k}}{\alpha\sqrt{\epsilon}} + \frac{k^{1/3}}{\alpha^{4/3}\epsilon^{2/3}} + \frac{1}{\alpha\epsilon} \right)$. Our result is almost the same as the lower bound, except for the term $\frac{\sqrt{k}}{\alpha\epsilon}$ (up to a polylog factors). This term is the result of the fact that testing for $\mathcal{A}_k$ distance uses the $L_2$ norm based tester, resulting in the term $\frac{\sqrt{k}}{\alpha\epsilon}$. This discussion will make appear in the camera-ready version of the paper.

As we promise to edit this version as to include your comments, we believe that ultimately our result - especially due to its many applications detailed in Table 1 - merits publication in NeurIPS. We humbly hope that you agree.

Specific reviewers' comments are provided as well.

Meta-review: This paper studies the sample complexity of the problem of equivalence testing for continuous distributions under approximate differential privacy, and presents a new algorithm in this setting. Specifically, it adapts the algorithm of Diakonikolas, Kane, and Nikishkin (FOCS 2015) to the differentially private setting.

The reviewers are in agreement that this paper should be accepted, with the main concern being around the writing of the paper and the fact that some definitions are omitted. The authors are expected to address this concern in the final version as they promised in the rebuttal.
Decision: Accept (poster)