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

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

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

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

<p>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.</p>

CC BY-SA 3.0
2016-02-26T05:34:18.233Z
2016-02-26T05:34:18.233Z
usul
<p>Here is a popular generalization bound:</p>

<blockquote>
  <p>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$. </p>
  
  <p>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)$. </p>
  
  <p>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}} $$</p>
</blockquote>

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

<machine-learning><lg.learning>
The dependence of learning generalization bounds on the dimension of the instance space
Daniel
# The dependence of learning generalization bounds on the dimension of the instance space

(Asked by: username_0 on 2016-02-25)

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

**Tags:** machine-learning, lg.learning


---

## 1 answers

### Answer by username_1 on 2016-02-26. Score: 2 | Accepted answer

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.


---

