# Differentially Private Medians and Interior Points for Non-Pathological Data

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 18 references that are in the map.
- First posted on arXiv 22 May 2023.

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

- [Finite Sample Differentially Private Confidence Intervals](https://mlsanity.com/paper/1711.03908/) (2017)
- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [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)
- [Smoothed Analysis of Online and Differentially Private Learning](https://mlsanity.com/paper/2006.10129/) (2020)
- [Privately Learning Thresholds: Closing the Exponential Gap](https://mlsanity.com/paper/1911.10137/) (2019)
- [Near Instance-Optimality in Differential Privacy](https://mlsanity.com/paper/2005.10630/) (2020)
- [~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization](https://mlsanity.com/paper/2211.06387/) (2022)
- [Propose, Test, Release: Differentially private estimation with high probability](https://mlsanity.com/paper/2002.08774/) (2020)
- [Private Center Points and Learning of Halfspaces](https://mlsanity.com/paper/1902.10731/) (2019)
- [Optimal Private Median Estimation under Minimal Distributional Assumptions](https://mlsanity.com/paper/2011.06202/) (2020)

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

- [Private Geometric Median](https://mlsanity.com/paper/2406.07407/) (2024)
- [Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings](https://mlsanity.com/paper/2510.00574/) (2025)

## Abstract (arXiv)

We construct differentially private estimators with low sample complexity that estimate the median of an arbitrary distribution over ℝ satisfying very mild moment conditions. Our result stands in contrast to the surprising negative result of Bun et al. (FOCS 2015) that showed there is no differentially private estimator with any finite sample complexity that returns any non-trivial approximation to the median of an arbitrary distribution.