Finite-Sample Distribution Theory and Efficient Large-Scale Inference for Online Quantile Regression

Ziyang Wei; Jiaqi Li; Lan Wang; Wei Biao Wu

stat.MLOct 5, 2026

Finite-Sample Distribution Theory and Efficient Large-Scale Inference for Online Quantile Regression

Authors: Ziyang Wei, Jiaqi Li, Lan Wang, Wei Biao Wu

Organizations: Department of Statistics, University of Chicago · Department of Statistics, Rice University · Department of Management Science, University of Miami

Abstract

This paper studies online quantile regression for large-scale and streaming data using Stochastic SubGradient Descent (SSGD) with constant learning rates. Classical offline inference for quantile regression is computationally and memory intensive. Existing works of online inference for quantile regression provide only asymptotic guarantees and typically require sub-exponential tail conditions for distribution theory. To bridge these gaps, we introduce new techniques to prove a quenched central limit theorem (CLT) and finite-sample Gaussian approximation for SSGD under a finite-moment assumption. We further show that Ruppert-Polyak averaging with a constant learning rate has a non-vanishing bias and fails to satisfy CLT centering at the population target. Hence we propose suffix averaging to address this issue and establish its finite-sample Gaussian approximation. Based on these results, we provide an efficient online inference method for quantile regression that avoids covariance estimation. Numerical experiments show that our method achieves desirable empirical coverage rates and competitive performance compared to other inference methods. We also apply our approach to U.S. wage data to demonstrate its practical effectiveness.

Figures & tables

Figure 1 : Convergence, inference speed, and bias of RP averaging. (a) compares convergence under constant and decaying learning rates with dimension

d=100

. (b) shows the computational time of three inference methods with dimension

d=100

. Parallel SSGD is the one proposed in this paper, which achieves a speedup of more than

100\times

over the two competing methods. (c) shows that the

\sqrt{n}

-scaled bias of full RP averaging remains non-negligible across different constant learning rates, whereas suffix averaging substantially reduces this scaled bias. The

1/2

-suffix estimator averages the second half of the iterates, while the

4/5

-power-suffix estimator approximately averages the final

n-n^{4/5}

iterates.

Figure 3 : Estimation and inference wall-clock time vs. sample size and dimension. The time for the first two panels is plotted on a logarithmic scale on the y-axis. The SSGD algorithm and parallel inference method are orders of magnitude faster.

Panel of Figure 4 — Figure 4 : Parallel inference and random scaling – empirical coverage and length of confidence intervals. The first two rows: $(n,d,1-\alpha)\in\{(10^{7},1500,95\%),(3\times 10^{6},500,95\%)\}$ and 1000 replications. The last two rows: $(n,d,1-\alpha)\in\{(10^{7},1500,99\%),(3\times 10^{6},500,99\%)\}$ and 10000 replications. The shadows represent the error bars with one standard deviation.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

\displaystyle\bar{\bm{\beta}}_{i,K}\leftarrow\frac{1}{K}\sum_{k=1}^{K}\bm{\beta}^{\mathrm{SF}}_{i,(k)},\quad\hat{\sigma}^{2}_{\bm{v}}\leftarrow\frac{1}{K-1}\sum_{k=1}^{K}\left(\bm{v}^{\top}\bm{\beta}^{\mathrm{SF}}_{i,(k)}-\bm{v}^{\top}\bar{\bm{\beta}}_{i,K}\right)^{2}.

Appendix

Algorithm 1 Efficient Online Inference for Large-Scale Quantile Regression

$\alpha=0.05,\,d=500$		Coverage (Relative error)	Length (std)
$k=7.5\times 10^{5}$	Parallel Inference	0.9490 (0.020)	0.011 (0.00333)
$k=7.5\times 10^{5}$	Random Scaling	0.9850 (0.700)	0.023 (0.01515)
$k=1.5\times 10^{6}$	Parallel Inference	0.9470 (0.060)	0.006 (0.00208)
$k=1.5\times 10^{6}$	Random Scaling	0.9840 (0.680)	0.012 (0.00766)
$k=3\times 10^{6}$	Parallel Inference	0.9470 (0.060)	0.004 (0.00137)
$k=3\times 10^{6}$	Random Scaling	0.9740 (0.480)	0.007 (0.00388)

Appendix

Table 1 : Comparison of Parallel Inference and Random Scaling for

\alpha=0.05

d=500

, and

n=3\times 10^{6}

. The value of

k

represents the

k

-th iteration or

k

-th sample. Coverage relative error is defined by

\mathcal{D}_{\alpha}

in ( 106 ). CI lengths are reported as mean with standard deviation in parentheses.

$\alpha=0.01,\,d=500$		Coverage (Relative error)	Length (std)
$k=7.5\times 10^{5}$	Parallel Inference	0.9894 (0.060)	0.017 (0.00535)
$k=7.5\times 10^{5}$	Random Scaling	0.9975 (0.750)	0.036 (0.02287)
$k=1.5\times 10^{6}$	Parallel Inference	0.9885 (0.150)	0.010 (0.00333)
$k=1.5\times 10^{6}$	Random Scaling	0.9968 (0.680)	0.019 (0.01145)
$k=3\times 10^{6}$	Parallel Inference	0.9904 (0.040)	0.007 (0.00222)
$k=3\times 10^{6}$	Random Scaling	0.9955 (0.550)	0.010 (0.00574)

Appendix

Table 2 : Comparison of Parallel Inference and Random Scaling for

\alpha=0.01

d=500

, and

n=3\times 10^{6}

. The value of

k

represents the

k

-th iteration or

k

-th sample. Coverage relative error is defined by

\mathcal{D}_{\alpha}

in ( 106 ). CI lengths are reported as mean with standard deviation in parentheses.

$\alpha=0.05,\,d=1500$		Coverage (Relative error)	Length (std)
$k=2.5\times 10^{6}$	Parallel Inference	0.9420 (0.160)	0.006 (0.00209)
$k=2.5\times 10^{6}$	Random Scaling	0.9890 (0.780)	0.021 (0.01486)
$k=5\times 10^{6}$	Parallel Inference	0.9350 (0.300)	0.004 (0.00126)
$k=5\times 10^{6}$	Random Scaling	0.9880 (0.760)	0.011 (0.00736)
$k=10^{7}$	Parallel Inference	0.9510 (0.020)	0.003 (0.00086)
$k=10^{7}$	Random Scaling	0.9850 (0.700)	0.006 (0.00369)

Appendix

Table 3 : Comparison of Parallel Inference and Random Scaling for

\alpha=0.05

d=1500

, and

n=10^{7}

. The value of

k

represents the

k

-th iteration or

k

-th sample. Coverage relative error is defined by

\mathcal{D}_{\alpha}

in ( 106 ). CI lengths are reported as mean with standard deviation in parentheses.

$\alpha=0.01,\,d=1500$		Coverage (Relative error)	Length (std)
$k=2.5\times 10^{6}$	Parallel Inference	0.9884 (0.160)	0.010 (0.00319)
$k=2.5\times 10^{6}$	Random Scaling	0.9988 (0.880)	0.033 (0.02242)
$k=5\times 10^{6}$	Parallel Inference	0.9886 (0.140)	0.006 (0.00196)
$k=5\times 10^{6}$	Random Scaling	0.9991 (0.910)	0.017 (0.01118)
$k=10^{7}$	Parallel Inference	0.9902 (0.020)	0.004 (0.00131)
$k=10^{7}$	Random Scaling	0.9971 (0.710)	0.009 (0.00554)

Appendix

Table 4 : Comparison of Parallel Inference and Random Scaling for

\alpha=0.01

d=1500

, and

n=10^{7}

. The value of

k

represents the

k

-th iteration or

k

-th sample. Coverage relative error is defined by

\mathcal{D}_{\alpha}

in ( 106 ). CI lengths are reported as mean with standard deviation in parentheses.

Method	$\bm{n=10^{4}}$	$\bm{n=3\times 10^{4}}$	$\bm{n=10^{5}}$	$\bm{n=5\times 10^{5}}$
Parallel Inference	0.0009	0.0022	0.0071	0.0339
Conquer Bootstrap	0.0474	0.1116	0.3303	1.4667
Standard Quantile Regression	0.3874	0.7623	1.5802	4.6028

Appendix

Table 5 : Average inference time in seconds for different sample sizes (

d=20

Figure 7 : Lack-of-fit diagnosis QQ plot.

Explore similar work

Online simultaneous inference for quantiles via smoothed stochastic gradient descent
May 19, 2025Likai Chen, Georg Keilbar, Wei Biao WuQuantile Regression Exponential Family
Department of Mathematics and Statistics · Washington University in St.Louis · St.Louis, MO, USA +6
Statistical Inference for Stochastic Gradient Descent Beyond Finite Variance
May 25, 2026Jose Blanchet, Peter Glynn, Wenhao YangStochastic Gradient Descent Confidence Intervals
Management Science and Engineering, Stanford University
Adaptive Iterative Hard Thresholding for Online High-dimensional Quantile Regression
Jun 26, 2026Zitian Zhou, Nan LinMulti-Quantile Regression Sparsity
Washington University in St. Louis

May 19, 2025, stat.MLJ/K move · Enter open · S save

Online simultaneous inference for quantiles via smoothed stochastic gradient descent

Likai Chen, Georg Keilbar, Wei Biao Wu

Department of Mathematics and Statistics · Washington University in St.Louis · St.Louis, MO, USA+6

Quantile Regression Exponential Family Stochastic Gradient Descent Smoothing Conditional-Value-At-Risk

Open paper AskPDF arXiv

This paper considers the estimation of quantiles via a smoothed version of the stochastic gradient descent (SGD) algorithm. By smoothing the score function with a bandwidth tied to the learning rate, we obtain estimates that are monotone in the quantile level at every iteration, while retaining the memory and computational efficiency required for streaming data. We establish non-asymptotic tail probability bounds for the smoothed estimate with and without Polyak-Ruppert averaging, which are sub-exponential with a multi-regime structure. For the averaged estimate we further derive a Bahadur representation that is uniform in the quantile level and across coordinates, and a resulting Gaussian approximation by the maximum of Brownian bridges, with the dimension

p

allowed to grow exponentially in the sample size. This yields simultaneous inference across coordinates and quantile levels. As an alternative that avoids estimating the sparsity function, we propose an online multiplier bootstrap that preserves monotonicity, runs in a single pass and is asymptotically valid. Extending the theory to a localized recursion, we obtain online nonparametric conditional quantile estimates with uniform bands over design points and quantile levels. Simulations confirm accurate finite-sample coverage, and we illustrate the method on conditional value-at-risk curves.

Abstract

Explore similar work

Online simultaneous inference for quantiles via smoothed stochastic gradient descent

Statistical Inference for Stochastic Gradient Descent Beyond Finite Variance

Adaptive Iterative Hard Thresholding for Online High-dimensional Quantile Regression