A Screening Rule for 1 -Regularized Ising Model Estimation
We discover a screening rule for 1 -regularized Ising model estimation. The simple closed-form screening rule is a necessary and sufficient condition for exactly recovering the blockwise structure of a solution under any given regularization parameters. With enough sparsity, the screening rule can be combined with various optimization procedures to deliver solutions efficiently in practice. The screening rule is especially suitable for large-scale exploratory data analysis, where the number of variables in the dataset can be thousands while we are only interested in the relationship among a handful of variables within moderate-size clusters for interpretability. Experimental results on various datasets demonstrate the efficiency and insights gained from the introduction of the screening rule.
SUMMARY:
========
The authors propose an efficient screening for sparse Ising model structure estimation.  The screening rule is shown to be optimal for locating non-interacting variables in an L1 regularized MLE.  Combining this screening rule with approximate optimization allows efficient parallel computation of the full model structure, as demonstrated on several synthetic graph problems.
PROS:
=====
The screening rule can be calculated fairly efficiently, in time quadratic in the number of data elements, and as such could be easily adopted in practice.  The authors also clearly show that the method is optimal in a regularized MLE sense, and computation of the screening rule also provides a range of valid regularization parameters including those that yield a fully disconnected graph.
CONS:
=====
The authors do not discuss the relationship between the proposed screening rule and the *nearly* identical "correlation decay" property considered in Loh and Wainwright (2013) and references therein.  The work of Loh and Wainwright is referenced but not cited in the text.  This oversight is curious since Loh and Wainwright provide a probabilistic bound of correct reconstruction using the nodewise method considered in the present paper.  
This reviewer feels that the experimental results are lacking and too much material is referenced in the supplement.  In particular, the authors claim experiments on real world data (L:228).  However, the real world experiment is a single gene interaction network on which only the node-wise method is performed, and is entirely contained in the supplement (B.6).  Moreover, the real world experiment is a small graph for which screening only yields a 20% speed improvement.  This is an unfortunate omission as more detailed experimentation of real world data would have been beneficial.
In addition to the real world experiment, other experimental details are deferred to the supplement or not discussed at all.  Discussion of model selection is omitted and references B.4, which in turn provides only a few sentences and references Liu et al. (2010).  Approximations are only compared to exact inference in a single experiment (also in the supplement) for which exact computation is computed in 90s.  Finally, inclusion of the "mixed" approach which uses NW for model selection and PL for estimation is both slower than PL and less accurate than NW, it is unclear why this approach would be considered.