Learning latent tree models with small query complexity
Abstract
We consider the problem of structure recovery in a graphical model of a tree where some variables are latent. Specifically, we focus on the Gaussian case, which can be reformulated as a well-studied problem: recovering a semi-labeled tree from a distance metric. We introduce randomized procedures that achieve query complexity of optimal order. Additionally, we provide statistical analysis for scenarios where the tree distances are noisy. The Gaussian setting can be extended to other situations, including the binary case and non-paranormal distributions.
Fields of Study & Subjects
Data Quality and Management
Bayesian Modeling and Causal Inference
Data Mining Algorithms and Applications
Publication details
- Journal / source
- Bernoulli
- Volume
- 32
- Issue
- 4
- Pages
- 2639–2659
- Publication date
- 31 July 2026
- Language
- EN