Generalization Risk

From Sample to Risk

An ERM learner receives a training set rather than direct access to the underlying distribution D. It can examine what happened on the sampled examples, but the guarantee we want concerns the risk of the learned hypothesis under D. Generalization risk asks how likely the sampled training set is to produce a hypothesis whose risk is unacceptably large.

How the Training Set Is Sampled

The notation S ∼ D^m describes a random training set S containing m examples. The i.i.d. assumption means two things: the examples are independent of one another, and every example is drawn from the same distribution D. Thus, the training set is formed by repeatedly sampling from D under the same distributional source, with the samples treated as independent.

The Risk Threshold ϵ

The parameter ϵ defines how much risk is tolerated before the learner is considered to have failed. It is a boundary for the guarantee being studied. A guarantee aims to control the probability that sampling produces an output whose risk crosses this boundary, rather than claiming that every output has zero risk.

Correctness versus Failure

Let hS denote the hypothesis produced from the sampled training set S, and consider its risk written as L(D,f)(hS). The learner is approximately correct when L(D,f)(hS) is at most ϵ. The learner has failed with respect to this guarantee when L(D,f)(hS) exceeds ϵ. This distinction evaluates the learned hypothesis under D, not merely on the particular sample that produced it.

Combining Bad Events

To analyze failure, define the set HB of bad hypotheses: hypotheses whose risk is beyond the permitted accuracy level. The analysis can associate separate events with these bad hypotheses and then combine those events. The Union Bound says that the probability of at least one event occurring is no greater than the sum of the separate event-probability bounds. This gives an overall upper bound on failure probability.

Common Reasoning Errors

• Treating S ∼ D^m as if the learner directly receives D.

  S ∼ D^m describes a random training set of m examples drawn from D; the learner receives S.

  Fix: Separate the distribution D from the particular sample S drawn from it.

• Interpreting ϵ as a claim that the hypothesis must be perfect.

  ϵ defines the tolerated risk boundary. The guarantee concerns whether risk crosses that boundary.

  Fix: Ask whether L(D,f)(hS) is at most ϵ, not whether it is zero.

• Confusing a bad training-set outcome with every possible learner output.

  The analysis bounds the probability that sampling produces an unacceptable output.

  Fix: Describe failure as an event whose probability is being bounded.

• Assuming Union Bound addition requires disjoint events.

  The Union Bound applies even when events overlap; overlap is why the sum may be larger than the exact union probability.

  Fix: Use the sum as an upper bound for the probability that at least one event occurs.

Check Your Understanding

Summary

1. S ∼ D^m means that the training set contains m independent examples drawn from the same distribution D.
2. The parameter ϵ is the tolerated-risk threshold used to define the guarantee.
3. L(D,f)(hS) at most ϵ represents approximate correctness, while L(D,f)(hS) greater than ϵ represents learner failure for the guarantee.
4. Bad hypotheses can be grouped into failure events, and the Union Bound combines their separate probability bounds into an upper bound for the probability that at least one occurs.
5. The resulting sum is an upper bound even when the bad events overlap.