Nonuniform Learnability: Sample Size Flexibility

Nonuniform learnability makes sample-size requirements flexible across competing hypotheses.

Programming

A Flexible Comparison

Suppose a learner is comparing several hypotheses instead of judging one hypothesis in isolation. Nonuniform learnability allows the amount of sample data to vary according to the hypotheses involved in the comparison. The learner therefore does not have to impose one uniform sample-size requirement on every hypothesis comparison.

How can hypotheses be compared when each is allowed to use a different number of training examples?

Reading the Comparison

In the notation that h is (ϵ, δ)-competitive with h′, the two hypotheses have different roles. h is the hypothesis being assessed. h′ is the comparison hypothesis, or reference point, against which h is considered. Reading the notation correctly is the first step before interpreting any claimed competitiveness result.

Worked example

Assigning the Two Roles

Interpret the statement that h is (ϵ, δ)-competitive with h′.

1
Identify h
h is the hypothesis being assessed.
2
Identify h′
h′ is the comparison hypothesis.
3
Keep the direction
The statement evaluates h in relation to h′. It does not, by itself, say that h′ is being assessed in relation to h.

Result

The statement compares the assessed hypothesis h with the reference hypothesis h′.

Which hypothesis is evaluated, which is the competitor or reference, and how are they related in the comparison?

The Probability Threshold

The definition refers to a probability higher than 1 − δ. This threshold describes how likely the desired comparison event must be: its probability must exceed 1 − δ, not merely equal an unspecified lower value. The notation alone does not identify what that event is.

The parameter δ appears in the threshold as the amount subtracted from 1. If a particular event has probability greater than 1 − δ, then its complementary failure event has probability less than δ. However, the supplied definition stops after the probability phrase. Therefore, you must not infer whether the event concerns error, loss, risk, sample requirements, or another quantity unless the statement explicitly supplies that condition.

What does it mean for the desired comparison to hold with probability greater than 1 − δ, and how does that threshold relate to failure probability δ?

What do you think happens?

A statement says that a desired event has probability greater than 1 − δ. What can you safely conclude before knowing the event itself?

The event is guaranteed to happen
The event exceeds the threshold 1 − δ
The event must concern prediction error
The exact comparison condition is already known

Reveal answer

Answer:

The event exceeds the threshold 1 − δ.

The probability threshold is specified, but the supplied definition does not specify the exact event that must satisfy it.

Finding the Missing Quantity

A competitiveness statement is incomplete if it gives the probability phrase but does not state what is being compared. A reader cannot complete the definition by guessing. The missing condition might concern error, loss, risk, sample requirements, or another quantity, but the source statement does not identify which one.

What specific quantity is being compared between h and h′?

Best practice

Use a three-part reading check: first identify h and h′; then locate the probability threshold; finally verify the actual comparison condition. If the third part is absent, describe the statement as incomplete rather than supplying your own interpretation.

Common Reading Errors

Common mistake
Assuming every competing hypothesis uses one identical sample-size requirement.
What it looks like
Treating nonuniform learnability as though one fixed amount of sample data must apply to every comparison.
Why it fails
The central idea is that sample-size requirements can vary according to the hypotheses with which the learner is competing.
Do this instead
Allow the sample requirement to depend on the particular comparison.
Common mistake
Swapping the roles of h and h′.
What it looks like
Reading h′ as the assessed hypothesis and h as the reference.
Why it fails
In the supplied notation, h is the hypothesis being assessed and h′ is the comparison hypothesis.
Do this instead
Read the statement directionally: assess h relative to h′.
Common mistake
Replacing greater than 1 − δ with a guarantee of certainty.
What it looks like
Concluding that the comparison event must occur with probability 1.
Why it fails
The stated requirement is that the probability be higher than 1 − δ.
Do this instead
Report the threshold exactly and do not strengthen it to certainty.
Common mistake
Inventing the missing comparison condition.
What it looks like
Assuming that the incomplete probability phrase automatically refers to error or risk.
Why it fails
The supplied definition does not specify the exact event after the probability phrase.
Do this instead
Identify the statement as incomplete until the quantity and condition being compared are provided.

Apply the Reading Check

MEDIUM

A learner writes: h is (ϵ, δ)-competitive with h′ with probability greater than 1 − δ. Explain what this statement identifies and what it leaves unspecified.

Hints

State the role of h.
State the role of h′.
State the probability threshold.
Check whether the actual quantity or event being compared is present.

Your attempt (not saved)

Worked example

Completing the Interpretation

Analyze the statement without adding a comparison condition that is not written.

1
Assessed hypothesis
h is the hypothesis being assessed.
2
Reference hypothesis
h′ is the comparison hypothesis.
3
Probability requirement
The relevant probability must be higher than 1 − δ.
4
Completeness check
The exact event or quantity whose probability is being discussed has not been supplied.

Result

The statement establishes the roles and threshold, but it is incomplete as a full definition because the actual comparison condition is missing.

Key Takeaways

1
Nonuniform learnability makes sample-size requirements flexible across competing hypotheses.
2
In the statement that h is (ϵ, δ)-competitive with h′, h is assessed and h′ is the comparison hypothesis.
3
The relevant probability must be higher than 1 − δ.
4
A probability threshold does not identify the comparison event by itself.
5
Always verify the quantity and condition being compared before treating a competitiveness statement as complete.

At a glance

Nonuniform learnability permits sample-size requirements to vary across different hypothesis comparisons.
h is the hypothesis being assessed, while h′ is the comparison hypothesis.
The required probability is higher than 1 − δ, but the supplied definition does not identify the exact event.
A competitiveness statement is incomplete when it omits the quantity or condition being compared.

More concepts starting with N