The minimax learning rates of normal and Ising undirected graphical models

DOI10.1214/20-EJS1721zbMATHOpenAlexMaRDI QIDQ2192304FDO

Authors Abbas Mehrabian, Tommy Reddad, Luc Devroye

Publication date 17 August 2020

Published in Electronic Journal of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.06887

zbMATH Keywords

density estimationgraphical modelIsing modelmultivariate normalMarkov random fieldFano's lemmadistribution learning

Mathematics Subject Classification ID

Density estimation (62G07) Applications of graph theory (05C90) Probabilistic graphical models (62H22) Minimax procedures in statistical decision theory (62C20) Applications of statistics to physics (62P35) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Abstract: Let $G$ be an undirected graph with $m$ edges and $d$ vertices. We show that $d$-dimensional Ising models on $G$ can be learned from $n$ i.i.d. samples within expected total variation distance some constant factor of $min1,sqrt(m+d)/n$, and that this rate is optimal. We show that the same rate holds for the class of $d$-dimensional multivariate normal undirected graphical models with respect to $G$. We also identify the optimal rate of $min1,sqrtm/n$ for Ising models with no external magnetic field.

Recommendations

• Efficiently learning Ising models on arbitrary graphs (extended abstract)
• Learning planar Ising models
• Learning a tree-structured Ising model in order to make predictions
• Learning factor graphs in polynomial time and sample complexity
• Learning loosely connected Markov random fields

Cites work

• scientific article; zbMATH DE number 3133919 (Why is no real title available?)
• scientific article; zbMATH DE number 3870398 (Why is no real title available?)
• scientific article; zbMATH DE number 3907540 (Why is no real title available?)
• scientific article; zbMATH DE number 4021509 (Why is no real title available?)
• scientific article; zbMATH DE number 3656965 (Why is no real title available?)
• scientific article; zbMATH DE number 1149166 (Why is no real title available?)
• scientific article; zbMATH DE number 1952026 (Why is no real title available?)
• scientific article; zbMATH DE number 4001210 (Why is no real title available?)
• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• A note on L₁consistent estimation
• Asymptotic methods in statistical decision theory
• Central limit theorems for empirical measures
• Combinatorial methods in density estimation
• Complexity of random smooth functions on the high-dimensional sphere
• Concentration inequalities. A nonasymptotic theory of independence
• Convergence of estimates under dimensionality restrictions
• Deep learning
• Efficiently learning Ising models on arbitrary graphs (extended abstract)
• Efficiently learning mixtures of two Gaussians
• Estimation of analytic functions
• Exact recovery in the Ising blockmodel
• Handbook of linear algebra
• Information-Theoretic Limits of Selecting Binary Graphical Models in High Dimensions
• Introduction to nonparametric estimation
• Mean Field Models for Spin Glasses
• Mean field models for spin glasses. Volume I: Basic examples.
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the learnability of discrete distributions
• Rigorous results on the bipartite mean-field model
• Testing Ising models
• Understanding machine learning. From theory to algorithms

Cited in

(16)

• Learning planar Ising models
• Learning polynomial transformations via generalized tensor decompositions
• What scientific folklore knows about the distances between the most popular distributions
• Learning a tree-structured Ising model in order to make predictions
• The role of mutual information in variational classifiers
• Real roots near the unit circle of random polynomials
• A note on concentration for polynomials in the Ising model
• Parameter estimation for SPDEs based on discrete observations in time and space
• Local exchangeability
• Efficiently learning Ising models on arbitrary graphs (extended abstract)
• Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu
• Tensor recovery in high-dimensional Ising models
• Long lines in subsets of large measure in high dimension
• scientific article; zbMATH DE number 7626800 (Why is no real title available?)
• Posterior-based Wald-type statistics for hypothesis testing
• Simple and optimal methods for stochastic variational inequalities. II: Markovian noise and policy evaluation in reinforcement learning

This page was built for publication: The minimax learning rates of normal and Ising undirected graphical models

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