Fast Algorithms for the Quantile Regression Process

Victor Chernozhukov, Iván Fernández‐Val, Blaise Melly

Abstract

Quantile regression (QR) is a fundamental tool for analyzing heterogeneous effects across a distribution. However, estimating the entire quantile process or performing bootstrap inference on large datasets is often computationally prohibitive. This paper introduces two novel algorithms: a recursive preprocessing approach that is numerically exact and a one-step estimator that is asymptotically equivalent to the full QR estimator. These methods achieve speedups of up to 100x, enabling complex distributional analysis on millions of observations in minutes rather than months.

Introduction

While standard Ordinary Least Squares (OLS) regression focuses on the conditional mean, Quantile Regression (QR) allows researchers to examine effects at any point in the distribution, such as the 10th or 90th percentiles. This is essential for studying phenomena like income inequality, financial risk, or birth weight outcomes. However, QR lacks a closed-form solution and requires solving linear programming problems. For large datasets or many quantiles, the computational burden becomes a significant barrier to empirical research.

Algorithmic Innovations

The authors propose two primary strategies to accelerate the estimation of the quantile process:

1. Recursive Preprocessing

Building on the concept of preprocessing, this algorithm uses the estimate from a previously calculated quantile (e.g., $\tau = 0.50$) to inform the estimation of an adjacent quantile (e.g., $\tau = 0.51$). By identifying observations that are highly likely to remain on one side of the regression line, the algorithm reduces the "effective" sample size that the computer must process. This method is numerically exact, yielding the same results as traditional interior-point or simplex methods but at a fraction of the time.

2. The One-Step Estimator

For even greater speed, the authors propose a one-step estimator based on a single Newton-Raphson iteration. Starting from a known quantile estimate, a first-order Taylor approximation is used to "jump" to a nearby quantile. While this is an approximation, it is asymptotically equivalent to the full QR estimator, meaning its accuracy improves as the sample size increases. It is designed for extremely large datasets where exact computation is unnecessary.

3. Accelerated Bootstrapping

The preprocessing logic is extended to the bootstrap. By using the full-sample estimate as a starting point for each bootstrap replicate, the authors demonstrate that bootstrapping a QR estimator can actually become faster than bootstrapping a standard OLS estimator, which is a significant reversal of traditional computational expectations.

Empirical Evaluation

The algorithms were tested using simulated wage data calibrated to the 2013 Current Population Survey and a massive real-world dataset of 2.2 million birth records from the 2017 Natality Data.

  • Massive Speedups: In simulations with 50,000 observations, the preprocessing algorithm was 30 times faster than standard Stata implementations, while the one-step estimator was nearly 130 times faster.
  • The "Two Months to 30 Minutes" Jump: On the 2.2 million observation Natality dataset, estimating 91 quantiles with 100 bootstrap replications took only 30 minutes on a standard 4-core laptop. The authors estimate that using standard built-in commands in existing software would have taken over two months of continuous computation.
  • Minimal Accuracy Loss: The one-step estimator performed almost identically to the exact estimator in terms of Mean Squared Error (MSE) once the sample size reached 5,000 observations.

Conclusion

These algorithmic improvements significantly lower the barrier to entry for sophisticated distributional analysis. By transforming tasks that once required high-performance computing clusters into operations that can be performed on a standard laptop in a coffee shop, these methods democratize high-end econometrics and enable researchers to explore complex heterogeneous effects in massive datasets with unprecedented ease.

Summary updated

BibTeX
@inproceedings{chernozhukov2020fast,
  author = {Victor Chernozhukov and Iván Fernández‐Val and Blaise Melly},
  title = {{Fast Algorithms for the Quantile Regression Process}},
  booktitle = {Empirical},
  year = {2020},
  doi = {10.1007/s00181-020-01898-0},
}
Figure