Certifiably Optimal Sparse Inverse Covariance Estimation

Abstract

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.

References in corpus (12)

• Nearly unbiased variable selection under minimax concave penalty
• High-dimensional graphs and variable selection with the Lasso
• Challenges of Big Data Analysis
• Covariance regularization by thresholding
• Sparse permutation invariant covariance estimation
• Sparsistency and rates of convergence in large covariance matrix estimation
• Computing in Operations Research using Julia
• Network exploration via the adaptive LASSO and SCAD penalties
• High-dimensionality effects in the Markowitz problem and other quadratic programs with linear constraints: Risk underestimation
• Least quantile regression via modern optimization
• Polyhedral approximation in mixed-integer convex optimization
• L0 Sparse Inverse Covariance Estimation

Cited by in corpus (1)

• A unified approach to mixed-integer optimization problems with logical constraints