Nearly Linear Row Sampling Algorithm for Quantile Regression
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.
Code (0)
등록된 구현이 없습니다.
Tasks
quantile regressionregressionSimilar Papers 제목 키워드 기반
Quantile Regression for Large-scale Applications
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 relationship between the response variable an…
quantile regressionregressionbqror: An R package for Bayesian Quantile Regression in Ordinal Models
This article describes an R package bqror that estimates Bayesian quantile regression for ordinal models introduced in Rahman (2016). The paper classifies ordinal models into two types and offers computationally efficien…
quantile regressionregressionProbabilistic water demand forecasting using quantile regression algorithms
Machine and statistical learning algorithms can be reliably automated and applied at scale. Therefore, they can constitute a considerable asset for designing practical forecasting systems, such as those related to urban …
Demand Forecastingquantile regressionregressionTime Series+1On Quantile Regression Forests for Modelling Mixed-Frequency and Longitudinal Data
The aim of this thesis is to extend the applications of the Quantile Regression Forest (QRF) algorithm to handle mixed-frequency and longitudinal data. To this end, standard statistical approaches have been exploited to …
quantile regressionregressionA Pathwise Coordinate Descent Algorithm for LASSO Penalized Quantile Regression
$\ell_1$ penalized quantile regression is used in many fields as an alternative to penalized least squares regressions for high-dimensional data analysis. Existing algorithms for penalized quantile regression either use …
quantile regressionregression