Tree Learning: Optimal Algorithms and Sample Complexity - Hierarchical Clustering and PAC Learning

Explore the intricacies of hierarchical tree representation learning in this Google TechTalk presented by Dmitrii Avdyukhin. Delve into optimal sample complexity bounds for various learning settings, including PAC learning and online learning. Discover how tight bounds of Natarajan and Littlestone dimensions contribute to the problem's solution. Learn about efficient tree classifier construction methods that operate in near-linear time. Gain insights into hierarchical clustering, practical algorithms, and applications in phylogenetic trees. Examine the challenges of classification in hierarchical clustering settings and understand the nuances of PAC Learning algorithms and sample complexity. Investigate the generalization of VC dimension, Natarajan dimension for hierarchical clustering, and tree building techniques. Explore non-binary trees, k-tuples, non-realizable cases, and online settings to broaden your understanding of tree learning algorithms and their sample complexity.

Intro
Hierarchical clustering (HC)
Practical HC algorithms
Application: phylogenetic tree
Almost correct tree
Our settings
Classification in HC settings
PAC Learning: Algorithm
PAC Learning: Sample Complexity
Naive generalization of VC dimension
Natarajan dimension for HC: Lower Bound
Tree Building
Choosing contradictory constraints
Proof Outline
Non-binary trees
k-tuples
Non-realizable case
Online settings
Conclusion