Property testing in high-dimensional Ising models
From MaRDI portal
Publication:2328049
DOI10.1214/18-AOS1754zbMATH Open1432.62039arXiv1709.06688MaRDI QIDQ2328049FDOQ2328049
Authors: Matey Neykov, Han Liu 
Publication date: 9 October 2019
Published in: The Annals of Statistics (Search for Journal in Brave)
Abstract: This paper explores the information-theoretic limitations of graph property testing in zero-field Ising models. Instead of learning the entire graph structure, sometimes testing a basic graph property such as connectivity, cycle presence or maximum clique size is a more relevant and attainable objective. Since property testing is more fundamental than graph recovery, any necessary conditions for property testing imply corresponding conditions for graph recovery, while custom property tests can be statistically and/or computationally more efficient than graph recovery based algorithms. Understanding the statistical complexity of property testing requires the distinction of ferromagnetic (i.e., positive interactions only) and general Ising models. Using combinatorial constructs such as graph packing and strong monotonicity, we characterize how target properties affect the corresponding minimax upper and lower bounds within the realm of ferromagnets. On the other hand, by studying the detection of an antiferromagnetic (i.e., negative interactions only) Curie-Weiss model buried in Rademacher noise, we show that property testing is strictly more challenging over general Ising models. In terms of methodological development, we propose two types of correlation based tests: computationally efficient screening for ferromagnets, and score type tests for general models, including a fast cycle presence test. Our correlation screening tests match the information-theoretic bounds for property testing in ferromagnets.
Full work available at URL: https://arxiv.org/abs/1709.06688
Recommendations
Parametric hypothesis testing (62F03) Hypothesis testing in multivariate analysis (62H15) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)
Cites Work
- High-dimensional graphs and variable selection with the Lasso
- The nonparanormal: semiparametric estimation of high dimensional undirected graphs
- Sparse permutation invariant covariance estimation
- Model selection and estimation in the Gaussian graphical model
- Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
- Approximating discrete probability distributions with dependence trees
- High-dimensional Ising model selection using \(\ell _{1}\)-regularized logistic regression
- High-dimensional structure estimation in Ising models: local separation criterion
- High-dimensional covariance estimation by minimizing \(\ell _{1}\)-penalized log-determinant divergence
- A constrained \(\ell _{1}\) minimization approach to sparse precision matrix estimation
- Detecting positive correlations in a multivariate sample
- Testing Ising models
- On combinatorial testing problems
- Beitrag zur Theorie des Ferromagnetismus
- Title not available (Why is that?)
- Title not available (Why is that?)
- Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms
- Detection of correlations
- Probability on graphs. Random processes on graphs and lattices.
- Concentration inequalities for polynomials of contracting Ising models
- Inference in Ising models
- Efficiently learning Ising models on arbitrary graphs (extended abstract)
- Combinatorial inference for graphical models
- Detecting Markov random fields hidden in white noise
- Information-Theoretic Limits of Selecting Binary Graphical Models in High Dimensions
- Global testing against sparse alternatives under Ising models
- Exact recovery in the Ising blockmodel
- Property testing in high-dimensional Ising models
- Curie–Weiss magnet—a simple model of phase transition
Cited In (9)
- Exact Goodness‐of‐Fit Testing for the Ising Model
- Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
- Testing Ising models
- Tensor recovery in high-dimensional Ising models
- Efficient estimation in tensor Curie-Weiss and Erdős-Rényi Ising models
- Global testing against sparse alternatives under Ising models
- High-temperature structure detection in ferromagnets
- On testing for parameters in Ising models
- Property testing in high-dimensional Ising models
This page was built for publication: Property testing in high-dimensional Ising models
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2328049)
