# The dependence of learning generalization bounds on the dimension of the instance space

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

• 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$
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.