Privacy Amplification by Iteration
  Many commonly used learning algorithms work by iteratively updating an
intermediate solution using one or a few data points in each iteration.
Analysis of differential privacy for such algorithms often involves ensuring
privacy of each step and then reasoning about the cumulative privacy cost of
the algorithm. This is enabled by composition theorems for differential privacy
that allow releasing of all the intermediate results. In this work, we
demonstrate that for contractive iterations, not releasing the intermediate
results strongly amplifies the privacy guarantees.
  We describe several applications of this new analysis technique to solving
convex optimization problems via noisy stochastic gradient descent. For
example, we demonstrate that a relatively small number of non-private data
points from the same distribution can be used to close the gap between private
and non-private convex optimization. In addition, we demonstrate that we can
achieve guarantees similar to those obtainable using the
privacy-amplification-by-sampling technique in several natural settings where
that technique cannot be applied.
