# Private Statistical Estimation of Many Quantiles

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 64 references that are in the map.
- First posted on arXiv 14 Feb 2023.

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Differentially Private Release and Learning of Threshold Functions](https://mlsanity.com/paper/1504.07553/) (2015)
- [Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams](https://mlsanity.com/paper/2202.08312/) (2022)
- [Differentially Private Assouad, Fano, and Le Cam](https://mlsanity.com/paper/2004.06830/) (2020)
- [Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data](https://mlsanity.com/paper/2106.01336/) (2021)
- [Privately Learning Thresholds: Closing the Exponential Gap](https://mlsanity.com/paper/1911.10137/) (2019)
- [Local Privacy, Data Processing Inequalities, and Statistical Minimax Rates](https://mlsanity.com/paper/1302.3203/) (2013)
- [Differentially Private Testing of Identity and Closeness of Discrete Distributions](https://mlsanity.com/paper/1707.05128/) (2017)
- [Near Instance-Optimality in Differential Privacy](https://mlsanity.com/paper/2005.10630/) (2020)
- [Differentially Private Quantiles](https://mlsanity.com/paper/2102.08244/) (2021)
- [Fisher information under local differential privacy](https://mlsanity.com/paper/2005.10783/) (2020)
- [Unified lower bounds for interactive high-dimensional estimation under information constraints](https://mlsanity.com/paper/2010.06562/) (2020)
- [Local differential privacy: Elbow effect in optimal density estimation and adaptation over Besov ellipsoids](https://mlsanity.com/paper/1903.01927/) (2019)
- [Inference under Information Constraints III: Local Privacy Constraints](https://mlsanity.com/paper/2101.07981/) (2021)
- [Differentially Private Approximate Quantiles](https://mlsanity.com/paper/2110.05429/) (2021)
- [Classification under local differential privacy](https://mlsanity.com/paper/1912.04629/) (2019)
- [Optimal Rates for Nonparametric Density Estimation under Communication Constraints](https://mlsanity.com/paper/2107.10078/) (2021)
- [Information-constrained optimization: can adaptive processing of gradients help?](https://mlsanity.com/paper/2104.00979/) (2021)
- [Bounded Space Differentially Private Quantiles](https://mlsanity.com/paper/2201.03380/) (2022)
- [Non-parametric Differentially Private Confidence Intervals for the Median](https://mlsanity.com/paper/2106.10333/) (2021)
- [On the Statistical Complexity of Estimation and Testing under Privacy Constraints](https://mlsanity.com/paper/2210.02215/) (2022)
- [Private Quantiles Estimation in the Presence of Atoms](https://mlsanity.com/paper/2202.08969/) (2022)

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

- [About the Cost of Central Privacy in Density Estimation](https://mlsanity.com/paper/2306.14535/) (2023)
- [Learning with Differentially Private (Sliced) Wasserstein Gradients](https://mlsanity.com/paper/2502.01701/) (2025)
- [How Much is Left? LLMs Linearly Encode Their Remaining Output Length](https://mlsanity.com/paper/2607.05316/) (2026)

## Abstract (arXiv)

This work studies the estimation of many statistical quantiles under differential privacy. More precisely, given a distribution and access to i.i.d. samples from it, we study the estimation of the inverse of its cumulative distribution function (the quantile function) at specific points. For instance, this task is of key importance in private data generation. We present two different approaches. The first one consists in privately estimating the empirical quantiles of the samples and using this result as an estimator of the quantiles of the distribution. In particular, we study the statistical properties of the recently published algorithm introduced by Kaplan et al. 2022 that privately estimates the quantiles recursively. The second approach is to use techniques of density estimation in order to uniformly estimate the quantile function on an interval. In particular, we show that there is a tradeoff between the two methods. When we want to estimate many quantiles, it is better to estimate the density rather than estimating the quantile function at specific points.