Learning Ising Models with Independent Failures

Understand

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.