%ABhattacharyya, Arnab%AGayen, Sutanu%AKandasamy, Saravanan%AVinodchandran, N.%Anull Ed.%D2021%I
%K
%MOSTI ID: 10289198
%PMedium: X
%TTesting Product Distributions: A Closer Look
%XWe study the problems of identity and closeness testing of n-dimensional product distributions. Prior works of Canonne et al. (2017) and Daskalakis and Pan (2017) have established tight sample complexity bounds for non-tolerant testing over a binary alphabet: given two product distributions P and Q over a binary alphabet, distinguish between the cases P = Q and dTV(P;Q) > epsilon . We build on this prior work to give a more comprehensive map of the complexity of testing of product distributions by investigating tolerant testing with respect to several natural distance measures and over an arbitrary alphabet. Our study gives a fine-grained understanding of how the sample complexity of tolerant testing varies with the distance measures for product distributions. In addition,
we also extend one of our upper bounds on product distributions to bounded-degree Bayes nets.
Country unknown/Code not availableOSTI-MSA