提出BISR方法，实现多轮私有训练中矩阵分解误差的理论最优。
Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGD
- 设计带状逆平方根因子分解法，解决多轮训练下的隐私噪声问题。
- 理论证明其误差渐近最优，与上下界一致，突破现有研究差距。
- 兼顾高效实现与易分析性，适合隐私机器学习研究者使用。
面向差分隐私训练的矩阵分解方法已成为在隐私约束下提升模型性能的有前景途径。实际训练中模型常需多轮迭代，要求考虑重复参与的矩阵分解机制。现有针对多轮分解误差的理论上下界存在显著差距。本文提出一种新的显式分解方法——带状逆平方根（BISR），在逆相关矩阵上施加带状结构。该方法使我们能对多轮误差进行明确且紧致的刻画，并进一步证明BISR在渐近意义上达到最优误差，与上下界匹配。实验表明，BISR在性能上媲美当前最优方法，同时实现更简单的部署、更高的计算效率和更易分析的特性。
原文摘要 · Abstract (English)
Matrix factorization mechanisms for differentially private training have emerged as a promising approach to improve model utility under privacy constraints. In practical settings, models are typically trained over multiple epochs, requiring matrix factorizations that account for repeated participation. Existing theoretical upper and lower bounds on multi-epoch factorization error leave a significant gap. In this work, we introduce a new explicit factorization method, Banded Inverse Square Root (BISR), which imposes a banded structure on the inverse correlation matrix. This factorization enables us to derive an explicit and tight characterization of the multi-epoch error. We further prove that BISR achieves asymptotically optimal error by matching the upper and lower bounds. Empirically, BISR performs on par with state-of-the-art factorization methods, while being simpler to implement, computationally efficient, and easier to analyze.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。