The most common algorithms for differentially private (DP) machine learning
(ML) are all based on stochastic gradient descent, for example, DP-SGD. These
algorithms achieve DP by treating each gradient as an independent private
query. However, this independence can cause us to overpay in privacy loss
because we don't analyze the entire gradient trajectory. In this work, we
propose a new DP algorithm, which we call Accelerated-DP-SRGD (DP stochastic
recursive gradient descent), that enables us to break this independence and
only pay for privacy in the gradient difference, i.e., in the new information
at the current step. Our algorithm achieves the optimal DP-stochastic convex
optimization (DP-SCO) error (up to polylog factors) using only a single epoch
over the dataset, and converges at the Nesterov's accelerated rate.
Our algorithm can be run in at most $\sqrt{n}$ batch gradient steps with
batch size at least $\sqrt{n}$, unlike prior work which required $O(n)$ queries
with mostly constant batch sizes. To achieve this, our algorithm combines three
key ingredients, a variant of stochastic recursive gradients (SRG), accelerated
gradient descent, and correlated noise generation from DP continual counting.
Finally, we also show that our algorithm improves over existing SoTA on
multi-class logistic regression on MNIST and CIFAR-10.

我们提出了一种新的差分隐私算法，叫做加速差分隐私随机递归梯度下降（Accelerated-DP-SRGD），它能够在只对当前步骤的新信息进行隐私代价计算的情况下实现最优 DP - 随机凸优化（DP-SCO）错误，通过仅使用数据集上的单个时期并以 Nesterov 的加速速率收敛，解决了从 DP 持续计数中生成相关噪声的问题，最后还展示了我们的算法在 MNIST 和 CIFAR-10 上对多类逻辑回归的优越性。