Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss
A central issue in machine learning is how to train models on sensitive user
data. Industry has widely adopted a simple algorithm: Stochastic Gradient
Descent with noise (a.k.a. Stochastic Gradient Langevin Dynamics). However,
foundational theoretical questions about this algorithm's privacy loss remain
open -- even in the seemingly simple setting of smooth convex losses over a
bounded domain. Our main result resolves these questions: for a large range of
parameters, we characterize the differential privacy up to a constant factor.
This result reveals that all previous analyses for this setting have the wrong
qualitative behavior. Specifically, while previous privacy analyses increase ad
infinitum in the number of iterations, we show that after a small burn-in
period, running SGD longer leaks no further privacy.
  Our analysis departs completely from previous approaches based on fast
mixing, instead using techniques based on optimal transport (namely, Privacy
Amplification by Iteration) and the Sampled Gaussian Mechanism (namely, Privacy
Amplification by Sampling). Our techniques readily extend to other settings,
e.g., strongly convex losses, non-uniform stepsizes, arbitrary batch sizes, and
random or cyclic choice of batches.