Decentralized Learning of Tree-Structured Gaussian Graphical Models from Noisy Data

This paper studies the decentralized learning of tree-structured Gaussian\ngraphical models (GGMs) from noisy data. In decentralized learning, data set is\ndistributed across different machines (sensors), and GGMs are widely used to\nmodel complex networks such as gene regulatory networks and social networks.\nThe proposed decentralized learning uses the Chow-Liu algorithm for estimating\nthe tree-structured GGM.\n In previous works, upper bounds on the probability of incorrect tree\nstructure recovery were given mostly without any practical noise for\nsimplification. While this paper investigates the effects of three common types\nof noisy channels: Gaussian, Erasure, and binary symmetric channel. For\nGaussian channel case, to satisfy the failure probability upper bound $\\delta >\n0$ in recovering a $d$-node tree structure, our proposed theorem requires only\n$\\mathcal{O}(\\log(\\frac{d}{\\delta}))$ samples for the smallest sample size\n($n$) comparing to the previous literature \\cite{Nikolakakis} with\n$\\mathcal{O}(\\log^4(\\frac{d}{\\delta}))$ samples by using the positive\ncorrelation coefficient assumption that is used in some important works in the\nliterature. Moreover, the approximately bounded Gaussian random variable\nassumption does not appear in \\cite{Nikolakakis}. Given some knowledge about\nthe tree structure, the proposed Algorithmic Bound will achieve obviously\nbetter performance with small sample size (e.g., $< 2000$) comparing with\nformulaic bounds. Finally, we validate our theoretical results by performing\nsimulations on synthetic data sets.\n