Why is DP-SGD differentially private?

Question

The paper 'Deep Learning with Differential Privacy' explains how to make a deep learning algorithm as differentially private. This explanation is implemented in Tensorflow Privacy

My question is: we know that differential privacy is a concept defined only for randomized algorithms. Why is the DP-SGD in the paper above even a randomized algorithm?

Because once you have a trained model, then the model's prediction for a given input dataset is fixed, thus making it a deterministic algorithm. Their method gives a randomized algorithm only if you train your model every time you make a prediction, because then the weights could change during re-training producing a different output. But surely no one trains a model every single time they make a prediction. So why is it even a randomized algorithm?

Answer 1

@Arya is right: the algorithm that's private isn't the resulting neural network, it's the algorithm of training that neural network. If you re-run DP-SGD on the same training data, you'll get different networks out each time, and you won't be able to infer too much about specific training data points by investigating the learned networks.

Answer 2

Here is a non-technical answer: In each lot (subset of data) the authors of that paper

• average of the clipped gradients (scaled to be length $\leq C$) from that lot. The clipping allows us to know that the sensitivity (max change by arbitrarily rewriting one data point in the original set) of taking an average is $C$.
• use the Gaussian mechanism with epsilon (parameter given by user), sensitivity $C$ (parameter given by user and ensured in previous bullet) to add random noise to the average.
• the math proof seems involved, but the basic idea is that the Gaussian mechanism as used provides epsilon-delta-privacy, and composition theorems mean you can add them up over the iterations.