Natarajan's Lemma
The proof has separate lower-bound and upper-bound routes.
Two Routes Through the Proof
Natarajan's Lemma is important because it supplies the ingredient needed to extend the binary upper-bound argument to multiclass classification. The proof of the Multiclass Fundamental Theorem, stated as Theorem 29.3, divides into two routes: a lower-bound route obtained from the Binary Fundamental Theorem and an upper-bound route that follows the binary strategy but replaces Sauer's Lemma with Natarajan's Lemma.
The central proof pattern is not a completely new argument. It preserves the binary proof's overall structure and changes one nontransferable ingredient.
The Lower-Bound Route
The lower bounds in the Multiclass Fundamental Theorem come from a reduction from the multiclass problem to the Binary Fundamental Theorem. In other words, the lower-bound argument does not begin by proving a new multiclass counting result. It uses the already available binary theorem as the source of the lower bounds.
Tracing the Lower-Bound Choice
Suppose you are organizing the proof of the Multiclass Fundamental Theorem and must decide where the lower bounds come from.
Identify the route: Choose the lower-bound route rather than the upper-bound route.
Apply the reduction: Reduce the multiclass problem to the Binary Fundamental Theorem.
Use the binary result: Take the lower-bound information supplied by the Binary Fundamental Theorem.
The lower-bound part of the multiclass theorem is obtained through the binary reduction.
The Upper-Bound Replacement
The upper-bound proof retains the same general lines as the binary-classification proof. The difficulty is that one important ingredient from the binary proof does not transfer directly: Sauer's Lemma. The multiclass proof therefore replaces Sauer's Lemma with Natarajan's Lemma.
Label-Pair Witnesses
The multiclass role of Natarajan's Lemma can be pictured through label-pair witnesses. For each point in a set, assign two distinct labels. The relevant multiclass condition is that every combination of those selected labels is realized by hypotheses. This label-pair view is the multiclass structure that the lemma handles in the upper-bound proof.
The diagram is a conceptual witness pattern, not a numerical calculation. Its purpose is to show why a multiclass replacement is needed: the proof must account for combinations built from distinct labels at each point, rather than relying only on the binary ingredient.
Two Lemmas, Two Roles
| Ingredient | Classification setting | Role in the theorem proof |
|---|---|---|
| Sauer's Lemma | Binary | The counting ingredient used by the binary upper-bound strategy |
| Natarajan's Lemma | Multiclass | The replacement for Sauer's Lemma in the multiclass upper-bound strategy |
Sauer's Lemma and Natarajan's Lemma are therefore related by proof role. Sauer's Lemma belongs to the binary proof. Natarajan's Lemma has the same general spirit as Sauer's Lemma, but supplies the multiclass replacement required by the upper-bound argument.
Treating Natarajan's Lemma as a replacement for the entire binary proof.
The upper-bound proof retains the binary proof strategy in general.
Fix:
Replace the specific Sauer's Lemma step while keeping the overall binary strategy.Using Sauer's Lemma unchanged in the multiclass upper-bound proof.
The source identifies Sauer's Lemma as the important ingredient that does not transfer directly.
Fix:
Use Natarajan's Lemma as the multiclass replacement.Deriving the lower bounds from Natarajan's Lemma.
The lower bounds come from a reduction to the Binary Fundamental Theorem.
Fix:
Keep the proof routes separate: binary reduction for lower bounds, Natarajan's Lemma for the upper-bound replacement.
Proof Map Practice
Complete the proof map in words: the lower bounds come from ________, while the upper bounds follow the binary strategy after ________ is replaced by ________.
Hints
- Name the binary theorem used by the lower-bound route.
- Identify the binary lemma that does not transfer directly.
- Name the multiclass lemma that takes its place.
What do you think happens?
Which route should you select if the proof task asks for the lower bounds?
Reveal answer
Answer: Reduce to the Binary Fundamental Theorem
The lower bounds are obtained through a reduction from the multiclass problem to the Binary Fundamental Theorem. The replacement of Sauer's Lemma belongs to the upper-bound route.
Key Takeaways
- The proof of the Multiclass Fundamental Theorem has separate lower-bound and upper-bound routes.
- The lower bounds are obtained by reducing the multiclass problem to the Binary Fundamental Theorem.
- The upper-bound proof keeps the general binary strategy but cannot use Sauer's Lemma unchanged.
- Natarajan's Lemma supplies the multiclass replacement for Sauer's Lemma.
- Natarajan's Lemma has the same general proof spirit as Sauer's Lemma while addressing the multiclass setting.
Key Takeaways
- The Multiclass Fundamental Theorem proof divides into lower-bound and upper-bound routes.
- A reduction from the Binary Fundamental Theorem supplies the lower bounds.
- The upper-bound route follows the binary proof strategy except at the Sauer's Lemma step.
- Natarajan's Lemma replaces Sauer's Lemma for the multiclass argument.
- Label-pair witnesses provide the key multiclass perspective behind the replacement.