PAC Learning and Sample Complexity

From Finite Samples to Distribution Guarantees

A learning algorithm receives a finite sample, but the learning model is described relative to an underlying probability distribution. This creates a central question: when is the finite sample representative enough that conclusions drawn from it apply to the distribution? Uniform convergence formalizes this question for an entire hypothesis class, rather than for only one selected hypothesis.

The Uniform Convergence Guarantee

The word uniform is important. The guarantee is not limited to the single hypothesis eventually chosen by a learning algorithm. It covers every hypothesis in H simultaneously. The probability statement also matters: the guarantee holds with probability at least 1 minus delta over the random drawing of the finite sample. It does not claim that every possible sample has the desired representativeness.

Four Parameters with Different Jobs

A uniform-convergence statement connects four pieces: epsilon, delta, D, and m. Each describes a different part of the guarantee. Keeping their roles separate prevents the common mistake of treating sample size, accuracy, and confidence as interchangeable.

The Sample-Size Threshold

The function m_UC_H(epsilon, delta) denotes the minimal sample complexity for uniform convergence for the hypothesis class H at the selected accuracy and confidence parameters. It is a threshold: the defining sample-size condition is m at least m_UC_H(epsilon, delta). When that condition is met, the uniform-convergence guarantee applies with probability at least 1 minus delta.

Testing a Proposed Sample Size

1. Identify the relevant hypothesis class H and the selected epsilon and delta.
2. Read the corresponding threshold m_UC_H(epsilon, delta).
3. Compare the proposed sample size m with that threshold.
4. If m is at least the threshold, the stated uniform-convergence guarantee applies with probability at least 1 minus delta.
5. If m is below the threshold, the given condition does not establish that guarantee.

Common Interpretation Errors

• Treating uniform convergence as a claim about only the selected hypothesis.

  The defining comparison applies to every hypothesis in H simultaneously.

  Fix: Keep the class-wide scope visible: the guarantee concerns all hypotheses in H.

• Reading probability at least 1 minus delta as a guarantee for every possible sample.

  The guarantee holds with high probability over the random sample, not necessarily for every possible sample.

  Fix: Interpret delta as allowing a failure probability of delta.

• Confusing epsilon with delta.

  Epsilon controls the accuracy gap, while delta controls the confidence level.

  Fix: Associate epsilon with closeness and delta with the probability statement.

• Using a sample size below the threshold as if it proved uniform convergence.

  The defining condition requires m to be at least m_UC_H(epsilon, delta).

  Fix: Compare the proposed m directly with the threshold before making the conclusion.

• Ignoring the distribution D.

  The learning model is described relative to an underlying probability distribution, and true error is interpreted under D.

  Fix: Include D when identifying what the empirical sample is meant to represent.

Uniform Convergence Checklist

1. Uniform convergence connects a finite i.i.d. sample with the representativeness of an underlying distribution.
2. For every hypothesis in H, empirical error should be within epsilon of true error under D, with probability at least 1 minus delta.
3. Epsilon controls accuracy, delta controls confidence, D supplies the underlying distribution, and m is the finite sample size.
4. The function m_UC_H(epsilon, delta) gives the minimal sample complexity for the guarantee.
5. The defining test is m at least m_UC_H(epsilon, delta).