The Minimax Learning Rates of Normal and Ising Undirected Graphical\n Models

2018/06/18 by Luc Devroye, Devroye, Luc, Abbas Mehrabian +3 · 2 citations
Computer Science · Mathematics · #62G07 #82B20 #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and Algorithms #Statistical Methods and Inference #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.1806.06887

openalex publication_date 2018/06/18 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28

Abstract

Let G be an undirected graph with m edges and d vertices. We show that\nd-dimensional Ising models on G can be learned from n i.i.d. samples\nwithin expected total variation distance some constant factor of \min 1,\n\√((m + d)/n) , and that this rate is optimal. We show that the same rate\nholds for the class of d-dimensional multivariate normal undirected graphical\nmodels with respect to G. We also identify the optimal rate of \min 1,\n\√(m/n) for Ising models with no external magnetic field.\n

Cited by

• Estimating Ising Models in Total Variation Distance
• Robust Learnability of Sample-Compressible Distributions under Noisy or Adversarial Perturbations

Related

• Sample-Optimal and Efficient Learning of Tree Ising models
• Structure learning of antiferromagnetic Ising models
• On the Information Theoretic Limits of Learning Ising Models
• Efficiently learning Ising models on arbitrary graphs
• Learning Graphical Models Using Multiplicative Weights