Learning Ising Models with Independent Failures

[edit]

Surbhi Goel, Daniel M. Kane, Adam R. Klivans ;
Proceedings of the Thirty-Second Conference on Learning Theory, PMLR 99:1449-1469, 2019.

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.

Related Material