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