📊 statistics

Locally Private Online Quantile Regression: Estimation and Inference

This paper proposes a locally private online quantile regression framework that utilizes a novel finite-alphabet channel with support-aware stochastic quantization and randomized response to enable unbiased, consistent, and asymptotically normal estimation and inference under user-level differential privacy.

Original authors: Yi Liu, Qirui Hu

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yi Liu, Qirui Hu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to predict the future price of a taxi ride based on distance, time of day, and passenger count. You have millions of people sending you their trip data. However, these people are worried about privacy. They don't want you to see their exact trip details (like exactly where they started or how long they took), but they do want you to learn the general patterns so you can build a better prediction model.

This paper solves a very specific puzzle: How can you learn from millions of people's private data, one person at a time, without ever seeing their raw data, while still getting accurate predictions?

Here is the breakdown of the problem and the solution, using everyday analogies.

The Problem: The "Broken" Puzzle Piece

In standard data analysis, to learn a pattern, you usually need two things from a person:

The Context: (e.g., "It was 8 PM, 5 miles away").
The Reaction: (e.g., "The trip took 15 minutes").

The math used to update the prediction model (called "quantile regression") requires looking at the relationship between the context and the reaction together. It's like trying to solve a puzzle where you need to see how a specific piece fits with the picture next to it.

The Privacy Obstacle:
Under strict privacy rules (Local Differential Privacy), a person must scramble their data before sending it.

If they scramble the "Context," the server doesn't know what the data is about.
If they scramble the "Reaction," the server doesn't know how the person responded.
If they scramble them separately, the server can't see how they fit together.

It's like asking a friend to describe a movie scene to you, but they are only allowed to whisper one scrambled word at a time. You can't reconstruct the scene because the words are disconnected. The authors call this the "coupling" problem: the server needs the connection between the context and the reaction, but privacy rules break that connection.

The Solution: The "Secret Code" Channel

The authors invented a clever way to send a single, scrambled message that still allows the server to figure out the pattern. They call this the CQX Channel.

Think of it like a mystery box game:

The Local Calculation (The User):
Instead of sending raw numbers, the user looks at their data and asks a simple question: "Is my trip longer or shorter than the model predicted?"
- If the answer is "Shorter," they pick a "Blue Card."
- If the answer is "Longer," they pick a "Red Card."
- They also look at specific details (like distance) and round them to a simple grid (like "Short," "Medium," "Long").
The Scramble (Randomized Response):
To protect privacy, the user flips a coin.
- If it's Heads, they tell the truth about which card they picked.
- If it's Tails, they lie and say they picked the opposite card.
- Crucially: The server doesn't know if the user is lying or telling the truth for any specific person. But the server knows the probability of the coin flip.
The Decoding (The Server):
The server receives thousands of these "Blue" and "Red" reports. Because the server knows the rules of the coin flip, it can use a mathematical trick (like a reverse-engineering formula) to cancel out the lies.
- Even though individual reports are noisy, the average of thousands of reports reveals the true pattern.
- The server effectively reconstructs the "connection" between the context and the reaction without ever seeing the raw data.

Why This is Better Than Other Methods

The paper compares their method to two other common ways of handling privacy:

Method A (The "Sprinkler"): Imagine trying to hide a secret by throwing water (noise) all over the paper. This protects the secret, but it also washes away the ink (the useful data). The paper shows this method is too messy for this specific type of math.
Method B (The "Strict Fence"): Imagine only allowing people to send data that fits inside a tiny, rigid box. This keeps the data "safe," but it forces the data into a shape that doesn't match the real world, leading to wrong predictions.

The Authors' Method:
Their method is like a smart translator. It compresses the data into a simple code (the card color) and adds just enough "noise" (the coin flip) to hide the individual, but uses a special decoder to ensure the overall message remains accurate.

The Results: Does it Work?

The authors tested this in two ways:

Simulations: They created fake data to see how well the system learned. They found that as they allowed a slightly larger "privacy budget" (meaning slightly less strict privacy), their method got very close to the accuracy of a system that saw all the raw data. It significantly outperformed the "Sprinkler" and "Strict Fence" methods.
Real World Test (NYC Taxis): They used real data from New York City taxi trips. They treated each trip as a private record.
- They wanted to predict trip duration.
- They found that even with privacy protection, their model could predict trip times almost as well as a model that saw the raw data.
- The "private" model was much more accurate than models using the older, simpler privacy methods.

The Bottom Line

This paper proves that you can build a smart, learning machine that updates itself every time a new person joins, without ever seeing that person's private details.

It works by having users send a single, scrambled report that acts like a vote. The server collects millions of these votes and uses math to figure out the true trend, ignoring the individual lies introduced for privacy. It's a way to get the best of both worlds: strong privacy for the individual and high accuracy for the group.

Technical Summary: Locally Private Online Quantile Regression

Problem Statement
The paper addresses the challenge of performing online quantile regression (QR) under a one-report, user-level $\varepsilon$ -locally differentially private ( $\varepsilon$ -LDP) protocol. In standard online QR, the server updates the estimator using the estimating-equation contribution $g_\beta(X, Y) = X \{ \mathbb{1}(Y \le X^\top \beta) - \tau \}$ . This vector couples the covariate $X$ with a residual comparison (the indicator function). Under user-level LDP, a server receives only a privatized report from each user. The core difficulty is that a standard privatization of this vector is impossible without violating the privacy constraint or destroying the conditional mean structure required for stochastic approximation. Specifically, if the server cannot observe $X$ and the indicator directly, it cannot form the unbiased update vector necessary for convergence. Existing methods for scalar private quantiles or central/private distributed QR do not address this specific "decoded estimating-equation" problem where a single LDP report must be transformed into an unbiased, covariate-dependent update.

Methodology
The authors propose a framework where the server does not receive the raw gradient but rather a decoded input that preserves the conditional mean of the estimating equation.

Support-Aware Geometry: The exact QR estimating-equation contribution $g_\beta(O)$ lies on a specific two-face support geometry $G_\tau$ . The intercept coordinate identifies the active face ( $\mathbb{1}(Y \le X^\top \beta) = 0$ or $1$), and the slope coordinates are constrained to symmetric intervals determined by the face and the bounded covariates.
The CQX(q, s) Channel: The authors construct a finite-alphabet channel named CQX( $q, s$ $q, s$ ), where $q$ $q$ is the grid size for slope quantization and $s$ $s$ is the size of a selected coordinate block.
- Local Processing: Each user computes $g_\beta(X, Y)$ locally. They stochastically quantize selected slope coordinates (using a public grid) to a finite category. If the intercept is selected, it acts as a face label; otherwise, slopes are quantized on an unconditional grid.
- Randomized Response: The user applies randomized response to the resulting finite category (the "selected-block category") to generate a single LDP report.
- Server-Side Decoding: The server applies an affine randomized-response decoder to correct the distortion and uses Horvitz-Thompson reconstruction to recover the full vector.
- Key Property: The decoded input $\tilde{g}_\beta$ satisfies conditional unbiasedness: $E[\tilde{g}_\beta(X, Y) \mid X, Y, \beta] = g_\beta(X, Y)$ . This allows the server to use the decoded input in a projected Polyak-Ruppert averaging scheme ( $\beta_i = \Pi_B \{ \beta_{i-1} - \eta_i \tilde{g}_i(\beta_{i-1}) \}$ ) without biasing the target parameter.
Inference: The paper develops Hessian-free inference procedures that do not require estimating the QR Hessian (which is difficult under LDP). These include:
- Self-Normalization (SN): Uses the temporal variation of the Polyak averages in a single trajectory.
- Divide-and-Conquer (DC): Partitions the stream into disjoint groups to compute group averages and form Hotelling-type confidence sets.
- HiGrad: Uses a public tree structure to generate correlated group centers with known covariance templates for studentization.

Key Contributions

Formulation: The paper formulates streaming linear QR under sequential one-report user-level LDP as a decoded estimating-equation problem, separating the privacy guarantee of the report from the mean-preserving requirement of stochastic approximation.
Mechanism Construction: It introduces the CQX( $q, s$ ) channel, which combines public coordinate selection, support-aware stochastic quantization, randomized response, and affine decoding. This mechanism exploits the two-face support geometry of the QR contribution to ensure the decoded server input is conditionally unbiased.
Theoretical Guarantees: For fixed finite channel designs, the authors prove:
- Local privacy ( $\varepsilon$ -LDP) for the one-record contribution.
- Conditional decoder unbiasedness.
- Consistency and asymptotic normality of the projected Polyak-Ruppert averaged estimator.
- Validity of Hessian-free self-normalized inference for prespecified scalar contrasts and vector ellipsoids.
Empirical Validation: Through simulations and a New York City taxi-trip data illustration, the paper demonstrates that the private trajectory approaches the non-private online reference as the privacy budget ( $\varepsilon$ ) increases. The proposed channel outperforms direct Laplace release (which ignores support) and face-exponential release (which shifts the mean) in terms of estimation error and uncertainty quantification.

Results

Estimation Accuracy: In simulations, the CQX( $q, s$ ) mechanism achieves lower mean Euclidean estimation error compared to geometric baselines (Direct Laplace and Face-exponential). The Face-exponential mechanism often fails at high quantiles ( $\tau=0.75$ ) due to mean-field mismatch causing projection boundary saturation.
High-Budget Recovery: As $\varepsilon \to \infty$ and the grid resolution $q$ increases, the private estimator's covariance converges to that of the non-private ASGD oracle.
Inference Calibration: The self-normalized (SN), divide-and-conquer (DC), and HiGrad procedures provide confidence intervals with coverage rates close to the nominal 95% level, particularly for scalar contrasts and dense contrasts. Full-vector ellipsoids are more sensitive to finite effective information and conditioning but remain valid under the stated rank conditions.
Real-Data Application: On the NYC taxi dataset, the private estimates preserve the holdout calibration (hit rates) and predictive check loss of the non-private reference, with performance improving as $\varepsilon$ increases.

Significance and Claims
The paper claims to present the first one-report LDP framework for online QR estimation and inference based on mean-preserving decoded estimating-equation inputs. It argues that standard additive-noise SGD approaches are ill-suited for QR because they ignore the specific support geometry of the estimating equation. By decoupling the privacy mechanism from the estimation update via a decoding step, the authors show that one-report local privacy is compatible with online QR. The significance lies in enabling valid statistical inference (consistency, normality, confidence intervals) in a streaming, privacy-constrained environment without requiring a trusted curator or multiple reports per user. The authors note that the theory is deliberately fixed-dimensional and relies on bounded covariates; extensions to high-dimensional settings or adaptive channel designs are left for future work.