Fast Inference for Quantile Regression with Tens of Millions of Observations

Sokbae Lee, Yuan Liao, Myung Hwan Seo, Youngki ShinJournal of Econometrics 2022 · arXiv

Abstract

Big data analytics has opened new avenues in economic research, but the challenge of analyzing datasets with tens of millions of observations is substantial. Conventional econometric methods based on extreme estimators require large amounts of computing resources and memory, which are often not readily available. In this paper, we focus on linear quantile regression applied to "ultra-large" datasets, such as U.S. decennial censuses. A fast inference framework is presented, utilizing stochastic subgradient descent (S-subGD) updates. The inference procedure handles cross-sectional data sequentially: (i) updating the parameter estimate with each incoming "new observation", (ii) aggregating it as a Polyak-Ruppert average, and (iii) computing a pivotal statistic for inference using only a solution path. The methodology draws from time-series regression to create an asymptotically pivotal statistic through random scaling. Our proposed test statistic is calculated in a fully online fashion and critical values are calculated without resampling. We conduct extensive numerical studies to showcase the computational merits of our proposed inference. For inference problems as large as $(n, d) \sim (10^7, 10^3)$, where $n$ is the sample size and $d$ is the number of regressors, our method generates new insights, surpassing current inference methods in computation. Our method specifically reveals trends in the gender gap in the U.S. college wage premium using millions of observations, while controlling over $10^3$ covariates to mitigate confounding effects.

Introduction

Quantile regression (QR) is a cornerstone of modern econometrics, offering a more granular view of data than standard ordinary least squares (OLS). By modeling the conditional quantiles of a response variable, QR allows researchers to examine how covariates affect different segments of a distribution—such as the 10th percentile of earners versus the 90th. However, as datasets scale to the "ultra-large" regime (tens of millions of observations), traditional QR methods encounter a "memory wall."

The computational difficulty stems from the QR loss function (the "check function"), which is non-differentiable. Unlike OLS, which has a closed-form solution, QR requires iterative optimization. Furthermore, conducting statistical inference—calculating confidence intervals and p-values—traditionally requires estimating the conditional density of the error term or employing computationally expensive bootstrapping. On datasets with $10^7$ observations and $10^3$ variables, these traditional approaches become practically impossible.

The S-subGD Inference Framework

To address these scalability challenges, this paper introduces a high-speed inference framework that operates in a fully online fashion. The methodology integrates three key components:

1. Stochastic Subgradient Descent (S-subGD)

Instead of processing the entire dataset simultaneously, the algorithm updates parameter estimates sequentially. As each new observation arrives, the model performs a small update. This sequential processing ensures a minimal memory footprint, as the system never needs to store the full dataset in active memory.

2. Polyak-Ruppert Averaging

To achieve the statistical efficiency of traditional estimators, the framework employs Polyak-Ruppert averaging. By taking the average of the intermediate estimates produced along the "solution path" of the S-subGD process, the estimator achieves an optimal rate of convergence, matching the performance of more computationally intensive batch methods.

3. Random Scaling for Online Inference

The core innovation of this work is the use of "random scaling" for inference. Borrowing techniques from time-series analysis, the authors utilize the fluctuations of the solution path itself to construct an asymptotically pivotal statistic.

In traditional QR, inference requires estimating a "nuisance parameter" (the error density), which often involves sensitive tuning parameters like bandwidths. The random scaling approach bypasses this entirely. By analyzing the partial sums of the estimates, the method generates a test statistic that follows a known distribution related to Brownian motion. This allows for the calculation of confidence intervals without ever needing to run a bootstrap or estimate a Hessian matrix.

Empirical Performance and Scalability

The framework was evaluated using both synthetic Monte Carlo simulations and real-world data from the IPUMS USA (U.S. Census and American Community Survey).

Computational Benchmarks

In simulations with $n=10^6$ observations and $d=320$ regressors, the S-subGD method demonstrated a massive speed advantage:

  • S-subGD: 16 seconds
  • CONQUER (State-of-the-art): 22 minutes
  • Traditional Bootstrap: Over 1 hour

When scaled to $n=10^7$, most existing methods failed due to memory constraints, while the proposed framework maintained stable coverage rates and narrow confidence intervals.

The U.S. College Wage Premium

Applying the method to U.S. wage structures from 1980–2015, the authors controlled for over 1,000 covariates, including complex interactions between age, gender, and geography. The analysis revealed that the female college wage premium is significantly higher than the male premium at the median. This nuanced insight highlights the importance of large-scale controls—which only this high-speed method could efficiently process—to mitigate confounding effects in economic data.

Conclusion and Future Directions

This framework provides a scalable solution for quantile regression on a scale previously considered unreachable for standard research hardware. By treating the optimizer's path as the engine for inference, it eliminates the need for resampling and density estimation.

While the current theoretical proofs assume independent and identically distributed (i.i.d.) data and a fixed number of dimensions ($d$), future work may extend these proofs to time-series data and high-dimensional settings where $d$ grows with $n$. Additionally, the authors suggest that the "selection path" generated by this method could eventually be adapted for real-time, online variable selection.

Summary updated

Abstract

Big data analytics has opened new avenues in economic research, but the challenge of analyzing datasets with tens of millions of observations is substantial. Conventional econometric methods based on extreme estimators require large amounts of computing resources and memory, which are often not readily available. In this paper, we focus on linear quantile regression applied to "ultra-large" datasets, such as U.S. decennial censuses. A fast inference framework is presented, utilizing stochastic subgradient descent (S-subGD) updates. The inference procedure handles cross-sectional data sequentially: (i) updating the parameter estimate with each incoming "new observation", (ii) aggregating it as a $\textit{Polyak-Ruppert}$ average, and (iii) computing a pivotal statistic for inference using only a solution path. The methodology draws from time-series regression to create an asymptotically pivotal statistic through random scaling. Our proposed test statistic is calculated in a fully online fashion and critical values are calculated without resampling. We conduct extensive numerical studies to showcase the computational merits of our proposed inference. For inference problems as large as $(n, d) \sim (10^7, 10^3)$, where $n$ is the sample size and $d$ is the number of regressors, our method generates new insights, surpassing current inference methods in computation. Our method specifically reveals trends in the gender gap in the U.S. college wage premium using millions of observations, while controlling over $10^3$ covariates to mitigate confounding effects.
BibTeX
@article{lee2022fast,
  author = {Sokbae Lee and Yuan Liao and Myung Hwan Seo and Youngki Shin},
  title = {{Fast Inference for Quantile Regression with Tens of Millions of Observations}},
  journal = {Journal of Econometrics},
  year = {2022},
}
Figure