Fast Relative-Error Approximation Algorithm for Ridge Regression

Shouyuan Chen CUHK, Yang Liu, Michael Lyu Chinese University of Hong Kong, Irwin King, Shengyu Zhang
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:367-376, 2015.

Abstract

Ridge regression is one of the most popular and effective regularized regression methods, and one case of particular interest is that the number of features $p$ is much larger than the number of samples $n$, i.e. $p \gg n$. In this case, the standard optimization algorithm for ridge regression computes the optimal solution $\mathbf{x}^*$ in $O(n^2 p+n^3)$ time. In this paper, we propose a fast relative-error approximation algorithm for ridge regression. More specifically, our algorithm outputs a solution $\tilde\x$ satisfying $\|\tilde\x -\mathbf{x}^*\|_2 \le \epsilon\|\mathbf{x}^*\|_2$ with high probability and runs in $\tilde O(\nnz(\mathbf{A})+n^3/\epsilon^2)$ time, where $\nnz(\mathbf{A})$ is the number of non-zero entries of matrix $\mathbf{A}$. To the best of our knowledge, this is the first algorithm for ridge regression that runs in $o(n^2 p)$ time with provable relative-error approximation bound on the output vector. In addition, for supplements to our main result, we analyze the risk inflation bound of our algorithm and apply our techniques to two generalizations of ridge regression, including multiple response ridge regression and a non-linear ridge regression problem. Finally, we show empirical results on both synthetic and real datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-cuhk15a, title = {Fast Relative-Error Approximation Algorithm for Ridge Regression}, author = {CUHK, Shouyuan Chen and Liu, Yang and Kong, Michael Lyu Chinese University of Hong and King, Irwin and Zhang, Shengyu}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {367--376}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/cuhk15a/cuhk15a.pdf}, url = {https://proceedings.mlr.press/r13/cuhk15a.html}, abstract = {Ridge regression is one of the most popular and effective regularized regression methods, and one case of particular interest is that the number of features $p$ is much larger than the number of samples $n$, i.e. $p \gg n$. In this case, the standard optimization algorithm for ridge regression computes the optimal solution $\mathbf{x}^*$ in $O(n^2 p+n^3)$ time. In this paper, we propose a fast relative-error approximation algorithm for ridge regression. More specifically, our algorithm outputs a solution $\tilde\x$ satisfying $\|\tilde\x -\mathbf{x}^*\|_2 \le \epsilon\|\mathbf{x}^*\|_2$ with high probability and runs in $\tilde O(\nnz(\mathbf{A})+n^3/\epsilon^2)$ time, where $\nnz(\mathbf{A})$ is the number of non-zero entries of matrix $\mathbf{A}$. To the best of our knowledge, this is the first algorithm for ridge regression that runs in $o(n^2 p)$ time with provable relative-error approximation bound on the output vector. In addition, for supplements to our main result, we analyze the risk inflation bound of our algorithm and apply our techniques to two generalizations of ridge regression, including multiple response ridge regression and a non-linear ridge regression problem. Finally, we show empirical results on both synthetic and real datasets.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Fast Relative-Error Approximation Algorithm for Ridge Regression %A Shouyuan Chen CUHK %A Yang Liu %A Michael Lyu Chinese University of Hong Kong %A Irwin King %A Shengyu Zhang %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-cuhk15a %I PMLR %P 367--376 %U https://proceedings.mlr.press/r13/cuhk15a.html %V R13 %X Ridge regression is one of the most popular and effective regularized regression methods, and one case of particular interest is that the number of features $p$ is much larger than the number of samples $n$, i.e. $p \gg n$. In this case, the standard optimization algorithm for ridge regression computes the optimal solution $\mathbf{x}^*$ in $O(n^2 p+n^3)$ time. In this paper, we propose a fast relative-error approximation algorithm for ridge regression. More specifically, our algorithm outputs a solution $\tilde\x$ satisfying $\|\tilde\x -\mathbf{x}^*\|_2 \le \epsilon\|\mathbf{x}^*\|_2$ with high probability and runs in $\tilde O(\nnz(\mathbf{A})+n^3/\epsilon^2)$ time, where $\nnz(\mathbf{A})$ is the number of non-zero entries of matrix $\mathbf{A}$. To the best of our knowledge, this is the first algorithm for ridge regression that runs in $o(n^2 p)$ time with provable relative-error approximation bound on the output vector. In addition, for supplements to our main result, we analyze the risk inflation bound of our algorithm and apply our techniques to two generalizations of ridge regression, including multiple response ridge regression and a non-linear ridge regression problem. Finally, we show empirical results on both synthetic and real datasets. %Z Reissued by PMLR on 04 October 2026.
APA
CUHK, S.C., Liu, Y., Kong, M.L.C.U.o.H., King, I. & Zhang, S.. (2015). Fast Relative-Error Approximation Algorithm for Ridge Regression. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:367-376 Available from https://proceedings.mlr.press/r13/cuhk15a.html. Reissued by PMLR on 04 October 2026.

Related Material