Abstract
We study the problem of learning a tree graphical model from samples such that low-order marginals are accurate. We define a distance (``small set TV" or ssTV) between distributions P and Q by taking the maximum, over all subsets S of a given size, of the total variation between the marginals of P and Q on S. Approximating a distribution to within small ssTV allows making predictions based on partial observations. Focusing on pairwise marginals and tree-structured Ising models on p nodes, we give an algorithm that produces a distribution (from the same class) with ssTV at most eta using log p / eta^2 IID samples. We also prove a matching lower bound showing that this sample complexity is optimal. In contrast to the problem of learning the tree structure itself, there is no dependence on the strength of edge interactions. Thus, even when there are far too few samples to recover the correct tree, it is possible to learn an incorrect tree that is useful. The time complexity of the proposed algorithm is on the order of p^2, dominated by the computation of pairwise correlations.
Joint work with Mina Karzand.