The minimax learning rates of normal and Ising undirected graphical models

DOI10.1214/20-EJS1721zbMATH Open1445.62069arXiv1806.06887OpenAlexW3037947134MaRDI QIDQ2192304FDOQ2192304

Authors: Abbas Mehrabian, Tommy Reddad, Luc Devroye 

Publication date: 17 August 2020

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Introduction to nonparametric estimation
• Asymptotic methods in statistical decision theory
• Title not available (Why is that?)
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Convergence of estimates under dimensionality restrictions
• Understanding Machine Learning
• Testing Ising Models
• On the learnability of discrete distributions
• Title not available (Why is that?)
• Mean Field Models for Spin Glasses
• Combinatorial methods in density estimation
• Central limit theorems for empirical measures
• Mean field models for spin glasses. Volume I: Basic examples.
• Efficiently learning mixtures of two Gaussians
• Rigorous results on the bipartite mean-field model
• Handbook of linear algebra
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Estimation of analytic functions
• Complexity of random smooth functions on the high-dimensional sphere
• Title not available (Why is that?)
• Title not available (Why is that?)
• A note on L₁consistent estimation
• Efficiently Learning Ising Models on Arbitrary Graphs
• Information-Theoretic Limits of Selecting Binary Graphical Models in High Dimensions
• Exact recovery in the Ising blockmodel

Cited In (13)

• What scientific folklore knows about the distances between the most popular distributions
• 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
• Tensor recovery in high-dimensional Ising models
• Title not available (Why is that?)
• Learning polynomial transformations via generalized tensor decompositions
• Local exchangeability
• Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu
• 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
• Long lines in subsets of large measure in high dimension

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)