Questions: VC Dimension Theory

Question 1

A hypothesis class H has VC dimension d. What is the minimum number of samples needed to PAC-learn this class with error epsilon and confidence delta?

• A. O(log(1/delta) / epsilon^2)
• B. O((d log(1/epsilon) + log(1/delta)) / epsilon^2)
• C. O(d^2 * epsilon * delta)
• D. O(1/epsilon)

Answer: (B)

The sample complexity for PAC learning is Theta((d + log(1/delta)) / epsilon^2) or equivalently O((d + log(1/delta)) / epsilon^2). This shows that the number of samples scales linearly with VC dimension d, logarithmically with the confidence parameter 1/delta, and inversely with the square of the accuracy parameter epsilon. The 1/epsilon^2 dependence comes from concentration inequalities; the log(1/delta) captures the confidence boosting that requires extra samples.

Question 2

If a hypothesis class has infinite VC dimension, what can we conclude about its learnability in the PAC framework?

• A. It is not PAC-learnable — the sample complexity bound from the VC theorem is infinite
• B. It may still be learnable under additional distributional assumptions
• C. It is definitely learnable because infinite expressiveness is always better
• D. It can only be learned if all training data are labeled perfectly

Answer: (A)

By the fundamental theorem of statistical learning, a hypothesis class is PAC-learnable if and only if its VC dimension is finite. Infinite VC dimension means there exist arbitrarily large shatterable sets, so the class can fit any labeling. This allows the learner to memorize the training data perfectly while generalizing terribly on test data (overfitting). Without finite VC dimension, there is no guarantee that empirical error bounds the test error uniformly over the class, which is what PAC learning requires.

Question 3

The VC dimension of linear classifiers in R^d is d+1. Explain why this dimension grows linearly with the feature space dimensionality.

Model answer: Linear classifiers use hyperplanes to separate classes. In R^d, a hyperplane is defined by d+1 parameters (coefficients plus bias). Geometrically, to shatter a set of d+1 points in general position, you can always find a hyperplane to separate any subset from the rest — you have enough 'degrees of freedom' (d+1 parameters) to encode any dichotomy. With d+2 points, some dichotomies become impossible (e.g., in R^2, you cannot linearly separate two interlocked XOR patterns). This linear growth in VC dimension with dimensionality is why high-dimensional spaces lead to high sample complexity — you need O(d/epsilon) samples in d dimensions.

This illustrates the curse of dimensionality in learning theory. As feature spaces grow, hypothesis classes typically gain capacity (higher VC dimension), requiring proportionally more data to learn. This is a fundamental tradeoff: richer hypothesis classes (more features) can express more complex concepts but demand more training data. Regularization and dimensionality reduction are practical ways to reduce VC dimension and improve sample efficiency.

Question 4

The VC dimension provides a distribution-free learning bound. Which of the following best describes what 'distribution-free' means in this context?

• A. The learning bound does not depend on the specific data distribution D, so it holds for any D (including adversarial ones)
• B. The learning bound assumes the data comes from a uniform distribution
• C. The learning bound is tighter if the data distribution is unknown
• D. The learning bound only applies to normally distributed data

Answer: (A)

Distribution-free means the VC-based PAC bound holds for any data distribution D. The same sample complexity and hypothesis class work whether D is Gaussian, uniform, sparse, or adversarially chosen. This is the strength of VC dimension theory — you get a guaranteed bound without assuming anything about the data distribution. The tradeoff is that the bound is often conservative (loose) for benign, structured distributions where tighter distribution-dependent bounds might exist.

Question 5

A hypothesis class shatters a set of 10 points but fails to shatter some set of 11 points. What is its VC dimension?

• A. Exactly 10
• B. Less than 10
• C. More than 11
• D. Exactly 11

Answer: (A)

VC dimension is the size of the largest shatterable set. If H shatters a specific 10-point set, then VC dim >= 10. If H fails to shatter some 11-point set, that tells us VC dim < 11. Combining these, VC dim = 10. Note that this reasoning requires that the 10-point set is the largest shatterable set (no larger set is shatterable by H). If another 11-point set could be shattered, VC dim would be >= 11.