# Robustifying Algorithms of Learning Latent Trees with Vector Variables

arXiv: https://arxiv.org/abs/2106.00885 · HTML: https://mlsanity.com/paper/2106.00885/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 27 references that are in the map.
- First posted on arXiv 2 Jun 2021.

## Builds on (most cited first, 6 of 6)

- [Robust estimation of tree structured Gaussian Graphical Model](https://mlsanity.com/paper/1901.08770/) (2019)
- [Robust High Dimensional Sparse Regression and Matching Pursuit](https://mlsanity.com/paper/1301.2725/) (2013)
- [SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples](https://mlsanity.com/paper/2101.08917/) (2021)
- [Guaranteed Scalable Learning of Latent Tree Models](https://mlsanity.com/paper/1406.4566/) (2014)
- [Spectral neighbor joining for reconstruction of latent tree models](https://mlsanity.com/paper/2002.12547/) (2020)
- [Robust estimation of tree structured models](https://mlsanity.com/paper/2102.05472/) (2021)

## Built on by (most cited first, 2 of 2)

- [Active-LATHE: An Active Learning Algorithm for Boosting the Error Exponent for Learning Homogeneous Ising Trees](https://mlsanity.com/paper/2110.14341/) (2021)
- [Robust Model Selection of Gaussian Graphical Models](https://mlsanity.com/paper/2211.05690/) (2022)

## Abstract (arXiv)

We consider learning the structures of Gaussian latent tree models with vector observations when a subset of them are arbitrarily corrupted. First, we present the sample complexities of Recursive Grouping (RG) and Chow-Liu Recursive Grouping (CLRG) without the assumption that the effective depth is bounded in the number of observed nodes, significantly generalizing the results in Choi et al. (2011). We show that Chow-Liu initialization in CLRG greatly reduces the sample complexity of RG from being exponential in the diameter of the tree to only logarithmic in the diameter for the hidden Markov model (HMM). Second, we robustify RG, CLRG, Neighbor Joining (NJ) and Spectral NJ (SNJ) by using the truncated inner product. These robustified algorithms can tolerate a number of corruptions up to the square root of the number of clean samples. Finally, we derive the first known instance-dependent impossibility result for structure learning of latent trees. The optimalities of the robust version of CLRG and NJ are verified by comparing their sample complexities and the impossibility result.