Optimization Online


Scalable Inference of Sparsely-changing Markov Random Fields with Strong Statistical Guarantees

Salar Fattahi(fattahi***at***umich.edu)
Andres Gomez(gomezand***at***usc.edu)

Abstract: In this paper, we study the problem of inferring time-varying Markov random fields (MRF), where the underlying graphical model is both sparse and changes sparsely over time. Most of the existing methods for the inference of time-varying MRFs rely on the regularized maximum likelihood estimation (MLE), that typically suffer from weak statistical guarantees and high computational time. Instead, we introduce a new class of constrained optimization problems for the inference of sparsely-changing MRFs. The proposed optimization problem is formulated based on the exact L0 regularization, and can be solved in near-linear time and memory. Moreover, we show that the proposed estimator enjoys a provably small estimation error. As a special case, we derive sharp statistical guarantees for the inference of sparsely changing Gaussian MRFs (GMRF) in the high-dimensional regime, showing that such problems can be learned with as few as one sample per time. Our proposed method is extremely efficient in practice: it can accurately estimate sparsely-changing graphical models with more than 500 million variables in less than one hour.

Keywords: MRF, L0-optimization, graphical lasso

Category 1: Applications -- Science and Engineering (Statistics )

Category 2: Combinatorial Optimization

Citation: University of Southern California, Feb 2021

Download: [PDF]

Entry Submitted: 02/05/2021
Entry Accepted: 02/05/2021
Entry Last Modified: 02/05/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society