Differentially Private Assouad, Fano, and Le Cam

Abstract

Le Cam's method, Fano's inequality, and Assouad's lemma are three widely used techniques to prove lower bounds for statistical estimation tasks. We propose their analogues under central differential privacy. Our results are simple, easy to apply and we use them to establish sample complexity bounds in several estimation tasks. We establish the optimal sample complexity of discrete distribution estimation under total variation distance and ${\ell }_2$ distance. We also provide lower bounds for several other distribution classes, including product distributions and Gaussian mixtures that are tight up to logarithmic factors. The technical component of our paper relates coupling between distributions to the sample complexity of estimation under differential privacy.

References in corpus (9)

• Discrete Distribution Estimation under Local Privacy
• Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication
• Mutual Information Optimally Local Private Discrete Distribution Estimation
• Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians
• The Cost of Privacy: Rates of Convergence for Parameter Estimation with Differential Privacy
• Test without Trust: Optimal Locally Private Distribution Testing
• Private Mean Estimation of Heavy-Tailed Distributions
• Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters
• Differentially Private Testing of Identity and Closeness of Discrete Distributions

Cited by in corpus (6)

• CoinPress: Practical Private Mean and Covariance Estimation
• A Primer on Private Statistics
• Learning discrete distributions: user vs item-level privacy
• On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians
• Privately Learning Markov Random Fields
• Privately Learning Mixtures of Axis-Aligned Gaussians