From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms

The new research derives explicit upper bounds on approximate max-information for any algorithm satisfying (ε, δ)-differential privacy or Rényi differential privacy, surpassing classical results under pure ε-differential privacy. The authors also leverage internal randomization structure to prove stronger guarantees for two common privacy-preserving learning algorithms: output perturbation with the Gaussian mechanism and streaming DP-SGD. As an application, these results yield non-vacuous PAC-Bayes generalization bounds for deep networks, where the prior distribution is learned by DP-SGD rather than chosen in the classical data-independent way.