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.
- On Learning Discrete Graphical Models using Greedy Methods (pdf, software)
A. Jalali, C. Johnson, P. Ravikumar.
In Neural Information Processing Systems (NIPS), 2011.