# Private Quantiles Estimation in the Presence of Atoms

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 48 references that are in the map.
- First posted on arXiv 15 Feb 2022.

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [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)
- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Winning the NIST Contest: A scalable and general approach to differentially private synthetic data](https://mlsanity.com/paper/2108.04978/) (2021)
- [Differentially Private SQL with Bounded User Contribution](https://mlsanity.com/paper/1909.01917/) (2019)
- [Near Instance-Optimality in Differential Privacy](https://mlsanity.com/paper/2005.10630/) (2020)
- [Differentially Private Quantiles](https://mlsanity.com/paper/2102.08244/) (2021)
- [Propose, Test, Release: Differentially private estimation with high probability](https://mlsanity.com/paper/2002.08774/) (2020)
- [Differentially Private Approximate Quantiles](https://mlsanity.com/paper/2110.05429/) (2021)
- [Technical Privacy Metrics: a Systematic Survey](https://mlsanity.com/paper/1512.00327/) (2015)
- [Chorus: a Programming Framework for Building Scalable Differential Privacy Mechanisms](https://mlsanity.com/paper/1809.07750/) (2018)

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

- [On the Statistical Complexity of Estimation and Testing under Privacy Constraints](https://mlsanity.com/paper/2210.02215/) (2022)
- [Private Statistical Estimation of Many Quantiles](https://mlsanity.com/paper/2302.06943/) (2023)
- [Differentially private multivariate medians](https://mlsanity.com/paper/2210.06459/) (2022)
- [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)

## Abstract (arXiv)

We consider the differentially private estimation of multiple quantiles (MQ) of a distribution from a dataset, a key building block in modern data analysis. We apply the recent non-smoothed Inverse Sensitivity (IS) mechanism to this specific problem. We establish that the resulting method is closely related to the recently published ad hoc algorithm JointExp. In particular, they share the same computational complexity and a similar efficiency. We prove the statistical consistency of these two algorithms for continuous distributions. Furthermore, we demonstrate both theoretically and empirically that this method suffers from an important lack of performance in the case of peaked distributions, which can degrade up to a potentially catastrophic impact in the presence of atoms. Its smoothed version (i.e. by applying a max kernel to its output density) would solve this problem, but remains an open challenge to implement. As a proxy, we propose a simple and numerically efficient method called Heuristically Smoothed JointExp (HSJointExp), which is endowed with performance guarantees for a broad class of distributions and achieves results that are orders of magnitude better on problematic datasets.