# A Unifying Framework for Differentially Private Sums under Continual Observation

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 77 references that are in the map.
- First posted on arXiv 18 Jul 2023.

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

- [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)
- [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)
- [Almost Tight Error Bounds on Differentially Private Continual Counting](https://mlsanity.com/paper/2211.05006/) (2022)
- [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)
- [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)
- [Differentially Private Continual Releases of Streaming Frequency Moment Estimations](https://mlsanity.com/paper/2301.05605/) (2023)
- [Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming](https://mlsanity.com/paper/2104.01808/) (2021)
- [On Differentially Private Counting on Trees](https://mlsanity.com/paper/2212.11967/) (2022)

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

- [Correlated Noise Provably Beats Independent Noise for Differentially Private Learning](https://mlsanity.com/paper/2310.06771/) (2023)
- [Privacy Amplification for Matrix Mechanisms](https://mlsanity.com/paper/2310.15526/) (2023)
- [Banded Square Root Matrix Factorization for Differentially Private Model Training](https://mlsanity.com/paper/2405.13763/) (2024)
- [Streaming Private Continual Counting via Binning](https://mlsanity.com/paper/2412.07093/) (2024)
- [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)
- [Continual Release Moment Estimation with Differential Privacy](https://mlsanity.com/paper/2502.06597/) (2025)
- [Online Differentially Private Synthetic Data Generation](https://mlsanity.com/paper/2402.08012/) (2024)
- [Improved Communication-Privacy Trade-offs in L2 Mean Estimation under Streaming Differential Privacy](https://mlsanity.com/paper/2405.02341/) (2024)
- [Binned Group Algebra Factorization for Differentially Private Continual Counting](https://mlsanity.com/paper/2504.04398/) (2025)
- [Private Continual Counting of Unbounded Streams](https://mlsanity.com/paper/2506.15018/) (2025)
- [Learning Rate Scheduling with Matrix Factorization for Private Training](https://mlsanity.com/paper/2511.17994/) (2025)
- [Optimal Rates for O(1)-Smooth DP-SCO with a Single Epoch and Large Batches](https://mlsanity.com/paper/2406.02716/) (2024)
- [The Binary Tree Mechanism is Optimal for Differentially Private Continual Counting](https://mlsanity.com/paper/2607.00876/) (2026)
- [Almost linear time differentially private release of synthetic graphs](https://mlsanity.com/paper/2406.02156/) (2024)
- [Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsampling](https://mlsanity.com/paper/2510.11640/) (2025)

## Abstract (arXiv)

We study the problem of maintaining a differentially private decaying sum under continual observation. We give a unifying framework and an efficient algorithm for this problem for any sufficiently smooth function. Our algorithm is the first differentially private algorithm that does not have a multiplicative error for polynomially-decaying weights. Our algorithm improves on all prior works on differentially private decaying sums under continual observation and recovers exactly the additive error for the special case of continual counting from Henzinger et al. (SODA 2023) as a corollary. Our algorithm is a variant of the factorization mechanism whose error depends on the γ2 and γF norm of the underlying matrix. We give a constructive proof for an almost exact upper bound on the γ2 and γF norm and an almost tight lower bound on the γ2 norm for a large class of lower-triangular matrices. This is the first non-trivial lower bound for lower-triangular matrices whose non-zero entries are not all the same. It includes matrices for all continual decaying sums problems, resulting in an upper bound on the additive error of any differentially private decaying sums algorithm under continual observation. We also explore some implications of our result in discrepancy theory and operator algebra. Given the importance of the γ2 norm in computer science and the extensive work in mathematics, we believe our result will have further applications.