From Book: VC dimension (Vapnik, 1998)

VC dimension (Vapnik-Chervonenkis dimension) is based on the foundational work by Vladimir Vapnik and Alexey Chervonenkis (1971, with key refinements in Vapnik's 1998 book "Statistical Learning Theory"):

---

1. What is VC Dimension?

The VC dimension is a measure of the capacity (complexity) of a hypothesis class (e.g., neural networks, decision trees). It quantifies the largest set of points that a model can shatter (classify correctly for all possible labelings).

• Key Idea: A model with high VC dimension can fit more complex patterns but risks overfitting.

• Formal Definition:
  A hypothesis class $\mathcal{H}$ has VC dimension $d$ if there exists a set of $d$ points that can be shattered by $\mathcal{H}$, but no set of $d+1$ points can be shattered.

---

2. Intuitive Example

Example: Linear Classifiers in 2D

• VC dimension = 3: Can shatter any 3 non-collinear points (all $2^3=8$ labelings).

• But fails for 4 points: No line can classify all $2^4=16$ labelings of 4 points (e.g., XOR problem).

Linear classifiers shatter 3 points but not 4 (VC dim = 3).

---

3. Key Theorems

(1) Generalization Bound

Vapnik’s theorem links VC dimension to generalization error:

$$\text{Test Error}\le \text{Train Error}+\mathcal{O}\left(\sqrt{\frac{d+\log (1\mathrm{/}\delta )}{n}}\right)$$

where:

• $d$ = VC dimension,

• $n$ = sample size,

• $\delta$ = confidence level.

Interpretation:

• Higher $d$ → Larger gap between train/test error (risk of overfitting).

• To generalize well, ensure $n\gg d$.

(2) Sample Complexity

The number of samples needed for good generalization scales with VC dimension:

$$n=\mathrm{\Omega }\left(\frac{d+\log (1\mathrm{/}\delta )}{{ϵ}^2}\right)$$

where $ϵ$ is the desired error tolerance.

---

4. VC Dimension of Common Models

Model	VC Dimension
Linear classifiers (ℝᵈ)	$d+1$
Neural Networks
Decision Trees	Grows with tree depth
SVM (RBF kernel)	Infinite (but still generalizes!)

---

5. Why VC Dimension Matters

• Model Selection: Prefer models with lower VC dimension for small datasets.

• Explains Overfitting: High VC dimension → Need more data to generalize.

• Theoretical Foundation: Basis for PAC learning theory.

---

6. Limitations

• Loose Bounds: VC bounds are often too pessimistic (e.g., SVMs generalize despite infinite VC dim).

• Modern Extensions:

  • Rademacher Complexity: Tighter bounds for today’s models.

  • Implicit Bias: Gradient descent favors "simple" solutions even in high-capacity models.

---

7. Example: Calculating VC Dimension

Problem: Prove that linear classifiers in ℝ² have VC dimension 3.
Proof:

1. Shattering 3 points: For any 3 non-collinear points, all $2^3=8$ labelings can be achieved by a line.

2. Cannot shatter 4 points: No line can classify the XOR labeling of 4 points.

---

8. Original Paper & Resources

• Foundational Paper:
  Vapnik & Chervonenkis (1971), "On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities".

• Modern Treatment:
  Vapnik (1998), "Statistical Learning Theory" (Chapter 4).

• Interactive Tutorial: VC Dimension Explained Visually.

---

Key Takeaway

VC dimension formalizes the tradeoff between model complexity and generalization, laying the groundwork for modern ML theory. While newer tools (e.g., Rademacher complexity) refine these ideas, VC theory remains fundamental.

Related: 

VC Bounds: A Formal Explanation of Generalization

VC (Vapnik-Chervonenkis) bounds are theoretical guarantees that predict how well a machine learning model will generalize to unseen data, based on its VC dimension (a measure of model complexity). Introduced by Vapnik and Chervonenkis in the 1970s, these bounds connect model capacity, training data size, and generalization error.

---

1. Core Idea of VC Bounds

VC bounds quantify the worst-case gap between training error and test error for a hypothesis class $\mathcal{H}$. They show that:

• Models with high VC dimension (complexity) need more data to generalize well.

• Models with low VC dimension (simplicity) generalize even with less data.

---

2. Key VC Inequality

The most celebrated VC bound states that with probability $1-\delta$:

$$\text{Test Error}\le \text{Training Error}+\mathcal{O}\left(\sqrt{\frac{d+\log (1\mathrm{/}\delta )}{n}}\right)$$

where:

• $d$ = VC dimension of $\mathcal{H}$,

• $n$ = number of training samples,

• $\delta$ = confidence level (e.g., 0.05 for 95% confidence).

Interpretation:

• The term $\sqrt{\frac{d}{n}}$ is the generalization gap.

• If $d$ is large, you need $n\gg d$ to keep the gap small.

---

3. Intuition Behind the Bound

• Shattering: If a model can fit all possible labelings of $d$ points, its VC dimension is $\ge d$.

• Overfitting Risk: High VC dimension means the model can memorize noise, leading to poor generalization.

• Sample Complexity: To ensure generalization, the number of samples $n$ must grow with $d$.

Example:

• A linear classifier in ${\mathbb{R}}^2$ has VC dimension $d=3$.

• If $n=1000$, the VC bound ensures the test error is close to training error.

• If $n=10$, the bound becomes loose (high risk of overfitting).

---

4. VC Bound for Classification (Formal)

For a binary classifier $h\in \mathcal{H}$ with VC dimension $d$, with probability $1-\delta$:

$$\text{Generalization Error}\le \text{Empirical Error}+\sqrt{\frac{d(\log \left(\frac{2n}{d}\right)+1)+\log \left(\frac{4}{\delta }\right)}{n}}$$

This shows that:

• The gap shrinks as $n\to \mathrm{\infty }$.

• The gap grows with $d$.

---

5. Practical Implications

(1) Model Selection

• Prefer simpler models (low $d$) when data is scarce.

• Deep learning paradox: Modern neural networks have huge $d$ but still generalize (due to implicit regularization).

(2) Sample Size Estimation

To achieve generalization error $ϵ$, you need roughly:

$$n\approx \frac{d}{{ϵ}^2}$$

Example: If $d=100$ and $ϵ=0.1$, $n\approx 10,\text{\hspace{0.17em}⁣}000$.

(3) Structural Risk Minimization (SRM)

Vapnik’s framework for model selection:

1. Choose a hierarchy of models ${\mathcal{H}}_1\subset {\mathcal{H}}_2\subset \dots$ with increasing $d$.

2. Pick the model that minimizes:

   $$\text{Training Error}+\text{VC Penalty Term}$$

---

6. Limitations of VC Bounds

• Overly Pessimistic: Actual generalization is often better than VC bounds predict (e.g., deep nets).

• Doesn’t Explain SGD: Modern training relies on optimization dynamics, not just hypothesis class.

• Alternative Theories:

  • Rademacher Complexity: Tighter bounds for specific data distributions.

  • PAC-Bayes: Incorporates prior knowledge.

---

7. Example: VC Bound Calculation

Problem: A model has VC dimension $d=50$. How many samples $n$ are needed to ensure the generalization gap is $\le 0.1$ with 95% confidence?

Solution:
Using the simplified bound $ϵ\approx \sqrt{\frac{d}{n}}$:

$$0.1\ge \sqrt{\frac{50}{n}}⟹n\ge \frac{50}{0.1^2}=5,\text{\hspace{0.17em}⁣}000$$

---

8. Key Papers & Resources

• Original VC Paper:
  Vapnik & Chervonenkis (1971), "On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities".

• Modern Treatment:
  Vapnik (1998), "Statistical Learning Theory" (Chapter 4).

• Visual Guide: VC Dimension Explained.

---

Summary

VC bounds provide worst-case guarantees on generalization, showing that:
✅ Simpler models generalize better with limited data.
✅ Complex models need exponentially more data.
✅ Inspired modern theory (e.g., Rademacher complexity).

No Link as this is a book?

Link: