We study the problem of learning a high-dimensional tree graphical model from samples such that low-order marginals are accurate. This enables making accurate predictions based on an observation of few variables. We give a new analysis of the classical Chow-Liu algorithm, which finds the maximum likelihood tree, in the context of a loss function capturing prediction performance. A take-home message is that the necessary number of samples is dramatically lower than is required to learn the exact underlying tree. On the technical side, this requires reasoning about predictions computed using the wrong tree.
Joint work with Mina Karzand.