  Prior work on differential privacy analysis of randomized SGD algorithms
relies on composition theorems, where the implicit (unrealistic) assumption is
that the internal state of the iterative algorithm is revealed to the
adversary. As a result, the R\'enyi DP bounds derived by such composition-based
analyses linearly grow with the number of training epochs. When the internal
state of the algorithm is hidden, we prove a converging privacy bound for noisy
stochastic gradient descent (on strongly convex smooth loss functions). We show
how to take advantage of privacy amplification by sub-sampling and randomized
post-processing, and prove the dynamics of privacy bound for "shuffle and
partition" and "sample without replacement" stochastic mini-batch gradient
descent schemes. We prove that, in these settings, our privacy bound converges
exponentially fast and is substantially smaller than the composition bounds,
notably after a few number of training epochs. Thus, unless the DP algorithm
converges fast, our privacy analysis shows that hidden state analysis can
significantly amplify differential privacy.
