Timezone: »
Poster
Independence Testing for Bounded Degree Bayesian Networks
Arnab Bhattacharyya · Clément L Canonne · Qiping Yang
We study the following independence testing problem: given access to samples from a distribution $P$ over $\{0,1\}^n$, decide whether $P$ is a product distribution or whether it is $\varepsilon$-far in total variation distance from any product distribution. For arbitrary distributions, this problem requires $\exp(n)$ samples. We show in this work that if $P$ has a sparse structure, then in fact only linearly many samples are required.Specifically, if $P$ is Markov with respect to a Bayesian network whose underlying DAG has in-degree bounded by $d$, then $\tilde{\Theta}(2^{d/2}\cdot n/\varepsilon^2)$ samples are necessary and sufficient for independence testing.
Author Information
Arnab Bhattacharyya (National University of Singapore)
Clément L Canonne (IBM Research)
Qiping Yang (National University of Singapore)
Research Assistant at National University of Singapore. Research interests: statistics, learning theory and algorithms.
More from the Same Authors
-
2023 Poster: Private Distribution Learning with Public Data: The View from Sample Compression »
Shai Ben-David · Alex Bie · Clément L Canonne · Gautam Kamath · Vikrant Singhal -
2023 Poster: Unified Lower Bounds for Interactive High-dimensional Estimation under Information Constraints »
Jayadev Acharya · Clément L Canonne · Ziteng Sun · Himanshu Tyagi -
2022 Poster: Nearly-Tight Bounds for Testing Histogram Distributions »
Clément L Canonne · Ilias Diakonikolas · Daniel Kane · Sihan Liu -
2022 Poster: An Adaptive Kernel Approach to Federated Learning of Heterogeneous Causal Effects »
Thanh Vinh Vo · Arnab Bhattacharyya · Young Lee · Tze-Yun Leong -
2022 Poster: Verification and search algorithms for causal DAGs »
Davin Choo · Kirankumar Shiragur · Arnab Bhattacharyya -
2022 Poster: Robust Testing in High-Dimensional Sparse Models »
Anand Jerry George · Clément L Canonne -
2020 Poster: Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning »
Arnab Bhattacharyya · Sutanu Gayen · Kuldeep S Meel · N. V. Vinodchandran -
2020 Poster: Private Identity Testing for High-Dimensional Distributions »
Clément L Canonne · Gautam Kamath · Audra McMillan · Jonathan Ullman · Lydia Zakynthinou -
2020 Spotlight: Private Identity Testing for High-Dimensional Distributions »
Clément L Canonne · Gautam Kamath · Audra McMillan · Jonathan Ullman · Lydia Zakynthinou