Quantile regression predicts a chosen percentile of an outcome, such as the 5th or 95th, instead of its average. It is the standard tool when data are skewed or heavy-tailed. Its loss, the "check loss" $\rho_\tau(u) = u(\tau - \mathbb{I}_{\{u<0\}})$ for residual $u$ and target quantile $\tau$, has a sharp corner at zero. That corner is why the fastest exact high-dimensional solvers run one coordinate at a time on a single thread. The Finite Smoothing Algorithm (FSA) and Semismooth Newton Coordinate Descent (SNCD) both work this way. The parallel coordinate descent methods that do scale across cores, PCDM and Asy-GCD, assume a smooth loss. The Asy-GCD paper explicitly lists non-smooth objectives as unresolved.
The obvious fix is to smooth the corner and run a parallel coordinate method on the result. This throws away most of the available parallelism. For dense design matrices, a generic parallel step-size rule must assume every coordinate interacts with every other, so adding processors buys almost nothing. Our observation is that after FSA-style smoothing, curvature comes only from the few observations whose residuals sit inside the smoothing window, close to the corner. Every other observation contributes a purely linear term. We therefore propose a parallel block update that sets its step sizes from that small near-corner set. A trust region keeps the update exact by stopping residuals from crossing into the window unnoticed. FSA's exactness step then recovers the true non-smooth solution. The work also includes a benchmark with wall-clock profiling on real hardware, because the third direction in the source material is precisely that theory in this area goes untimed.
Core Claim
FSA replaces the check loss inside a window $[-\delta,\delta]$ with a quadratic. Its Hessian with respect to the coefficients $\beta$ is then
$$ H(\beta) = \frac{1}{\delta}\, X_{W(\beta)}^\top X_{W(\beta)}, $$
where $X$ is the $n\times p$ design matrix and $W(\beta)$ is the set of rows whose residual lies in the window. Rows outside $W$ contribute nothing to $H$.
Consider a block update that moves each outside-window residual by less than its distance to the window edge. Within that region the objective is exactly quadratic plus linear. The curvature constant that limits simultaneous updates, called the Expected Separable Overapproximation (ESO) parameter in PCDM, can then be computed from $X_W$ alone.
Two regimes favour this. In high dimensions, $|W|$ is at most $n$ and is often near the number of "support vectors" that FSA identifies. On large sparse data, the coordinate coupling measured on the near-corner rows is far below the coupling measured on all rows.
The claim, stated concretely, has three parts. Kink-aware step sizes should give near-linear multicore speedup where a global ESO bound on the same smoothed loss gives little. The update needs no approximation beyond FSA's own smoothing. FSA's support-vector constraint step still returns the exact check-loss solution.
Research Program
Update rule. At each outer iteration the solver takes a snapshot of the near-corner set $W$ and computes per-coordinate curvature bounds from $X_W$. It then samples a random block of coordinates across the cores and computes their proximal steps in parallel. The penalty can be Lasso, elastic net, SCAD or MCP, following FSA's hdqr/hdsvm machinery.
Trust-region clip. Before accepting a step, the solver checks whether it would push any outside-window residual across the window edge. If so, it either scales the step back or admits those rows into $W$ and recomputes. This safeguard is what makes the local curvature bound valid, not heuristic.
Screening and exactness. Feature screening comes from SNCD's Adaptive Strong Rule. FSA's exactness step runs unchanged at the end.
Analysis. We will prove a PCDM-style iteration bound in which the ESO parameter depends on $X_W$. We will also test empirically how much of the gap between the global and kink-aware constants survives in practice.
Asynchronous variant. A lock-free version in the style of Asy-GCD, with stale reads of $W$, is a stretch goal. Asy-GCD's bounded-delay analysis needs smoothness, which the trust region supplies only locally. We treat this variant as exploratory.
Baselines
Naive reference. Single-threaded FSA (hdqr) and SNCD on the same machine form the do-nothing baseline. The strongest reported numbers in the file come from these solvers:
- On the Riboflavin data, SNCD computed a full solution path in about 3 seconds, against more than 500 seconds for
quantreg(SNCD). - At $p = 10{,}000$, FSA solved a high-dimensional SVM in 0.12 seconds, against about 1,389 seconds for
ReHlineand about 1,425 seconds forCVXR(FSA). - There is no reported result on Lacuna for multicore penalized quantile regression. The nearest multicore figure is Asy-GCD's 13 to 15 times speedup on 20 cores, which is for kernel SVM.
Beating the naive baseline means lower wall-clock time for the same final objective, to a relative tolerance of $10^{-7}$ (the precision SNCD reports).
Threaded inner products. This baseline keeps FSA sequential over coordinates but splits each coordinate's $O(n)$ residual inner product across threads. It is the cheapest way to use cores and wins whenever $n$ is large and the coordinate loop is short.
Global-ESO ablation. This is PCDM on the same FSA-smoothed loss with the global ESO parameter. It is the ablation that isolates the proposal's key ingredient. It uses the same block sampling, screening and core count, and differs only in computing curvature from all of $X$ rather than $X_W$.
Embarrassingly parallel path. Each core fits a different penalty value $\lambda$, target quantile $\tau$, or cross-validation fold. Its cost is the loss of warm starts along the path.
GPU proximal gradient. Accelerated proximal gradient runs on the smoothed loss on a GPU, with the same strong-rule screening.
Fairness rules. Every method gets the same data, the same $\lambda$ grid, the same smoothing width $\delta$, the same stopping tolerance, and the same hardware budget of 1 to 32 CPU cores or one GPU. Each gets an equal tuning budget of 20 configurations, and we report the best configuration per method.
Why not just…?
Why not just run Adam or mini-batch SGD on the smoothed check loss on a GPU? Gradient methods touch every feature on every step and cannot drop inactive features cheaply. Coordinate screening is where the reported advantages come from: SNCD's strong rule gave a 40 to 100 times speedup at $p = 100{,}000$, and FSA's 10,000-fold gap over general convex solvers points the same way. Stochastic steps also struggle to reach the tight tolerances that exact penalized solutions need. We include a tuned GPU proximal-gradient baseline rather than assume this. If it matches our wall-clock time at $10^{-7}$ tolerance on the large sparse problems, the multicore coordinate route is not worth its complexity there.
Why not just parallelize across the λ grid, τ levels, or CV folds? This is the most serious threat, and we expect it to win on total throughput when a user needs many independent fits. Its weakness is latency and memory. Pathwise coordinate descent relies on warm starts, so an independent fit per $\lambda$ can cost several times one warm-started path. Each core also needs its own residual state. We will report both throughput for a full $\lambda$ by $\tau$ by fold grid and latency for a single path. We will also test the hybrid that is likely best in practice: the path parallelized across $\tau$, with kink-aware blocks inside each path. We claim an advantage only on the latency and large-$p$ axes.
Why not just solve the linear-program form with a multithreaded interior-point solver? The file reports interior-point cost growing as $O(np^2)$. It gives quantreg taking more than 500 seconds where SNCD takes 3, and exact LP solvers failing at 10,000 samples in the vector quantile regression study. Threaded linear algebra does not remove the $p^2$ factor. We keep quantreg as a reference on problems where it runs.
Why not just use distributed double smoothing? DHSQR and the communication-constrained method reduce communication between machines. They solve the central surrogate Lasso sequentially and change the estimator through their bandwidth choices. Our method is complementary: it could serve as the solver inside each node. We will demonstrate this by plugging it into the DHSQR central step on the HIV drug resistance data.
Proposed Experiments
Correctness checks, not speedup claims. The genomic datasets from FSA and SNCD are too small to reward parallelism: BREAST, MALARIA, OVARIAN, LEUK, COLON, Rat Eye with $p=31{,}000$ and $n=120$, and Riboflavin. We use them to confirm three things. The parallel solver must reach the same objective within $10^{-7}$, the same support, and the same prediction error as single-threaded FSA and SNCD. We expect overhead to cancel any speedup on these datasets, and we will report whatever we find.
Speedup benchmarks. The speedup claims rest on three settings:
- rcv1.binary ($n=677{,}399$, $p=47{,}236$), fitted with hinge loss through FSA's SVM path.
- KDDB, using a quantile-transformed regression target.
- The synthetic $p = 10{,}000$ to $100{,}000$ design used by FSA and SNCD, with $n$ scaled up to $10^6$ and Cauchy, $t_2$ and Laplace noise.
We deliberately include rcv1 because PCDM flagged its large coupling parameter as a scaling obstacle. It is therefore the cleanest test of whether measuring coupling on near-corner rows removes that obstacle.
Metrics. We report wall-clock time to tolerance, speedup curves from 1 to 32 cores, and the measured ratio of global to kink-aware curvature constants along the path. We also report the fraction of steps that the trust region clips, and hardware counters for cache misses and synchronization wait.
Decisive checks. The main result is the ablation: kink-aware against global ESO at equal cores. If the curvature ratio is large but wall-clock gains are small, the bottleneck lies elsewhere, most likely memory bandwidth. The hardware profile should show which. If clipping fires on a large share of steps, the near-corner set is too unstable, and a wider $\delta$ or periodic resynchronization becomes the necessary fix.
The field-level check follows from the Gaussian-design caveats in the proximal SGD risk-tracking and one-shot federated papers. We will vary feature distributions from Gaussian to heavy-tailed and correlated, and test whether $|W|$, and with it the speedup, stays small. This is where theory built on idealized designs could quietly fail.
References
- Finite Smoothing Algorithm for High-Dimensional Support Vector Machines and Quantile Regression
- Semismooth Newton Coordinate Descent Algorithm for Elastic-Net Penalized Huber Loss Regression and Quantile Regression
- Parallel coordinate descent methods for big data optimization
- Asynchronous Parallel Greedy Coordinate Descent
- Fast Nonlinear Vector Quantile Regression
- Distributed High-Dimensional Quantile Regression: Estimation Efficiency and Support Recovery
- Communication-Constrained Distributed Quantile Regression with Optimal Statistical Guarantees
- Estimating Generalization Performance Along the Trajectory of Proximal SGD in Robust Regression
- One-Shot Weighted Ensemble Estimation for Federated Quantile Regression: Optimal Statistical Guarantees under Heterogeneous Structured Data