Nearly Linear Row Sampling Algorithm for Quantile Regression

Yi Li, Ruosong Wang, Lin Yang, Hanrui Zhang
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:5979-5989, 2020.

Abstract

We give a row sampling algorithm for the quantile loss function with sample complexity nearly linear in the dimensionality of the data, improving upon the previous best algorithm whose sampling complexity has at least cubic dependence on the dimensionality. Based upon our row sampling algorithm, we give the fastest known algorithm for quantile regression and a graph sparsification algorithm for balanced directed graphs. Our main technical contribution is to show that Lewis weights sampling, which has been used in row sampling algorithms for $\ell_p$ norms, can also be applied in row sampling algorithms for a variety of loss functions. We complement our theoretical results by experiments to demonstrate the practicality of our approach.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-li20o, title = {Nearly Linear Row Sampling Algorithm for Quantile Regression}, author = {Li, Yi and Wang, Ruosong and Yang, Lin and Zhang, Hanrui}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {5979--5989}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/li20o/li20o.pdf}, url = {https://proceedings.mlr.press/v119/li20o.html}, abstract = {We give a row sampling algorithm for the quantile loss function with sample complexity nearly linear in the dimensionality of the data, improving upon the previous best algorithm whose sampling complexity has at least cubic dependence on the dimensionality. Based upon our row sampling algorithm, we give the fastest known algorithm for quantile regression and a graph sparsification algorithm for balanced directed graphs. Our main technical contribution is to show that Lewis weights sampling, which has been used in row sampling algorithms for $\ell_p$ norms, can also be applied in row sampling algorithms for a variety of loss functions. We complement our theoretical results by experiments to demonstrate the practicality of our approach.} }
Endnote
%0 Conference Paper %T Nearly Linear Row Sampling Algorithm for Quantile Regression %A Yi Li %A Ruosong Wang %A Lin Yang %A Hanrui Zhang %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-li20o %I PMLR %P 5979--5989 %U https://proceedings.mlr.press/v119/li20o.html %V 119 %X We give a row sampling algorithm for the quantile loss function with sample complexity nearly linear in the dimensionality of the data, improving upon the previous best algorithm whose sampling complexity has at least cubic dependence on the dimensionality. Based upon our row sampling algorithm, we give the fastest known algorithm for quantile regression and a graph sparsification algorithm for balanced directed graphs. Our main technical contribution is to show that Lewis weights sampling, which has been used in row sampling algorithms for $\ell_p$ norms, can also be applied in row sampling algorithms for a variety of loss functions. We complement our theoretical results by experiments to demonstrate the practicality of our approach.
APA
Li, Y., Wang, R., Yang, L. & Zhang, H.. (2020). Nearly Linear Row Sampling Algorithm for Quantile Regression. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:5979-5989 Available from https://proceedings.mlr.press/v119/li20o.html.

Related Material