Questions: PAC Learning Framework

Question 1

A learning algorithm is given 500 training examples drawn i.i.d. from an unknown distribution and outputs a hypothesis with 3% test error. A colleague claims this proves the concept class is PAC-learnable. What is wrong with this claim?

• A. 500 examples is too few for any PAC guarantee — PAC learning requires at least 10,000 samples
• B. PAC learnability is a property of the concept class and algorithm pair that must hold for ALL distributions and ALL target concepts, not just one empirical run
• C. 3% error is too high — PAC learning requires zero error on the test set
• D. The claim is correct — achieving low error on a single run is sufficient to establish PAC learnability

Answer: (B)

PAC learnability is a worst-case guarantee over all possible distributions D and all target concepts c in the class. A single successful experiment shows the algorithm worked for one distribution and one target, but says nothing about whether it would succeed for adversarially chosen distributions or different targets. The 'probably' (1 - delta) and 'approximately' (epsilon) parameters must be achievable for any requested epsilon and delta, with sample complexity polynomial in 1/epsilon and 1/delta.

Question 2

In the PAC framework, why does the sample complexity bound depend on 1/epsilon and 1/delta rather than on epsilon and delta directly?

• A. It is a notational convention with no mathematical significance
• B. Smaller epsilon (tighter accuracy) and smaller delta (higher confidence) are harder guarantees that require more data — the inverse relationship captures that more stringent requirements demand more samples
• C. The dependence on 1/epsilon comes from Bayes' theorem and 1/delta comes from the central limit theorem
• D. The inverse dependence ensures the bound goes to zero as the number of samples increases

Answer: (B)

Epsilon is the allowed error rate and delta is the allowed failure probability. Wanting lower error (smaller epsilon) or higher confidence (smaller delta) naturally requires more evidence. The sample complexity scales as O(1/epsilon) or O(1/epsilon^2) depending on the setting, and O(log(1/delta)) typically — reflecting that tightening accuracy is expensive while boosting confidence is relatively cheap (logarithmic). This inverse relationship is not a convention but a mathematical consequence of concentration inequalities.

Question 3

PAC learning requires that the learning algorithm succeed for any distribution over the input space, including adversarially chosen ones.

• T. True
• F. False

Answer: True

This is the distribution-free property of PAC learning. The algorithm must work without knowing or assuming anything about the distribution D that generates the data. The same algorithm must achieve the (epsilon, delta) guarantee whether D is uniform, Gaussian, concentrated on a few points, or any other distribution. This is a very strong requirement — it means the learner cannot exploit distributional assumptions. The tradeoff is that PAC bounds are often loose for specific 'nice' distributions precisely because they must hold in the worst case.

Question 4

A concept class that requires exponential time to learn but only polynomial samples is considered PAC-learnable.

• T. True
• F. False

Answer: False

PAC learnability requires both polynomial sample complexity AND polynomial computational complexity. The algorithm must run in time polynomial in 1/epsilon, 1/delta, and the size of the representation. A concept class that needs exponentially many computation steps — even if the number of training examples is polynomial — is not efficiently PAC-learnable. This computational requirement distinguishes PAC learning from purely statistical frameworks and connects learning theory to complexity theory.

Question 5

Explain the role of the 'probably' and 'approximately' components in PAC learning and why both relaxations are necessary.

Model answer: The 'approximately' component (epsilon) allows the learned hypothesis to have small but nonzero error — it does not need to perfectly identify the target concept, only get within epsilon of it. The 'probably' component (delta) allows the algorithm to fail with small probability — on some unlucky draws of training data, the hypothesis may have error greater than epsilon, but this happens with probability at most delta. Both relaxations are necessary because learning from finite samples is inherently uncertain: any finite training set might be unrepresentative (justifying delta), and even a representative sample cannot perfectly pin down the target when hypothesis space is rich (justifying epsilon). Without the 'approximately' relaxation, only trivial concept classes would be learnable; without 'probably,' no finite sample could provide guarantees since there is always some probability of drawing a pathologically unrepresentative sample.

The two parameters give the framework its power and flexibility. Users can dial epsilon and delta to any desired level, paying in sample complexity. The framework then tells you exactly how many samples suffice. This parametric structure is what makes PAC learning a practical tool for reasoning about learning algorithms, not just an existence result.