Privately Learning High-Dimensional Distributions
Talkat Data Privacy: From Foundations to Applications (Simons Institute workshop, 2019) · 2019-03-04..03-08·
summary
Claims a private algorithm that learns d‑dimensional Gaussians in total variation with sample complexity near d^2/α^2 plus d^2/(αε) and an extra d^{3/2}·polylog(κ)/ε term, focusing on zero mean covariance estimation. Core tools are truncation/Windsorizing to bound sensitivity, the Gaussian mechanism on empirical covariances, and a private preconditioner that makes the covariance roughly isotropic to reduce condition number; the method is constructive and matches several lower bounds.
AI-written summary · about
chapters (18)
- 0:00Intro
- 1:25Algorithms vs. Statistics
- 2:20Privacy in Statistics
- 4:34An Example
- 9:56Background: Univariate Private Statistics
- 11:40Results: Multivariate Private Statistics
- 17:47Today's talk: Gaussian Covariance Estimation
- 18:24Learning a Multivariate Gaussian
- 19:43Non-Private Covariance Estimation
- 20:21Recap: Gaussian Mechanism
- 21:58Private Covariance Estimation: Take 1
- 22:25Sensitivity of Empirical Covariance
- 23:44Limiting Sensitivity via Truncation
- 24:18Private Covariance Estimation: Take 2
- 26:59What Went Wrong?
- 28:20Private Recursive Preconditioning
- 29:15Preconditioning: An Illustration
- 29:49Private Covariance Estimation: Take 3
related talks
01h 02mLarge-Scale Private Learning, Part I
21mDimension-free Private Mean Estimation for Anisotropic Distributions
39mAbove Average-Case Analysis?
01h 00mAlgorithmic High Dimensional Robust Statistics I
01h 07mRecent Progress in High-Dimensional Learning
01h 30mAnalytic Methods for Supervised Learning IV
48mComputational-Statistical Tradeoffs in Robust High-Dimensional Estimation
53mDesigning Robust Learners