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?