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

Abstract

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.

arXiv admin note: text overlap with arXiv:1906.11923

References in corpus (3)

• Deep Learning with Differential Privacy
• Robust empirical mean Estimators
• The Cost of Privacy: Rates of Convergence for Parameter Estimation with Differential Privacy

Cited by in corpus (7)

• Differential privacy and robust statistics in high dimensions
• Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits
• Differentially Private (Gradient) Expectation Maximization Algorithm with Statistical Guarantees
• Optimal Private Median Estimation under Minimal Distributional Assumptions
• Differentially private depth functions and their associated medians
• Duff: A Dataset-Distance-Based Utility Function Family for the Exponential Mechanism
• The Relative Gaussian Mechanism and its Application to Private Gradient Descent