Discussion Section: Learning Theory

What this lecture covers

This discussion section formalizes ideas about generalization that the main CS229 lectures use informally: why a learning algorithm trained on finite data ever performs well on new data, and what limits that performance. It reframes bias and variance as properties of an estimator's sampling distribution, then builds up the machinery (empirical risk minimization, the union bound, Hoeffding's inequality) needed to bound the gap between training error and true error.

The section sits after the course has already covered supervised learning basics and regularization, and it precedes the deeper treatment of learning theory in the main lecture sequence. After watching, you should be able to explain bias and variance in terms of an estimator's mean and variance, decompose generalization error into irreducible, approximation and estimation error, and state what the sample complexity bound says about how much data a model needs.

Key ideas

• Data-generating distribution: the course assumes training and test examples are drawn independently from the same fixed distribution D; without this assumption, generalization theory has no foothold.
• Sampling distribution: because the training set is random, the learned parameter theta-hat is itself a random variable with its own distribution, centered and spread in ways that define bias and variance.
• Bias vs variance: bias measures whether the sampling distribution is centered on the true parameter theta-star; variance measures how spread out it is. They are independent properties of an algorithm at a fixed sample size.
• Statistical efficiency and consistency: efficiency is how fast variance shrinks toward zero as sample size grows; a consistent estimator converges to the true parameter as the sample size goes to infinity.
• Approximation vs estimation error: generalization error splits into irreducible (Bayes) error, approximation error (the cost of restricting to a hypothesis class), and estimation error (the cost of having only finite data).
• Empirical risk minimization (ERM): an algorithm that picks the hypothesis minimizing average training error; restricting analysis to ERM lets you prove uniform convergence results.
• Hoeffding's inequality and the union bound: two tools combined to bound, with high probability, how far the empirical error of every hypothesis in a class can be from its true generalization error.
• Sample complexity: for a finite hypothesis class of size K, keeping the error margin and confidence fixed requires a training set size that grows with log(K), giving a concrete "how much data do I need" answer.

Walkthrough

Framing the learning problem (0:03)

The TA sets up the assumptions behind the rest of the course: a fixed data-generating distribution D produces independent (x, y) pairs, some of which become the training set and some of which appear at test time. A learning algorithm maps a training sample S to a hypothesis h, and because S is random, the resulting hypothesis (or its parameters theta-hat) is a random variable with a "sampling distribution." The unknown true parameter is called theta-star, and it is treated as a fixed constant, not a random variable.

Bias and variance in parameter space (14:16)

Instead of the usual curve-fitting picture, the section visualizes several algorithms as clouds of points in parameter space, each point representing the theta-hat obtained from one random training sample. Bias is whether a cloud is centered on theta-star; variance is how spread out the cloud is. Increasing the training set size shrinks variance toward zero, and how quickly it shrinks is called statistical efficiency. If the expected value of theta-hat equals theta-star at every sample size, the estimator is unbiased; if theta-hat converges to theta-star as the sample size grows, it is consistent.

Fighting variance and the bias-variance tradeoff (30:17)

Two levers reduce variance: collecting more data, or adding regularization. Regularization works by shrinking the effective hypothesis class, which leaves less room for the estimate to wander (lower variance) but typically pulls the estimate away from the unrestricted best hypothesis (higher bias). The lecture stresses that whether regularization actually increases bias is not guaranteed, only likely, and that this tradeoff is easier to see once bias and variance are defined in terms of the sampling distribution rather than a fitted curve.

Decomposing generalization error (30:39)

The section introduces g, the best possible hypothesis overall, and h-star, the best hypothesis within a chosen class H. The error of g is the Bayes or irreducible error, present even for a perfect model. The gap between g and h-star is approximation error, the cost of restricting to class H. The gap between h-star and the actually learned h-hat is estimation error, driven mainly by having finite data. Generalization error is the sum of all three, and estimation error further splits into a bias term and a variance term, giving two related but distinct decompositions of the same overall error.

Empirical risk minimization (45:22)

ERM is defined as any learning algorithm that selects, from a hypothesis class, the member minimizing average training error (empirical risk). The lecture notes that losses used in practice, such as logistic loss, approximate this behavior well enough that the theory still applies. Restricting attention to ERM-style algorithms is what makes it possible to prove the uniform convergence results that follow.

Uniform convergence, the union bound and Hoeffding's inequality (48:43)

The lecture states the union bound (the probability of any of several events happening is at most the sum of their individual probabilities) and Hoeffding's inequality (for averages of bounded random variables, the chance the estimate strays far from the true parameter shrinks exponentially with sample size). Applying Hoeffding's inequality to one fixed hypothesis, then extending it across an entire finite hypothesis class with the union bound, gives "uniform convergence": with high probability, every hypothesis's training error is close to its true error simultaneously, not just on average over random samples.

Sample complexity and VC dimension (1:23:30)

Solving the uniform convergence bound for the sample size m yields a sample complexity result: to guarantee a given error margin with a given confidence, the required number of training examples grows with the logarithm of the size of a finite hypothesis class. The lecture closes by naming VC dimension as the tool for extending this result to infinite hypothesis classes (such as all linear separators), stating without proof that the needed sample size scales with the VC dimension instead of log(K).

Before you watch

• Be comfortable with logistic regression, regularization and gradient descent, since the section assumes them as running examples.
• Review basic probability, including expectation, variance and Bernoulli random variables.
• Having seen the informal bias-variance picture (underfitting, overfitting, "just right" curves) from earlier in the course will make the parameter-space reframing easier to follow.

Check your understanding

1. Why does treating the training set S as a random variable make the learned hypothesis h-hat a random variable as well?
2. How do bias and variance differ, and why does adding regularization typically trade one for the other?
3. What is the difference between approximation error and estimation error, and which one does more training data primarily reduce?
4. How do the union bound and Hoeffding's inequality combine to produce a uniform convergence guarantee across an entire hypothesis class?
5. According to the sample complexity result, how does the required training set size change as the hypothesis class grows larger?