# Tree Learning: Optimal Algorithms and Sample Complexity

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 26 references that are in the map.
- First posted on arXiv 9 Feb 2023.

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

- [Hierarchical Clustering with Structural Constraints](https://mlsanity.com/paper/1805.09476/) (2018)
- [Adaptive Hierarchical Clustering Using Ordinal Queries](https://mlsanity.com/paper/1708.00149/) (2017)
- [Maximizing Agreements for Ranking, Clustering and Hierarchical Clustering via MAX-CUT](https://mlsanity.com/paper/2102.11548/) (2021)

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

- [Optimal VC Dimension of Contrastive Learning with Margin](https://mlsanity.com/paper/2609.38834/) (2026)

## Abstract (arXiv)

We study the problem of learning a hierarchical tree representation of data from labeled samples, taken from an arbitrary (and possibly adversarial) distribution. Consider a collection of data tuples labeled according to their hierarchical structure. The smallest number of such tuples required in order to be able to accurately label subsequent tuples is of interest for data collection in machine learning. We present optimal sample complexity bounds for this problem in several learning settings, including (agnostic) PAC learning and online learning. Our results are based on tight bounds of the Natarajan and Littlestone dimensions of the associated problem. The corresponding tree classifiers can be constructed efficiently in near-linear time.