Differentially Private Continual Releases of Streaming Frequency Moment Estimations
summary
A differentially private streaming algorithm estimates Lp frequency moments over T rounds with 0.9 probability and gives explicit multiplicative and additive error bounds while using O(log T) words of space. Construction combines the binary tree mechanism (additive noise with O(log T) error), a new private grouping scheme (multiplicative error, smaller space), sampling+hashing for large universes, CountSketch for heavy hitters, and conversion to sliding-window via smooth histogram.
AI-written summary · about
chapters (12)
- 0:00Intro
- 0:24Motivation
- 1:44Model
- 4:20Main result
- 5:26Binary Tree Mechanism [2, 3]
- 6:52Grouping
- 8:52Distinct Elements (small universe)
- 10:31Distinct Elements (large universe)
- 11:50General Frequency Moment Estimation: Low Frequency
- 13:25General Frequency Moment Estimation: High Frequency
- 15:18Putting things together
- 16:24Continual Release → Sliding Window
related talks
01h 03mAdversarially Robust Streaming Algorithms
24mLocally Differentially Private Protocols for Frequency Estimation
58mLarge-Scale Private Learning, Part III
01h 00mDifferential Privacy: Fundamentals to Forefront I
43mDifferential Privacy Meets Robust Statistics
16mHow to Break, Then Fix, Differential Privacy on Finite Computers
27mImproved Frequency Estimation Algorithms with and without Predictions
32mYou've got trust issues, we've got solutions: Differential Privacy