Local Privacy, Data Processing Inequalities, and Statistical Minimax Rates
This work addresses privacy-preserving statistical estimation for data analysts, providing foundational results that are not incremental but establish optimal rates.
The paper tackles the tradeoff between privacy guarantees and statistical utility under local privacy constraints, deriving matching lower and upper bounds for problems like mean estimation and density estimation, with optimal mechanisms achieving these bounds.
Working under a model of privacy in which data remains private even from the statistician, we study the tradeoff between privacy guarantees and the utility of the resulting statistical estimators. We prove bounds on information-theoretic quantities, including mutual information and Kullback-Leibler divergence, that depend on the privacy guarantees. When combined with standard minimax techniques, including the Le Cam, Fano, and Assouad methods, these inequalities allow for a precise characterization of statistical rates under local privacy constraints. We provide a treatment of several canonical families of problems: mean estimation, parameter estimation in fixed-design regression, multinomial probability estimation, and nonparametric density estimation. For all of these families, we provide lower and upper bounds that match up to constant factors, and exhibit new (optimal) privacy-preserving mechanisms and computationally efficient estimators that achieve the bounds.