[local]1[/local][local]1[/local]Contents
Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
1 Why Is Nonparametric Regression Important? . . . . . . . 1
1.1 Regression Analysis and L2 Risk . . . . . . . . . . . . . . . . . . . . . 1
1.2 Regression Function Estimation and L2 Error . . . . . . . . . . 2
1.3 Practical Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Application to Pattern Recognition . . . . . . . . . . . . . . . . . . . 6
1.5 Parametric versus Nonparametric Estimation . . . . . . . . . . 9
1.6 Consistency. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.7 Rate of Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.8 Adaptation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.9 Fixed versus Random Design Regression . . . . . . . . . . . . . . . 15
1.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Problems and Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2 How to Construct Nonparametric Regression Estimates?.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1 Four Related Paradigms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2 Curse of Dimensionality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 Bias–Variance Tradeoff . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4 Choice of Smoothing Parameters and Adaptation . . . . . . . 26
2.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Problems and Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3 Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.1 Slow Rate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 Minimax Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3 Individual Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.4 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Problems and Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4 Partitioning Estimates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.2 Stone’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.3 Consistency. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.4 Rate of Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
Problems and Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5 Kernel Estimates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.2 Consistency. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.3 Rate of Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.4 Local Polynomial Kernel Estimates . . . . . . . . . . . . . . . . . . . 80
5.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
Problems and Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6 k-NN Estimates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.2 Consistency. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.3 Rate of Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
6.4 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
Problems and Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
7 Splitting the Sample . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
7.1 Best Random Choice of a Parameter . . . . . . . . . . . . . . . . . . 100
7.2 Partitioning, Kernel, and Nearest Neighbor Estimates . . . 105
7.3 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
Problems and Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
8 Cross-Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
8.1 Best Deterministic Choice of the Parameter . . . . . . . . . . . . 112
8.2 Partitioning and Kernel Estimates . . . . . . . . . . . . . . . . . . . . 113
8.3 Proof of Theorem 8.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
8.4 Nearest Neighbor Estimates . . . . . . . . . . . . . . . . . . . . . . . . . 126
8.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
Problems and Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
9 Uniform Laws of Large Numbers . . . . . . . . . . . . . . . . . . . . . 130
9.1 Basic Exponential Inequalities . . . . . . . . . . . . . . . . . . . . . . . 131
9.2 Extension to Random L1 Norm Covers . . . . . . . . . . . . . . . . 134
9.3 Covering and Packing Numbers . . . . . . . . . . . . . . . . . . . . . . 140
9.4 Shatter Coefficients and VC Dimension . . . . . . . . . . . . . . . . 143
9.5 A Uniform Law of Large Numbers . . . . . . . . . . . . . . . . . . . . 153
9.6 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
Problems and Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
10 Least Squares Estimates I: Consistency . . . . . . . . . . . . . . . 158
10.1 Why and How Least Squares? . . . . . . . . . . . . . . . . . . . . . . . . 158
10.2 Consistency from Bounded to Unbounded Y . . . . . . . . . . . 165
10.3 Linear Least Squares Series Estimates . . . . . . . . . . . . . . . . . 170
10.4 Piecewise Polynomial Partitioning Estimates . . . . . . . . . . . 174
10.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
Problems and Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
11 Least Squares Estimates II: Rate of Convergence . . . . . 183
11.1 Linear Least Squares Estimates . . . . . . . . . . . . . . . . . . . . . . 183
11.2 Piecewise Polynomial Partitioning Estimates . . . . . . . . . . . 194
11.3 Nonlinear Least Squares Estimates . . . . . . . . . . . . . . . . . . . 197
11.4 Preliminaries to the Proof of Theorem 11.4 . . . . . . . . . . . . 203
11.5 Proof of Theorem 11.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
11.6 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
Problems and Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
12 Least Squares Estimates III: Complexity Regularization 222
12.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
12.2 Definition of the Estimate . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
12.3 Asymptotic Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
12.4 Piecewise Polynomial Partitioning Estimates . . . . . . . . . . . 232
12.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
Problems and Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
13 Consistency of Data-Dependent Partitioning Estimates 235
13.1 A General Consistency Theorem. . . . . . . . . . . . . . . . . . . . . . 235
13.2 Cubic Partitions with Data-Dependent Grid Size . . . . . . . 241
13.3 Statistically Equivalent Blocks . . . . . . . . . . . . . . . . . . . . . . . 243
13.4 Nearest Neighbor Clustering . . . . . . . . . . . . . . . . . . . . . . . . . 245
13.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
Problems and Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
14 Univariate Least Squares Spline Estimates . . . . . . . . . . . . 252
14.1 Introduction to Univariate Splines . . . . . . . . . . . . . . . . . . . . 252
14.2 Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
14.3 Spline Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
14.4 Rate of Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
14.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
Problems and Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281