Solution Path of Time-Varying Markov Random Fields with Discrete Regularization

We study the problem of inferring sparse time-varying Markov random fields (MRFs) with discrete regularization on the parameters. Because of the intractability of discrete regularization, most approaches for solving this problem rely on maximum-likelihood estimation (MLE) with relaxed regularization, which neither results in ideal statistical properties nor scales to the dimensions encountered in realistic settings. In this paper, we address these challenges by resorting to a new class of constrained optimization problems with exact, discrete regularization. Despite nonconvex and discrete nature of our formulation, we show that it can be solved efficiently and parametrically for all sparsity levels. 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. Utilizing our algorithm, we can recover the complete solution path for instances of time-varying MRFs featuring more than 30 million variables in less than 12 minutes on a standard laptop computer.

History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete.

Funding: This work was supported by the Office of Naval Research [Grants N000142612117 and N000142612074], the Air Force Office of Scientific Research [Grant FA95502410086], the Division of Mathematical Sciences [Grants 2152776 and 2152777], and the Division of Computing and Communication Foundations [Grants 2006762 and 2337776].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0850) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.0850). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.