CS Paper Radar

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

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

cs.LG stat.MLmath.STstat.ME ·submitted 2026-10-05 06:35 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Online Inference for Quantile Distributional Reinforcement Learning

cs.LG stat.ML ·2026-08-13 ·Zijie Cheng, Yang Peng, Zhihua Zhang
theory similarity 0.69
Abstract

In this paper, we study online statistical inference for quantile-based distributional policy evaluation, which aims to characterize the distribution of discounted cumulative rewards under a given policy. To obtain a finite-dimensional representation of the return distribution, we consider the fixed point $\bmη_m$ of the quantile-projected distributional Bellman equation, parameterized by the quantile vector $\bmθ_m$. We develop two online inference procedures for $\bmθ_m$, covering synchronous and asynchronous sampling from a generative model as well as Markovian data. The first method uses the trajectory of quantile temporal-difference learning (QTD). We establish functional central limit theorems for the partial sums of QTD iterates and construct a recursively computable random-scaling statistic. The resulting confidence intervals have asymptotically exact coverage at deterministic horizons, with length of order $T^{-1/2}$ in probability. The second method constructs anytime-valid confidence intervals directly from samples. Exploiting the monotonicity of the quantile Bellman map, we develop a computationally explicit coordinate-shaving algorithm with finite-sample simultaneous coverage. Under positive limiting state-visit frequencies, the resulting confidence intervals have lengths of order $\sqrt{\log\log T/T}$, which we establish as classwise optimal through a matching lower bound. Together, these results provide complementary guarantees for online inference in quantile distributional reinforcement learning, combining asymptotically exact fixed-horizon inference with finite-sample anytime validity.

0.34

Online Inference in Distributional Temporal-Difference Learning

cs.LG stat.ML ·2026-08-14 ·Yang Peng, Liangyu Zhang
theory similarity 0.64
Abstract · There is a technical error in "Step 3" of the proof of Theorem 4, section 4

We study online statistical inference for functionals of the return distribution under a fixed policy. The return distribution is estimated by nonparametric distributional temporal-difference learning from a single Markov trajectory. For the Polyak--Ruppert averaged estimator, we prove that its root-$T$ error converges weakly to a centered Gaussian random element in Cramér space. We also prove that, conditionally on the observed trajectory, the root-$T$ difference between the bootstrap and original averages converges weakly to the same Gaussian limit. These results justify bootstrap inference for smooth statistical functionals, including variance, CVaR, expected shortfall, and expectiles. For nonsmooth statistical functionals, we develop a local asymptotic theory for the estimated return CDF over $T^{-1/2}$-neighborhoods of finitely many thresholds, together with its bootstrap analogue. This theory allows us to conduct inference for nonsmooth statistical functionals characterized by CDF equations, including return quantiles.

0.34

Conformalized Quantile Regression and Minimax Limits of Fixed-Score Calibration under Known Covariate Shift

cs.LG math.STstat.ML ·2026-09-21 ·Rustam Isaev, Anton Conrad, Denis Belomestny, Eric Moulines, Sergey Samsonov
theory similarity 0.62
Abstract · 65 pages, 3 figures

In this paper, we study nonasymptotic $L^p$ error bounds for interval length and conditional coverage in split conformalized quantile regression (CQR). Our bounds rely on local regularity conditions and accuracy guarantees for the estimated quantiles. We further instantiate our bounds for quantile regression with sparse ReLU neural networks. We also consider covariate shift, where the calibration and test covariates have different distributions, and derive nonasymptotic bounds for this setting. We obtain matching minimax upper and lower bounds in expectation for two constructed fixed-score calibration benchmarks under known covariate shift. The bounds match for every $p\in[1,\infty]$ in the scalar problem and for finite $p$ in the $K$-threshold problem; for the latter, a high-probability minimax lower bound holds for every $p\in[1,\infty]$.

0.60

Strong Gaussian Approximation of Constant Learning Rate SGD: Bias and Trajectory Inference

cs.LG stat.ML ·2026-10-10 ·Joseph Keslin, Wei Biao Wu
similarity 0.61
Abstract

This paper develops strong Gaussian approximations (KMT type) for constant learning rate stochastic gradient descent (SGD). We work with heavy tailed noise and assume that the number of iterates grows and the learning rate shrinks simultaneously. Our work constructs simple Gaussian processes on the same space and bounds, in probability, the maximum difference between the SGD errors and their respective limits. While there exist central limit theorems for constant rate SGD centered at the optimum, these only provide individual iterate inference. By contrast, our quenched KMT approximations allow for finite sample, simultaneous, whole-trajectory-level inference and imply stochastic process convergence (Functional Central Limit Theorems (FCLTs)). For accumulated errors centered at the true optimum, we first obtain a KMT-type approximation bound when the learning rate scales as $γ_n=\frac{c}{\sqrt n}+o(n^{-1/2})$ for a constant $c \in \mathbb{R}^+$ and $n$ iterations. The result reveals a trade off between controlling the bias of SGD and the initialization effect, with no learning rate scaling generally making both contributions vanish in the accumulated error limit. To eliminate these contributions, we consider a Burn in scheme and Richardson-Romberg extrapolation and prove respective KMT and FCLT theorems. We also prove a finite-horizon KMT-type approximation and FCLT for the rescaled iterate trajectory to a stationary Ornstein--Uhlenbeck (OU) process. We consider applications in risk control and simultaneous inference and perform simulations to illustrate our results.

0.22

Robust Aggregation of Quantile Statistics: from Median to Interval

cs.GT ·2026-11-03 ·Mingyu Song, Yizhou Wang, Yuqing Kong
similarity 0.61
Abstract · 24 pages, 5 figures

Quantile-based summaries, such as prediction intervals and medians, are commonly used in economic forecasting, climate science, and public health. For highly skewed samples, experimental evidence suggests that estimates of the mean can be biased toward the median, whereas estimates of the median are relatively accurate. This motivates aggregating explicitly elicited quantiles rather than reported means. We study robust aggregation of quantile reports for bounded outcomes under squared loss, minimizing worst-case regret relative to an omniscient Bayesian aggregator who knows the information structure and observes all private signals. Without restrictions on the information structure, no rule improves on the constant forecast at the range midpoint in worst-case regret. We therefore consider weak substitutes, a diminishing-returns condition on the value of information, and characterize optimal aggregation rules under this condition. For central prediction intervals with common nominal coverage $α$, the optimal rule, which we call regularized simple average for prediction intervals, shrinks the average reported interval midpoint toward the range midpoint, with a weight determined by $α$ and the number $n$ of experts. This optimal rule strictly improves on the constant baseline in worst-case regret when $α<1/\sqrt{n}$; at or above this threshold, the constant rule is optimal. The optimal worst-case regret is minimized at a unique interior coverage level, revealing a nonmonotonic relationship between coverage and aggregation performance. For median reports, regularized simple average for medians similarly shrinks the average reported median toward the range midpoint, assigning weight $1/n$ to the reported average and strictly improving on the constant baseline in worst-case regret for every finite $n\ge2$.

0.14

Limit Theory for Online Expectile Estimation under Short and Long Range Dependence

cs.LG stat.MLmath.ST ·2026-10-12 ·Younghun Lee, Jake Zummo, Wei Biao Wu
similarity 0.61
Abstract · 36 pages, 1 figure

Expectiles are tail-sensitive distributional summaries with important applications in financial risk measurement and forecasting, yet statistical theory for their online estimation from dependent data remains limited. We study a one-pass, stochastic-gradient algorithm with constant learning rate $γ$ for estimating the marginal expectile of a stationary causal process. The recursion admits a unique stationary causal solution and geometrically forgets its initialization. Under short-range dependence, its last iterate is asymptotically Gaussian at the $\sqrtγ$ scale, with variance governed by the population curvature and the long-run variance of the expectile score. For long-memory linear processes the scale changes to $γ^{β-1/2}\ell(1/γ)$, with a Gaussian limit arising from a fractional Brownian motion integral. We further derive the joint long-memory limit for multiple expectile levels and characterize its limiting covariance structure. Various numerical experiments corroborate the predicted Gaussian approximations and regime-specific fluctuation scales.

0.29

Quantile-based Loss Filtering for Outlier-Robust Stochastic Gradient Descent

cs.LG math.NA ·2026-09-11 ·Jamie Haddock, Anna Ma, Elizaveta Rebrova
theory similarity 0.60
Abstract

We study loss-based filtering for finite-sum optimization with a subset of corrupted component functions whose gradients may be highly unreliable. Motivated by minimum-loss-based SGD (min-$k$-loss) and quantile-based methods for corrupted linear systems, we propose and analyze a general loss-filtering framework -- Quantile-\(k\)-Loss SGD (Q\(k\)L-SGD) -- that samples \(k\) component losses at each iteration and updates using an index chosen uniformly from the lower empirical \(q\)-quantile. We prove linear convergence of this family of methods under standard convexity assumptions, requiring the sample size to scale with the number of corruptions and a subset strong-convexity threshold. For the cases when large enough sampling is impossible or undesirable, we give a complementary small-sample probabilistic analysis that covers any sample size $k$ and the convergence behavior depends on the probability of selecting an outlier and on the curvature of the selected good step. Experiments on polynomial regression, regularized logistic regression, and regularized hinge loss show that intermediate quantiles often outperform both standard SGD and min-\(k\)-loss SGD. In particular, min-\(k\) often stalls by repeatedly selecting nearly solved components, while intermediate quantiles retain robustness and produce more informative updates.

0.30

Personalized Federated Learning via Variance-Aware Nonparametric Empirical Bayes

cs.LG stat.MLstat.ME ·2026-08-10 ·Jae Ho Chang, Arnab Auddy, Subhadeep Paul
similarity 0.59
Abstract

We develop a new approach to Personalized Federated Learning across heterogeneous clients using Nonparametric Empirical Bayes (NPEB). Leveraging the asymptotic normality of local parameter estimates obtained from Empirical Risk Minimization or M-estimation, our method formulates these estimates as noisy observations to estimate an unknown shared prior via Nonparametric Maximum Likelihood. A key challenge in applying NPEB in this setting is that existing approaches assume known fixed variances, which is not true in practice. To address this, we introduce a Variance-Aware Nonparametric Empirical Bayes (VANEB) framework that leverages the parameter-dependent asymptotic variance of local M-estimators. A key technical contribution is a generalized Tweedie's formula for this heteroskedastic setting. We then establish non-asymptotic error rates for density estimation in the average squared Hellinger distance and derive an oracle denoising inequality that provides error bounds for our estimator. While our theoretical guarantees are rooted in the asymptotic regime of M-estimators, we empirically explore heuristic extensions of VANEB to modern federated learning settings involving Deep Neural Networks (DNNs). For DNNs, we propose VANEB-head and VANEB-FT, which personalize the last fully connected layer via an NPEB step using an approximate diagonal variance estimator. We show that our method has strong performance on popular vision datasets MNIST and CIFAR-10, using a convolutional neural network architecture.

0.04