Communication and Memory Efficient Testing of Discrete Distributions
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Two-sample testingSimilar Papers 제목 키워드 기반
Robust Testing and Estimation under Manipulation Attacks
We study robust testing and estimation of discrete distributions in the strong contamination model. We consider both the "centralized setting" and the "distributed setting with information constraints" including communic…
Interactive Inference under Information Constraints
We study the role of interactivity in distributed statistical inference under information constraints, e.g., communication constraints and local differential privacy. We focus on the tasks of goodness-of-fit testing and …
Density EstimationLocal minimax rates for closeness testing of discrete distributions
We consider the closeness testing problem for discrete distributions. The goal is to distinguish whether two samples are drawn from the same unspecified distribution, or whether their respective distributions are separat…
Two-sample testingTesting for Families of Distributions via the Fourier Transform
We study the general problem of testing whether an unknown discrete distribution belongs to a specified family of distributions. More specifically, given a distribution family P and sample access to an unknown discrete d…
Two-sample testingOptimal Testing of Discrete Distributions with High Probability
We study the problem of testing discrete distributions with a focus on the high probability regime. Specifically, given samples from one or more discrete distributions, a property $\mathcal{P}$, and parameters $0< \epsil…
Vocal Bursts Intensity Prediction