The Minimax Learning Rates of Normal and Ising Undirected Graphical Models
This work provides foundational theoretical guarantees for statistical learning in graphical models, which is important for researchers in machine learning and statistics, though it is incremental in refining existing bounds.
The paper tackles the problem of learning undirected graphical models, specifically Ising and multivariate normal models, by establishing optimal minimax learning rates for expected total variation distance, with rates like min{1, sqrt((m+d)/n)} and proving their optimality.
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 $\min\{1, \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 $\min\{1, \sqrt{m/n}\}$ for Ising models with no external magnetic field.