  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.
