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

arXiv:2605.26222 · cs.LG, stat.ML · Submitted 2026-05-25 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "From Privacy to Generalization".

Jane: Understanding how differentially private stochastic gradient descent (DP-SGD) can be used to derive generalization guarantees for deep networks is a central challenge in modern machine learning theory,

Tom: First, who's behind it and why it matters.

Title and authors: Tom: So folks, we're diving into this paper today called "From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms." It sounds super technical, but basically, it tackles that big question of how much privacy you get versus how well your AI model performs on new data.

Jane: That's right. The title itself sets up the tension between privacy and generalization, which is a massive challenge in deep learning theory because existing methods often don't give us solid guarantees when we have models with millions of parameters or so many training examples.

Lu: From my perspective at Tsinghua, this paper is really interesting because it tries to connect approximate differential privacy directly to the structural properties of the model's information, which is a very deep theoretical connection.

Meng: I'm curious about how this translates into something practical for deployment; if we can control generalization through these bounds, it means we can deploy models with known performance ceilings rather than just hoping they work well.

Lalam: I think the implication here is that we can build AI systems that are inherently more trustworthy because the privacy constraints are mathematically linked to how well the model learns, not just tacked on as an afterthought.

The paper's summary: Tom: Alright, so what does this paper actually prove? It establishes a finite-sample bound on the approximate max-information of DP-SGD that scales linearly with the dataset size. This is a huge step because it shows that for these differentially private algorithms, we can get bounds comparable to those from earlier work on epsilon-differentially private algorithms, specifically showing a linear scaling with n in the dataset size.

Jane: In simpler terms, they're giving us a concrete mathematical rule that tells us how much information we can retain about the training data while keeping the model's performance predictable. It moves away from vague qualitative statements toward a quantifiable complexity term.

Lu: The core mechanism they are using involves analyzing the approximate max-information of the Gaussian mechanism applied to a single application, which they break down through several steps, including bounding variance using bounded difference inequalities and establishing tail bounds with McDiarmid’s inequality.

Meng: That sounds mathematically intensive; I need to know how that actually affects the training process. If we use this bound, can we actually tune the noise strength or clipping threshold to hit a specific generalization target?

Lalam: It suggests that by controlling these optimization hyperparameters, we get explicit control over the complexity term in the generalization bounds, which is a big deal for building robust systems.

The paper's improvements: Tom: The real meat of this work is how they use this linear max-information bound to construct data-dependent priors for PAC-Bayes generalization bounds. This allows them to get a generalization bound that depends entirely on the DP-SGD hyperparameters, rather than needing some arbitrary prior distribution that we have to guess based on the data.

Jane: That's powerful because it means the prior itself can be learned by DP-SGD during training, which ties everything together in a self-referential way. It removes the dependency on finding some perfect, fixed prior beforehand.

Lu: They show that this necessary additive correction term in the prior construction has an analogous form to something they've already analyzed, allowing it to be controlled by a suitable choice of DP-SGD’s hyperparameters. This is a clever way to make the bound explicit.

Meng: So, if we use this approach, I could potentially train my large models and then immediately get a rigorous certificate on their generalization performance just by looking at the noise settings I chose during training. That's how you move from experimental tuning to theoretical assurance.

Lalam: It means we are no longer relying on a data-independent prior for the PAC-Bayes analysis; instead, the bound becomes explicit in terms of what we set for DP-SGD, which is much more transparent for auditing our AI systems.

Conclusion: Tom: So to wrap up on "From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms," the main point is that they provide a general-purpose PAC-Bayes generalization bound where the necessary prior distribution can be learned by DP-SGD, controlled entirely by optimization hyperparameters.

Jane: Essentially, this gives us a way to get tight, non-vacuous generalization guarantees for deep networks trained via DP-SGD that rely only on the noise and clipping settings we choose during training.

Lu: It shows that the Gaussian mechanism achieves a functional form comparable to generic epsilon-DP algorithms, suggesting DP-SGD can serve as a plug-in replacement for steps that previously required using those other privacy mechanisms.

Meng: For practical deployment, this means we can get test error estimates based only on our training data and settings, which gives us a real safety margin before we push the model live.

Lalam: It really solidifies the idea that we can build AI systems that are both private and theoretically well-generalized by making the privacy constraints explicit in terms of those hyperparameters.

Tom: That’s all for this deep dive into "From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms." We'll be back soon with more exciting research from arXiv.

Jane: We'll definitely keep an eye on how this explicit control over complexity impacts the next set of papers we review.

Institute of Science and Technology Austria (ISTA)

cs.LG, stat.ML

Submitted: 2026-05-25

Updated: 2026-09-28

Importance score: 82/100

The gist: Understanding how differentially private stochastic gradient descent (DP-SGD) can be used to derive generalization guarantees for deep networks is a central challenge in modern machine learning

Key concepts

Approximate Max-Information
This is a measure of how much information the learning algorithm retains about the true underlying distribution of the data after being perturbed by differential privacy noise. The paper derives an explicit bound for DP-SGD, showing it scales predictably with dataset size and privacy parameters.
PAC-Bayes Generalization Bounds
These are mathematical tools used to estimate how well a model trained on a specific dataset will perform on unseen data. The paper shows that the max-information bound from DP-SGD can be used to build these bounds, creating a generalization guarantee that depends only on the optimization settings.
Gaussian Mechanism Analysis
The proof heavily relies on analyzing the noise introduced by the Gaussian mechanism, which is standard in DP. The analysis involves bounding variances using bounded difference inequalities and using McDiarmid’s inequality to establish tail bounds for the stochastic parts of the information quantity.
Data-Dependent Priors
Instead of using a prior distribution that is fixed regardless of the data, this method constructs a prior whose parameters are determined by the DP-SGD hyperparameters. This makes the resulting generalization bound more specific and potentially tighter for DP-SGD trained models.

Terminology

Summary

Understanding how differentially private stochastic gradient descent (DP-SGD) can be used to derive generalization guarantees for deep networks is a central challenge in modern machine learning theory, particularly because existing methods often fail to provide non-vacuous bounds in overparameterized settings. This work establishes an explicit finite-sample bound on the approximate max-information of DP-SGD, which allows for the construction of data-dependent priors for PAC-Bayes generalization bounds and provides a new generalization bound specifically for DP-SGD trained models controlled entirely by optimization hyperparameters.

Main Contribution and Core Result

The central technical result is Theorem 1, which establishes a bound on the approximate max-information of DP-SGD. Specifically, it proves that the approximate max-information of DP-SGD on a dataset with independent elements fulfills:

I β∞(DP-SGD(S), S) = O E n ζ squared σ squared (log E/β).

This result is significant because it provides the first guarantees on the max-information for a practical (ϵ, δ)-DP learning algorithm, applicable to modern deep networks trained in industry or academia.

Connection to PAC-Bayes Generalization Bounds

The paper demonstrates how this max-information bound facilitates the construction of data-dependent priors for PAC-Bayes bounds. Theorem 2 shows that DP-SGD can be used to obtain data-dependent priors for PAC-Bayes generalization bounds. This step is achieved by showing that the necessary additive correction term in the prior construction has an analogous form to (1), allowing it to be controlled by a suitable choice of DP-SGD’s hyperparameters. Consequently, this leads to a generalization bound for DP-SGD-trained models that depends only on the DP-SGD hyperparameters, rather than requiring a data-independent prior.

Analysis of the Gaussian Mechanism

The proof relies heavily on analyzing the approximate max-information of the Gaussian mechanism applied to a single application, as detailed in Proposition 1. This analysis involves several key steps:

  1. Deriving an explicit upper bound, g(G, Z), for the quantity f(S, Y) = log p(Y S) / p(Y).

  2. Bounding the variance of G using bounded difference inequalities (Lemma 3), which yields EG - E[G] squared ≤ ν = m ζ squared σ squared.

  3. Establishing tail bounds for the stochastic parts of g(G, Z) using McDiarmid’s inequality (Lemma 4).

  4. Combining these results to show that P n h(G, Z) > λo ≤ β for a specific choice of q related to the noise strength and privacy parameters.

Generalization Guarantees and Scaling

The paper compares its findings with classic results from Dwork et al. (2015b). By relating the max-information bound to the scaling properties, it shows that the Gaussian mechanism achieves a functional form comparable to generic ϵ-DP algorithms, suggesting that DP-SGD can serve as a plug-in replacement for steps that previously required the use of an ϵ-DP algorithm. The ratio of leading terms between its result and the classic result is shown to be bounded (Lemma 6), confirming that the generalization abilities are comparable to those of a generic differentially private algorithm.

Practical Applications and Numerical Validation

The work validates these theoretical bounds through extensive numerical experiments on standard datasets like MNIST and CIFAR-10, using complex deep networks. The results show that the resulting generalization bounds are non-vacuous, even for highly overparameterized models, and that they are tightened by the use of a DP-SGD prior rather than a data-independent prior. Table 1 and Table 2 provide numeric upper bounds on the risk, R, demonstrating that these bounds yield test errors comparable to or better than those achieved with data-independent priors. The analysis also covers various update rules, including momentum and weight decay.

Limitations and Future Directions

The paper notes two primary limitations. First, the current analysis assumes fixed-size, non-overlapping batches, contrasting with works that use variable-size batches like Poisson sampling or shuffling techniques for stronger guarantees. Second, the PAC-Bayes bounds are currently restricted to bounded loss functions. The authors suggest that extensions to unbounded losses might be possible but would require changes to the proof techniques. Furthermore, they note that for Theorem 2, the exact privacy guarantees of DP-SGD do not matter as much because the prior serves mainly as an analysis tool and is explicit in terms of hyperparameters rather than (ϵ, δ).

Improvements for AI systems

Based on the provided scientific paper, here are specific improvements that can be made to AI systems by leveraging its findings:

The core capability derived from this paper is establishing a principled, explicit connection between data privacy (via DP-SGD) and generalization guarantees (via PAC-Bayes theory), specifically for overparameterized deep networks. This allows practitioners to train models that are both private and theoretically well-generalized without relying on computationally intractable or overly restrictive prior assumptions.

Here are the specific improvements and what the improved system can do:

  2. Improved Generalization Bounds with Data-Dependent Priors (Theorem 2 & Corollary 3)

The paper proves that DP-SGD can be used to learn a data-dependent prior distribution for PAC-Bayes bounds, which is crucial because standard priors are often data-agnostic and fail in complex settings.

The improved AI system can:

Train deep networks (like GPT variants or large vision models) while simultaneously learning a private prior distribution directly from the training data itself using DP-SGD. This allows the system to derive generalization guarantees that depend only on the optimization hyperparameters (clipping constant, noise strength, epochs), rather than requiring an arbitrary, data-independent prior.

  2. Explicit Complexity Control for Privacy-Preserving Training (Theorem 1)

The paper provides a finite-sample bound on the approximate max-information of DP-SGD that scales linearly with dataset size, providing explicit control over the privacy/generalization trade-off using optimization hyperparameters.

The improved AI system can:

Precisely tune the training process (hyperparameters like clipping and noise) to achieve a desired level of generalization performance while maintaining a specific, guaranteed level of differential privacy. This moves beyond qualitative privacy settings to quantitative, explicit control over the complexity term in generalization bounds.

  2. Robust Generalization Guarantees for DP-SGD-Trained Models (Corollary 3)

The paper establishes a PAC-Bayes bound that applies directly to the resulting models trained via DP-SGD, which is a significant step beyond bounds that require assuming a specific prior structure.

The improved AI system can:

Obtain tight, non-vacuous generalization guarantees for deep networks trained using DP-SGD, even in highly overparameterized regimes (like large LLMs), ensuring that the model learned from private data is not only private but also statistically likely to perform well on unseen data.

  2. Adaptive Privacy Trade-off Selection (Lemma 6)

The analysis of the ratio of leading terms shows that the generalization performance scales predictably with the chosen privacy parameters, allowing for informed selection between different DP mechanisms (like Gaussian vs. pure epsilon-DP).

The improved AI system can:

Dynamically select and optimize its privacy mechanism during training based on desired generalization targets. For instance, if a higher level of accuracy is required, the system can choose a DP mechanism that offers better generalization scaling relative to the privacy cost.

  2. Model-Specific Risk Estimation (Table 2)

The numerical experiments show how these bounds translate into concrete upper bounds on test error for specific architectures (MLP on MNIST, ConvNet on CIFAR-10).

The improved AI system can:

Before deployment, the system can use the derived PAC-Bayes certificates to estimate a high-confidence upper bound on its generalization risk (test error) based only on the training data and optimization settings, providing a rigorous safety margin for deployment.

Sources

Related papers