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

This paradigm provides a rigorous mathematical framework for the study and design of privacy-preserving algorithms. This setting assumes that there is a trusted curator that holds data containing some possibly sensitive records of n individuals. The goal of differential privacy is to simultaneously protect every individual record while releasing global characteristics of the database [14]. This is achieved by constructing randomized algorithms that release noisy versions of the desired outputs, where the noise level is calibrated to prevent any individual level data to be identifiable by querying the database. Even though the machine learning community has been very prolific in developing differentially private algorithms for complex settings including multiarmed bandit problems [23, 26, 30], high-dimensional regression [18, 29] and deep learning [1, 19], some fundamental statistical questions are only starting to be understood. For example, the first statistical minimax rates of convergence under differential privacy were recently established in [7,11]. Some earlier work framing differential privacy in traditional statistics terms include [9, 17, 20, 28, 31].