Primal and Dual Combinatorial Dimensions
This work addresses foundational theoretical gaps in learning theory by providing precise dimensional relationships, though it is incremental as it extends existing results.
The paper establishes tight bounds between primal and dual combinatorial dimensions, such as pseudo-dimension and fat-shattering dimension, for multi-valued function classes, generalizing a known bound from binary to multi-valued cases.
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.