Sample Complexity of Joint Structure Learning

Saurabh Sihag; Ali Tajer

ICASSP 2019accepted0 citations

Sample Complexity of Joint Structure Learning

Abstract

This paper considers the problem of jointly recovering the structures of two graphical models with unknown edge structures. It is assumed that both graphs have the same number of nodes and a known subset of nodes have identical structures in both graphs. The classes of Ising models and Gaussian models are considered. For Ising models, the objective is to recover the connectivity of both graphs under an approximate recovery criterion. For Gaussian models, the objectives of edge structure recovery and inverse covariance estimation are considered. Information-theoretic bounds on the sample complexity for bounded probability of error under the aforementioned criteria are established and compared with the corresponding bounds on the sample complexity for recovering the graphs independently.

BibTeX

@inproceedings{icassp2019_samplecomplexity,
  title = {Sample Complexity of Joint Structure Learning},
  author = {Saurabh Sihag and Ali Tajer},
  booktitle = {ICASSP 2019},
  year = {2019}
}