Large-Scale Private Learning, Part I
summary
Covers concrete mechanisms and bounds: the Gaussian mechanism adds N(0,σ^2) with σ = Θ(√(ln(1/δ))/ε) to any ℓ2‑sensitive query, privacy tracked via the privacy‑loss random variable, and k‑fold adaptive composition blows up ε only as ε0·√(O(k ln(1/δ))). Gives a usable private PCA recipe: add symmetric Gaussian noise to the covariance, then take top‑k eigenvectors, yielding an additive utility loss ≈ O(k·√d) (provably unavoidable in general). States ERM excess risk ≈ (1/ε)·√(d/n). Demo of Google’s open‑source DP ML library is planned.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 1:55Outline
- 2:53Differential Privacy
- 4:48Privacy Lost Random
- 10:08Differential Privacy Definition
- 12:58Gaussian Mechanism
- 14:12Theorem
- 19:30Tail Bound
- 31:06Basic Composition Theorem
- 36:14Principal Components Analysis
- 42:36Algorithm
- 44:50Optimization
- 53:48Desiderata
related talks
36mPrivately Learning High-Dimensional Distributions
17mData privacy and reliable learning
26mAlgorithms with More Granular Differential Privacy Guarantees
21mDimension-free Private Mean Estimation for Anisotropic Distributions
01h 14mTutorial: Privacy, Part II
43mIs Interaction Necessary for Distributed Private Learning?
51mPrivate Boosting and Noise-tolerant Learning
33mPrivacy of Decentralized Machine Learning