Generalization performances of randomized classifiers and algorithms built on data dependent distributions

In this paper we prove that a randomized algorithm based on the data generating dependent prior and data dependent posterior Boltz- mann distributions of Catoni (2007) is Differentially Private (DP) and shows better generalization properties than the Gibbs (randomized) classi- fier associated to the same distributions. For this purpose, we will develop a tight DP-based generalization bound, which improve over the current state-of-the-art Hoefiding-type bound.