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 STAT 210B at UC Berkeley, taught by Song Mei [15]; High-Dimensional Probability and Introduction to Machine Learning at Peking University, taught by Zhihua Zhang and Lei Wu, respectively [29, 25]; STAT 300B at Stanford University [6]; and STAT 364 at Yale University [26]. I also referred to the book High-Dimensional Statistics: A Non-Asymptotic Viewpoint [24].
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