# Certifiably Optimal Sparse Inverse Covariance Estimation

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jun 2019.

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

- [Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives](https://mlsanity.com/paper/2307.09366/) (2023)
- [Integer Programming for Learning Directed Acyclic Graphs from Non-identifiable Gaussian Models](https://mlsanity.com/paper/2404.12592/) (2024)
- [Solution Path of Time-varying Markov Random Fields with Discrete Regularization](https://mlsanity.com/paper/2307.13750/) (2023)
- [Inverse Covariance and Partial Correlation Matrix Estimation via Joint Partial Regression](https://mlsanity.com/paper/2502.08414/) (2025)

## Abstract (arXiv)

We consider the maximum likelihood estimation of sparse inverse covariance matrices. We demonstrate that current heuristic approaches primarily encourage robustness, instead of the desired sparsity. We give a novel approach that solves the cardinality constrained likelihood problem to certifiable optimality. The approach uses techniques from mixed-integer optimization and convex optimization, and provides a high-quality solution with a guarantee on its suboptimality, even if the algorithm is terminated early. Using a variety of synthetic and real datasets, we demonstrate that our approach can solve problems where the dimension of the inverse covariance matrix is up to 1,000s. We also demonstrate that our approach produces significantly sparser solutions than Glasso and other popular learning procedures, makes less false discoveries, while still maintaining state-of-the-art accuracy.