Differentially Private Learning Needs Hidden State (Or Much Faster
  Convergence)
  Differential privacy analysis of randomized learning algorithms typically
relies on composition theorems, where the implicit assumption is that the
internal state of the iterative algorithm is revealed to the adversary.
However, by assuming hidden states for DP algorithms (when only the
last-iterate is observable), recent works prove a converging privacy bound for
noisy gradient descent (on strongly convex smooth loss function) that is
significantly smaller than composition bounds after $O(1/\text{step-size})$
epochs. In this paper, we extend this hidden-state analysis to the noisy
mini-batch stochastic gradient descent algorithms on strongly-convex smooth
loss functions. We prove converging R\'enyi DP bounds under various mini-batch
sampling schemes, such as "shuffle and partition" (which are used in practical
implementations of DP-SGD) and "sampling without replacement". We prove that,
in these settings, our privacy bound is much smaller than the composition bound
for training with a large number of iterations (which is the case for learning
from high-dimensional data). Our converging privacy analysis, thus, shows that
differentially private learning, with a tight bound, needs hidden state privacy
analysis or a fast convergence. To complement our theoretical results, we run
experiment on training classification models on MNIST, FMNIST and CIFAR-10
datasets, and observe a better accuracy given fixed privacy budgets, under the
hidden-state analysis.
