6 Function Spaces
Data in the real world often takes the form \(y=f(x)+\epsilon \), and a central question is to understand the function space in which \(f\) lives. In this section, we examine several perspectives on function spaces. The section is organized as follows:
- 1.
- Rademacher Complexity
- 2.
- Metric Entropy Method
- 3.
- Glivenko-Cantelli Theorem and Donsker Theorem
- 4.
- Information Theory
This section mainly follows STAT210B (UC Berkeley, taught by Song Mei), High-dimensional probability (PKU, taught by Zhihua Zhang), Introduction to Machine Learning (PKU, taught by Lei Wu), STAT300B (Stanford), STAT364 (Yale). I also referred to the book High-Dimensional Statistics: A Non-Asymptotic Viewpoint [6].
6.1.1 Empirical Process Theory
6.1.2 Rademacher Complexity Bounds
6.1.3 VC Dimension
6.2 Metric Entropy Method
6.2.1 Entropies of Function Classes
6.2.2 One-step Discretization Bound
6.2.3 Chaining Method
6.2.4 Examples of Rademacher Complexity Bounds
6.3 Glivenko-Cantelli Theorem and Donsker Theorem
6.3.1 Glivenko-Cantelli Theorem
6.3.2 Donsker Theorem
6.4 Information Theory
6.4.1 Fundamentals
6.4.2 Data Processing Inequalities
6.4.3 Minimax Lower Bound