Propose, Test, Release: Differentially private estimation with high probability
Preprint
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.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Privacy-Preserving Parametric Inference: A Case for Robust StatisticsJournal of the American Statistical Association, 2020
- Certified Robustness to Adversarial Examples with Differential Privacy2019
- Distributed statistical estimation and rates of convergence in normal approximationElectronic Journal of Statistics, 2019
- Inference using noisy degrees: Differentially private $\beta$-model and synthetic graphsThe Annals of Statistics, 2016
- Bandits With Heavy TailIEEE Transactions on Information Theory, 2013
- The Algorithmic Foundations of Differential Privacy2013
- A Statistical Framework for Differential PrivacyJournal of the American Statistical Association, 2010
- Differential privacy and robust statistics2009
- Problem Complexity and Method Efficiency in OptimizationJournal of the Operational Research Society, 1984