Differential Privacy (DP) is the gold standard for sharing statistical insights without compromising individual privacy. A classic task in data analysis is calculating quantiles—such as medians, deciles, or percentiles. However, when multiple quantiles are needed, existing differentially private algorithms fare poorly. They either compute quantiles individually, which splits the privacy budget and reduces accuracy, or they summarize the entire distribution, which wastes computational effort and adds unnecessary noise.
To bridge this gap, researchers have developed JointExp, a novel algorithm that simultaneously estimates exactly $m$ quantiles from $n$ data points while guaranteeing differential privacy. JointExp achieves significantly higher accuracy than existing methods without sacrificing computational efficiency.
The Challenge of Multiple Quantiles
When calculating a single quantile (e.g., the median salary in a company), DP adds carefully calibrated noise to prevent the exact value from revealing an individual's data. The challenge arises when requesting multiple quantiles (e.g., the 10th, 20th, ..., 90th percentiles). Standard DP approaches typically hit a wall due to two main strategies:
- Composition: Calculating each quantile individually requires splitting the total "privacy budget" ($\epsilon$) among them. More quantiles mean more noise per quantile, leading to a sharp drop in accuracy.
- Distribution Summaries: Releasing a private summary of the entire data distribution (like a Cumulative Distribution Function) avoids budget splitting but is often "overkill." It yields less accurate estimates for specific quantiles unless a massive number of them are requested.
JointExp targets the crucial "middle ground"—applications needing between 1 and 30 quantiles—where existing methods are frustratingly imprecise.
The JointExp Method: Low Sensitivity and High Efficiency
JointExp is an instantiation of the Exponential Mechanism, which assigns a "utility score" to every possible output and samples an output with a probability proportional to its score.
The Secret Sauce: Low Sensitivity
The core innovation of JointExp is a joint utility function that measures how well a set of $m$ proposed quantiles matches the actual data. Crucially, this function has a sensitivity of 2, regardless of how many quantiles ($m$) are requested. In the realm of DP, low sensitivity is highly desirable; it means the algorithm does not need to increase the noise as it extracts more information. By treating the quantiles as a single joint output rather than $m$ independent ones, JointExp avoids the "privacy tax" of composition.
Efficient Sampling via Dynamic Programming
Sampling from this mechanism is theoretically difficult because the output space is continuous and $m$-dimensional. A naive approach would take $O(n^m)$ time, which is intractable for even small datasets. To make JointExp practical, the authors leverage a connection to graphical models:
- Discretization: The algorithm first samples the intervals between data points where the quantiles should fall.
- Dynamic Programming: Because the utility function's structure resembles a chain-structured graphical model, the authors use a "forward-backward" dynamic programming algorithm to sample these intervals efficiently.
- FFT Optimization: Fast Fourier Transforms (FFT) are used to speed up matrix multiplications, bringing the final computational complexity down to a highly practical $O(mn \log n + m^2n)$.
Experimental Results
The authors evaluated JointExp against three state-of-the-art competitors (AppIndExp, CSmooth, and AggTree) using both synthetic (Gaussian and Uniform) and real-world datasets (Goodreads ratings and page counts).
JointExp consistently outperformed the competition across all tested datasets.
- Accuracy: For a single quantile ($m=1$), JointExp matches the best existing methods. However, as $m$ increases toward 30, JointExp's error is often 2 to 3 times smaller than its closest competitor.
- The "Sweet Spot": JointExp is the clear winner for any number of quantiles between 1 and approximately 30.
- Speed: The algorithm remains highly efficient in practice, processing 1,000 data points in about 1 millisecond and a million data points in under a minute.
Limitations and Future Work
While JointExp dominates for moderate numbers of quantiles, specialized tree-based CDF methods (like AggTree) may become more efficient if a user needs hundreds of quantiles simultaneously.
Looking ahead, the authors suggest applying this "joint exponential mechanism" framework to other structured problems. Any utility function that can be decomposed into a "chain" or "tree" of dependencies could potentially be made private and efficient using the same dynamic programming logic, opening new doors for practical, high-accuracy differential privacy.
Summary updated