Primal and dual combinatorial dimensions

Pieter Kleer, Hans Simon

Research output: Contribution to journalArticleScientificpeer-review

3 Citations (Scopus)

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 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.

Original languageEnglish
Pages (from-to)185-196
Number of pages12
JournalDiscrete Applied Mathematics
Volume327
Early online dateDec 2022
DOIs
Publication statusPublished - 15 Mar 2023

Keywords

  • Dual dimension
  • Fat-shattering dimension
  • Pseudo-dimension
  • VC dimension

Fingerprint

Dive into the research topics of 'Primal and dual combinatorial dimensions'. Together they form a unique fingerprint.

Cite this