Primal and dual combinatorial dimensions

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 classical 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.(c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).

Automated summary

We provide tight bounds on the relation between the primal and dual of various combinatorial dimensions for multi-valued function classes. These dimensions are important in the field of learning theory. We review classical results that bound the dual dimension of a function class based on its primal, and introduce almost matching lower bounds. Furthermore, we generalize Assouad's well-known bound on primal and dual VC-dimensions of binary function classes to multi-valued function classes.