Sequential Algorithms for Testing Closeness of Distributions
Authors: Aadil Oufkir
Omar Fawzi
Nicolas Flammarion
Aurélien Garivier
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Distribution testing
property testing
sequential algorithms

Abstract:   What advantage do sequential procedures provide over batch algorithms for testing properties of unknown distributions? Focusing on the problem of testing whether two distributions $\mathcal{D}_1$ and $\mathcal{D}_2$ on $\{1,\dots, n\}$ are equal or $\epsilon$-far, we give several answers to this question. We show that for a small alphabet size $n$, there is a sequential algorithm that outperforms any batch algorithm by a factor of at least $4$ in terms sample complexity. For a general alphabet size $n$, we give a sequential algorithm that uses no more samples than its batch counterpart, and possibly fewer if the actual distance between $\mathcal{D}_1$ and $\mathcal{D}_2$ is larger than $\epsilon$. As a corollary, letting $\epsilon$ go to $0$, we obtain a sequential algorithm for testing closeness (with no a priori bound on the distance between $\mathcal{D}_1$ and $\mathcal{D}_2$) with a sample complexity $\tilde{\mathcal{O}}(\frac{n^{2/3}}{TV(\mathcal{D}_1, \mathcal{D}_2)^{4/3}})$: this improves over the $\tilde{\mathcal{O}}(\frac{n/\log n}{TV(\mathcal{D}_1, \mathcal{D}_2)^{2} })$ tester of [Daskalakis and Kawase 2017]  and is optimal up to multiplicative constants. We also establish limitations of sequential algorithms for the problem of testing closeness: they can improve the worst case number of samples by at most a constant factor. 

Sequential Algorithms for Testing Closeness of Distributions
Omar Fawzi
Nicolas Flammarion EPFL Lausanne, Switzerland nicolas www.mariiannniaamm ionemmrroo@ep......m ch
Univ Lyon, ENS Lyon, UCBL CNRS, Inria, LIP, F-69342 Lyon Cedex 07, France omar fawa.fffzzeeeennyonnnn fr
Aurélien Garivier UMPA UMR 5669 and LIP UMR 5668 CNRS, ENS de Lyon. UCB Lyon 1 Lyon, France
Aadil Oufkir LIP UMR 5668 CNRS ENS de Lyon, UCB Lyon Lyon, France aadil oufkirrens--yon.... fr
aurelien, garivierenies -ateeeeennnnnnn......
aurelien.garrvvierenn--
Abstract
What advantage do sequential procedures provide over batch algorithms for testing properties of unknown distributions? Focusing the problem of testing whether two distributions DD and D2 on {1,...,n) n are equal or g-far, we give several answers to this question. We show that for a small alphabet size n, there is sequential algorithm that outperforms any batch algorithm by a factor of at least 4 in terms sample complexity. For general alphabet size n, we give a sequential algorithm that uses no more samples than its batch counterpart, and possibly fewer if the actual distance TV (D1, D2) between D3 and D: is larger than E. As a corollary, letting E go to 0, we obtain sequential algorithm for testing closeness when no a priori bound on (VD11, D2) given that has a sample complexity n/logn tester of Daskalakis and this improves over the Ö ((Tv/lo TV(2,
a 2/3
1473
Kawase (017) and is optimal up multiplicative constants. We also establish limitations of sequential algorithms for the problem of testing closeness: they can improve the worst case number of samples by at most constant factor.
Introduction
How test if two discrete sources of randomness are similar or distinct? This basic and ubiquitous question is surprisingly not closed frugality matters, that is if one wants to take the right decision using as few samples as possible. what "distinct" means. In this paper, we endow the set of probability distributions on (1.....n)
state the problem more precisely, one first needs to define
with the total variation distance TV, and we fix tolerance parameter E [0, 1]. We consider two distributions D, and D2, and we assume that either D, D2 or TV(D,, D2) < TV(D,, D2) < E, we do not expect any determined behaviour from our test. When both distributions are unknown we are testing closenesy, based on equal number of independent samples of both distributions.
Whenever
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Model
Lower bound
Upper bound
Batch 4 1og((//8e= (log log(l//))//1) 1/0)E
4log 1/0)E + O(ns
log (1/))
Sequential (71)
-
+O((n + log (1/6)2////) )-2)
log [
Sequential (T2)
log(1 log(1/8)d~2 O(d-))
+0 ((n + log log(L/
Table 1: Lower and upper bounds on the sample complexities for testing closeness in the batch and sequential settings with = TV((1, The O hides universal constants.
We also need to specify what kind of "test" is considered. Here treat the two hypotheses symmetrically (there is no "null hypothesis"): given a fixed risk d E (0, 1), we expect our procedure find the true one with probability 1 6, whichever is. We call such a procedure S-correct. Finally, we consider and compare two notions of "frugality": in the batch setting, the agent specifies in advance the number of samples needed for the test: she takes her decision just after observing the data all at once, and the sample complexity of the test is the smallest sample size of d-correct procedure. In the sequential setting, the agent observes the samples one by one, and decides accordingly whether she takes her decision or requests to see more samples before making a decision. Then, the sample complexity of the test the smallest expected number of samples needed before 8-correct procedure takes a decision. Note that this expected number can depend on the unknown distributions D) and D2, which can lead to important advantages of sequential procedures.
Contributions When 2 2 is small, we show that the optimal sample complexities can be precisely characterized (up to lower order terms d) in both the batch and sequential setting as shown in Table This establishes provable advantage for sequential strategies over batch strategies when n < log( log(1/5): sequential algorithms reduce the sample complexity by a factor of at least 4 for any pair of distributions Di and D2. In addition, the sequential algorithms stop even more rapidly if the tested distributions are far (i.e., (V,D1, D2) >> E). The improvements of the sequential algorithm are illustrated in Fig. [ The sequential algorithms use stopping rules inspired from time uniform concentration inequalities. The problem of testing closeness for small n is studied in Sec.
For general n 2 2, we improve the dependence on E to V TV(D,. D2) in the best batch algorithm due Diakonikolas et al. (2020) which is known to be optimal up to multiplicative constants. Namely we obtain sequential closeness testing algorithm using number of samples given by
n/3 log (1/6) TV 4/3)
1/2 log 1/2 (1/8)
log(1/8)
))
o max
(1)
(E ( TV(D), 22)) (EVTV(D, D₂))²
As special case, when e (the algorithm should not stop when Dj = D2 in this case) we show that there is an algorithm that stops after
(log log(1/d) d2
2/3 log log log(1/d)//3 1/2 log log (og(1/d)//2 (2111/122))
o max
(2)
d4/3
d²
samples where d TV(D1, D2) 0. This is an improvement over the sequential algorithm of
Daskalakis and Kawase (017 which uses O logn
de log log(1/d) samples. We design the stopping
rules according to time uniform concentration inequality deduced from McDiarmid's inequality, where we use the ideas of Howard et al. 20188 2020 in order to obtain powers of log log(1/d)
inequull
instead of log(1/d)
We show that the sample complexity for the testing closeness problem given by Eq. II) is optimal up to multiplicative constants in the worst case setting (i.e., when looking for bound independent of
the distributions D, and D2). To do so, we construct two families of distributions whose cross TV
distance is exactly d 2 and hard to distinguish unless we have a number of samples given by Eq. (T) This latter lower bound based on properties of KI. divergence along with Wald's Lemma. We
establish a lower bound on the number of queries that matches Eq. (2 up to multiplicative constants.

---

Teating closcuess for n 10, <- 0.05 and 8 10-10
Tassing elecenes for
0.1 and & 10
Sequential for IV(D,,2) Pa)
TV.2. 1. Day]
Sequeatial Ty for TV(D,, D2)
Empirical TV distance
(V Deal
16
Sequeatial n: TV(P,, D1)
o(1)
Lower bound on batch F
d(t)
Lower bonnd on badtcl + of +-i++
10
07
0.5
1.5
Sample complexity
2.5
3.5
4.5
<10
1205
4000
Iterations
18000
Figure 1: Left: histogram of the stopping times for 100 Monte-Carlo experiments. Black: Dj
D2 Un, blue (resp. magenta): D U, and D2 ((1 + 2:)/n} (resp. {(1 = 4e)nn)). Right: D1 =U2 and D2- = {1 = 22) The sequential tester stops as soon as the statistic enters the red region (for H1) or blue region (for H2) whereas the batch tester waits for the red and blue regions to cover the whole segment [0. 1]. The blue/red and black dashed lines represent respectively the stopping times of the sequential and batch algorithms. We note that, in both cases, the sequential tester stops long before the batch algorithm.
The proof is inspired by Karp and Kleinberg [007] who proved lower bounds for testing whether the mean of a sequence of i.i.d. Bernoulli variables is smaller or larger than 1/2. We construct well-chosen distributions Dx (for integer) that are at distance EN (Ex decreasing to 0) from uniform and then use properties of the Kullback-Leibler divergence to show that no algorithm can distinguish between D2 and uniform using fewer samples than in Eq.
Discussion on the setting and related work It is clearly impossible to test D2 D2 versus D1 # D2 in finite time: this is why we introduce the slack parameter e. Other authors like Bakkaaaalk and Kawase [017] make different choice: they fix e, but only require that the test decides for D1 7 D2 as soon as it can, and never stops with high probability when D1 = D22 We focus on the TV distance in testing closeness problems because it characterises the probability of error for the problem of distributions discrimination: as noted by Daskalakis et al. [2018) using other distances such KL and x is in general impossible.
For an overview of testing discrete distributions we recommend the survey of Canonne [2020]. Testing closeness was solved by Chan et al. [2014], and distribution dependent complexity was found by Diakonikolas and Kane [0166] and finally the high probability version by Diakonikolas
ett al. 2020]. Moreover, the problem of testing Dj D2 Dj + D: was solved by Daskalakis
and Kawase 2017) for n = 2, however the constants are not optimal. They also propose algorithms for the general case using black-box reduction from non-sequential hypothesis testers. Sequential and adaptive procedures have also been explored in active hypothesis setting (Naghshyar and Javidi 2013) and channels' discrimination [Hayashi] 2009]. Sequential strategies have been also considered for testing continuous distributions by Zhao et al. (0016) and [Balsubramani and Ramdas 2015). In the latter, the authors design sequential algorithms whose stopping time adapts to the unknown difficulty of the problem. The techniques used are time uniform concentration incqualities which are surveyed by Howard al. 2020). In contrast to the present work, however, they test on the means of the distributions.
2 Preliminaries
We follow mostly Daskalakis and Kawase [2017] in the notation. Given two distributions Dj and D2 on (l,..., n) we want to distinguish between two hypothesis Hi DD D2 and
H₂ TV(D1, D2)
We call stopping rule function T UseN [n] x [m]] + {0. 1.
such that if T v) # 0 then T(zz, yt) T(z, y) for all strings x, y, 2, with |x| [y] and |2| = |t].
3

---

T(z, y) = (resp. T(x,y) = 2) means that the rule accepts H1 (resp. H2) after seeing the sequences
and y while [(z, y) means the rule doesn't t make choice and continue sampling. We
define two different stopping times, the first 7i (T, D1, D2) = inf [t. T(x ... ... V1 ... Wee 1] inf [t, [x) ... 2t, V1 ... yt)
2} where Ii,... are i.i.d. samples from D1 and V1.... samples from D2 We want to find stopping rules satisfying
and the second 72 D1 D2)
(T2 Dr, D2) S Ti (T, D1, D2)) S 8 if Di = D2 and P (TI (T,, Dr. D2) S (2 D1, D2)) < whenever IV D2) > s. We call such stopping rules d-correct. Our goal is to minimize the expected sample complexity E(T (T, Di, D2)) in case of the input is from Dj, D2 such that Dj = D2
and (TT D1, D2)) in case of the input is from D1, D2 such that TV(D1, D2)
3 Testing closeness for small
In this section, we focus on small n 2 2 and we consider two distributions Dj and D2 on [n]. We are testing two hypothesis H1: D1 D:2 and H2: TV(D1. D2) > E. We are interested in precisely comparing the sample complexity of testing closeness in the sequential versus the batch setting. In order find the optimal constant, we first need obtain sharp lower bound in the batch setting, which is done directly by using Stirling's approximation. We then turn to the sequential case.
3.1 Batch setting
In the batch setting, the number of steps T is fixed before the test. The tester samples Ai,...,A, ~ DD and BI...., B,- ~ D22 then decides according to the comparison between the empirical TV distance TV1 D2,) and s/2 where DI, = (Σf= -A,= /=] [EiN]
and
are the empirical distributions. If TV D2y) S e/2, she D2, = ((,= /T) iE[M]
accepts H1 and rejects it otherwise. In order to control the number of steps so that the er- ror of this algorithm does not exceed 8, McDiarmid's inequality (Habib al. (2013) writes for 1log(2m/2/8)
3 C [n/2] (I) - DD) (B)+ +
> 2
S
-- 58. (M)
BC[n/2]
Using the following property of TV distance: (V, maxBc|ln/2]] [Pi(B) (B) along
with the concentration inequality (M) for Dj = D2 (to control the type error) and for D # D2 (to control the type II error) we prove that this test 5-correct. We show in the following proposition that this number of steps T is necessary.
Proposition 3.1. In the batch setting, the algorithm consisting of accepting H₁ when TV, D2x) S e/2 and rejecting otherwise is 5-correct for 4 4/gg(2//2 18)
8²
Moreover, any d-correct algorithm testing closeness requires at least 7 samples, where
log(1/26) } 2KL(1/2-e/411/2 - 2XL
log(1/26)
log log(1/6)
T 2 min
E2
For this proof, we show that every 5-correct tester can be transformed into test which depends only on the numbers of 1's,2's. ......... n's occurred on (A......A44 the distributions D1.2 = 11/2, 0, 0) or D1,2 = e1/2 1/2 ..... 00 depending on the outcome of the algorithm when it sees two words of samples having respectively 7(1/2 s/4) and 7 r11/2 + e/4) ones (the rest of samples are equal to 2) and derive tight lower bounds on the probability mass function of the multinomial distribution (the full proof is deferred to App. A)).
A,} }
and [B..... .......,,, B,} We then consider

---

This simple analysis relies on well-known arguments for testing Bernoulli variables D B(p) and D2 BB)g). For example, Antthnyy and Bartlett 2009) and Karp and Kleinberg [2007] test whether q /= E q 1/2 E with an error probability 8. Anthony and Bartleu 2009 show that we need roughly log(1 11)5e= /4 samples while Karp and Kleinberg 2007 prove that (og() -2 samples are sufficient. If E is not known to the tester, sequential algorithms prove to be essential. Indeed, Karp and Kleinberg [007]] manage to prove that θ (log log(1//g 1/21)lq
1/2] is necessary and sufficient to test q 1/2 vs < 1/2 with an error probability 1/3. In what follows, we use sequential algorithms to expose the dependency on (V D2) for the testing closeness problem.
3.2 Sequential setting
If one wants to leverage the sequential setting to improve the optimal sample complexity of testing closeness, it is natural to first investigate how it can be improved by removing the batch assumption of the previous lower- bound in Proposition 3.1
We first state new lower bound inspired from the
work of Garivier and Kaufmann (2019).
Proposition 3.2. Let T be a stopping rule for testing closeness: Di D2 vs TV(D1, with an error probability 8. Let and T2 the associated stopping times. We have
1og(1/30)
log(1/30)
sup E(TI (Dr, KL(1/2 E/2) + KL e/2) c02
and
D;=D;
E2
log(1/38)
log(1/30)
sup Dy)Dd
E (Tr, 2 4L(1/2+ SLL1/2-d/2/1//
2
d²
if d >
An average number of samples equivalent to the tester can access sequentially to the samples, which is roughly times less than the complexity obtained in the batch setting. The proof, with strong situations: when the samples are from equal distributions and when they are from e-far distributions. Those samples cannot be distinguished until their size is large enough, can be proved by combining properties Kullback-Leible Leibler's ' divergence and Wald's lemma (see the detailed proof in App.
V TV(D1, D2)) is thus necessary when
flavor, compares two
In the sequential testing, the tester chooses when to stop according to the previous observations ((A), B..,..., (A,,
Be)), making comparisons at each step f. The key explanation of the sequential speedup is that the tester can stop as soon as she is sure that she can accept one of the hypothesis Hi H2. On the contrary, in the batch setting she had to sample enough observation to be simultaneously sure that either Hi or H2 hold. In this aim, at each time step, after sampling new observation (A,, Bi), she compares the updated empirical TV distance S, = TV(D le: Dz.) to specific thresholds and sees (a) S, is sufficiently far from to surely accept Hz. (b) S, is sufficiently close to e to surely accept H1, (c) she is unsure and needs further samples to take sound decision. This test is formally described in Alg. and its execution is illustrated in Figure for n = 2.
To show the correctness of such sequential algorithms, we need here no more than McDiarmid's inequality (M) and the union bound:
P 3 1 c [n/2]
(I.((B) - (BB) -D,, +2(B)) > 2; 16,
where 4, denote the constant 4, Vlog
(2- x
/t. On the other hand, to control the sample
complexity, we prove upper bounds on the expected stopping times:
= inf {1 1211 1: TV (Di.. D2.) S tz and 72 inf {1 1: TV (Dr... Das.) > $1
5

---

Algorithm I Distinguish between Di = D2 and TV(D1, D2) > e with high probability Require: A.,... samples from D1 and B samples from D
Ensure: Accept if D = D2 and Reject if (V(D,, D2) > with probability of error less than 8 1= 1, W
while W
do
D1,
(-) -A5=t
/t]
D2.
1B,= ( kEmM
iE|n]
2" l((()))
TV (DI,1.2.1))
log
then
W = 0
return Reject
else if TV (Di,t. D21) S
log
2
then
W =0
return Accept
else
f t
end if end while
It is clear that the stopping time of the algorithm is random. Yet, show that this algorithm stops before the non sequential one and give an upper bound on the expected stopping time T (or expected sample complexity) using the inequality E(T) S N Ee>N P(T 2 t), where N is chosen so that ( t) is (exponentially) small for i N (see Lemma 4.3). In the following theorem, we state an upper bound on the estimated sample complexity of this algorithm. The full analysis of this algorithm is detailed in App. B
Theorem 3.3. The Alg.
is 8-correct and its stopping times verify for n S (Olog((18)))
1og(2*+1/00
log(2"
1/)/2/3
E(r (D, <
+0
if =D =D and
E²
g2
log(2n+1/00 TV, D2)
(os(2mt//8)24))
E(ra(PI, D2))
O
TV(,,, >
TV(DI, D2)2
These upper bounds are tight on the sense that they match the asymptotic lower bounds of Lemma 3.2 < log(1/8) We see here the many advantages of the sequential setting: (a) the sequential algorithm stops always before the non-sequential algorithm since after the batch complexity the decision regions of the sequential algorithm intersect, (b) the estimated sample complexity is times less than the optimal complexity in the non sequential setting, (c) the sample complexity in the sequential setting depends on the unknown distributions Dj and D2 through the distance TV(D,, D2). Note that this cannot be the case in the batch setting the number of sample should be fixed beforehand. This attribute makes a considerable difference when D1 is very different from D2. Nevertheless, the above lower bounds and upper bounds do not match exactly, the dependence on n cannot be avoided if n is of the order (or larger) of log(1/6). Finally, we can always truncate a sequential algorithm with the batch one in way to get the best sample complexity in every regime.
4 Testing closeness-the general case
We consider here the general case 2 3. We recall that we have two unknown distributions D2 and Dr and want to distinguish between D, D2 and TV(D,, D2) > e with high probability - Inspired by the small-n case, we describe how to transform a batch to sequential algorithm with better expected sample complexity. In that case, exactly identifying the sample complexity remains out of reach: the dependency on and can be computed only up to multiplicative constant.

---

4.1 Batch sefting
Recently, Diakonikolas al. [2020] have shown that the dependence on the error probability in the sample complexity of the closeness problem could be better than the log 1/ found by repeating log 1/6 times the classical algorithm Chan et al. [2014] and accepting or rejecting depending on the majority test. More precisely:
Theorem 4.1 (Diakonikolas al. (0200). O (max (n log (1/5) n2/3 (2/8)) log(1/6)
4473
samples are necessary and sufficient to test whether Dj = D2 or TV(D1, D2) > with an er- for 5 >
The main ingredient of closeness tester is efficient test statistic which can distinguish between the two hypothesis. Let us define by X; (resp. Yj) the number of samples from DD (resp. D2) whose values are equal to i E [n]. Thinking to take a decision based on the statistic Σ |X; Yil. However this simple statistic suffers from a principal caveat: its expected value is neither zero neither easily lower bounded when D1 = D2. As remedy. Diakonikolas et al. (2020) propose to use the following statistic: Z E Ex Y, X Y Y X, X X Y I. where X and Y! correspond to a second set of independent samples. The expected value of the estimator Z is obviously 0 when the distributions Dj and D2 are equal. On the other hand when TV(D1, D2) > E, they provide a lower bound on the expected value of the estimator Z which enable to test closeness between DD and Dz, Since these results turn out be similarly useful in our subsequent analysis, we summarized them in the following lemma.
the TV distance we use, we could be tempted
Lemma 4.2 (Diakonikolas et al. (0200). Ler = TV(D1. D2). Let ls 2 1 and (k1, k2 Ri, K2) ~ Multinom ( 4k, (1/4, 1/4,1/4,1/4) Let (X.) and (X!) two sets of ii.dd samples from D1 KG and (Y:) and (Y:),² two sets of independent samples from Dz2. Then there are universal constants and C such that
E|Z] 0. ITV((D,,))) E|Z] > Cmin { kd, ktd R2/2 /n
-oVk.
The lower bound on the expectation of Z is obtained by Poissonization. This bound is stronger than the one obtained for the chi-square estimator; Σ (X.-Y.)--X.- used by Chan et al. 2014]. Indeed X,+Y,
for far distributions the lower bound on the expected value of the chi-square estimator does not allow the best dependency on and 6. This lemma is the key ingredient behind the batch algorithm. Indeed, for sufficiently large k = (max]
2/3 1/g1/5(1/6)
log(1/5) )). Diakonikolas et al. n²/2 log (1/66)
2473
[0200 show that E| 2 C" /llg for universal constant C" if (V, D2) then by applying McDiarmid's inequality they prove that the algorithm consisting of returning H2 Z 2 C" /k log 1 1/8/2 and returning H, otherwise S-correct. In the following we draw our inspiration from their work design sequential algorithm for testing closeness.
4.2 Sequential setting
We present here how the sequential setting can improve the sample complexity found in the batch setting. Our sequential tester based on the test statistic Z of Diakonikolas et al. [2020). but we allow the stopping rules of this new algorithm to be time-dependen When the distributions to be tested D and D2 are equal, the estimator Z, cannot be very large, and if they are e-far, the estimator cannot be very small: at each step. the tester compares Z, to some well chosen thresholds. If she cannot decide with sufficient confidence, she asks for more samples. This can possibly last until the two decision regions meet. This time has the order of the complexity of the batch algorithm. This tester is formally
7

---

Algorithm 2 Distinguish between D1 = D2 and TV D2) > e with high probability
Require: A,,... samples from D and Bi.... samples from D2
Ensure: Accept if D = D2 and Reject if TV(D, D2) > with probability of error less than 8 == 1, W 1
while W do
(m,, mi m2,,, m2,1) Multinom(( (41, (1/4.//)1111/11/44)
Z = Σ 1=1
X, Y + X - Y X X 1 Y/
where (ressp. X Y, Y2) are the numbers of i's in the word formed with m1,t (resp- m1,0 m2,1, m2 samples from D (resp. P1, 22, D2). We need only to sample the difference
of (m1.* 11,1-1) (m mi,--))* from D1 and (m2, m2,e-1)* (mg, m22 +
from D2.
if [z > 2 2t log ( + 4et log(log(() + then
W 0
return Reject
else if' [2,] < C min te, n Vn
Re7 12/2g2 cvt - 2 2t log
12 35
+ 4et log(log(t) + then
W =
return Accept
else
t= ++1
end if end while
defined in Alg. 2 For sake of simplicity, let us denote by A, C min te,
182222
evt
vn
and by V/, 2 2t log defined by
x2
+ 4et log(log(t) + 1). The stopping times тı and 72 of Alg.
are then
TI = inf (t 1: |2 S A. w.), and 72 inf (t 1: Zz w.
We prove now that Alg. is 8-correct and then study its sample complexity.
4.2.1 Correctness
We prove here that Alg. 2 has error probability less than 8. The proof relies on the following uniform concentration lemma for Z,:
Lemma 4.3. For 7, > 1, let sn,, = 12tts
logít) log(n) + +1) 1-f--1oos log({(s) where
((x) = En>r d. Then
P 12 E[Z J(n, 8, 4f)) 55.
The proof of this lemma is inspired from Howard et al. 2018 and relies on dividing the set of integers into some well chosen subsets, applying union bound and finally invoking McDiarmid's inequality with specific arguments for each interval. It is deferred to Appendix F.4 Note that Lemma 4.3 yields the best second order term on McDiarmid's inequality. This feature is not essential for the study of the testing closeness problem as we are interested here in leading terms only (see Theorem However, the log log dependency proves useful when showing that Alg. 2 used with 0 obtains the optimal sample complexity for
simple union bound complexity, in contrast

---

testing D1 D2 vs D1 * D2 (see Theorem 4.6 For = e and 2. the function J becomes
J(e, 4t) ; and Lemma 4.3 proves the correctness of Alg. as sketched below:
Df = D2, the probability of error is bounded as P (T2 < Ti) < P ( 1: 2 w S 6. (V D2) > s, the probability of error can be bounded as:
(8) P (T) = P (3t 2 1: Zz < A - w. S P 12 E(Z)) 2 ( A v
(1t)
(16)
P 33t 1: 14 - ((4) w1
v 6
where (t) follows from the triangular incquality I2,
Z, (ti) follows by the fact that (Z)) 2 A, from Lemma 4.2 and (iti) follows from Lemma 4.3
4.2.2 Complexity
The following theorem shows the preeminence of our sequential algorithm, by bounding the expecta- tions of the stopping times and 72.
Theorem 4.4. Let d (V1 D2). The sample complexity of Alg. satisfies
IfD: D2, ((n (T. D2) 1 2N (FTV(D), D2) E(T. D2)) - 2Na
where for all n 0, N₂ is defined by
128
log
512e 122
128 log( =²
16c²
N, = max
log
log
+1
C
172
12222
C21
128
x2 n² log(
512en
x2 128 n² log( C
16
1/3
36
log
log
36
+1
+
C
C2p
C
x² 128 n log(
512en
n² 128 n log(
16c²n
1/2
38
log
log
36
+1
C
Can
C
17
17"
and the constants and C come from Lemma
4.2
This theorem states that O mmxx
samples sufficient to distinguish between D D2 and TV(D,, D2) > with high probability and C We remark that after N. steps, the two stopping conditions of Alg- cannot be both unsatisfied. Therefore, the Alg. stops surely before N₂ hence has least comparable complexity, in the leading terms, of the batch algorithm of Diakonikolas et al. [2020] when D, D2. Moreover, Alg. 2 has the advantage of stopping rapidly when D, and D2 are far away. It turns out that Alg. 2is is tight, the following lower bounds show that its complexity is optimal up to multiplicative constant.
n/3 log (1/8)) 2/2 log (1.88)
log(1/8)
(eVTV(D, 423 (eVTV(D, (2)) Po
its proof can be found in App.[C)
Theorem 4.5. There is no stopping rule T for the problem of testing D, = D2 vs (V(D,, > with error probability d such that
n2/22 log(1 11/38)1/2 TV(D,, D2)²
(T, Sc
- (V(DI, > e and
1/2 log (gg(1/38)1/2
(T, D1, D2) <
21-6 8 iDD = D2,
2²
n²/2 log 1og(1/35)2/2 (eVTV(Di.Pa))
where universal constant. We have similar statement if replace log(1/30
by
2/3/ 1///1/3
(eVIV(D,.D.)) or

---

These results imply that if we are looking at bounds that depend only on n. and ö, then sequential algorithms can at most gain a constant factor in terms of complexity. But it is possible that sequential algorithms stop much faster for some classes of distributions, such if (V( D2) is large. Investigating other classes of distributions for which we get an advantage an interesting future direction. This theorem is proven using almost the same construction of distributions as for the batch lower bounds. We point out that the constructed distributions have a TVV distance equal exactly to d >> instead of and we use Wald's lemma along with the tensorization property of KL to deduce lower bounds on a random stopping time. The complete proof is deferred to App. D
4.3 Special case, taking E -
If we take the precision 0. Alg. provides stopping rules for which the algorithm does stop D = D2 and rejects if D1 * D2 with probability at least 1 - 6. Hence, the upper bound on the stopping time T2 can be translated to upper bound on the stopping time of testing DD D2 vs D * D2. Theorem 4.4 and its proof in App. C show that, with high probability, we have
72 S NTV(DD.,s) and this upper bound O
log log 1/d)
2/3 log( (og(1/)))
1/2 log log(1 (og(1/a) d=
d'
d473
when d (V(D1, - O. This the object of the following theorem.
Theorem 4.6. There is stopping rule that decide D3 F DD2 with probability at least 9/10 using V n²/a log log(1 //a5//8 V a n/ log log (1/d//22
most O Ing (og(1/d)
samples where d == (V,D1,
8-1
d2
This result improves upon the sample complexity of Daskalakis and Kawase 2017 where the dependency n/ log n. Furthermore, it is optimal. Indeed we cannot find stopping rules whose sample complexity is tighter than this upper bound as stated in the following theorem (see proof in
App. E
Theorem 4.7. There is stopping rule T for the problem of testing D =D2 D1 # D2 with
error probability 1/10 such that
3/2 log log( (1/)
15
T2 (T,D),,))) S
d²
16
where d = TD, D2) and universal constant. n2/ log 1//(1/4)"/3
We have similar statements if we replace
n log 12 log log(1/d) or by d
d4/3
To sum up, a number + sary and sufficient to decide whether D1 D2 or D1 # D2 with probability 9/10.
log l/g( V 2/3 log log! 1/4) d4/3
n log log( log( 1/d) of samples is neces-
4
d²
5 Conclusion
We have provided a tight analysis of the complexity of testing closeness for small n, where the importance of sequential procedures is clearly exhibited. We would like to emphasize that similar arguments permit to obtain sequential procedures for testing identity problem with similar factor 4 improvement.
For the general case, we proposed tight algorithm for testing closeness where the complexity depend on the actual TV distance between the two distributions. Our techniques can also be transferred to the testing identity problem based on the hatch algorithm derived by Diikonikolas et al. (207)). We note that for some specific families of distributions the improvement can be much more than the general one. This is the case of distributions concentrated in small sets which can be tested rapidly by sequential strategies and direction worth pursuing.
10


Reviews:
[{"review_id": "y-aThpzXY_t", "reviewer": "Reviewer_yo4x", "summary": "In distribution property testing, one aims to solve decision problems on probability distributions with some slack between instances that should be accepted and instances that should be rejected (instances in the slack may be accepted or rejected). In this paper, the authors consider testing whether two discrete distributions with support size n are the same, or differ in total variation distance by at least some constant $\\epsilon$. In particular, they compare the standard batch / non-adaptive setting, where an algorithm specififies a number of samples to draw from both distributions i.i.d. in advance, and the sequential setting, where an algorithm may query sample by sample until it decides it has seen enough. (i) Their sequential algorithm improves the asymptotical dependence of the best known and optimal batch algorithm's sample complexity from $\\epsilon$ to $\\max(\\epsilon, TVD)$, where $TVD$ is the total variation distance of the two input distributions. In other words, given a lower bound on the total variation distance, the algorithms performs best possible in the sense it would not improve if a tight lower bound was known. The resulting algorithm has sample complexity roughly $O(n^{2/3} / \\max(\\epsilon, TVD) \\cdot polylog(\\delta))$. The authors show that their algorithm is asymptotically optimal. (ii) Furthermore, they show that if no lower bound is known, the algorithm stops after roughly $O(n^{2/3} / d^2 \\cdot polylog(\\log TVD))$ samples (provided $TVD > 0$), which improves the dependence on $n$ by roughly a factor $n^{1/3}$ compared to previous work and is shown to be optimal. (iii) For error probability $\\delta$ and $n << \\log(1 / \\delta)$, they show that the query complexity of the best sequential algorithms is separated from the best batch algorithms by a constant factor of 4.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Sequential algorithms have a practical advantage over batch algorithms: their complexity may adapt to the real edit distance / TVD instead of the lower bound $\\epsilon$. This way, one can specify a small $\\epsilon$ and still benefit from a large TVD of the actual distributions when it comes to sample complexity. A standard approach to simulate this using batch algorithms would be to start with a large $\\epsilon'$, say $\\epsilon'=1$, and then iterate by decreasing $\\epsilon'$ each time by some factor, say $1/2$, and restarting until $\\epsilon = \\epsilon'$ or the algorithm rejects. As far as I can judge at a glance, it seems to me that this results in asymptotically comparable bounds at least for $\\epsilon > 0$. In summary, it is not very clear to me how strong the improvement of the theoretical analysis of case (i), and to some extend, also of case (ii), is. As of now, I can see that the dependence $\\log(\\log(TVD))$ improves over $\\log(TVD)$, which I think results from using a batch algorithm as described before, in case (ii), and the separating constant factor 4 of the tight bounds in case (iii). From a theoretical perspective, this would imply a negative result regarding the advantages of sequential algorithms for this problem in the case of $\\epsilon > 0$ and a minor improvement for the case $\\epsilon = 0$. For case (i), I don't see why the standard approach for batch algorithms doesn't yield similar bounds. It would be interesting to see how the sequential algorithm performs against the actual batch algorithm in practice.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Questions to authors:\n1. I'm really confused what the asymptotical benefit of the sequential algorithm over the batch algorithm with an exponential-search like procedure for $\\epsilon' \\rightarrow \\epsilon$ is, for both $\\epsilon > 0$ and $\\epsilon = 0$. The former case seems comparable to me, while the latter has a $\\log(\\log(1/d))$ dependence when the batch approach might have a $\\log(1/d)$ dependence (which results from choosing an exponentially decreasing error probability). Could you confirm whether this is the case, and if not, why? To be precise, I'm thinking of this algorithm:\nbatch_to_sequential($\\epsilon$)\n  $\\epsilon' = 1$\n  result = true\n  while result==true and $\\epsilon < \\epsilon'$:\n    $\\epsilon' = \\epsilon' / 2$\n    result = result && batch_algorithm($\\epsilon'$) //accept = true\n  return result\n\n2. I'm not sure about how I should read the factor 4. To me, it sums up to \"asymptotically, sequential algorithms have no advantage over batch algorithms; however, their absolute complexities are still separated by a constant factor\". Maybe you could carve out and stress your interpretation?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "bE0m_FIMeTt", "reviewer": "Reviewer_fYML", "summary": "In this paper, the authors look at the problem of the goodness of fit testing in the sequential model. There has been a plethora of results and techniques in the last 20 years for the batch model. Here the authors allow the algorithm to stop at any point in time or ask for more samples. They show that the sequential setting beats the batch setting by at least a factor of 4 in the sample complexity. In fact, for a Boolean sample space, they have a more precise characterization up to the lower order terms in the batch setting. For the n>2 cases, they improve the dependence on the farness parameter from $\\epsilon$ to $max(\\epsilon, TV(D_1,D_2))$, which in particular improves upon a result by Daskalakis and Kawase for the case when $epsilon=0$.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "I think the findings are interesting, but the techniques are somewhat limited and incremental, as mentioned below. Therefore, I reckon the paper is marginally above acceptance threshold.\n- Some results in this paper are claimed tight up to multiplicative constants, which is standard in property testing. Then the headline result: that sequential algorithms beat batch algorithm by a factor 4, for n=constant, looks rather weak to me. Although I understand that mathematics has a finer sense of tightness.\n- Lines 69-73: actually, testing in chi-squared or KL is well-known to be in general impossible. See this paper titled: `which distribution distances are sub-linearly testable’.\n- Section 4.1 (Algorithm 2): the techniques are from Diakonikolas et al. and I found their tester is not telling anything new technically. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "TYXHajGZDT", "reviewer": "Reviewer_fx8n", "summary": "The authors tackle (a version of) the two-sample testing problem, where the distributions in question are known to be discrete.  This is clearly a fundamental problem across both theoretical and applied machine learning / statistics.\n\nLetting $\\mathcal D_1, \\mathcal D_2$ be two distributions on $\\{1,\\ldots,n\\}$, and $\\varepsilon > 0$ be some fixed tolerance level, the authors consider testing:\n$$\nH_0: \\mathcal D_1 = \\mathcal D_2 \\quad \\textrm{vs.} \\quad H_1: \\textrm{TV}(\\mathcal D_1, \\mathcal D_2) > \\varepsilon,\n$$\n\nwhere $\\textrm{TV}$ denotes the usual total variation operator.\n\nThe authors study the above problem in both (i) the batch setting, where $\\tau > 0$ samples from both $\\mathcal D_1, \\mathcal D_2$ are available, a priori; and (ii) the sequential setting, where (pairs of) draws from the two distributions stream in, one at a time.  The authors give minimax lower and upper bounds on the testing risk (phrased in the paper in terms of sample complexity, i.e., in terms of $\\tau$); actually, the authors give pairs of bounds (one pair for each problem setting): one bound for $n \\geq 2$, and another for $n \\geq 3$.  A single simulation study is presented.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Overall, the authors tackle an important problem.  And the paper (being a resubmission from COLT) appears to be very solid.  My main issue is that the paper does not really situate itself properly in the literature.  I give some detailed feedback below, broken down into sections according to the categories suggested by the NeurIPS reviewer guidelines.\n\n**Originality.**  I suppose this is a good place to expand on my comment re: related work that I made above.  Two-sample testing is of course a fundamental problem in statistics, and has a long history there.  So, I'm not entirely sure why the authors essentially disregard that entire literature, and only focus on citing TCS papers, in their paragraph on \"Discussion on the setting and related work\" (line 65).  The Kolmogorov-Smirnov and chi-squared examples of relevant tests, though there are others.  And as far as sequential testing goes, the authors might want to give this paper (+ the references therein plus follow-up work) a look: https://arxiv.org/pdf/1506.03486.pdf.\n\nIt's true that much of the above mentioned work concentrates on the situation where the underlying distributions are continuous, but there are remedies for that.  It's also true that these works focus on the K-S distance, though this object is certainly related to the TV distance; in any event, this issue raises the question of why we should care about testing for closeness in the TV sense in the first place (which the authors essentially say comes down to mathematical convenience ~line 66).\n\nAt the very minimum, I think the above works (and more) should be cited; probably more warranted would be a discussion of how the methods and theory in these two literatures compare.\n\n**Clarity.**  The paper is pretty well written, though I found a number of typos:\n* Lines 25-27: I don't understand this.  What you are doing is no different than hypothesis testing, where you are ask for the type 1 and type 2 errors to be controlled in the same way.\n* Line 111: replace the bars \"$||$\" with a comma \",\" inside the TV operator.\n* Line 136: I think you mean Proposition 3.1 (not Theorem 3.1).\n* Line 139: I think you forgot the subscripts on the distributions inside the first sup.  Also, did you flip the order of the subscripts describing the asymptotics?\n\n**Significance.**  In my opinion, the lower bounds are the most important contribution of the paper, and should be quite useful to the community at large.\n\n**Quality.**  I think the paper is, overall, pretty solid.  The authors give some new lower bounds (which seem to be proven essentially by direct arguments, rather than information-theoretic ones).  They also give upper bounds that (the authors say outperform, in terms of testing risk, the state-of-the-art batch method of Diakonikolas et al. (2020), but more to the point ...) outperforms the state-of-the-art sequential algorithm of Daskalakis and Kawase (2017).\n\nMy only complaint, as far as quality goes, is that there aren't enough simulations.  I guess that is fine, for a theory paper.  But when words like \"shows the preeminence of our sequential algorithm\" (line 250) are being thrown around, then you really are claiming that your algorithm is better than all others, and so you had better have some pretty convincing numerical evidence backing that claim up.  Obviously, the current \"experiment\" (i.e., Figure 1) is not really thorough enough by any means to back up that claim ...", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Aside from my comments re: quality above, I'm not sure this section really applies here.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides new upper and lower bounds of the sample complexity of testing closeness of distributions, which together highlight the advantages of a sequential approach to the problem. Despite some initial concerns over constant-factor separations, the reviewers have reached a consensus that the results of the paper are novel and significant, providing crisp complexity bounds on a fundamental learning-related problem.

In revising the manuscript, the authors should pay close attention to the reviewer’s feedback, particularly in regards to discussion of related literature.
Decision: Accept (Spotlight)