On Learning Discrete Graphical Models Using Greedy Methods

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 node-degree 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 guarantees graph selection for samples scaling as n = Omega(d^2 log(p)), in contrast to 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.

References in corpus (2)

• High-dimensional Ising model selection using ${\ell }_1$-regularized logistic regression
• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers

Cited by in corpus (19)

• Non-convex Optimization for Machine Learning
• Role Discovery in Networks
• Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization
• Forward-Backward Greedy Algorithms for General Convex Smooth Functions over A Cardinality Constraint
• High-dimensional Sparse Inverse Covariance Estimation using Greedy Methods
• Learning loopy graphical models with latent variables: Efficient methods and guarantees
• Gradient Projection Newton Algorithm for Sparse Collaborative Learning Using Synthetic and Real Datasets of Applications
• Causal Inference Under Interference And Network Uncertainty
• Structure learning of antiferromagnetic Ising models
• Global and Quadratic Convergence of Newton Hard-Thresholding Pursuit
• Federated Nonconvex Sparse Learning
• Convergence Rates of Biased Stochastic Optimization for Learning Sparse Ising Models
• Privately Learning Markov Random Fields
• Predictive Learning on Hidden Tree-Structured Ising Models
• Statistical Inference in the Differential Privacy Model
• Learning Gaussian Graphical Models via Multiplicative Weights
• A New Greedy Algorithm for Multiple Sparse Regression
• Learning pairwise Markov network structures using correlation neighborhoods
• Approximation Guarantees of Local Search Algorithms via Localizability of Set Functions