Nonuniform Learnability: Sample Size Flexibility
Nonuniform learnability makes sample-size requirements flexible across competing hypotheses.
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.
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.
Assigning the Two Roles
Interpret the statement that h is (ϵ, δ)-competitive with h′.
Identify h: h is the hypothesis being assessed.
Identify h′: h′ is the comparison hypothesis.
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.
The statement compares the assessed hypothesis h with the reference hypothesis h′.
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 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?
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.
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
Assuming every competing hypothesis uses one identical sample-size requirement.
The central idea is that sample-size requirements can vary according to the hypotheses with which the learner is competing.
Fix:
Allow the sample requirement to depend on the particular comparison.Swapping the roles of h and h′.
In the supplied notation, h is the hypothesis being assessed and h′ is the comparison hypothesis.
Fix:
Read the statement directionally: assess h relative to h′.Replacing greater than 1 − δ with a guarantee of certainty.
The stated requirement is that the probability be higher than 1 − δ.
Fix:
Report the threshold exactly and do not strengthen it to certainty.Inventing the missing comparison condition.
The supplied definition does not specify the exact event after the probability phrase.
Fix:
Identify the statement as incomplete until the quantity and condition being compared are provided.
Apply the Reading Check
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.
Completing the Interpretation
Analyze the statement without adding a comparison condition that is not written.
Assessed hypothesis: h is the hypothesis being assessed.
Reference hypothesis: h′ is the comparison hypothesis.
Probability requirement: The relevant probability must be higher than 1 − δ.
Completeness check: The exact event or quantity whose probability is being discussed has not been supplied.
The statement establishes the roles and threshold, but it is incomplete as a full definition because the actual comparison condition is missing.
Key Takeaways
- Nonuniform learnability makes sample-size requirements flexible across competing hypotheses.
- In the statement that h is (ϵ, δ)-competitive with h′, h is assessed and h′ is the comparison hypothesis.
- The relevant probability must be higher than 1 − δ.
- A probability threshold does not identify the comparison event by itself.
- Always verify the quantity and condition being compared before treating a competitiveness statement as complete.
Key Takeaways
- 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.