Differential Privacy and Robust Statistics

Proceedings of the 41th Annual ACM Symposium on Theory of Computing (STOC) |

Published by Association for Computing Machinery, Inc.

We show by means of several examples that robust statistical estimators present an excellent starting point for differentially private estimators. Our algorithms use a new paradigm for differentially private mechanisms, which we call Propose-Test-Release (PTR), and for which we give a formal definition and general composition theorems.