# Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 48 references that are in the map.
- First posted on arXiv 18 Jul 2023.

## Builds on (most cited first, 14 of 14)

- [Interactive Supercomputing on 40,000 Cores for Machine Learning and Data Analysis](https://mlsanity.com/paper/1807.07814/) (2018)
- [Best Subset Selection via a Modern Optimization Lens](https://mlsanity.com/paper/1507.03133/) (2015)
- [Fast Best Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms](https://mlsanity.com/paper/1803.01454/) (2018)
- [Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization](https://mlsanity.com/paper/2004.06152/) (2020)
- [Sparse High-Dimensional Regression: Exact Scalable Algorithms and Phase Transitions](https://mlsanity.com/paper/1709.10029/) (2017)
- [Iteration Complexity Analysis of Block Coordinate Descent Methods](https://mlsanity.com/paper/1310.6957/) (2013)
- [Subset Selection with Shrinkage: Sparse Linear Modeling when the SNR is low](https://mlsanity.com/paper/1708.03288/) (2017)
- [Regularization vs. Relaxation: A conic optimization perspective of statistical variable selection](https://mlsanity.com/paper/1510.06083/) (2015)
- [A convex pseudo-likelihood framework for high dimensional partial correlation estimation with convergence guarantees](https://mlsanity.com/paper/1307.5381/) (2013)
- [Using L1-relaxation and integer programming to obtain dual bounds for sparse PCA](https://mlsanity.com/paper/1810.09062/) (2018)
- [Best subset selection is robust against design dependence](https://mlsanity.com/paper/2007.01478/) (2020)
- [Certifiably Optimal Sparse Inverse Covariance Estimation](https://mlsanity.com/paper/1906.10283/) (2019)
- [Sparse PCA: A New Scalable Estimator Based On Integer Programming](https://mlsanity.com/paper/2109.11142/) (2021)
- [Scalable Inference of Sparsely-changing Markov Random Fields with Strong Statistical Guarantees](https://mlsanity.com/paper/2102.03585/) (2021)

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

- [QuantEase: Optimization-based Quantization for Language Models](https://mlsanity.com/paper/2309.01885/) (2023)
- [Integer Programming for Learning Directed Acyclic Graphs from Non-identifiable Gaussian Models](https://mlsanity.com/paper/2404.12592/) (2024)
- [An Asymptotically Optimal Coordinate Descent Algorithm for Learning Bayesian Networks from Gaussian Models](https://mlsanity.com/paper/2408.11977/) (2024)
- [Probabilistic Iterative Hard Thresholding for Sparse Learning](https://mlsanity.com/paper/2409.01413/) (2024)
- [Inverse Covariance and Partial Correlation Matrix Estimation via Joint Partial Regression](https://mlsanity.com/paper/2502.08414/) (2025)

## Abstract (arXiv)

We consider the problem of learning a sparse graph underlying an undirected Gaussian graphical model, a key problem in statistical machine learning. Given n samples from a multivariate Gaussian distribution with p variables, the goal is to estimate the p × p inverse covariance matrix (aka precision matrix), assuming it is sparse (i.e., has a few nonzero entries). We propose GraphL0BnB, a new estimator based on an ℓ0-penalized version of the pseudo-likelihood function, while most earlier approaches are based on the ℓ1-relaxation. Our estimator can be formulated as a convex mixed integer program (MIP) which can be difficult to compute beyond p≈ 100 using off-the-shelf commercial solvers. To solve the MIP, we propose a custom nonlinear branch-and-bound (BnB) framework that solves node relaxations with tailored first-order methods. As a key component of our BnB framework, we propose large-scale solvers for obtaining good primal solutions that are of independent interest. We derive novel statistical guarantees (estimation and variable selection) for our estimator and discuss how our approach improves upon existing estimators. Our numerical experiments on real and synthetic datasets suggest that our BnB framework offers significant advantages over off-the-shelf commercial solvers, and our approach has favorable performance (both in terms of runtime and statistical performance) compared to the state-of-the-art approaches for learning sparse graphical models.