Tree Learning: Optimal Algorithms and Sample Complexity

Dmitrii Avdiukhin, Grigory Yaroslavtsev, Danny Vainstein, Orr Fischer, Sauman Das +1 more
2/9/2023
cs.LG

No confident code implementation found for this paper. 2 possible matches can be shown below.

Abstract

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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. 2 weaker matches are hidden by default — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Optimal Sample Complexity of Contrastive Learning

83% match2026

Learning accurate and interpretable tree-based models

81% match2024

Optimal estimation of Gaussian (poly)trees

80% match2024

On Computing Optimal Tree Ensembles

80% match2023

Learning-Augmented Hierarchical Clustering

80% match2025

Nearly Optimal Sample Complexity for Learning with Label Proportions

79% match2025

Cite this paper

@article{avdiukhin2023tree,
  title  = {Tree Learning: Optimal Algorithms and Sample Complexity},
  author = {Dmitrii Avdiukhin and Grigory Yaroslavtsev and Danny Vainstein and Orr Fischer and Sauman Das and Faraz Mirza},
  year   = {2023},
  eprint = {2302.04492},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2302.04492v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2302.04492.svg)](https://codeofpaper.com/paper/2302.04492)

Discussion