Large Scale Private Learning on Data Streams, and the BLTs
summary
Introduces a streaming noise construction that produces the correlated Gaussian noise for DP-FTRL with a buffer cost of about log^2(training steps)×dimensions, avoiding pregenerating an n×d noise matrix; utility matches any lower-triangular Toeplitz factorization up to an additive constant, so accuracy stays near optimal. Construction encodes Toeplitz square roots as Buffered Linear Toeplitz (BLT) operators realized via rational function approximation and constant recurrence sequences, yields polylog space and shows empirically that a handful of buffers suffices though numerical stability near poles needs care.
AI-written summary · about
chapters (9)
- 0:00Private learning on data streams
- 1:09DP-SGD and DP-FTRL overview
- 4:25DP-FTRL for Android keyboard
- 8:18Deconstructing FTRL updates
- 13:04Toeplitz factorization and BLTs
- 17:33Buffered Linear Toeplitz operators
- 20:09Rational function representation of BLTs
- 24:39Optimizing BLTs empirically
- 27:05Conclusion and future work
related talks
01h 14mTutorial: Privacy, Part III
51mPrivate Boosting and Noise-tolerant Learning
01h 02mLarge-Scale Private Learning, Part I
01h 07mLarge-Scale Private Learning, Part II
44mPersonalized Federated Training of Diffusion Models with Privacy Guarantees
31mShort Industry Talks pt. 1
43mPrivacy Amplification by Sampling in Practice
36mPrivately Learning High-Dimensional Distributions