# Binned Group Algebra Factorization for Differentially Private Continual Counting

arXiv: https://arxiv.org/abs/2504.04398 · HTML: https://mlsanity.com/paper/2504.04398/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 32 references that are in the map.
- First posted on arXiv 6 Apr 2025.

## Builds on (most cited first, 22 of 22)

- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams](https://mlsanity.com/paper/2202.08312/) (2022)
- [(Amplified) Banded Matrix Factorization: A unified approach to private training](https://mlsanity.com/paper/2306.08153/) (2023)
- [Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learning](https://mlsanity.com/paper/2211.06530/) (2022)
- [The Power of Factorization Mechanisms in Local and Central Differential Privacy](https://mlsanity.com/paper/1911.08339/) (2019)
- [Constant matters: Fine-grained Complexity of Differentially Private Continual Observation](https://mlsanity.com/paper/2202.11205/) (2022)
- [Correlated Noise Provably Beats Independent Noise for Differentially Private Learning](https://mlsanity.com/paper/2310.06771/) (2023)
- [Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy](https://mlsanity.com/paper/2404.16706/) (2024)
- [A Unifying Framework for Differentially Private Sums under Continual Observation](https://mlsanity.com/paper/2307.08970/) (2023)
- [Factorization Norms and Hereditary Discrepancy](https://mlsanity.com/paper/1408.1376/) (2014)
- [Differentially Private Histograms under Continual Observation: Streaming Selection into the Unknown](https://mlsanity.com/paper/2103.16787/) (2021)
- [Scaling up the Banded Matrix Factorization Mechanism for Differentially Private ML](https://mlsanity.com/paper/2405.15913/) (2024)
- [Differentially Private Algorithms for Graphs Under Continual Observation](https://mlsanity.com/paper/2106.14756/) (2021)
- [A Smooth Binary Mechanism for Efficient Private Continual Observation](https://mlsanity.com/paper/2306.09666/) (2023)
- [Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries](https://mlsanity.com/paper/2403.00028/) (2024)
- [Banded Square Root Matrix Factorization for Differentially Private Model Training](https://mlsanity.com/paper/2405.13763/) (2024)
- [Differentially Private Continual Releases of Streaming Frequency Moment Estimations](https://mlsanity.com/paper/2301.05605/) (2023)
- [Differentially Private Decentralized Learning with Random Walks](https://mlsanity.com/paper/2402.07471/) (2024)
- [Improved Differentially Private Continual Observation Using Group Algebra](https://mlsanity.com/paper/2412.02840/) (2024)
- [Streaming Private Continual Counting via Binning](https://mlsanity.com/paper/2412.07093/) (2024)
- [Continual Release Moment Estimation with Differential Privacy](https://mlsanity.com/paper/2502.06597/) (2025)
- [Making Old Things New: A Unified Algorithm for Differentially Private Clustering](https://mlsanity.com/paper/2406.11649/) (2024)

## Built on by (most cited first, 3 of 3)

- [Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGD](https://mlsanity.com/paper/2505.12128/) (2025)
- [Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting](https://mlsanity.com/paper/2509.14334/) (2025)
- [Beyond Square Roots: A Memory-Efficient Explicit Factorization for Multi-Epoch Private Learning](https://mlsanity.com/paper/2605.18379/) (2026)

## Abstract (arXiv)

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(√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.