Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models
We consider the problem of learning the underlying graph of an unknown Ising model on p spins from a collection of i.i.d. samples generated from the model. We suggest a new estimator that is computationally efficient and requires a number of samples that is near-optimal with respect to previously established informationtheoretic lower-bound. Our statistical estimator has a physical interpretation in terms of "interaction screening". The estimator is consistent and is efficiently implemented using convex optimization. We prove that with appropriate regularization, the estimator recovers the underlying graph using a number of samples that is logarithmic in the system size p and exponential in the maximum coupling-intensity and maximum node-degree.
This paper deals with reconstructing the graph of an Ising model. The paper is well-written. The main effort is to improve upon the  recent results provided by Bresler, showing that the complexity of identifying the structure of max degree d Ising model is polynomial  in p and independent of d.   Strong Points:   1) The timeliness of the topic in this paper is good, meaning that there is currently ongoing interest and work on Ising model reconstruction. 2) The paper contains more or less all the necessary theoretical results (mainly in terms of sample complexity) that one would expect to see in such a draft.  3) The approach to the solution, i.e., the use of the ISO and the l_1-penalization is quite intuitive in the way that is described in the paper.  Weak points:   1) The whole approach is based on the introduction of the ISO. This is the main trick in the proposed approach. Other than that, the rest  of the method and its analysis are usual and well studied (l_1-penalization and connection with the tutorial by Negahban et. al. on M-estimators), i.e., the rest of the proposed approach is nothing but very usual and well-studied approaches and ideas.    2) Due to the previous point, the analysis is based on well-established proof techniques or even more crucially similar mathematical statements  that have been extensively derived and proposed in the related literature. 3) The authors need to highlight better the discussion in lines 166-170. 4) I would like to see more simulations demonstrating the performance of the proposed method.  Overall, I think that the paper is nice, nevertheless with the aforementioned weaknesses under consideration. 
The timeliness of the topic and the derived results are more important according to my opinion than the aforementioned weaknesses. Although normally I would not suggest publication of papers with l_1-penalization, since I think that these approaches have been extensively studied so far in literature, in this particular case I think that an exemption can be made.