# Differentially Private Quantiles

arXiv: https://arxiv.org/abs/2102.08244 · HTML: https://mlsanity.com/paper/2102.08244/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 48 references that are in the map.
- First posted on arXiv 16 Feb 2021.

## Builds on (most cited first, 13 of 13)

- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [The Discrete Gaussian for Differential Privacy](https://mlsanity.com/paper/2004.00010/) (2020)
- [Graphical-model based estimation and inference for differential privacy](https://mlsanity.com/paper/1901.09136/) (2019)
- [Differentially Private Release and Learning of Threshold Functions](https://mlsanity.com/paper/1504.07553/) (2015)
- [Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation](https://mlsanity.com/paper/1906.02830/) (2019)
- [Privately Learning Thresholds: Closing the Exponential Gap](https://mlsanity.com/paper/1911.10137/) (2019)
- [A Primer on Private Statistics](https://mlsanity.com/paper/2005.00010/) (2020)
- [Optimal Private Median Estimation under Minimal Distributional Assumptions](https://mlsanity.com/paper/2011.06202/) (2020)
- [Differentially Private Learning of Undirected Graphical Models using Collective Graphical Models](https://mlsanity.com/paper/1706.04646/) (2017)
- [Duff: A Dataset-Distance-Based Utility Function Family for the Exponential Mechanism](https://mlsanity.com/paper/2010.04235/) (2020)
- [Optimal Differential Privacy Composition for Exponential Mechanisms and the Cost of Adaptivity](https://mlsanity.com/paper/1909.13830/) (2019)

## Built on by (most cited first, 23 of 23)

- [Conformal Prediction for Federated Uncertainty Quantification Under Label Shift](https://mlsanity.com/paper/2306.05131/) (2023)
- [Differentially Private Approximate Quantiles](https://mlsanity.com/paper/2110.05429/) (2021)
- [Non-parametric Differentially Private Confidence Intervals for the Median](https://mlsanity.com/paper/2106.10333/) (2021)
- [Unbounded Differentially Private Quantile and Maximum Estimation](https://mlsanity.com/paper/2305.01177/) (2023)
- [A Survey of Privacy-Preserving Model Explanations: Privacy Risks, Attacks, and Countermeasures](https://mlsanity.com/paper/2404.00673/) (2024)
- [Private Quantiles Estimation in the Presence of Atoms](https://mlsanity.com/paper/2202.08969/) (2022)
- [Learning-Augmented Private Algorithms for Multiple Quantile Release](https://mlsanity.com/paper/2210.11222/) (2022)
- [DP-XGBoost: Private Machine Learning at Scale](https://mlsanity.com/paper/2110.12770/) (2021)
- [Private Statistical Estimation of Many Quantiles](https://mlsanity.com/paper/2302.06943/) (2023)
- [Towards Biologically Plausible and Private Gene Expression Data Generation](https://mlsanity.com/paper/2402.04912/) (2024)
- [Federated Learning of Quantile Inference under Local Differential Privacy](https://mlsanity.com/paper/2509.21800/) (2025)
- [How Much is Left? LLMs Linearly Encode Their Remaining Output Length](https://mlsanity.com/paper/2607.05316/) (2026)
- [Differentially-Private Decision Trees and Provable Robustness to Data Poisoning](https://mlsanity.com/paper/2305.15394/) (2023)
- [Differentially Private Nonparametric Confidence Intervals Under Minimal Distributional Assumptions](https://mlsanity.com/paper/2511.01303/) (2025)
- [Differentially Private Maximal Information Coefficients](https://mlsanity.com/paper/2206.10685/) (2022)
- [DPpack: An R Package for Differentially Private Statistical Analysis and Machine Learning](https://mlsanity.com/paper/2309.10965/) (2023)
- [DPSW-Sketch: A Differentially Private Sketch Framework for Frequency Estimation over Sliding Windows (Technical Report)](https://mlsanity.com/paper/2406.07953/) (2024)
- [End to End Collaborative Synthetic Data Generation](https://mlsanity.com/paper/2412.03766/) (2024)
- [Federated Computation of ROC and PR Curves](https://mlsanity.com/paper/2510.04979/) (2025)
- [The Privacy Price of Tail-Risk Learning: Effective Tail Sample Size in Differentially Private CVaR Optimization](https://mlsanity.com/paper/2605.16219/) (2026)
- [Workload-Preserving Differentially Private Synthetic Data for Causal Inference via Maximum-Entropy Calibration](https://mlsanity.com/paper/2607.08122/) (2026)
- [FinancialAuditBench: Benchmark Construction under Differential Privacy Using Real-World Priors](https://mlsanity.com/paper/2609.32835/) (2026)
- [Tight End-to-End Accounting for Differentially Private Synthetic Data](https://mlsanity.com/paper/2610.17249/) (2026)

## Abstract (arXiv)

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(mnlog(n) + m2n). 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.