Sparse Inverse Covariance Estimation via an Adaptive Gradient-Based Method

Suvrit Sra, Dong‐Min KimarXiv 2011 · DOI · arXiv

Abstract

We study the problem of estimating from data a sparse approximation to the inverse covariance matrix. Estimating a sparsity-constrained inverse covariance matrix is a key component in Gaussian graphical model learning, but one that is numerically very challenging. We address this challenge by developing a new adaptive gradient-based method that carefully combines gradient information with an adaptive step-scaling strategy, resulting in a scalable, highly competitive method. Our algorithm, like its predecessors, maximizes an $\ell_1$-norm penalized log-likelihood and has the same per-iteration arithmetic complexity as the best methods in its class. Our experiments reveal that our approach outperforms state-of-the-art competitors, often significantly so, for large problems.

Introduction

In fields ranging from bioinformatics to signal processing, Gaussian Markov Random Fields (GMRFs) are essential for modeling dependencies between variables. The core challenge in learning these models is identifying the underlying graph structure—specifically, determining which variables are conditionally independent. Mathematically, this is equivalent to identifying zeros in the inverse covariance matrix (the precision matrix).

To find a parsimonious model, researchers typically solve an optimization problem that maximizes the log-likelihood of the observed data while applying an $\ell_1$-norm penalty to encourage sparsity. However, this approach faces two significant hurdles: the non-smoothness of the $\ell_1$ penalty and the requirement that the estimated matrix remains positive-definite. The latter is particularly taxing, as traditional methods require frequent, expensive matrix decompositions that do not scale well with high-dimensional data.

The SICE Framework

The Sparse Inverse Covariance Estimation (SICE) algorithm is an adaptive gradient-based method designed to overcome these computational bottlenecks. By operating on the dual formulation of the optimization problem, SICE transforms the objective into a differentiable function subject to simple box constraints. The efficiency of SICE is driven by three primary innovations:

1. Modified Barzilai-Borwein (MBB) Steps

The Barzilai-Borwein method is a well-regarded technique for choosing step sizes in unconstrained optimization. SICE adapts this for constrained problems by incorporating an active-set strategy. By identifying "binding" variables—those likely to be zero at the optimum—the algorithm focuses its computational resources on the reduced subspace of active variables, significantly accelerating convergence.

2. Optimistic Diminishing Scalars

Rather than performing a computationally expensive line search at every iteration to ensure improvement, SICE utilizes an "optimistic" scaling factor. This factor diminishes over time but is only adjusted if a descent condition fails after a block of $M$ iterations. This heuristic prevents the algorithm from becoming overly cautious, allowing for larger steps when progress is steady.

3. Checkpointing for Positive-Definiteness

Enforcing the positive-definite constraint is typically the most expensive part of the estimation process. SICE employs a "lazy" enforcement strategy, checking for positive-definiteness only at specific checkpoints rather than at every iteration. Because intermediate steps often naturally remain within the valid region, this approach drastically reduces the frequency of costly eigenvalue calculations without sacrificing the validity of the final estimate.

Experimental Evaluation

The performance of SICE was evaluated using synthetic datasets designed to mimic high-dimensional, real-world challenges. These benchmarks included sparse random matrices ranging in size from $100 \times 100$ to $1000 \times 1000$, perturbed with noise to test robustness.

Key Results

  • Superior Scalability: In tests on $1000 \times 1000$ matrices, SICE reached a high-accuracy solution (a duality gap of $10^{-4}$) in just 234 seconds. In contrast, the Projected Gradient (PG) method required 1,405 seconds, while other state-of-the-art methods exceeded 9,000 seconds.
  • High-Precision Dominance: SICE is particularly effective when high precision is required. While competing methods often find coarse solutions quickly, their convergence rates stall as they approach the optimum. SICE maintains a consistent pace, even at very tight tolerances.
  • Computational Efficiency: Despite its speed, SICE maintains an $O(n^3)$ per-iteration arithmetic complexity, the same as its most efficient competitors. Its performance edge stems from superior algorithmic design and heuristic efficiency rather than increased raw computational requirements.

Conclusion

SICE provides a highly efficient path for learning the structure of Gaussian Markov Random Fields. By combining subspace optimization with clever constraint enforcement, it offers a scalable solution for large-scale precision matrix estimation. Future work may further enhance the algorithm through parallelization and the development of techniques to bypass explicit matrix inversions entirely, potentially reducing the $O(n^3)$ cost further.

Summary updated

Abstract

We study the problem of estimating from data, a sparse approximation to the inverse covariance matrix. Estimating a sparsity constrained inverse covariance matrix is a key component in Gaussian graphical model learning, but one that is numerically very challenging. We address this challenge by developing a new adaptive gradient-based method that carefully combines gradient information with an adaptive step-scaling strategy, which results in a scalable, highly competitive method. Our algorithm, like its predecessors, maximizes an $\ell_1$-norm penalized log-likelihood and has the same per iteration arithmetic complexity as the best methods in its class. Our experiments reveal that our approach outperforms state-of-the-art competitors, often significantly so, for large problems.
BibTeX
@misc{sra2011sparse,
  author = {Suvrit Sra and Dong‐Min Kim},
  title = {{Sparse Inverse Covariance Estimation via an Adaptive Gradient-Based Method}},
  year = {2011},
  eprint = {1106.5175},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1106.5175},
}
Figure