What is usually the next step after showing the VC dimension?

Question

I am new to statistical learning. I have a structure $X$ where I showed its hypothesis class $H$ has VC dimension $d$. All I know now is that I can bound the number of examples by $m\geq \frac{1}{\epsilon}ln \frac{d}{\delta}$ and with probability at least $1-\delta$ I will get a hypothesis with error at most $\epsilon$.

My question concerns what is usually the next step(s),with regard to the big picture of learning a structure $X$, after showing its VCD?

I thought about studying other complexity measures for $X$ but wish to hear others suggestions.

Answer 1

A distinction should be made between constructing practical machine learning algorithms and theoretical algorithms, such as PAC learning algorithms. A machine learning practitioner doesn't usually invoke the concept of VC dimension — indeed, many of them probably have never heard of it, especially if they're applying machine learning in some other subject. While VC dimension might be useful in coming up with algorithms (as in the case of SVMs), it appears to have no practical import.

When constructing theoretical algorithms such as learning algorithms under the PAC model, the story could be different, but unfortunately I don't know too much about that. From the little I've seen, VC dimension doesn't get mentioned even there. In fact, it seems that VC dimension is mentioned mostly in literature attempting to relate it to other parameters.

Answer 2

If, as you've stated, you're interested in coming up with a PAC learning algorithm then finite VC-dimension is a prerequisite. This follows from what is sometimes referred to as the Fundamental Theorem of Statistical Learning Theory. In brief this results says that if a concept class $C$ has finite VC-dimension $d$ then a learning algorithm that produces a hypothesis $h \in C$ consistent with a sample $S$ of size $m$ is a PAC learning algorithm, where $$ m \ge c_0 \left(\frac{1}{\epsilon}\log{\frac{1}{\delta}} + \frac{d}{\epsilon}\log{\frac{1}{\epsilon}}\right). $$ Notice that we haven't made any reference to time taken by the learning algorithm, instead we've placed a bound on the number of samples required. This is why I said prerequisite, since obviously no algorithm running in polynomial time could make use of more than a polynomial number of samples.

My favorite reference for this result is the book An Introduction Computational Learning Theory by Kearns and Vazirani, although I much prefer the shifting proof of the Sauer-Shelah Lemma to the more common inductive approach they use. It appears as Theorem 3.3. They then go on to show (Theorem 3.5) that this result is tight within a factor of $\log{\frac{1}{\epsilon}}$.