Let $H$ be a hypothesis class of multiclass predictors; namely, each $h\in H$ is a function from $X$ to $[k]$.

Denote the Natarajan dimension of $H$ by $Ndim(H)$. Hope you can give me an intuitive proof of the following lemma .

$|H|\le |X|^{Ndim(H)}\cdot k^{2Ndim(H)}$

The lemma is in the book "Understanding Machine Learning: from theory to algorithms". You just search keywords "Lemma 29.4".


1 Answer 1


You can check Natarajan, On learning sets and functions or Haussler and Long, A generalization of Sauer's lemma.

  • $\begingroup$ Thank you. But those proofs are very complex, making me really sleepy. Could you give me an intuitive proof? $\endgroup$
    – Ben
    Commented Nov 23, 2019 at 0:16
  • $\begingroup$ If you don’t like proofs, you can just accept the validity of the statement. I don’t expect there to be simpler proofs around of the lemma. $\endgroup$ Commented Nov 23, 2019 at 7:45

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.