# Propose, Test, Release: Differentially private estimation with high probability

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2020.

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

- [Differential privacy and robust statistics in high dimensions](https://mlsanity.com/paper/2111.06578/) (2021)
- [High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2107.11136/) (2021)
- [From Robustness to Privacy and Back](https://mlsanity.com/paper/2302.01855/) (2023)
- [Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits](https://mlsanity.com/paper/2106.02575/) (2021)
- [Non-parametric Differentially Private Confidence Intervals for the Median](https://mlsanity.com/paper/2106.10333/) (2021)
- [Private Quantiles Estimation in the Presence of Atoms](https://mlsanity.com/paper/2202.08969/) (2022)
- [Renyi Differential Privacy of Propose-Test-Release and Applications to Private and Robust Machine Learning](https://mlsanity.com/paper/2209.07716/) (2022)
- [Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewards](https://mlsanity.com/paper/2306.01121/) (2023)
- [Subset-Based Instance Optimality in Private Estimation](https://mlsanity.com/paper/2303.01262/) (2023)
- [Differentially private projection-depth-based medians](https://mlsanity.com/paper/2312.07792/) (2023)
- [Differentially private multivariate medians](https://mlsanity.com/paper/2210.06459/) (2022)
- [Differentially Private Medians and Interior Points for Non-Pathological Data](https://mlsanity.com/paper/2305.13440/) (2023)
- [Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Condition](https://mlsanity.com/paper/2509.04668/) (2025)
- [The Relative Gaussian Mechanism and its Application to Private Gradient Descent](https://mlsanity.com/paper/2308.15250/) (2023)
- [Privately Estimating Black-Box Statistics](https://mlsanity.com/paper/2510.00322/) (2025)

## Abstract (arXiv)

We derive concentration inequalities for differentially private median and mean estimators building on the "Propose, Test, Release" (PTR) mechanism introduced by Dwork and Lei (2009). We introduce a new general version of the PTR mechanism that allows us to derive high probability error bounds for differentially private estimators. Our algorithms provide the first statistical guarantees for differentially private estimation of the median and mean without any boundedness assumptions on the data, and without assuming that the target population parameter lies in some known bounded interval. Our procedures do not rely on any truncation of the data and provide the first sub-Gaussian high probability bounds for differentially private median and mean estimation, for possibly heavy tailed random variables.