通过分箱优化群代数分解，实现低内存高效率的差分隐私计数。
Binned Group Algebra Factorization for Differentially Private Continual Counting
- 利用分箱技术对相似行值分组，降低矩阵分解内存与时间开销。
- 在输入流长度为n时，内存与运行时间降至$ ilde O( ext{√}n)$，误差仍较低。
- 适合大规模实时差分隐私系统，兼顾理论精度与实际效率。
我们研究在持续观测下实现差分隐私计数的高效矩阵分解方法。尽管Henzinger和Upadhyay（2024）提出基于群代数的分解方法以降低误差，但其在流式场景中的实用性受限于计算开销。本文揭示了群代数分解的新结构特性，使能采用Andersson与Pagh（2024）提出的分箱技术。通过将行中相似数值分组，该方法将内存使用和运行时间降至$ ilde O( ext{√}n)$，其中$n$为输入流长度，同时保持较低误差。本工作弥合了因子分解精度的理论提升与大规模隐私学习系统中实际效率之间的差距。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。