# Learning Some Popular Gaussian Graphical Models without Condition Number Bounds

arXiv: https://arxiv.org/abs/1905.01282 · HTML: https://mlsanity.com/paper/1905.01282/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 May 2019.

## Built on by (most cited first, 20 of 20)

- [Statistical Efficiency of Score Matching: The View from Isoperimetry](https://mlsanity.com/paper/2210.00726/) (2022)
- [A New Approach to Learning Linear Dynamical Systems](https://mlsanity.com/paper/2301.09519/) (2023)
- [On the Power of Preconditioning in Sparse Linear Regression](https://mlsanity.com/paper/2106.09207/) (2021)
- [A Computationally Efficient Method for Learning Exponential Family Distributions](https://mlsanity.com/paper/2110.15397/) (2021)
- [Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models](https://mlsanity.com/paper/2106.03969/) (2021)
- [Fast Projected Newton-like Method for Precision Matrix Estimation under Total Positivity](https://mlsanity.com/paper/2112.01939/) (2021)
- [Learning Continuous Exponential Families Beyond Gaussian](https://mlsanity.com/paper/2102.09198/) (2021)
- [Feature Adaptation for Sparse Linear Regression](https://mlsanity.com/paper/2305.16892/) (2023)
- [Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps](https://mlsanity.com/paper/2402.15409/) (2024)
- [BUILD with Precision: Bottom-Up Inference of Linear DAGs](https://mlsanity.com/paper/2512.16111/) (2025)
- [Learning Gaussian DAG Models without Condition Number Bounds](https://mlsanity.com/paper/2511.06164/) (2025)
- [Learning with latent group sparsity via heat flow dynamics on networks](https://mlsanity.com/paper/2201.08326/) (2022)
- [Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs](https://mlsanity.com/paper/2203.02824/) (2022)
- [On Computationally Efficient Learning of Exponential Family Distributions](https://mlsanity.com/paper/2309.06413/) (2023)
- [Efficient Hamiltonian, structure and trace distance learning of Gaussian states](https://mlsanity.com/paper/2411.03163/) (2024)
- [Graph Regularized PCA](https://mlsanity.com/paper/2601.10199/) (2026)
- [Learning Networks from Gaussian Graphical Models and Gaussian Free Fields](https://mlsanity.com/paper/2308.02344/) (2023)
- [Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Information](https://mlsanity.com/paper/2411.11516/) (2024)
- [Learning under Latent Group Sparsity via Diffusion on Networks](https://mlsanity.com/paper/2507.15097/) (2025)
- [Sparse Linear Regression is Easy on Random Supports](https://mlsanity.com/paper/2511.06211/) (2025)

## Abstract (arXiv)

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.