Binned Group Algebra Factorization for Differentially Private Continual Counting
By: Monika Henzinger, Nikita P. Kalinin, Jalaj Upadhyay
Potential Business Impact:
Keeps private data safe while learning from it.
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.
Similar Papers
Private Continual Counting of Unbounded Streams
Cryptography and Security
Protects private counting data while still counting.
Improved Accuracy for Private Continual Cardinality Estimation in Fully Dynamic Streams via Matrix Factorization
Cryptography and Security
Protects private data while counting items.
Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting
Data Structures and Algorithms
Makes private AI training more accurate and efficient.