Sample Size Flexibility

Agnostic PAC learnability requires a sample-size rule that is independent of h.

Programming

The Comparison Question

Suppose a learning algorithm receives a sample and produces a hypothesis. The central question is how that output is evaluated against hypotheses in the class. In both agnostic PAC learnability and nonuniform learnability, the output must be (ε, δ)-competitive with every other hypothesis in the class. The difference is whether the number of examples needed for that guarantee must be the same for every comparison hypothesis.

Key point

Sample size flexibility concerns dependency: may the required sample size change when the comparison hypothesis changes?

Agnostic PAC Requires Uniformity

Agnostic PAC learnability uses an h-independent sample-size requirement. Here, h denotes the hypothesis selected for comparison with the algorithm's output. After fixing any comparison hypothesis h in the class, the required sample size m cannot depend on which h was chosen. The same sample-size condition must therefore work uniformly across those comparisons.

Which dependency is prohibited in the agnostic PAC sample-size requirement?

Tracing a Uniform Bound

Worked example

Testing an agnostic PAC requirement

An algorithm's output must be compared with h1 and h2. A proposed guarantee uses one sample-size requirement m for both comparisons. Does this match the h-independence requirement?

1
Choose h1
Compare the algorithm's output with h1 and apply the proposed sample-size requirement m.
2
Choose h2
Replace h1 with h2. The proposed requirement still uses m rather than changing the required number of examples.
3
Check dependency
The required sample size does not depend on which comparison hypothesis was selected.

Result

The proposed rule has the required uniform form for agnostic PAC learnability with respect to this dependency question.

Can one sample-size requirement remain unchanged when the comparison hypothesis changes?

Nonuniform Flexibility

Nonuniform learnability relaxes the sample-size condition. It permits the required m to depend on the particular comparison hypothesis h. Thus, fixing h1 may lead to one sample-size requirement, while fixing h2 may lead to another. This changes the sample-size policy, not the comparison target: the algorithm's output must still be (ε, δ)-competitive with every other hypothesis in the class.

How can the required sample size change when the bound is allowed to depend on the comparison hypothesis?

Worked example

Testing a nonuniform requirement

A proposed learning guarantee uses m(h1) when comparing with h1 and m(h2) when comparing with h2. Is the dependence on h allowed under nonuniform learnability?

1
Fix h1
The required number of examples is determined using the comparison hypothesis h1.
2
Fix h2
The requirement may change because the comparison hypothesis is now h2.
3
Check the preserved condition
Even though the sample-size rule varies, the output still has to be compared with every hypothesis in the class.

Result

The hypothesis-dependent sample-size rule is permitted by nonuniform learnability, while the all-comparisons requirement remains.

Why This Is a Relaxation

Nonuniform learnability is a relaxation because it removes one restriction while retaining the shared performance requirement. Agnostic PAC learnability requires a sample-size rule that is independent of h. Nonuniform learnability allows that rule to vary with h. Since the nonuniform notion accepts the additional possibility of hypothesis-dependent sample sizes, it imposes a less restrictive sample-size condition.

Which requirement changes when moving from agnostic PAC learnability to nonuniform learnability?

Which performance requirement remains the same in both notions?

Dependency Audit

1
Identify the comparison hypothesis h used in the guarantee.
2
Ask whether changing h is allowed to change the required sample size m.
3
If m must remain independent of h, the sample-size condition has the agnostic PAC form.
4
If m may vary with h, the sample-size condition has the nonuniform form.
5
Check separately that the output is still required to be (ε, δ)-competitive with every hypothesis in the class.

Question	Agnostic PAC learnability	Nonuniform learnability
May m depend on h?	No	Yes
Must the output be competitive with every hypothesis in the class?	Yes	Yes
What changes between the notions?	The sample-size rule is uniform across comparison hypotheses	The sample-size rule may vary with the comparison hypothesis

The distinction is limited to the dependency of the sample-size requirement.

Can one sample-size bound work for every comparison hypothesis, or may different hypotheses receive different bounds?

Common Mistakes

Common mistake
Treating nonuniform learnability as if it weakened the comparison requirement.
What it looks like
Assuming the algorithm only needs to be competitive with selected hypotheses rather than every hypothesis in the class.
Why it fails
The relaxation concerns only the sample-size policy. Both notions retain the requirement of being (ε, δ)-competitive with every other hypothesis in the class.
Do this instead
Separate the performance requirement from the sample-size requirement. Ask first whether all comparisons are still required, then ask whether m may depend on h.
Common mistake
Assuming that uniform means comparing against only one hypothesis.
What it looks like
Reading h-independent as if the same fixed h were used throughout.
Why it fails
Uniform describes whether m changes across comparisons, not how many hypotheses are used.
Do this instead
Remember that the output can still be compared with every hypothesis in the class while the same sample-size condition is used for all of them.
Common mistake
Checking only whether a bound has a numerical value.
What it looks like
Focusing on the size of m instead of asking whether the notation or rule changes with h.
Why it fails
The decisive issue is dependency, not calculating a numerical sample size.
Do this instead
Audit the inputs to the sample-size rule and determine whether the comparison hypothesis is permitted to influence m.

Practice Check

EASY

A learning guarantee compares the algorithm's output with every hypothesis in the class. In one version, the required sample size is the same regardless of the comparison hypothesis. In another version, the required sample size may vary with the comparison hypothesis. Identify which version has the agnostic PAC form and which has the nonuniform form. Then state the requirement shared by both.

Hints

Look only at whether m may depend on h.
Do not confuse sample-size flexibility with the set of hypotheses used for comparison.
Both versions retain the same competitiveness requirement.

Your attempt (not saved)

What do you think happens?

If a proposed guarantee uses one sample-size requirement for h1 and a different requirement for h2, which notion permits this dependency?

Agnostic PAC learnability
Nonuniform learnability
Neither notion

Reveal answer

Answer:

Nonuniform learnability

Nonuniform learnability permits the required sample size to depend on the comparison hypothesis, while agnostic PAC learnability requires an h-independent sample-size condition.

Key Takeaways

1
Agnostic PAC learnability requires an h-independent sample-size condition.
2
Nonuniform learnability permits the required sample size to depend on the comparison hypothesis h.
3
Nonuniform learnability is a relaxation because it loosens the sample-size condition.
4
Both notions still require the algorithm's output to be (ε, δ)-competitive with every hypothesis in the class.
5
To classify a sample-size bound, inspect whether changing h is allowed to change m.

At a glance

Agnostic PAC learnability uses a sample-size requirement that cannot depend on the comparison hypothesis.
Nonuniform learnability allows different comparison hypotheses to have different sample-size requirements.
The nonuniform notion relaxes sample-size uniformity, not the requirement to compare against every hypothesis.
The decisive test is whether the comparison hypothesis h is permitted to influence m.

Related concepts

More concepts starting with S