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 from a given dataset of n instances, where each instance is a set of values of the independent variables and the corresponding value of the dependent variable. One of the classical and widely used approaches is Ordinary Least Square Regression (OLS), where the objective is the minimize the average squared error between the predicted and actual value of the dependent variable. Another classical approach is Quantile Regression (QR), where the objective is to minimize the average weighted absolute error between the predicted and actual value of the dependent variable. QR (also known as "Median Regression" for the special case of the middle quantile), is less affected by outliers and thus statistically a more robust alternative to OLS [15, 18]. However, while there exist efficient algorithms for OLS, the state-of-art algorithms for QR require solving large linear programs with many variables and constraints. They can be solved using using interior point methods [24] which are weakly polynomial (i.e., in the arithmetic computation model the running time is polynomial in the number of bits required to represent the rational numbers in the input), or using Simplex-based exterior point methods which can have exponential time complexity in the worst case [10]. The main focus of our paper is an investigation of the computational complexity of Quantile Regression, and in particular, to design efficient strongly polynomial algorithms (i.e., in the arithmetic computation model the running time is polynomial in the number of rational numbers in the input) for various special cases of the problem.