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 训练的模型性能与现有最佳方法相当，同时完全避免了计算开销。

用于差分隐私模型训练的分带平方根矩阵因式分解

Banded Square Root Matrix Factorization for Differentially Private Model  Training

Many methods in differentially private model training rely on computing the
similarity between a query point (such as public or synthetic data) and private
data. We abstract out this common subroutine and study the following
fundamental algorithmic problem: Given a similarity function $f$ and a large
high-dimensional private dataset $X \subset \mathbb{R}^d$, output a
differentially private (DP) data structure which approximates $\sum_{x \in X}
f(x,y)$ for any query $y$. We consider the cases where $f$ is a kernel
function, such as $f(x,y) = e^{-\|x-y\|_2^2/\sigma^2}$ (also known as DP kernel
density estimation), or a distance function such as $f(x,y) = \|x-y\|_2$, among
others.
Our theoretical results improve upon prior work and give better
privacy-utility trade-offs as well as faster query times for a wide range of
kernels and distance functions. The unifying approach behind our results is
leveraging `low-dimensional structures' present in the specific functions $f$
that we study, using tools such as provable dimensionality reduction,
approximation theory, and one-dimensional decomposition of the functions. Our
algorithms empirically exhibit improved query times and accuracy over prior
state of the art. We also present an application to DP classification. Our
experiments demonstrate that the simple methodology of classifying based on
average similarity is orders of magnitude faster than prior DP-SGD based
approaches for comparable accuracy.

给定一个相似度函数和一个大型高维私有数据集，输出近似表示任意查询的总和的差分隐私数据结构。在核函数和距离函数等情况下，我们的理论结果改进了先前的研究，并提供了更好的隐私 - 效用权衡和更快的查询时间。实验表明，基于平均相似性进行分类的简单方法比基于 DP-SGD 的方法更快且准确性相当。