Skip to yearly menu bar Skip to main content


Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss

Jason Altschuler · Kunal Talwar

Hall J (level 1) #331

Keywords: [ Convex Optimization ] [ stochastic gradient Langevin dynamics ] [ private optimization ] [ DP-SGD ] [ privacy losss ] [ noisy-SGD ]


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. 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 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.

Chat is not available.