# 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

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