Rademacher Complexity

"A class is complex when it can fit randomness on the sample it was handed."

Overview

Rademacher complexity is a data-dependent measure of how well a function class correlates with random signs.

Statistical learning theory is the chapter where finite samples meet future performance. It does not ask only whether a model performed well on observed data. It asks what assumptions let observed performance control unobserved risk.

This section is written in LaTeX Markdown. Inline mathematics uses $...$, and display equations use `

`. The notes emphasize theorem-level objects such as risk, hypothesis class, sample complexity, capacity, and confidence.

Prerequisites

• Generalization Bounds
• Functional Analysis
• Kernel Methods
• Robustness and Distribution Shift

Companion Notebooks

Learning Objectives

After completing this section, you will be able to:

• Define true risk, empirical risk, and generalization gap
• State PAC guarantees using $\epsilon$ and $\delta$
• Derive finite-class sample complexity with union bounds
• Compute simple VC dimensions and growth functions
• Explain the bias-variance decomposition under squared loss
• Compare finite-class, VC, margin, norm, and Rademacher bounds
• Estimate simple Rademacher complexity by simulation
• Separate learnability theory from empirical benchmarking
• Identify when classical assumptions fail for modern AI systems
• Use learning-theory notation consistently with the repo guide

Study Flow

1. Read the pages in order and pause after each page to restate the main definition or theorem.
2. Run theory.ipynb when you want to check the formulas numerically.
3. Use exercises.ipynb after the reading path, not before it.
4. Return to this overview page when you need the chapter-level navigation.

Runnable Companions

• Theory notebook
• Exercises notebook