Local Privacy, Data Processing Inequalities, and Statistical Minimax Rates

Abstract

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.

59 pages, 3 figures

References in corpus (2)

• Convergence Rates for Differentially Private Statistical Estimation
• Optimal rates for zero-order convex optimization: the power of two function evaluations

Cited by in corpus (16)

• Protection Against Reconstruction and Its Applications in Private Federated Learning
• Discrete Distribution Estimation under Local Privacy
• A Comprehensive Survey on Local Differential Privacy Toward Data Statistics and Analysis
• Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation
• Privacy Aware Learning
• Optimality guarantees for distributed statistical estimation
• Differentially Private Federated Learning on Heterogeneous Data
• Helen: Maliciously Secure Coopetitive Learning for Linear Models
• Is Private Learning Possible with Instance Encoding?
• Learning in the Presence of Corruption
• Privacy-preserving Stochastic Gradual Learning
• Local Differential Privacy for Regret Minimization in Reinforcement Learning
• Locally private online change point detection
• Improving Frequency Estimation under Local Differential Privacy
• A Minimax Distortion View of Differentially Private Query Release
• Time Complexity Analysis of a Distributed Stochastic Optimization in a Non-Stationary Environment