Download: pdf

Citation

• On Learning Discrete Graphical Models using Greedy Methods (pdf, software)
  A. Jalali, C. Johnson, P. Ravikumar.
  In Neural Information Processing Systems (NIPS), 2011.
  
  Bibtex:
  
  @inproceedings{jalali2011onlearnin, author = "Ali Jalali AND Christopher Johnson AND Pradeep Ravikumar", title = "On Learning Discrete Graphical Models using Greedy Methods", booktitle = "Neural Information Processing Systems (NIPS)", volume = "24", year = "2011", 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." }