Binned Group Algebra Factorization for Differentially Private Continual Counting
This work improves the practical efficiency of differentially private continual counting for large-scale private learning systems by reducing computational constraints.
This paper addresses memory-efficient matrix factorization for differentially private continual counting. It introduces new structural properties of group algebra factorization, enabling a binning technique that reduces memory usage and running time to \tilde O(\sqrt{n}) while maintaining low error.
We study memory-efficient matrix factorization for differentially private counting under continual observation. While recent work by Henzinger and Upadhyay 2024 introduced a factorization method with reduced error based on group algebra, its practicality in streaming settings remains limited by computational constraints. We present new structural properties of the group algebra factorization, enabling the use of a binning technique from Andersson and Pagh (2024). By grouping similar values in rows, the binning method reduces memory usage and running time to $\tilde O(\sqrt{n})$, where $n$ is the length of the input stream, while maintaining a low error. Our work bridges the gap between theoretical improvements in factorization accuracy and practical efficiency in large-scale private learning systems.