Certifiably optimal sparse inverse covariance estimation

Bertsimas, D, Lamperski, J and Pauphilet, J (2020) Certifiably optimal sparse inverse covariance estimation. Mathematical Programming, 184 (1-2). pp. 491-530. ISSN 0025-5610


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 1000 s. 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.

More Details

[error in script]
Item Type: Article
Subject Areas: Management Science and Operations
Additional Information:

© 2020 Springer Nature

Date Deposited: 23 Nov 2020 09:40
Subjects: Mathematical programming
Last Modified: 20 Apr 2024 01:17
URI: https://lbsresearch.london.edu/id/eprint/1561
[error in script] More

Export and Share


Full text not available from this repository.


View details on Dimensions' website

Downloads from LBS Research Online

View details

Actions (login required)

Edit Item Edit Item