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

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.

• As far as I know, in real life you don't compute the VC dimension at all, and you just try various learning algorithms. Do you mean what is the next step in designing a theoretical learning algorithm? Jan 22 '14 at 14:18
• @YuvalFilmus uh that seems strong statement to me. I know VCD is important for the learnability of a given structure. There are some algorithms proposed in the literature for learning $X$. Do not know how they supposed to change in the light of knowing the VCD. Jan 22 '14 at 15:08
• From the point of view of a machine learning practitioner, as far as I can tell (I'm not one myself) VC dimension never gets mentioned. It's a purely theoretical concept. Vapnik claims it helped him think of Support Vector Machines, which are definitely useful in practice. Jan 22 '14 at 15:52
• @YuvalFilmus Thanks.. so the usual next step is get real and propose a learning algorithm $L$ then check whether $L$ in practice requires $d$ examples or even less. Jan 22 '14 at 16:27
• It depends on your perspective. If you're trying to solve a real-world problem, you'll never have gotten to the stage of computing the VC dimension. If you're trying to design a theoretical learning algorithm, say a PAC learning algorithm, then VC dimension might be helpful - I've no idea. The real question is: what is your end goal? Jan 22 '14 at 19:16

## 2 Answers

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.

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