Skip to main content

Please enter a keyword and click the arrow to search the site

Certifiably optimal sparse inverse covariance estimation

Journal

Mathematical Programming

Subject

Management Science and Operations

Authors / Editors

Bertsimas D;Lamperski J;Pauphilet J

Biographies

Publication Year

2020

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

Available on ECCH

No


Select up to 4 programmes to compare

Select one more to compare
×
subscribe_image_desktop 5949B9BFE33243D782D1C7A17E3345D0

Sign up to receive our latest news and business thinking direct to your inbox

×

Sign up to receive our latest course information and business thinking

Leave your details above if you would like to receive emails containing the latest thought leadership, invitations to events and news about courses that could enhance your career. If you would prefer not to receive our emails, you can still access the case study by clicking the button below. You can opt-out of receiving our emails at any time by visiting: https://london.edu/my-profile-preferences or by unsubscribing through the link provided in our emails. View our Privacy Policy for more information on your rights.