Almost Tight Error Bounds on Differentially Private Continual Counting
Explore a Google TechTalk on differentially private continual observation and its applications in large-scale private optimization. Delve into a novel mechanism for continual counting that offers asymptotically optimal mean squared error, significantly outperforming the standard binary mechanism. Examine the almost-tight analysis through non-asymptotic lower and upper bounds, and understand the constant-time matrix mechanism for the counting matrix. Discover how this research impacts private learning algorithms and provides the first tight lower bound on continual counting under approximate differential privacy. Learn about a new technique for proving lower bounds on linear queries, including its application to parity queries. Gain insights into recent developments in factorization norm analysis for a broader class of matrices, enabling counting under decaying sum.