Privacy Amplification by Mixing and Diffusion Mechanisms
  A fundamental result in differential privacy states that the privacy
guarantees of a mechanism are preserved by any post-processing of its output.
In this paper we investigate under what conditions stochastic post-processing
can amplify the privacy of a mechanism. By interpreting post-processing as the
application of a Markov operator, we first give a series of amplification
results in terms of uniform mixing properties of the Markov process defined by
said operator. Next we provide amplification bounds in terms of coupling
arguments which can be applied in cases where uniform mixing is not available.
Finally, we introduce a new family of mechanisms based on diffusion processes
which are closed under post-processing, and analyze their privacy via a novel
heat flow argument. On the applied side, we generalize the analysis of "privacy
amplification by iteration" in Noisy SGD and show it admits an exponential
improvement in the strongly convex case, and study a mechanism based on the
Ornstein-Uhlenbeck diffusion process which contains the Gaussian mechanism with
optimal post-processing on bounded inputs as a special case.
