VC Dimension

From Samples to Guarantees

A learner sees only a finite labeled sample, but a PAC guarantee concerns performance on the entire underlying distribution. The central question is therefore whether the sample is capable of detecting every hypothesis that disagrees with the target on a sufficiently large part of that distribution. VC dimension supplies the capacity measure, while epsilon-nets supply the coverage argument that turns a sample into a guarantee.

Epsilon-Net Coverage

The important feature is the universal coverage requirement. The sample is not merely likely to hit one particular high-probability set. It must hit every set in the relevant class that has probability at least epsilon. This is what allows the argument to eliminate an entire collection of bad hypotheses at once.

Disagreement Class H_c

To apply epsilon-net coverage to classification, fix a target hypothesis c and compare every candidate h with c. For each h in H, form the set of domain points on which h and c disagree. The collection of all such disagreement sets is the class H_c.

The PAC Proof Trace

Assume the realizable setting: the target c belongs to H, and the sample receives labels according to c. Consider a candidate h whose true error is at least epsilon. Its disagreement set with c therefore has probability at least epsilon. If the sample is an epsilon-net for H_c, the sample intersects that disagreement set, so h makes at least one error on the labeled sample.

Because c is consistent with the sample, a hypothesis that makes a sampled error cannot be an empirical-risk minimizer. Therefore, once the sample intersects every disagreement set of probability at least epsilon, every hypothesis with true error at least epsilon is excluded from being an ERM hypothesis.

Capacity Through Shattering

A classification class is more expressive when it can realize more different labelings of data points. VC dimension measures this capacity by asking for the largest number of points that can be shattered. A set of points is shattered when every possible binary labeling of those points can be produced by some classifier in the class.

In the PAC argument, VC dimension controls the complexity of the relevant hypothesis or disagreement class. The equality between the VC dimensions of H and H_c allows the complexity of H to be carried into the epsilon-net analysis. Thus, VC dimension connects the number of distinguishable labelings to the sample size needed for a high-probability learning guarantee.

Homogeneous Halfspaces

For homogeneous halfspaces in R^d, the separating boundary is required to pass through the origin. Their VC dimension is exactly d.

For the upper bound, take any d+1 vectors in R^d. They are linearly dependent, so there are real coefficients, not all zero, whose weighted combination is the zero vector. Separate the indices with positive coefficients from those with negative coefficients. If both groups are nonempty, a weight vector that assigns the required opposite signs would create incompatible sign conditions when applied to the dependence relation. If one group is empty, the corresponding side becomes an equality and the contradiction still follows. Therefore, no d+1 vectors can be shattered by homogeneous halfspaces.

Bias Adds One Degree

Non-homogeneous halfspaces in R^d include a bias term, so their separating boundary is not required to pass through the origin. Their VC dimension is exactly d+1.

For the lower bound, use the zero vector together with the d standard basis vectors. The source proof states that this set of d+1 vectors is shattered by non-homogeneous halfspaces, paralleling the homogeneous construction for the basis vectors.

For the upper bound, suppose d+2 vectors in R^d could be shattered by non-homogeneous halfspaces. The standard reduction described in the source converts this into d+2 vectors in R^(d+1) shattered by homogeneous halfspaces. That contradicts the homogeneous result, because homogeneous halfspaces in R^(d+1) have VC dimension d+1 and cannot shatter d+2 vectors. Hence the non-homogeneous VC dimension is d+1.

Common Reasoning Errors

• Treating an epsilon-net as a guarantee about only one selected set.

  An epsilon-net must intersect every set in the relevant class whose probability is at least epsilon.

  Fix: Keep the universal requirement in view: the same sample must cover all sufficiently probable sets in the class.

• Using the original hypotheses directly without constructing the disagreement class.

  The epsilon-net argument operates on sets, while classification error is a property of hypotheses.

  Fix: Associate each h with its disagreement set with c, then use the equality between true error and the distribution probability of that set.

• Assuming that a large true error automatically prevents ERM selection.

  ERM minimizes empirical risk, so the proof must show that a large-error hypothesis makes at least one sampled error.

  Fix: Use epsilon-net coverage to force the sample to intersect the hypothesis's disagreement set.

• Forgetting the realizability condition.

  The argument relies on c being consistent with the sample, which makes a sampled-error hypothesis unable to minimize empirical risk.

  Fix: State that the guarantee is for the realizable setting and for samples labeled according to c.

• Giving both kinds of halfspaces the same VC dimension.

  Homogeneous halfspaces in R^d have VC dimension d, while non-homogeneous halfspaces have VC dimension d+1.

  Fix: Track whether the boundary must pass through the origin and whether a bias parameter is available.

Check Your Understanding

Key Takeaways

1. An epsilon-net intersects every set in the relevant class whose probability is at least epsilon.
2. The disagreement class H_c converts the true classification error of h into the probability of a set.
3. If the sample is an epsilon-net for H_c, every hypothesis with true error at least epsilon makes a sampled error and cannot be an ERM hypothesis in the realizable setting.
4. VC dimension measures the largest number of points that a class can shatter and carries from H to H_c in the source argument.
5. Homogeneous halfspaces in R^d have VC dimension d, while non-homogeneous halfspaces have VC dimension d+1 because the bias term adds one parameter of freedom.