Abstract
Quantiles are often used for summarizing and understanding data. If that data is sensitive, it may be necessary to compute quantiles in a way that is differentially private, providing theoretical guarantees that the result does not reveal private information. However, when multiple quantiles are needed, existing differentially private algorithms fare poorly: they either compute quantiles individually, splitting the privacy budget, or summarize the entire distribution, wasting effort. In either case the result is reduced accuracy. In this work we propose an instance of the exponential mechanism that simultaneously estimates exactly $m$ quantiles from $n$ data points while guaranteeing differential privacy. The utility function is carefully structured to allow for an efficient implementation that returns estimates of all $m$ quantiles in time $O(mn\log(n) + m^2n)$. Experiments show that our method significantly outperforms the current state of the art on both real and synthetic data while remaining efficient enough to be practical.
Introduction
Quantiles are essential for summarizing data distributions, but they can leak sensitive information. For example, if a company has only two salary tiers, publishing an exact median salary could reveal a specific employee's pay. Differential Privacy (DP) provides a mathematical framework to prevent such leaks, but existing DP quantile algorithms struggle when multiple values are required.
Current approaches typically fall into two categories:
- Composition: These methods calculate each quantile individually, splitting the "privacy budget" ($\varepsilon$) among them. As the number of quantiles ($m$) grows, the noise added to each estimate increases, significantly reducing accuracy.
- Full Distribution Summary: These methods attempt to release a private version of the entire data distribution (e.g., via a noisy CDF). This often wastes the privacy budget on parts of the distribution that are not of interest to the user.
This paper introduces JointExp, a novel algorithm that addresses these issues by treating the estimation of $m$ quantiles as a single joint operation.
The JointExp Algorithm
JointExp is built on the Exponential Mechanism, a standard tool in differential privacy that selects outputs based on a "utility function." The core innovation lies in the design of this function and the method used to sample from it.
A Low-Sensitivity Utility Function
The authors designed a utility function that measures how many data points fall into the intervals between proposed quantiles compared to the "ideal" number. Crucially, they prove this function has a sensitivity of 2, regardless of how many quantiles are being estimated. This is because moving a single data point can only change the counts in at most two adjacent quantile intervals. Because the sensitivity remains constant, the privacy budget does not need to be diluted as $m$ increases, allowing for much higher accuracy than composition-based methods.
Efficient Sampling via Dynamic Programming
Sampling from the exponential mechanism over a continuous $m$-dimensional space is generally computationally intractable. To solve this, the authors discretize the problem by considering intervals between data points. They then frame the sampling problem as an inference task on a graphical model.
By representing the joint utility as a chain (as shown in the figure above), the algorithm can use a dynamic programming approach—similar to the forward-backward algorithm in Hidden Markov Models—to sample the quantiles efficiently. To further optimize the process, the authors utilize the Fast Fourier Transform (FFT) to handle Toeplitz matrix operations, reducing the computational complexity from $O(mn^2)$ to $O(mn \log n + m^2n)$. This makes the algorithm viable for datasets with millions of points.
Experimental Evaluation
The authors evaluated JointExp against several state-of-the-art baselines, including independent applications of the exponential mechanism (AppIndExp), smooth sensitivity methods (CSmooth), and tree-based CDF approaches (AggTree). Testing was conducted on both synthetic data (Gaussian and Uniform distributions) and real-world datasets from Goodreads (book ratings and page counts).
Key Results
- Superior Accuracy: Across all datasets, JointExp consistently outperformed competitors. For a wide range of $m$, it achieved 2-3x lower error than the next best method. While composition-based methods see error grow superlinearly with $m$, JointExp’s error scales only linearly.
- Practical Speed: Despite the underlying mathematical complexity, the algorithm is highly efficient. It processes 1,000 data points in approximately 1 millisecond and handles a dataset of 1 million points in under a minute.
- Robustness: The method proved effective on both smooth synthetic data and the skewed, "messy" distributions found in real-world Goodreads data.
Conclusion and Future Work
JointExp demonstrates that estimating multiple quantiles jointly is not inherently "riskier" from a privacy perspective than estimating one. By framing the privacy problem as a graphical model inference task, the authors achieved a significant breakthrough in accuracy without sacrificing practical performance.
Future work may involve addressing the algorithm's performance on datasets with massive clusters of identical values (where "jittering" the data is currently recommended) and exploring how this "low-sensitivity utility + efficient DP sampling" framework can be applied to other complex data summarization tasks.
Summary updated