Realizable Assumption

Why the Assumption Matters

PAC learnability is not simply the claim that an algorithm can produce a useful hypothesis. It is a precise guarantee about when a hypothesis class H can be learned. The definition specifies how many labeled examples are needed, which algorithm receives them, what distribution produces the examples, how the examples are labeled, and how accurate and reliable the returned hypothesis must be.

From Examples to a Guarantee

The PAC process can be read as a pipeline. A distribution D over the instance space X supplies examples. The labeling function f assigns labels to those examples. The learning algorithm receives enough labeled examples and returns a hypothesis h. PAC learnability then asks whether h has loss at most epsilon with probability at least 1 minus delta.

The Definition Components

Each symbol in the PAC definition has a distinct role. H is the hypothesis class to be learned. The function m_H determines how many labeled examples are required for the chosen accuracy and confidence parameters. Epsilon describes the permitted loss, while delta describes the amount of probability left outside the guarantee. D is a distribution over the instance space X, and f is the labeling function. The learning algorithm uses labeled examples and returns h, the hypothesis whose loss is evaluated.

What Realizable Means

The realizable assumption says that the target labeling function f is consistent with the hypothesis class H in the setting defined by H, D, and f. In practical terms, the target labeling situation is treated as one that the chosen hypothesis class can represent. This condition matters because the stated PAC guarantee is required only when the realizable assumption holds.

Reading the Sample Threshold

The threshold m_H(epsilon, delta) connects the learner's resources to the requested guarantee. The learner must receive at least that many labeled examples. The source definition does not specify a particular numerical value for m_H; it requires that such a function exist and determine the required sample size.

Common Interpretation Errors

• Treating m_H as the returned hypothesis.

  m_H is the function that determines how many examples are required, while h is the hypothesis returned by the learning algorithm.

  Fix: Keep the roles separate: m_H sets the sample threshold, and h is evaluated using the PAC guarantee.

• Ignoring the realizable assumption.

  The definition requires the realizable assumption to hold.

  Fix: State explicitly that the guarantee is conditional on the realizable setting.

• Confusing epsilon with delta.

  The guarantee uses epsilon for the loss bound and 1 minus delta for the probability level.

  Fix: Remember the two parts separately: loss at most epsilon, with probability at least 1 minus delta.

• Assuming the source provides a numerical sample bound.

  The definition only states that m_H supplies the required bound.

  Fix: Use the symbolic threshold m at least m_H(epsilon, delta) unless a particular function is provided.

• Treating PAC learnability as a guarantee for one fixed situation only.

  The definition requires the guarantee for every allowed epsilon and delta, every distribution D over X, and every labeling function f when realizability holds.

  Fix: Pay attention to the scope of the quantifiers in the definition.

Practice Check

A complete answer should say that H is PAC learnable when there is a sample-complexity function m_H and a suitable learning algorithm such that, for every allowed epsilon and delta, every distribution D over X, and every labeling function f satisfying the realizable assumption, receiving at least m_H(epsilon, delta) labeled examples leads to a returned hypothesis h with loss at most epsilon with probability at least 1 minus delta.