Testing Product Distributions: A Closer Look

Arnab Bhattacharyya, Sutanu Gayen, Saravanan Kandasamy, N. V. Vinodchandran
Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:367-396, 2021.

Abstract

We study the problems of {\em identity} and {\em closeness testing} of $n$-dimensional product distributions. Prior works of Canonne, Diakonikolas, Kane and Stewart (COLT 2017) and Daskalakis and Pan (COLT 2017) have established tight sample complexity bounds for {\em 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 $d_{\mathrm{TV}}(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 {\em 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v132-bhattacharyya21a, title = {Testing Product Distributions: A Closer Look}, author = {Bhattacharyya, Arnab and Gayen, Sutanu and Kandasamy, Saravanan and Vinodchandran, N. V.}, booktitle = {Proceedings of the 32nd International Conference on Algorithmic Learning Theory}, pages = {367--396}, year = {2021}, editor = {Feldman, Vitaly and Ligett, Katrina and Sabato, Sivan}, volume = {132}, series = {Proceedings of Machine Learning Research}, month = {16--19 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v132/bhattacharyya21a/bhattacharyya21a.pdf}, url = {https://proceedings.mlr.press/v132/bhattacharyya21a.html}, abstract = {We study the problems of {\em identity} and {\em closeness testing} of $n$-dimensional product distributions. Prior works of Canonne, Diakonikolas, Kane and Stewart (COLT 2017) and Daskalakis and Pan (COLT 2017) have established tight sample complexity bounds for {\em 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 $d_{\mathrm{TV}}(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 {\em 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.} }
Endnote
%0 Conference Paper %T Testing Product Distributions: A Closer Look %A Arnab Bhattacharyya %A Sutanu Gayen %A Saravanan Kandasamy %A N. V. Vinodchandran %B Proceedings of the 32nd International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Vitaly Feldman %E Katrina Ligett %E Sivan Sabato %F pmlr-v132-bhattacharyya21a %I PMLR %P 367--396 %U https://proceedings.mlr.press/v132/bhattacharyya21a.html %V 132 %X We study the problems of {\em identity} and {\em closeness testing} of $n$-dimensional product distributions. Prior works of Canonne, Diakonikolas, Kane and Stewart (COLT 2017) and Daskalakis and Pan (COLT 2017) have established tight sample complexity bounds for {\em 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 $d_{\mathrm{TV}}(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 {\em 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.
APA
Bhattacharyya, A., Gayen, S., Kandasamy, S. & Vinodchandran, N.V.. (2021). Testing Product Distributions: A Closer Look. Proceedings of the 32nd International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 132:367-396 Available from https://proceedings.mlr.press/v132/bhattacharyya21a.html.

Related Material