The problem of learning tree-structured Gaussian graphical models from 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 universally, the extremal tree structures which maximize and
minimize the error exponent are the star and the Markov chain for any fixed set
of correlation coefficients on the edges of the tree. 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.