Generalization Bounds for Predictors with Low ℓ1 Norm

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.

Programming

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.

Key point

How do the meanings of B and R change between the two similar-looking bounds?

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.

Worked example

Reading B correctly

Suppose a learner sees two bounds with similar overall structure and wants to determine what B means in each one.

1
Step 1
Identify the theorem before interpreting B.
2
Step 2
For Theorem 26.12, read B as imposing an ℓ2 constraint on w.
3
Step 3
For Theorem 26.15, read B as imposing an ℓ1 constraint on w.
4
Step 4
Do not treat the two B parameters as interchangeable merely because the bounds look similar.

Result

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.

Which theorem places the stronger restriction on the predictor parameter w?

Best practice

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

The same symbols appear in both bounds, but their norm assignments differ between the theorems.

How does R constrain the instances differently in the two theorems?

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.

How should prior knowledge about the instances and the expected good predictor guide theorem selection?

1
Write down what B constrains: w under ℓ2 in Theorem 26.12, or w under ℓ1 in Theorem 26.15.
2
Write down what R describes: the instances under low ℓ2 norm in Theorem 26.12, or under low ℓ∞ norm in Theorem 26.15.
3
Check whether the expected good predictor matches the selected constraint on w.
4
Check whether the known properties of the instances match the selected interpretation of R.
5
Only then compare the resulting bounds, including the extra log(d) factor in Theorem 26.15.

Common Interpretation Mistakes

Common mistake
Assuming B has the same norm meaning in both theorems.
What it looks like
Treating B as an ℓ2 constraint on w in both Theorem 26.12 and Theorem 26.15.
Why it fails
Theorem 26.12 uses an ℓ2 constraint on w, while Theorem 26.15 uses an ℓ1 constraint on w.
Do this instead
Identify the theorem before interpreting B.
Common mistake
Treating R as a constraint on the predictor parameter w.
What it looks like
Reading R as another bound on the size of w.
Why it fails
R describes a norm assumption on the instances.
Do this instead
Associate R with the instances, then identify whether the assumption is low ℓ2 norm or low ℓ∞ norm.
Common mistake
Ignoring the difference between low ℓ2 norm and low ℓ∞ norm.
What it looks like
Using the same interpretation of R for both theorems because the symbol is unchanged.
Why it fails
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.
Do this instead
Track the norm attached to R in the specific theorem being used.
Common mistake
Choosing a theorem only because its displayed bound looks similar.
What it looks like
Selecting a theorem without checking the assumed predictor constraint and instance norm.
Why it fails
The similar appearance hides different meanings for B and R.
Do this instead
Check both the predictor-side assumption and the instance-side assumption before applying a bound.

Practice Check

EASY

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.

Your attempt (not saved)

Key Takeaways

1
Theorem 26.12 uses B for an ℓ2 constraint on w; Theorem 26.15 uses B for an ℓ1 constraint on w.
2
The ℓ1 constraint on w is stronger than the ℓ2 constraint.
3
R concerns the instances, not w: it represents low ℓ2 norm in Theorem 26.12 and low ℓ∞ norm in Theorem 26.15.
4
The low ℓ∞-norm assumption on instances is described as weaker than the low ℓ2-norm assumption.
5
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.

At a glance

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.

Related concepts

Generalization bounds

More concepts starting with G