文章

Generalization Bound and Complexity

作者：Mipha

发布于 2026-08-05T06:48:38Z · 公开内容更新于 2026-08-17T13:59:20Z

In this blog, we talk about the generalization ability of function class in machine learning. We assume that readers have basic knowledge of machine learning.

Generalization Bound and Complexity

Mipha

(August 17, 2026)

1 Introduction

In this blog, we talk about the generalization ability of function class in machine learning. We assume that readers have basic knowledge of machine learning.

2 Risk and Empirical Risk Minimization

Definition 1 (Population Risk).

The population risk of a hypothesis $ℎ$ is defined as

𝑅 (ℎ) = 𝔼 (𝑥, 𝑦) \sim D [ℓ (ℎ (𝑥), 𝑦)],

where $ℓ$ is the loss function and $D$ is the data distribution.

Definition 2 (Empirical Risk).

The empirical risk of a hypothesis $ℎ$ is defined as

ˆ 𝑅 (ℎ) = 1 𝑛 𝑛 \sum 𝑖 = 1 ℓ (ℎ (𝑥 𝑖), 𝑦 𝑖),

where $(𝑥 𝑖, 𝑦 𝑖)$ are i.i.d. samples from $D$ and $𝑛$ is the number of samples.

In generalization theory, our goal is to minimize the population risk $𝑅 (𝑓)$ , or equivalently, to minimize the excess risk $𝑅 (𝑓) - 𝑅 (𝑓 *)$ , where $𝑓 *$ is the Bayes optimal predictor. However, since we do not have access to the data distribution $D$ , we can only minimize the empirical risk $ˆ 𝑅 (𝑓)$ based on the training data. Therefore, we need to analyze the relationship between the population risk and the empirical risk, which is known as generalization analysis.

Definition 3 (ERM).

Empirical Risk Minimization (ERM) is a learning paradigm that aims to find a hypothesis $ˆ 𝑓$ that minimizes the empirical risk $ˆ 𝑅 (𝑓)$ over a hypothesis class $F$ :

ˆ 𝑓 = a r g m i n 𝑓 \in H ˆ 𝑅 (𝑓) .

Proposition 4 (Risk Minimization Decomposition).

The excess risk can be decomposed as follows:

𝑅 (ˆ 𝑓) - 𝑅 (𝑓 *) = (𝑅 (ˆ 𝑓) - i n f 𝑓' \in F 𝑅 (𝑓')) ⏟____⏟____⏟ E s t i m a t i o n E r r o r + (i n f 𝑓' \in F 𝑅 (𝑓') - 𝑅 (𝑓 *)) ⏟_____⏟_____⏟ A p p r o x i m a t i o n E r r o r .

The estimation error is often further decomposed using $𝑔 F \in a r g m i n 𝑓 \in F 𝑅 (𝑓)$ as the best-in-class predictor:

𝑅 (ˆ 𝑓) - i n f 𝑓' \in F 𝑅 (𝑓') = 𝑅 (ˆ 𝑓) - 𝑅 (𝑔 F) = (𝑅 (ˆ 𝑓) - ˆ 𝑅 (ˆ 𝑓)) + (ˆ 𝑅 (ˆ 𝑓) - ˆ 𝑅 (𝑔 F)) + (ˆ 𝑅 (𝑔 F) - 𝑅 (𝑔 F)) \leq s u p 𝑓 \in F (𝑅 (𝑓) - ˆ 𝑅 (𝑓)) + 0 + s u p 𝑓 \in F (ˆ 𝑅 (𝑓) - 𝑅 (𝑓)) \leq 2 s u p 𝑓 \in F ∣ 𝑅 (𝑓) - ˆ 𝑅 (𝑓) ∣

3 Generalization Bounds

Theorem 5 (Uniform Bound for Finite Models).

We assume loss functions from $F$ are bounded between $0$ and $𝑙 \infty$ . For any $𝛿 \in (0, 1)$ , with probability greater than $1 - 𝛿$ , we have:

s u p 𝑓 \in F ∣ 𝑅 (𝑓) - ˆ 𝑅 (𝑓) ∣ \leq 𝑙 \infty \sqrt l o g (2 | F |) 2 𝑛 + 𝑙 \infty \sqrt 2 𝑛 \sqrt l o g 1 𝛿

Proof.

For any fixed $𝑓 \in F$ , Hoeffding’s inequality gives

ℙ (∣ 𝑅 (𝑓) - ̂ 𝑅 (𝑓) ∣ > 𝑡) \leq 2 e x p (- 2 𝑛 𝑡 2 𝑙 2 \infty) .

Applying the union bound over $F$ ,

ℙ (s u p 𝑓 \in F ∣ 𝑅 (𝑓) - ̂ 𝑅 (𝑓) ∣ > 𝑡) \leq 2 | F | e x p (- 2 𝑛 𝑡 2 𝑙 2 \infty) .

Setting the right-hand side equal to $𝛿$ yields

𝑡 = 𝑙 \infty \sqrt l o g (2 | F |) + l o g (1 / 𝛿) 2 𝑛 .

Using $\sqrt 𝑎 + 𝑏 \leq \sqrt 𝑎 + \sqrt 𝑏$ , we obtain, with probability at least $1 - 𝛿$ ,

s u p 𝑓 \in F ∣ 𝑅 (𝑓) - ̂ 𝑅 (𝑓) ∣ \leq 𝑙 \infty \sqrt l o g (2 | F |) 2 𝑛 + 𝑙 \infty \sqrt 2 𝑛 \sqrt l o g 1 𝛿 .

∎

Remark 6.

We can not say that $∣ 𝑅 (ˆ 𝑓) - ˆ 𝑅 (ˆ 𝑓) ∣$ can be bounded as well since $ˆ 𝑅$ is data-depended and thus we can’t apply Hoeffding’s inequality.

Definition 7 (Covering Number).

We assume that for $𝜀 > 0$ there are $𝑚 = 𝑚 (𝜀)$ elements $𝑓 1, \dots 𝑓 𝑚 \in F$ such that for any $𝑓 \in F$ , there exists $𝑖 \in [𝑚]$ , $Δ (𝑓, 𝑓 𝑖) \leq 𝜀$ . Here, $𝑚 (𝜀)$ is called the covering number of $F$ .

Theorem 8 (Uniform Bound for Infinite Models).

We assume the loss function is G-Lipschitz with respect to the second argument and is bounded between $0$ and $𝑙 \infty$ . $𝑚 (𝜀)$ is the covering number with respect to $𝜀 > 0$ . For any $𝛿 \in (0, 1)$ , with probability greater than $1 - 𝛿$ , we have:

s u p 𝑓 \in F ∣ 𝑅 (𝑓) - ˆ 𝑅 (𝑓) ∣ \leq 2 𝐺 𝜀 + 𝑙 \infty \sqrt l o g (2 𝑚 (𝜀)) 2 𝑛 + 𝑙 \infty \sqrt 2 𝑛 \sqrt l o g 1 𝛿

Proof.

Let ${𝑓 1, \dots, 𝑓 𝑚}$ be an $𝜀$ -cover of $F$ , where $𝑚 = 𝑚 (𝜀)$ . For every $𝑓 \in F$ , choose $𝑓 𝑖$ such that

Δ (𝑓, 𝑓 𝑖) \leq 𝜀 .

By the $𝐺$ -Lipschitz property,

| 𝑅 (𝑓) - 𝑅 (𝑓 𝑖) | \leq 𝐺 Δ (𝑓, 𝑓 𝑖) \leq 𝐺 𝜀,

and similarly,

| ̂ 𝑅 (𝑓) - ̂ 𝑅 (𝑓 𝑖) | \leq 𝐺 Δ (𝑓, 𝑓 𝑖) \leq 𝐺 𝜀 .

Hence,

| 𝑅 (𝑓) - ̂ 𝑅 (𝑓) | \leq | 𝑅 (𝑓) - 𝑅 (𝑓 𝑖) | + | 𝑅 (𝑓 𝑖) - ̂ 𝑅 (𝑓 𝑖) | + | ̂ 𝑅 (𝑓 𝑖) - ̂ 𝑅 (𝑓) | \leq 2 𝐺 𝜀 + | 𝑅 (𝑓 𝑖) - ̂ 𝑅 (𝑓 𝑖) | .

Therefore,

s u p 𝑓 \in F | 𝑅 (𝑓) - ̂ 𝑅 (𝑓) | \leq 2 𝐺 𝜀 + m a x 𝑖 \in [𝑚] | 𝑅 (𝑓 𝑖) - ̂ 𝑅 (𝑓 𝑖) | .

Applying the finite-model bound to ${𝑓 1, \dots, 𝑓 𝑚}$ , with probability at least $1 - 𝛿$ ,

m a x 𝑖 \in [𝑚] | 𝑅 (𝑓 𝑖) - ̂ 𝑅 (𝑓 𝑖) | \leq 𝑙 \infty \sqrt l o g (2 𝑚) 2 𝑛 + 𝑙 \infty \sqrt 2 𝑛 \sqrt l o g 1 𝛿 .

Substituting $𝑚 = 𝑚 (𝜀)$ proves the result. ∎

4 Rademacher Complexity

Definition 9 (Rademacher Complexity).

Let $𝑆 = (𝑍 1, \dots, 𝑍 𝑛)$ be an i.i.d. sample and let $𝜎 1, \dots, 𝜎 𝑛$ be independent Rademacher random variables, i.e.,

ℙ (𝜎 𝑖 = 1) = ℙ (𝜎 𝑖 = - 1) = 12 .

For a function class $H$ , its empirical Rademacher complexity is

̂ ℜ 𝑆 (H) : = 𝔼 𝜎 [s u p ℎ \in H ∣ 1 𝑛 𝑛 \sum 𝑖 = 1 𝜎 𝑖 ℎ (𝑍 𝑖) ∣] .

Its expected Rademacher complexity is

ℜ 𝑛 (H) : = 𝔼 𝑆 [̂ ℜ 𝑆 (H)] .

For the risk $𝑅 (𝑓) = 𝔼 [ℓ (𝑌, 𝑓 (𝑋))]$ , we take

H = ℓ \circ F : = {(𝑥, 𝑦) \mapsto ℓ (𝑦, 𝑓 (𝑥)) : 𝑓 \in F} .

Proposition 10 (Symmetrization).

Let $𝑆 = (𝑍 1, \dots, 𝑍 𝑛)$ be an i.i.d. sample. Then

𝔼 𝑆 [s u p 𝑓 \in F ∣ 𝑅 (𝑓) - ̂ 𝑅 (𝑓) ∣] \leq 2 ℜ 𝑛 (ℓ \circ F) .

Proof.

Let $𝑆' = (𝑍' 1, \dots, 𝑍' 𝑛)$ be an independent copy of $𝑆$ . Then

𝔼 𝑆 s u p 𝑓 \in F | 𝑅 (𝑓) - ̂ 𝑅 (𝑓) | \leq 𝔼 𝑆, 𝑆' s u p 𝑓 \in F ∣ 1 𝑛 𝑛 \sum 𝑖 = 1 (ℓ 𝑓 (𝑍' 𝑖) - ℓ 𝑓 (𝑍 𝑖)) ∣ = 𝔼 𝑆, 𝑆', 𝜎 s u p 𝑓 \in F ∣ 1 𝑛 𝑛 \sum 𝑖 = 1 𝜎 𝑖 (ℓ 𝑓 (𝑍' 𝑖) - ℓ 𝑓 (𝑍 𝑖)) ∣ \leq 2 ℜ 𝑛 (ℓ \circ F),

where $ℓ 𝑓 (𝑥, 𝑦) : = ℓ (𝑦, 𝑓 (𝑥))$ . ∎

Theorem 11 (Generalization Bound for Rademacher Complexity).

Assume that

0 \leq ℓ (𝑦, 𝑓 (𝑥)) \leq 𝑙 \infty

for every $𝑓 \in F$ . For any $𝛿 \in (0, 1)$ , with probability at least $1 - 𝛿$ ,

s u p 𝑓 \in F ∣ 𝑅 (𝑓) - ̂ 𝑅 (𝑓) ∣ \leq 2 ℜ 𝑛 (ℓ \circ F) + 𝑙 \infty \sqrt l o g (1 / 𝛿) 2 𝑛 .

Proof.

Define

Φ (𝑆) : = s u p 𝑓 \in F | 𝑅 (𝑓) - ̂ 𝑅 (𝑓) | .

Replacing one observation changes $Φ (𝑆)$ by at most $𝑙 \infty / 𝑛$ . Hence, by McDiarmid’s inequality,

Φ (𝑆) \leq 𝔼 𝑆 [Φ (𝑆)] + 𝑙 \infty \sqrt l o g (1 / 𝛿) 2 𝑛

with probability at least $1 - 𝛿$ . By symmetrization,

𝔼 𝑆 [Φ (𝑆)] \leq 2 ℜ 𝑛 (ℓ \circ F),

which proves the result. ∎

Theorem 12 (Generalization Bound for Rademacher Complexity(Empirical)).

Assume that

0 \leq ℓ (𝑦, 𝑓 (𝑥)) \leq 𝑙 \infty

for every $𝑓 \in F$ . For any $𝛿 \in (0, 1)$ , with probability at least $1 - 𝛿$ ,

s u p 𝑓 \in F ∣ 𝑅 (𝑓) - ̂ 𝑅 (𝑓) ∣ \leq 2 ̂ ℜ 𝑆 (ℓ \circ F) + 3 𝑙 \infty \sqrt l o g (2 / 𝛿) 2 𝑛 .

Proof.

By the preceding theorem, with probability at least $1 - 𝛿 / 2$ ,

s u p 𝑓 \in F | 𝑅 (𝑓) - ̂ 𝑅 (𝑓) | \leq 2 ℜ 𝑛 (ℓ \circ F) + 𝑙 \infty \sqrt l o g (2 / 𝛿) 2 𝑛 .

Moreover, bounded differences gives, with probability at least $1 - 𝛿 / 2$ ,

ℜ 𝑛 (ℓ \circ F) \leq ̂ ℜ 𝑆 (ℓ \circ F) + 𝑙 \infty \sqrt l o g (2 / 𝛿) 2 𝑛 .

Combining the two inequalities and applying the union bound yields

s u p 𝑓 \in F | 𝑅 (𝑓) - ̂ 𝑅 (𝑓) | \leq 2 ̂ ℜ 𝑆 (ℓ \circ F) + 3 𝑙 \infty \sqrt l o g (2 / 𝛿) 2 𝑛 .

∎

Generalization Bound and Complexity

1 Introduction

2 Risk and Empirical Risk Minimization

Definition 1 (Population Risk).

Definition 2 (Empirical Risk).

Definition 3 (ERM).

Proposition 4 (Risk Minimization Decomposition).

3 Generalization Bounds

Theorem 5 (Uniform Bound for Finite Models).

Proof.

Remark 6.

Definition 7 (Covering Number).

Theorem 8 (Uniform Bound for Infinite Models).

Proof.

4 Rademacher Complexity

Definition 9 (Rademacher Complexity).

Proposition 10 (Symmetrization).

Proof.

Theorem 11 (Generalization Bound for Rademacher Complexity).

Proof.

Theorem 12 (Generalization Bound for Rademacher Complexity(Empirical)).

Proof.

References