Solution Path of Time-varying Markov Random Fields with Discrete
  Regularization
Salar Fattahi Andres Gomez
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 $\mathcal{O}(pT^3)$, 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
\url{https://sites.google.com/usc.edu/gomez/data}.