Learning Gaussian Tree Models: Analysis of Error Exponents and Extremal Structures

Abstract

The problem of learning tree-structured Gaussian graphical models from independent and identically distributed (i.i.d.) samples is considered. The influence of the tree structure and the parameters of the Gaussian distribution on the learning rate as the number of samples increases is discussed. Specifically, the error exponent corresponding to the event that the estimated tree structure differs from the actual unknown tree structure of the distribution is analyzed. Finding the error exponent reduces to a least-squares problem in the very noisy learning regime. In this regime, it is shown that the extremal tree structure that minimizes the error exponent is the star for any fixed set of correlation coefficients on the edges of the tree. If the magnitudes of all the correlation coefficients are less than 0.63, it is also shown that the tree structure that maximizes the error exponent is the Markov chain. In other words, the star and the chain graphs represent the hardest and the easiest structures to learn in the class of tree-structured Gaussian graphical models. This result can also be intuitively explained by correlation decay: pairs of nodes which are far apart, in terms of graph distance, are unlikely to be mistaken as edges by the maximum-likelihood estimator in the asymptotic regime.

Submitted to Transactions on Signal Processing

References in corpus (1)

• Sparse permutation invariant covariance estimation

Cited by in corpus (23)

• High-dimensional structure estimation in Ising models: Local separation criterion
• Forest Density Estimation
• A Large-Deviation Analysis of the Maximum-Likelihood Learning of Markov Tree Structures
• High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion
• Learning Graphs with Monotone Topology Properties and Multiple Connected Components
• Sparse Nonparametric Graphical Models
• Testing the Structure of a Gaussian Graphical Model with Reduced Transmissions in a Distributed Setting
• High Dimensional Structure Learning of Ising Models on Sparse Random Graphs
• Ordering for Communication-Efficient Quickest Change Detection in a Decomposable Graphical Model
• Non-submodular Function Maximization subject to a Matroid Constraint, with Applications
• Learning of Tree-Structured Gaussian Graphical Models on Distributed Data under Communication Constraints
• Predictive Learning on Hidden Tree-Structured Ising Models
• Chernoff Information between Gaussian Trees
• Optimal Rates for Learning Hidden Tree Structures
• Exact Asymptotics for Learning Tree-Structured Graphical Models with Side Information: Noiseless and Noisy Samples
• Robust estimation of tree structured Gaussian Graphical Model
• Robust estimation of latent tree graphical models: Inferring hidden states with inexact parameters
• Chernoff Information of Bottleneck Gaussian Trees
• Tree density estimation
• Bayesian learning of forest and tree graphical models
• Decentralized Learning of Tree-Structured Gaussian Graphical Models from Noisy Data
• SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples
• Learning Graphs from Linear Measurements: Fundamental Trade-offs and Applications