# General formula for the VC Dimension of a SVM

I am interested in the question of the Vapnik–Chervonenkis (VC) dimension of Support Vector Machines (SVM). Until now, I have only found partial results related to particular cases of SVM. Some examples:

However, my belief is that we can produce some kind of general result $-$ and very abstract too $-$ on the VC Dimension of any SVM, by using two facts:

• The first example above, regarding the VC dimension of affine classifiers and hence of linear SVM, and
• The fact that a kernelized SVM works as a linear SVM applied to a higher-dimensional space $\mathcal{H}$.

In the following lines I explain my reasoning. Data $x_1, ..., x_N$ comes from some space $\mathcal{L}$ that can be thought as $\mathbb{R}^n$.

Let $K$ be some kernel. Let first define: $$\Phi(K) = \{\phi: K(x,y) = \phi(x)\cdot\phi(y), \; (x,y) \in \mathcal{L} \times \mathcal{L}, \; \phi:\mathcal{L} \rightarrow \mathcal{H}\}$$

$\Phi(K)$ is the set of all feature mappings that can be associated to kernel $K$ $-$ i.e. the set of all mappings implicitly defined by $K$; for an example of multiple mappings associated to a single kernel see (Burges, 1998), page 17, where $K(x,y)=(x \cdot y )^2.$

Now, letting $\Phi_K \equiv \Phi(K)$, we define:

$$H(\Phi_K) = \{\mathcal{H}: \phi \in \Phi(K)\}$$

$H(\Phi_K)$ is the set of higher-dimensional spaces $\mathcal{H}$ "generated" by $\Phi(K)$ $-$ each mapping $\phi$ is associated to a space $\mathcal{H}$; $H(\Phi_K)$ is simply the set of all these spaces.

We now define:

$$d_K^{\,\min} = \min_{\mathcal{H} \,\in \, H(\Phi_K)} dim(\mathcal{H})$$

$d_K^{\,\min}$ is simply the dimension of the space $\mathcal{H} \in H(\Phi_K)$ with minimal dimension.

Finally, let $f_K$ be a SVM equipped with a kernel $K$. Given that the underlying mechanism of a kernelized SVM is to classify data in a higher-dimensional space $-$ i.e. $dim(\mathcal{L}) \leq dim(\mathcal{H})$ $-$ where it is linearly separable and using the fact that the VC Dimension of affine classifiers in $n$ dimensions is $n+1$, my claim is:

Claim: The VC Dimension of a SVM $f_K$ equipped with kernel $K$ can be defined as $d_K^{\,\min}+1$.

Of course, I have arbitrarily chosen $d_K^{\,\min}$ $-$ we could for example have defined and chosen $d_K^{\,\max}$ instead $-$ but the minimum choice seems the most sensible one.

As I haven't read anything similar to this claim in SVM related sources, I was wondering what might be wrong with it. Does it make sense? Am I making any mistakes in my reasoning?

• I know this questions hasn't been active in years, but could share any news on this? Thanks! Commented Dec 21, 2020 at 14:07
• @nullgeppetto Does my answer make sense? Commented Oct 5, 2022 at 10:23

Your Claim: The VC Dimension of a SVM $$f_K$$ equipped with kernel $$K$$ can be defined as $$d^{any}_K+1$$.
Now, Just consider $$K=(x.y)^2$$ with transformation $$\phi(x) = \begin{pmatrix} x_1^2 \\ \sqrt{2} x_1x_2 \\ x_2^2 \end{pmatrix}$$.
Just check that, $$\nexists x$$ $$(=(x_1, x_2))$$ s.t $$\phi(x) = \begin{pmatrix} x_1^2 \\ \sqrt{2} x_1x_2 \\ x_2^2 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}$$
Essentially, higher-dimensional space $$\mathcal{H}$$ generated through any mapping $$\phi$$ is a "restrictive" space, in the sense that not all points exists in that space. There needs to be a separate proof for VC-dimension in these "restricted" spaces and we may need to proof it for different kernels.
(I hope you got my point, above $$K$$ and $$\phi$$ are just examples to get this point across)