2026-09-18T21:05:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25976 2026-09-05T19:31:54Z ddc:004 open_access

Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting (Extended Abstract) Henzinger, Monika Kalinin, Nikita Upadhyay, Jalaj Differential privacy continual release factorization norm The factorization norms of the lower-triangular all-ones n× n matrix, γ₂(M_{count}) and γ_{F}(M_{count}), 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 γ₂(M_{count}) was 1 + (log(n))/π by Mathias (Linear Algebra and Applications, 1993), and the best known lower bound was 1/π (2 + log((2n+1)/3)) ≈ 0.507 + (log(n))/π (Matoušek, Nikolov, Talwar, IMRN 2020), where log(⋅) 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 + (log(n))/π ≤ γ₂(M_{count}) ≤ 0.846 + (log(n))/π + 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 γ_{F}(M_{count}) compared to prior work, and we also establish an improved lower bound for γ_{F}(M_{count}): o(1) + 0.701 + (log(n))/π ≤ γ_{F}(M_{count}) ≤ 0.748 + (log(n))/π + o(1). That is, the gap between the lower and upper bound provided by our explicit factorization is 0.047 + o(1). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Monika Henzinger and Nikita Kalinin and Jalaj Upadhyay 2026 Is Part Of LIPIcs, Volume 368, 7th Symposium on Foundations of Responsible Computing (FORC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FORC.2026.5 urn:nbn:de:0030-drops-259767 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2026.5 eng https://creativecommons.org/licenses/by/4.0/legalcode