Testing ising models
© Copyright 2018 by SIAM. Given samples from an unknown multivariate distribution p, is it possible to distinguish whether p is the product of its marginals versus p being far from every product distribution? Similarly, is it possible to distinguish whether p equals a given distribution q versus p a...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Society for Industrial and Applied Mathematics
2022
|
| Online Access: | https://hdl.handle.net/1721.1/143463 |
| _version_ | 1811085944363679744 |
|---|---|
| author | Daskalakis, C Dikkala, N Kamath, G |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Daskalakis, C Dikkala, N Kamath, G |
| author_sort | Daskalakis, C |
| collection | MIT |
| description | © Copyright 2018 by SIAM. Given samples from an unknown multivariate distribution p, is it possible to distinguish whether p is the product of its marginals versus p being far from every product distribution? Similarly, is it possible to distinguish whether p equals a given distribution q versus p and q being far from each other? These problems of testing independence and goodness-of-fit have received enormous attention in statistics, information theory, and theoretical computer science, with sample-optimal algorithms known in several interesting regimes of parameters [BFF+01, Pan08, VV17, ADK15, DK16]. Unfortunately, it has also been understood that these problems become intractable in large dimensions, necessitating exponential sample complexity. Motivated by the exponential lower bounds for general distributions as well as the ubiquity of Markov Random Fields (MRFs) in the modeling of high-dimensional distributions, we initiate the study of distribution testing on structured multivariate distributions, and in particular the prototypical example of MRFs: the Ising Model. We demonstrate that, in this structured setting, we can avoid the curse of dimensionality, obtaining sample and time efficient testers for independence and goodness-of-fit. One of the key technical challenges we face along the way is bounding the variance of functions of the Ising model. |
| first_indexed | 2024-09-23T13:17:37Z |
| format | Article |
| id | mit-1721.1/143463 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:17:37Z |
| publishDate | 2022 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/1434632023-06-22T13:37:10Z Testing ising models Daskalakis, C Dikkala, N Kamath, G Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © Copyright 2018 by SIAM. Given samples from an unknown multivariate distribution p, is it possible to distinguish whether p is the product of its marginals versus p being far from every product distribution? Similarly, is it possible to distinguish whether p equals a given distribution q versus p and q being far from each other? These problems of testing independence and goodness-of-fit have received enormous attention in statistics, information theory, and theoretical computer science, with sample-optimal algorithms known in several interesting regimes of parameters [BFF+01, Pan08, VV17, ADK15, DK16]. Unfortunately, it has also been understood that these problems become intractable in large dimensions, necessitating exponential sample complexity. Motivated by the exponential lower bounds for general distributions as well as the ubiquity of Markov Random Fields (MRFs) in the modeling of high-dimensional distributions, we initiate the study of distribution testing on structured multivariate distributions, and in particular the prototypical example of MRFs: the Ising Model. We demonstrate that, in this structured setting, we can avoid the curse of dimensionality, obtaining sample and time efficient testers for independence and goodness-of-fit. One of the key technical challenges we face along the way is bounding the variance of functions of the Ising model. 2022-06-17T15:58:25Z 2022-06-17T15:58:25Z 2018-01-01 2022-06-17T14:41:37Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/143463 Daskalakis, C, Dikkala, N and Kamath, G. 2018. "Testing ising models." Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. en 10.1137/1.9781611975031.130 Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics SIAM |
| spellingShingle | Daskalakis, C Dikkala, N Kamath, G Testing ising models |
| title | Testing ising models |
| title_full | Testing ising models |
| title_fullStr | Testing ising models |
| title_full_unstemmed | Testing ising models |
| title_short | Testing ising models |
| title_sort | testing ising models |
| url | https://hdl.handle.net/1721.1/143463 |
| work_keys_str_mv | AT daskalakisc testingisingmodels AT dikkalan testingisingmodels AT kamathg testingisingmodels |