Matrix factorization (MF) mechanisms for differential privacy (DP) have
substantially improved the state-of-the-art in privacy-utility-computation
tradeoffs for ML applications in a variety of scenarios, but in both the
centralized and federated settings there remain instances where either MF
cannot be easily applied, or other algorithms provide better tradeoffs
(typically, as $\epsilon$ becomes small).
In this work, we show how MF can subsume prior state-of-the-art algorithms in
both federated and centralized training settings, across all privacy budgets.
The key technique throughout is the construction of MF mechanisms with banded
matrices. For cross-device federated learning (FL), this enables
multiple-participations with a relaxed device participation schema compatible
with practical FL infrastructure (as demonstrated by a production deployment).
In the centralized setting, we prove that banded matrices enjoy the same
privacy amplification results as for the ubiquitous DP-SGD algorithm, but can
provide strictly better performance in most scenarios -- this lets us always at
least match DP-SGD, and often outperform it even at $\epsilon\ll2$. Finally,
$\hat{b}$-banded matrices substantially reduce the memory and time complexity
of per-step noise generation from $\mathcal{O}(n)$, $n$ the total number of
iterations, to a constant $\mathcal{O}(\hat{b})$, compared to general MF
mechanisms.

本文介绍了一种基于带状矩阵的矩阵分解机制，可以用于差分隐私的联合训练和集中式训练，并且具有更好的性能和更低的计算复杂度。

(扩展) 带状矩阵分解：一种私有化训练的统一方法

(Amplified) Banded Matrix Factorization: A unified approach to private  training

Banded matrices can be used as precision matrices in several models including
linear state-space models, some Gaussian processes, and Gaussian Markov random
fields. The aim of the paper is to make modern inference methods (such as
variational inference or gradient-based sampling) available for Gaussian models
with banded precision. We show that this can efficiently be achieved by
equipping an automatic differentiation framework, such as TensorFlow or
PyTorch, with some linear algebra operators dedicated to banded matrices. This
paper studies the algorithmic aspects of the required operators, details their
reverse-mode derivatives, and show that their complexity is linear in the
number of observations.

本文的主要研究领域是将带状矩阵用于高斯模型的精度矩阵中，旨在通过配备专门用于带状矩阵的线性代数算子来实现现代推理方法的运用，同时研究这些算子的算法方面，详细阐述它们的反向传播导数，并证明它们的复杂度与观测数量呈线性关系。