Sequential Algorithms for Testing Closeness of Distributions

Omar Fawzi (1, 2, 3) , Nicolas Flammarion (4) , Aurélien Garivier (1, 3) , Aadil Oufkir (1, 2)

1 LIP - Laboratoire de l'Informatique du Parallélisme
2 QINFO - Traitement optimal de l'information avec des dispositifs quantiques
3 UMPA-ENSL - Unité de Mathématiques Pures et Appliquées
4 CMCS-EPFL - CMCS-EPFL

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/logn/TV(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 identity and closeness: they can improve the worst case number of samples by at most a constant factor.

Domaines: Informatique [cs]

Omar Fawzi, Nicolas Flammarion, Aurélien Garivier, Aadil Oufkir. Sequential Algorithms for Testing Closeness of Distributions. NeurIPS 2021, Dec 2021, Virtual, France. ⟨hal-03481048⟩