Statistical Learning Theory for Hyperparameter Optimization

Learn about statistical learning theory in hyperparameter optimization. Understand generalization bounds, PAC learning, and statistical guarantees.

Introduction

Statistical learning theory provides theoretical foundations for understanding generalization in machine learning. These principles apply to hyperparameter optimization, explaining why validation sets work and how to achieve good generalization.

Generalization Error

True Error

R(λ) = E_(x,y)~D[L(f_λ(x), y)]

Expected loss on distribution D.

Empirical Error

R̂_S(λ) = (1/n) Σ_i=1ⁿ L(f_λ(x_i), y_i)

Average loss on sample S.

Generalization Bounds

Basic Bound

With probability 1-δ:

R(λ) ≤ R̂_S(λ) + O(√(log|Λ|/n))

VC Dimension Bound

R(λ) ≤ R̂_S(λ) + O(√(d_VC log(n/d_VC)/n))

Where d_VC is Vapnik-Chervonenkis dimension.

PAC Learning

Definition

Probably Approximately Correct learning:

Probably: With high probability
Approximately: Within ε of optimal
Correct: Generalizes well

Sample Complexity

n ≥ (1/ε) log(|Λ|/δ)

Uniform Convergence

Key Principle

Empirical error uniformly close to true error:

P(sup_λ |R(λ) - R̂_S(λ)| > ε) ≤ δ

Rademacher Complexity

Definition

R_n(F) = E_S,σ[sup_f∈F (1/n) Σ σ_i f(x_i)]

Measures function class complexity.

Generalization Bound

R(λ) ≤ R̂_S(λ) + 2R_n(F) + O(√(log(1/δ)/n))

Key Insight

Statistical learning theory explains why hyperparameter optimization on validation sets generalizes. Generalization bounds quantify the trade-off between model complexity and sample size.

Bias-Variance Trade-off

Decomposition

E[R(λ)] = Bias² + Variance + Irreducible Error

Hyperparameter Role

Hyperparameters control:

Bias: Model capacity
Variance: Regularization
Trade-off: Balance both

Cross-Validation Theory

k-Fold CV

Unbiased estimate of generalization error:

CV(λ) = (1/k) Σ_i=1^k R̂_S_i(λ)

Variance Reduction

Multiple folds reduce variance:

More stable estimates
Better hyperparameter selection
Reduced overfitting

Frequently Asked Questions

What is generalization error?

Generalization error R(λ) = E[L(f_λ(x), y)] is expected loss on unseen data. It measures how well model performs on new examples beyond training data.

What are generalization bounds?

Generalization bounds relate true error R(λ) to empirical error R̂_S(λ) with high probability: R(λ) ≤ R̂_S(λ) + complexity_term. They quantify generalization ability.

What is PAC learning?

PAC (Probably Approximately Correct) learning means learning with high probability (probably) to within ε of optimal (approximately correct). Sample complexity: n ≥ (1/ε) log(|Λ|/δ).

What is VC dimension?

VC (Vapnik-Chervonenkis) dimension measures model complexity - maximum number of points that can be shattered. Appears in generalization bounds: R(λ) ≤ R̂_S(λ) + O(√(d_VC/n)).

What is Rademacher complexity?

Rademacher complexity measures function class complexity using random signs. It appears in generalization bounds and provides tighter bounds than VC dimension for many cases.