Streaming Private Continual Counting via Binning

Learn about a novel approach to differential privacy in streaming settings through this 52-minute Google TechTalk. Explore the challenge of continual observation in differential privacy, where functions of datasets must be continuously released as data arrives one element at a time while maintaining privacy guarantees. Discover how traditional factorization mechanisms, while effective for continual counting problems, face significant space limitations in streaming environments due to their requirement for space proportional to input size. Examine a innovative binning solution that approximates factorization mechanisms in sublinear space by strategically grouping adjacent matrix entries with similar values to maintain matrix-vector products efficiently. Understand the theoretical foundations including provable sublinear space guarantees for lower triangular matrices with monotonically decreasing entries away from the diagonal. Analyze empirical results demonstrating how this low-space approach can match or exceed the performance of asymptotically optimal factorization mechanisms. Compare this binning methodology with alternative approaches such as rational function approximation techniques, and understand its applications in differentially private stochastic gradient descent implementations where continual counting plays a crucial role in maintaining privacy while processing streaming data.