Learning Some Popular Gaussian Graphical Models without Condition Number Bounds

Abstract

Gaussian Graphical Models (GGMs) have wide-ranging applications in machine learning and the natural and social sciences. In most of the settings in which they are applied, the number of observed samples is much smaller than the dimension and they are assumed to be sparse. While there are a variety of algorithms (e.g. Graphical Lasso, CLIME) that provably recover the graph structure with a logarithmic number of samples, they assume various conditions that require the precision matrix to be in some sense well-conditioned. Here we give the first polynomial-time algorithms for learning attractive GGMs and walk-summable GGMs with a logarithmic number of samples without any such assumptions. In particular, our algorithms can tolerate strong dependencies among the variables. Our result for structure recovery in walk-summable GGMs is derived from a more general result for efficient sparse linear regression in walk-summable models without any norm dependencies. We complement our results with experiments showing that many existing algorithms fail even in some simple settings where there are long dependency chains, whereas ours do not.

arXiv commentV2: Updated version with some new results

References in corpus (10)

• Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
• Brain covariance selection: better individual functional connectivity models using population prior
• Lower bounds on the performance of polynomial-time algorithms for sparse linear regression
• Random design analysis of ridge regression
• High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion
• Adaptive Lasso for High Dimensional Regression and Gaussian Graphical Modeling
• Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models
• Learning without Concentration
• Information Theoretic Optimal Learning of Gaussian Graphical Models
• Subset Selection for Gaussian Markov Random Fields

Cited by in corpus (5)

• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
• Sample-Optimal and Efficient Learning of Tree Ising models
• On Learning Continuous Pairwise Markov Random Fields
• Learning Gaussian Graphical Models via Multiplicative Weights
• A Computationally Efficient Method for Learning Exponential Family Distributions