Abstract
Quantile regression is a method to estimate the quantiles of the conditional distribution of a response variable, and as such it permits a much more accurate portrayal of the rela- tionship between the response variable and observed covariates than methods such as Least-squares or Least Absolute Deviations regression. It can be expressed as a linear program, and interior-point methods can be used to find a solution for moderately large problems. Dealing with very large problems, e.g., involving data up to and beyond the ter- abyte regime, remains a challenge. Here, we present a randomized algorithm that runs in time that is nearly linear in the size of the in- put and that, with constant probability, com- putes a (1+ε) approximate solution to an ar- bitrary quantile regression problem. Our al- gorithm computes a low-distortion subspace- preserving embedding with respect to the loss function of quantile regression. Our empiri- cal evaluation illustrates that our algorithm is competitive with the best previous work on small to medium-sized problems, and that it can be implemented in MapReduce-like envi- ronments and applied to terabyte-sized prob- lems.
Author
Jiyan Yang, Xiangrui Meng, Michael W. Mahoney
Journal
Proceedings of the 30th International Conference on Machine Learning,
Paper Publication Date
2013
Paper Type
Astroinformatics