From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms
Abstract
Understanding the relationship between generalization and privacy remains a challenge in modern machine learning theory, particularly for deep networks that are trained by variants of differentially private stochastic gradient descent (DP- SGD). In this work we make progress on this persistent open problem. First, we derive explicit upper bounds on the approximate max-information of any algorithm that fulfills $(ε, δ)$-differential privacy or Rényi differential privacy, thereby going beyond the classical results for pure ε-differential privacy. Subsequently, we show even stronger guarantees for two common private learning algorithms, output perturbation with the Gaussian mechanism, and streaming DP-SGD, by exploiting the structure of their internal randomization. As an application of our results, we demonstrate how to obtain non-vacuous PAC-Bayes generalization bounds for deep networks, in which the prior distribution is learned by DP-SGD instead of the classical way of choosing it in a data-independent way.
Related
- Residual-Information Generalization Bounds Under Selective Privacy: Extended Version
- Differentially Private Learning of Markov Chains: Near-Optimal Sample Complexity for Item and User Level Privacy
- Corrections to ``The Method of Gaps: Exact Expressions for the Generalization Error of Supervised Learning Algorithms
- Learning Sparse Support under Differential Privacy: Adaptive Algorithms and Minimax Limits
- Differentially Private Distributed Optimization via the Intrinsic Randomness of Zeroth-Order Estimators: Sampling Geometry, Convergence, and Privacy Guarantees
BibTeX
@misc{lampert2026from,
title = {{From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms}},
author = {Christoph H. Lampert and Max Cairney-Leeming and Hossein Zakerinia},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.26222},
eprint = {2605.26222},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.26222},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms
AU - Christoph H. Lampert
AU - Max Cairney-Leeming
AU - Hossein Zakerinia
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2605.26222
UR - https://arxiv.org/abs/2605.26222
AB - Understanding the relationship between generalization and privacy remains a challenge in modern machine learning theory, particularly for deep networks that are trained by variants of differentially private stochastic gradient descent (DP- SGD). In this work we make progress on this persistent open problem. First, we derive explicit upper bounds on the approximate max-information of any algorithm that fulfills $(ε, δ)$-differential privacy or Rényi differential privacy, thereby going beyond the classical results for pure ε-differential privacy. Subsequently, we show even stronger guarantees for two common private learning algorithms, output perturbation with the Gaussian mechanism, and streaming DP-SGD, by exploiting the structure of their internal randomization. As an application of our results, we demonstrate how to obtain non-vacuous PAC-Bayes generalization bounds for deep networks, in which the prior distribution is learned by DP-SGD instead of the classical way of choosing it in a data-independent way.
ER -