Differentially Private Medians and Interior Points for Non-Pathological Data

Maryam Aliakbarpour, Rose Silver, Thomas Steinke, Jonathan Ullman
5/22/2023
cs.DScs.LG

No confident code implementation found for this paper.

Abstract

We construct differentially private estimators with low sample complexity that estimate the median of an arbitrary distribution over $\mathbb{R}$ 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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Private Mean Estimation with Person-Level Differential Privacy

82% match2024

Differentially Private Multi-Sampling from Distributions

81% match2024

Private Geometric Median

80% match2024

Differentially Private Sliced Inverse Regression: Minimax Optimality and Algorithm

80% match2024

Differential privacy with dependent data

79% match2025

Resampling methods for private statistical inference

79% match2024

Cite this paper

@article{aliakbarpour2023differentially,
  title  = {Differentially Private Medians and Interior Points for Non-Pathological Data},
  author = {Maryam Aliakbarpour and Rose Silver and Thomas Steinke and Jonathan Ullman},
  year   = {2023},
  eprint = {2305.13440},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2305.13440v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2305.13440.svg)](https://codeofpaper.com/paper/2305.13440)

Discussion