Here is a popular generalization bound:

If $X$ is the input space and $Y=\{0, 1\}$ is the output/label space, and there is a joint distribution $D$ defined on this space. We sample $m$ points from this joint distribution as observation/training data: $S = ((x_1, y_1)\ldots(x_m,y_m)) \in (X\times Y)^m$. Suppose $H$ is a class we (user) are choosing from, and $h \in H$.

Define the risk (true expected error) as $$L_D(h) := \Pr_{(x,y)\sim D} [h(x)\neq y]$$ the empirical risk as $$L_S(h) := \frac{1}{m}\sum_{i=1}^m l(h,z_i)$$ where $z_i = (x_i, y_i)$.

Then, with probability of at least $1 − \delta$ we have $$\forall h\in H, L_D(h) \leq L_S(h) + c\sqrt{\frac{VCdim(H)+ \log(2/\delta)}{2m}} $$

Question: Any intuition why the dimension of instance space $X$ and its size $|X|$ do not come into play in this inequality? Intuitively the bigger the dimension is, the harder the estimation problem should be. (E.g. $X = \mathbb{R}^d$, $|\mathbb{R}|=\infty$ should be harder than $|\{x\}|=1$.)


I think the VC-dimension term pretty much takes care of it. You can think of three cases:

  • The hypothesis space $H$ is far more "complex" than the input space $X$
  • $H$ and $X$ are matched up well to each other
  • $H$ is much "simpler" than $X$

We are usually only motivated by the second and third cases, so the VC-dimension term in your bound captures what we care about.

For example in $X=\mathbb{R}^d$, you probably want to choose a hypothesis class that depends on $d$, for instance halfspaces in $\mathbb{R}^d$, and so $d$ shows up in the VC-dimension term (in the case of halfspaces, this is $d+1$).

There are also some examples of classes with finite VC-dimension that are still interesting. Here even if $X$ is "large" or complex, we can get a small bound.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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