# Solution Path of Time-varying Markov Random Fields with Discrete Regularization

arXiv: https://arxiv.org/abs/2307.13750 · HTML: https://mlsanity.com/paper/2307.13750/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 82 references that are in the map.
- First posted on arXiv 25 Jul 2023.

## Builds on (most cited first, 20 of 20)

- [Self-Tuning Networks: Bilevel Optimization of Hyperparameters using Structured Best-Response Functions](https://mlsanity.com/paper/1903.03088/) (2019)
- [Network Inference via the Time-Varying Graphical Lasso](https://mlsanity.com/paper/1703.01958/) (2017)
- [Node-Based Learning of Multiple Gaussian Graphical Models](https://mlsanity.com/paper/1303.5145/) (2013)
- [Submodular Functions: from Discrete to Continous Domains](https://mlsanity.com/paper/1511.00394/) (2015)
- [Graphical Lasso and Thresholding: Equivalence and Closed-form Solutions](https://mlsanity.com/paper/1708.09479/) (2017)
- [Sparse and Smooth Signal Estimation: Convexification of L0 Formulations](https://mlsanity.com/paper/1811.02655/) (2018)
- [Graph Learning from Data under Structural and Laplacian Constraints](https://mlsanity.com/paper/1611.05181/) (2016)
- [Joint Estimation of Multiple Graphical Models from High Dimensional Time Series](https://mlsanity.com/paper/1311.0219/) (2013)
- [Time-dependent spatially varying graphical models, with application to brain fMRI data analysis](https://mlsanity.com/paper/1711.03701/) (2017)
- [Computational Implications of Reducing Data to Sufficient Statistics](https://mlsanity.com/paper/1409.3821/) (2014)
- [Large-Scale Sparse Inverse Covariance Estimation via Thresholding and Max-Det Matrix Completion](https://mlsanity.com/paper/1802.04911/) (2018)
- [Partially Linear Additive Gaussian Graphical Models](https://mlsanity.com/paper/1906.03362/) (2019)
- [Change-Point Estimation in High-Dimensional Markov Random Field Models](https://mlsanity.com/paper/1405.6176/) (2014)
- [Hardness of parameter estimation in graphical models](https://mlsanity.com/paper/1409.3836/) (2014)
- [A Graph-based Decomposition Method for Convex Quadratic Optimization with Indicators](https://mlsanity.com/paper/2110.12547/) (2021)
- [Certifiably Optimal Sparse Inverse Covariance Estimation](https://mlsanity.com/paper/1906.10283/) (2019)
- [Inference for Sparse Conditional Precision Matrices](https://mlsanity.com/paper/1412.7638/) (2014)
- [Learning Sparse Structural Changes in High-dimensional Markov Networks: A Review on Methodologies and Theories](https://mlsanity.com/paper/1701.01582/) (2017)
- [Fast and Scalable Learning of Sparse Changes in High-Dimensional Gaussian Graphical Model Structure](https://mlsanity.com/paper/1710.11223/) (2017)
- [Efficient Inference of Spatially-varying Gaussian Markov Random Fields with Applications in Gene Regulatory Networks](https://mlsanity.com/paper/2206.10174/) (2022)

## Built on by (most cited first, 1 of 1)

- [Coordinate Optimality Reformulation for Mixed-Integer Convex Programs with Indicators](https://mlsanity.com/paper/2608.01385/) (2026)

## Abstract (arXiv)

We study the problem of inferring sparse time-varying Markov random fields (MRFs) with different discrete and temporal regularizations on the parameters. Due to the intractability of discrete regularization, most approaches for solving this problem rely on the so-called maximum-likelihood estimation (MLE) with relaxed regularization, which neither results in ideal statistical properties nor scale to the dimensions encountered in realistic settings. In this paper, we address these challenges by departing from the MLE paradigm and resorting to a new class of constrained optimization problems with exact, discrete regularization to promote sparsity in the estimated parameters. Despite the nonconvex and discrete nature of our formulation, we show that it can be solved efficiently and parametrically for all sparsity levels. More specifically, we show that the entire solution path of the time-varying MRF for all sparsity levels can be obtained in O(pT3), where T is the number of time steps and p is the number of unknown parameters at any given time. The efficient and parametric characterization of the solution path renders our approach highly suitable for cross-validation, where parameter estimation is required for varying regularization values. Despite its simplicity and efficiency, we show that our proposed approach achieves provably small estimation error for different classes of time-varying MRFs, namely Gaussian and discrete MRFs, with as few as one sample per time. Utilizing our algorithm, we can recover the complete solution path for instances of time-varying MRFs featuring over 30 million variables in less than 12 minutes on a standard laptop computer. Our code is available at urlhttps://sites.google.com/usc.edu/gomez/data.