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

Abstract

The factorization norms of the lower-triangular all-ones $n\times n$ matrix, ${\gamma }_2(M_{\mathrm{𝖼𝗈𝗎𝗇𝗍}})$ and ${\gamma }_{\mathrm{F}}(M_{\mathrm{𝖼𝗈𝗎𝗇𝗍}})$, 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 ${\gamma }_2(M_{\mathrm{𝖼𝗈𝗎𝗇𝗍}})$ was $1+\frac{\log (n)}{\pi }$ by Mathias (Linear Algebra and Applications, 1993), and the best known lower bound was $\frac{1}{\pi }\left(2+\log \left(\frac{2n+1}{3}\right)\right)\approx 0.507+\frac{\log (n)}{\pi }$ (Matoušek, Nikolov, Talwar, IMRN 2020), where $\log (\cdot )$ is 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 $o(1)+0.701+\frac{\log (n)}{\pi }\le {\gamma }_2(M_{\mathrm{𝖼𝗈𝗎𝗇𝗍}})\le \mathrm{\hspace{0.33em}0.846}+\frac{\log (n)}{\pi }+o(1).$ That is, we reduce the gap between the upper and lower bound to $0.14+o(1)$ and first improvement in over three decades. Additionally, we show that our factors achieve a better upper bound for ${\gamma }_{\mathrm{F}}(M_{\mathrm{𝖼𝗈𝗎𝗇𝗍}})$ compared to prior work, and we also establish an improved lower bound for ${\gamma }_{\mathrm{F}}(M_{\mathrm{𝖼𝗈𝗎𝗇𝗍}})$: $o(1)+0.701+\frac{\log (n)}{\pi }\le {\gamma }_{\mathrm{F}}(M_{\mathrm{𝖼𝗈𝗎𝗇𝗍}})\le \mathrm{\hspace{0.33em}0.748}+\frac{\log (n)}{\pi }+o(1).$ That is, the gap between the lower and upper bound provided by our explicit factorization is $0.047+o(1)$.