Random Design Analysis of Ridge Regression

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

Abstract

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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v23-hsu12, title = {Random Design Analysis of Ridge Regression}, author = {Daniel Hsu and Sham M. Kakade and Tong Zhang}, booktitle = {Proceedings of the 25th Annual Conference on Learning Theory}, pages = {9.1--9.24}, year = {2012}, editor = {Shie Mannor and Nathan Srebro and Robert C. Williamson}, volume = {23}, series = {Proceedings of Machine Learning Research}, address = {Edinburgh, Scotland}, month = {25--27 Jun}, publisher = {JMLR Workshop and Conference Proceedings}, pdf = {http://proceedings.mlr.press/v23/hsu12/hsu12.pdf}, url = {http://proceedings.mlr.press/v23/hsu12.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Random Design Analysis of Ridge Regression %A Daniel Hsu %A Sham M. Kakade %A Tong Zhang %B Proceedings of the 25th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2012 %E Shie Mannor %E Nathan Srebro %E Robert C. Williamson %F pmlr-v23-hsu12 %I PMLR %J Proceedings of Machine Learning Research %P 9.1--9.24 %U http://proceedings.mlr.press %V 23 %W PMLR %X 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.
RIS
TY - CPAPER TI - Random Design Analysis of Ridge Regression AU - Daniel Hsu AU - Sham M. Kakade AU - Tong Zhang BT - Proceedings of the 25th Annual Conference on Learning Theory PY - 2012/06/16 DA - 2012/06/16 ED - Shie Mannor ED - Nathan Srebro ED - Robert C. Williamson ID - pmlr-v23-hsu12 PB - PMLR SP - 9.1 DP - PMLR EP - 9.24 L1 - http://proceedings.mlr.press/v23/hsu12/hsu12.pdf UR - http://proceedings.mlr.press/v23/hsu12.html AB - 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. ER -
APA
Hsu, D., Kakade, S.M. & Zhang, T.. (2012). Random Design Analysis of Ridge Regression. Proceedings of the 25th Annual Conference on Learning Theory, in PMLR 23:9.1-9.24

Related Material