- 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:
- For Tables 1, 2, and 3, what are and ? Is the same as the prior distribution? Is optimized from the DP priors with PAC-Bayes methods without DP? What is the “Numeric upper bounds ”? Is it the generalization bound ? Why are there empty values (“-”) in the table? Are they not computable or missing?
- Table 1 caption: and complexity/n is not explained or defined.
Minor:
- Line 101 Eq (2), the probability notation is not consistent
Some questions regarding the generalization bound:
- If 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 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?
- Does the result mean using a DP prior gives the model better generalization than a random prior?
- Why $\hat{R}(h_0) > \hat{R}(\rho) $ and $\mathcal{B}(h_0) > \mathcal{B}(\rho) $
Questions for authors
Some more questions:
- 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?
- 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)?
- What is the intuition of setting the prior distribution of the model class to the posterior distribution?
- What’s the intuition for going from Eq. (13) to (14)?
3 comments
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.
- one splits the training data into two disjoint parts. The first part is used to create the prior , while the actual model 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.
- one constructs the prior and the actual model on the full dataset, but the prior training has to fulfill pure-DP with small . 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 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 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 (the Table lists itself), but the right hand side of the bound (Compexity/n) decreases substantially.
Answers to further questions from the Weaknesses section:
-
in the table is prior, which is learned with differential private. 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. is a value that upper bounds the (uncomputable) true risk . It is constructed by solving the bounds (13), (14) or (15) for , 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 .
-
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.
-
is the training error: because is finetuned compared to and without privacy, so it achieves better training loss.
-
is the bound on the test error: finetuning 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.
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.
Yes, that is exactly what we are doing! The generalization bound (Theorem 5) holds for any model ρ trained on S. The privately trained prior π 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(ρ∥π) on the right hand side, the bounds get tighter if ρ and π are similar to each other. Therefore, in our experiments we do not learn π and ρ independently, but we first privately train π, and obtain ρ from it by non-private finetuning. As a special case, what if the target model, ρ, is actually trained privately itself? Then, one does not need a separate private prior but can evaluate the bound simply for π=ρ, such that KL(ρ∥π)=0. Because this case might be of independent interest, we stated it as a separate Corollary 6.
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.325, whereas the DP-SGD prior yields a better upper bound of B=0.233.