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

GraphL0: Sparse Gaussian Graphical Models with Discrete Optimization Recovering sparse dependency graphs in undirected Gaussian graphical models is a well-known problem in statistical machine learning. Given samples from a [Formula: see text]-dimensional Gaussian distribution, the task amounts to estimating the [Formula: see text] precision (inverse covariance) matrix under the assumption that only a small fraction of its entries are nonzero. In “Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives,” the authors introduce GraphL0. GraphL0 is an estimator based on an [Formula: see text]-penalized pseudo-likelihood, departing from the more common [Formula: see text] relaxation. The resulting formulation is a convex mixed-integer program, which becomes challenging for standard commercial solvers at moderate-to-large [Formula: see text]. To make the approach practical, the authors develop a custom nonlinear branch-and-bound algorithm, alongside scalable approximate solvers. The paper also provides new statistical guarantees for estimation accuracy and support recovery, and experiments on synthetic and real data sets show substantial computational gains over off-the-shelf solvers and competitive runtime and accuracy versus leading alternatives.