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



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.