# The Minimax Learning Rates of Normal and Ising Undirected Graphical Models

arXiv: https://arxiv.org/abs/1806.06887 · HTML: https://mlsanity.com/paper/1806.06887/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jun 2018.

## Built on by (most cited first, 11 of 11)

- [A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width](https://mlsanity.com/paper/2311.09197/) (2023)
- [User-Level Differential Privacy With Few Examples Per User](https://mlsanity.com/paper/2309.12500/) (2023)
- [Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models](https://mlsanity.com/paper/2106.03969/) (2021)
- [Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics](https://mlsanity.com/paper/2409.05284/) (2024)
- [Learning and Testing Latent-Tree Ising Models Efficiently](https://mlsanity.com/paper/2211.13291/) (2022)
- [Learning finitely correlated states: stability of the spectral reconstruction](https://mlsanity.com/paper/2312.07516/) (2023)
- [Estimating Ising Models in Total Variation Distance](https://mlsanity.com/paper/2511.21008/) (2025)
- [Privately Estimating a Gaussian: Efficient, Robust and Optimal](https://mlsanity.com/paper/2212.08018/) (2022)
- [Interaction Screening and Pseudolikelihood Approaches for Tensor Learning in Ising Models](https://mlsanity.com/paper/2310.13232/) (2023)
- [Robust Learnability of Sample-Compressible Distributions under Noisy or Adversarial Perturbations](https://mlsanity.com/paper/2506.06613/) (2025)
- [Information-Theoretic Bounds for Sparse Covariance Estimation in the Vertical-Split Distributed Model](https://mlsanity.com/paper/2606.07124/) (2026)

## Abstract (arXiv)

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, √(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, √m/n for Ising models with no external magnetic field.