On Learning Discrete Graphical Models using Greedy Methods

Ali Jalali, Chris Johnson, Pradeep Ravikumar

Abstract:   In this paper, we address the problem of learning the structure of a pairwise graphical model from samples in a high-dimensional setting. Our first main result studies the sparsistency, or consistency in sparsity pattern recovery, properties of a forward-backward greedy algorithm as applied to general statistical models. As a special case, we then apply this algorithm to learn the structure of a discrete graphical model via neighborhood estimation. As a corollary of our general result, we derive sufficient conditions on the number of samples n, the maximum nodedegree d and the problem size p, as well as other conditions on the model parameters, so that the algorithm recovers all the edges with high probability. Our result guaranteesgraphselectionforsamplesscalingasn=Ω(d^2 log(p)),incontrastto existing convex-optimization based algorithms that require a sample complexity of Ω(d^3 log(p)). Further, the greedy algorithm only requires a restricted strong convexity condition which is typically milder than irrepresentability assumptions. We corroborate these results using numerical simulations at the end.

Download: pdf


  • On Learning Discrete Graphical Models using Greedy Methods (pdf, software)
    A. Jalali, C. Johnson, P. Ravikumar.
    In Neural Information Processing Systems (NIPS), 2011.