# Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 35 references that are in the map.
- First posted on arXiv 17 Sep 2025.

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

- [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)
- [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)
- [Factorization Norms and Hereditary Discrepancy](https://mlsanity.com/paper/1408.1376/) (2014)
- [Correlated Noise Mechanisms for Differentially Private Learning](https://mlsanity.com/paper/2506.08201/) (2025)
- [Improved Differentially Private Continual Observation Using Group Algebra](https://mlsanity.com/paper/2412.02840/) (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)
- [On Design Principles for Private Adaptive Optimizers](https://mlsanity.com/paper/2507.01129/) (2025)
- [Binned Group Algebra Factorization for Differentially Private Continual Counting](https://mlsanity.com/paper/2504.04398/) (2025)

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

- [DP-λCGD: Efficient Noise Correlation for Differentially Private Model Training](https://mlsanity.com/paper/2601.22334/) (2026)
- [Learning Rate Scheduling with Matrix Factorization for Private Training](https://mlsanity.com/paper/2511.17994/) (2025)
- [Matrix Factorization for Practical Continual Mean Estimation Under User-Level Differential Privacy](https://mlsanity.com/paper/2601.22320/) (2026)

## Abstract (arXiv)

The factorization norms of the lower-triangular all-ones n × n matrix, γ2(Mcount) and γF(Mcount), play a central role in differential privacy as they are used to give theoretical justification of the accuracy of the only known production-level private training algorithm of deep neural networks by Google. Prior to this work, the best known upper bound on γ2(Mcount) was 1 + fraclog nπ by Mathias (Linear Algebra and Applications, 1993), and the best known lower bound was frac1π(2 + log(frac2n+13)) ≈ 0.507 + fraclog nπ (Matouvsek, Nikolov, Talwar, IMRN 2020), where log denotes the natural logarithm. Recently, Henzinger and Upadhyay (SODA 2025) gave the first explicit factorization that meets the bound of Mathias (1993) and asked whether there exists an explicit factorization that improves on Mathias' bound. We answer this question in the affirmative. Additionally, we improve the lower bound significantly. More specifically, we show that  0.701 + fraclog nπ + o(1) ;≤; γ2(Mcount) ;≤; 0.846 + fraclog nπ + o(1).  That is, we reduce the gap between the upper and lower bound to 0.14 + o(1). We also show that our factors achieve a better upper bound for γF(Mcount) compared to prior work, and we establish an improved lower bound:  0.701 + fraclog nπ + o(1) ;≤; γF(Mcount) ;≤; 0.748 + fraclog nπ + o(1).  That is, the gap between the lower and upper bound provided by our explicit factorization is 0.047 + o(1).