We present novel information-theoretic limits on detecting sparse changes in Ising models, a problem that arises in many applications where network changes can occur due to some external stimuli. We show that the sample complexity for detecting sparse changes, in a minimax sense, is no better than learning the entire model even in settings with local sparsity. This is a surprising fact in light of prior work rooted in sparse recovery methods, which suggest that sample complexity in this context scales only with the number of network changes. To shed light on when change detection is easier than structured learning, we consider testing of edge deletion in forest-structured graphs, and high-temperature ferromagnets as case studies. We show for these that testing of small changes is similarly hard, but testing of large changes is well-separated from structure learning. These results imply that testing of graphical models may not be amenable to concepts such as restricted strong convexity leveraged for sparsity pattern recovery, and algorithm development instead should be directed towards detection of large changes.

First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. This paper reduces a broad class of machine learning problems involving latent variables to the problem of finding anchors defining the conical hull of the data (via the method of moments). In addition, it proposes a new divide-and-conquer algorithm based on random projections to speed up the search for the anchors. Overall, I found this an interesting paper presenting significant contributions. However the presentation could be greatly improved as it lacks clarity here and there. It looks like this paper was squeezed in a hurry to fit the 8-page limit.

Understanding the principles of causal inference in the visual system has a long history at least since the seminal studies by Albert Michotte.

Perhaps a log-log plot would be better. Q2: Please summarize your review in 1-2 sentences This is a well-written and clear paper, but I think the proposed method is well understood by the graphical models community and is not that original. I also feel that the experiments section was not objective enough - both the strengths and the weakness of a method need to be discussed by the authors.

Neural Information Processing Systems http://nips.cc/

Neural Information Processing Systems http://nips.cc/

Neural Information Processing Systems http://nips.cc/

Neural Information Processing Systems http://nips.cc/