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?

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