A Distribution-Free Theory of Nonparametric Regression

by Gyorfi, Laszlo; Kohler, Michael; Krzyzk, Adam; Walk, Harro

• ISBN13: 9780387954417
• ISBN10: 0387954414
• Format: Hardcover
• Copyright: 2002-08-01
• Publisher: Springer Verlag

Summary

This book provides a systematic in-depth analysis of nonparametric regression with random design. It covers almost all known estimates such as classical local averaging estimates including kernel, partitioning and nearest neighbor estimates, least squares estimates using splines, neural networks and radial basis function networks, penalized least squares estimates, local polynomial kernel estimates, and orthogonal series estimates. The emphasis is on distribution-free properties of the estimates. Most consistency results are valid for all distributions of the data. Whenever it is not possible to derive distribution-free results, as in the case of the rates of convergence, the emphasis is on results which require as few constrains on distributions as possible, on distribution-free inequalities, and on adaptation.The relevant mathematical theory is systematically developed and requires only a basic knowledge of probability theory. The book will be a valuable reference for anyone interested in nonparametric regression and is a rich source of many useful mathematical techniques widely scattered in the literature. In particular, the book introduces the reader to empirical process theory, martingales and approximation properties of neural networks.

Table of Contents

Preface	vii
Why Is Nonparametric Regression Important?	1	(17)
Regression Analysis and L2 Risk	1	(1)
Regression Function Estimation and L2 Error	2	(2)
Practical Applications	4	(2)
Application to Pattern Recognition	6	(3)
Parametric versus Nonparametric Estimation	9	(3)
Consistency	12	(1)
Rate of Convergence	13	(1)
Adaptation	14	(1)
Fixed versus Random Design Regression	15	(1)
Bibliographic Notes	16	(2)
Problems and Exercises	16	(2)
How to Construct Nonparametric Regression Estimates?	18	(13)
Four Related Paradigms	18	(5)
Curse of Dimensionality	23	(1)
Bias-Variance Tradeoff	24	(2)
Choice of Smoothing Parameters and Adaptation	26	(2)
Bibliographic Notes	28	(3)
Problems and Exercises	29	(2)
Lower Bounds	31	(21)
Slow Rate	31	(5)
Minimax Lower Bounds	36	(7)
Individual Lower Bounds	43	(7)
Bibliographic Notes	50	(2)
Problems and Exercises	50	(2)
Partitioning Estimates	52	(18)
Introduction	52	(3)
Stone's Theorem	55	(5)
Consistency	60	(4)
Rate of Convergence	64	(3)
Bibliographic Notes	67	(3)
Problems and Exercises	68	(2)
Kernel Estimates	70	(16)
Introduction	70	(1)
Consistency	71	(6)
Rate of Convergence	77	(3)
Local Polynomial Kernel Estimates	80	(2)
Bibliographic Notes	82	(4)
Problems and Exercises	82	(4)
k-NN Estimates	86	(14)
Introduction	86	(2)
Consistency	88	(5)
Rate of Convergence	93	(3)
Bibliographic Notes	96	(4)
Problems and Exercises	97	(3)
Splitting the Sample	100	(12)
Best Random Choice of a Parameter	100	(5)
Partitioning, Kernel, and Nearest Neighbor Estimates	105	(3)
Bibliographic Notes	108	(4)
Problems and Exercises	109	(3)
Cross-Validation	112	(18)
Best Deterministic Choice of the Parameter	112	(1)
Partitioning and Kernel Estimates	113	(2)
Proof of Theorem 8.1	115	(11)
Nearest Neighbor Estimates	126	(1)
Bibliographic Notes	127	(3)
Problems and Exercises	127	(3)
Uniform Laws of Large Numbers	130	(28)
Basic Exponential Inequalities	131	(3)
Extension to Random L1 Norm Covers	134	(6)
Covering and Packing Numbers	140	(3)
Shatter Coefficients and VC Dimension	143	(10)
A Uniform Law of Large Numbers	153	(3)
Bibliographic Notes	156	(2)
Problems and Exercises	156	(2)
Least Squares Estimates I: Consistency	158	(25)
Why and How Least Squares?	158	(7)
Consistency from Bounded to Unbounded Y	165	(5)
Linear Least Squares Series Estimates	170	(4)
Piecewise Polynomial Partitioning Estimates	174	(6)
Bibliographic Notes	180	(3)
Problems and Exercises	180	(3)
Least Squares Estimates II: Rate of Convergence	183	(39)
Linear Least Squares Estimates	183	(11)
Piecewise Polynomial Partitioning Estimates	194	(3)
Nonlinear Least Squares Estimates	197	(6)
Preliminaries to the Proof of Theorem 11.4	203	(7)
Proof of Theorem 11.4	210	(9)
Bibliographic Notes	219	(3)
Problems and Exercises	220	(2)
Least Squares Estimates III: Complexity Regularization	222	(13)
Motivation	222	(3)
Definition of the Estimate	225	(2)
Asymptotic Results	227	(5)
Piecewise Polynomial Partitioning Estimates	232	(1)
Bibliographic Notes	233	(2)
Problems and Exercises	234	(1)
Consistency of Data-Dependent Partitioning Estimates	235	(17)
A General Consistency Theorem	235	(6)
Cubic Partitions with Data-Dependent Grid Size	241	(2)
Statistically Equivalent Blocks	243	(2)
Nearest Neighbor Clustering	245	(5)
Bibliographic Notes	250	(2)
Problems and Exercises	251	(1)
Univariate Least Squares Spline Estimates	252	(31)
Introduction to Univariate Splines	252	(15)
Consistency	267	(6)
Spline Approximation	273	(4)
Rate of Convergence	277	(4)
Bibliographic Notes	281	(2)
Problems and Exercises	281	(2)
Multivariate Least Squares Spline Estimates	283	(14)
Introduction to Tensor Product Splines	283	(7)
Consistency	290	(4)
Rate of Convergence	294	(2)
Bibliographic Notes	296	(1)
Problems and Exercises	296	(1)
Neural Networks Estimates	297	(32)
Neural Networks	297	(3)
Consistency	300	(15)
Rate of Convergence	315	(11)
Bibliographic Notes	326	(3)
Problems and Exercises	328	(1)
Radial Basis Function Networks	329	(24)
Radial Basis Function Networks	329	(3)
Consistency	332	(8)
Rate of Convergence	340	(8)
Increasing Kernels and Approximation	348	(2)
Bibliographic Notes	350	(3)
Problems and Exercises	350	(3)
Orthogonal Series Estimates	353	(27)
Wavelet Estimates	353	(3)
Empirical Orthogonal Series Estimates	356	(2)
Connection with Least Squares Estimates	358	(3)
Empirical Orthogonalization of Piecewise Polynomials	361	(5)
Consistency	366	(6)
Rate of Convergence	372	(6)
Bibliographic Notes	378	(2)
Problems and Exercises	378	(2)
Advanced Techniques from Empirical Process Theory	380	(27)
Chaining	380	(5)
Extension of Theorem 11.6	385	(5)
Extension of Theorem 11.4	390	(7)
Piecewise Polynomial Partitioning Estimates	397	(7)
Bibliographic Notes	404	(3)
Problems and Exercises	405	(2)
Penalized Least Squares Estimates I: Consistency	407	(26)
Univariate Penalized Least Squares Estimates	408	(6)
Proof of Lemma 20.1	414	(4)
Consistency	418	(7)
Multivariate Penalized Least Squares Estimates	425	(2)
Consistency	427	(2)
Bibliographic Notes	429	(4)
Problems and Exercises	129	(304)
Penalized Least Squares Estimates II: Rate of Convergence	433	(15)
Rate of Convergence	433	(7)
Application of Complexity Regularization	440	(6)
Bibliographic notes	446	(2)
Problems and Exercises	447	(1)
Dimension Reduction Techniques	448	(11)
Additive Models	449	(2)
Projection Pursuit	451	(5)
Single Index Models	456	(1)
Bibliographic Notes	457	(2)
Problems and Exercises	457	(2)
Strong Consistency of Local Averaging Estimates	459	(34)
Partitioning Estimates	459	(20)
Kernel Estimates	479	(7)
k-NN Estimates	486	(5)
Bibliographic Notes	491	(2)
Problems and Exercises	491	(2)
Semirecursive Estimates	493	(19)
A General Result	493	(3)
Semirecursive Kernel Estimate	496	(11)
Semirecursive Partitioning Estimate	507	(3)
Bibliographic Notes	510	(2)
Problems and Exercises	511	(1)
Recursive Estimates	512	(28)
A General Result	512	(5)
Recursive Kernel Estimate	517	(1)
Recursive Partitioning Estimate	518	(1)
Recursive NN Estimate	518	(2)
Recursive Series Estimate	520	(6)
Pointwise Universal Consistency	526	(11)
Bibliographic Notes	537	(3)
Problems and Exercises	537	(3)
Censored Observations	540	(24)
Right Censoring Regression Models	540	(1)
Survival Analysis, the Kaplan-Meier Estimate	541	(7)
Regression Estimation for Model A	548	(7)
Regression Estimation for Model B	555	(8)
Bibliographic Notes	563	(1)
Problems and Exercises	563	(1)
Dependent Observations	564	(25)
Stationary and Ergodic Observations	565	(3)
Dynamic Forecasting: Autoregression	568	(4)
Static Forecasting: General Case	572	(4)
Time Series Problem: Cesaro Consistency	576	(1)
Time Series Problem: Universal Prediction	576	(6)
Estimating Smooth Regression Functions	582	(5)
Bibliographic Notes	587	(2)
Problems and Exercises	589	(1)
Appendix A: Tools	589	(20)
A.1 A Denseness Result	589	(3)
A.2 Inequalities for Independent Random Variables	592	(6)
A.3 Inequalities for Martingales	598	(3)
A.4 Martingale Convergences	601	(8)
Problems and Exercises	607	(2)
Notation	609	(3)
Bibliography	612	(27)
Author Index	639	(5)
Subject Index	644