acceptodds
Under review as a conference paper at ICLR 2027

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.

Primary area:
learning theory
Keywords:
Differential Privacy, Generalization, Max-Information, PAC-Bayes

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_HRWsOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors derived a tighter approximate max-information bound for approximate DP (epsilon-delta)-DP. Leveraging the better max-information bound, the authors demonstrated that a better generalization bound for ML models can be achieved with data-dependent priors. The authors demonstrated with MNIST and CIFAR10 that such bounds can be applied to modern deep learning ML models and showed that the new generalization bound is tighter than generalization bounds derived with data-independent priors.

Critical strengths

The structure of the paper is relatively easy to follow, and the experiments are thorough. It is an important topic

Critical weaknesses

Some notations are not defined and are hard to understand:

  1. For Tables 1, 2, and 3, what are h0h_0 and ρ\rho? Is h0h_0 the same as the prior distribution? Is ρ\rho optimized from the DP priors with PAC-Bayes methods without DP? What is the “Numeric upper bounds B\mathcal{B}”? Is it the generalization bound kl(R^(ρ)∣∣R(ρ))kl(\hat{R}(\rho) || R(\rho))? Why are there empty values (“-”) in the table? Are they not computable or missing?
  2. Table 1 caption: κ\kappa and complexity/n is not explained or defined.

Minor:

  1. Line 101 Eq (2), the probability notation is not consistent

Some questions regarding the generalization bound:

  1. If ρ\rho is optimized from the DP priors with PAC-Bayes methods without DP, why do we want to do that and what does the generalization bound B(ρ)\mathcal{B}(\rho) give us? Are we leveraging the DP priors to give a better generalization bound for a non-DP trained model, rather than developing a generalization bound for DP learning algorithms?
  2. Does the result mean using a DP prior gives the model better generalization than a random prior?
  3. Why $\hat{R}(h_0) > \hat{R}(\rho) $ and $\mathcal{B}(h_0) > \mathcal{B}(\rho) $
Questions for authors

Some more questions:

  1. What is the relationship between the generalization bound and approximate DP? Can data-dependent prior be derived from non-DP methods as well? Why do we need the prior from approximate DP methods?
  2. What does the lower upper bound in generalization error mean? Does it mean the model converges better and has lower generalization error (closer to the theoretical minimum generalization error)?
  3. What is the intuition of setting the prior distribution of the model class to the posterior distribution?
  4. What’s the intuition for going from Eq. (13) to (14)?
3 comments

Thank you for your review. We hope that after our replies your concerns are addressed and you will be able to support our work for publication.

First, we would like to answer two questions from the “Weaknesses” part, as we believe this will clarify our method and contribution.

Are we leveraging the DP priors to give a better generalization bound for a non-DP trained model, rather than developing a generalization bound for DP learning algorithms?

Yes, that is exactly what we are doing! The generalization bound (Theorem 5) holds for any model ρ\rho trained on SS. The privately trained prior π\pi only acts as a mathematical tool to do so, its accuracy or generalization properties do not enter the guarantees (as always the case in PAC-Bayes). Because of the term KL(ρ∥π)KL(\rho\|\pi) on the right hand side, the bounds get tighter if ρ\rho and π\pi are similar to each other. Therefore, in our experiments we do not learn π\pi and ρ\rho independently, but we first privately train π\pi, and obtain ρ\rho from it by non-private finetuning. As a special case, what if the target model, ρ\rho, is actually trained privately itself? Then, one does not need a separate private prior but can evaluate the bound simply for π=ρ\pi=\rho, such that KL(ρ∥π)=0KL(\rho\|\pi)=0. Because this case might be of independent interest, we stated it as a separate Corollary 6.

Does the result mean using a DP prior gives the model better generalization than a random prior?

The actual generalization error of a model does not depend on the prior, it’s always equal to the difference between its training error and its test error. But the numerical guarantees we can give do depend on the prior, and there our results indeed show exactly what you write: the DP-prior yields a tighter bound than the random (data-independent) prior. For example, in Table 1, the random prior guarantees an upper bound B=0.325B=0.325, whereas the DP-SGD prior yields a better upper bound of B=0.233B=0.233.

Regarding the “Questions For Authors”:

What is the relationship between the generalization bound and approximate DP? Can data-dependent prior be derived from non-DP methods as well? Why do we need the prior from approximate DP methods?

There are two previous approaches to construct data-dependent priors. So far, we discuss them in lines 336-345 and 412-426, but will be happy to expand.

  1. one splits the training data into two disjoint parts. The first part is used to create the prior π\pi, while the actual model ρ\rho is evaluated on the second part of the data. This setup resembles a train/validation approach for assessing model quality, which is valid and useful, of course, but it means that some data must be left out of actual evaluation in the bound, and it provides few conceptual insights.
  2. one constructs the prior and the actual model on the full dataset, but the prior training has to fulfill pure-DP with small ϵ\epsilon. The problem here is that pure-DP training tends to be useless for machine learning tasks, because so much noise has to be added that the resulting models behave no better than random ones. In contrast, DP-SGD is practical and commonly used in ML tasks, but it provides only approximate-DP or Renyi-DP guarantees (not pure-DP). That is why we believe our results are valuable for the community: they connect the world of DP-prior learning with actual ML tasks. That said, we would like to emphasize that our technical contribution lies in the bounds on the max-information (Theorem 1-4). The numerical evaluation of the generalization bounds just demonstrates one application of these.

What does the lower upper bound in generalization error mean? Does it mean the model converges better and has lower generalization error (closer to the theoretical minimum generalization error)?

It means a stronger guarantee on the actual test error that the model will achieve. “Convergence” is not covered, as the bounds are not restricted to just iterative learning algorithms.

What is the intuition of setting the prior distribution of the model class to the posterior distribution?

Please see our discussion above: the prior must be private, the target model (posterior) can be anything. However, if the target model happens to be privately learned as well, there is no need to have them different, but one can choose prior and posterior equal. This reduces the upper bound, because the term KL(ρ∣π)KL(\rho | \pi) on the right hand side vanishes. The result is a generalization bound for the privately trained target model (stated as Corollary 6).

What’s the intuition for going from Eq. (13) to (14)?

For (13), the prior must be independent of the training data. For (14), one is allowed to use a data-dependent prior, but this causes an additional max-information term to appear in the numerator of the right hand side. Nevertheless, doing so might lead to an overall smaller right hand side, because KL(ρ∣π)KL(\rho | \pi) might become much smaller in return. This is exactly what our results show, e.g. in Table 1: going from row “data-indep.” (i.e. (13)), to DP-SGD (i.e. (14)), adds a penalty κ/n\kappa/n (the Table lists κ\kappa itself), but the right hand side of the bound (Compexity/n) decreases substantially.

Answers to further questions from the Weaknesses section:

  • h0h_0 in the table is prior, which is learned with differential private. ρ\rho is the posterior, which can be constructed in an arbitrary way, but in this case is obtained by training without privacy, starting at the private model parameters. B\mathfrak{B} is a value that upper bounds the (uncomputable) true risk R(ρ)R(\rho). It is constructed by solving the bounds (13), (14) or (15) for RR, i.e. numerically inverting the kl-expression. As these are common steps in PAC-Bayes analysis, we presented the steps only in Appendix A.3 but will be happy to detail them earlier.

  • The empty values “-” in Table 1 indicate that these quantities don’t exist, because the data-independent method does not learn a private prior h0h_0.

  • κ\kappa abbreviates the max-information, as in Table 2 and 3. We will add this to the caption of Table 1 as well.

  • “complexity/n” refers to the normalized complexity term (i.e. the right hand side of the generalization bounds) divided by the number of samples. We’ll make this more explicit.

  • Probability notation in line 101: thank you for spotting this.

  • R^\hat R is the training error: R^(h0)>R^(ρ)\hat R(h_0)>\hat R(\rho) because ρ\rho is finetuned compared to h0h_0 and without privacy, so it achieves better training loss.

  • B\mathfrak{B} is the bound on the test error: finetuning ρ\rho increases the complexity terms, but it lowers the training error, overall resulting in a better guarantee on the test error.

I thank the authors for the detailed response. It addresses all my questions. I will raise the score.

Reviewer_vQLrOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper establishes explicit upper bounds on approximate max-information for (ϵ,δ)(\epsilon,\delta)-differentially private (DP) and Rényi-DP (RDP) algorithms. For (ϵ,δ)(\epsilon,\delta)-DP, it identifies a sharp threshold: the bound is finite if and only if β≥nδ\beta \geq n\delta. For RDP, the authors obtain a bound of order nϵ~2/8+O(ϵ~n)n\tilde{\epsilon}^2/8 + O(\tilde{\epsilon}\sqrt{n}), eliminating the additional log⁡n\log n factor. The paper further provides tighter, mechanism-specific bounds for Gaussian output perturbation and single-pass streaming DP-SGD. As a practical application, the authors use DP-SGD to learn Gaussian PAC-Bayes priors directly from the training data and account for the resulting data dependence through max-information. Experiments on MNIST and CIFAR-10 demonstrate non-vacuous generalization bounds for neural networks with up to 13 million parameters, without requiring data splitting.

Critical strengths
  1. The paper establishes a sharp characterization of approximate max-information for (ϵ,δ)(\epsilon,\delta)-DP, showing that a finite bound is possible if and only if β≥nδ\beta \geq n\delta. The result provides explicit constants and improves upon the more restrictive conditions in Rogers et al. (2016). The proof technique is also elegant, avoiding the potentially loose bounds arising from group privacy.

  2. The paper presents a novel connection between RDP and max-information. The bound connecting RDP to approximate max-information appears to be new and represents a meaningful theoretical contribution. The analysis uses an interesting combination of divergence identities and concentration arguments, which may also be useful in other privacy-related problems.

  3. The PAC-Bayes framework carefully accounts for the data dependence introduced by learning priors from the training set, including the relevant privacy guarantees and multiple model configurations. Importantly, the resulting bounds apply to the actual training procedure without requiring data splitting, which is a useful improvement over earlier approaches based on DP priors.

Critical weaknesses
  1. The practical relevance seems overstated, and the experimental evidence is not convincing enough to support the claims. The authors state that their guarantees hold "in a regime where real-world deep learning models are trained" (lines 058–063), but I do not think the experiments support this claim for several reasons.

    • Privacy level. The non-vacuous bounds appear to require very strong privacy guarantees. The actual (ϵ,δ)(\epsilon,\delta) values used in the experiments are not reported, and the settings in Appendix C suggest that ϵ\epsilon is well below 1. At the privacy levels of the deployed models cited in the paper, the bounds would likely become weak or naive. In particular, the leading max-information term in Theorem 1 is nϵ2/8n\epsilon^2/8, corresponding to ϵ2/8\epsilon^2/8 per training example. This is already 0.5 per example at ϵ=2\epsilon=2 (VaultGemma) and 8 per example at ϵ=8\epsilon=8 (DP-Cap). Such values would make it very difficult to obtain meaningful PAC-Bayes certificates.

    • Missing baseline. The paper does not compare its approach against data-splitting methods using the same architectures and experimental settings. For example, Pérez-Ortiz et al., "Tighter Risk Certificates for Neural Networks" (JMLR 2021), report substantially tighter certificates. A direct comparison would be important for understanding whether avoiding data splitting actually provides a meaningful advantage.

  2. The novelty relative to existing work is not sufficiently clarified, and some claims about prior results appear inaccurate. The idea of learning a data-dependent prior through differential privacy, controlling the dependence using max-information, and then applying PAC-Bayes bounds was already introduced by Dziugaite and Roy, "Data-dependent PAC-Bayes Priors via Differential Privacy" (NeurIPS 2018). The authors should explain more clearly what is new in their implementation and analysis compared with this earlier framework.

    Also, approximating max-information bounds for (ϵ,δ)(\epsilon,\delta)-DP already exist. Rogers et al., "Max-Information, Differential Privacy, and Post-Selection Hypothesis Testing" (FOCS 2016), already established such bounds. Their constants are explicit, although the bounds are looser. This work also establishes the necessity of the product-distribution assumption for these general guarantees. I think this assumption should be explicitly stated alongside Theorem 1, as it is important for understanding the scope of the result.

    Fianlly, the mechanism-specific bound has limited practical value in its current form. The result only applies to single-pass DP-SGD, which is considerably more restrictive than typical deep learning training procedures. Moreover, the generic RDP bound actually performs better than the mechanism-specific bound in the reported experiments. This raises the question of when the specialized result would be useful in practice.

Questions for authors
  1. Could the authors report the actual (ϵ,δ)(\epsilon,\delta) values and test errors corresponding to each reported bound? I would also like to see what the bounds look like at more practical privacy levels, such as ϵ=2\epsilon=2 and ϵ=8\epsilon=8.

  2. How do the proposed certificates compare with those obtained using data-split priors on the same datasets and network architectures? A direct comparison would help clarify the practical benefit of avoiding data splitting.

  3. Could the authors clarify what is genuinely new compared with Rogers et al., "Max-Information, Differential Privacy, and Post-Selection Hypothesis Testing" (FOCS 2016), and Dziugaite and Roy, "Data-dependent PAC-Bayes Priors via Differential Privacy" (NeurIPS 2018)? Also, what exactly does "Linear" in the title refer to, given that previous bounds already have linear dependence on nn?

3 comments

Thank you for your review. We hope our response addresses your remaining questions.

Could the authors report the actual (epsilon,delta) values and test errors corresponding to each reported bound?

For (ϵ,δ)(\epsilon,\delta)-values, please see our reply to Reviewer 2ZtL above. The test errors were similar to the reported training error, typically within 1%, as typical for networks of this type:

  • Table 1, MNIST: Training error: 0.144, Test error: 0.150, Bound: 0.233

  • Table 3, CIFAR-10, 4-layers: Training error: 0.534, Test error: 0.539, Bound: 0.716

  • Table 3, CIFAR-10, 9-layers: Training error: 0.629, Test error: 0.627, Bound: 0.782

  • Table 3, CIFAR-10, 15-layers: Training error: 0.648, Test error: 0.655, Bound: 0.757

We’ll add these, and the privacy levels, to the revised manuscript.

I would also like to see what the bounds look like at more practical privacy levels, such as eps=2eps=2 and eps=8eps=8.

Numerically, the bound (14) for A\mathcal{A} with ϵ>1\epsilon>1 would indeed be loose or vacuous. However, this is not actually the problem as it might appear: A\mathcal{A} is the algorithm for learning the prior π\pi, not the actual model ρ\rho. As always in PAC-Bayes analysis, the prior π\pi acts purely as a mathematical reference, its accuracy is nowhere required. The generalization guarantees of Theorem 5 are for the posterior model ρ\rho, which can be determined any way we want. It does not have to fulfill any privacy, and certainly not ϵ<1\epsilon<1. In case you were referring to Corollary 6, there indeed the generalization bound is instantiated for a privately trained model. The insight there would simply be that large ϵ\epsilon-DP alone cannot guarantee good generalization properties. That is not a shortcoming of our results, though, but a consequence of lower bounds on the generalization gap even for pure ϵ\epsilon-DP (essentially, one cannot guarantee less than tanh⁡(ϵ/4)\tanh(\epsilon/4)). We’ll add a discussion to our manuscript.

How do the proposed certificates compare with those obtained using data-split priors on the same datasets and network architectures? A direct comparison would help clarify the practical benefit of avoiding data splitting.

We do not see work on privately-learned priors in competition with data-split bounds, in the sense of “those bounds are better than those”. The two approaches simply study different procedures. Learning the prior privately yields guarantees for models that are learned and evaluated on all available training data. In data splitting, the guarantees are based on evaluation on a subset of the available training set, because the rest has to be reserved for learning the prior. Conceptually, we prefer the former, because comparing the quality of prior to posterior and the KL between them provides insights about the complexity of the learning tasks. Tight data-split bounds can be obtained by assigning a large fraction of the data to the prior, and setting the posterior identical or close to it. Then the bound resembles guarantees obtained from a validation set. That’s a valid approach to estimate model quality, of course, but with different insights.

The assumption of a product distribution should be explicitly stated alongside Theorem 1.

We had introduced all our datasets to contain independent samples, but we agree that it’s clearer to also state it explicitly in the theorems, so we will edit the manuscript accordingly.

[...] the generic RDP bound actually performs better than the mechanism-specific bound in the reported experiments.

This seems a misinterpretation of our results. Multi-epoch training achieved better bounds than streaming training in Table 1, because it achieved lower training errors, but in an apples-to-apples comparison (single-epoch) of Figure 2, the explicit DP-SGD bound is often far tighter than the generic RDP one. Therefore, we believe it is valuable to report both.

Also, what exactly does "Linear" in the title refer to, given that previous bounds already have linear dependence on nn?

Indeed, the classic bounds for ϵ\epsilon- and (ϵ,δ)(\epsilon,\delta)-dp were linear in nn. Our work establishes new bounds for Renyi-DP, the Gaussian mechanism and DP-SGD that also have this linear dependence. If you find the term misleading, we can adjust the title.

Could the authors clarify what is genuinely new compared with Rogers et al., "Max-Information, Differential Privacy, and Post-Selection Hypothesis Testing" (FOCS 2016), and Dziugaite and Roy, "Data-dependent PAC-Bayes Priors via Differential Privacy" (NeurIPS 2018)?

Regarding Rogers et al:

  • We apologize if our discussion was overly simplistic, we will be happy to clarify our discussion of this work. Rogers et al.’s Theorem 3.1 states a bound O(ϵ2n+nδ/ϵ)O(\epsilon^2 n + n\sqrt{\delta/\epsilon}) on the β\beta-approximate max-information for (ϵ,δ)(\epsilon,\delta)-DP when β=e−ϵ2n+O(nδ/ϵ)\beta=e^{-\epsilon^2 n} + O(n\sqrt{\delta/\epsilon}), and the big-O notation prevents using this for numeric evaluation, such as PAC-Bayes applications. However, as part of their proof, they indeed also state expressions with explicit constants. However, those are very loose (such as 72ϵ272 \epsilon^2 in contrast to 18ϵ2\frac{1}{8} \epsilon^2 in our bound), and would result in a vacuous bound in all our settings. Additionally, the term δ/ϵ\delta/\epsilon is somewhat counter-intuitive, as it grows rather than shrinks for ϵ→0\epsilon\to 0 at fixed δ\delta, and it prevents studying cases ϵ→0\epsilon\to 0 unless also δ→0\delta\to 0.

  • In contrast, our Theorem 1 is fully explicit in its assumption and expressions, and no term δ/ϵ\delta/\epsilon occurs. The constants are tighter, in the sense that for δ→0\delta\to 0 we recover a result for pure-DP, which itself is a 4x improvement over (Dwork et al 2015).

Regarding Dziugaite and Roy (as well as Rivasplata):

  • (Dziugate and Roy, 2018) pioneered the concept of learning priors for PAC-Bayes by differentially private algorithms. However, they only considered pure-DP algorithms, presumably because only for those, suitable bounds on the max-information were known. Pure-DP algorithms are rare in ML, in the paper they use SGLD, which only approximates this properly. The explicit form of their bound is phrased in terms of ϵ\epsilon, the max-information only appears in the proof.

  • (Rivasplata 2020) provided a bound in the form (14) that holds for any learning algorithm for which the max-information can be controlled. However, the only examples provided were again pure-DP.

  • Our Theorem 5 is a restatement of Rivasplate’s in our own notation, and Corollary 6 is a direct consequence. Note that we openly state so (lines 350-353), we do not claim novelty of this. Our contribution is the explicit expression to insert for the max-information term, and the observation that this allows us to learn priors using practical methods, which are only (ϵ,δ)(\epsilon,\delta)-DP or RenyiDP, such as DP-SGD.

Regarding your other comments: As your criticism seems to be mostly focussed on the PAC-Bayesian results in Section 5, we would like to emphasize that the main technical contribution of our work lies in Section 3 and 4, where we actually establish the new bounds on the max-information. In Section 5 we demonstrate how these are applicable in the context of generalization bounds, as pioneered by (Dziugate&Roy, 2018) and (Rivasplata et al, 2020), but we do not claim novelty for the functional form of these bounds.

Regarding practical relevance, we would like to clarify a misunderstanding. Our work is theoretical, and we do not claim impact on practical ML tasks, see also our discussion in lines 476-485. What we meant by “practical” in lines 058-063 is that our bounds on the max-information can be evaluated for models trained under practical conditions, in particular deep networks with DP-SGD. This is in contrast to the prior work we had discussed before (lines 040-047), which is applicable only to simple, e.g. shallow, models, models in special-purpose parametrizations, or impractical pure-DP learning algorithms. We do not claim that the numeric values of our bounds, inserted into PAC-Bayes bounds, would yield non-vacuous generalization guarantees for large real-world models such as VaultGemma. Such results, if possible at all, are far beyond the state of the art in generalization theory. We will be happy to make this distinction clearer in the manuscript.

I thank the authors for their detailed response, which has addressed all my questions and concerns. I will maintain my original score and positive assessment of the paper. Overall, I believe the paper deserves acceptance and will make a valuable contribution to the differential privacy community.

Reviewer_2ZtLOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper examines the relationship between differential privacy and generalization using approximate max-information. The authors establish explicit upper bounds on approximate max-information for algorithms that satisfy approximate differential privacy and Rényi differential privacy, broadening earlier findings largely developed for pure differential privacy. They also obtain sharper bounds for the Gaussian mechanism and streaming DP-SGD by leveraging their particular randomization structures. These theoretical findings are then used to derive PAC-Bayes generalization bounds involving data-dependent priors trained with DP-SGD. Empirical results on MNIST and CIFAR-10 show non-vacuous generalization bounds for neural networks containing as many as 13.2 million parameters, without requiring data splitting or model compression.

Critical strengths
  1. Substantial theoretical extension of privacy-based generalization analysis. By deriving explicit upper bounds, the paper broadens previous analyses of approximate max-information from pure DP to approximate DP and Rényi DP. The refined constants and sharper bounds for Gaussian perturbation and streaming DP-SGD are especially useful, since they enhance the relevance of the theoretical findings for numerical evaluation and practical learning settings.

  2. Effective integration of theoretical findings with deep learning applications. The use of data-dependent priors trained via DP-SGD in PAC-Bayes generalization analysis is a notable strength. More specifically, the authors establish non-vacuous generalization bounds for neural networks with as many as 13.2 million parameters, without depending on data splitting or model compression. This illustrates the broader potential of the proposed framework beyond a purely theoretical setting.

Critical weaknesses
  1. Limited applicability of the tighter algorithm-specific bounds. The tighter max-information bounds for DP-SGD in Theorem 4 are restricted to fixed-size, non-overlapping batches with independent samples. This setting differs from standard DP-SGD training, which typically involves multiple epochs and randomized subsampling. Consequently, the experiments with Poisson subsampling rely on the more general Rényi-DP bounds rather than the tighter algorithm-specific results, limiting their applicability to practical deep learning scenarios.

  2. Relatively loose generalization guarantees in the experiments. Although the proposed approach achieves non-vacuous PAC-Bayes bounds, the numerical guarantees remain relatively loose, particularly for larger networks. For instance, the 13.2M-parameter model on CIFAR-10 has an empirical risk of 0.648 but a certified upper bound of 0.757. This substantial gap limits the practical informativeness of the resulting generalization guarantees.

  3. Limited experimental comparison with existing approaches. The experiments mainly compare DP-SGD-based priors against data-independent Gaussian priors. Although the paper emphasizes its advantages over approaches based on data splitting or model compression, direct empirical comparisons with these alternatives are largely absent. As a result, the relative advantages of the proposed method over existing PAC-Bayes approaches are not fully established experimentally.

Questions for authors
  1. Can the analysis in Theorem 4 be extended to multi-epoch DP-SGD with randomized subsampling?
  2. Could the authors report the achieved privacy budgets and further clarify the trade-off between model performance and certified generalization bounds in the CIFAR-10 experiments?
2 comments

Thank you for your review. We hope our response addresses your remaining questions.

Can the analysis in Theorem 4 be extended to multi-epoch DP-SGD with randomized subsampling?

Limited applicability of the tighter algorithm-specific bounds.

We currently do not see a direct way to adapt the proof of Theorem 4, as it exploits the fact that data between batches is independent. However, multi-epoch training with random subsampling is exactly the setting where privacy amplification yields strong (Renyi)DP guarantees, in particular stronger than what would follow simply from a naive composition analysis. Therefore, we believe Theorem 2 is the right tool to use. This is also what we do in our multi-epoch experiments.

Could the authors report the achieved privacy budgets and further clarify the trade-off between model performance and certified generalization bounds in the CIFAR-10 experiments?

Here are the privacy budgets of the reported results, computed as Renyi-DP by the Opacus framework and converted to (epsilon,delta)(epsilon,delta) with δ=n−1.1\delta=n^{-1.1}:

  • Table 1 (MNIST, 2 epochs, batch size 5000, clipping norm 0.1): ϵ=0.327586,δ=5.54669×10−6\epsilon=0.327586, \delta=5.54669 \times 10^{-6}, max-inf: 1224,

  • Table 3 (CIFAR-10, 4 and 15 layers, 5 epochs, batch size 5000, clipping norm 0.05): ϵ=0.268949,δ=6.77849×10−6\epsilon=0.268949, \delta=6.77849 \times 10^{-6}, max-inf: 757 (the fact that the same hyperparameters emerged for the 4-layer and the 15-layer networks is a coincidence)

  • Table 3 (CIFAR-10, 9 layers, 2 epochs, batch size 5000, clipping norm 0.05): ϵ=0.165441,δ=6.77849×10−6\epsilon=0.165441, \delta=6.77849 \times 10^{-6}, max-inf: 342

For our experiments, hyperparameters were selected to achieve small upper bounds (including compensation for the selection by a union bound), which favors small ϵ\epsilon at the expense of larger training errors than what could be achieved when optimizing for convergence. We hope this answers your question about the trade-off, but if you meant something else, please let us know.

Tightness of the guarantees.

We agree that there is more room for improvement and the problem is not solved. However, we believe our results are a meaningful step toward tighter certificates for neural networks.

Experimental comparisons.

We do not see work on privately-learned priors in competition with data-split bounds, in the sense of “those bounds are better than those”. The two approaches simply study different procedures. Learning the prior privately yields guarantees for models that are learned and evaluated on all available training data. In data splitting, the guarantees are based on evaluation on a subset of the available training set, because the rest has to be reserved for learning the prior. Conceptually, we prefer the former, because comparing the quality of prior to posterior and the KL between them provides insights about the complexity of the learning tasks. Tight data-split bounds can be obtained by assigning a large fraction of the data to the prior, and setting the posterior identical or close to it. Then the bound resembles guarantees obtained from a validation set. That’s a valid approach to estimate model quality, of course, but with different insights.

Thank you for the additional analyses. The reply does not change the reviewer's judgment of the paper. Thus the score will be maintained.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.