Primal and Dual Combinatorial Dimensions

Pieter Kleer, Hans Simon

Research output: Working paperOther research output


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.
Original languageEnglish
Place of PublicationIthaca
PublisherCornell University Library
Number of pages12
Publication statusPublished - Aug 2021

Publication series



Dive into the research topics of 'Primal and Dual Combinatorial Dimensions'. Together they form a unique fingerprint.

Cite this