Private Mean Estimation of Heavy-Tailed Distributions

Abstract

We give new upper and lower bounds on the minimax sample complexity of differentially private mean estimation of distributions with bounded $k$-th moments. Roughly speaking, in the univariate case, we show that $n=\Theta \left(\frac{1}{{\alpha }^2}+\frac{1}{{\alpha }^{\frac{k}{k-1}}\epsilon }\right)$ samples are necessary and sufficient to estimate the mean to $\alpha$-accuracy under $\epsilon$-differential privacy, or any of its common relaxations. This result demonstrates a qualitatively different behavior compared to estimation absent privacy constraints, for which the sample complexity is identical for all $k\ge 2$. We also give algorithms for the multivariate setting whose sample complexity is a factor of $O(d)$ larger than the univariate case.

arXiv commentAppeared in COLT 2020

References in corpus (10)

• Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians
• Privacy and Statistical Risk: Formalisms and Minimax Bounds
• The Cost of Privacy: Rates of Convergence for Parameter Estimation with Differential Privacy
• Differentially Private Confidence Intervals
• Generalized Resilience and Robust Statistics
• CoinPress: Practical Private Mean and Covariance Estimation
• Differentially Private Testing of Identity and Closeness of Discrete Distributions
• A Primer on Private Statistics
• Density estimation in linear time
• The Optimal Approximation Factor in Density Estimation

Cited by in corpus (14)

• Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism
• Enabling Fast Differentially Private SGD via Just-in-Time Compilation and Vectorization
• Learning discrete distributions: user vs item-level privacy
• Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data
• Robust and Differentially Private Mean Estimation
• Covariance-Aware Private Mean Estimation Without Private Covariance Estimation
• Pufferfish Privacy: An Information-Theoretic Study
• Differentially Private Assouad, Fano, and Le Cam
• Differential privacy and robust statistics in high dimensions
• Optimal Private Median Estimation under Minimal Distributional Assumptions
• High-Dimensional Differentially-Private EM Algorithm: Methods and Near-Optimal Statistical Guarantees
• Learning with User-Level Privacy
• Universal Private Estimators
• Selective MPC: Distributed Computation of Differentially Private Key-Value Statistics