Learning Ising Models with Independent Failures

2019/02/13 by Surbhi Goel, Daniel M. Kane, Goel, Surbhi +3 · 2 citations
Computer Science · Mathematics · #Bayesian Modeling and Causal Inference #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.1902.04728

openalex publication_date 2019/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give the first efficient algorithm for learning the structure of an Ising model that tolerates independent failures; that is, each entry of the observed sample is missing with some unknown probability p. Our algorithm matches the essentially optimal runtime and sample complexity bounds of recent work for learning Ising models due to Klivans and Meka (2017). We devise a novel unbiased estimator for the gradient of the Interaction Screening Objective (ISO) due to Vuffray et al. (2016) and apply a stochastic multiplicative gradient descent algorithm to minimize this objective. Solutions to this minimization recover the neighborhood information of the underlying Ising model on a node by node basis.

Citations

• Information Theoretic Properties of Markov Random Fields, and their\n Algorithmic Applications

Cited by

• Robust Estimation for Dependent Binary Network Data
• Learning Juntas under Markov Random Fields

Related

• A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width
• Learning Ising models from one or multiple samples
• Efficiently learning Ising models on arbitrary graphs
• Better Models and Algorithms for Learning Ising Models from Dynamics
• Which graphical models are difficult to learn?