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

Kayhan Behdin, Wenyu Chen, Rahul MazumderarXiv 2023 · DOI · arXiv

Introduction

In high-dimensional data analysis, understanding the conditional independence structure between variables is a fundamental challenge. Gaussian Graphical Models (GGMs) provide a robust framework for this, where the presence or absence of an edge in a graph represents the conditional dependence between two nodes. Mathematically, this is reflected in the sparsity of the precision matrix (the inverse of the covariance matrix).

While $\ell_1$-regularization methods like the Graphical Lasso (GLASSO) have become the industry standard due to their convexity and computational ease, they serve only as proxies for the true objective: $\ell_0$ regularization. $\ell_0$ optimization directly penalizes the number of non-zero entries, leading to more interpretable models and superior statistical properties. However, $\ell_0$ optimization is NP-hard, and until recently, Mixed Integer Programming (MIP) approaches were limited to small-scale problems with approximately 100 variables. This paper introduces GraphL0BnB, a framework that scales discrete optimization for GGMs to 10,000 variables, effectively bridging the gap between statistical optimality and computational feasibility.

Methodology

The GraphL0BnB framework achieves its scalability through a combination of statistical reformulation and high-performance optimization engineering. The core of the approach rests on three pillars:

1. Pseudolikelihood Objective

Rather than optimizing the full Gaussian log-likelihood, which is computationally intensive, the authors utilize a pseudolikelihood approach. This involves decomposing the problem into a collection of conditional regressions for each variable. The authors provide theoretical justification that this approach maintains high statistical accuracy while significantly reducing the computational burden.

2. Perspective Reformulation

To improve the efficiency of the Branch-and-Bound (BnB) search, the authors apply a "perspective reformulation." This mathematical technique tightens the continuous relaxation of the discrete problem. By providing a tighter lower bound, the solver can prune sub-optimal branches of the search tree much earlier, preventing the exponential explosion of the search space.

3. Specialized Nonlinear Branch-and-Bound Solver

Moving away from general-purpose commercial solvers like Gurobi, the authors engineered a custom solver tailored to the specific structure of GGM objectives:

  • Node Solvers: Each node in the search tree is solved using specialized first-order methods, specifically Coordinate Descent with active sets.
  • Dual Bounds: A novel method for calculating dual bounds allows the solver to quickly identify and discard unpromising paths.
  • Primal Heuristics: Fast approximate algorithms are used to find high-quality feasible solutions early in the process, further accelerating the pruning process.

Statistical and Computational Performance

Scalability and Speed

GraphL0BnB represents a significant leap in performance. The framework successfully handled problems with $p=10,000$ variables—involving 50 million binary decision variables—in under an hour on standard hardware. Compared to CONCORD, a leading convex pseudolikelihood method, GraphL0BnB demonstrated a 4–5x speedup on medium-sized problems and continued to scale in scenarios where CONCORD failed to converge.

Support Recovery

In synthetic benchmarks (Uniform Sparsity and Banded Precision), GraphL0BnB consistently outperformed $\ell_1$ methods in support recovery. Using the Matthews Correlation Coefficient (MCC) as a metric, the $\ell_0$ approach proved more adept at identifying true edges while maintaining a lower false-positive rate. The authors also proved that their $\ell_0$ estimator is minimax optimal, meaning it achieves the best possible error rate with the minimum number of samples.

Real-World Application: Financial Portfolio Optimization

The model was tested on stock return data from Yahoo! Finance (2005–2019) for 1,452 companies. When used for portfolio optimization, the $\ell_0$-based precision matrix estimates resulted in portfolios with higher returns and superior risk-adjusted performance compared to those derived from GLASSO or CLIME. This suggests that the structural accuracy of $\ell_0$ models translates directly into better decision-making in downstream tasks.

Discussion and Limitations

While GraphL0BnB marks a milestone in discrete optimization, it is not without constraints. The formulation relies on a "Big-M" parameter to bound the entries of the precision matrix; selecting an appropriate $M$ remains a practical challenge. Additionally, the efficiency of the BnB solver is inherently tied to the assumption of sparsity. As the underlying graph becomes denser, the computational advantage of the discrete approach may diminish.

Future research directions include extending this framework to non-Gaussian distributions (e.g., Poisson or Binomial models) and developing methods for time-varying graphs to capture dynamic relationships in evolving datasets.

Summary updated

Abstract

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 \times 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 $\ell_0$-penalized version of the pseudo-likelihood function, while most earlier approaches are based on the $\ell_1$-relaxation. Our estimator can be formulated as a convex mixed integer program (MIP) which can be difficult to compute beyond $p\approx 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.
BibTeX
@misc{behdin2023sparse,
  author = {Kayhan Behdin and Wenyu Chen and Rahul Mazumder},
  title = {{Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives}},
  year = {2023},
  eprint = {2307.09366},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2307.09366},
}
Figure