Large-Scale Private Learning, Part III
summary
Defines and contrasts local differential privacy vs central: accuracy degrades — sum estimation error grows roughly like sqrt(n)/epsilon rather than depending only on epsilon — proved by anticoncentration/Berry‑Esseen. Uses classic randomized response and a one‑row-per‑client adaptation of the count‑min sketch to recover heavy hitters via prefix expansion. Shows a noninteractive, cohorted randomized‑response protocol that approximates the median (avoiding many rounds). Notes an implemented system (RAPPOR) and pushes that Chrome, Apple and Microsoft adopt LDP for telemetry.
AI-written summary · about
chapters (13)
- 0:00Start
- 0:44Central Differential Privacy
- 5:21Q1: Are you a citizen of the United States? Q2: Are you not a citizen of the United States?
- 22:52Learning population mean
- 27:56LDP Heavy Hitters
- 28:37The Heavy Hitters Problem
- 30:13Non-private Frequency Oracle
- 39:23Unknown Unknowns: Private Heavy Hitters Without the Dictionary
- 41:17Convex Optimization
- 45:44Learning the Median: Binary Search
- 47:10Learning the Median Non-Interactively
- 52:40Google Chrome Privacy Whitepaper
- 56:35Google Chrome Privacy White Paper
related talks
37mUser-level and federated local differential privacy
17mData privacy and reliable learning
01h 00mDifferential Privacy: Fundamentals to Forefront I
30mAccuracy First: Selecting a Differential Privacy Level for Accuracy-Constrained...
44mLocally Private Statistical Inference: Communication, Samples, and Shared Randomness
01h 14mTutorial: Privacy, Part II
32mYou've got trust issues, we've got solutions: Differential Privacy
26mAaron Roth, Associate Professor, University of Pennsylvania, NYC 2017