The Minimax Learning Rate of Normal and Ising Undirected Graphical Models

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 \(\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.