改进了差分隐私中计数矩阵的因子分解界，缩小了理论误差范围。
Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting
- 提出新显式分解方法，逼近最优因子分解界。
- γ₂下界提升至0.701 + ln n/π，上界降至0.846 + ln n/π。
- 适用于高精度差分隐私训练算法研究与实现。
下三角全1矩阵 $M_{count}$ 的因子分解范数 $γ_2(M_{count})$ 与 $γ_{F}(M_{count})$ 在差分隐私中至关重要，是谷歌唯一生产级私有深度学习训练算法理论准确性的核心依据。此前，$γ_2(M_{count})$ 的最佳上界为 1 + rac{ ext{ln } n}{π}（Mathias, 1993），下界约为 0.507 + rac{ ext{ln } n}{π}（Matoušek 等, IMRN 2020）。本文首次构造出达到 Mathias 上界的显式分解，并进一步将下界提升至 0.701 + rac{ ext{ln } n}{π} + o(1)，上界降至 0.846 + rac{ ext{ln } n}{π} + o(1)，使上下界差距缩小至 0.14 + o(1)。同时，对 $γ_{F}(M_{count})$ 的上界和下界也分别优化为 0.748 + rac{ ext{ln } n}{π} + o(1) 与 0.701 + rac{ ext{ln } n}{π} + o(1)，差距仅 0.047 + o(1)。
原文摘要 · Abstract (English)
The factorization norms of the lower-triangular all-ones $n \times n$ matrix, $γ_2(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 $γ_2(M_{count})$ was $1 + \frac{\log n}π$ by Mathias (Linear Algebra and Applications, 1993), and the best known lower bound was $\frac{1}π(2 + \log(\frac{2n+1}{3})) \approx 0.507 + \frac{\log n}π$ (Matoušek, 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 + \frac{\log n}π + o(1) \;\leq\; γ_2(M_{count}) \;\leq\; 0.846 + \frac{\log 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}(M_{count})$ compared to prior work, and we establish an improved lower bound: $$ 0.701 + \frac{\log n}π + o(1) \;\leq\; γ_{F}(M_{count}) \;\leq\; 0.748 + \frac{\log n}π + o(1). $$ That is, the gap between the lower and upper bound provided by our explicit factorization is $0.047 + o(1)$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。