The Binary Fundamental Theorem
The proof has separate lower-bound and upper-bound routes.
The Proof Map
The proof of the Multiclass Fundamental Theorem is easiest to understand as two separate routes. The lower-bound route reduces the multiclass problem to the Binary Fundamental Theorem. The upper-bound route keeps the general strategy used for binary classification, but replaces one ingredient that does not transfer directly: Sauer's Lemma is replaced by Natarajan's Lemma.
The Lower-Bound Route
The lower bounds are obtained by reduction. Instead of proving the multiclass lower bounds from scratch, the argument reduces the multiclass problem to the Binary Fundamental Theorem. The binary result then supplies the lower-bound information needed for the multiclass theorem.
Reading a Reduction-Based Lower Bound
Identify the logical role of the lower-bound argument in the Multiclass Fundamental Theorem proof.
Begin with the multiclass problem: The proof needs lower bounds for the multiclass setting.
Apply the reduction: The multiclass lower-bound question is reduced to the Binary Fundamental Theorem.
Use the binary result: The Binary Fundamental Theorem provides the lower-bound basis for the multiclass conclusion.
The lower-bound route is a reduction route: it obtains the multiclass lower bounds from the Binary Fundamental Theorem.
The Upper-Bound Route
The upper-bound proof follows the same general lines as the binary-classification proof. However, the binary strategy cannot be transferred unchanged. One important ingredient must be replaced: Sauer's Lemma is not retained as the counting ingredient for the multiclass argument. Natarajan's Lemma takes its place.
The important distinction is between the proof strategy and the proof ingredient. The strategy remains recognizable from the binary proof. The ingredient changes precisely where the binary argument uses Sauer's Lemma. Natarajan's Lemma supplies the multiclass replacement, and its proof has the same general spirit as Sauer's Lemma.
Two Lemmas, Different Roles
| Lemma | Role in the proof | Setting described by the source |
|---|---|---|
| Sauer's Lemma | The ingredient used in the binary upper-bound proof | Binary classification |
| Natarajan's Lemma | The replacement ingredient in the multiclass upper-bound proof | Multiclass classification |
The source distinguishes the lemmas by their positions in the proof. Sauer's Lemma belongs to the binary upper-bound argument. Natarajan's Lemma occupies the corresponding position in the multiclass argument. The point is not that the entire binary proof is discarded; rather, the binary counting ingredient is replaced while the overall proof strategy is retained.
A Complete Proof Trace
Tracing Theorem 29.3
Put the major proof moves in the order described by the source.
Separate the goals: Treat the lower-bound and upper-bound parts as two distinct proof routes.
Establish the lower bounds: Reduce the multiclass problem to the Binary Fundamental Theorem.
Retain the upper-bound strategy: Follow the same general lines as the binary-classification proof.
Replace the nontransferable ingredient: Replace Sauer's Lemma with Natarajan's Lemma for the multiclass upper-bound argument.
Combine the routes: The reduction supplies the lower bounds, while the adapted upper-bound proof supplies the upper bounds.
The proof of the Multiclass Fundamental Theorem has a lower-bound reduction and an upper-bound adaptation, joined in the final theorem.
Common Proof-Reading Mistakes
Treating the proof as one undivided argument
The proof divides naturally into separate lower-bound and upper-bound routes.
Fix:
Identify which route establishes lower bounds and which route establishes upper bounds.Assuming Sauer's Lemma transfers unchanged
The source identifies Sauer's Lemma as the important ingredient that must be replaced.
Fix:
State that Natarajan's Lemma replaces Sauer's Lemma in the multiclass upper-bound argument.Thinking the entire binary strategy is discarded
The upper-bound proof follows the same general lines as the binary-classification proof.
Fix:
Separate the retained strategy from the replaced ingredient.Reversing the lemma roles
The source assigns Sauer's Lemma to the binary upper-bound proof and Natarajan's Lemma to its multiclass replacement.
Fix:
Remember: Sauer for the binary ingredient, Natarajan for the multiclass replacement.
Check Your Understanding
Explain in two or three sentences why the upper-bound proof can be described as both similar to and different from the binary proof.
Hints
- Identify what remains the same at the level of overall strategy.
- Identify the one important ingredient that changes.
Classify each statement as describing the lower-bound route or the upper-bound route: reduction to the Binary Fundamental Theorem; replacement of Sauer's Lemma; same general lines as the binary-classification proof; obtaining the lower bounds.
Hints
- The lower-bound route is defined by reduction.
- The upper-bound route keeps the binary strategy but changes its key lemma.
Final Takeaways
- The Multiclass Fundamental Theorem proof has separate lower-bound and upper-bound routes.
- The lower bounds come from reducing the multiclass problem to the Binary Fundamental Theorem.
- The upper-bound proof retains the general binary strategy.
- Sauer's Lemma is the binary ingredient that must be replaced.
- Natarajan's Lemma supplies the multiclass replacement and has the same general spirit as Sauer's Lemma.
Key Takeaways
- The proof separates naturally into lower-bound and upper-bound routes.
- A reduction from the Binary Fundamental Theorem gives the multiclass lower bounds.
- The upper-bound route follows the binary proof strategy but replaces Sauer's Lemma.
- Natarajan's Lemma is the multiclass replacement for Sauer's Lemma.
- The central proof-reading skill is distinguishing the retained strategy from the changed ingredient.