Finite VC dimension > the number of free parameters

Question

I'm looking for an example of the following:

A hypothesis class $\mathcal{H}$ such that

• $\forall h \in \mathcal{H}$, the number of free parameters of $h$ is equal to $n \in \mathbb{N}$ (where $n < \infty$); and
• The VC dimension of $\mathcal{H}$ satisfy $\text{VC-dim}(\mathcal{H}) > n$.

I'm only familiar with classes s.t. $\text{VC-dim}(\mathcal{H}) \le n$.

Answer 1

Here's a classic example. For $\alpha>0$, define $f_\alpha(x)=\sin(\alpha x)$ and let $F$ be the collection of all functions $f_\alpha$ thresholded at $0$ --- that is, every $h \in F$ is the sign function composed with some $f_\alpha$. Then every member of $F$ is fully specified by a single parameter, $\alpha$, but $F$ has infinite VC-dim. (A stronger statement, concerning the fat-shattering dimension of the unthresholded class, is proven in Theorem 9 here: https://www.cs.bgu.ac.il/~karyeh/fat-add.pdf ).