Binned Group Algebra Factorization for Differentially Private Continual Counting
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912312739233792 |
|---|---|
| author | Henzinger, Monika Kalinin, Nikita P. Upadhyay, Jalaj |
| author_facet | Henzinger, Monika Kalinin, Nikita P. Upadhyay, Jalaj |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_04398 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Binned Group Algebra Factorization for Differentially Private Continual Counting Henzinger, Monika Kalinin, Nikita P. Upadhyay, Jalaj Data Structures and Algorithms Machine Learning 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. |
| title | Binned Group Algebra Factorization for Differentially Private Continual Counting |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2504.04398 |