Differentially Private Equivalence Testing for Continuous Distributions and Applications

Authors: daniel omer math
  dept
or  sheffet
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 16:51:54

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.

Main paper: 
 introduction: 
 Differential privacy (DP), a mathematically rigorous notion that bounds the effect of any single datum on the output distribution, is the current (de facto) gold-standard of privacy preserving data analysis. By now we have a myriad of DP-algorithms for learning and for various tasks of statistical inference. Indeed, the design of DP-hypothesis testers is crucial for the dissipation of DP into other data-centric fields -such as 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 Total-Variation distance of α using, 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 was resolved in the works of [10, 15, 16] who restricted the TV-distance to using k-intervals. Formally, these works measure distance in A k -norm: where for any two distributions P and Q we have that ∥P -Q∥ A k = sup But the fact remains that continuous distributions pose a special challenge for DP-algorithm designers. In fact, releasing even a simple statistics like the median is impossible over infinite domains [6, 7] .And yet, as we show in this work, it 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 kdistance. 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 Subsample-and-Aggregate framework [26] simply run O(1/ϵ)-times the non-private equivalence tester of Diakonikolas et al [16] and return the most prevalent output using simple noisy count. This gives a simple ϵ-DP equivalence tester with O((k 4/6 α -6/5 + k 1/2 α -2 )/ϵ) sample complexity with two clear drawbacks: (1) its large sample complexity bound and (2) its decision to accept or reject is explained as '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 k 4/5 α 6/5 , k 1/2 α 2 , k 2/3 αϵ 1/3 , k 1/3 α 4/3 ϵ 2/3 , Fact 1. Given a univariate distribution family C and α, let k = k(C, α) be the smallest integer such that for anyf 1 , f 2 ∈ C it holds that ∥f 1 -f 2 ∥ 1 ≤ ∥f 1 -f 2 ∥ A k + α/2.Then there exists a (ϵ, δ)-DP equivalence testing algorithm for C using Õ max k 4/5 /α 6/5 , k 2/3 /αϵ 1/3 , k 1/2 /α 2 , k 1/3 /α 4/3 ϵ 2/3 , √ k /αϵ samples.In Section 4 we detail, much like [16] , a variety of such hypothesis-families and the sample complexities we obtain for their respective DP-equivalence testers.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 a sample complexity of √ n α 4 . Batu et 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 Ω( √ n α 2 ) and proposed a new uniformity test using unique element statistics. The works of [1, 10, 29] explored optimal bounds for identity testing, focusing on χ 2 -based testers. They established a lower bound for closeness testing at [10] providing matching upper bounds for L 2 closeness testing under certain conditions. [14] . introduced a technique reducing distribution norms to O 1 n by expanding the domain size, demonstrating an efficient L 2 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 k 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 L 2 and χ 2 , and [12, 13] demonstrated efficient sample complexity using direct L 1 metric testers due to low sensitivity. We refer the interested reader to Cannone's excellent survey [9] .O n 2/3 α 4/3 + √ n α 2 , withSeveral recent papers have examined hypothesis testing problems under the framework of differential privacy. Cai et al [8] used χ 2 statistic for identity testing, achieving a sample complexity of Õ max√ n α 2 , √ n α 3/2 ϵ , n 1/3 α 5/3 ϵ 2/3• log(1/β) . Aliakbarpour et al [4] proposed three algorithms for differentially private uniformity and closeness testing. They privatized unique element algorithms, collision-based testers, and χ 2 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 concerning privacy and distance parameters by privatizing an L 1 statistic-based algorithm. Aliakbarpour et al [3] also examined closeness testing between distributions with unequal sample sizes, introducing a 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 small sensitivity and sample complexity ofO √ n α 2 + n 2/3 α 4/3 + √ n α √ ϵ + n 1/3 α 4/3 ϵ 2/3 + 1 αϵ .Comparison to Existing Lower Bounds. The well-known lower bound for A k closeness testing in the non-private regime is given in [16] . It is equal toO k 4/5 α 6/5 + √ k α 2 .As far as we know, there is no known lower bound for the private regime in that task. In [2] , a lower bound for the private regime in identity testing is presented asO √ n α 2 + n 2/3 α 4/3 + √ n α √ ϵ + n 1/3 α 4/3 ϵ 2/3 + 1 αϵ (where n = k is the domain size), which is a 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 L 1 tester that is known with low sensitivity. We have established an upper bound that is asymptotically close to the lower bound, given by Õ maxk 4/5 /α 6/5 , k 2/3 /αϵ 1/3 , k 1/2 /α 2 , k 1/3 /α 4/3 ϵ 2/3 , √ k /αϵ .The difference between our upper bound and the lower bound lies in two specific terms:√ k αϵ and k 2/3 αϵ 1/3The first term is a result of the high sensitivity in our algorithm due to the use of L 2 norm testing, which was selected to ensure the utility proof. Additionally, we did not focus on optimizing the term log k αϵδ .Pr [|N j i -E[N j i ]| > 2 N /4m j log(800m)] <Provided N /8m j > 4 log(800m). And so, w.p. ≥ 1 -1 200m it follows that |X j i -Y j i | ≤ 4 N /8m j log(800m) + 2 N /4m j log(800m) ≤ 6 N /m j log(800m). Applying the Union Bound on all m 0 + m 1 + ... + m j0 ≤ 2m bins, we have the required.We now can complete the proof that Part II also returns NULL. Note that in each invocation of TestClosenesswe use m = j N j i points over n = m j bins. It was already established in the proof of Lemma 6 that the probability that there exists an invocation where n max ≤ 6m n log (800m) yet due to the Laplace noise nmax > 6m n log (800m) + 8 log( 2 /j 0 δ) ϵ ′ is upper bounded by δ 2 . We show a similar result for the difference of Ẑ -Z, which we denote as a random variable R ∼ Lap( 16 log4 /3 ( 2 /δ)nz /ϵ ′ ). Standard properties of the Laplace distribution give that the probability that exists even a single invocation of TestCloseness where R is greater than log(10j 0 ) 16 log4 /3 ( 2 /δ)nz /ϵ ′ 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] = m j i=1 ( N 8m -N 8m ) = 0 and Var[Z] ≤ 2 • ( N /8m j + N /8m j ) 2 m j = N 2 8m j . Using the Chebyshev Inequality and the Union Bound that Pr[∃j, Z > 10N log( 1 /α)/8m j ] ≤ j 0 • when N ≥ 3000m log(800m).Lemma 23 (Lemma 11 restated). Fix p ∈ (0, 1). Suppose there exists n non-negative random variables X 1 , X 2 , . . . , X n , such that for each i it holds that for some fixed number a i we have Pr[X i ≥ a i ] ≥ p. Then, given a constant c > 0 there exists another constant C > 0 such that with a probability at least C it holds that Y i ≤ c • E n i=1 Y i ≤ Pr n i=1 Y i -E n i=1 Y i ≥ (1 -c)E n i=1 Y i ≤ Var [ n i=1 Y i ] (1 -c) 2 • E [ n i=1 Y i ] 2 ≤ p(1 -p) n i=1 a 2 i (1 -c) 2 p 2 ( n i=1 a 2 i ) 2 ≤ p(1 -p) p 2 (1 -c) 2Now, since we have Pr[X i ≥ a i ] ≥ p = Pr[Y i = a i ] and Pr[X i ∈ (0, a i )] ≤ 1 -p = Pr[Y i = 0] for each i, it is easy to see that Pr if a = -∞ or b = ∞ our analysis is even simpler, as we take π0 and πm+1 as the respective partition point. 
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)) to denote the total probability mass assigned by P (resp. Q) to a set S. We assume the two distributions are continuous with no discrete point mass, which can always be obtained by concatenating each sample with a uniformly drawn number ∈ R [0, 1]. •If X i ∼ Poi(λ) then Pr[|X -λ| > k] ≤ 2 exp -k 2 2(λ+k) . So for any β > 0, setting k = 2 λ log( 2 /β) we get Pr[|X -λ| > 2 λ log( 2 /β)] ≤ β provided λ > 4 log( 2 /β).Misc. We use Õ (resp. Ω) to denote big-O (resp. big-Ω) up to poly-log factors. We made no effort to minimize constants or the degree of the poly-log. 
private equivalence testing for continuous distributions: 
 In this section, we present our DP-tester for equivalence between two distributions with large A k distance and give both its formal privacy guarantee and its sample complexity bounds. The tester is detailed in Algorithm 1 (which in turn invokes Algorithm 2), where c dkn 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 to 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 to 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 a Bernoulli random variable to each index position (line II.5). Consequently, the algorithm can iteratively run j 0 iterations of the L 2 -tester TestCloseness on based on the randomized partition, where in each invocation of TestCloseness we sample a Poisson-size batch from each partition (line II.11). If the L 2 -tester doesn't reject, then we merge adjacent partition cells (line II.15) and move on to the next iteration. If either invocations of TestCloseness (or the estimator Z has too high of a value) then we reject; but if all test pass we return NULL.Input: 2 continuous distributions P, Q, distance parameter α, privacy parameter ϵ, δ.Output: "NULL" if P = Q; "ALT" if ∥P -Q∥ A k ≥ α 1: Part I: 1. Set m ← 100c dkn k 4 5 /α 6 5 + k 2 3 /αϵ 1 32. Draw s ∼ Poi(m) points from 1 2 (P + Q). 3. Label each x i drawn from P with ℓ(x i ) = 1 and label each x j drawn from Q as ℓ(x j ) = -1. 4. Sort the sample, denote the outcome asx (1) < x (2) < • • • < x (s) . 5. Z = s-1 i=1 ℓ(x (i) )ℓ(x (i+1) ) 6. Draw X ∼ Lap(6/ϵ). 7. Z = Z + X 8. if Z > m 3 α 3 2k 2 then return ALT 2: Part II: 1. Set N ← 10 7 k 1/3 α 4/3 ϵ 2/3 + √ k αϵ + √ k α 2 log 6 ( k /αϵδ) and assert m divides N . 2. Draw s p ∼ Poi N 2 and s q ∼ Poi N 2 ind. Set s ← s p + s q . 3. S ← a sample of s p i.i.d. examples from P and s q i.i.d. examples from Q. 4. Sort S. Denote the outcome as x (1) < x (2) ≤ • • • < x (s) . 5. For each 1 ≤ i ≤ m set π i ← i • N m + B i for ind. drawn B i ∼ Ber( 1 /2). Also set π 0 ← 0, π m+1 ← s + 1. 6. Form the Partition Π0 = {Π 0 1 , Π 0 2 , ..., Π 0 m } where Π 0 i = {x (i ′ ) : π i < i ′ < π i+1 } for every 1 ≤ i ≤ m. 7. Set j 0 ← 1 + ⌈log (m/k)⌉ and m 0 ← m.8. for j = 0, 1, . . . , j 0 -1 do: 9.for i = 1, 2, . . . , m j do: 10.DrawN J i ∼ Poi( N 4m j ). 11.Pick a u.a.r. subsetC J i of N j i points from Π j i . (If N j i > |Π j i | then use special ⊥ points.) 12. Set X j i (resp. Y j i ) as #points from P (resp. Q) in C j i . 13. if TestCloseness i N j i , m j , ⟨X j i ⟩, ⟨Y j i ⟩, α 12 √ 2k+1•log( 1 /α) , ϵ 8 √ j0 log( 2 /δ) , δ 2j0 , δ = ALT then 14.return ALTMerge cells: Set m j+1 ← ⌊ m j /2⌋, and for each 1 ≤ i ≤ m j+1 set:Π j+1 i ← Π j 2i-1 ∪ {x (π i ′ ) } ∪ Π j 2i▷ i ′ =the separating index of the two bins 3: return NULLIn this subsection, our goal is to proof the following theorem. Theorem 3. Algorithm 1 is (2ϵ, 2δ)-DP.The proof of Theorem 3 shows that Part I of Algorithm 1 is ϵ-DP -which is very straight forward, whereas Part II of the algorithm is (ϵ, 2δ)-DP -which involves more intricate arguments. In fact, all that is required regarding the DP of Part I is the following claim. Its proof, as well as most proofs in this section, is deferred to Appendix A. 2 TestCloseness-(N, m, X, Ȳ , α, ϵ ′ , δ ′ , δ) 1: Set n max ← max i {|X i -Y i |}. 2: Set nmax ← n max + Lap( 8 /ϵ) 3: Set Z ← i (X i -Y i ) 2 -X i -Y i = i |X i -Y i | 2 -(X i + Y i ). 4: Set n z ← 6N m log (800N ) + 16 ln(1/δ ′ ) ϵ ′ + 1 5: Set Ẑ ← Z + Lap( 16 log4 /3 ( 2 /δ)nz /ϵ ′ ) 6: if (n max < 6N m log (800N ) + 8 ln(1/δ ′ ) ϵ ′ and Ẑ < 1 2 α 2 N 2 ) then return NULL 7: else return ALTWe thus focus for now on Part II of Algorithm 1. In Part II our output is the (2j 0 )-long tuple ⟨n j max , Z j ⟩ j0-1 j=0 which we may return from the j 0 invocations of TestCloseness. Thus, we denoteϵ ′ = ϵ 8 √ j0 log( 2 /δ) , δ ′ = δ2j0 and note that each invocation of TestCloseness is with these parameters. Throughout our analysis of Part II we assume that the Poisson random variables are known to us, but leave the Bernoulli and the Laplace random variables unknown.Each invocation of TestCloseness releases two statistics: an approximation of n max and approximation of Z. The next two claims bounds their sensitivity (w.h.p.). Claim 5. The Global Sensitivity of n max is at most 4. Lemma 6. There exists an event E where Pr[¬E] < 3δ /2, and under E it holds that the sensitivity ofZ at any iteration j is at most 8 log 4/3 (2/δ) 6N m log (800) + 16 ln(1/δ ′ ) ϵ ′ + 1 .Proof. Denote E 0 as the event that there exists an invocation of TestCloseness with m balls andn bins in which n max ≥ 6m n log (800m) + 16 ln(1/δ ′ ) ϵ ′ , yet nmax < 6m n log (800m) + 8 ln(1/δ ′ ) ϵ ′. It follows that there must exists an invocation of TestCloseness in which the noise added to n max (drawn from Lap(8/ϵ ′ )) must be smaller than -8 ln(1/δ ′ ) ϵ ′ . This holds w.p. < δ ′ /2, and from the Union Bound it follows that Pr[E 0 ] = j0•δ ′ 2 = δ 2 . We now turn to the Bernoulli random variables. Fix S and S ′ to be two neighboring inputs, and again, we assume that the changed point appears in place (1) in S and in place (s) in S ′ . (Otherwise, our analysis is only simpler.) It follows that the changed point falls in Π 0 1 in S and in Π 0 m in S ′ . We now specify the coupling of the Bernoulli random variables between S and S ′ , which is the following. We draw B 1 , B ′ 1 . B 2 , B ′ 2 and so on, u.a.r. and independently, and apply B i -s to the invocation on S and B ′ i -s to the invocation on S ′ , until the first occurrence of B i = 0, B ′ i = 1 from which we give B i+1 , B i+2 and so on to both invocation. This is depicted in Figure 1 .Denote E j as the event that the first occurrence of B i = 0, B ′ i = 1 is at the j-th draw. Clearly Pr[E j ] = ( 3 /4) j-1 • 1 /4. Thus, from the disjointness of events, it follows that Prlog4 /3 (2/δ) j=1 E j = 1 4 log4 /3 (2/δ) j=1 ( 3 /4) j-1 = 1 4 1-( 3 /4) log 4/3 (2/δ) 1-3 /4 = 1 -δ /2. Symmetrically, we apply the same coupling 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, π 1 , is such that for S we go B 1 = 0 and for S ′ we have B ′ 1 = 0; but the index defining the 2nd bin, π 2 it does hold that B 2 = 0, B ′ 2 = 1 so the indices starting from bin 2 onwards align.to align the last bins, those affected by x (s) , in the last position. We use the coupling that providesB m , B ′ m , B m-1 , B ′ m1 , B m-2 , B ′ m-2and so on until the first occurrence of (1, 0) then it switches to the same variable B j . Denoting E ′ j as the event that the first occurrence of B i = 1, B ′ i = 0 is at the m -j-th draw, we have that Prlog4 /3 (2/δ) j=1 E ′ j = 1 -δ /2.We thus denote E = E 0 ∪ log4 /3 (2/δ) j=1 (E j ∪ E ′ j )2 log 4/3 (2/δ) • 4 • (n max + 1) ≤ 8 log 4/3 (2/δ) 6N m log (800N ) + 16 ln(1/δ ′ ) ϵ ′ + 1 .Completing the Proof of Theorem 3 is simple, and is deferred to Appendix A.In this subsection, our goal is to proof the following theorems. Theorem 7. W.p. ≥ 2/3, Algorithm 1 returns NULL whenP = Q. Theorem 8. W.p. ≥ 2/3, Algorithm 1 returns ALT when ∥P -Q∥ A k ≥ α.The proof of Theorem 7 is fairly simple, but the proof of Theorem 8 requires some preliminaries.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. ≥ 5/6. Proving that Part I is correct is very straight-forward due to claims from [16] . And so we focus on the correctness of Part II. Its correctness requires that we first assert a few rudimentary propositions and 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 Πj . 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 k -difference the specific partition Πj * cause us to reject. (Arguing that when P = Q 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 discussion we fix some particular iteration j and examine solely it, without considering the previous iterations.Due to space constraint, we defer nearly all the claims in this section to Appendix B, but they all lead to towards the following main lemma. Lemma 9. Fix index j. For each index i denote by I i as the interval (x (π j i ) , x (π j i+1 ) ) which is the interval defining bin i in the partition Πj . Then the estimator Z computed by TestCloseness satisfies that 2 whereE[Z] = m j i=1 (p i -q i )p i = N P(I i ) 4m(P(I i ) + Q(I i )) , q i = N Q(I i ) 4m(P(I i ) + Q(I i )).and that Var[Z] = m j i=1 4(p i + q i )(p i -q i ) 2 + 2(p i + q i ) 2 .In Lemma 9 we established the expectation and variance of our estimator using the notation p i which in turn is defined as N P(I) 4m(P(I)+Q(I)) (and q i similarly). The following claim is going to assist us in bounding the denominators of p i and q i . Claim 10. If N > 3000m log(2m), then with a probability of 1 -1 m , any I that forms a bin Π 0 i in Π 0 , has that 1 1.01m ≤ P(I)+Q(I)2 ≤ 1.01 m .Unfortunately, due to space constraints, we defer proof of Claim 10 as well as the entire proof of Theorem 7 to Appendix B.We now turn our attention to proving Theorem 8, however, we need one more technical lemma, whose proof -like all proofs in this section -is deferred to Appendix B. Then we can proof Theorem 8.Lemma 11. Fix p ∈ (0, 1). Suppose there exists n non-negative random variables X 1 , X 2 , . . . , X n , such that for each i it holds that for some fixed number a i we have Pr[X i ≥ a i ] ≥ p. Then, given a constant c > 0 there exists another constant C > 0 such that with a probability at least C it holds that then by Chebyshev's inequality we get that with probability 5 6 it holds that Now, consider the total probability mass between a and π i , then the first datapoint selected for the partition that is greater than a. Since the total number of points is taken from a 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 a to π is distributed like the sum of Exponential random variables, namely, a Gamma-distribution with meanZ ≥ E[Z] -10 √ m -|X| ≥ m 3 α 3 2k 2 (≤ N m • 1 N = 1 m , and variance ≤ N m • ( 1 N ) 2 = 1 mN < 1 3000m 2 log(m). It follows that w.p. ≤ 0.01 we have that 12 (P[a, π i ]+Q[a, π i ]) > 1.01 m . A similar analysis shows that for π j , the last datapoint selected for the partition before b, we also haveP([π j , b]) + Q([π j , b]) < 2.02m . 1 Note that a large interval must have a total probability mass P(I) + Q(I) ≥ 10 m and so w.p. ≥ 0.98 we have formed the subinterval I ′ = [π i , π j ] ⊂ I. Moreover, by the subinterval property of large intervals, we have that because P([a,π i ]) + Q([a, π i ]) + P([π j , b]) + Q([π j , b]) < 4.04m then γ(I ′ ) ≥ γ(I) -5γ(I) 10 = γ(I)/2. Therefore, denote N I as the indicator of the event that|P(I ′ )-Q(I ′ )| ≥ γ(I)2 , and we denote P Π 0 and Q Π 0 as the reduced discretized distribution formed by the partition point. We show it preserves most of the total variation∥P Π 0 -Q Π 0 ∥ 1 = I ′ |P(I ′ ) -Q(I ′ )| ≥ I∈I N I γ(I) 2 ≥ I∈I, I large N I γ(I) 2 .We have established that if I is large interval then Pr[N I ] ≥ 0.98, and so, for the random variables, N I γ(I) 2-s (one for each large interval) where for each variable with probability 0.98 it holds that N I γ(I) 2≥ γ(I) 2 , we apply Lemma 11 with c = 0.36 and have that there for the constant C = 1 -0.98(1-0.98) 0.98 2 (1-0.36) 2 > 0.95 such that with probability C > 0.95EQUATIONTherefore, with probability > 0.95,∥P Π 0 -Q Π 0 ∥ 1 ≥ α 12 .Observe that the TV-distance follows from finding suitable subintervals I ′ inside large intervals with large discrepancy. Thus, each of the ≤ k large intervals now gives (at most) 2 points that form I ′ , so these ≤ 2k points partition the real line to ≤ 2k + 1 intervals where the various I ′ -s are part of this partition. It follows that∥P Π 0 -Q Π 0 ∥ A 2k+1 ≥ α12 . Now, to complete the proof, we need to show that Part I of the algorithm detects the discrepancy. We deploy the following lemma from [16] where for a vector v the notation ∥v∥ 1,k refers to the sum of the largest k bins/coordinates of v.Lemma 13. For any two distributions P and Q on[m] such that ∥P -Q∥ A k > α, there iteration j ∈ [log( m /k)] such that ∥P Π j -Q Π j ∥ 1,k > α/ log( m /k). So since ∥P Π 0 -Q Π 0 ∥ A 2k+1 ≥ α12 , we know that by Lemma 13, there exists somej * ∈ [log(m/k)] such that P Π j * -Q Π j * 1,2k+1≥ α 12 log( m /k) and therefore by Cauchy-Schwarz inequalityP Π j * -Q Π j * 2 ≥ α 12 √ 2k+1 log( m /k) . We know that P Π j * -Q Π j * 1,2k+1≥ α 12 log( m /k) . Denote the set of indices of these 2k + 1 intervals as S, we get from Lemma 9 thatE[Z] = m j i=1 (p i -q i ) 2 ≥ i ′ ∈S (p i ′ -q i ′ ) 2 Cau.Sch. ≥ ( i ′ ∈S |p i ′ -q i ′ |) 2 2k+1 ≥ 1 2k+1 i ′ ∈S N |P(I)-Q(I)| 4m j |P(I)+Q(I)| 2 .Also from Lemma 9 we can infer thatPr |Z -E[Z]| ≤ 1 4 E[Z] ≤ 16Var[Z] E[Z] 2 ≤ m j i=1 64(p i + q i )(p i -q i ) 2 + 32(p i + q i ) 2 ( m j i=1 (p i -q i ) 2 ) 2 = m ji=1 64( N (P(I)+Q(I) 4m j (P(I)+Q(I) )(p i -q i ) 2 + 32( N (P(I)+Q(I) 4m j (P(I)+Q(I) ) 2 (m j i=1 (p i -q i ) 2 ) 2 = 2N 2 /m j ( m j i=1 (p i -q i ) 2 ) 2 + 16N/m j m j i=1 (p i -q i ) 2 m j ≥k ≤ 6 • 588 2 (2k + 1) log 2 ( m /k) N 2 α 4 + 28224 log( m /k) N α 2 < 0.01 when N ≥ 10 6 √ k log 2 (m/k) α 2. Now we assert that the noise we added is also proportional to at most1 4 E[Z],and indeed if we draw a random variable R ∼ Lap ∆(Z)ϵ ′with ∆(Z) as defined in Line 5 of TestCloseness, then we get Pr R ≥N 2 α 2 2500(2k+1) log(m/k) ≤ exp N 2 α 2 ϵ ′ 2500(2k+1)∆(Z) ≤ 0.01. which holds if N > 10 6 k∆(Z) α √ ϵ ′ ≥ 10 6 α √ ϵ ′ k • 16 log 4 /3 ( 2 /δ) max N 2k log (10N ), 16 ln(1/δ ′ ) ϵ ′ so we get N = Ω k 1/3 α 4/3 ϵ 2/3 + √ k αϵ .Combining it all together, we have that w.p. ≥ 5/6 Part II of the algorithm also returns ALT. 
applications: 
 Our algorithm is designed for continuous distributions, but it can also be used for discrete distributions. The process is simple: for a given discrete distribution P, for each example x j ∼ P we draw a number i j ∈ R [0, 1], and then sort all the examples ⟨(x j , i j )⟩ m j=1 using lexicographic order. This process gives a simple privatization of the "Flattening method" proposed by Diakonikolas et al [14] , as it does so without looking at the example drawn. Our algorithm method is quite simple: draw m samples from 1 2 (P + Q), then calculate the autocorrelation to identify discrepancies within small intervals. Next, use 2 min(m, n) for flatting to test for total variation distance. It's important to remember that if n = k, where n is the size of the domain, then A k distance is equal to L 1 . However, the sample complexity of the first part, which involves finding discrepancies in small intervals using the analysis of [16] , requires n 4/5 α 6/5 . Fact 1 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 a brief summary of the various statistical inference tasks that can be conducted using our algorithm. , (t(d+1)) 2/3EQUATIONα 4/3 ϵ 1/3 , 1 α 3 ϵ 2/3 , 1 α 5/4 ϵ k- mixture of log- concave k √ α Õ max t 4/5 α 8/5 , k 2/3 α 4/3 ϵ 1/3 , k 1/2 α 9/5 , k 1/3 α 3 ϵ 2/3 , √ k α 5/4 ϵ t-model over [n] t log(n) α Õ max (t log(n)) 4/5 α 2 , (t log(n)) 2/3 α 5/2 ϵ 1/3 , (t log(n)) 1/2 α 5/2 , (t log(n)) 1/3 α 5/3 ϵ 2/3 , √ t log(n) α 3/2 ϵ MHR over [n] log(n/α) α Õ max (log(n/α)) 4/5 α 2 , log(n/α) 2/3 α 5/3 ϵ 1/3 , (log(n/α)) 1/2 α 5/2 , (log(n/α)) 1/3 α 5/3 ϵ 2/3 , √ log(n/α) α 3/2 ϵA Missing Proofs -Privacy Claim 14 (Claim 4 restated). The estimator Z = s i=1 ℓ(x (i) )ℓ(x (i+1) ) in Part I of Algorithm 1 (Line 5) has global senstivity of 6.Proof. Consider omitting a single datapoint, x (i) . It is easy to check cases and see that when ℓ(x (i-1) ) = ℓ(x (i+1) ) = -ℓ(x (i) ) then before omitting x (i) the three entries contributed -2 to Z andafter the omittance they contribute 1 to Z. Thus the change is 3. Considering S and S ′ that are different on a single entry, we have that this change to a 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 n max is at most 4.Proof. Fix S and S ′ to be two neighboring inputs that differ on a single point, and assume that the changed point appears in first place in S and the last (s-th) place in S ′ . Now, it is simple to see that each bin changes by at most two points (its first and last), as shown in Figure 1 . However, since we may not know the beginning-points and end-points of each bin due to the Bernoulli random noise added to each, then in the extreme case the bin from S has addition more point and from S ′ missed a point. This sums to 4 points that may belong to one bin and not the other, shifting the value of X i -Y i by at most 4.Proof of Theorem 3. First, we discuss Part I. In this part we only release the noisy estimator s i=1 ℓ(x (i) )ℓ(x (i+1) ) + X. Due to Claim 4 we know that adding Lap( 6 /ϵ) to this estimator is ϵ-DP. We now move to Part II of the algorithm.In this part we release j 0 -times a pair of outputs: (i) a noisy estimator of n max and (ii) a noisy estimator of Z. Assume the event from Lemma 6 holds. Adding Lap( 8 /ϵ ′ )noise to n max which has global sensitivity of 4 (Claim 5) is ϵ ′ /2-DP. Adding noise of Lap 16 log 4/3 (2/δ) , so it follows from Advanced Composition, that overall we preserve (ϵ, δ/2)-DP under E.6m n log (800m) + 16 ln(1/δ ′ ) ϵ ′ + 1 /ϵ ′ is ϵ ′ /2Summing both Parts together, Algorithm 1 preserves (2ϵ, δ /2)-DP under an event that holds w.p. 1 -3δ /2; so overall Algorithm 1 is (2ϵ, 2δ)-DP.Recall that in Part II we partition the domain into bins by using a list of sorted samples, and see if the examples in those bins pass our L 2 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 Π j i has t i points we argue that the distribution of the number of points following a binomial distribution from P (resp. Q).Claim 16. Fix index j. Fix index i. Denote I as the interval (x (π j i ) , x (π j i+1 ) ) which is some interval defining a bin in the partition Π j i , which contains t i points overall. Then the number of points in an interval Π j i coming from P follow Bin t i , P(I) P(I)+Q(I) . Moreover, for any two disjoint bins Π j i and Π j i ′ it holds that the number of points from P (resp. Q) in each bin is independent of the other.Proof. We draw s from a Poisson distribution with parameter N , representing the number of samples we take from 1 2 (P + Q). As a result, we can determine that within any fixed interval, including the interval I, the number of points we denote as XI follows a Poisson distribution with parameter 1 2 (P(I)). However, we know that the number of points within interval I is exactly t i . So now, conduct a thought experiment, where we re-sample S until precisely t i points from S fall in I. Replacing our original t points in Π 0 i with the new points is indistinguishable as they are distributed precisely the same. Denote Xi (resp. Ỹi ) as the number of points from P (resp. Q) in our repeated thought experiment that fall in I, and define X I (resp. Y I ) as the number of points from P (resp. Q) that fall within interval I in the draw where precisely t i points fall in I from both distributions together. ThereforeX I ∼ XI | XI + ỸI = t iWe can recall that by the definition of our sampling from Poisson distribution, we get that XI ∼ Poi N 2 P(I) , ỸI ∼ Poi N 2 Q(I) , hence by Proposition 2 it follows that X I ∼ Bin(t i , P(I) P(I)+Q(I) ). Note also that X I and X I ′ are independent for every I 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.We now prove that our new selection of points in each bin follows a Poisson distribution.Claim 17. For each interval I defining a bin Π j i , as in Claim 16, it holds that X j i ∼ Poi Proof. Using the same notation as in Claim 16 -we know that for each interval I defining a bin Π j i , the following holds: X I is distributed according to a binomial distribution with parameters t i and P(I) P(I)+Q(I) . Now, let us take a subset of points C j i of size N j i from I, where N j i is a Poisson random variable with parameter λ = N 4m j , and denote X j i as the sum of Bernoulli i.i.d. random variables b r , such that each b r is distributed according to a Bernoulli distribution Ber( P(I) P(I)+Q(I) ). In other words,X j i = Ni r=1 b r .Based on Proposition 2 in the preliminaries, it holds that X j i is distributed like a Poisson r.v. with parameter λ • P(I) P(I)+Q(I) . The proof for Y j i is symmetrical. To prove independence of X j i =N j i i=1 Ber(p) and Y j i = N j i i=1Ber(1 -p), and we havePr[X i = a , Y i = b] = Pr[X i = a , X i + Y i = a + b] = Pr[X i = a | X i + Y i = a + b] • Pr[X i + Y i = a + b] = a + b a p a (1 -p) b • e -( N 4m ) N 4m a+b (a + b)! = 1 a!b! p a (1 -p) b • e -( N 4m )p+( N 4m )(1-p) N 4m a+b (a + b)! = N 4m p a e -( N 4m )p a! • N 4m (1 -p) b e -( N 4m )(1-p) b! = Pr[X i = a] • Pr[Y i = b]Moreover, we need to ensure that each selection of a subset of points does not require more points than we already have, which is no more than N m for each bin, meaning no bin holds any ⊥ points. Claim 18. If N > 32 /3 • m ln(2m), then with probability 1 -1 2m it holds that for each bin i, the size of the chosen subset C i is no greater than N m -1.Proof. The proof follows from standard tail bounds of the Poisson distribution. Given a random variable X ∼ Poi(λ), we haveEQUATIONTherefore, if we want each of the m 0 + m 1 + m 2 + ... + m j ≤ 2m bins to have a subset size that doesn't exceed N m j , we getPr ∀ i, ∀ j, |C j i | < N m j ≥ 1 - i,j Pr[N j i < 4 N 4m j ] ≥ 1 - j m j exp - 3N 16m j ≥ 1 -2m exp - 3N 16m 0 = 1 -2me -2 ln(2m) = 1 - 1 2mLemma 19 (Lemma 9 restated). Fix index j. For each index i denote by I i as the interval (x (π j i ) , x (π j i+1 ) ) which is the interval defining bin i in the partition Πj . Then the estimator Z computed by TestCloseness satisfies that 2 whereE[Z] = m j i=1 (p i -q i )p i = N P(I i ) 4m(P(I i ) + Q(I i )) , q i = N Q(I i ) 4m(P(I i ) + Q(I i )).and that Var[Z] = m j i=1 4(p i + q i )(p i -q i ) 2 + 2(p i + q i ) 2 .Proof. For brevity, we denote X j i as X i and the same for Y i . We want to calculate the expectation of the statisticZ = i (X i -Y i ) 2 -X i -Y i . Therefore E[Z] = E   m j i=1 (X i -Y i ) 2 -X i -Y i   = m j i=1 E[X 2 i -2X i Y i + Y 2 i -X i -Y i ] = m j i=1 p i + p 2 i -2p i q i + q i + q 2 i -p i -q i = m j i=1 (p i -q i ) 2We now want to calculate the variance of Z =n j i=1 (X i -Y i ) 2 -X i -Y i . Therefore Var[Z] = Var   n j i=1 (X i -Y i ) 2 -X i -Y i   = n j i=1 Var (X i -Y i ) 2 -X i -Y i Let's denote Z i = (X i -Y i ) 2 -X i -Y i and calculate E Z 2 i : E Z 2 i = E (X i -Y i ) 2 -X i -Y i 2 = E (X i -Y i ) 4 -2(X i + Y i )(X i -Y i ) 2 + (X i + Y i ) 2We analyze the expectations of each term separately, based on known first to fourth moments of the Poisson distribution [25] and the independence of X i and Y i , we know thatE (X i -Y i ) 4 = E[X 4 i -4X 3 i Y i + 6X 2 i Y 2 i -4X i Y 3 + Y 4 i ] = p 4 i + 6p 3 i + 7p 2 i + p i -4p i (q 3 i + 3q 2 i + q i ) + 6(p i + p 2 i )(q i + q 2 i ) -4q i (p 3 i + 3p 2 i + p i ) + q 4 i + 6q 3 i + 7q 2 i + q i = (p i -q i ) 4 + 6p 3 i + 7p 2 i + p i -4p i (3q 2 i + q i ) + 6p i q i + 6p i q 2 i + 6p 2 i q i -4q i (3p 2 i + p i ) + 6q 3 i + 7q 2 i + q i = (p i -q i ) 4 + 7(p i -q i ) 2 + 6(p 3 i -p 2 i q i -p i q 2 i + q 3 i ) + p i + q i + 12p i q i It is to see that E[(X i + Y i ) 2 ] = p i + p 2 i + q i + q 2 i + 2p i q i = (p i + q i ) 2 + p i + q i , so now E[(X i + Y i )(X i -Y i ) 2 ] = E[X 3 i -2X 2 i Y i + X i Y 2 i + Y i X 2 i -2X i Y 2 i + Y 3 i ] = p 3 i + 3p 2 i + p i -q i (p i + p 2 i ) -p i (q i + q 2 i ) + q 3 i + 3q 2 i + q i = p 3 i -q i p 2 i -p i q 2 i + q 3 i + 3(p i -q i ) 2 + p i + q i + 4p i q iCombining all three terms, we getE Z 2 i = (p i -q i ) 4 + 7(p i -q i ) 2 + 6(p 3 i -p 2 i q i -p i q 2 i + q 3 i ) + p i + q i + 12p i q i -2(p 3 i -q i p 2 i -p i q 2 i + q 3 i + 3(p i -q i ) 2 + p i -q i + 4p i q i ) + (p i + q i ) 2 + p i + q i = (p i -q i ) 4 + 4(p 3 i -p 2 i q i -p i q 2 i + q 3 i ) + (p i -q i ) 2 + (p i + q i ) 2 + 4p i q i = (p i -q i ) 4 + 4(p i + q i )(p i -q i ) 2 + 2(p i + q i ) 2And so we get thatVar[Z i ] = E[Z 2 i ] -E[Z i ] 2 = (p i -q i ) 4 + 4(p i + q i )(p i -q i ) 2 + 2(p i + q i ) 2 -(p i + q i ) 4 = 4(p i + q i )(p i -q i ) 2 + 2(p i + q i ) 2So overall by independence we getVar[Z] = m j i=1 Var[Z i ] = m j i=1 4(p i + q i )(p i -q i ) 2 + 2(p i + q i ) 2Claim 20 (Claim 10 restated). If N > 3000m log(2m), then with a probability of 1 -1 m , any I that forms a bin Π 0 i in Π 0 , has that 1 1.01m ≤ P(I)+Q(I)2 ≤ 1.01 m .Proof. Let I be an interval determining a bin Π 0 i , and denote S I = 1 2 (P(I) + Q(I)). From our process of partitioning the domain and creating the intervals, we know that S I ∼ N/m i=1 Exp (N ). Therefore, as the sum of independent Exponential r.v.s we can conclude that S I ∼ Gamma N /m, 1 N . Using the tail bound of the sum of the exponential distribution [24] , we get the following inequality:∀t > 0, Pr[S I > tE[S I ]] ≤ min 1 t , 1 exp(-α(t -1 -log(t)))where α = E[S I ] 1 /N . In our case, we have E[S I ] = N /m N , so α = N m . By setting t = 1.01, we arrive at the following result:EQUATIONAnd now if t = 1 1.01 ≤ 1, then we getEQUATIONSo by the Union-Bound, we get that Pr[∃I, S I > 1.01 /m or SI < 1 /1.01m] ≤ m( 1 2m 2 + 1 2m 2 ) = 1 m .Having acquired the rudimentary tools, we can now prove Theorem 7.Proof of Theorem 7. We can see that in the Part I of the algorithm, we have s ∼ Poi(m) samples such that for all 1 ≤ i ≤ s ℓ(x i ) ∈ {1, -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 I of Algorithm 1 we haveE[Z] = i E[ℓ(x i )ℓ(x i+1 )] = i E[ℓ(x i )]E[ℓ(x i+1 )] = 0.We can bound the variance of Z using O(m) by the Effron Stein inequality / Jackknife principle.Proposition 21. Var[Z] ≤ 9m.Proof of Proposition 21. Denote our points X = (x 1 , x 2 , . . . , x i , . . . , x s ) ∈ {1, -1} s , and it is clear to see that if we change one of the points independentlyX (i) = (x 1 , x 2 , . . . , x ′ i , . . . , x s ) then Var[Z|s] ≤ 1 2 s i=1 E Z(X) -Z X (i) 2 ≤ 1 2 s i=1 E (ℓ(x i-1 )ℓ(x i ) + ℓ(x i )ℓ(x i+1 ) -ℓ(x i-1 )ℓ(x ′ i ) -ℓ(x ′ i )ℓ(x i+1 )) 2 ≤ 1 2 • 16s = 8sAnd we know that Var[E[Z|s]] ≤ Var[s] = m. Therefore we get Var[Z] = E[Var[Z|s]] + Var[E[Z|s]] ≤ E[8s] + m = 9mTherefore by Chebyshev's inequality, it follows thatPr[Z ≤ 10 √ m] ≥ 1 -Pr[|Z -E[Z]| > 10 √ m] ≥ 1 - 9m 100m ≥ 0.91.Now we prove that our Laplace noise does not exceed m 3 α 3 8k 2 , provided m ≥ 100k .EQUATIONEQUATIONAnd so , with probability ≥ 0.9 it holds that Z ≤ 10 In Part II, we also need to argue that all invocations of TestClosenessreturn NULL. Fix an iteration j and observe that for any i it holds that X j i and Y j i are distributed like Poi( N 8m j ) as the labeling of points as coming from P or Q is completely random Ber( 1 /2). We next bound |X j i -Y j i | and i (X j i -Y j i )) 2 using known tail bounds on Poisson random variables (Proposition2).√ m + 1 4 m 3 α 3 2k 2 < m 3 α 3 2k 2 , provided m ≥ 40 kProposition 22. Assume that for all j we have N /8m j > 4 log(800m). Then with probability > 0.99 it holds that for any j and any i we have|X j i -Y j i | ≤ 6N m j log (800m)Proof. We have thatN j i ∼ Poi( N 4m j ), Poi( N 8m j ) and Y i = N j i -X j i . Therefore, |X j i -Y j i | = |2X j i -N j I | ≤ 2|X j i -E[X j i ]| + |N j i -E[N j i ]| + |2E[X j i ] -E[N j i ]|. Seeing as 2E[X j i ] -E[N j i ]= 0 we bound the other two terms using known tail bounds on the Poisson distribution from Proposition 2.i -E[X j i ]| > 2 N /8m j log(800m)] < 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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. 

To 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.
strength_weakness: strength_weakness: There are a few issues that can be addressed to improve the paper.

It will be nice if the authors can present the algorithm 1 using plain English, instead of just presenting the pseudo code. 

One 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? 

Together with the issues above, it will be good to highlight the significance of contribution. 

Line 45, what is alpha?

Line 58, the data using into -- drop either into or using

Line 72, use re-sample -- remove one of them
questions: questions: See above
limitations: limitations: N/A
paper_summary: paper_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

- if $P$ and $Q$ are equal, the algorithm outputs $\texttt{yes}$  with probability at least $2/3$, and
- 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$.

Moreover, the algorithm must satisfy $(\varepsilon, \delta)$ differential privacy.

${\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.

The sample complexity this paper obtains is 

$$
\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).
$$

The first two terms are the non-private cost that matches the upper and lower bound of [1].

Technically 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.

[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.
strength_weakness: strength_weakness: The quality of writing and clarity could be improved at some parts. See questions, for some suggested changes.
questions: 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.

In 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?

My 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.

Writing and clarity suggestions:
I 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.

I think there might be a typo on line 104. Another typo on line 161.
limitations: limitations: Yes, the authors have addressed the limitations.
paper_summary: paper_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$.
strength_weakness: strength_weakness: * 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. 

* 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]?

Minor points:

* 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. 

* 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?

* The paper could use another thorough proofread for spelling and punctuation.
questions: questions: Remarks / suggestions / questions:

* 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.

* 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?

* 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: 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.
paper_summary: paper_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.

To 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.

This paper also gives the applications of their algorithm on multiple families of distributions. Their approach can be easily applied to discrete distributions.
strength_weakness: strength_weakness: 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.

Some typos:
1. In line 10 and line 11 of Algorithm 1, should the letter 'j' be lowercase?
2. In line 188, a comma was mistakenly written as a period.
questions: 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: limitations: This paper discusses several limitations.

Comments: comment: I thank the authors for the rebuttal. I have updated my score.
Thank you for the rebuttal.
Thank you for your response. I wish to maintain my score.