VC dimension covers the binary classification case, i.e. when we want to get a predictor $X \to \{0, 1\}$. Using VC dimension, we can get the upper bound on the sample complexity for PAC-learning.
In our problem, we have 3 classes, i.e. we want to train a predictor $X \to \{0, 1, 2\}$. We know a "VC dimension" for our problem, defined as the size of the largest $S$ such that all $3^{|S|}$ combinations of labels of $S$ are possible using our hypothesis space.
Question: can we get the upper bound on PAC sample complexity using this "VC dimension"?
For more than two classes, a Natarajan dimension seems to be the common approach. But we don't know it. I don't see how to upper-bound Natarajan dimension using our "VC dimension". If it's possible, ideally, I need at most a constant factor increase (e.g. Natarajan dimension ≤ 2 · "VC dimension").
