hide
Free keywords:
Mathematics, Combinatorics, math.CO,Computer Science, Discrete Mathematics, cs.DM,Computer Science, Learning, cs.LG
Abstract:
We give tight bounds on the relation between the primal and dual of various
combinatorial dimensions, such as the pseudo-dimension and fat-shattering
dimension, for multi-valued function classes. These dimensional notions play an
important role in the area of learning theory. We first review some (folklore)
results that bound the dual dimension of a function class in terms of its
primal, and after that give (almost) matching lower bounds. In particular, we
give an appropriate generalization to multi-valued function classes of a
well-known bound due to Assouad (1983), that relates the primal and dual
VC-dimension of a binary function class.
