# Non-parametric Differentially Private Confidence Intervals for the Median

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 56 references that are in the map.
- First posted on arXiv 18 Jun 2021.

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

- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [Finite Sample Differentially Private Confidence Intervals](https://mlsanity.com/paper/1711.03908/) (2017)
- [CoinPress: Practical Private Mean and Covariance Estimation](https://mlsanity.com/paper/2006.06618/) (2020)
- [Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo](https://mlsanity.com/paper/1502.07645/) (2015)
- [Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain](https://mlsanity.com/paper/1803.02596/) (2018)
- [Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation](https://mlsanity.com/paper/1906.02830/) (2019)
- [On the Theory and Practice of Privacy-Preserving Bayesian Data Analysis](https://mlsanity.com/paper/1603.07294/) (2016)
- [Differentially Private Simple Linear Regression](https://mlsanity.com/paper/2007.05157/) (2020)
- [Differentially Private Chi-Squared Hypothesis Testing: Goodness of Fit and Independence Testing](https://mlsanity.com/paper/1602.03090/) (2016)
- [Differentially Private Bayesian Linear Regression](https://mlsanity.com/paper/1910.13153/) (2019)
- [Differentially Private Quantiles](https://mlsanity.com/paper/2102.08244/) (2021)
- [Differentially Private Confidence Intervals](https://mlsanity.com/paper/2001.02285/) (2020)
- [Bayesian Differential Privacy through Posterior Sampling](https://mlsanity.com/paper/1306.1066/) (2013)
- [Differentially Private Bayesian Inference for Exponential Families](https://mlsanity.com/paper/1809.02188/) (2018)
- [Locally Private Mean Estimation: Z-test and Tight Confidence Intervals](https://mlsanity.com/paper/1810.08054/) (2018)
- [Propose, Test, Release: Differentially private estimation with high probability](https://mlsanity.com/paper/2002.08774/) (2020)
- [Optimal Private Median Estimation under Minimal Distributional Assumptions](https://mlsanity.com/paper/2011.06202/) (2020)
- [Differentially private significance tests for regression coefficients](https://mlsanity.com/paper/1705.09561/) (2017)
- [Differentially Private Nonparametric Hypothesis Testing](https://mlsanity.com/paper/1903.09364/) (2019)
- [Differentially Private Bayesian Learning on Distributed Data](https://mlsanity.com/paper/1703.01106/) (2017)
- [Differential Privacy for Government Agencies -- Are We There Yet?](https://mlsanity.com/paper/2102.08847/) (2021)
- [Revisiting Differentially Private Hypothesis Tests for Categorical Data](https://mlsanity.com/paper/1511.03376/) (2015)

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

- [Differentially Private Bootstrap: New Privacy Analysis and Inference Strategies](https://mlsanity.com/paper/2210.06140/) (2022)
- [Nonparametric extensions of randomized response for private confidence sets](https://mlsanity.com/paper/2202.08728/) (2022)
- [Resampling methods for private statistical inference](https://mlsanity.com/paper/2402.07131/) (2024)
- [Private Statistical Estimation of Many Quantiles](https://mlsanity.com/paper/2302.06943/) (2023)
- [Privately Estimating Black-Box Statistics](https://mlsanity.com/paper/2510.00322/) (2025)
- [Differentially Private Nonparametric Confidence Intervals Under Minimal Distributional Assumptions](https://mlsanity.com/paper/2511.01303/) (2025)
- [Near-Optimal Private Tests for Simple and MLR Hypotheses](https://mlsanity.com/paper/2601.21959/) (2026)

## Abstract (arXiv)

Differential privacy is a restriction on data processing algorithms that provides strong confidentiality guarantees for individual records in the data. However, research on proper statistical inference, that is, research on properly quantifying the uncertainty of the (noisy) sample estimate regarding the true value in the population, is currently still limited. This paper proposes and evaluates several strategies to compute valid differentially private confidence intervals for the median. Instead of computing a differentially private point estimate and deriving its uncertainty, we directly estimate the interval bounds and discuss why this approach is superior if ensuring privacy is important. We also illustrate that addressing both sources of uncertainty--the error from sampling and the error from protecting the output--simultaneously should be preferred over simpler approaches that incorporate the uncertainty in a sequential fashion. We evaluate the performance of the different algorithms under various parameter settings in extensive simulation studies and demonstrate how the findings could be applied in practical settings using data from the 1940 Decennial Census.