mlsanityData to 14 Oct 2026

Binned Group Algebra Factorization for Differentially Private Continual Counting

arXiv 2504.04398 ↗First posted 6 Apr 2025cs.DS cs.LGcited by 3

Not on the map. Why?

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.

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

22 of 32 references.

References · 22

  1. 2021Practical and Private (Deep) Learning without Sampling or Shufflingcited by 170
  2. 2022Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streamscited by 59
  3. 2023(Amplified) Banded Matrix Factorization: A unified approach to private trainingcited by 49
  4. 2022Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learningcited by 48
  5. 2019The Power of Factorization Mechanisms in Local and Central Differential Privacycited by 30
  6. 2022Constant matters: Fine-grained Complexity of Differentially Private Continual Observationcited by 23
  7. 2023Correlated Noise Provably Beats Independent Noise for Differentially Private Learningcited by 23
  8. 2024Efficient and Near-Optimal Noise Generation for Streaming Differential Privacycited by 17
  9. 2023A Unifying Framework for Differentially Private Sums under Continual Observationcited by 15
  10. 2014Factorization Norms and Hereditary Discrepancycited by 14
  11. 2021Differentially Private Histograms under Continual Observation: Streaming Selection into the Unknowncited by 14
  12. 2024Scaling up the Banded Matrix Factorization Mechanism for Differentially Private MLcited by 13
10 more
  1. 2021Differentially Private Algorithms for Graphs Under Continual Observationcited by 12
  2. 2023A Smooth Binary Mechanism for Efficient Private Continual Observationcited by 12
  3. 2024Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queriescited by 12
  4. 2024Banded Square Root Matrix Factorization for Differentially Private Model Trainingcited by 12
  5. 2023Differentially Private Continual Releases of Streaming Frequency Moment Estimationscited by 10
  6. 2024Differentially Private Decentralized Learning with Random Walkscited by 8
  7. 2024Improved Differentially Private Continual Observation Using Group Algebracited by 7
  8. 2024Streaming Private Continual Counting via Binningcited by 7
  9. 2025Continual Release Moment Estimation with Differential Privacycited by 5
  10. 2024Making Old Things New: A Unified Algorithm for Differentially Private Clusteringcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 1.

3 papers.

  1. 2025Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGDcited by 7
  2. 2025Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Countingcited by 3
  3. 2026Beyond Square Roots: A Memory-Efficient Explicit Factorization for Multi-Epoch Private Learningcited by 0