CS229  Machine Learning Lecture 9: Learning Theory

CS229  Machine Learning

Lecture 9: Learning Theory  Bias, Variance & Generalization Bounds
Andrew Ng | Stanford University

Topics covered:
✓ The Bias-Variance Trade-o: Intuition and Formal Model
✓ Empirical Risk Minimization (ERM) and Hypothesis Classes
✓ Training Error vs. Generalization Error
✓ Two Key Lemmas: Union Bound & Hoeding's Inequality
✓ Uniform Convergence for Finite Hypothesis Classes
✓ Generalization Error Bound for ERM
✓ Three Equivalent Forms: Probability / Sample Complexity / Error Bound
✓ The Formal Bias-Variance Decomposition
✓ Corollary: How Much Training Data Do You Need?
⇒ Grand connections across all lectures

Why Learning Theory?

You have now seen many powerful algorithms: linear regression, logistic regression, SVMs,
Naïve Bayes, neural networks. Learning theory answers the deeper questions that separate
an expert from a novice:

ˆ Why does minimizing training error lead to good test performance?

ˆ How much training data do you need?
ˆ When should you use a more complex model?
ˆ Why does overtting happen, and what exactly goes wrong?
Without theory, you are just turning knobs. With theory, you understand why each knob
matters.

1 Bias and Variance: The Central Trade-o Revisited

1.1 Intuition Through Examples
Connection to Lectures 13

In Lecture 3 we rst saw that a degree-1 polynomial underts housing data while a degree-4
polynomial overts it. We called these high bias and high variance. Now we will formalize
exactly what these mean and prove when each occurs.

y line misses curvature

y captures true structure
y memorizes noise

x x x
Undert (High Bias) Good Fit Overt (High Variance)

1
CS229  Machine Learning Lecture 9: Learning Theory

Informal Denitions of Bias and Variance

ˆ High Bias (Undertting): Even with innite training data, the model fails to cap-
ture the true structure. The hypothesis class is too simple.
ˆ High Variance (Overtting): The model ts idiosyncratic noise in the training set
rather than the underlying pattern. It performs well on training data but poorly on
new examples.

2 The Formal Model: Setting Up the Framework

2.1 Key Objects
Distribution D, Training Error ε̂, Generalization Error ε
ˆ Distribution D: A xed (unknown) probability distribution over input-output pairs
(x, y). Training examples are drawn i.i.d. from D.
ˆ Training error (empirical risk):
m
1 X h i
ε̂(h) = 1 h(x(i) ) ̸= y (i)
m
i=1

What fraction of your training examples does h get wrong?

ˆ Generalization error (true risk):

ε(h) = P(x,y)∼D [h(x) ̸= y]

If you draw a new example from D, how likely is h to be wrong?

The Hat Convention

Throughout learning theory, a hat ( ˆ ) denotes an estimate of the true quantity:

ε̂(h) ≈ ε(h) ĥ ≈ h∗ (best hypothesis)

We observe ε̂ (computable from data); we care about ε (unknown). The central question of
learning theory: when is ε̂ a good surrogate for ε?

2.2 Empirical Risk Minimization (ERM)

Hypothesis Class H and ERM
The hypothesis class H is the set of functions the algorithm can choose:

H = {hθ | θ ∈ Θ}

For linear classiers: H = {hθ (x) = 1[θ⊤ x ≥ 0] | θ ∈ Rn }.

Empirical Risk Minimization (ERM): Choose ĥ ∈ H that minimizes training error:

ĥ = arg min ε̂(h)

h∈H

2
CS229  Machine Learning Lecture 9: Learning Theory

Why ERM Is the Right Framework

Logistic regression and SVMs are both approximations to ERM. Minimizing training error
directly is a non-convex combinatorial problem; logistic regression relaxes the 0-1 loss to log-
loss, and SVMs use hinge loss  both convex surrogates that lead to the same conceptual
algorithm. Everything we prove about ERM applies (loosely) to them.

3 Two Key Lemmas

3.1 Lemma 1: The Union Bound
Union Bound

Let A1 , A2 , . . . , Ak be any k events (not necessarily independent). Then:

 
k
[ k
X
P Aj  ≤ P[Aj ]
j=1 j=1

The probability that at least one bad event happens is at most the sum of the individual
probabilities.

Venn Diagram Intuition

A3

A1 A2

Area(A ∪ A ∪ A ) ≤ Area(A )+Area(A )+Area(A )

(overlap is counted multiple times on the right, so it over-counts)
1 2 3 1 2 3

The union's measure is at most the sum because overlaps get counted multiple times in the
sum but only once in the union.

3.2 Lemma 2: Hoeding's Inequality

Hoeding's Inequality

Let Z1 , . . . , Zm be i.i.d. Bernoulli(ϕ) random variables (i.e. P[Zi = 1] = ϕ). Dene the
1 Pm
sample mean ϕ̂ = m i=1 Zi . Then for any γ > 0:
h i
P |ϕ̂ − ϕ| > γ ≤ 2 exp(−2γ 2 m)

What Hoeding's Inequality Says

Your sample mean ϕ̂ concentrates around the true mean ϕ exponentially fast in the sample
size m. The probability of a large error:

ˆ Decreases exponentially as m increases.

ˆ Decreases as γ (the allowed gap) increases.

3
CS229  Machine Learning Lecture 9: Learning Theory

ϕ density
(true mean)

small
large m
tail ≤ 2e−2γ
2
m ϕ̂ m
γ

This is NOT the Central Limit Theorem

Hoeding's inequality holds for any nite m, even m = 2. The CLT only gives asymptotic
approximations. Hoeding gives explicit, nite-sample guarantees  essential for rigorous
machine learning theory.

4 Uniform Convergence: The Main Theorem

4.1 Step 1  One Hypothesis at a Time
Fix any single hypothesis hj ∈ H . Dene:

Zi = 1[hj (x(i) ) ̸= y (i) ]

Since training examples are i.i.d. from D, the Zi 's are i.i.d. Bernoulli with mean ϕ = ε(hj ) (the
generalization error of hj ). Moreover:

m
1 X
ε̂(hj ) = Zi = ϕ̂
m
i=1

By Hoeding's inequality applied to this:

2m
P[|ε̂(hj ) − ε(hj )| > γ] ≤ 2e−2γ
Why This is Natural

Training error is just the sample mean of the 0-1 loss on your training set. Generalization
error is the true mean. Hoeding says the sample mean concentrates around the true mean.
So training error ≈ generalization error  for a single xed hypothesis.

4.2 Step 2  All Hypotheses Simultaneously (Uniform Convergence)

We want this to hold for all K hypotheses in H simultaneously. Dene the bad event for
hypothesis j:
Aj = {|ε̂(hj ) − ε(hj )| > γ}
The probability that any hypothesis has a large error gap is:
 
K
[
P[∃ hj ∈ H : |ε̂(hj ) − ε(hj )| > γ] = P Aj 
j=1
K
X
≤ P[Aj ] (Union Bound)
j=1
K
2m
X
≤ 2e−2γ (Hoeding)
j=1
2m
= 2Ke−2γ

4
CS229  Machine Learning Lecture 9: Learning Theory

Taking complements:

Uniform Convergence Result

simultaneously
2m
With probability at least 1 − 2Ke−2γ , we have for all h ∈ H:

|ε̂(h) − ε(h)| ≤ γ

Hypothesis class H (K functions)

h3
h1
h4
h2
larger m m↑
better bound

h5
· · · hK
εˆ(hj ) ≈ ε(hj )
all simultaneously!

Why Uniform Convergence?

Uniform means the convergence ε̂(h) → ε(h) holds for all h ∈ H simultaneously, not just for
one xed h. This is much stronger  and necessary  because ERM chooses ĥ after seeing
the data. If convergence only held for a pre-specied h, ERM could cheat by always picking
the h with the best-looking training error.

5 Generalization Bound for ERM

5.1 Bounding the Error of ĥ
Let h∗ = arg minh∈H ε(h) be the best hypothesis in H (the one with the lowest true generalization
error, if we had unlimited data).
Assuming uniform convergence holds (i.e. |ε̂(h) − ε(h)| ≤ γ for all h), we can bound ε(ĥ):

Proof in Three Lines

ε(ĥ) ≤ ε̂(ĥ) + γ (1: uniform conv. applied to ĥ)

≤ ε̂(h∗ ) + γ (2: ĥ minimizes training error)
∗
≤ ε(h ) + 2γ (3: uniform conv. applied to h∗ )

Each step has a clear meaning:

ˆ Step 1: Uniform convergence tells us ε(ĥ) ≤ ε̂(ĥ) + γ .

ˆ Step 2: ERM chose ĥ as the minimizer of training error, so no hypothesis (including
h∗ ) can have lower training error.
ˆ Step 3: Uniform convergence tells us ε̂(h∗ ) ≤ ε(h∗ ) + γ .

5
CS229  Machine Learning Lecture 9: Learning Theory

: ERM output ≤ 2γ gap h : best in H ∗

(min training error) (min true error)

ĥ

estimation error (2γ) if h ∈/ H: bias ∗

True optimal
(unknown)

6 Three Equivalent Forms of the Bound

The uniform convergence result has three equally valid presentations, each answering a dierent
practical question:

Form 1  Probability Bound

2m
For xed γ and m: With probability at least 1 − 2Ke−2γ , simultaneously for all h ∈ H:

|ε̂(h) − ε(h)| ≤ γ

Use when: You know m and γ, and want to know how likely convergence is.

Form 2  Sample Complexity Bound

2m
For xed γ and condence δ (where δ = 2Ke−2γ ), uniform convergence holds with prob-
ability ≥ 1 − δ whenever:
1 2K
m ≥ 2
log
2γ δ
Use when: You want to know how much training data you need.

Form 3  Error Bound

For xed m and condence δ, with probability ≥ 1 − δ:

r
1 2K
|ε̂(h) − ε(h)| ≤ log ∀h ∈ H
2m δ
Use when: You have a xed dataset and want to bound the generalization gap.

6
CS229  Machine Learning Lecture 9: Learning Theory

How to Navigate the Three Forms

All three are algebraically equivalent; they are just the same inequality solved for dierent
2m
variables. Set δ = 2Ke−2γ and solve for whichever quantity you want:

Form 1 Form 2
Given m, γ Given γ, δ
nd δ nd m

2
δ = 2Ke−2γ m

Form 3
Given m, δ
nd γ

7 The Full Theorem and Its Corollary

Theorem 1 (Generalization Bound for Finite H). Let |H| = K (nite). For any xed m and
δ > 0, with probability at least 1 − δ:
r
1 2K
ε(ĥ) ≤ min ε(h) + 2 log
h∈H 2m δ

Reading the Theorem

r
log(2K/δ)
ε(ĥ) ≤ min ε(h) + 2
|{z}
what ERM gives you
h∈H
| {z } | {z2m }
best possible in H estimation error
(variance term)
(bias term)

ˆ First term: irreducible error  the best H can do. Decreases as H grows.
ˆ Second term: grows with K (more hypotheses = harder to learn) and shrinks with m
(more data = better estimates).

Corollary 1 (Sample Complexity). For xed γ, δ > 0, to guarantee ε(ĥ) ≤ ε(h∗ ) + 2γ with
probability ≥ 1 − δ, it suces to have:

 
1 2K 1 K
m ≥ log = O 2 log
2γ 2 δ γ δ

The Logarithmic Dependence on K Is Everything

The sample complexity grows as log K , not K. This is a crucial insight:

ˆ Doubling the size of H (from K to 2K ) only requires log(2K) − log(K) = log 2 ≈ 0.693
extra examples.
ˆ You can grow H enormously (even to K = 10100 ) and only need about 230 extra
training examples.
ˆ This is why large models can still generalize: as long as m ≫ log K , ERM works.

7
CS229  Machine Learning Lecture 9: Learning Theory

8 Formalizing the Bias-Variance Trade-o

Formal Bias-Variance Decomposition (Classication)

Suppose we expand H to H′ (e.g. from linear to quadratic classiers), so K increases to K′

∗
and h improves to h∗′ :
r
∗′ log(2K ′ /δ)
ε(ĥ) ≤ ε(h ) +2
| {z } 2m
↓ (bias improves)
richer class

The second term increases because K′ > K.

Trade-o:

ˆ Larger H: bias ↓, variance ↑

ˆ Smaller H: bias ↑, variance ↓

Error optimal complexity High Variance

bias
High Bias

Generalization error
variance

Training error
Model complexity
What Each Region Means

Region Cause Remedy

High Bias H too simple; can't t data Add features / use richer
model

High Vari- H too complex; ts noise Get more data / regularize
ance

Sweet Spot Balanced Cross-validation to select

8
CS229  Machine Learning Lecture 9: Learning Theory

9 The Proof Strategy: A Bird's-Eye View

Hoeding's Union
Inequality Bound

Uniform Convergence
Union Bound for all h ∈ H
2
P[|ε̂(hj ) − ε(hj )| > γ] ≤ 2e−2γ m

for one hypothesis w.p. ≥ 1 − 2Ke −2γ 2 m

ERM def.
Main Theorem:
ε(ĥ) ≤ ε(h∗ ) + 2γ
w.p.≥1−δ

10 Looking Ahead: Innite Hypothesis Classes

Limitation: What About |H| = ∞?
Logistic regression has K =∞ (innitely many possible parameter vectors θ ∈ Rn ). Our
bound 2Ke −2γ 2 m blows up!

The x comes in Lecture 10: replace K with the VC dimension of H  a measure of the
eective complexity of an innite class. The sample complexity still grows only polynomially
(not exponentially) in the VC dimension.

VC Dimension (Preview)

The VapnikChervonenkis (VC) dimension dV C (H) is the largest set of points that H
can shatter (correctly classify in all 2d possible labelings).

For linear classiers in Rn : dV C = n + 1.

The analog of our bound for innite classes:

  
1 1 1
m=O dV C log + log
γ2 γ δ

11 The Grand Picture: Connecting Everything

11.1 How Lecture 9 Fits the CS229 Arc
Lin. Reg LWR Logistic GLM
(L12) (L3) (L34) (L4)

GDA NB
SVM+ Learning
Kernel Theory
(L5) (L56)
(L68) (L9)

Regulariz. VC Dim.
/ Model Sel. (L10)
(L10+)

9
CS229  Machine Learning Lecture 9: Learning Theory

11.2 Explicit Connections Across Lectures

1. Bias (L13) ↔ Formal Bias Term ε(h∗ ): In Lecture 3 we observed that a linear model
underts a quadratic data set. Formally, this means ε(h∗ ) > 0  the best hypothesis in the
linear class H still has non-zero generalization error. The bias term in our bound quanties
exactly how much irreducible error this model class incurs.

2. Regularization / Model Complexity (L4 GLMs) ↔ Variance Term: The second term
q
log(2K/δ)
2m in our bound grows with K  the size of the hypothesis class. Regularization

(L4) articially shrinks H by penalizing large parameters, which reduces K eectively and
thus reduces variance.

3. MLE (throughout) ↔ ERM: Maximum likelihood estimation, which underpins logistic

regression and GDA, is a special case of ERM with log-loss. Everything we proved about
ERM applies directly to MLE-based algorithms with appropriate loss substitutions.

4. SVM's Margin ↔ Learning Theory: The SVM maximizes the geometric margin. It turns
out (via VC theory) that the VC dimension of large-margin classiers is smaller than that
of all linear classiers. The SVM implicitly regularizes H by forcing large margins, which
tightens our generalization bound. The margin and the bound are formally linked.

5. Bandwidth in LWR (L3) ↔ Model Complexity: The bandwidth τ in locally weighted

regression controls model complexity  small τ overts (high variance), large τ underts
(high bias). This is the same trade-o formalized by our theorem: a small τ corresponds to
a large eective K , worsening the variance term.

6. Soft-Margin SVM's C (L8) ↔ Bias-Variance: Large C = near hard margin = small

eective H = low variance, but potentially high bias. Small C = large H = high variance but
low bias. This is precisely our formal bias-variance trade-o, expressed as a hyperparameter.

7. Hoeding ↔ Cross-Validation (future): Hoeding tells us the sample mean concentrates

around the true mean. This is why cross-validation works: the average error on a held-out set
is a good estimate of generalization error (an application of Hoeding on the held-out set).

8. Gaussian Kernel's σ (L8) ↔ Complexity: Choosing σ is equivalent to choosing model

complexity. Small σ creates an innite-dimensional classier that can memorize data (high
variance); large σ creates a smoother, simpler classier (lower variance, higher bias).

10
CS229  Machine Learning Lecture 9: Learning Theory

12 Quick Reference: Key Formulas

Concept Formula Notes

1 (i) ) ̸= y (i) ]
P
Training error ε̂(h) = m i 1[h(x Computable

Generalization er- ε(h) = P(x,y)∼D [h(x) ̸= y] Unknown

ror

ERM ĥ = arg minh∈H ε̂(h) Our algorithm

2m
Hoeding P[|ϕ̂ − ϕ| > γ] ≤ 2e−2γ Key lemma
P
Union bound P[∪j Aj ] ≤ j P[Aj ] Key lemma

Uniform conv. P[∃h : |ε̂(h) − ε(h)| > γ] ≤ Main result

2
2Ke−2γ m
q
Error bound ε(ĥ) ≤ ε(h∗ ) + 2 log(2K/δ)
2m Final theorem

1
Sample complex- m≥ 2γ 2
log 2K
δ How much data
ity

What really separates the people that really understand machine learning, compared to people

 Andrew Ng, Lecture 9

that maybe read the textbook, will be what you do next. Will be in your decisions of what to do
when the algorithm doesn't quite do what you wanted.

11