Outlier-Robust Learning of Ising Models Under Dobrushin's Condition
This work provides a robust learning solution for Ising models, which are fundamental in statistical physics and machine learning, for researchers and practitioners dealing with noisy or adversarial data.
This paper addresses the challenge of learning Ising models under Dobrushin's condition when a constant fraction of samples are corrupted by adversaries. The authors present the first computationally efficient robust learning algorithm for this problem, achieving near-optimal error guarantees.
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.