mlsanityData to 7 Oct 2026

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

arXiv 2102.02171 ↗First posted 3 Feb 2021cs.LG cs.DS math.PRcited by 14

Not on the map. Why?

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.

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

Builds on

27 of 60 references.

References · 27

  1. 2018Spectral Signatures in Backdoor Attackscited by 457
  2. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  3. 2016Agnostic Estimation of Mean and Covariancecited by 131
  4. 2018Sever: A Robust Meta-Algorithm for Stochastic Optimizationcited by 123
  5. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 100
  6. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  7. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  8. 2018Robust Estimation via Robust Gradient Estimationcited by 76
  9. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
  10. 2014Efficiently learning Ising models on arbitrary graphscited by 50
  11. 2017Resilience: A Criterion for Learning in the Presence of Arbitrary Outlierscited by 43
  12. 2017Learning Graphical Models Using Multiplicative Weightscited by 43
15 more
  1. 2018Moving Beyond Sub-Gaussianity in High-Dimensional Statistics: Applications in Covariance Estimation and Linear Regressioncited by 42
  2. 2020Settling the Robust Learnability of Mixtures of Gaussianscited by 32
  3. 2019Faster Algorithms for High-Dimensional Robust Covariance Estimationcited by 28
  4. 2020Robustly Learning any Clusterable Mixture of Gaussianscited by 28
  5. 2019Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filteringcited by 23
  6. 2017Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applicationscited by 21
  7. 2020Near-Optimal Learning of Tree-Structured Distributions by Chow-Liucited by 20
  8. 2020Outlier-Robust Clustering of Non-Spherical Mixturescited by 19
  9. 2014Structure learning of antiferromagnetic Ising modelscited by 8
  10. 2016Robust Learning of Fixed-Structure Bayesian Networkscited by 8
  11. 2019Learning Ising Models with Independent Failurescited by 8
  12. 2020Robust Estimation of Tree Structured Ising Modelscited by 7
  13. 2020Sample-Optimal and Efficient Learning of Tree Ising modelscited by 6
  14. 2017Concentration of Multilinear Functions of the Ising Model with Applications to Network Datacited by 5
  15. 2020Learning Ising models from one or multiple samplescited by 3

Built on by

Cited by year

Citing papers per year: 2021: 3; 2022: 5; 2023: 3; 2024: 1; 2025: 2.

14 papers.

Sort:

  1. 2022Is Out-of-Distribution Detection Learnable?cited by 109
  2. 2022Streaming Algorithms for High-Dimensional Robust Statisticscited by 21
  3. 2023A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Widthcited by 13
  4. 2021A Computationally Efficient Method for Learning Exponential Family Distributionscited by 10
  5. 2021Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Modelscited by 9
  6. 2023Learning Hard-Constrained Models with One Samplecited by 7
  7. 2022Trimmed Maximum Likelihood Estimation for Robust Learning in Generalized Linear Modelscited by 6
  8. 2024Learning the Sherrington-Kirkpatrick Model Even at Low Temperaturecited by 5
  9. 2021Dimension-Free Rates for Natural Policy Gradient in Multi-Agent Reinforcement Learningcited by 4
  10. 2022Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Modelscited by 4
  11. 2022Learning and Covering Sums of Independent Random Variables with Unbounded Supportcited by 2
  12. 2023On Computationally Efficient Learning of Exponential Family Distributionscited by 2
2 more
  1. 2025Learning Juntas under Markov Random Fieldscited by 2
  2. 2025Learning the Inverse Temperature of Ising Models under Hard Constraints using One Samplecited by 1