Dimension-free Private Mean Estimation for Anisotropic Distributions
summary
Provides an (ε,δ)-DP estimator that achieves Euclidean error ≤α with sample complexity n ≳ tr(Σ)/α^2 + tr(Σ^{1/2})/(αε), and proves that bound is optimal up to logs; algorithm uses a FriendlyCore-based pre-check and Gaussian noise scaled to a dampened version of Σ rather than isotropic noise; for unknown covariance gives methods that replace the prior √d privacy cost by a d^{1/4} improvement in structured cases and learns k variances privately at cost ≈√k/ε.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 1:03Problem setup
- 2:06Private mean estimation
- 4:36Anisotropic covariance
- 8:16Covariance-dependent error
- 10:03Known covariance solution
- 12:56FriendlyCore algorithm
- 14:52Unknown covariance challenges
- 17:25Diagonal covariance case
- 18:29Adaptive decentralized estimators
- 21:22Q&A
related talks
36mPrivately Learning High-Dimensional Distributions
01h 02mLarge-Scale Private Learning, Part I
53mOptimality in Locally Private Estimation and Learning
17mData privacy and reliable learning
09mFrom Robustness to Privacy and Back
40mDifferential Privacy with Elliptical Stochastic Processes
37mUser-level and federated local differential privacy
01h 14mTutorial: Privacy, Part II