Federated Heavy Hitters Discovery with Differential Privacy
summary
Federated algorithm builds a prefix tree by sampling M = M = γ√n devices each round, having each sampled device cast a single-character vote, and pruning prefixes whose counts fall below a threshold θ ≈ log n. Running L rounds (L = max word length) yields an (ε,δ)-DP guarantee (δ ≈ 1/n for θ ~ log n) while keeping utility: on Sentiment140 single-digit ε recovers the top ~350 words (recall 1 for top ~350 words). Implements secure aggregation / shufflers and proposes threshold crypto; compares favorably to local DP baselines (local DP recall ~0.86, precision ~0.2).
AI-written summary · about
chapters (14)
- 0:00Introduction
- 0:37Federated Learning
- 4:11Multiparty Computation
- 9:25Open Research
- 12:23Applications
- 12:48Differential Privacy
- 15:15Two Models
- 17:23Four Essential Ingredients
- 21:23The Algorithm
- 25:08Algorithm Parameters
- 26:43Results
- 31:26Tradeoffs
- 33:19Deltas
- 35:05Comparison
related talks
37mUser-level and federated local differential privacy
34mEfficient Robust Private Aggregation for DP
01h 14mStatistical Inference and Privacy, Part III
28mPrivacy versus Robustness in Federated Learning: Limits and Algorithms
16mDP-BREM: Differentially-Private and Byzantine-Robust Federated Learning...
55mFederated, Synthetic, Personalized: Heterogeneity Here or There?
15mDifferentially Private Algorithms for 2020 Decennial Census Detailed DHC Race & Ethnicity
44mPersonalized Federated Training of Diffusion Models with Privacy Guarantees