Sample Size Flexibility

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.

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.

Tracing a Uniform Bound

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.

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.

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.

Common Mistakes

• Treating nonuniform learnability as if it weakened the comparison requirement.

  The relaxation concerns only the sample-size policy. Both notions retain the requirement of being (ε, δ)-competitive with every other hypothesis in the class.

  Fix: 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.

• Assuming that uniform means comparing against only one hypothesis.

  Uniform describes whether m changes across comparisons, not how many hypotheses are used.

  Fix: 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.

• Checking only whether a bound has a numerical value.

  The decisive issue is dependency, not calculating a numerical sample size.

  Fix: Audit the inputs to the sample-size rule and determine whether the comparison hypothesis is permitted to influence m.

Practice Check

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.