Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 


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. 

However, 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. 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

Quality – 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$.

Clarity – The paper is well written and easy to follow.

Significance – 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.

Overall 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.

-------------------------After Rebuttal-------------------------
Thanks 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.

limitations_and_societal_impact: The paper does not seem to have any potential negative societal impact.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.
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. 

In 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. 

The 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.

Overall, the paper is well-written and well-placed in the context of the literature. My main questions with the paper are as follows:

1. 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?

2. 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.


limitations_and_societal_impact: This is primarily a theoretical paper, and I do not foresee any potential negative societal impacts.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

The 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.
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.

In 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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
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. 

Quality/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. 

Clarity: 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. 

Additional questions to be clarified:
1. (3c) should be symmetric. How do you force it in optimization?
2. In line 88, TVGL does not use interior point method, only requiring O(Td^3) per iteration through ADMM that can be parallelized.
3. 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?
4. In line 190, there must be some sufficient condition on \nu to define its inverse properly, e.g. positive, etc. 


limitations_and_societal_impact: It would be interesting to apply this method to some COVID dataset for a bigger societal impact.
review_title: null

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)