Efficient Strongly Polynomial Algorithms for Quantile Regression
Linear Regression is a seminal technique in statistics and machine learning, where the objective is to build linear predictive models between a response (i.e., dependent) variable and one or more predictor (i.e., independent) variables. In this paper, we revisit the classical technique of Quantile Regression (QR), which is statistically a more robust alternative to the other classical technique of Ordinary Least Square Regression (OLS). However, while there exist efficient algorithms for OLS, almost all of the known results for QR are only weakly polynomial. Towards filling this gap, this paper proposes several efficient strongly polynomial algorithms for QR for various settings. For two dimensional QR, making a connection to the geometric concept of $k$-set, we propose an algorithm with a deterministic worst-case time complexity of $\mathcal{O}(n^{4/3} polylog(n))$ and an expected time complexity of $\mathcal{O}(n^{4/3})$ for the randomized version. We also propose a randomized divide-and-conquer algorithm -- RandomizedQR with an expected time complexity of $\mathcal{O}(n\log^2{(n)})$ for two dimensional QR problem. For the general case with more than two dimensions, our RandomizedQR algorithm has an expected time complexity of $\mathcal{O}(n^{d-1}\log^2{(n)})$.
Code (0)
등록된 구현이 없습니다.
Tasks
quantile regressionregressionSimilar Papers 제목 키워드 기반
Self-Normalized Inference in (Quantile, Expected Shortfall) Regressions for Time Series
This paper proposes valid inference tools, based on self-normalization, in time series expected shortfall regressions and, as a corollary, also in quantile regressions. Extant methods for such time series regressions, ba…
quantile regressionregressionTime SeriesvalidNonparametric Quantile Regression: Non-Crossing Constraints and Conformal Prediction
We propose a nonparametric quantile regression method using deep neural networks with a rectified linear unit penalty function to avoid quantile crossing. This penalty function is computationally feasible for enforcing n…
Conformal PredictionPredictionPrediction Intervalsquantile regression+1ChePAN: Constrained Black-Box Uncertainty Modelling with Quantile Regression
Most of the predictive systems currently in use do not report any useful information for auditing their associated uncertainty and evaluating the corresponding risk. Taking for granted that their replacement may not be a…
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+1Fast Algorithms for Quantile Regression with Selection
This paper addresses computational challenges in estimating Quantile Regression with Selection (QRS). The estimation of the parameters that model self-selection requires the estimation of the entire quantile process seve…
Computational Efficiencyquantile regressionregression