  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.
