Testing Ising models

MaRDI QIDQ4608021zbMATH OpenFDO

Authors Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1612.03147, http://dl.acm.org/citation.cfm?id=3175435

zbMATH Keywords

Ising modelsmultivariate distribution

Mathematics Subject Classification ID

Nonparametric hypothesis testing (62G10) Markov processes: hypothesis testing (62M02) Applications of statistics to physics (62P35) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Abstract: 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. 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.

Recommendations

• Property testing in high-dimensional Ising models
• Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
• On testing for parameters in Ising models
• Global testing against sparse alternatives under Ising models
• Testing identity of structured distributions

Cited in

(16)

• Two-sample hypothesis testing for inhomogeneous random graphs
• Global testing against sparse alternatives under Ising models
• Concentration inequalities for polynomials of contracting Ising models
• Modified log-Sobolev inequalities, Beckner inequalities and moment estimates
• The minimax learning rates of normal and Ising undirected graphical models
• Higher order concentration for functions of weakly dependent random variables
• Stein's method for stationary distributions of Markov chains and application to Ising models
• Property testing in high-dimensional Ising models
• A note on concentration for polynomials in the Ising model
• Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
• Predictive learning on hidden tree-structured Ising models
• High-temperature structure detection in ferromagnets
• Hardness of identity testing for restricted Boltzmann machines and Potts models
• Exact Goodness‐of‐Fit Testing for the Ising Model
• One-shot learning for k-SAT
• Sample efficient identity testing and independence testing of quantum states

This page was built for publication: Testing Ising models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608021)