Scalable Inference of Sparsely-changing Gaussian Markov Random Fields 
Authors: Salar Fattahi
Andres Gomez
Venue: NeurIPS 2021 Poster (2021)
Keywords: Markov Random Fields
Sparse inference
Discrete optimization

Abstract: We study the problem of inferring time-varying Gaussian Markov random fields, where the underlying graphical model is both sparse and changes {sparsely} over time. Most of the existing methods for the inference of time-varying Markov random fields (MRFs) rely on the \textit{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 Gaussian MRFs (GMRFs). The proposed optimization problem is formulated based on the exact $\ell_0$ regularization, and can be solved in near-linear time and memory. Moreover, we show that the proposed estimator enjoys a provably small estimation error. We derive sharp statistical guarantees in the high-dimensional regime, showing that such problems can be learned with as few as one sample per time period. Our proposed method is extremely efficient in practice: it can accurately estimate sparsely-changing GMRFs with more than 500 million variables in less than one hour.

Scalable Inference of Sparsely-changing Gaussian Markov Random Fields
Salar Fattahi
Department of Industrial & Operations Engineering University of Michigan Ann Arbor, MI 48 18109 fattahi @umi ch. edu
Andrés Gómez
Department of Industrial & System Engineering University Southern California
Los Angeles, CA 90089 gomezand@usc.eda
Abstract
We study the problem of inferring time-varying Gaussian Markov random fields, where the underlying graphical model is both sparse and changes sparsely over time. Most the existing methods for the inference time-varying Markov ran- dom fields (MRFs) rely the regularized maximum likelihood estimation (MLE), that typically suffer from weak statistical guarantees and high computational time. class of constrained optimization problems for the Gaussian MRFs (GMRFs). The proposed optimiza- tion problem is formulated based the exact regularization, and can be solved in near-linear time and memory. Moreover, we show that the proposed estimator enjoys provably small estimation error. We derive sharp statistical guarantees the high- sith-dimensional regime, showing that such problems can be learned with as few as one sample per time period. Our proposed method extremely efficient practice: it can accurately estimate sparsely-changing GMRFs with more than 500 million variables in less than one hour.
Instead, introduce inference of sparsely-changioe
1 Introduction
Contemporary systems are comprised of massive numbers of interconnected components that interact according hierarchy of complex, unknown, and time-varying topologies. For example, with billions of neurons and hundreds of thousands of voxels, the human brain is considered as one of the most complex physiological networks I& 20
30 37 The temporal behavior of today's interconnected systems can be captured via time-varying Markov random fields (MRF). Time-varying MRFs are associated with a temporal sequence of undirected Markov graphs (V E.). where V and E, are the set of nodes and edges in the graph at time t. The node set V represents the random variables in the model, while the edge set E, captures the conditional dependency between these variables at time t. A popular approach for the inference of MRFs is based on the maximum maximmm--likelihood likelihood estimation (MLE): to obtain model based on which the observed data most probable to occur (42
Despite being known as theoretically powerful tools 20 39 MLF--ased methods suffer from several fundamental drawbacks which render them impractical realistic settings. First, they often suffer from notoriously high computational cost in massive problems, where the number of variables to be inferred is in the order of millions, more. Second, they struggle incorporate sparsity amongst
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

their components, which is pervasive in large-scale systems. In particular, while sparsely-changing MRFs can in theory be accurately estimated using most of the existing methods resort to relaxed or weaker variants of such regularization (such as E penalty), thereby suffering from inferior statistical guarantees.
regularizers (such as la penalty),
To address the aforementioned challenges, we propose a class of constrained optimization problems that achieve superior statistical and computational guarantees, compared the regularized MLE, for the inference of time-varying Gaussian MRFs (GMRFs), Our approach departs from the usual wisdom in statistics and machine learning that inference problems with nonconvex to terms are intractable, and convex proxies should be used instead. In particular, we show that the inference of sparsely-changing Gaussian MRFs can be solved efficiently via nonconvex lo penalties.
Notations. The 1th element of time-series vector it is denoted as Vagi: the (i, element of time-series matrix V, is denoted Viaj- For vector v, the notation Dayj is used denote the subvector of u from index to j. For a vector v, the notations ||w]|>>, || |[v]lo denote the &o norm, lg norm, and the number of nonzero elements, respectively. Moreover, for matrix M, the notations [| M loo. || 11/11, |aMlo refer to the induced 2-norm, induced oc-norm, L norm, and
fo norm, respectively. Moreover, we define ||M = ||M[l1/ Σi= |Mai For vector and matrix M, the notations supp(e) and supp(M) are defined the sets of their nonzero elements. Given two sequences [n) and g(n), the notation [() S g(n) implies that there exists a constant C' < oo that satisfies (n) S Cg(n). and f(n)= x g(n) implies that fn) S g(n) and g(n) S fn).
All proofs are deferred to the supplementary file.
1.1 Warm-up: Regularized MLE for Sparsely-changing GMRF'
Consider multivariate zero-mean Gaussian process {X,) with distribution
P(X,)= {
1 H (0, (x, ) + Xz) - A(u,, 6.)
(I)
., T' where A Raxd R is the log-partition function used to normalize the distribution. Without loss of generality, we assume that the mean is zero. At any given time f, a sequence of data samples (x(()) Ji=1 is collected from ①. The inference of time-varying GMRFs reduces to Moreover, the
for 0............ O....
estimating the time-varying precision matrix O from the data samples (x((0 Ji=1- 1 edge set of the Markov graph G, coincides with the off-diagonal nonzero elements of θ 45
We first illustrate the fundamental drawbacks of the f regeulaard MLE for tire-iarying GMRFs with sparsely- chaanii-- structures. The sparse precision matrices be estimated via the following regularized MLE, also known as time-varying Graphical Lasso (GL.) 1
T
( = arg min
Σ 1=0
(n Ee) - log logd
8
T
+ m1
O + 72
Σ
110 0.-1l12/1
(2a)
1=0
s.t.
O 0
t= 0, 1,..,,TT
(2b)
where ÊS E RRdxd is the sample covariance matrix at time t. Without loss of generality, we assume that the samples have zero mean. Example 1 below shows that may lead to poor estimates.
Example 1. Consider a scenario where {0.) E 222522 are randomly generated symmetric and sparse matrices. At each time t = O,..., the precision matrix O has exactly 30 off-diagonal elements with value one in its upper-triangular part, and the remaining off-diagonal entries are set to zero. Moreover, the diugonal entries O1st are chosen 1 + E5ts O1äz-- At every time, 5 nonzero off-
diagonal elements are changed to zero, and 5 zero elements are set to one. The sample covariance E, obtained by collecting 500 samples from the Gaussian distribution with the constructed precision matrices. Figure Ta illustrates heatmap of the mismatch error, i.e., the total number of mismatches the spursity patterns of the true and estimated precision matrices and their differences, for different values of the regularization coefficients. It can be seen that after exhaustive search over the
2

---

regularization coefficient space, the best achievable mismatch ervor is in the order of 50. Thus, the estimated parameters reveal little information about the true structure of the viry-igrying GMRF. Moreover, Figure Tb depicts the concatena- tion of the nonzero elements the true pre- cision matrices (dashed red line), and their corresponding values in the estimated matri-
08
(blue curve). It can be seen that, even when the sparsity pattern of the elements is correctly recovered, the estimated nonzero entries are "shrunk" " toward zero, incurring a substantial bias.
The above example shows the inferior statis- tical performance of the time-varying GL as an instance of a regularized MILE method for sparsely-changing GMRFs. In addition to its subpar statistical performance, time-varying GL suffers from expensive computational complexity: a general-purpose interior-point algorithm for solving timevarrying GL has a prohibitive per-iteration complexity of O(Td)) [CC] More recent
(a)
Figure I: (a) The heatmap of the mismatch eror. (b) The true and estimated nonzero elements of the precision matrix.
algorithms for solving time- varying GL have lower per- per-iteration complexity of (Td))
[6 26 32]
However, these methods suffer from a slow (sublinear) convergence rate of O(1/e). increasing the overall complexity OTd'² /e) in order to obtain é-accurate solution. Thus, there is inherent tradeoff between the quality of the solution found and the computational time required, with the performance deteriorating sharply computational complexity may fall short of practical use in the large-scale settings. We now discuss the proposed method, which finds optimal solutions to the relevant optimization problems in strongly polynomial time.
the number of precision digits increase. Solvers with such
Proposed Approach
The proposed framework is based on exact solutions to class of tractable discrete fo-problems, thus circumventing bias and other drawbacks of the standard e f-approximations while guaranteeing the scalability of the proposed method. As a general framework, we study the optimization problem:
T
T
min (1 (1-7) Σ
Orllo +
Σ [=1
110 -0- 1
(3a)
1=0
110 - F (EeElol/ Sx
1 0, I,...,T
(3b)
O, O Rddd
t = 0, T.... T
(3c)
where the optimal solutions (G.)T are the estimates of the precision matrices of the sparsely- changing GMRF, E, E Rddd is the sample covariance matrix at time I, and (*(+) is an approximate backward mapping of the model. In particular, we use the approximate backward mapping proposed in [46], see $4.1 for a formal definition.
First, we establish a deterministic guarantee on the estimation error of the optimal solution to B
Theorem (Estimation error and sparsistency). Let < 7 < 1. For every t O...., T, define S, as the set of indices corresponding to the nonzero elements of the true precision matrix O and define D, as the set of indices corresponding to the nonzero elements O ; Assume that
F=
< >x VO T,
80/00
2 S min ( 40 S1ST,
2X, + 2A,-1 S min(JJ)D 1o. - - 04 ST.
Then, the following statements hold for every 0 STST:
Sparsistency supp (@.) supp (0;) and supp
@ ( supp (0: 07-1).
Estimation error 1 0; 1l0/ 2A, and | , 0 2l2 < <2v(S.
3

---

Theorem presents a set of conditions under which the proposed estimation method achieves sparsistency and small estimation error. The first condition entails that the true precision matrix i is feasible solution to B The second and third conditions imply that there is non-negligible gap between the zero and nonzero elements of the true parameters and their temporal changes. present additional bounds specific to our choice of backward mapping.
we
Theorem (Computational complexity). Given F (En),
, the optimization problem can be solved to optimality in at most (dd))² time and memory on a single thread.
Theorem 2 shows that the optimization problem ( can be solved efficiently and in strongly poly- nomial time despite its non-convex nature. As will be explained later, our choice of approximate backwards mapping [6 requires inverting T + 1 matrices, each with size d d, thereby increasing the overall complexity to ((dT)² + Td.). If < d, the complexity of the our method is dominated by that of the matrix inversion, which is unavoidable, even if the sample covariance matrix coincides with its true analog (since we still need to invert them to obtain the true precision matrices).
Our solution method for p relies on the flement-wise decomposability of G we decompose B into
smaller subproblems over different coordinates of {@r)ī-o- Then, we show that the optimal solution be obtained by solving shortest path problem
to each subproblem
auxiliary weighted Moreover, the
directed acyclic graph (DAG). The details of the solution method are presented in $
proposed algorithm is easily parallelizable, leading to better runtimes in practice.
Example (continued). Figure 2 depicts the performance of the proposed method, compared to the regularized MLE with m 0.14 and n2 = 0.16 (corresponding to the smallest mis- match error) for the instances generated in Ex- ample 1. The regularization parameter ry in the objective function of (3) is set to 0.2. Moreover, for simplicity, we set An
X4 X. Fig- ure La demonstrates that the proposed method enjoys significantly smaller mismatch error, for a wide range of X. On the other hand, Fig- ure shows that the synthetic bias caused by the & penalty in the regularized MLE is allevi- ated via the proposed method.
14
64
(a)
(b)
Figure 2: (a) The mismatch error of the proposed
method for different values of compared to regular- ized MLF, (b) The true and estimated nonzero elements of the precision matrix.
3 Related Works
a recent line of works where a kernel averaging technique combined with Graphical Lasso used to estimate the smoothly-changgng precision matrices. However, these methods do not leverage the prior information about the sparsity of the parameter differences. With the goal of addressing this deficiency, several works have studied the inference of sparsely-changing MRF (also known as sparse disferential networks) 43 47 27
Time-varying MRE. In addition to the time-varying GL introduced in L.1 have studied the inference of smoothly-changing GMRFs [23] 15 48
However, the main drawback these methods is that they only estimate the parameter differences, and their theoretical guarantees are restricted to problems with two time steps (7 = 0, 1). Similarly, regression-basee approaches have been proposed for change point detection problems [24] 36 with MRFs and two time periods, assuming the sparsity pattern of all entries of the precision matrices change at the same time. In contrast, [4] studies the inference of sparse MRFs given an index variable under the assumption that the sparsity pattern is invariant, whereas precision matrix is a linear function of the index variable.
assumes that the
Sparsity-promoting optimization. Optimization problems with tu terms are often deemed to be intractable, and approximations are solved instead. Perhaps the most popular approach is the fused 38 41, which calls for replacing terms |Oy]]o and ||O, e,-1lo with their & approximations. Nonetheless, such approximations result subpar statistical performance when compared with exact to methods 19 29].
lasso 34 40

---

Exact or near-optimal methods for optimization problems of the form
min OE(C.up
110|| l + Σ 9.,(0, - -,);
(4)
for given one-dimensional functions Pij IR + R. have also been studied in the literature. If functions Pi are convex, then problem 4 admits pseudo poo.ndomill time algorithm 7l Moreover, convex relaxations that deliver near-optimal solutions for 4 were proposed for the special case of convex quadratic g functions [6: if, additionally, we have
4 is in fact solvable in strongly polynomial time [5]. On the other hand, problem + is much more challenging for non-convex g: if g(x) = 1 {Ir + 0). the case in GB, then problem d NP-hard even if the term |ollo is dropped from the objective [17] Nonetheless, as we show in this paper, problem 4 can
and v oe, then problem
be solved efficiently in the context of mar-ing MRFs, where Iiy (r) = 0 whenever j > >
Statistical analysis
Theorem presents set of deterministic conditions under which the estimates from enjoy mismatch error and small estimation error. However, the formulation of (3) is contingent upon the availability of accurate backward mapping, and choice of X that satisfies the conditions of Theorem In this section, we show how to efficiently design sample-efficient approximate backward mappings, and select A₁ accordingly for the class of sparsely-changing GMRFs. Moreover, the deterministic conditions of Theorem to arrive at non-asymptotic probabilistic guarantee for the inference of time-varying GMRFs under different prior knowledge on their temporal behavior, such as sparsity and smoothness.
4.1 Sparsely-changing GMRFs
Given the true covariance matrix Σ., the backward mapping of time-varying GMRFs as defined in
takes the form F* (E,) = Σ, In light of this foosed-form expression for the backward mapping,
commonly-used approximation is (",(E)) ET where Σ, = N² Σn x (6) x.() is the sample covariance matrix. However, in the high-dimensional settings where d Nr, this approximate backward mapping is not well-defined, since the sample covariance matrix is highly rank-deficient.
To address this issue, [4 propose proxy backward mapping for high-dimensional settings: consider the soft-thresholding operator (MM Rdxd + Rdxd, where (Mf); = Msj sign(Ms;) min / if / j. and (M)} Mij if ofi=p j. The approximate backward map- ping is then given by (S,)) (S.)) which well-defined, even the high-dimensional setting, with an appropriate choice of the threshold 46. We make the following assumption.
Assumption (Bounded norm). There exist constant numbers K1 < 0o, K2 > 0, and Riz < oc such that, for every f 0,...,
||0||mo S KI,
inf wellw
|o 2 K2, [Ellooo/o S K3.
Assumption D implies that the true covariance matrices and their inverses have bounded norms.
Another key notion which plays an important role in our statistical guarantees is the weak sparsity of the covariance matrices, defined next.
def < g < 1 and dimension d, define salg, d)
Definition 1 (Weak sparsity). Given max, E [..
Assuming that (0, d) < d, Assumption I reduces to the covariance matrix being sparse. Moreover, in many cases, a sparse inverse covariance matrix leads to weakly sparse covariance matrices. For instance, if O, has banded structure with small bandwidth, then it is known that the elements of E, O,1 enjoy exponential decay away from the main diagonal elements [12 21 Under such circumstances, one can verify that sa(q, d) <
1-pe for some constant C 0 and < 1. More generally, similar statement holds for a class of inverse covariance matrices whose support graphs have large average path length [ 9 a large class of inverse covariance matrices with row- and column-sparse sparse structures satisfy this condition. Theorem B states that the proposed method results in
C
5

---

high-quality solutions provided that the number of samples N₂ is sufficiently large with respect to the weak sparsity of the covariance matrices.
Theorem 3. Consider a sparsely-changing GMRF and let Ç max(loga + 1), Given an arbitrary T > 2, let N₂ 2 sa(g, d) - log d, for some S q < Then, with the approximate
backward mapping F (Ex) = 1T,, (E.) and parameters Vs x V
rlogd and d x / Flo the
No
estimates
obtained from 5 satisfy the following statements for all t 0, ,,..., with
probability of at least 1 4d-
Sparsisteney We have supp (6,) supp (0;) and supp (0, - = supp (0; 17
Estimation error | 00 2
log N.
and ( 0; / log
N₂
Theorem B is a direct consequence Theorem and provides, to the best of our knowledge, the first non-asymptotic guarantee on the inference of sparsely-changing GMRFs with arbitrary length of time horizon T. In particular, it shows that the proposed optimization (3) guarantees small estimation error and zero mismatch error for sparsely-changing GMRFs, provided that N, scales logarithmically with the dimension of the precision matrices. In the static setting (T = 0), the derived bound recovers
the existing results on the sample complexity of learning static GMRFs
3 55
4.2
sanssel--ndd-moothly---
GMRFs
In many applications, such as financial markets and motion detection in video frames, the associated graphical model should be learned "on-the-go", as the data arrives with continuously changing graphical model. Under such circumstances, one may have access to few (or even one) samples at each time.
Suppose that the precision matrices change smoothly over time. Such smooth changes can be modeled via continuous function (z)) [0, + Rdxd with uniformly bounded element-wise
second derivatives [0" = ( such that θ; = ((t/T) 15 4 If θ(t) ;/- al for every t E [0, 1] and some a > 0, then the covariance matrix Σ(t) = ((t) 1 is well-defined and smooth. Then, the problem of inferring the tome-varying GMRF reduces to estimating sequence of precision matrices (0(0), ( ((1)) given the samples X, ~ NN ((t/E()))). To alleviate the scarcity of samples, 15 4 leverage the smoothness of the precision matrices, by taking the
dad
weighted average of the samples over time, where the weights are obtained from a nonparametric kernel. In particular, consider the weighted sample covariance matrix Σn
1 K
Sur
w[ss t)2is, where w(s
- Th
Th
and K(-) is symmetric nonnegative kernel that satisfies set of mild conditions which hold for most standard kernels, including the (truncated) Gaussian kernel. These conditions are delineated in the appendix. Next, present the counterparts of Assumption and Definition I for sparsely-ande smoothly-changing GMRFs.
Assumption 2 (Bounded norm). There exist constant numbers Kı 00, K2 > O, and R3 oo such that, every t E [0,7].
[((t/T)]le Ski inf [[(t/T)w/lo 2 K2, [E(t/T) S Kg. wr:||e/]|> =1
Definition 2 (Weak sparsity). Given 0 < q < 1 and dimension d, define selg, d) def
m0x [(((/(()))
We now present the analog of Theorem for
GMRFs.
Theorem 4. Consider
GMRF with one sample per time, let < = max(log, + 1), 1}, and suppose that the sample covariance matrices are constructed
according to 5 with h = T-133, Given an arbitrary > + 2, let T Z selg. d) - (T log 3/)
Then, with the approximate backward mapping F (É,) ST,, (ET) and parameters V4 x Ving
T1/3
and de- x T1,3
Voloog the estimates {Ô, 1io obtained from
B satisfy the following statements for all
T = 0, 1, .....I T with probability of at least 1 d' ++++

---

Sparsistency supp ( supp (0;) and supp
(ô: 61-1) supp (0; 11) - 01 r|S, log
Estimation error - -i S
log T2/3
and
72/3
Theorem 4 shows how the smoothness assumption the true covariance matrix can be used to construct the backward mappings using the samples collected during the entire time horizon, thereby significantly reducing the sample complexity of learning time- marying GMRFs. In partieular, leveraging the smoothness of the covariance matrix can reduce the minimum required number of samples from (T log d) ((log d) 19). On the other hand, Theorem 3 does impose any lower bound on T, and its estimation error decays faster in terms of the sample size.
Solution Method
In this section, we describe the proposed algorithm for solving 3 For the simplicity of notation, we define the lower bound and upper bound matrices 4 and ue as leis = [F [F*(E.)ls - A and
F (Te))yg + de, for every 1 S i,j S d. The following fact plays key role in our analysis.
Fact 1. An optimal solution { 2 of satisfies for every 1 Si si<jse
T
(G E arg min (1 (1- 1= (Quss
1 * 0} +
1(0m O 7 0}
(6a)
1=0
s.t. 4as S Orss S ues
vO S t T.
(6b)
Fact DactTimpe iimplies that decomposes into the smaller subproblems Therefore, our main focus is devoted to solving each subproblem independently. To further simplify the notation, we drop the subscript ij from ( whenever it is chosen arbitrarily, and use 0, instead of O
Let (PT) denote the truncated problem from time to j with the regularization coefficient y:
Fi. min (1-7) Σ (0.P2.
100
+ 03 +
Σ 1=2+1
1(0, 0,-1 + 03
(7a)
1=1
subject to 4 5 0: 5
Vi vist
(7b)
Let the objective function for candidate solution 0 be denoted as (0); by convention, we let (0) = whenever < Moreover, the optimal objective value and the set of optimal solutions to (7) are respectively denoted as fī-j and Xi=nj. Similarly, d. E X2 is used to denote an optimal solution to OPT;-;j(7) We omit the subscript i + j whenever = 0 and
j = T. The Th feasible interval is defined as A. = [4, u.). Accordingly, the notation A refers to
A A
def A n . n
5.1 Special case: 7 = 1
As the first step, consider the special case = 1, and provide efficient algorithm (Algorithm) for solving OPTo--7(1), where the sparsity is only promoted on the parameter differences (and not on the individual parameters). As will be shown later, Algorithm D will be used as subroutine in our proposed algorithm for the general case 0 < 7 < 1. At high level, Algorithm I recursively performs the following operations: any given time the algorithm looks into the future to find nonempty interval that feasible for the longest possible time 8. Then, sets the subvector 07:5 to an arbitrarily chosen element from this nonempty interval.
Proposition Greedy(1, u, O, T) returns an optimal solution {0 Creeedy over, the truncated solution (0) (gfreedy). J y is optimal for O1)o
Ji-o (PTo-T(11). More-
5.2 General case: 0 < <1
Now, we present our main algorithm for the general case 0 < 7 < 1.
7

---

Algorithm 1 Greedy u, T)
1: Output: Solution of the objective value 5T to OPT, -T), and the index set of maximal nonempty intervals
2: Find largest 6 such that AP-48 0;
3: Set @rreedy 1j for some A7-6
4: if T then
5: Execute Greedy(l, + 1,T);;
6: end if
7: Set S
-t 110frocty. - 00reeds 40];
8: Set r e T [6};
9: Return (0greedy17
1T
Greedy and I;
1I=T 7-
Definition 3. The set Z,-, = Ii.i j} is called a zero-feasible sequence i & 0 < un for every k E Zi-z. Moreover, the zero-feasible sequence Zi-j is called maximal if is not strictly contained within another zero-feasible sequence.
Let Zi.+jo- Zig 222--j22..... Zig -zz be the set of all maximal zero-feasible sequences such that 0 S S J1 < i2 S J2 < < iz S jz I T, where Z is the number maximal zero-feasible sequences. = 0, ie., there is no zero-feasible sequence, then 0} + 1 for every feasible solution, and hence, Greedy (1, u, O, T) leads to optimal solution Another special case is when é 0 and ýi T, in which case the optimal solution is 0 - O. Therefore, without loss of generality, suppose that Z > 0 and either i1 * 0 or j1 + T.
easy to see that Σ 1 (0 +
Our goal now is to obtain optimal solution to 7 by solving shortest path problem directed acyclic graph (DAG) whose nodes correspond to the maximal zero- fers-bee sequences. In particular, consider weighted DAG G with the vertex set V = {0, 1 ...... Z, Z + 1}. where the vertices k and are connected via a directed are (k. 1) if < I. Moreover, for every are (k:, 1). the 0 or (k:, I) (Z, Z 1). T, and
weighted
weight W(k, 1) if (k: 1) (0, 1),
(k,, - (4 - ju - 1) + T 1- + f + 0) + x111 + Z ++1
(8)
otherwise, where we define jo 1 and iz+ +
Algorithm 2 Algorithm for solving
1: Output: Optimal solution and the objective value f" to OPTo-I(1))
2: Find the maximal zero-feasibl sequences;
3: Construct the DAG with weights defined as 3
4: Find the shortest path (U1, U2...., U,) between the vertices 0 and Z in G; for every 1,2,.... 1.......7
5: Set J..,
grreedy 0 +1 and 6 2044
+1580411
6: Return (0)T t= and
Theorem 5. The shortest froh to + 1 on G has value f*
The above theorem implies that the optimal solution to 3 can be obtained via Algorithm 2 Theorem 6. Problem 7 can be solved OZTT) time and memory.
Since Z = (T)) and a solution to B requires solving O(d2) instances of we find the total complexity stated in Theorem 2 Note however that if Z (1), then the overall complexity reduces to (TTd)), which is linear the total number variables. In the next section, we will show that the practical runtime of the proposed algorithm is near-linear with respect to the number of variables.
Numerical Analysis
In this section, we evaluate the performance of the proposed estimator in synthetically generated massive datasets, and case study the correlation network inference in stock markets. We refer

---

the reader to the supplementary file for an extensive discussion of our simulations (e.g., the choice of parameters, robustness analysis, and comparison with other sfate-of-the-ar methods). In all of our simulations, the parameters and d are chosen directly from the data samples, i.e., without prior knowledge of the true solution, via Bayesian Inference Criterion (BIC) 31 13
Case Study on Large Datasets We consider randomly generated instances of sparsely-changing GMRFs, where the true inverse covariance matrix constructed as follows: at time | 0, we set G Ia + E(.))s A(t2), where A(5)) is sparse positive semidefinite matrix with exactly
two nonzero off-diagonal elements. For every (i,j) E S, we set A
Al -0.4 and
A A/ 0.4. Clearly, A = O, and hence, O > In the first experiment, we fix T = 10 and change the values of d. The number of nonzero elements in the individual precision matrices and their differences are set to 3d and 0.04d, respectively. We evaluate the performance of the proposed method in the high dimensional settings, where N, = dd2 for every t O,..., T. Moreover, define TPR and FPR for the individual parameters and their differences as the true positive and and false positive values, normalized by the total number of nonzero and zero elements in the true precision matrices and their differences, respectively. Clearly, both TPR and FPR are between 0 and 1. with TPR 1 and FPR corresponding to the perfect recovery of the sparsity patterns. Figure depicts TPR, FPR, and the max-norm eπтоr of the estimated parameters, as well as the runtime of our algorithm for different values of d with and without parallelization. It can be seen that both TPR and FPR values improve with the dimension for the estimated parameters and their differences. Moreover, with a single core, the runtime of our algorithm scales almost linearly with d?, which is in line with the result of Theorem g Using 5 cores, the runtime of our algorithm is improved by 40% on average. Using 10 cores deteriorates the performance due to the shared memory limitations. Using our algorithm, we reliably infer instances of spursely- GMRFs with more almost 500 million variables in less than one hour.
x10
Individual Difference
Indiviual
Difference
0.95
4
TPR
0.9
FPR
2
0.85
0.8
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
(a)
(b)
0.16
Error (max norm)
0.14
Time (scconds)
1800
0.12
1000
D.1
500
cores
5 cores
0.08
10 pores
0
2000
4000
6000
8000
10000
0
Number of variables
x10
(c)
(d)
Figure 3: (a) TPR of the proposed method. (b) FPR of the proposed method. (c) The max-norm of estimation
error. (d) The runtime of the proposed algorithm with and without parallelization.
Case Study on Stock Market Finally, we illustrate the performance of our algorithm for the inference of stock correlation network. partieular, we consider an investor seeking to understand re- lationships between securities over time. Sparsity of the precision matrices guarantees interpretability,
9

---

while the sparsely- changingg structure is imposed to identify sharp changes in market conditions, and need rebalance the portfolio. We consider the daily changes for 214 securities from 1990/01/00 to 2017/08/11 10, with the total number of 6990 days (d = 214 and T = 6990). Due to the continu- ously changing nature of the stock correlation network, we will use the kernel averaging approach Using the constructed sample covariance matrices, we estimate the sparsely-changing precision matrix (t//T') at discrete times E {30, 60,
introduced in Subsection
A drastic change in the correlation network signals a spike in the stock market, which may reflect the market's response to unexpected events. Figure I shows the number of changes in the estimated network, for the choices of National Association of Securities Dealers Automated Quotations (NASDAQ) M. It can be seen that the major spikes in the estimated network can be attributed to the historical stock market crashes. For instance, the spikes A, B, and C respectively correspond to the "early 1990s recession", "dot-com bubble", and "global financial crisis"; see 4 for more details. Interestingly, the estimated network can also detect other historical (but less severe) downturns 2011 (point D) and 2016 (point E). the supplementary materials, provide more detailed analysis with different choices of parameters.
3. A = 0.16, and ? 0.9, together with the historical chart of
4000
18:000
3930
15.00
Nuntae sturgee
12,00
2200
12,00
2000
1000
800
4080
1030
(a)
(b)
Figure 4: (a) NASDAQ historical chart
2
(bb The number of changes in the estimated network.
Acknowledgments and Disclosure of Funding
S.F. is supported by MICDE Catalyst Grant and MIDAS PODS Grant. A.G. is supported, in part, by the National Science Foundation under grant CIF 2006762.
References
[1] About nasdaq. https://www nasdaq com/
com/about about 2020.
[2] Nasdaq composite 45 year historical chart. attps://uww.macrott nasdaq- hwtgg--htttoiiicahhhhhaeg chart 2020.
net/1320/
[3] Ravindra K Ahuja, Dorit S Hochbaum, and James B Orlin. A cut-based algorithm for the nonlinear dual of the minimum cost network flow problem. Algorithmica, 39(3):189-208, 2004.
[4] Robert Z Aliber and Charles P Kindleberger. Manias, panics, and crashes: A history financial crises. Springer, 2017.
[5] Alper Atamtürk and Andrés Gómez. Strong formulations for quadratic optimization with m-matrices and indicator variables. Mathematical Programming, 170(1):141-1766 2018.
[6] Alper Atamtürk, Andrés Gómez, and Shaoning Han. Sparse and smooth signal estimation: Convexification of fn-ormulatiinss arXiv preprint arXiv:1811.02655. 2018.
[7] Francis Bach. Submodular functions: from discrete to continuous domains. Mathematical Programming, 175(1-2):419 459, 2019.
[8] Michele Benzi and Nader Razouk. Decay bounds and o (n) algorithms for approximating functions of sparse matrices. Electron. Trans. Numer. Anal, 28:16 28:16-39, 2007.
10

---

[9] Michele Benzi and Valeria Simoncini. Decay bounds for functions of hermitian matrices with banded kronecker structure. SIAM Journal on Matrix Analysis and Applications, 36(3):1263- 1 1282, 2015.
[10] Stephen Boyd, Stephen Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[11] Biao Cai, Gemeng Zhang, Aiying Zhang, Julia M Stephen. Tony W Wilson, Vince D Calhoun, and Yu-Ping Wang. Capturing dynamic connectivity from resting state fmri using time-varying graphical lasso. IEEE Transactions Biomedical Engineering, 66(7):1852-1866 2018.
[12] Stephen Demko, William Moss, and Philip W Smith. Decay rates for inverses band matrices. Mathematics of computation, 43(168):491-44) 1984.
[13] Rina Foygel and Mathias Drton, Extended bayesian information criteria for gaussian graphical models. arXiv preprint arXiv: 2010.
[14] Sinong Geng, Minhao Yan, Mladen Kolar, and Sanmi Koyejo. Partially linear additive gaussian graphical models. In International Conference on Machine Learning, pages 2180-2190. PMLR, 2019.
[15] Kristjan Greenewald, Seyoung Park, Shuheng Zhou, and Alexander Giessing, Time-dependent spatially varying graphical models, with application brain fmri data analysis. In Advances in 2017.
Neural Information Processing Systems, pages
[16] David Hallac, Youngsuk Park, Stephen Boyd, and Jure Leskovec. Network inference via the time-varying graphical lasso. In Proceedings of the 23rd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pages 205-213, 2017.
[17] Dorit S Hochbaum. An efficient algorithm for image segmentation, markov random fields and related problems. Journal of the ACM (JACM), 48(4): 201 2001.
[18] Shuai Huang, Jing Li, Liang Sun, Jieping Ye, Adam Fleisher, Teresa Wu, Kewei Chen, and Eric Reiman. Learning brain connectivity of alzheimer's disease by sparse inverse covariance estimation.
Neurolmage, 50(3):935-949, 2010.
[19] Sean Jewell and Daniela Witten. Exact spike train inference via to optimization. arXiv preprint arXiv:1703.08644 2017.
[20] Rudolph Emil Kalman. A new approach to linear filtering and prediction problems. 1960.
[21] D Kershaw. Inequalities the elements of the inverse of certain tridiagonal matrix. Mathe- matics of computation, pages 155-158, 1970.
[22] Junghi Kim and Wei Pan. Highly adaptive tests for group differences in brain functional connectivity. Neurolmage: Clinical, 9:625-639, 2015.
[23] Mladen Kolar and Eric Xing. On time varying undirected graphs. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 407-415. JMLR Workshop and Conference Proceedings, 2011.
[24] Mladen Kolar and Eric P Xing. Estimating networks with jumps. Electronic journal of statistics, 6:2069, 2012.
[25] Clifford Lam and Jianqing Fan. Sparsistency and rates of convergence in large covariance matrix estimation. Annals of statistics, 37(66):4254, 2009.
[26] Batiste Le Bars, Pierre Humbert, Argyris Kalogeratos, and Nicolas Vayatis. Learning the piece-wise constant graph structure of a varying ising model. International Conference on Machine Learning, 2020.
[27] Song Liu, Kenji Fukumizu, and Taiji Suzuki. Learning sparse structural changes high- dimensional markov networks. Behaviormetrika, 44(1):265-286, 2017.
11

---

[28] Xiao Liu and Jeff H Duyn. Time-varying functional network information extracted from brief instances of spontaneous brain activity. Proceedings of the National Academy of Sciences, 1 110(11))433)) (((11))4392-439)) 2013.
[29] Alan Miller. Subset Selection in Regression. CRC Press, 2002.
[30] Manjari Narayan, Genevera Allen, and Steffie Tomson. Two sample inference for pop- ulations of graphical models with applications to functional connectivity, arXiv preprint arXiv:1502.038833 2015.
[31] Andrew A Neath and Joseph E Cavanaugh. The bayesian information criterion: background, derivation, and applications. Wiley Interdisciplinary Reviews: Computational Statistics, 1(2):199-203, 2012.
[32] Pradeep Ravikumar, Martin J Wainwright, and John D Lafferty. High-dimensional ising model selection using E1-regularized logistic regression. The Annals of Statistics, 3883)11287-1319, 2010.
[33] Pradeep Ravikumar, Martin J Wainwright, Garvesh Raskutti, and Bin Yu. High-dimensional covariance estimation by minimizing & d1-penalized log-determinant divergence. Electronic Journal of Statistics, 5:935-988 2011.
[34] Alessandro Rinaldo et al. Properties and refinements of the fused lasso. The Annals of Statistics, 37:2922-2952,, 2009. 2009.
[35] Adam J Rothman, Peter J Bickel, Elizaveta Levina, Ji Zhu, et al. Sparse permutation invariant covariance estimation. Electronic Journal of Statistics, 2:494-515, 2008.
[36] Sandipan Roy, Yves Atchadé, and George Michailidis. Change point estimation in high dimensional markov random-field models. Journal of the Royal Statistical Society. Series B, Statistical methodology, 79(4): 187, 2017.
[37] Mikail Rubinov and Olaf Sporns. Complex network measures of brain connectivity: uses and interpretations. Neuroimage, 105):1059-1069 2010.
[38] Leonid Rudin, Stanley Osher, and Emad Fatemi. Nonlinear total variation based noise removal algorithms. Physica D: Nonlinear Phenomena, 60:259-266 2688, 1992.
[39] Jerome Clair Shellenbarger. Estimation of covariance parameters for an adaptive kalman filter. 1966.
[40] Robert Tibshirani, Michael Saunders, Saharon Rosset, Ji Zhu, and Keith Knight. Sparsity and smoothness via the fused lasso. Journal of the Royal Statistical Society: Series (Staristical Methodology), 1-:91-108, 2005.
[41] Curtis R Vogel and Mary E Oman. Iterative methods for total variation denoising. SIAM Journal on Scientific Computing, 17:227-238, 1996.
[42] Martin Wainwright and Michael Irwin Jordan. Graphical models, exponential families, and variational inference. Now Publishers Inc, 2008
[43] Beilun Wang, Yanjun Qi, et al. Fast and scalable learning of sparse changes in high-dimensional gaussian graphical model structure. In International Conference on Artificial Intelligence and Statistics, pages 1691-1700. PMLR, 2018
[44] Jialei Wang and Mladen Kolar. Inference for sparse conditional precision matrices. arXiv preprint arXiv: /4/2. 2014.
[45] Yair Weiss and William Freeman. Correctness of belief propagation in gaussian graphical models of arbitrary topology. In Advances in Neural Information Processing Systems, pages 673-679, 2000.
[46] Funho Yang, Aurélie C Lozano, and Pradeep K Ravikumar. Elementary estimators for graphical models. In Advances in neural information processing systems, pages 2159-2167, 2014.
12

---

[47] Sihai Dave Zhao, T Tony Cai, and Hongzhe Li. Direct estimation of differential networks. Biometrika, 101(2):253-266 268. 2014.
[48] Shuheng Zhou, John Lafferty, and Larry Wasserman. Time varying undirected graphs. Machine Learning, 80(-3))295-319, 2010.
13


Reviews:
[{"review_id": "pf_WKD3Jeqe", "reviewer": "Reviewer_CuaR", "summary": "This work tackles the sparsely changing GMRT problems. By mainly comparing with TVGL, the method claims to have stronger theoretical guarantees and computational efficiency. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The problem setup is mainly covered in TVGL paper, but the method is novel enough in a sense of proposing new optimization problem, optimization algorithm, and statistical guarantees. \n\nQuality/Significance: It provided solid and thorough theoretical guarantees and proofs. However, the experiments are rather weak. It only compared with TVGL through one simple synthetic experiments (that could have been particularly adversarial) whereas TVGL did extensive synthetic and real data experiments with reporting various scores. \n\nClarity: The writing can be improved in general. To name a few, for example, indicate that the the proof of theorem 2 will be provided in section 5. Some notations like approx backward mapping \\tilde F, \\Delta^cap_{t->s} is overly complicated, making the readers difficult to follow. \n\nAdditional questions to be clarified:\n1. (3c) should be symmetric. How do you force it in optimization?\n2. In line 88, TVGL does not use interior point method, only requiring O(Td^3) per iteration through ADMM that can be parallelized.\n3. In line 124, the matrix inversion seems to be needed for each time t. and thus need Td^3 in total? It this is true, how do you compare the computational cost with TVGL?\n4. In line 190, there must be some sufficient condition on \\nu to define its inverse properly, e.g. positive, etc. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It would be interesting to apply this method to some COVID dataset for a bigger societal impact. ", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "nsFMOkM-vBE", "reviewer": "Reviewer_GycU", "summary": "This paper proposes a scalable algorithm to learn time varying gaussian graph models, and show that it has good convergence property. It also conducts a large scale experiment to demostrate the efficiency of the algorithm.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The theoretical findings of this paper is very good. The algorithm is both simple and efficient. And it will be useful for a wide range of problems.\n\nThe structure of the paper is somewhat counterintuitive. The definitions of $F^*$ and the main idea of the algorithm should be moved to the beginning of the paper. Otherwise some statements in Section 2 are quite confusing.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The notations of matrix norms should be defined more clearly. I can only guess the double infinity norm is the entrywise norm? I have not seen this notation before.\n\nIn the experiments, the authors should provide more comparisons to previous methods. Is the time-varying Graphical Lasso applicable to the large scale problem? If so, what is the performance of it compared to the proposed algorithm?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "m-mJHGfFchW", "reviewer": "Reviewer_jzT4", "summary": "In this paper, the authors consider the problem of learning Sparsely changing Gaussian Markov Random Fields. They pose the problem as a non-convex optimization problem that can be solved exactly. The authors provide statistical guarantees. Furthermore, they also provide a computationally efficient algorithm to recover the graphical model.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality – The problem of Gaussian Graphical Models evolving with time is surely an interesting one and the authors provide a novel optimization problem formulation to solve this problem. The authors clearly delineate their work compared to existing literature.\n\nQuality – The claims are well supported. The first concern I have is with the weak sparsity condition. While the authors do provide some insights into the examples when the weak sparsity is bounded, it seems to restrict the applicability to a small class of Gaussian graphical models. Another concern is the lack of discussion about choosing the parameters $\\lambda$ and $\\gamma$.\n\nClarity – The paper is well written and easy to follow.\n\nSignificance – The paper addresses an important problem and the practicality of the proposed solution could see it being used in practice. Future work could be aimed at demystifying and hopefully relaxing the weak sparsity condition.\n\nOverall I think this is a great paper with a novel approach to solve an interesting problem and has a good mix of statistical guarantees as well as a computationally feasible algorithm.\n\n-------------------------After Rebuttal-------------------------\nThanks for providing further insights into the weak sparsity condition as well as choosing $\\lambda$ and $\\gamma$, it really helped in bringing out the idea clearly.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper does not seem to have any potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "hq5xTW9QN-H", "reviewer": "Reviewer_zSRw", "summary": "This submission considers the problem of estimating the time-varying precision matrices corresponding to a Gaussian graphical model. The authors propose an \\ell_0-regularized optimization problem (that runs in polynomial time), and establish theoretical guarantees as well as its performance on simulated and real datasets. The paper is quite well-written and seems like an important contribution to this active research area.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "There has been considerable interest in establishing efficient algorithms and theoretical guarantees for recovering the underlying structure (i.e., edges) of Markov random fields (MRFs). A great deal of this work has focused on the Gaussian case, and relied on \\ell_1-regularized maximum likelihood estimators, often referred to as Graphical Lasso. Most of this work makes so-called \"incoherence\" assumptions on the underlying precision matrix (and this work seems to rely on similar assumptions) to then give sample complexity bounds. \n\nIn many settings, it may be of more interest to understand how the edges of the MRF change over time. The naive approach to this problem is to re-estimate the set of edges, and compare the differences. However, the sample complexity will be dominated by the total number of edges in each instance, even if the number of changes is small. This submission focused on this problem and demonstrates that an \\ell_0-regularized maximum likelihood estimator can be solved in polynomial time to find the changes, with a sample complexity that depends primarily on the number of changes. Thus, the paper makes a novel conceptual contribution and uses to establish new theoretical guarantees on a well-motivated problem. To the best of my knowledge, this is the first paper to characterize the sample complexity of time-varying precision matrices via an efficient algorithm. \n\nThe paper also demonstrates the performance of the proposed \\ell_0-regularized estimator on simulated and real data. In particular, I appreciated Figure 1, which clearly establishes that traditional \\ell_1-regularized methods fail to capture the sparse, time-varying changes, combined with Figure 2 that shows the success of the proposed method.\n\nOverall, the paper is well-written and well-placed in the context of the literature. My main questions with the paper are as follows:\n\n1. How do the precision matrix assumptions in this work compare to those of related work? Is there a natural family of models where both sets of assumptions apply? How efficiently can these assumptions be checked for a given model?\n\n2. I didn't quite understand the point of Figure 3. Wouldn't it be helpful to plot the \\ell_1-performance to make a comparison? If this is not feasible (due to runtime issue), then a comment to that effect would suffice.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is primarily a theoretical paper, and I do not foresee any potential negative societal impacts. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "TuStWPLNXPR", "reviewer": "Reviewer_5AUA", "summary": "  This paper study the problem of inferring time-varying Gaussian Markov random fields, where the underlying graphical model is both sparse and changes {sparsely} over time. A new class of constrained optimization problems was introduced for the inference of sparsely-changing Gaussian MRFs (GMRFs). The proposed optimization problem is formulated based on the exact regularization and can be solved in near-linear time and memory. \n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The reviewer finds this work provides very interesting and meaningful theoretical and algorithmic results. The overall novelty and significance is very good and would bring significant impact to various real-world application. \n\nHowever, the reviewer does find numerical tests compared with existing works missing, as only the performance evaluated is for the proposed algorithm, but no comparison with other existing frameworks is provided. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the task of estimating a sparse Gaussian graphical model with a graph that changes sparsely over time. A nonconvex optimization formulation is shown to be efficiently solvable and to achieve good performance both empirically and theoretically. This is an important problem and the paper makes worthwhile progress. 
Decision: Accept (Poster)