# Upper bounds on the Natarajan dimensions of some function classes

arXiv: https://arxiv.org/abs/2209.07015 · HTML: https://mlsanity.com/paper/2209.07015/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 0 of its 10 references that are in the map.
- First posted on arXiv 15 Sep 2022.

## Built on by (most cited first, 8 of 8)

- [Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequality](https://mlsanity.com/paper/2212.09900/) (2022)
- [Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimization](https://mlsanity.com/paper/2307.02108/) (2023)
- [Adaptive Experimental Design for Policy Learning](https://mlsanity.com/paper/2401.03756/) (2024)
- [Sparse Mixture-of-Experts for Compositional Generalization: Empirical Evidence and Theoretical Foundations of Optimal Sparsity](https://mlsanity.com/paper/2410.13964/) (2024)
- [Statistical learning by sparse deep neural networks](https://mlsanity.com/paper/2311.08845/) (2023)
- [Information-theoretic Generalization Analysis for VQ-VAEs: A Role of Latent Variables](https://mlsanity.com/paper/2505.19470/) (2025)
- [Position: Agentic AI System Is a Foreseeable Pathway to AGI](https://mlsanity.com/paper/2605.12966/) (2026)
- [Pessimistic Risk-Aware Policy Learning in Contextual Bandits](https://mlsanity.com/paper/2605.15620/) (2026)

## Abstract (arXiv)

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.