Skip to main content
PathsSauer-Shelah growth bound

Theorem trail

Sauer-Shelah growth bound

The combinatorial bridge from infinite classes to finite growth.

Open topicExplore AtlasClaim evidenceEvidence panel

Record

Research Record

A compact audit view for the theorem before the full source, proof, diagnostic, and failure-mode sections.

Claim scope
lemma
Evidence level
Exact Lean wrapper
Source precision
reviewed / A
Diagnostics
1 item
Exercises
1 exercise
Failure checks
2 checks
Open Atlas traceOpen evidence recordJump to sourcesJump to failures

Theorem Statement

If , then for all :

Assumptions

  • binary hypothesis class
  • finite VC dimension d

Proof Sketch

Track how many labelings a class can realize on m points when no set of size d+1 is shattered. The inductive recurrence bounds the growth function by the sum of binomial coefficients through d, which is polynomial in m for fixed VC dimension.

Proof Obligations

No shattered set above VC dimension d

assumption

Verify the class has VC dimension d, so no sample of size d + 1 is shattered, before applying the growth-function bound.

Confusing one finite sample's labeling count with the worst-case growth function invalidates the combinatorial statement.

Inductive growth recurrence

proof step

The proof route is the recurrence on realized labelings, which bounds the growth function by binomial coefficients through d.

Jumping straight to the polynomial bound hides the combinatorial condition that makes infinite classes controllable.

Worst-case capacity, not observed training fit

boundary

The Sauer-Shelah bound is a worst-case capacity result; it does not estimate the actual realized complexity of a trained model on one dataset.

Using the lemma as an empirical model-selection score would misstate both the theorem and its evidence status.

VC dimension must be established separately

boundary

The growth bound starts after the class has a known finite VC dimension; it does not by itself prove the value of that dimension.

Plugging in an unverified VC dimension makes the sample-complexity trail look more formal than its input evidence.

Source Locators

Understanding Machine Learning (2014)

proof

Chapter 6 — The VC-dimension

shalev-shwartz-ben-david-2014:ch6

kind
chapter
review
reviewed / A
extract
manual

Chapter-level canonical support for VC dimension and growth-function bounds.

Understanding Machine Learning (2014)

proof

Lemma 6.10 — Sauer-Shelah-Perles

shalev-shwartz-ben-david-2014:lem6.10

kind
lemma
review
reviewed / A
extract
manual
number
6.10

Anchor: Sauer-Shelah-Perles

Reviewed lemma-level support for the Sauer-Shelah-Perles growth bound.

Curated Trace

  1. 1
    Labeling capacityobject

    VC theory starts by counting dichotomies a class can realize.

    Checkpoint

    Separate the class H from the sampled point set.

  2. 2
    No large shattered setassumption

    Finite VC dimension rules out shattering all subsets above size d.

    Checkpoint

    The growth function is still finite-sample and worst-case.

  3. 3
    Sauer-Shelah lemmalemma

    The recurrence turns the no-shattering condition into a binomial upper bound.

    Checkpoint

    For fixed d, the bound grows polynomially in sample size.

  4. 4
    VC sample complexitydownstream

    Replacing |H| by a growth function lets uniform convergence handle infinite classes.

    Checkpoint

    The price moves from log |H| to VC dimension terms.

Failure Modes

Worst-case capacity, not observed training fit

The Sauer-Shelah bound is a worst-case capacity result; it does not estimate the actual realized complexity of a trained model on one dataset.

Risk: Using the lemma as an empirical model-selection score would misstate both the theorem and its evidence status.

Check: The Sauer-Shelah bound is a worst-case capacity result; it does not estimate the actual realized complexity of a trained model on one dataset.

VC dimension must be established separately

The growth bound starts after the class has a known finite VC dimension; it does not by itself prove the value of that dimension.

Risk: Plugging in an unverified VC dimension makes the sample-complexity trail look more formal than its input evidence.

Check: The growth bound starts after the class has a known finite VC dimension; it does not by itself prove the value of that dimension.