Communication and Memory Efficient Testing of Discrete Distributions

By Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, Sankeerth Rao. 2019

31 citations recorded by the source corpus.

We study distribution testing with communication and memory constraints in the following computational models: (1) The {\em one-pass streaming model} where the goal is to minimize the sample complexity of the protocol subject to a memory constraint, and (2) A {\em distributed model} where the data samples reside at multiple machines and the goal is to minimize the communication cost of the protocol. In both these models, we provide efficient algorithms for uniformity/identity testing (goodness of fit) and closeness testing (two sample testing). Moreover, we show nearly-tight lower bounds on (1) the sample complexity of any one-pass streaming tester for uniformity, subject to the memory constraint, and (2) the communication cost of any uniformity testing protocol, in a restricted `one-pass' model of communication.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction (2018, background): “constraints has been studied in [20],6 and, subsequent to an earlier version of this work, the distribution testing problem has been considered in [19].”
Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit (2019, background): “Related to identity testing, a recent work of (Diakonikolas et al., 2019) considers identity testing under both memory and communication constraints.”
Distributed Signal Detection under Communication Constraints (2020, background): “…Xu and Raginsky, 2017; Han et al., 2018a,b; Barnes et al., 2019; Cai and Wei, 2020; Acharya et al., 2019b,d), while distributed testing of distributions in the ﬁnite sample regime was considered in (Acharya et al., 2019b,d; Andoni et al., 2018; Fischer et al., 2018; Diakonikolas et al., 2019).”
Pan-Private Uniformity Testing (2019, methodology): “By a new lower bound, again adapting the memory-restricted lower bound of Diakonikolas et al. [19], we show that sequentially interactive locally private uniformity testing has sample complexity Θ( k ) (Section 5.2).”