Sequential Algorithms for Testing Closeness of Distributions
Year: 2021

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 D1 and D2 on {1, . . . , n} are equal or ε-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 TV(D1,D2) between D1 and D2 is larger than ε. As a corollary, letting ε go to 0, we obtain a sequential algorithm for testing closeness when no a priori bound on TV(D1,D2) is given that has a sample complexity Õ( n 2/3 TV(D1,D2) ): this improves over the Õ( n/ logn TV(D1,D2) ) 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.

text: What advantage do sequential procedures provide over batch algorithms for testing properties of unknown distributions? Focusing on the problem of testing whether two distributions D1 and D2 on {1, . . . , n} are equal or ε-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 TV(D1,D2) between D1 and D2 is larger than ε. As a corollary, letting ε go to 0, we obtain a sequential algorithm for testing closeness when no a priori bound on TV(D1,D2) is given that has a sample complexity Õ( n 2/3
TV(D1,D2)4/3 ): this improves over the Õ( n/ lognTV(D1,D2)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.

heading: 1 Introduction
text: How to test if two discrete sources of randomness are similar or distinct? This basic and ubiquitous question is surprisingly not closed if frugality matters, that is if one wants to take the right decision using as few samples as possible. To state the problem more precisely, one first needs to define what “distinct" means. In this paper, we endow the set of probability distributions on {1, . . . , n} with the total variation distance TV, and we fix a tolerance parameter ε ∈ [0, 1]. We consider two distributions D1 and D2, and we assume that either D1 = D2 or TV(D1,D2) > ε. Whenever 0 < TV(D1,D2) ≤ ε, we do not expect any determined behaviour from our test. When both distributions are unknown we are testing closeness, based on an equal number of independent samples of both distributions.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
We also need to specify what kind of “test" is considered. Here we treat the two hypotheses symmetrically (there is no “null hypothesis") : given a fixed risk δ ∈ (0, 1), we expect our procedure to find the true one with probability 1− δ, whichever it is. We call such a procedure δ-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 a δ−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 is the smallest expected number of samples needed before a δ-correct procedure takes a decision. Note that this expected number can depend on the unknown distributions D1 and D2, which can lead to important advantages of sequential procedures.
Contributions When n ≥ 2 is small, we show that the optimal sample complexities can be precisely characterized (up to lower order terms in δ) in both the batch and sequential setting as shown in Table 1. This establishes a provable advantage for sequential strategies over batch strategies when n log(1/δ): sequential algorithms reduce the sample complexity by a factor of at least 4 for any pair of distributions D1 and D2. In addition, the sequential algorithms stop even more rapidly if the tested distributions are far (i.e., TV(D1,D2) ε). The improvements of the sequential algorithm are illustrated in Fig. 1. The sequential algorithms use stopping rules inspired from time uniform concentration inequalities. The problem of testing closeness for small n is studied in Sec. 3.
For general n ≥ 2, we improve the dependence on ε to ε ∨ TV(D1,D2) in the best batch algorithm due to Diakonikolas et al. [2020], which is known to be optimal up to multiplicative constants. Namely we obtain a sequential closeness testing algorithm using a number of samples given by
O ( max ( n2/3 log1/3(1/δ)
(ε ∨ TV(D1,D2))4/3 , n1/2 log1/2(1/δ) (ε ∨ TV(D1,D2))2 ,
log(1/δ)
(ε ∨ TV(D1,D2))2
)) . (1)
As a special case, when ε = 0 (the algorithm should not stop when D1 = D2 in this case) we show that there is an algorithm that stops after
O ( max ( log log(1/d)
d2 , n2/3 log log(1/d)1/3 d4/3 , n1/2 log log(1/d)1/2 d2
)) (2)
samples where d = TV(D1,D2) > 0. This is an improvement over the sequential algorithm of Daskalakis and Kawase [2017] which uses Θ(n/ lognd2 log log(1/d)) samples. We design the stopping rules according to a time uniform concentration inequality deduced from McDiarmid’s inequality, where we use the ideas of Howard et al. [2018, 2020] in order to obtain powers of log log(1/d) instead of log(1/d).
We show that the sample complexity for the testing closeness problem given by Eq. (1) is optimal up to multiplicative constants in the worst case setting (i.e., when looking for a bound independent of the distributions D1 and D2). To do so, we construct two families of distributions whose cross TV distance is exactly d ≥ ε and hard to distinguish unless we have a number of samples given by Eq. (1). This latter lower bound is based on properties of KL divergence along with Wald’s Lemma. We establish a lower bound on the number of queries that matches Eq. (2) up to multiplicative constants.
The proof is inspired by Karp and Kleinberg [2007] 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 Dk (for k integer) that are at distance εk (εk decreasing to 0) from uniform and then use properties of the Kullback-Leibler’s divergence to show that no algorithm can distinguish between Dk and uniform using fewer samples than in Eq. (2).
Discussion on the setting and related work It is clearly impossible to test D1 = D2 versus D1 6= D2 in finite time: this is why we introduce the slack parameter ε. Other authors like Daskalakis and Kawase [2017] make a different choice: they fix no ε, but only require that the test decides for D1 6= D2 as soon as it can, and never stops with high probability when D1 = D2. 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 as KL and χ2 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 a distribution dependent complexity was found by Diakonikolas and Kane [2016] and finally the high probability version by Diakonikolas et al. [2020]. Moreover, the problem of testing D1 = D2 vs D1 6= D2 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 [Naghshvar and Javidi, 2013] and channels’ discrimination [Hayashi, 2009]. Sequential strategies have been also considered for testing continuous distributions by Zhao et al. [2016] 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 inequalities which are surveyed by Howard et al. [2020]. In contrast to the present work, however, they test on the means of the distributions.

heading: 2 Preliminaries
text: We follow mostly Daskalakis and Kawase [2017] in the notation. Given two distributions D1 and D2 on {1, . . . , n} we want to distinguish between two hypothesis H1 : D1 = D2 and H2 : TV(D1,D2) > ε. We call a stopping rule a function T : ⋃ k∈N[n]
k × [n]k → {0, 1, 2} such that if T (x, y) 6= 0 then T (xz, yt) = T (x, y) for all strings x, y, z, t with |x| = |y| and |z| = |t|.
T (x, y) = 1 (resp. T (x, y) = 2) means that the rule accepts H1 (resp. H2) after seeing the sequences x and y while T (x, y) = 0 means the rule doesn’t make a choice and continue sampling. We define two different stopping times, the first τ1(T,D1,D2) = inf{t, T (x1 · · ·xt, y1 . . . yt) = 1} and the second τ2(T,D1,D2) = inf{t, T (x1 · · ·xt, y1 . . . yt) = 2} where x1, . . . are i.i.d. samples from D1 and y1, . . . samples from D2 . We want to find stopping rules satisfying P (τ2(T,D1,D2) ≤ τ1(T,D1,D2)) ≤ δ if D1 = D2 and P (τ1(T,D1,D2) ≤ τ2(T,D1,D2)) ≤ δ whenever TV(D1,D2) > ε. We call such stopping rules δ-correct. Our goal is to minimize the expected sample complexityE(τ1(T,D1,D2)) in case of the input is fromD1,D2 such thatD1 = D2 and E(τ2(T,D1,D2)) in case of the input is from D1, D2 such that TV(D1,D2) > ε.

heading: 3 Testing closeness for small n
text: In this section, we focus on small n ≥ 2 and we consider two distributions D1 and D2 on [n]. We are testing two hypothesis H1: D1 = D2 and H2: TV(D1,D2) > ε. We are interested in precisely comparing the sample complexity of testing closeness in the sequential versus the batch setting. In order to find the optimal constant, we first need to obtain a sharp lower bound in the batch setting, which is done directly by using Stirling’s approximation. We then turn to the sequential case.

heading: 3.1 Batch setting
text: In the batch setting, the number of steps τ is fixed before the test. The tester samples A1, . . . , Aτ ∼ D1 and B1, . . . , Bτ ∼ D2 then decides according to the comparison between the empirical TV distance TV(D̃1τ , D̃2τ ) and ε/2 where D̃1τ = {(∑τ j=1 1Aj=i ) /τ } i∈[n] and
D̃2τ = {(∑τ j=1 1Bj=i ) /τ } i∈[n]
are the empirical distributions. If TV(D̃1τ , D̃2τ ) ≤ ε/2, she accepts H1 and rejects it otherwise. In order to control the number of steps τ so that the error of this algorithm does not exceed δ, McDiarmid’s inequality (Habib et al. [2013]) writes for τ = 4 log(2
n/2/δ) ε2 :
P ( ∃B ⊂ [n/2] : ∣∣∣D̃1,τ (B)−D1(B)− D̃2,τ (B) +D2(B)∣∣∣ > ε 2 ) ≤ ∑ B⊂[n/2] e−τε 2/4 ≤ δ . (M)
Using the following property of TV distance: TV(D1,D2) = maxB⊂[bn/2c] |D1(B)−D2(B)| along with the concentration inequality (M) for D1 = D2 (to control the type I error) and for D1 6= D2 (to control the type II error) we prove that this test is δ-correct. We show in the following proposition that this number of steps τ is necessary. Proposition 3.1. In the batch setting, the algorithm consisting of accepting H1 when TV(D̃1τ , D̃2τ ) ≤ ε/2 and rejecting it otherwise is δ-correct for τ = 4 log(2n/2/δ) ε2 .
Moreover, any δ-correct algorithm testing closeness requires at least τ samples, where τ ≥ min { log(1/2δ)
2 KL(1/2− ε/4‖1/2− ε/2) ,
log(1/2δ)
2 KL(1/2 + ε/4‖1/2)
} −O ( log log(1/δ)
ε2
) .
For this proof, we show that every δ-correct tester can be transformed into a test which depends only on the numbers of 1′s, 2′s, . . . , n′s occurred on {A1, . . . , Aτ} and {B1, . . . , Bτ} . We then consider the distributionsD1,2 = {1/2, 1/2, 0, . . . , 0} orD1,2 = {1/2±ε/2, 1/2∓ε/2, 0, . . . , 0} depending on the outcome of the algorithm when it sees two words of samples having respectively τ(1/2− ε/4) and τ(1/2 + ε/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).
This simple analysis relies on well-known arguments for testing Bernoulli variables D1 = B(p) and D2 = B(q). For example, Anthony and Bartlett [2009] and Karp and Kleinberg [2007] test whether q = 1/2 + ε or q = 1/2− ε with an error probability δ. Anthony and Bartlett [2009] show that we need roughly log(1/δ)ε−2/4 samples while Karp and Kleinberg [2007] prove that 2 log(1/δ)ε−2 samples are sufficient. If ε is not known to the tester, sequential algorithms prove to be essential. Indeed, Karp and Kleinberg [2007] manage to prove that Θ(log log(1/|q − 1/2|)|q − 1/2|−2) is necessary and sufficient to test q > 1/2 vs q < 1/2 with an error probability 1/3. In what follows, we use sequential algorithms to expose the dependency on TV(D1,D2) for the testing closeness problem.

heading: 3.2 Sequential setting
text: 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 a new lower bound inspired from the work of Garivier and Kaufmann [2019].
Proposition 3.2. Let T be a stopping rule for testing closeness: D1 = D2 vs TV(D1,D2) > ε with an error probability δ. Let τ1 and τ2 the associated stopping times. We have
sup D1=D2
E(τ1(D1,D2)) ≥ log(1/3δ)
KL(1/2‖1/2 + ε/2) + KL(1/2‖1/2− ε/2) ∼ ε→0
log(1/3δ)
ε2 and
sup TV(D1,D2)=d
E(τ2(D1,D2)) ≥ log(1/3δ)
KL(1/2 + d/2‖1/2) + KL(1/2− d/2‖1/2) ∼ d→0
log(1/3δ)
d2 if d > ε .
An average number of samples equivalent to log(1/3δ)(ε ∨ TV(D1,D2))−2 is thus necessary when the tester can access sequentially to the samples, which is roughly 4 times less than the complexity obtained in the batch setting. The proof, with a strong information-theoretic flavor, compares two situations: when the samples are from equal distributions and when they are from ε-far distributions. Those samples cannot be distinguished until their size is large enough, as can be proved by combining properties of Kullback-Leibler’s divergence and Wald’s lemma (see the detailed proof in App. A).
In the sequential testing, the tester chooses when to stop according to the previous observations ((A1, B1), . . . , (At, Bt)), making comparisons at each step t. 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 hypothesisH1 or H2. On the contrary, in the batch setting she had to sample enough observation to be simultaneously sure that either H1 or H2 hold. In this aim, at each time step, after sampling a new observation (At, Bt), she compares the updated empirical TV distance St = TV(D̃1t, D̃2t) to specific thresholds and sees if (a) St is sufficiently far from 0 to surely accept H2, (b) St is sufficiently close to ε to surely accept H1, (c) she is unsure and needs further samples to take a sound decision. This test is formally described in Alg. 1 and its execution is illustrated in Figure 1 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 ( ∃t ≥ 1,∃B ⊂ [n/2] : ∣∣∣D̃1,t(B)−D1(B)− D̃2,t(B) +D2(B)∣∣∣ > Φt) ≤ δ, where Φt denote the constant Φt = √ log ( 2n−1t(t+1) δ ) /t. On the other hand, to control the sample
complexity, we prove upper bounds on the expected stopping times: τ1 = inf { t ≥ 1 : TV ( D̃1,t, D̃2,t ) ≤ ε− Φt } , and τ2 = inf { t ≥ 1 : TV ( D̃1,t, D̃2,t ) > Φt } .
Algorithm 1 Distinguish between D1 = D2 and TV(D1,D2) > ε with high probability Require: A1, . . . samples from D1 and B1, . . . samples from D2 Ensure: Accept if D1 = D2 and Reject if TV(D1,D2) > ε with probability of error less than δ t = 1, W = 1 while W = 1 do D̃1,t = {(∑t j=1 1Aj=i ) /t } i∈[n] , D̃2,t = {(∑t j=1 1Bj=i ) /t } i∈[n]
if TV ( D̃1,t, D̃2,t ) >
√ log (
2n−1t(t+1) δ ) t then
W = 0 return Reject
else if TV ( D̃1,t, D̃2,t ) ≤ ε−
√ log (
2n−1t(t+1) δ ) t then
W = 0 return Accept
else t = t+ 1
end if end while
It is clear that the stopping time of the algorithm is random. Yet, we can show that this algorithm stops before the non sequential one and give an upper bound on the expected stopping time τ (or expected sample complexity) using the inequality E(τ) ≤ N + ∑ t≥N P(τ ≥ t), where N is chosen so that P(τ ≥ t) is (exponentially) small for t ≥ 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. 1 is δ-correct and its stopping times verify for n ≤ O(log(1/δ)1/3):
E(τ1(D,D)) ≤ log(2n+1/δ)
ε2 +O
( log(2n+1/δ)2/3
ε2
) if D1 = D2 = D and
E(τ2(D1,D2)) ≤ log(2n+1/δ)
TV(D1,D2)2 +O
( log(2n+1/δ)2/3
TV(D1,D2)2
) if TV(D1,D2) > ε .
These upper bounds are tight on the sense that they match the asymptotic lower bounds of Lemma 3.2 if n log(1/δ) . 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 4 times less than the optimal complexity in the non sequential setting, (c) the sample complexity in the sequential setting depends on the unknown distributions D1 and D2 through the distance TV(D1,D2). Note that this cannot be the case in the batch setting as 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/δ). Finally, we can always truncate a sequential algorithm with the batch one in a way to get the best sample complexity in every regime.

heading: 4 Testing closeness-the general case
text: We consider here the general case n ≥ 3. We recall that we have two unknown distributions D1 and D2 and want to distinguish between D1 = D2 and TV(D1,D2) > ε with high probability 1 − δ. Inspired by the small-n case, we describe how to transform a batch to a sequential algorithm with better expected sample complexity. In that case, exactly identifying the sample complexity remains out of reach: the dependency on ε, δ and n can be computed only up to a multiplicative constant.

heading: 4.1 Batch setting
text: Recently, Diakonikolas et 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/δ times the classical algorithm of Chan et al. [2014] and accepting or rejecting depending on the majority test. More precisely:
Theorem 4.1 (Diakonikolas et al. [2020]). Θ ( max ( n2/3 log1/3(1/δ)
ε4/3 , n 1/2 log1/2(1/δ) ε2 , log(1/δ) ε2 )) samples are necessary and sufficient to test whether D1 = D2 or TV(D1,D2) > ε with an error δ > 0.
The main ingredient of a closeness tester is an efficient test statistic which can distinguish between the two hypothesis. Let us define by Xi (resp. Yi) the number of samples from D1 (resp. D2) whose values are equal to i ∈ [n]. Thinking to the TV distance we use, we could be tempted to take a decision based on the statistic ∑n i=1 |Xi − Yi|. However this simple statistic suffers from a principal caveat: its expected value is neither zero neither easily lower bounded when D1 = D2. As a remedy, Diakonikolas et al. [2020] propose to use the following statistic: Z =∑n i=1 |Xi − Yi|+ |X ′i − Y ′i | − |Xi −X ′i| − |Yi − Y ′i |, where X ′i and Y ′i correspond to a second set of independent samples. The expected value of the estimator Z is obviously 0 when the distributions D1 and D2 are equal. On the other hand when TV(D1,D2) > ε, they provide a lower bound on the expected value of the estimator Z which enable to test closeness between D1 and D2. Since these results turn out to be similarly useful in our subsequent analysis, we summarized them in the following lemma.
Lemma 4.2 (Diakonikolas et al. [2020]). Let d = TV(D1,D2). Let k ≥ 1 and (k1, k2, k′1, k′2) ∼ Multinom(4k, (1/4, 1/4, 1/4, 1/4)). Let (Xi)k1i=1 and (X ′ i) k′1 i=1 two sets of i.i.d. samples from D1 and (Yi)k2i=1 and (Y ′ i ) k′2 i=1 two sets of independent samples fromD2. Then there are universal constants c and C such that
• If D1 = D2, E[Z] = 0. • If TV(D1,D2) > ε, E[Z] ≥ C min { kd, k 2d2 n , k3/2d2√ n } − c √ k.
The lower bound on the expectation ofZ is obtained by Poissonization. This bound is stronger than the one obtained for the chi-square estimator; ∑n i=1 (Xi−Yi)2−Xi−Yi Xi+Yi
, used by Chan et al. [2014]. Indeed for far distributions the lower bound on the expected value of the chi-square estimator does not allow the best dependency on ε and δ. This lemma is the key ingredient behind the batch algorithm. Indeed, for sufficiently large k = Ω ( max ( n2/3 log1/3(1/δ)
ε4/3 , n 1/2 log1/2(1/δ) ε2 , log(1/δ) ε2
)) , Diakonikolas et al.
[2020] show that E[Z] ≥ C ′′ √ k log 1/δ for a universal constant C ′′ if TV(D1,D2) > ε, then by applying McDiarmid’s inequality they prove that the algorithm consisting of returning H2 if Z ≥ C ′′ √ k log 1/δ/2 and returning H1 otherwise is δ-correct. In the following we draw our inspiration from their work to design a sequential algorithm for testing closeness.

heading: 4.2 Sequential setting
text: We present here how the sequential setting can improve the sample complexity found in the batch setting. Our sequential tester is based on the test statistic Z of Diakonikolas et al. [2020], but we allow the stopping rules of this new algorithm to be time-dependent. When the distributions to be tested D1 and D2 are equal, the estimator Zt cannot be very large, and if they are ε-far, the estimator cannot be very small: at each step, the tester compares Zt 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
Algorithm 2 Distinguish between D1 = D2 and TV(D1,D2) > ε with high probability Require: A1, . . . samples from D1 and B1, . . . samples from D2 Ensure: Accept if D1 = D2 and Reject if TV(D1,D2) > ε with probability of error less than δ t = 1, W = 1 while W = 1 do
(m1,t,m ′ 1,t,m2,t,m ′ 2,t) ∼Multinom(4t, (1/4, 1/4, 1/4, 1/4))
Zt = n∑ i=1 |Xi − Yi|+ |X ′i − Y ′i | − |Xi −X ′i| − |Yi − Y ′i | ,
where Xi(resp. X ′i, Yi, Y ′ i ) are the numbers of i’s in the word formed with m1,t (resp. m′1,t,m2,t,m ′ 2,t) samples from D1 (resp. D1,D2,D2) . We need only to sample the difference of (m1,t−m1,t−1)+ + (m′1,t−m′1,t−1)+ from D1 and (m2,t−m2,t−1)+ + (m′2,t−m′2,t−1)+ from D2. if |Zt| > 2 √ 2t log ( π2
3δ
) + 4et log(log(t) + 1) then
W = 0 return Reject else if |Zt| ≤ C min { tε, t 2ε2 n , t3/2ε2√ n } − c √ t− 2 √ 2t log ( π2 3δ ) + 4et log(log(t) + 1) then
W = 0 return Accept
else t = t+ 1
end if end while
defined in Alg. 2. For sake of simplicity, let us denote by ∆t = C min { tε, t 2ε2 n , t3/2ε2√ n } − c √ t
and by Ψt = 2 √ 2t log ( π2
3δ
) + 4et log(log(t) + 1). The stopping times τ1 and τ2 of Alg. 2 are then
defined by
τ1 = inf {t ≥ 1 : |Zt| ≤ ∆t −Ψt} , and τ2 = inf {t ≥ 1 : |Zt| > Ψt} .
We prove now that Alg. 2 is δ-correct and then study its sample complexity.

heading: 4.2.1 Correctness
text: We prove here that Alg. 2 has an error probability less than δ. The proof relies on the following uniform concentration lemma for Zt:
Lemma 4.3. For η, s > 1, let J(η, s, t) = √ 2ηts log (
log(t) log(η) + 1
) − 2t log(ζ(s)−1δ/2) , where
ζ(s) = ∑ n≥1 1 ns . Then
P (∃t ≥ 1 : |Zt − E[Zt]| > J(η, s, 4t)) ≤ δ .
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 in the complexity, in contrast to a simple union bound 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 4.4). However, the log− log dependency proves useful when showing that Alg. 2 used with ε = 0 obtains the optimal sample complexity for
testing D1 = D2 vs D1 6= D2 (see Theorem 4.6). For η = e and s = 2, the function J becomes J(e, 2, 4t) = Ψt and Lemma 4.3 proves the correctness of Alg. 2 as sketched below:
• If D1 = D2, the probability of error is bounded as P (τ2 ≤ τ1) ≤ P (∃t ≥ 1 : |Zt| > Ψt) ≤ δ . • If TV(D1,D2) > ε, the probability of error can be bounded as:
P (τ1 ≤ τ2) = P (∃t ≥ 1 : |Zt| ≤ ∆t −Ψt) (i)
≤ P (∃t ≥ 1 : |Zt − E(Zt)| ≥ E(Zt)−∆t + Ψt) (ii)
≤ P (∃t ≥ 1 : |Zt − E(Zt)| ≥ Ψt) (iii)
≤ δ . where (i) follows from the triangular inequality |Zt − E(Zt)| ≥ E(Zt)− Zt, (ii) follows by the fact that E(Zt) ≥ ∆t from Lemma 4.2 and (iii) follows from Lemma 4.3.

heading: 4.2.2 Complexity
text: The following theorem shows the preeminence of our sequential algorithm, by bounding the expectations of the stopping times τ1 and τ2. Theorem 4.4. Let d = TV(D1,D2). The sample complexity of Alg. 2 satisfies
• If D1 = D2, E(τ1(T,D1,D2)) ≤ 2Nε. • If TV(D1,D2) > ε, E(τ2(T,D1,D2)) ≤ 2Nd.
where for all η > 0, Nη is defined by
Nη = max
{ 128
C2 log(π
2
3δ )
η2 +
512e C2η2 log
( log ( 128 log(π 2 3δ )
η2C2
) + 1 ) + 16c2
C2η2 ,
( 128
C2 n2 log(π
2
3δ )
η4 +
512en2
C2η4 log
( log ( 128
C2 n2 log(π
2
3δ )
η4
) + 1 ) + 16c2n2
η4C2
)1/3 ,
( 128
C2 n log(π
2
3δ )
η4 +
512en C2η4 log
( log ( 128
C2 n log(π
2
3δ )
η4
) + 1 ) + 16c2n
η4C2
)1/2} ,
and the constants c and C come from Lemma 4.2.
This theorem states that O ( max (
n2/3 log1/3(1/δ) (ε∨TV(D1,D2))4/3 , n 1/2 log1/2(1/δ) (ε∨TV(D1,D2))2 , log(1/δ) (ε∨TV(D1,D2))2
)) samples
are sufficient to distinguish between D1 = D2 and TV(D1,D2) > ε with high probability and its proof can be found in App. C. We remark that after Nε steps, the two stopping conditions of Alg. 2 cannot be both unsatisfied. Therefore, the Alg. 2 stops surely before Nε hence it has at least a comparable complexity, in the leading terms, of the batch algorithm of Diakonikolas et al. [2020] when D1 = D2. Moreover, Alg. 2 has the advantage of stopping rapidly when D1 and D2 are far away. It turns out that Alg. 2 is tight, the following lower bounds show that its complexity is optimal up to multiplicative constant. Theorem 4.5. There is no stopping rule T for the problem of testing D1 = D2 vs TV(D1,D2) > ε with an error probability δ such that
P ( τ2(T,D1,D2) ≤ c n1/2 log(1/3δ)1/2
TV(D1,D2)2
) ≥ 1− δ if TV(D1,D2) > ε and
P ( τ1(T,D1,D2) ≤ c n1/2 log(1/3δ)1/2
ε2
) ≥ 1− δ if D1 = D2,
where c a universal constant. We have similar statement if we replace n 1/2 log(1/3δ)1/2
(ε∨TV(D1,D2))2 by log(1/3δ)
(ε∨TV(D1,D2))2 or n2/3 log(1/3δ)1/3 (ε∨TV(D1,D2))4/3 .
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 as if TV(D1,D2) is large. Investigating other classes of distributions for which we get an advantage is 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 TV 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.

heading: 4.3 Special case, taking ε→ 0
text: If we take the precision ε = 0, Alg. 2 provides stopping rules for which the algorithm does not stop if D1 = D2 and rejects if D1 6= D2 with probability at least 1 − δ. Hence, the upper bound on the stopping time τ2 can be translated to an upper bound on the stopping time of testing D1 = D2 vs D1 6= D2. Theorem 4.4 and its proof in App. C show that, with high probability, we have τ2 ≤ NTV(D1,D2) and this upper bound is O ( log log(1/d) d2 ∨ n2/3 log log(1/d)1/3 d4/3 ∨ n 1/2 log log(1/d)1/2 d2
) when d = TV(D1,D2)→ 0. This is the object of the following theorem. Theorem 4.6. There is a stopping rule that can decide D1 6= D2 with probability at least 9/10 using at most O ( log log(1/d)
d2 ∨ n2/3 log log(1/d)1/3 d4/3 ∨ n 1/2 log log(1/d)1/2 d2 ) samples where d = TV(D1,D2).
This result improves upon the sample complexity of Daskalakis and Kawase [2017] where the dependency in n is 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 no stopping rule T for the problem of testing D1 = D2 vs D1 6= D2 with an error probability 1/10 such that
P ( τ2(T,D1,D2) ≤ C n1/2 log log(1/d)1/2
d2
) ≥ 15
16 ,
where d = TV(D1,D2) and C a universal constant. We have similar statements if we replace n1/2 log log(1/d)1/2
d2 by log log(1/d) d or n2/3 log log(1/d)1/3 d4/3 .
To sum up, a number Θ (
log log(1/d) d2 ∨
n2/3 log log(1/d)1/3
d4/3 ∨ n
1/2 log log(1/d)1/2
d2
) of samples is neces-
sary and sufficient to decide whether D1 = D2 or D1 6= D2 with probability 9/10.

heading: 5 Conclusion
text: 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 a similar factor 4 improvement. For the general case, we proposed a tight algorithm for testing closeness where the complexity can depend on the actual TV distance between the two distributions. Our techniques can also be transferred to the testing identity problem based on the batch algorithm derived by Diakonikolas et al. [2017]. 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 a direction worth pursuing.

Review summaries:
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.

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

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.  Letting $\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: $$ H_0: \mathcal D_1 = \mathcal D_2 \quad \textrm{vs.} \quad H_1: \textrm{TV}(\mathcal D_1, \mathcal D_2) > \varepsilon, $$  where $\textrm{TV}$ denotes the usual total variation operator.  The 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.