Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper applies the concept of distributional generalization (DG)  to mitigate unwanted behavior at test time. They consider two main applications: (a) mitigating disparate impact of differential privacy and (b) group-distributional robustness. The authors show that (the previously established notion of) DG leads to a “what you see is what you get” phenomena where effects (that can be characterized by a loss function, e.g. performance on a group, etc) observed in training data will translate to test data. Thus, the goal of the paper is to develop algorithms that satisfy DG and at the same time have good behavior on the underlying objective (e.g. good performance on all subgroups). In particular, there is a direct connection between privacy and generalization, as DP algorithms satisfy DG. The authors build on this insight to develop algorithms like DP-IS-SGD (for task-(a)) and a DP-SGD based noisy gradient regularizer (for task-(b)). As a result, the authors show improvements in objects (a) and (b) over DP-SGD, while retaining test loss performance. 

strengths_and_weaknesses: Strength: 
I think the direction explored in the paper is quite interesting, and having algorithmic principles which would imply that ensuring certain properties like robustness, fairness, caliberation, etc on train data is sufficient to ensure that these properties also transfer to the test data, is quite valuable. The paper provide experiments that justify their algorithms, and the underlyinig principle of “what you see is what you get”. 

Weaknesses: 
I think the paper is not very novel. The idea of distributional generalization and its connections to differential privacy was known before. While proposition 2.6 is new, I think the rest of the parts like DP-IS-SGD and DP-SGD with noisy gradient regularizer are straightforward extensions of known algorithmic ideas. It seems that the authors are just rebranding distributional generalization and differential privacy as “what you see is what you get” principle. 

In general, it is not clear whether going though the route of designing algorithms with DG property is the best way to get desired behavior (fairness, robustness, etc) in practice. What are  the SOTA approaches for tasks-(a) and (b). It seems the experiments in Figure 3 or 4 does not compare to (or mention anything about) known SOTA approaches for mitigating these issues. 

questions: Is DP necessary to get DG? Are there concrete examples where DG provable holds but the algorithm is not private ? 
limitations: The paper has no potential negative societal impact. In fact, the goal of the paper is to address various societal issues like (fairness, robustness, etc) observed in practice.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper proposes the WYSIWYG framework which simply, formally, captures the idea that all behaviors should be nearly identical on the train and test set. The paper further goes on to show that differentially private algorithms exhibit this property and then provides some experiment to show it in practice.
strengths_and_weaknesses: Strength

* The paper highlights an interesting framework to capture the notion that**all** properties should behave uniformly on the train and the test set. The paper captures this idea and expresses it very well.
* The experiments with DP-IS-SGD and G-DRO provides a beautiful proof-of-concept. However, as I mention below, I think this is merely a small proof of concept and this nice but extremely limited experiment is not sufficient, in my opinion.

Weakness

I have listed two main weaknesses here - a) the experiment is simply too limited to claim anything about the generality of the framework and the theory ignores a huge body of work that proves information-theoretic generalisation bounds that applies to DP algorithms and, in fact, also shows distributional generalisation. I have listed further questions in the Questions section below.

* To show applications of the framework, the claims to experiment on   
  i. Group Distributionally Robust Optimisation and   
  ii. mitigate the disparate impact of DP.   
  However, in reality the first is a direct derivate of the second. More precisely, in the second case the authors propose an algorithm, derived from DP-SGD and that is guaranteed to be private with gradient clipping and adding noise *smartly*. In the the GDRO, the clipping part is removed. I find it quite a stretch to claim that the paper shows two applications of the framework.


* There is a large body of work on information theoretic generalisation bounds that is largely ignored by the authors. For example generalisation bounds based on bounded conditional mutual information (Steinke et. al [a]) is not discussed. In fact, the authors there also discuss their relation to DP and possibly their paper yields stronger results than this. On a more high level, there is now a huge body of work on generalisation guarantees of DP algorithms that are usually loss function agnostic and hence provides strong DG type guarantees. I would like to see a discussion of this.


[a] Steinke, Thomas, and Lydia Zakynthinou. "Reasoning about generalization via conditional mutual information."
questions: * The authors mention that DP training can improve fairness issues/accuracy disparity as observed in Bagdasaryan et al [1] and Pujol et al [2]. However, I imagine the results do not extend to the case of Sanyal et. al. [3] where the number of minority subpopulations scales with the sample size and also Cummings et. al [4] which has a somewhat related setting too. I don't say this as a criticism but rather for a better understanding of the problem. Could the authors please cite these two papers and discuss it?


* In light of the previous point, I find the theoretical part of this paper to not be the overwhelmingly major component here. Further, the DG framework is a very strong form of generalisation as is mentioned by the authors and the experiments do not reflect that as I mentioned in my first point on weakness. The paper mentions a)  Counterfactual fairness, b)Robustness to corruptions, and  Adversarial robustness as further use cases of these. I would like to see experiments on some if not all of these.

* Line 172 and Proposition 2.6 - The paper states that "DP algorithms enjoy a significantly stronger stability guarantee than the previously known one". Could the authors clarify and cite which previously known bound they are improving ? If it is the rather trivial $\mathrm{exp}(\epsilon)-1+\delta$ bound that is being improved, I would urge that this **not** be stated as an improvement over **known bounds** but rather another result; otherwise it sounds like an existing non-trivial result is being improved upon.

* The work by Feldman et. al [3] also introduces instance dependent privacy accounting which could possibly used for an algorithm like DP-IS-SGD. I would ask the authors to discuss the relation to this.


[1] Bagdasaryan, Eugene, Omid Poursaeed, and Vitaly Shmatikov. "Differential privacy has disparate impact on model accuracy." Advances in neural information processing systems 32 (2019).  
[2] Pujol, David, et al. "Fair decision making using privacy-protected data." Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency. 2020.  
[3] Sanyal, Amartya, Yaxi Hu, and Fanny Yang. "How unfair is private learning?." Proceedings of The 38th Conference on Uncertainty in Artificial Intelligence, 2022, https://openreview.net/forum?id=H2V43wIj5g9.   
[4] Cummings, Rachel, et al. "On the compatibility of privacy and fairness." Adjunct Publication of the 27th Conference on User Modeling, Adaptation and Personalization. 2019.  
[5] Feldman, Vitaly, and Tijana Zrnic. "Individual privacy accounting via a renyi filter. arXiv preprint 247." arXiv preprint arXiv:2008.11193 248 (2020).  
limitations: I have already discussed above that the paper does not address existing literature well.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper considers the “what you see is what you get” principle which means that the performance on the train dataset is similar to the performance on the test set. This principle is obtained from distributional generalisation which ensures that values of bounded functions are close on train and test sets. The paper then shows that by imposing differential privacy, distributional generalisation is achieved and uses this connection to define algorithms that maintain similar performance on train and test sets. 
strengths_and_weaknesses: Pros:
- The notion that ensuring DG implies that behavior generalises to the test data is interesting. 
- The concept that regularization methods improve DG is interesting (at least numerically). 
- The paper is well-written and I enjoyed reading it. 
- The numerical results are interesting. 

Cons:
- As the authors mention, the privacy -> generalisation implication is well-known. The DP-> DG implication therefore seems to be a (smaller) extension of this known result. 
- Since DP implies DG, why do we need this intermediate notion of DG? This is unclear to me. Algorithm 1 is essentially DP with importance sampling; it seems we do not make any modifications to achieve DG or use the properties of DG to define this algorithm (please correct me if I am wrong). Does DG give us any more information on what kind of noise to add and how to better trade off between noise/accuracy? This is thus my main comment: it is unclear what DG gives us in terms of algorithm design since the algorithms use DP; the case for DG is not entirely convincing. I can see that it allows us to derive the “what you see is what you get” guarantee, but this seems to also be derivable from DP itself. 
- Section 4.2 could be explained in more detail - these algorithms thus do not do gradient clipping and only add noise, so that formally both DP and DG are not satisfied? This again makes me question why DG is relevant to have as a concept. 
- As mentioned in 5.1 it is not possible to compute the exact DG gap so also numerically the notion of DG seems to be tricky to work with. 
questions: See above in the cons. The main comment is around why we need the concept of DG. 
limitations: There is no limitations section and this would be interesting to include.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work proposes to measure a model’s generalization under distribution shift with the previously proposed distributional generalization (DG), which is the maximum generalization error of the model under any loss function within [0,1]. They then prove that differential privacy (DP) leads to TV stability, which further leads to DG. Motivated by this result, the authors propose the DP-IS-SGD algorithm, which is essentially an importance weighted version of DP-SGD, so it requires the group labels at train time. However, DP usually leads to models with lower test performances, so the authors also experiment with adding noisy gradients to robust training methods like importance weighting and Group DRO.
strengths_and_weaknesses: Overall I find that there is a strong case to accept this work. The issue that popular methods such as importance weighting cannot generalize well is a well-known problem in this field, and this work investigates this problem through a theoretical lens and proposes some practical algorithms. The strengths of this work are:

1. The theory part is very well written and easy to understand. It nicely builds a bridge between DP and distributional robustness.
2. The algorithms make a lot of sense, and they show that noisy gradients can be a better regularizer than standard L2 regularization.

The biggest issue is that the DG condition seems too strong and very hard to achieve in practice. If I understand correctly, delta-DG implies (delta, pi)-DG for all pi because we can set phi(Z;theta) to be Pr(pi(Z;theta)) (correct me if I am wrong). Thus, delta-DG is a very strong condition, given that (delta, pi)-DG covers fairness, adversarial robustness and so on. And since DP and TV stability can imply DG, it implies that DP and TV stability are also very strong and are generally hard to achieve in practice. Nevertheless, there is no doubt that this work points to a very interesting and promising direction for theory.

questions: 1. Definitions 2.1 and 2.2 are confusing. In Eqn. (1), use a different notation: Change z ~ S to zhat ~ S to make it clear that these are the training samples, and this is the gap between training error and test error. Also in Definition 2.2 pi(Z) should be pi(Z; theta(S)).
2. Since DG is very hard to achieve, I suppose that the algorithms the authors propose cannot achieve good DG either. So is DG just an indicator of robust generalization and cannot be really maximized? Can we somehow find some “surrogate loss” for DG or DP that can be optimized more easily?

limitations: The limitations are addressed in Section 3.
review_title: null

Meta-review: metareview: The consensus amongst the reviewers is that the connection between DP and DG, and the resulting WYSIWYG framework for providing generalization guarantees for suitably trained models is both of theoretical, and as the paper demonstrates, potentially practical interest. The paper does have some downsides, in particular, that the connection between DP and DG (and similar ideas, including information-theoretic bounds based on conditional mutual information) have been floating around in the literature, and these connections seem to have been somewhat missed by the authors. However, overall, based on the merit of the theoretical framework, and the interesting experimental results, I recommend that this paper be accepted.
confidence: Less certain
Decision: Accept