mlsanityData to 7 Oct 2026

Differentially Private Medians and Interior Points for Non-Pathological Data

arXiv 2305.13440 ↗First posted 22 May 2023cs.DS cs.LGcited by 2

Not on the map. Why?

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.

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

Builds on

11 of 18 references.

References · 11

  1. 2017Finite Sample Differentially Private Confidence Intervalscited by 103
  2. 2018Private PAC learning implies finite Littlestone dimensioncited by 73
  3. 2014Private Learning and Sanitization: Pure vs. Approximate Differential Privacycited by 62
  4. 2015Differentially Private Release and Learning of Threshold Functionscited by 58
  5. 2020Smoothed Analysis of Online and Differentially Private Learningcited by 47
  6. 2019Privately Learning Thresholds: Closing the Exponential Gapcited by 30
  7. 2020Near Instance-Optimality in Differential Privacycited by 23
  8. 2022~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimizationcited by 16
  9. 2020Propose, Test, Release: Differentially private estimation with high probabilitycited by 15
  10. 2019Private Center Points and Learning of Halfspacescited by 13
  11. 2020Optimal Private Median Estimation under Minimal Distributional Assumptionscited by 13

Built on by

Cited by year

Citing papers per year: 2024: 1; 2025: 1.

2 papers.

  1. 2024Private Geometric Mediancited by 3
  2. 2025Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settingscited by 1