An Iterative, Sketching-based Framework for Ridge Regression

Agniva Chowdhury, Jiasen Yang, Petros Drineas
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:989-998, 2018.

Abstract

Ridge regression is a variant of regularized least squares regression that is particularly suitable in settings where the number of predictor variables greatly exceeds the number of observations. We present a simple, iterative, sketching-based algorithm for ridge regression that guarantees high-quality approximations to the optimal solution vector. Our analysis builds upon two simple structural results that boil down to randomized matrix multiplication, a fundamental and well-understood primitive of randomized linear algebra. An important contribution of our work is the analysis of the behavior of subsampled ridge regression problems when the ridge leverage scores are used: we prove that accurate approximations can be achieved by a sample whose size depends on the degrees of freedom of the ridge-regression problem rather than the dimensions of the design matrix. Our experimental evaluations verify our theoretical results on both real and synthetic data.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-chowdhury18a, title = {An Iterative, Sketching-based Framework for Ridge Regression}, author = {Chowdhury, Agniva and Yang, Jiasen and Drineas, Petros}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {989--998}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/chowdhury18a/chowdhury18a.pdf}, url = {https://proceedings.mlr.press/v80/chowdhury18a.html}, abstract = {Ridge regression is a variant of regularized least squares regression that is particularly suitable in settings where the number of predictor variables greatly exceeds the number of observations. We present a simple, iterative, sketching-based algorithm for ridge regression that guarantees high-quality approximations to the optimal solution vector. Our analysis builds upon two simple structural results that boil down to randomized matrix multiplication, a fundamental and well-understood primitive of randomized linear algebra. An important contribution of our work is the analysis of the behavior of subsampled ridge regression problems when the ridge leverage scores are used: we prove that accurate approximations can be achieved by a sample whose size depends on the degrees of freedom of the ridge-regression problem rather than the dimensions of the design matrix. Our experimental evaluations verify our theoretical results on both real and synthetic data.} }
Endnote
%0 Conference Paper %T An Iterative, Sketching-based Framework for Ridge Regression %A Agniva Chowdhury %A Jiasen Yang %A Petros Drineas %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-chowdhury18a %I PMLR %P 989--998 %U https://proceedings.mlr.press/v80/chowdhury18a.html %V 80 %X Ridge regression is a variant of regularized least squares regression that is particularly suitable in settings where the number of predictor variables greatly exceeds the number of observations. We present a simple, iterative, sketching-based algorithm for ridge regression that guarantees high-quality approximations to the optimal solution vector. Our analysis builds upon two simple structural results that boil down to randomized matrix multiplication, a fundamental and well-understood primitive of randomized linear algebra. An important contribution of our work is the analysis of the behavior of subsampled ridge regression problems when the ridge leverage scores are used: we prove that accurate approximations can be achieved by a sample whose size depends on the degrees of freedom of the ridge-regression problem rather than the dimensions of the design matrix. Our experimental evaluations verify our theoretical results on both real and synthetic data.
APA
Chowdhury, A., Yang, J. & Drineas, P.. (2018). An Iterative, Sketching-based Framework for Ridge Regression. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:989-998 Available from https://proceedings.mlr.press/v80/chowdhury18a.html.

Related Material