Technical Program

Paper Detail

Paper Title Structure Learning of Similar Ising Models: Information-theoretic Bounds
Paper IdentifierTU4.R5.3
Authors Saurabh Sihag, Ali Tajer, Rensselaer Polytechnic Institute, United States
Session Graphical Models
Location Saint Victor, Level 3
Session Time Tuesday, 09 July, 16:40 - 18:00
Presentation Time Tuesday, 09 July, 17:20 - 17:40
Manuscript  Click here to download the manuscript
Abstract This paper considers the problem of estimating the structures of a pair of structurally similar graphs associated with two distinct Ising models. It is assumed that the graphs have the same number of nodes with unknown structures, with the additional side information that a known subset of nodes have identical structures (connectivity) in both graphs. The objective is recovering the structures of both graphs exactly. The bounded degree and bounded edge sub-classes of Ising models are investigated, and necessary and sufficient conditions on the sample complexity for bounded probability of error under the two criteria are established. Furthermore, the results are compared with the conditions on the sample complexity of recovering the graphs independently. One major observation is that by judicially leveraging the information about the identical sub-graphs by jointly recovering both structures, the sample complexity reduces by a factor cp^2, where p is the number of nodes in the graph and c is some constant.