# Outlier-Robust Learning of Ising Models Under Dobrushin's Condition

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 60 references that are in the map.
- First posted on arXiv 3 Feb 2021.

## Builds on (most cited first, 27 of 27)

- [Spectral Signatures in Backdoor Attacks](https://mlsanity.com/paper/1811.00636/) (2018)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Robust Estimation via Robust Gradient Estimation](https://mlsanity.com/paper/1802.06485/) (2018)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014)
- [Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers](https://mlsanity.com/paper/1703.04940/) (2017)
- [Learning Graphical Models Using Multiplicative Weights](https://mlsanity.com/paper/1706.06274/) (2017)
- [Moving Beyond Sub-Gaussianity in High-Dimensional Statistics: Applications in Covariance Estimation and Linear Regression](https://mlsanity.com/paper/1804.02605/) (2018)
- [Settling the Robust Learnability of Mixtures of Gaussians](https://mlsanity.com/paper/2011.03622/) (2020)
- [Faster Algorithms for High-Dimensional Robust Covariance Estimation](https://mlsanity.com/paper/1906.04661/) (2019)
- [Robustly Learning any Clusterable Mixture of Gaussians](https://mlsanity.com/paper/2005.06417/) (2020)
- [Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering](https://mlsanity.com/paper/1911.08085/) (2019)
- [Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications](https://mlsanity.com/paper/1705.11107/) (2017)
- [Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu](https://mlsanity.com/paper/2011.04144/) (2020)
- [Outlier-Robust Clustering of Non-Spherical Mixtures](https://mlsanity.com/paper/2005.02970/) (2020)
- [Structure learning of antiferromagnetic Ising models](https://mlsanity.com/paper/1412.1443/) (2014)
- [Robust Learning of Fixed-Structure Bayesian Networks](https://mlsanity.com/paper/1606.07384/) (2016)
- [Learning Ising Models with Independent Failures](https://mlsanity.com/paper/1902.04728/) (2019)
- [Robust Estimation of Tree Structured Ising Models](https://mlsanity.com/paper/2006.05601/) (2020)
- [Sample-Optimal and Efficient Learning of Tree Ising models](https://mlsanity.com/paper/2010.14864/) (2020)
- [Concentration of Multilinear Functions of the Ising Model with Applications to Network Data](https://mlsanity.com/paper/1710.04170/) (2017)
- [Learning Ising models from one or multiple samples](https://mlsanity.com/paper/2004.09370/) (2020)

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

- [Is Out-of-Distribution Detection Learnable?](https://mlsanity.com/paper/2210.14707/) (2022)
- [Streaming Algorithms for High-Dimensional Robust Statistics](https://mlsanity.com/paper/2204.12399/) (2022)
- [A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width](https://mlsanity.com/paper/2311.09197/) (2023)
- [A Computationally Efficient Method for Learning Exponential Family Distributions](https://mlsanity.com/paper/2110.15397/) (2021)
- [Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models](https://mlsanity.com/paper/2106.03969/) (2021)
- [Learning Hard-Constrained Models with One Sample](https://mlsanity.com/paper/2311.03332/) (2023)
- [Trimmed Maximum Likelihood Estimation for Robust Learning in Generalized Linear Models](https://mlsanity.com/paper/2206.04777/) (2022)
- [Learning the Sherrington-Kirkpatrick Model Even at Low Temperature](https://mlsanity.com/paper/2411.11174/) (2024)
- [Dimension-Free Rates for Natural Policy Gradient in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2109.11692/) (2021)
- [Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models](https://mlsanity.com/paper/2206.04589/) (2022)
- [Learning Juntas under Markov Random Fields](https://mlsanity.com/paper/2506.00764/) (2025)
- [Learning and Covering Sums of Independent Random Variables with Unbounded Support](https://mlsanity.com/paper/2210.13313/) (2022)
- [On Computationally Efficient Learning of Exponential Family Distributions](https://mlsanity.com/paper/2309.06413/) (2023)
- [Learning the Inverse Temperature of Ising Models under Hard Constraints using One Sample](https://mlsanity.com/paper/2509.20993/) (2025)

## Abstract (arXiv)

We study the problem of learning Ising models satisfying Dobrushin's condition in the outlier-robust setting where a constant fraction of the samples are adversarially corrupted. Our main result is to provide the first computationally efficient robust learning algorithm for this problem with near-optimal error guarantees. Our algorithm can be seen as a special case of an algorithm for robustly learning a distribution from a general exponential family. To prove its correctness for Ising models, we establish new anti-concentration results for degree-2 polynomials of Ising models that may be of independent interest.