Generalization Bounds for Predictors with Low ℓ1 Norm
Theorem 26.12 and Theorem 26.15 have bounds that look similar apart from an extra log(d) factor in Theorem 26.15.
The Similarity Trap
Theorem 26.12 and Theorem 26.15 have bounds that look similar, except that Theorem 26.15 contains an additional log(d) factor. That visual similarity can be misleading. The two theorems use B and R differently, so comparing the displayed bounds requires more than comparing their surface form.
Before applying either theorem, identify two things separately: the constraint placed on the predictor parameter w, represented by B, and the norm assumption placed on the instances, represented by R.
Tracing B Across Theorems
In Theorem 26.12, B imposes an ℓ2 constraint on w. In Theorem 26.15, B imposes an ℓ1 constraint on w. Thus, B is not automatically the same kind of quantity in the two results. Its role is similar—a restriction on the predictor parameter—but the norm used for that restriction changes.
Reading B correctly
Suppose a learner sees two bounds with similar overall structure and wants to determine what B means in each one.
Step 1: Identify the theorem before interpreting B.
Step 2: For Theorem 26.12, read B as imposing an ℓ2 constraint on w.
Step 3: For Theorem 26.15, read B as imposing an ℓ1 constraint on w.
Step 4: Do not treat the two B parameters as interchangeable merely because the bounds look similar.
The theorem determines whether B refers to an ℓ2 constraint or an ℓ1 constraint on w.
Why the ℓ1 Constraint Is Stronger
The source describes the ℓ1 constraint on w as stronger than the ℓ2 constraint on w. In practical reading, this means that Theorem 26.15 uses a more restrictive assumption about the allowable predictor parameters than Theorem 26.12 does. The distinction concerns w, the predictor parameter; it does not describe the instances.
When comparing these theorems, first ask whether the expected good predictor is naturally described using an ℓ2 restriction or an ℓ1 restriction. The stronger ℓ1 perspective is appropriate only when that more restrictive description fits the predictor you expect to use.
Tracing R Across Instances
R describes a norm assumption on the instances, not on the predictor parameter w. In Theorem 26.12, R represents a low ℓ2-norm assumption on the instances. In Theorem 26.15, R represents a low ℓ∞-norm assumption on the instances.
| Theorem | Meaning of B | Meaning of R | Additional visual feature |
|---|---|---|---|
| Theorem 26.12 | ℓ2 constraint on w | Low ℓ2 norm of instances | No extra log(d) factor described in the comparison |
| Theorem 26.15 | ℓ1 constraint on w | Low ℓ∞ norm of instances | Extra log(d) factor |
Selecting a Constraint Perspective
The choice between the two perspectives should use prior knowledge about both parts of the problem. Examine the instances to decide whether a low ℓ2-norm or low ℓ∞-norm assumption is a better description. Then examine the expected good predictor to decide whether an ℓ2 or the stronger ℓ1 constraint on w is a better description.
- Write down what B constrains: w under ℓ2 in Theorem 26.12, or w under ℓ1 in Theorem 26.15.
- Write down what R describes: the instances under low ℓ2 norm in Theorem 26.12, or under low ℓ∞ norm in Theorem 26.15.
- Check whether the expected good predictor matches the selected constraint on w.
- Check whether the known properties of the instances match the selected interpretation of R.
- Only then compare the resulting bounds, including the extra log(d) factor in Theorem 26.15.
Common Interpretation Mistakes
Assuming B has the same norm meaning in both theorems.
Theorem 26.12 uses an ℓ2 constraint on w, while Theorem 26.15 uses an ℓ1 constraint on w.
Fix:
Identify the theorem before interpreting B.Treating R as a constraint on the predictor parameter w.
R describes a norm assumption on the instances.
Fix:
Associate R with the instances, then identify whether the assumption is low ℓ2 norm or low ℓ∞ norm.Ignoring the difference between low ℓ2 norm and low ℓ∞ norm.
The two theorems attach different instance-norm assumptions to R, and the source describes the low ℓ∞-norm assumption as weaker than the low ℓ2-norm assumption.
Fix:
Track the norm attached to R in the specific theorem being used.Choosing a theorem only because its displayed bound looks similar.
The similar appearance hides different meanings for B and R.
Fix:
Check both the predictor-side assumption and the instance-side assumption before applying a bound.
Practice Check
A theorem statement uses B for an ℓ1 constraint on w and R for a low ℓ∞-norm assumption on the instances. Which theorem from this lesson matches that description, and what additional factor distinguishes its bound from the other theorem?
Hints
- Match the norm used for B first.
- Then match the norm used for R.
- Recall which theorem contains the additional log(d) factor.
Key Takeaways
- Theorem 26.12 uses B for an ℓ2 constraint on w; Theorem 26.15 uses B for an ℓ1 constraint on w.
- The ℓ1 constraint on w is stronger than the ℓ2 constraint.
- R concerns the instances, not w: it represents low ℓ2 norm in Theorem 26.12 and low ℓ∞ norm in Theorem 26.15.
- The low ℓ∞-norm assumption on instances is described as weaker than the low ℓ2-norm assumption.
- Choose a theorem by checking both prior knowledge about the instances and the expected constraint on a good predictor, not by comparing the displayed bounds alone.
Key Takeaways
- B changes meaning between the two theorems: it is an ℓ2 constraint on w in Theorem 26.12 and an ℓ1 constraint on w in Theorem 26.15.
- The ℓ1 constraint on w is stronger than the ℓ2 constraint.
- R always describes the instances in this comparison, but its norm changes from ℓ2 to ℓ∞.
- Theorem 26.15 has an additional log(d) factor, but the different meanings of B and R are more important than the visual similarity of the bounds.
- The correct theorem depends on prior knowledge about both the instances and the expected good predictor.