Online Quantile Regression for Nonparametric Additive Models

Authors	Haoran Zhan
Year	2026
Field	Statistics / ML
arXiv	2604.08969
PDF	Download
Categories	stat.ML, cs.LG

Abstract

This paper introduces a projected functional gradient descent algorithm (P-FGD) for training nonparametric additive quantile regression models in online settings. This algorithm extends the functional stochastic gradient descent framework to the pinball loss. An advantage of P-FGD is that it does not need to store historical data while maintaining $O(J_t\ln J_t)$ computational complexity per step where $J_t$ denotes the number of basis functions. Besides, we only need $O(J_t)$ computational time for quantile function prediction at time $t$. These properties show that P-FGD is much better than the commonly used RKHS in online learning. By leveraging a novel Hilbert space projection identity, we also prove that the proposed online quantile function estimator (P-FGD) achieves the minimax optimal consistency rate O(t^{-\frac{2s}{2s+1}}) where $t$ is the current time and $s$ denotes the smoothness degree of the quantile function. Extensions to mini-batch learning are also established.

---

Engineering Breakdown

Plain English

This paper presents P-FGD (projected functional gradient descent), an algorithm for training quantile regression models that work on streaming data without storing historical samples. Traditional approaches like RKHS require keeping past data in memory and have expensive computational costs; this method cuts that down to O(J_t ln J_t) per step where J_t is the number of basis functions, and prediction takes only O(J_t) time. The key innovation is applying functional stochastic gradient descent to the pinball loss (used in quantile regression) while maintaining theoretical optimality guarantees, making it practical for real-time systems that need to estimate conditional quantiles continuously.

Core Technical Contribution

The core innovation is extending functional stochastic gradient descent from standard regression (squared loss) to quantile regression (pinball loss) in an online setting. The authors introduce a novel Hilbert space projection identity that enables them to prove minimax-optimal convergence rates while avoiding the computational burden of kernel methods like RKHS. This is the first practical algorithm that combines three properties: no historical data storage, sublinear per-step complexity, and theoretical optimality guarantees for nonparametric additive quantile models. The projection mechanism allows them to maintain a compact functional representation rather than storing all past observations.

How It Works

P-FGD operates on streaming data by maintaining a functional representation as a linear combination of basis functions (e.g., splines, wavelets). At each time step t, the algorithm receives a new sample and computes a gradient of the pinball loss (the asymmetric loss function for quantile regression) with respect to the current function estimate. This gradient is projected back into the space spanned by the basis functions using the novel Hilbert space projection identity, which efficiently updates the coefficients without storing historical data. The key technical component is the projection step: rather than computing expensive kernel evaluations against all historical points, the algorithm uses functional gradient information directly to update the J_t basis function coefficients. For prediction at time t, the algorithm simply evaluates the linear combination of basis functions at the new input point, taking O(J_t) time.

Production Impact

This approach enables quantile regression for real-time streaming systems where memory and computation are constrained—think risk modeling for financial transactions, confidence interval generation for demand forecasting, or percentile-based monitoring in real-time analytics platforms. The O(J_t ln J_t) per-step complexity is orders of magnitude faster than kernel methods that scale with the number of historical observations, making it feasible to retrain or update models on high-frequency data streams. Engineers adopting this would eliminate the need to maintain growing buffer windows of historical data, reducing memory footprint significantly while maintaining statistical guarantees on prediction intervals. The trade-off is that you must choose the basis functions and number of functions J_t upfront; adding more basis functions improves expressiveness but increases computational cost linearly, requiring careful tuning for your application.

Limitations and When Not to Use This

The paper assumes that the underlying nonparametric quantile function lies in a reproducing kernel Hilbert space (RKHS), which may not hold for all real-world relationships, particularly those with discontinuities or highly irregular structure. The method's performance depends critically on choosing appropriate basis functions and the number J_t; poor choices will lead to underfitting regardless of sample size, and the paper doesn't provide principled guidance for this selection in practice. The theoretical guarantees (minimax optimality) apply in the asymptotic regime and under smoothness assumptions that may be violated in practice; finite-sample behavior and robustness to basis function misspecification are not thoroughly analyzed. Additionally, the algorithm is restricted to nonparametric additive models, meaning it cannot capture feature interactions beyond the additive structure, limiting its applicability for complex relationships.

Research Context

This work builds on the functional stochastic gradient descent framework (previously applied to convex losses) and extends it to the nonconvex/non-smooth setting of quantile regression via the pinball loss. It advances the online nonparametric learning literature by bridging kernel methods (RKHS) and functional gradient methods, showing that you don't need to store all historical data to achieve theoretical optimality. The paper contributes to the broader area of streaming/online learning where maintaining constant memory and sublinear computation per step is essential, complementing recent work on neural tangent kernels and functional approaches to deep learning. This opens research directions in extending P-FGD to other loss functions, handling non-additive models, and developing adaptive basis selection strategies for unknown function classes.

---

:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::

---

Back to Research Lab → · Subscribe to AI Letters →