# Differentially Private Approximate Quantiles

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 19 references that are in the map.
- First posted on arXiv 11 Oct 2021.

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

- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Private Learning and Sanitization: Pure vs. Approximate Differential Privacy](https://mlsanity.com/paper/1407.2674/) (2014)
- [Differentially Private Release and Learning of Threshold Functions](https://mlsanity.com/paper/1504.07553/) (2015)
- [Privately Learning Thresholds: Closing the Exponential Gap](https://mlsanity.com/paper/1911.10137/) (2019)
- [Differentially Private Quantiles](https://mlsanity.com/paper/2102.08244/) (2021)

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

- [Unbounded Differentially Private Quantile and Maximum Estimation](https://mlsanity.com/paper/2305.01177/) (2023)
- [PLAN: Variance-Aware Private Mean Estimation](https://mlsanity.com/paper/2306.08745/) (2023)
- [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)
- [Private Statistical Estimation of Many Quantiles](https://mlsanity.com/paper/2302.06943/) (2023)
- [How Much is Left? LLMs Linearly Encode Their Remaining Output Length](https://mlsanity.com/paper/2607.05316/) (2026)
- [Differentially Private Nonparametric Confidence Intervals Under Minimal Distributional Assumptions](https://mlsanity.com/paper/2511.01303/) (2025)
- [End to End Collaborative Synthetic Data Generation](https://mlsanity.com/paper/2412.03766/) (2024)
- [DPrivBench: Benchmarking LLMs' Reasoning for Differential Privacy](https://mlsanity.com/paper/2604.15851/) (2026)
- [Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees](https://mlsanity.com/paper/2605.22756/) (2026)
- [Workload-Preserving Differentially Private Synthetic Data for Causal Inference via Maximum-Entropy Calibration](https://mlsanity.com/paper/2607.08122/) (2026)
- [Tight End-to-End Accounting for Differentially Private Synthetic Data](https://mlsanity.com/paper/2610.17249/) (2026)

## Abstract (arXiv)

In this work we study the problem of differentially private (DP) quantiles, in which given dataset X and quantiles q1, ..., qm ∈ [0,1], we want to output m quantile estimations which are as close as possible to the true quantiles and preserve DP. We describe a simple recursive DP algorithm, which we call ApproximateQuantiles (AQ), for this task. We give a worst case upper bound on its error, and show that its error is much lower than of previous implementations on several different datasets. Furthermore, it gets this low error while running time two orders of magnitude faster that the best previous implementation.