Learning and Testing Latent-Tree Ising Models Efficiently
This work addresses a specific problem in statistical inference for hidden variable models, offering incremental improvements for researchers in machine learning and statistics.
The paper tackles the problem of learning and testing latent-tree Ising models observed only at leaf nodes, providing efficient algorithms that improve on prior work in terms of time and sample complexity, with concrete gains in sample efficiency for testing.
We provide time- and sample-efficient algorithms for learning and testing latent-tree Ising models, i.e. Ising models that may only be observed at their leaf nodes. On the learning side, we obtain efficient algorithms for learning a tree-structured Ising model whose leaf node distribution is close in Total Variation Distance, improving on the results of prior work. On the testing side, we provide an efficient algorithm with fewer samples for testing whether two latent-tree Ising models have leaf-node distributions that are close or far in Total Variation distance. We obtain our algorithms by showing novel localization results for the total variation distance between the leaf-node distributions of tree-structured Ising models, in terms of their marginals on pairs of leaves.