Random Design Analysis of Ridge Regression


Daniel Hsu, Sham M. Kakade, Tong Zhang ;
Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:9.1-9.24, 2012.


This work gives a simultaneous analysis of both the ordinary least squares estimator and the ridge regression estimator in the random design setting under mild assumptions on the covariate/response distributions. In particular, the analysis provides sharp results on the “out-of-sample” prediction error, as opposed to the “in-sample” (fixed design) error. The analysis also reveals the effect of errors in the estimated covariance structure, as well as the effect of modeling errors; neither of which effects are present in the fixed design setting. The proof of the main results are based on a simple decomposition lemma combined with concentration inequalities for random vectors and matrices.

Related Material