Outlier-Robust Learning of Ising Models Under Dobrushin's Condition
arXiv:2102.02171
Abstract
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- polynomials of Ising models that may be of independent interest.
References in corpus (10)
- Sever: A Robust Meta-Algorithm for Stochastic Optimization
- Recent Advances in Algorithmic High-Dimensional Robust Statistics
- Moving Beyond Sub-Gaussianity in High-Dimensional Statistics: Applications in Covariance Estimation and Linear Regression
- Higher order concentration for functions of weakly dependent random variables
- Outlier-Robust Clustering of Non-Spherical Mixtures
- Logarithmic Sobolev inequalities in discrete product spaces: a proof by a transportation cost distance
- Structure learning of antiferromagnetic Ising models
- Robust Estimation of Tree Structured Ising Models
- Settling the Robust Learnability of Mixtures of Gaussians
- Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu