  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.
