English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse
  1. View item / 
  2. Item Summary

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Paper

Primal and Dual Combinatorial Dimensions

MPS-Authors
/persons/resource/persons45484

Simon,  Hans Ulrich
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

arXiv:2108.10037.pdf
(Preprint), 215KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Kleer, P., & Simon, H. U. (2021). Primal and Dual Combinatorial Dimensions. Retrieved from https://arxiv.org/abs/2108.10037.


Cite as: https://hdl.handle.net/21.11116/0000-0009-B834-D
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.