Why is DP-SGD differentially private? 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?

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.

