Introduction to Generalization

January 11, 2026

Table of Contents

1 Introduction

2 Union bound + covering number

3 Rademachor average

4 VC-dimension

Introduction to Generalization January 11, 2026 2 / 17

 Introduction

Introduction

Motivation: training data→unseen data (generalization)

i.i.d
Given D , {(x1 , y1 ), (x2 , y2 ), · · · , (xn , yn )}, (xi , yi ) ∼ P , want to
learn a function f (x) = y
Metric of learning:
Loss function: `(f (x), y )
Examples: `(f (x), y ) = 1f (x)6=y (classification),
`(f (x), y ) = kf (x) − y k22 (regression),
Pn ...
Empirical/training loss: n1 i=1 `(f (xi ), yi )
Trivial solution: fˆ(x) = y if x ∈ D; fˆ(x) = 0 otherwise.
Expected loss: EP (`(f (x),
Pny )).
Generalization error: | n1 i=1 `(f (xi ), yi ) − E[`(f (xi ), yi )]|

Introduction to Generalization January 11, 2026 3 / 17

 Introduction

Fixed f

Theorem
(Hoeffding’s inequality). Let X1 , · · · , Xn be independent random variables
such that Xi takes its values in [ai , bi ] almost surely for all i 6 n. Then for
every  > 0,
n
X  22 
P{ (Xi − E[Xi ]) > } 6 exp − Pn 2
.
i=1 i=1 (bi − ai )

and
n
X  22 
P{ (Xi − E[Xi ]) 6 −} 6 exp − Pn 2
.
i=1 i=1 (bi − ai )

Introduction to Generalization January 11, 2026 4 / 17

 Introduction

Fixed f

If `(f (x), y ) is bounded, e.g., `(f (x), y ) = 1f (x)6=y , then we have

n
1X  
P{ `(f (xi ), yi ) − E[`(f (xi ), yi )] > } 6 exp − 2n2 .
n
i=1

and
n
1X  
P{ `(f (xi ), yi ) − E[`(f (xi ), yi )] 6 −} 6 exp − 2n2 .
n
i=1

i.i.d
BUT: for learning, f depends on training data (xi , yi ) ∼ P,
i = 1, · · · , n.

Introduction to Generalization January 11, 2026 5 / 17

 Introduction

Bounding the supremum of empirical process

1 Pn
Empirical process: Pn f − Pf , Pn = n i=1 f (xi ), Pf = E[f (x)]
Goal: find supf ∈F |Pn f − Pf |
Union bound + covering number
Rademachor average
VC dimension

Introduction to Generalization January 11, 2026 6 / 17

 Union bound + covering number

Finite function classes

f ∈ F, F finite, e.g., f (x) = wx, w ∈ {0, 1}.

Apply Hoeffding’s inequality to each f ∈ F, and then use union bound

Theorem
(Uniform error bound for finite F). Let F be finite. Then for any  > 0,
n
n 1X o 2n2
P sup | f (xi ) − Ef | >  6 |F| exp(− ).
f ∈F n kFk2∞
i=1

or
n
r
n 1X (t + log |F|)kFk2∞ o
P sup | f (xi ) − Ef | > 6 e −t
f ∈F n i=1
n

Introduction to Generalization January 11, 2026 7 / 17

 Union bound + covering number

Infinite class

F is totally bounded
-cover of F, {g1 , · · · , gN }, kf − gi k < , for some i = 1, · · · , N,
N = N(F, , k · k)
| P (f ) − P(f ) | = |(Pn − P)(f − gf ) + (Pn − P)gf | 6
| n {z }
empirical process of f
|(Pn − P)(f − gf )| + |(Pn − P)gf | , gf ∈ -cover of F
| {z } | {z }
62 6supf ∈F |(Pn −P)gf |
supf ∈F |(Pn − P)gf | = supg ∈-cover of F |(Pn − P)g |, Uniform error
bound for finite F r
(t + log N(F, , k · k))kFk2∞
|Pn (f ) − P(f )| 6 2 + with probability
| {z n }
minimize w .r .t. 

Introduction to Generalization January 11, 2026 8 / 17

 Rademachor average

Self bounding property

Theorem
(McDiarmid’s inequality). Consider independent random variables
X1 , · · · , Xn ∈ X and a mapping φ : X n → R. If, for all i ∈ {1, · · · , n}, and
for all x1 , · · · , xn , xi0 ∈ X , the function f satisfies

|φ(x1 , · · · , xi−1 , xi , xi+1 , · · · , xn ) − φ(x1 , · · · , xi−1 , xi0 , xi+1 , · · · , xn )| 6 ci

then
n o −2t 2
P φ(X1 , · · · , Xn ) − Eφ) > t > exp( Pn 2
)
i=1 ci

and
n o −2t 2
P f φ(X1 , · · · , Xn ) − Eφ) 6 −t > exp( Pn 2
)
i=1 ci

Introduction to Generalization January 11, 2026 9 / 17

 Rademachor average

Symmetrization
φ(X1 , · · · , Xn ) = supf ∈F |Pn f − Pf |
McDiarmid’s inequality:
r
2τ kFk2∞
sup |Pn f − Pf | 6 E[sup |Pn f − Pf |] +
f ∈F f ∈F n
with probability at least 1 − exp(−τ ).
Lemma
(Symmetrization). It holds that
n
1X
EX1 ,··· ,Xn [sup {|Pn f − Pf |] 6 2E EX1 ,··· ,Xn [sup | i f (xi )|],
f ∈F f ∈F n
i=1

where i , i = 1, · · · , n are i.i.d. Rademachor random variables, i.e.,

P(i = 1) = 12 and P(i = −1) = 12 .
d
Core idea of proof: f (xi ) − f (xi0 ) = − f (xi ) − f (xi0 )


Introduction to Generalization January 11, 2026 10 / 17
 Rademachor average

Rademachor Average

Pn Pn
E EX [supf ∈F | n1 i=1 i f (xi )|] = EX E|X [supf ∈F | n1 i=1 i f (xi )|]
Pn
Rademachor average of F: Rn (F) = E|X [supf ∈F | n1 i=1 i f (xi )|]
F(X) , {(f (X1 ), · · · , f (Xn )) : f ∈ F}
Rn (F) = E|X supf∈F (X) | n1 T f| 6 E|X supf∈F (X) n1 kk2 kfk2 6 kFk∞
q
2
McDiarmid: ERn (F) 6 Rn (F) + 2τ kFn k∞ , with probability at least
1 − exp(−τ ).
q
2
supf ∈F |Pn f − Pf | 6 2Rn (F) + 3 2τ kFn k∞
Bounding Rn (F)

Introduction to Generalization January 11, 2026 11 / 17

 Rademachor average

F is finite
Lemma
(Finite-class lemma). Let X1 , · · · , Xn be random variables such that
λ2 σ 2
Ee λXi 6 e 2 0 and some σ 2 > 0. Then
, ∀λ > q
log n
E[maxi=1,··· ,n Xi ] 6 σ 2 .

n
1X
Rn (F) = E|X [supf ∈F | i f (xi )|] =
n
i=1
| {z }
yf
E[max{y1 , −y1 , · · · , y|F | , −y|F | }].
2 kF k2
Ee λyf 6 exp( λ 2n
∞
)
q
kF k∞ log(2|F |)
Rn (F) 6 √
n 2
q
|)
supf ∈F |Pn f − Pf | 6 O( log(2|F
n + √1 )
n
Introduction to Generalization January 11, 2026 12 / 17
 VC-dimension

Bounding Rademacher average

Rn (F) = E|X supf∈F (X) | n1 T f|

Suppose F consists of {−1, 1} valued function and |F(X)| 6 2n
Example: F = {1(−∞,t] : t ∈ R}
q q
kF k∞ log(2|F (X)|) kF k∞ log(2|F |)
Finite-class lemma: Rn (F) 6 √
n 2 6 √
n 2

Introduction to Generalization January 11, 2026 13 / 17

 VC-dimension

Shattering and VC-dimension

Definition
(Shattering and VC dimension).
Let F be a class of {±1}-valued functions on X .
Shattering: a set of n points {x1 , · · · , xn } ⊂ X is shattered by H if all
possible 2n binary labelings of the points can be realized by functions
in F.
VC dimension: The VC dimension of F, denoted by VCdim(F), is the
cardinality of the largest set of points in X that can be shattered by F.
If F shatters arbitrarily large sets of points in X , then
VCdim(F) = ∞.

Introduction to Generalization January 11, 2026 14 / 17

 VC-dimension

Example

Linear classifier: f (x) = sign(w T x + b), x ∈ X ⊂ R2

VCdim(f ) = 3

Figure: Three points shattered by linear classifiers

Introduction to Generalization January 11, 2026 15 / 17

 VC-dimension

Generalization error for classification

Theorem
(Uniform error bound for general F). Let VCdim(F) be finite. Then for
any  > 0,
n
n 1X
o
PD∼P n sup `0−1 (f (xi ), yi ) − EP [`0−1 (f (xi ), yi )] > )
f ∈F n i=1
6 4(2en) VCdim(F )
exp(−n2 /8)

or EP [`0−1 (f (xi ), yi )] 6
s
n

1X 8 VCdim(F) · (ln(2n) + 1) + ln(4/δ)
`0−1 (f (xi ), yi ) +
n n
i=1

with probability at least 1 − δ.

Introduction to Generalization January 11, 2026 16 / 17
 VC-dimension

n > VCdim(F)

Lemma
(Sauer-Shelah lemma). Let F be a 
class
 of functions such that VC (F) < h.
Ph n h
Then for all n ∈ N, sF (n) 6 i=0 and for all n > h, sF (n) 6 en
h .
i
√
Rn (F) 6 O( log n/n)

Introduction to Generalization January 11, 2026 17 / 17