Paper ID: | 8139 |
---|---|

Title: | Structure Learning with Side Information: Sample Complexity |

This paper studies the problem of "simultaneously learning two Ising models whose underlying graphs have some similarity constraints." The problem is interesting (and well-motivated) and the authors provide matching upper and lower bounds, with sharper characterization in some regimes. The proofs use more or less standard approaches, although applying these requires nontrivial work. Overall this is a solid contribution to NeurIPS. The authors responded to most of the reviewer's concerns. This is primarily a theoretical contribution: with a clean problem setting and tight results it has a certain aesthetic appeal which will be appreciated by NeurIPS attendees working on graphical models. The reviewers raised several concerns, many of which were addressed by the authors' response. The authors must address these in the final version of their work. * Make more clear the relationship of these results to the recently published paper at ICASSP: this paper could perhaps be characterized as a (substantive) generalization of that work. * it is unclear what new ideas (that might find use elsewhere) were needed to show the results. While it is true that Fano's inequality is the workhorse for many minimax bounds, their response claims their "choices and the techniques for analyzing the minimax rate are different" without really clarifying what this difference is or whether the choices give some insight into structural aspects of the problem. Since the upper and lower bounds differ, the lower bounds are interesting inasmuch as they give insight into how this specific problem is hard. * There was some confusion about the experimental validation: more careful explanation here would be good. * It is not clear what the practical implications of this result are. In particular, without some understanding of the quality of recovery in the shared subgraph, why is the result interesting outside pure mathematical interest? Tying back to some of the motivating applications would complete the story.