Concepts / Agnostic PAC Learnability

Agnostic PAC Learnability

The central result is not that ERM always chooses a perfect hypothesis. It is that a sufficiently large sample can make ERM an agnostic PAC learner.

  • Programming
Interactive lab

Try it: Empirical Risk Minimization

How ERM picks the hypothesis in a finite class H with the smallest empirical risk on a random sample , how far its true risk can be from , how often ERM misses ε over many samples compared with the finite-class sample-complexity bounds, and how a richer class trades approximation error for estimation error until memorising the sample overfits.

How it works

  1. D is known: x is uniform over n points in [0, 1] and its label is a target rule f (a threshold or an interval), flipped with probability η; so every can be computed exactly.
  2. Draw : independent labelled examples from a seeded random stream.
  3. For every h in H (thresholds or intervals on a grid, listed in order), count its mistakes on S to get , and compute its true risk from . For the class of all functions, ERM simply memorises S: the majority label at each seen point, 0 elsewhere.
  4. ERM returns , the first hypothesis with the smallest . Compare with , and split into plus .
  5. Repeat with R fresh samples and count how often . The finite-class bound says (realizable, ) or (agnostic, ) keeps that frequency at most δ.
  6. Run the same samples through richer and richer classes: falls, the average rises, and memorising (all functions) reaches small with a large .

Default run (16 steps): D: x uniform over 20 points in [0, 1], label f(x) = 1[x >= 0.4] flipped with probability η = 0.1. H = thresholds on the grid i/10, |H| = 11. The learner never sees D; it gets S ~ Dm with m = 20. … Richer classes on the same 200 samples: ε_app falls from 0.42 (thresholds, k = 1) to 0.1 (all functions), while the average ε_est rises to 0.2282 for all functions (average LS 0.0617). Lowest average LD(hS): thresholds, k = 5 (0.1136).

Simplified: A toy domain of 8-40 equally likely points on a line, a target that is a threshold or an interval, and symmetric label noise, so is an exact finite sum rather than an integral over a continuous distribution. Hypotheses are thresholds or intervals with endpoints on a grid i/k, or all functions on the n points. ERM ties are broken towards the first hypothesis in listing order (for all functions: towards label 0), where the textbook allows any minimiser. Failure frequencies come from at most 400 seeded samples, so they estimate the probability rather than compute it; the bounds use the natural logarithm.

Educational simulation

Loading the simulation…

Learning Without Perfect Representation

Agnostic learning does not assume that the data can be perfectly represented by a hypothesis in the chosen class. The learner therefore does not promise to find a perfect hypothesis. Instead, it aims to find a hypothesis whose performance is close to that of the best hypothesis available in the class. The upper-bound argument shows that, when the sample is sufficiently large, empirical risk minimization can achieve this goal with a controlled probability of failure.

Key point

The central result is not that ERM always chooses a perfect hypothesis. It is that a sufficiently large sample can make ERM an agnostic PAC learner.

From Sample to ERM Hypothesis

The learning process begins with a sample. ERM examines the hypotheses in the class and selects one that minimizes empirical risk, meaning the risk measured on that sample. This selection rule alone only describes performance on the observed data. To show that the selected hypothesis is useful beyond the sample, the proof must connect empirical risk with true risk. Theorem 26.5 supplies that connection, and the remaining probability argument makes the comparison hold across the entire hypothesis class.

SampleEmpirical riskERMSelected hypothesislowest empirical riskRisk comparisontrue versus empiricalAgnostic guaranteeclose to the best in classevaluatecompare hypothesesselectbound the gapapply sufficient condition
How does a training sample move through empirical risk minimization to produce a hypothesis whose true risk is close to the best hypothesis in the class?
Worked example

Tracing the ERM Argument

Follow the proof idea when the learner must choose among several hypotheses even though none is assumed to represent the data perfectly.

  1. 1
    Start with the sample

    The learner receives data and evaluates the hypotheses using empirical risk on that sample.

  2. 2
    Apply ERM

    ERM selects a hypothesis with minimum empirical risk in the hypothesis class.

  3. 3
    Compare risks

    Theorem 26.5 is used to control the difference between each hypothesis's empirical risk and its true risk.

  4. 4
    Control all hypotheses

    The union bound combines the individual failure events so that the comparison can hold for every hypothesis in the class with a controlled overall failure probability.

  5. 5
    Impose the sample condition

    A sufficient sample-size condition from Lemma A.2 is imposed so the final error is below epsilon.

Result

The resulting ERM procedure is shown to be an agnostic learner when the sample is sufficiently large.

True Risk and Empirical Risk

Empirical risk is computed from the sample used by ERM. True risk refers to performance over the data distribution. The key difficulty is that ERM directly minimizes only the empirical quantity. Theorem 26.5 provides a uniform risk comparison: it controls the difference between empirical and true risk for every hypothesis in the class, rather than establishing the comparison only for the single hypothesis eventually selected by ERM.

Empirical riskon the sampleUniform comparisonTheorem 26.5True riskover the distributioncomparecompare
What is the relationship between a hypothesis's empirical risk on the sample and its true risk over the data distribution, and how does the theorem bound their difference?

Combining Failure Events

The theorem gives a risk comparison for individual hypotheses, while the learner needs a statement that covers the whole hypothesis class. The union bound combines the failure events associated with the individual hypotheses. This produces a probability guarantee for the combined event that the desired risk comparison holds for every hypothesis simultaneously. That uniform guarantee is what lets the proof apply the comparison to the ERM-selected hypothesis.

Hypothesis h1individual failure eventUnion boundSimultaneousguaranteeall hypothesesHypothesis h2individual failure eventHypothesis hnindividual failure eventcombinecombinecombinecontrol total failure
How are the failure probabilities for individual hypotheses combined to obtain a probability guarantee that the risk bound holds for every hypothesis simultaneously?

The Sufficient Sample Condition

The proof needs a sufficient sample-size condition because the uniform risk-estimation error must be small enough to meet the desired accuracy and confidence requirements. The source excerpt does not display the literal algebraic expression for the sample complexity. Its structural conclusion is that one first proves the uniform risk bound, then combines the relevant failure events, and finally imposes the sufficient condition from Lemma A.2 so that the final error is below epsilon.

Small sampleerror not yet sufficientUniform risk errorcontrolled by the conditionSufficient sampleerror below epsilonmay be too largemake sufficiently small
How does increasing the sample size make the uniform risk-estimation error small enough to meet the desired accuracy and confidence requirements?
Sufficient samplesizeUniform risk boundControlled failureprobabilityError below epsilonenablescombine eventsestablish
What does the sample-complexity upper bound guarantee about the accuracy and failure probability of the ERM learner when the sample is sufficiently large?

Common Proof Mistakes

  • Common mistake

    Treating minimum empirical risk as an immediate guarantee of minimum true risk

    What it looks like

    Assuming that because ERM chooses the hypothesis with the best sample performance, it must also be best over the data distribution.

    Why it fails

    ERM minimizes empirical risk, but a theorem is needed to relate empirical performance to true performance.

    Do this instead

    Use Theorem 26.5 to control the difference between empirical and true risk.

  • Common mistake

    Applying a risk comparison only to the selected hypothesis

    What it looks like

    Ignoring the other hypotheses when establishing the probability guarantee.

    Why it fails

    The proof needs a comparison that remains valid for whichever hypothesis ERM selects.

    Do this instead

    Use the uniform comparison for every hypothesis in the class.

  • Common mistake

    Ignoring the combined failure probability

    What it looks like

    Showing that each individual hypothesis has a controlled failure event but never combining those events.

    Why it fails

    The learner's guarantee concerns the whole class, not one isolated hypothesis.

    Do this instead

    Apply the union bound to control the probability of the combined events.

  • Common mistake

    Omitting the sufficient sample-size condition

    What it looks like

    Concluding the final accuracy guarantee immediately after stating the uniform bound.

    Why it fails

    The proof still needs the risk-estimation error to be small enough for the desired epsilon accuracy.

    Do this instead

    Impose the sufficient condition from Lemma A.2.

Proof-Structure Practice

MEDIUM

Arrange these ideas in the order used by the agnostic PAC upper-bound argument: apply ERM, impose the sufficient sample-size condition, obtain a uniform risk comparison, start with a sample, and combine failure events with the union bound.

Hints
  • Begin with the object available to the learner.
  • The union bound is used after individual risk-comparison events have been identified.
  • The sufficient condition is used to make the final error meet the desired epsilon requirement.
  1. 1
    A correct order is: start with a sample, apply ERM, obtain a uniform risk comparison, combine failure events with the union bound, and impose the sufficient sample-size condition.

Key Takeaways

  1. 1
    An agnostic learner does not rely on perfect representation of the data. ERM chooses a hypothesis by minimizing empirical risk, but Theorem 26.5 is needed to relate that sample-based quantity to true risk. The theorem provides a uniform comparison across the hypothesis class. The union bound combines the individual failure events into a guarantee that the comparison holds simultaneously. Finally, a sufficient sample-size condition makes the uniform error small enough for the desired epsilon accuracy, establishing the upper-bound result.

At a glance

  • Agnostic learning seeks performance close to the best hypothesis in the class without assuming perfect representation.
  • ERM minimizes empirical risk, so a theorem must connect empirical risk with true risk.
  • Theorem 26.5 supplies a uniform risk comparison for every hypothesis in the class.
  • The union bound controls the combined probability of failure across hypotheses.
  • A sufficient sample-size condition ensures that the final error is below epsilon.

Related Topics

Related concepts

More concepts starting with A