Upper bounds on the Natarajan dimensions of some function classes

Ying Jin

Abstract

The Natarajan dimension is a fundamental tool for characterizing multi-class PAC learnability, generalizing the Vapnik-Chervonenkis (VC) dimension from binary to multi-class classification problems. This work establishes upper bounds on Natarajan dimensions for certain function classes, including (i) multi-class decision tree and random forests, and (ii) multi-class neural networks with binary, linear and ReLU activations. These results may be relevant for describing the performance of certain multi-class learning algorithms.
BibTeX
@inproceedings{jin2023upper,
  author = {Ying Jin},
  title = {{Upper bounds on the Natarajan dimensions of some function classes}},
  booktitle = {IEEE International Symposium on Information Theory (ISIT),},
  year = {2023},
  url = {https://openreview.net/forum?id=EwN0gyKeh7},
}

Loading related content...

Figure