%0 Journal Article %1 bhattacharyya2020efficient %A Bhattacharyya, Arnab %A Gayen, Sutanu %A Meel, Kuldeep S. %A Vinodchandran, N. V. %D 2020 %K approximate distributed learning readings stats %T Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning %U http://arxiv.org/abs/2002.05378 %X We design efficient distance approximation algorithms for several classes of structured high-dimensional distributions. Specifically, we show algorithms for the following problems: Given sample access to two Bayesian networks $P_1$ and $P_2$ over known directed acyclic graphs $G_1$ and $G_2$ having $n$ nodes and bounded in-degree, approximate $d_tv(P_1,P_2)$ to within additive error $\epsilon$ using $poly(n,\epsilon)$ samples and time Given sample access to two ferromagnetic Ising models $P_1$ and $P_2$ on $n$ variables with bounded width, approximate $d_tv(P_1, P_2)$ to within additive error $\epsilon$ using $poly(n,\epsilon)$ samples and time Given sample access to two $n$-dimensional Gaussians $P_1$ and $P_2$, approximate $d_tv(P_1, P_2)$ to within additive error $\epsilon$ using $poly(n,\epsilon)$ samples and time Given access to observations from two causal models $P$ and $Q$ on $n$ variables that are defined over known causal graphs, approximate $d_tv(P_a, Q_a)$ to within additive error $\epsilon$ using $poly(n,\epsilon)$ samples, where $P_a$ and $Q_a$ are the interventional distributions obtained by the intervention $do(A=a)$ on $P$ and $Q$ respectively for a particular variable $A$ Our results are the first efficient distance approximation algorithms for these well-studied problems. They are derived using a simple and general connection to distribution learning algorithms. The distance approximation algorithms imply new efficient algorithms for tolerant testing of closeness of the above-mentioned structured high-dimensional distributions.

@article{bhattacharyya2020efficient, abstract = {We design efficient distance approximation algorithms for several classes of structured high-dimensional distributions. Specifically, we show algorithms for the following problems: Given sample access to two Bayesian networks $P_1$ and $P_2$ over known directed acyclic graphs $G_1$ and $G_2$ having $n$ nodes and bounded in-degree, approximate $d_{tv}(P_1,P_2)$ to within additive error $\epsilon$ using $poly(n,\epsilon)$ samples and time Given sample access to two ferromagnetic Ising models $P_1$ and $P_2$ on $n$ variables with bounded width, approximate $d_{tv}(P_1, P_2)$ to within additive error $\epsilon$ using $poly(n,\epsilon)$ samples and time Given sample access to two $n$-dimensional Gaussians $P_1$ and $P_2$, approximate $d_{tv}(P_1, P_2)$ to within additive error $\epsilon$ using $poly(n,\epsilon)$ samples and time Given access to observations from two causal models $P$ and $Q$ on $n$ variables that are defined over known causal graphs, approximate $d_{tv}(P_a, Q_a)$ to within additive error $\epsilon$ using $poly(n,\epsilon)$ samples, where $P_a$ and $Q_a$ are the interventional distributions obtained by the intervention $do(A=a)$ on $P$ and $Q$ respectively for a particular variable $A$ Our results are the first efficient distance approximation algorithms for these well-studied problems. They are derived using a simple and general connection to distribution learning algorithms. The distance approximation algorithms imply new efficient algorithms for {\em tolerant} testing of closeness of the above-mentioned structured high-dimensional distributions.}, added-at = {2020-02-14T16:14:32.000+0100}, author = {Bhattacharyya, Arnab and Gayen, Sutanu and Meel, Kuldeep S. and Vinodchandran, N. V.}, biburl = {https://www.bibsonomy.org/bibtex/2499ecc23f593640a1a8540226525b099/kirk86}, description = {[2002.05378] Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning}, interhash = {850e0cce292a7082d3fb7c5a26dadc19}, intrahash = {499ecc23f593640a1a8540226525b099}, keywords = {approximate distributed learning readings stats}, note = {cite arxiv:2002.05378Comment: 24 pages, 1 figure}, timestamp = {2020-02-20T16:22:45.000+0100}, title = {Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning}, url = {http://arxiv.org/abs/2002.05378}, year = 2020 }