Current state-of-the-art methods for differentially private model training
are based on matrix factorization techniques. However, these methods suffer
from high computational overhead because they require numerically solving a
demanding optimization problem to determine an approximately optimal
factorization prior to the actual model training. In this work, we present a
new matrix factorization approach, BSR, which overcomes this computational
bottleneck. By exploiting properties of the standard matrix square root, BSR
allows to efficiently handle also large-scale problems. For the key scenario of
stochastic gradient descent with momentum and weight decay, we even derive
analytical expressions for BSR that render the computational overhead
negligible. We prove bounds on the approximation quality that hold both in the
centralized and in the federated learning setting. Our numerical experiments
demonstrate that models trained using BSR perform on par with the best existing
methods, while completely avoiding their computational overhead.

我们提出了一种新的矩阵分解方法 BSR，通过利用标准矩阵平方根的特性，可以有效地处理大规模问题，并且构造了解析表达式用于处理具有动量和权重衰减的随机梯度下降，从而克服了与当前最先进的差分隐私模型训练相关方法相比的高计算开销，同时证明了这种逼近质量在集中和联合学习环境中都成立，并通过数值实验证明使用 BSR 训练的模型性能与现有最佳方法相当，同时完全避免了计算开销。