What You See is What You Get: Principled Deep Learning via Distributional Generalization
Authors: Bogdan Kulynych
Yao-Yuan Yang
Yaodong Yu
Jarosław Błasiok
Preetum Nakkiran
Venue: NeurIPS 2022 Accept (2022)
Keywords: deep learning
differential privacy
disparate impact
distributional robustness
DRO
adversarial robustness
robust overfitting
distributional generalization

Abstract: Having similar behavior at training time and test time—what we call a “What You See Is What You Get” (WYSIWYG) property—is desirable in machine learning. Models trained with standard stochastic gradient descent (SGD), however, do not necessarily have this property, as their complex behaviors such as robustness or subgroup performance can differ drastically between training and test time. In contrast, we show that Differentially-Private (DP) training provably ensures the high-level WYSIWYG property, which we quantify using a notion of distributional generalization. Applying this connection, we introduce new conceptual tools for designing deep-learning methods by reducing generalization concerns to optimization ones: to mitigate unwanted behavior at test time, it is provably sufficient to mitigate this behavior on the training data. By applying this novel design principle, which bypasses “pathologies” of SGD, we construct simple algorithms that are competitive with SOTA in several distributional-robustness applications, significantly improve the privacy vs. disparate impact trade-off of DP-SGD, and mitigate robust overfitting in adversarial training. Finally, we also improve on theoretical bounds relating DP, stability, and distributional generalization.

What You See is What You Get: Principled Deep Learning via Distributional Generalization
Bogdan Kulynych Yao-Yuan Yang** Yaodong Yu Jaroslaw Blasiok' Preetum Nakkiran² 1EPFL UCC San Diego 'UC Berkeley *Columbia University
denotes equal contribution.
Abstract
we call a "What You See Is What You Get" (WYSIWYG) property- is desirable in machine learning. Models trained with standard stochastic gradient descent (SGD), however, do not necessarily have this property, as their complex behaviors such as robustness or subgroup performance can differ drastically between training and test time. In contrast, we show that Differentially-Per Privatte (DP) training provably ensures the high-level WYSIWYG property, which quantify using notion of distributional generalization. Applying this connection, we introduce new conceptual tools for designing deep-learning methods by reducing generalization concerns to optimiza- tion ones: to mitigate unwanted behavior at test time, it is provably sufficient to mitigate this behavior on the training data. By applying this novel design principle, which bypasses "pathologies" of SGD, we construct simple algorithms that are competitive with SOTA in several cntrrbutional-robustteee cantly improve the privacy vs. disparate impact trade-off of DP-SGD, and mitigate robust overfitting in adversarial training. Finally, also improve theoretical bounds relating DP, stability, and distributional generalization.
Having similar behavior at training time and test
applications, signifi-
1 Introduction
Much of machine learning (ML), both in theory and practice, operates under two assumptions. First, we have independent and identically distributed (i.i..) samples. Second, we care only about single averaged scalar metric (error, loss, risk). Under these assumptions, we have mature methods and theory: Modern learning methods excel when trained on i.i.d. data to directly optimize scalar loss, and there are many theoretical tools for reasoning about generalization, which explain when does optimization of a scalar on the training data translates to similar values of this scalar at test time.
The focus on scalar metrics such average error, however, misses many theoretically, practically, and socially relevant aspects of model performance. For example, models with small average error often have high error on salient minority subgroups [Buolamwini and Gebru, 2018, Koenecke et al., 2020]. In general, ML models are applied to the heterogeneous and long-tailed data distributions of the real world [Van Horn and Perona, 2017]. Attempting to summarize their complex behavior with only single scalar misses many rich and important aspects of learning.
These issues compounded for modern overparameterized networks, as their nuanced test-time behavior is not reflected at training time. For example, consider the setting of importance sampling: suppose we know that a certain subgroup of inputs underrepresented in the training data compared to the test distribution (breaking the i.i.d. assumption). For underparameterized models, we can upsample this underrepresented group account for the distribution shift [see, e.g., Gretton et al., 2009]. This approach, however, is known to empirically fail for overparameterized models [Byrd and Lipton, 2019]. Because "what you see" (on the training data) is not "what you get" (at test time), we cannot make principled train train-time interventions to affect test-time behaviors. This issue extends
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

SGD (CelebA)
DP-SGD (CelebA)
1.0
1.0
0.8
0.6
0.6
Moosttgroup
0.4
0.4
0.0
0.0
Standard
Importance sampling
Stundard
Importance sampling
Figure 1: Differential privacy ensures the desired behavior of importance sampling on test data. The train and test accuracy of ResNets on CelebA, evaluated on the worst-performing ("male, blond") subgroup. Left: Standard SGD has a large generalization gap on this subgroup, and Importance Sampling (IS) has little effect. Right: DP-SGD provably has small generalization gap on all subgroups, and IS improves subgroup performance as intended. See Section 5 for details.
beyond importance sampling. For example, theoretically principled methods for distributionally robust optimization (e.g. Namkoong and Duchi (2016)) fail for overparameterized deep networks, and require ad-hoc modifications [Sagawa al., 2019a].
We develop a thcoretical framework which sheds light on these cxisting issues, and leads to improved practical methods in privacy, fairness, and distributional robustness. The core object in our framework is what we call the "What You See Is What You Get" (WYSIWYG) property. A training procedure with the WYSIWYG property does not exhibit the "pathologies" of standard stochastic gradient descent (SGD): all test-time behaviors will be expressed on the training data as well, and there will be "no surprises" in generalization.
What You See What You Get (WYSIWYG) as a Design Principle. The WYSIWYG property is desirable for two reasons. The first is diagnostic: as there are "no surprises" at test time, all properties of model at test time are already evident at the training stage. It cannot be the case, for example, that WYSIWYG model has small disparate impact the training data, but large disparate impact at test time. The second reason is algorithmic: to mitigate any unwanted test-time behavior, it sufficient to mitigate this behavior on the training data. This means that algorithm designers be concerned only with achieving desirable behavior at train time, as the WYSIWYG property guarantees it holds at test time too. In practice, this enables the usage of many theoretically principled algorithms which were developed in the underparameterized regime to also apply in the modern overparameterized (deep learning) setting. For example, we find that interventions such as importance sampling, or algorithms for distributionally robust optimization, which fail without additional regularization, work exactly as intended with WYSIWYG (See Figure for illustration).
As WYSIWYG is a high-level conceptual property, we have to formalize to use in computational practice. We do using the notion of Distributional Generalization (DG), introduced by Nakkiran and Bansal [2020], Kulynych et al. [2022]. If classical generalization ensures that the values of the model's 's loss the training dataset and at test time are close on average "Shalev-Shwards et al., 2010], distributional generalization ensures that values of any other bounded test function not only loss are close training and test time. We say that model which satisfies appropriately high level of distributional generalization exhibits the W WYSIWYG property.
Achieving DG in Practice. Our key observation is that distributional generalization is formally implicd by differential privacy (DP) [Dwork et al., 2006, 2014]). The spirit of this observation is not novel: DP training is known to satisfy much stronger notions of generalization (e.g., robust generalization, see Section 6 for more details), and stability than standard SGD [Dwork et al., 2015a, Cummings et al., 2016, Bassily et al., 2016, Steinke and Zakynthinou, 2020]. We show that a similar connection holds for the notion of distributional generalization, and prove (and improve) tight bounds relating DP, stability, and DG. This guarantees the WYSIWYG property for any method that is differentially-prinn
including SP-SGD on deep neural networks [Abadi et al., 2016]. We demonstrate how DG can be useful design principle in three concrete settings. First, we show that we can mitigate disparate impact of DP training [Bagdasaryan et al., 2019, Pujol et al., 2020] by leveraging importance sampling. Second, we study the setting of distributionally robust

---

optimization [e.g,, Sagawa et al., 2019a, Hu et al., 2018]. We show how ideas from DP can be used construct heuristic optimizers. which do not formally satisfy DP, yet empirically exhibit DG. Our heuristics lead to competitive results with SOTA algorithms in five datasets in the distributional robustness setting. Third, we show that the heuristic optimizer also capable of reducing overfitting of adversarial loss in adversarial training [Madry et al., 2018, Zhang et al., 2019, Rice et al., 2020].
Our Contributions. We develop the theoretical connection between Differential Privacy (DP) and Distributional Generalization (DG), and we leverage our theory to improve empirical performance in privacy, fairnsss, and robustness applications. Theoretically (Sections 4):
1. We provide tighter bounds than previously reported connecting DP and strong forms of generalization, and show that DP training methods satisfy DG, thus the WYSIWYG property.
2. We introduce DP-IS-SGD an importance-sampling version of DP-SGD, and show it satisfies DP and DG.
Experimentally (Section 5):
1. We use framework to shed light disparate impact: The disparity in accuracy across groups at test time are provably reflected by the accuracy disparity on the train dataset.
2. We use our DP-IS-SGD algorithm to largely mitigate the disparate impact of DP using importance sampling.
3. Based on our theoretical intuitions, we propose a DP-inspired heuristic: addition of gradient noise. We find this empirically achieves competitive and even improved results in several DRO settings, and reduces overfitting of adversarial loss in adversarial training.
Taken together, our results emphasize the central role of the WYSIWYG property in designing machine learning algorithms which avoid the "pathologies" of standard SGD. We also establish DP as useful tool for achieving WYSIWYG, thus extend its applications further beyond privacy.
2 Theory of "What You See is What You Get" Generalization
We first review the notion of distributional generalization and demonstrate why it captures the WYSIWYG property. Second, we show that strong stability notions imply distributional generaliza- tion. Finally, we improve on the known stability guarantees of differential privacy. As a result, we extend the connections between differential privacy, stability, and generalization distributional generalization, showing that stability and privacy imply the WYSIWYG property.
Notation. We consider learning task with a set of examples X and labels Y. We assumee that source distribution of labeled examples z & (z. y) ~ 'D is defined over = X x Y. Given an .i.dl-sampled dataset S ~ DD' of size n, we use randomized training algorithm T(S) that outputs a model's parameter vector 0 from the set θ. We denote by fo(r) the resulting prediction function.
2.1 Distributional Generalization and WYSIWYG
If on- on-average generalization (Shalev-Shwartz et al., 2010] guarantees closeness only of loss values on train and test data, distributional generalization (DG) also guarantees closeness of values of all test functions ((2; 0) E [0, 1] beyond only loss:
Definition 2.1 (Based on Nakkiran and Bansal [2020]). An algorithm T(S) satisfies š-distributional
generalization for all Φ : x θ > [0,
E
(z:
E (z; 8.
(1)
SND"
SN2"
2-5
Z~D
By the variational characterization of the total-variation (TV) distance [see, e.g., Polyanskiy and
Wu, 2014, Chapter 6.3], Equation (1) is equivalent the bound dTv(PI, S 8, where P1 and Po are both distributions of (z, T(S)) over the randomness of S ~ D and the training algorithm T(-).
with the difference that 2 ~ S in the case of P; (train), and z ~ D in the case of Po (test).
might seem that DG only ensures average closeness of bounded tests on train and test data. This not, however, the full picture. Consider generalization in terms of a broader class of functions:
3

---

Definition 2.2 (Kulynych et al. [2022]). An algorithm T(S) satisfies (ó, x) -)ddsstribuutinall generaliza- tion if for a given property function x : TD x θ + R it holds that dTv( (T; P1, me Po) S 6, where my! P the distribution of π (1') for T
Because TV distance is preserved under post-processing. we can see that ò-distributional generaliza- tion implies (6, π disttribbution generalization for all property functions. Informally, 8-DG means that for all numeric property functions <T 0) of a model, the distributions of the property values are close the train and test data, on average. This fact captures the high-level idea of the "What You See is What You Get" (WYSIWYG) guarantee. Some example property functionn:
Subgroup loss: x(2; = 1(2 E G) E(2; 0), for some subgroup G C D.
Counterfactual fairness: <((z, 0) fo(2') - fo(x), where x' is a counterfactual version of x had it had a different value of a sensitive attribute [Kusner et al., 2017].
Robustness to corruptions: <=; 0) transformation that distorts the example, c.g., by adding Gaussian noise.
()), where A(x) is possibly randomized
Adversarial robustness: x(2; f) (z); 8), where Aa(2) is an adversarial example, e.g. generated using the PGD attack [Madry et al., 2018J.
In the next sections, we show how a training algorithm can provably satisfy DG and therefore provide WYSIWYG guarantees for all properties, including the ones above.
2.2 Distributional Generalization from Stability and Differential Privacy
The connections between privacy, stability, and generalization are well-known. In particular, stability of the learning algorithm--1 its non-sensitivity to limited changes in the training data iittaamm gener- alization [Bousquet and Elisseeff. 2002, Shalev-Shwartz al., 2010]. In turn, differential privacy implies strong forms of stability, thus ensuring generalization through the chain Privacy + Stability + Generalization [Raskhodnikova et al., 2008, Dwork et al., 2015b,a, Wang et al., 2016].
Let us formally define differential privacy:
Definition 2.3 (Differential Privacy [Dwork et al., 2006, 2014]). An algorithm T(S) is (c, 6)- differentially private (DP) if for any two neighbouring datasets differingg by one example- S, of size n, for any subset K C θ it holds that Pr(T(S) E K] S exp(c) Pr(T((') K] + 6.
DP mathematically encodes a notion of plausible deniability of the inclusion of an example in the dataset. However, it can also be thought as strong form of stability [Dwork et al., 2015b]. As such, DP implies other notions of stability. We consider the following notion, which has been studied in the literature under multiple names. In the context of privacy, it is equivalent to (0. diffifferettial privacy, and has been called additive differential privacy [Geng et al., 2019], and cotal-variation privacy [Barber and Duchi, 2014]. In the context of learning, it has been called varia-vai (TV) stability [Bassily et al., 2016]. We take this last approach and refer to it as TV stability:
Definition 2.4 (TV Stability). An algorithm T(S) is 6-TV stable if for any two neighbouring datasets S, S' of size n. for any subset T' C θ holds that Pr(T(S) E K] S Pr(T(S') E K] + d.
is easy to see that (c, 6DP immediately implies TVV stability with:
8' = exp(e) 11++ 5.
From Classical to Distributional Generalization. Similarly to the classical generalization, one way achieve distributional generalization is through strong stability:
Theorem 2.5. Suppose that the training algorithm is 5-TV stable. Then, the algorithm satisfies 5-DG.
We refer to Appendix B for the proofs of this and all other formal statements in the rest of the paper.
As DP implies TV-stability, by Theorem 2.5 we have that DP also implies DG. We show that DP algorithms enjoy a significantly stronger stability guarantee than previously known, which means that the DG guarantee that one obtains from DP is also stronger.
Proposition 2.6. An algorithum which is (c, DDP is also 8' -VV stable with:
exp(e) 1 28
exp(e) +1

---

In Appendix A.2, we discuss the relationship of this result other works in the literature on information- theoretic generalization. In particular, to Steinke and Zakynthinou [2020] whose results can also be used to relate DP and DG. Figure 2 shows that the known bounds quickly become vacuous unlike the bound in Proposition 2.6. In fact, we show that our bound is tight in Appendix B.
1.5
g
0.5
Equation (2)
and Zakyathinnn [2020]
Proposition 2.6 (Oum)
0.5
1
155
2
2.5
3.5
4.5
Figure 2: DG bound from (e, O)-D..
Stronger Distributional Generalization Guarantees, Although DG immediately implies generaliza- tion for all bounded properties, is possible obtain tighter bounds from TV stability. For example, directly applying 5-DG to the subgroup loss property yields bound that decays with the size of the subgroup: accuracy on very small subgroups is not guaranteed to generalize well. In Appendix C. we show that TV stability in fact implies "subgroup DG",, which guarantees that the accuracy on even small subgroups generalizes well in expectation. As another example, in Appendix C.2 we show that TV stability also ensures the generalization of calibration properties of the learning algorithm.
Example Applications
To demonstrate that WYSIWYG a useful property in algorithm design, in the remainder of this paper we use it to construct simple and high-perforning algorithms for three example applications: mitigation of disparate impact of DP, ensuring group-distributional robustness, and mitigation of robust overfitting in adversarial training.
Mitigating Disparate Impact of DP. First, we consider applications which learning presents privacy concerns, e.g., in the case that the training data contains sensitive information. Using training procedures that satisfy DP is a standard way to guarantee privacy in such settings. Training with DP, however, is known to incur disparate impact on the model accuracy: some subgroups of inputs can have worse test accuracy than others. For example, Bagdasaryan al. [2019] show that using DP-SGD-2 standard al algorithm for satisfying DP [Abadi et al., 2016]-in place of regular SGD causes a significant accuracy drop on "darker skin" faces in models trained on the CelebA dataset of celebrity faces [Liu et al., 2015), but a less severe drop on "lighter skin" faces. Our goal is to mitigate such disparate impact. This issue-a quality-of- -f-rrice harm [Madaio et al., 2020]-is but one of many possible harms due to ML systems. We do not aim to mitigate any other broad fairnes--elated issues, nor claim this is possible within our framework.
Formally, we assume the data distribution D is a mixture of m groups indexed by set g = (1..... ..] .m.. such that D E D:D The vector (g:..... qm) E [0, 1]mh represents the group probabilities, with Dm T 1. For given parameters (e, 8). we want to learn model 0 that simultaneously satisfies (c. DD,,, has high overall accuracy, and incurs small loss disparity:
max 9.9 Eg
E [((=;0)] A~DD
- E [[(2;0]] DnDDy
ProurpDiitribuutional Robustness. Next, we consider a setting of grouu-distributionally robust optimization [c.g., Sagawa et al., 2019a, Hu et al., 2018]. If in the standard learning approach we want train a model that minimizes average loss, in this setting, we want minimize the worst-case (highest) group loss. This objective can be used to mitigate fairness concerns such as those discussed previously, as well as to avoid learning spurious correlations [Sagawa et al., 2019a].
Formally, we want to learn a model 0 that minimizes the worst-case group loss:
max 959 I~D, [[(=;0)).
Unlike the previous application, in this setting, we do not require privacy of the training data. We use training with DP as a tool to ensure the generalization of the worst-case group loss.
Mitigating Robust Overfitting. Finally, consider the setting of robustness to test-time adversarial examples through adversarial training [Goodfellow et al., 2014]. A common way to train robust models in this sense in image domains is to minimize robust (adversarial) loss [Madry al., 2018]:
E
max E((Nadvv y):
(5)
(x.g)>D ||
5

---

Algorithm/ DP-IS-SGI (DP Importance Sampling SGD)
Input: Dataset S, loss f(2; f), initial parameters fn, learning rate 17, maximal gradient norm C, noise parameter 0, number of epochs T, sampling rate p. group probabilities (f.....,qmi
for /. = 1,..., T do
Sample batch S. (amplep() with sampling probabilities p(z) - f/ m/m-4
gr- [s:| E \mmax(1, c- c- Vol(2;;) aC I
Gradient elipping
Gradient noise
0. - 1,-1 + n7.9.
The highlighted parts indicate the differences with respect to DP-SGD, We obtain DP-SGD as a special case when we have a single group with = 1 (implying p(z) = p).
where 7 > is small constant. Rice al. [2020] observed that adversarially trained models exhibit "robust overfitting": higher generalization gap of robust loss than that of the regular loss. In this application, similarly aim to use a relaxed version of training with DP tool to ensure generalization of robust loss, thus mitigate robust overfitting.
4 Algorithms which Distributionally Generalize
In this section, we construct algorithms for the applications in Section 3. Our approach follows the blueprint: First, we apply a principled algorithmic intervention that ensures desired behavior on the training data (e.g., importance sampling). Second, modify the resulting algorithm to additionally ensure DG, which guarantees that the desired behavior generalizes to test time.
4.1
DP Training with Importance Sampling
Our first algorithm, DP-IS-SGD (Algorithm 1), is version of DP-SGD [Abadi et al., 2016] which performs importance sampling. DP-IS-SGD is designed to mitigate disparate impact while retaining DP guarantees. The standard DP-SGD samples data batches using uniform Poisson subsampling: Each example in the training set is chosen into the batch according to the outcome of a Bernoulli trial with probability ğ [0. 1]. To correct for unequal representation and the resulting disparate impact, we use non-uniform Poisson subsampling: Each example 2 E has a possibly different probability p(z) of being selected into the batch, where p(z) does not depend on the dataset S otherwise, and is bounded: 0 S p(2) S p" I 1. We denote this subsampling procedure as Samplep()(S).
We assume that we know to which group any 2 = (ar,) belongs, denoted as g(=), e.g., the group is one of the features in We choose p(z) to satisfy two properties. First, to increase the sampling probability for examples in minority groups: p(z) x 3//gin)- Second, to keep the average batch size equal to n as in standard DP-SGD. In the rest of the paper, we assume that the group probabilities (q)...., (m) are known, but it is possible to estimate them a private way using standard methods [Nelson and Reuben, 2020]. We present DP-IS-SGD in Algorithm 1, along with its differences to the standard DP-SGD.
DP Properties of DP-IS-SGD. Uniform Poisson subsampling is well-known to amplify the privacy guarantees of an algorithm [Chaudhuri and Mishra, 2006, Li et 2012]. For example, Li al. [2012] show that if an algorithm T(S) satisfies 5c, then T o (S) provides approximately (O(pc), (((pc).p8)-D DDP for small values of c. We show in Appendix B that non-uniform Poisson subsampling provides the same amplification guarantee with p = p², where p" is the maximum value of p(-).
As this guarantee is independent of the internal workings of T(S), it is loose. For DP-SGD, one way of computing tight privacy guarantees of subsampling is using the notion of Gaussian differential privacy (GDP) [Dong et al., 2019]. GDP is parameterized by a single parameter p. If an algorithm T(S) satisfies G-GDP, one can efficiently compute a set of (c, 6 guarantees also satisfied by T(S) [Dong et al., 2019]. We show that we can use any GDs-based mechanism for computing the privacy guarantee of DP-SGD to obtain the privacy guarantees of DP-IS-SGD in black- box manner: Proposition 4.1. Let us denote by p(p, o, C,T) (see Algorithm 1) a function that returns a μ-GDP guarantee of DP-SGD. Then, DP-IS- SSD satisfies GDP guarantee p(p", o. C, T)

---

4.2 Gaussian Gradient Noise
We showed that DP-IS-SGD enjoys theoretical guarantees for both DP and DG. DP models, however, often have lower test accuracy compared to standard training [Chaudhuri et al., 201 I]. This can be an unnecessary disadvantage in settings where privacy is not required, such as in our robustness applications. Thus, we explore training algorithms which are inspired by our theory yet do not come with generic theoretical guarantees DG.
Note that DP-SGD uses gradient clipping and noise (see Algorithm I), Individually, these are used as regularization methods for improving stability and generalization [Hardt et al., 2016, Neelakantan et al., 2015]. Following this, we relax DP-IS-SGI to only use gradient noise. This sacrifices privacy guarantees in exchange for practical performance. Specifically, we apply gradient noise three standard algorithms for achieving group couup-ditributionall robustness: importance sampling (IS-SGD), importance weighting (IW-SGD) [Gretton al., 2009], and gDRO [Sagawa et al., 2019a]. This results in the following variations: IS-SGD-n, IW-SGD-n, gDRO-n, respectively. Similarly, we apply gradient noise to standard PGD adversarial training [Madry et al., 2018]. See Appendix for details.
5
Experiments
We empirically study the distributional generalization in real-world applications. The code for the experiments is available at https:// htt///gttttbbb/ com wonn/yanggrbiter/dp--ar
Datasets. We use the following datasets with group annotations: CelebA [Liu et al., 2015], UTK- Face [Zhang et al., 2017J. iNaturalist0017 (iNat) [Horn et al., 2018), CivilComments [Borkan et al., 2019], MultiNLI [Williams al., 2018. Sagawa et al., 2019a], and ADULT [Kohavi al., 1996]. For every dataset, each example belongs to one group (e.g., CelebA) or multiple groups (e.g.. Civil- Comments). For example. in the CelebA dataset, there are four groups: "blond male", "male with other hair color", "blond female", and "female with other hair color". Additionally, we use the CIFAR- 10 [Krizhevsky et al., 2009] dataset for the adversarial-overfittng application. We present more details on the datasets, their groups, and used model architectures in Appendix E.
5.1 Enforcing DG in Practice
We empirically confirm that a training procedure with DP guarantees also has a bounded DG gap.
In practice, it is not possible to compute the exact DG gap. As
1.0
a proxy in applications which concern subgroup performance
group accurary
Train
in this section, and Sections 5.2 and 5.3, we use the difference
Test
between train-time and test-time worst-group accuracy. This (a)
0.8
follows the empirical approach by Nakkiran and Bansal [2020]
which proposes to estimate the gap in Equation (1) using a finite set of test functions, and (b) measures the aspect of distributional generalization that is relevant to our applications. We provide more details on this choice of the proxy measure in Appendix E.2.
0.2
10
102
108
10
10
SGD
Privacy budget
We train a model on CelebA using DP-SGD for varying levels of Figure 3 shows that the gap between training and testing worst- group accuracy increases as the level privacy decreases, which is consistent with our theoretical bounds. In Appendix E.3 we also explore how regularization methods which do not necessarily formally imply DG, can empirically improve DG.
Figure 3: Privacy induces DG. Train/test worst-case group accu- racies as function of privacy pa- rameter of DP-SGD CelebA (x axis). Increasing privacy re- duces the generalization gap.
5.2 Disparate Impact of Differentially Private Models
We evaluate DP-IS-SOL SGD (Algorithm 1), and demonstrate that it can mitigate the disparate impact in realistic settings where both privacy and faimess required.
Figure shows the accuracy disparity, test accuracy, and worst-case group accuracy, computed as in Equation (3), as function of the privacy budget The models are trained with DP-SGD and DP-IS-SGD. When comparing DP-SGD and IP-IS-SGD with the same or similar 6, we observe that DP-IS-SGD achieves lower disparity all datasets. However, this comes with drop in average
7

---

1.0
Worst-group accuracy
Accuracy dispurity
0.8
DPD
0.6
Test aocummy
0.4
0.4
DP-SGD
DP-SGD
0.2
DP-IS SGD
0.2
DP-IS SGD
10
15
20
10
15
20
0
10
15
20
Prinacy budger
Princcy budget
Privacy budget
(a) Accuracy disparity (lower better)
(b)
Worst-group accuracy (higher is better)
(c) Test accuracy (higher better)
Figure 4: Importance Sampling Improves Disparate Impact of DP-SGD. The accuracy disparity of the models trained with DP-SGD and DP-IS-SGU on CelebA. Adding importance sampling (IS) improves disparate impact at most privacy budgets in this setting. We set 8 1/2n, where the number of training examples. We use GDP accountant to compute the privacy budget E.
accuracy. On CelebA, with E [2, 12). DP-IS-SGD has around 8 p.p. lower test accuracy than DP-SGD. the same time, the disparity drop ranges from 40 p.p. to 60 p.p., which significantly higher than the accuracy drop. We observe similar results UTKFace. On iNat, however, although DP-IS-SGD decreases disparity, the overall test accuracy suffers a significant hit. This is likely because the minority subgroup is very small, which results in high maximum sampling probability p". thus deteriorating the privacy guarantce. Details for UTKFace and iNat are in Appendix E.4.
In summary. we find that DP-IS-SGIL can achieve lower disparity at the same privacy budget compared to standard DP-SGD, with mild impact on test accuracy.
Comparison to DP-SGD-F [Xu et al., 2021]. DP-SGD-F is a variant of DP-SGD which dynamically adapts gradient-clipping bounds for different groups reduce the disparate impact. We did not manage to achieve good overall performance of DP-SGD-F on the datasets above. In Appendix E.4, we compare DP-IS- DP-IS-SGD on the ADULT dataset (used by Xu et al. [2021]), D) finding that DP-IS- SGD obtains lower disparity for the same privacy level, yet also lower overall accuracy.
5.3
Group-Distributionally Robust Optimization
We investigate whether our proposed versions of standard algorithms with Gaussian gradient noise (Section 4.2) improve group-distributional robustness. To do so, evaluate empirical DG using worst-group accuracy as a proxy for DG gap as Section 5.1, following the evaluation criteria in prior work [Sagawa et al., 2019a, Idrissi et al., 2022]. State-of-the-art (SOTA) methods apply l2 regularization and carly-stopping to achieve the best performance. We compare three baselines with l2 regularization, IS-SGD-(2, IW-SGD-&2, and gDRO-(2 to our noisy-gradient variations as well as DP-IS-SGD. We use the validation set to select the best- pesst-erffrming regularization parameter and epoch (for early stopping) for each method. See Appendix E.5 for details on the experimental setup.
Table shows the worst- group accuracy of each algorithm on five datasets. When comparing IS-SGD, IW-SGD, and gDRO with their noisy counterparts, we observe that the noisy versions in general have similar or slightly better performance compared to non-noisy counterparts. For instance, IS-SGD-n improves the SOTA results on CivilComments dataset. This showcases that in terms of learning distributionally robust models, noisy gradient can be a more effective regularizer than the currently standard la regularizer. We also find that DP-IS-SGD improves on baseline methods or even achieves SOTA-competetitive performance on several datasets. For instance, on CelebA and MNLI, DP-IS- SGD achieves better performance than IS-SGD-f2. This is surprising, performance. This suggests that distributional robustness and privacy are not incompatible goals. Moreover, DP can be useful tool even when privacy is not required.
DP tends to deteriorate
5.4 Mitigating Robust Overfitting
As in the previous section, we expect that a modification of standard projected gradient descent (PGD) method for adversarial training [Madry et al., 2018] with added Gaussian gradient noise (Section 4.2) improves the generalization behavior of adversarial training.
IGD numbers are different from Fig. 1, as in the figure do not apply regularization.

---

Table I: Our noisy-gradient algorithms produce competitive results compared to counterparts with l regularization. The table shows worst-group accuracy of each algorithm. Baselines are in the top rows; our algorithms are in the bottom. For EDRO--2-SOTT we show avg. + std. over five runs from Idrissi al. [2022]. For CelebA, we show avg. = std. over three random splits.
CelehA
U'KKFace
iNat.
Civil.
MNLI
SGD-&
73.0 +
86.3
41.8
57.4
67.9
IS-SGD-C;
82.4 - 0.5
85.8
70.6
64.3
70.4
IW-SGD-f2
89.0 0.9
86.5
67.6
65.7
68.1
gDRO-f2
84.5 + 0.8
85.2
67.3
67.3
75.9
eDRO-E2-SOTA
86.9
69.9 + 0.5
78.0
+ 0.3
DP-IS-SGD
86.0 0.8
82.5
51.4
70.4
72.3
IS-SGDan
84.9 1.0
85.5
71.0
71.9
70.8
IW-sGD-n
88.5 + 0.4
88.5
70.9
69.9
69.7
gDRO-n
83.3
87.5
56.4
71.3
78.0
Robust accurccy gap
0.3
0.50
Ourr Early stopping
Robust accuracy
Ours Early stopping
0.45
0.1
0
10"3
10-22
10-3
10
Noise parameter
Noise parameter
(a) Gen, of robust accuracy (lower is better)
(b) Robust accuracy (higher is better)
Figure 5: Noisy gradient reduces overfitting adversarial training. We show the generalization gap of robust accuracy (left), and test-time robust accuracy (right) of adversarially trained models with different levels of noise magnitude. The dash orange lines represent the performance of adversarial training with early stopping. The model trained without noise exhibits "robust overfitting" of about 30 p.p. Gradient noise reduces the generalization gap by more than 3x for all values of the noise parameter at a cost of decreased robust accuracy as the noise gets larger.
To verify this, we adversarially train models the CIFAR-I0 dataset with varying levels of the noise magnitude. We provide more details on the setup in Appendix E.6. Figure 5 shows that in standard adversarial training without noise the gap between robust training accuracy and robust test accuracy is large at approximately 30 p.p., which consistent with the prior observations of Rice et al. [2020]. By injecting noise into the gradient, accuracy by more than x to less than 10 p.p. Surprisingly, in our experiments, training with gradient noise achieves both small adversarial accuracy gap and better adversarial test accuracy compared to standard adversarial training, when using small noise magnitude (a = 5 x 10-1). In terms of resulting robust accuracy, the method's 's performance is comparable to early stopping, identified as the most effective way to prevent robust overfitting by Rice et al. [2020]. These experimental results demonstrate how WYSIWYG can be useful design principle in practice.
proposed approach decreases the generalization gap of robust
6 Related Work
DP and Strong Generalization. DP is known to imply stronger than standard notion of gen- eralization, called robust generalization" [Cummings et al., 2016, Bassily et al., 2016). Robust generalization can be thought as a high-probability counterpart of DG: generalization holds with high probability over the train dataset, not only on average over datasets. We focus on our notion of DG for both conceptual and theoretical simplicity. A more comprehensive discussion of relations to robust generalization is in Appendix A. It can also be usefuul to consider intermediary definitions, varying in strength from DG to robust generalization. In Appendix C, we introduce such an notion ("strong DG") and show its connections to DP. Other than robust generalization, our connections in
Unrelated to "robust overfitting" in adversarial training.

---

Section 2 can also be derived from weaker generalization bounds that rely on iinoormation-thhorrttee measures [Steinke and Zakynthinou, 2020]. We detail this in Appendix A.2.
Disparate Impact of DP. Bagdasaryan et al. [2019], Pujol et al. [2020] have shown that ensuring DP in algorithmic systems can cause error disparity across population groups. Xu et al. [2021] proposed a variant of DP-SGD for reducing disparate impact. We compare our method to DP-SGD-F in Appendix E.4, In another line of related work, Sanyal al. [2022], Cummings al. [2019] show fundamental trade-offss between model's 's loss and DP training. As our theoretical results concern generalization, not loss per se, our results do not contradict these theoretical trade-offs. We discuss the relationship in detail in Appendix A.3.
linup- robustness aims to improve the worst-case group performance. Existing approaches include using worst-case group loss [Mohri et al., 2019, Sagawa al., 2019a, Zhang al., 2020], balancing majority and minority groups by reweighting or subsampling [Byrd and Lipton, 2019, Sagawa et al., 2019b, Idrissi et al., 2022], leveraging generative models [Goel al., 2020], and applying various regularization techniques [Sagawa al., 2019a, Cao et al., 2019]. Although some work [Sagawa et al., 2019a, Cao et al., 2019] discusses the importance of regularization in distributional robustness, they have not explored potential reasons for this (e.g. via the connection to generalization). Another line of work studies how to improve group performance without group annotations [Duchi al., 2021, Liu et al., 2021, Creager et al., 2021], which is a different setting from ours as we assume the group annotations are known.
Group-Distribun Di---iitttbuiionall Robustness.
Robust Overfitting. Rice al. [2020], Yu al. [2022] have shown that adversarially trained models tend to overfit in terms of robust loss. Rice et al. [2020] proposed to use regularization to mitigate overfitting, but the noisy gradient has not been explored for this. We showed that the WYSIWYG framework can serve as an alternative direction for mitigating and explaining this issue.
7 Conclusions and Future Work
We argue that a "What You See is What You Get" property, which we formalize through the notion of distributional generalization (DG), can be desirable for learning algorithms, as it enables principled algorithm design in settings including deep learning. We show that this property is possible to achieve with DP training. This enables us to leverage advances in DP to enforce DG in many applications.
We propose enforeing DG a general design principle, and use it construct simple yet effective algorithms in three settings. In certain fairness settings, we largely mitigate the disparate impact of differential privacy by using importance sampling and enforcing DG in our new algorithm DP- IS-SG.. In our analysis, however, the privacy and DG guarantees of DP-IS-SGI deteriorate in the presence of very small groups. Future work could explore ledividual-level accounting [Feldman and Zrnic, 2021] for tighter analysis. In certain worst-case generalization settings, inspired by DP-SGD, we propose using noisy-gradien regularizer. Compared to SOTA algorithms in DRÓ, noisy gradient achieves competitive results across many standard benchmarks. In certain adversarial- robustness settings, our proposed moisy-gradien regularizer significantly reduces robust overfitting. An interesting direction for future work would be to explore its effectiveness in large-scale settings, e.g., ImageNet [Croce and Hein, 2022]. We hope future work can explore extending this design principle to ensure generalization of other properties, such as calibration and counterfactual fairness.
Acknowledgements
We thank Kamalika Chaudhuri, Benjamin I.. Edelman, Saurabh Garg, Gautam Kamath, Maksym Andriushchenko, and Cassidy Laidlaw for useful feedback support from the Swiss National Science Foundation with grant 100021-18883 thanks NSF under CNS 1804829 and ARO MURI W91 1991NF2110N 10317 for the research support. DMS grant #203 PN
early draft. BK acknowledges Yang
Yaodong Yu acknowledges support from the joint Simons Foundation is grateful for support of the NSF and the Simons Foundation for the Collaboration on the Theoretical Foundations of Deep Learning through awards DMS-20 1883 and #814639.
httpe:///eeptoondatioon...
10

---

References
Martin Abadi, Andy Chu, lan Goodfellow, Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, 2016.
Eugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov. Differential privacy has disparate impact on model accuracy. Advances in Neural Information Processing Systems 32: Annual Conference Neural Information Processing Systems (NeurIPS), 2019.
Rina Foygel Barber and John Duchi. Privacy and statistical risk: Formalisms and minimax bounds. arXiv preprint 1412:4441..451, 2014.
Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman. Algorithmic stability for adaptive data analysis. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC, 2016.
Elettra Bietti. From ethics washing to ethics bashing: a view on tech ethics from within moral philosophy. In Proceedings of the Conference on Fairness, Accountability, and Transparency, 2020.
Daniel Borkan, Lucas Dixon, Jeffrey Sorensen, Nithum Thain, and Lucy Vasserman. Nuanced metries for measuring unintended bias with real data for text classification. In Companion proceedings of the 2019 World Wide Web conference, 2019.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2002.
Yuheng Bu, Shaofeng Zou, and Venugopal V Veeravalli. Tightening mutual information-bant based bounds on generalization error. IEEE Journal on Selected Areas in Information Theory, 2020a.
Zhiqi Bu, Jinshuo Dong, Qi Long, and Weijie J Su. Deep learning with gaussian differential privacy. Harvard data science review, 2020b.
Joy Buolamwini and Timnit Gebru. Gender shades: Intersectional accuracy disparities in commercial gender classification. In Conference fairness, accountability and transparency. 2018.
Jonathon Byrd and Zachary Chase Lipton. What is the effect of importance weighting in deep learning? In Proceedings of the 36th International Conference Machine Learning, ICML, 2019.
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with label-distributionn-aaar margin loss. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems (NeurIPS), 2019.
Kamalika Chaudhuri and Nina Mishra. When random sampling preserves privacy. In Annual International Cryptology Conference. Springer, 2006.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 2011.
Elliot Creager, Jörn-Henrik Jacobsen, and Richard Zemel. Environment inference for invariant learning. In Proceedings of the 38th International Conference on Machine Learning, ICMI,, 2021.
Francesco Croce and Matthias Hein. On the interplay of adversarial robustness and architecture components: patches, convolution and attention. arXiv preprint arXiv:2209.06953. 2022.
Rachel Cummings, Katrina Ligett, Kobbi Nissim, Aaron Roth, and Zhiwei Steven Wu. Adaptive learning with robust generalization guarantees. In Proceedings of the 29th Conference Learning Theory, COLT, 2016.
Rachel Cummings, Varun Gupta, Dhamma Kimpara, and Jamie Morgenstern. On the compatibility of privacy and fairesss. In Adjunci Publication of the 27th Conference on User Modeling, Adaptation and Personalization, 2019.
11

---

Jacob Devlin, Ming-Woi Wei Chang, Kenton Lee, and Kristina Toutanova. BERT; Pre- Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Volume I (Long and Short Papers), 2019.
Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. arXiv preprint arXiv: arXiv:/905.022 1905.02333 2019.
John C Duchi, Peter W Glynn, and Hongseok Namkoong. Statistics of robust optimization: A generalized empirical likelihood approach. Mathematics of Operations Research, 2021.
Cynthia Dwork, Frank McSherry. Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference. Springer, 2006.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor: Comput. Sci., 2014.
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. Generalization in adaptive data analysis and holdout reuse. In Advances Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 1- 2015, Montreal, Quebec, Canada, 2015a.
Cynthia Dwork, Vitaly Feldman. Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. Preserving statistical validity adaptive data analysis. In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing, STOC, 2015b.
Vitaly Feldman and Tijana Zrnie Individual privacy accounting via a Renyi filter. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems (NeurIPS), 2021.
Quan Geng, Wei Ding, Ruiqi Guo, and Sanjiv Kumar. Optimal noise-adding mechanism in additive differential privacy. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS, 2019.
Karan Goel, Albert Gu, Yixuan Li, and Christopher Re. Model patching: Closing the subgroup perfor- mance gap with data augmentation. In 8th International Conference on Learning Representations, ICLR, 2020.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.65777 2014.
Arthur Gretton, Alex Smola, Jiayuan Huang, Marcel Schmittfull, Karsten Borgwardt, and Bernhard Schölkopf. Covariate shift by kernel mean matching. Dataset shift machine learning, 2009.
Mahdi Haghifam, Jeffrey Negrea, Ashish Khisti, Daniel M Roy, and Gintare Karolina Dziugaite. Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems (NeurIPS), 2020.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In Proceedings of the 33nd International Conference on Machine Learning, ICML, 2016.
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis F. Oliphant. Array programming with NumPy. Nature, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR, 2016.
12

---

Grant Van Horn, Oisin Mac Aodha, Yang Song, Yin Cui, Chen Sun, Alexander Shepard, Hartwig Adam, Pietro Perona, and Serge J. Belongie. The inturallist species classification and detection dataset. In 2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR, 2018.
Weihua Hu, Gang Niu, Issei Sato, and Masashi Sugiyama. Does distributionally robust supervised learning give robust classifiers? In Proceedings of the 35th International Conference on Machine Learning, ICMI,, 2018.
Badr Youbi Idrissi, Martin Arjovsky, Mohammad Pezeshki, and David Lopez-Paz. Simple data balancing achieves competitive worst-group-aceurase In Conference Causal Learning and Reasoning, 2022.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In Proceedings of the 32nd International Conference on Machine Learning, ICML, 2015.
Allison Koenecke, Andrew Nam, Emily Lake, Joe Nudell, Minnie Quartey, Zion Mengesha, Connor Toups, John R Rickford, Dan Jurafsky, and Sharad Goel. Racial disparities in automated speech recognition. Proceedings of the National Academy of Sciences, 2020.
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Bal- subramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al. Wilds: A benchmark of in-the-wild distribution shifts. In Proceedings of the 38th International Conference on Machine Learning, JCML, 2021.
Ron Kohavi et al. Scaling up the accuracy of Naive-Baye Bayes classifiers: A decision-tree hybrid. In KDD, 1996.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Bogdan Kulynych, Mohammad Yaghini, Giovanni Cherubin, Michael Veale, and Carmela Troncoso. Disparate vulnerability to membership inference attacks. Proceedings on Privacy Enhancing Technologies, 2022.
Matt J. Kusner, Joshua R. Loftus, Chris Russell, and Ricardo Silva. Counterfactual faimesss In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems (NeurIPS), 2017.
Ninghui Li, Wahbeh Qardaji, and Dong Su. On sampling, anonymization, and differential privacy k-anonymization meets differential privacy. In Proceedings of the 7th ACM Symposium Information, Computer and Communications Security, 2012.
Evan Z Liu, Behzad Haghgoo, Annie S Chen, Aditi Raghunathan, Pang Wei Koh, Shiori Sagawa, Percy Liang, and Chelsea Finn. Just train twice: Improving group robustness without training group information. In Proceedings of the 38th International Conference on Machine Learning, ICML, 2021.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In 2015 IEEE International Conference on Computer Vision, ICCV 2015, Santiago, Chile, December 7-13, 2015, 2015.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In 7th International Conference on Learning Representations, ICLR, 2019.
Michael A Madaio, Luke Stark, Jennifer Wortman Vaughan, and Hanna Wallach. Co-designing checklists to understand organizational challenges and opportunities around fairness in ai. In Proceedings of the 2020 CHi Conference on Human Factors in Computing Systems, 2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In 6th International Conference on Learning Representations, ICLR, 2018.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Proceed- ings of the 36th International Conference on Machine Learning, ICML, 2019.
13

---

Preetum Nakkiran and Yamini Bansal. Distributional generalization: A new kind of generalization. arXiv preprint arXiv:2009.0809) 2020.
Hongseok Namkoong and John C. Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. In Advances in Neural Information Processing Systems 29:
Annual Conference on Neural Information Processing Systems (NeurIPS), 2016.
Arvind Neelakantan, Luke Vilnis, Quoe V Le, Ilya Sutskever, Lukasz Kaiser, Karol Kurach, and James Martens. Adding gradient noise improves learning for very deep networks. arXiv preprint arXiv:1511006877, 2015.
Boel Nelson and Jenni Reuben. SoK: Chasing accuracy and privacy, and catching both in differentially private histogram publication. Trans. Data Priv., 2020.
The pandas development team. pandas-dew/pandas:: Pandas, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer. James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, nigh-performance deep learning library. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems (NeurIPS), 2019.
Yury Polyanskiy and Yihong Wu. Lecture notes on information theory. 2014.
David Pujol, Ryan McKenna, Satya Kuppam, Michael Hay, Ashwin Machanavajjalla and Gerome Miklau. Fair decision making using privacy-protected data. In Proceedings of the Conference on Fairness, Accountability, and Transparency, 2020.
Sofya Raskhodnikova, Adam Smith, Homin K Lee, Kobbi Nissim, and Shiva Prasad Kasiviswanathan. What can we learn privately. In Proceedings of the 54th Annual Symposium on Foundations of Computer Science, 2008.
Leslie Rice, Eric Wong, and Zico Kolter. Overfitting in adversarially robust deep learning. In Proceedings of the 37th International Conference on Machine Learning. ICML., 2020.
Daniel Russo and James Zou. How much does your data exploration overfit? controlling bias via information usage. IEEE Transactions on Information Theory, 2019.
Shiori Sagawa, Pang Wei Koh, Tatsunori Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. 2019a.
arXiv preprint arXiv:
Shiori Sagawa, Aditi Raghunathan, Pang Wei Koh, and Percy Liang. An investigation of why overparameterization exacerbates spurious correlations. In Proceedings of the 37th International Conference on Machine Learning, ICML, 2019b.
Amartya Sanyal, Yaxi Hu, and Fanny Yang. How unfair is private learning? arXiv preprint arXiv:2206.03398, 2022.
Shai Shalev- Shwlev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 2010.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In IEEE symposium on security and privacy 2017.
Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual information. In Conference on Learning Theory, 2020.
Grant Van Horn and Pietro Perona. The devil in the tails: Fine-grained classification in the wild. arXiv preprint S0KV:1770.01444 2017.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. Nelson, Eric Jones, Robert Kern, Eric Larson, CJ Carey, Ilhan Polat, Yu Feng. Eric W. Moore, Jake VanderPlas,
14

---

Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 2020.
Yu-Xiang Wang.
Per-instance differential privacy. arXiv preprint arXiv:1707.07700 2017.
Yu-Xiang Wang, Jing Lei, and Stephen E Fienberg. Learning with differential privacy: Stability, learnability and the sufficiency and necessity of erm principle. The Journal of Machine Learning Research, 2016.
Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 2010.
Adina Williams, Nikita Nangia, and Samuel Bowman. A broad-coverage challenge corpus for sentence understanding through inference. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Volume 1 (Long Papers), 2018.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. Huggingface's transformers: State-of-ther -frt---rttee-tttt natural language processing. arXiv preprint 1rXiv:1910.03771, 2019.
Aolin Xu and Maxim Raginsky. Information-ttheoreii analysis of generalization capability of learning algorithms. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems, 2017.
Depeng Xu, Wei Du, and Xintao Wu. Removing disparate impact on model accuracy in differentially private stochastic gradient descent. In Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery & Data Mining, 2021.
Yao-Yuan Yang, Cyrus Rashtchian, Hongyang Zhang, Ruslan Salakhutdinov, and Kamalika Chaud- huri. A closer look accuracy robustness. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems (NeurIPS), 2020.
Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj, Jessica Zhao, Graham Cormode, and Ilya Mironov, Opacus: User-friendly differential privacy library in PyTorch. arXiv preprint arXiv:2109. 12298, 2021.
Chaojian Yu, Han, Li Shen, Jun Yu, Chen Gong, Mingming Gong, and Tongliang Liu. Understand- ing robust overfitting of adversarial training and beyond. In Proceedings of the 39th International Conference on Machine Learning, ICML, 2022.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In Proceedings of the 36th International Conference on Machine Learning, ICML, 2019.
Jingzhao Zhang, Aditya Menon, Andreas Veit, Srinadh Bhojanapalli, Sanjiy Kumar, and Suvrit Sra. Coping with label shift via distributionally robust optimisation. arXiv preprint arXiv:2010. /2230, 2020.
Zhifei Zhang, Yang Song, and Hairong Qi. Age progression/rerrssionn by conditional adversarial autoencoder. In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR, 2017.
15

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We address the limitations where appropriate, c.g., high-level limitations in Section 3, and the fact that some methods we use in the empirical evaluations deviate from theory in Sections 4 and 5.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] In Section 3 we caution against using WYSIWYG for fairnes-washingg [Bietti, 2020] through technical solutionism. Other than this, our potential negative societal impacts are the same as with any other academic work which aims to improve the performance of deep learning: applications that are harmful, e.g., is beyond the scope of our work to discuss such broad issues.
risk improving performance of deep learning in downstream or violating other civil liberties.
(d) Have you read the ethies review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix B.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] We included the experiment code supplemental material.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Appendix E.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] For experimental settings in which it was feasible for us to repeat experiments multiple times, we reported the standard errors (Table 1).
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix E.I.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] See Appendix E.
(b) Did you mention the license of the assets? [Yes] See Appendix E.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes] See Appendix E.
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [Yes] See Appendix E.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "naFUHFTXVTt", "reviewer": "Reviewer_cawT", "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. ", "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. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n- The notion that ensuring DG implies that behavior generalises to the test data is interesting. \n- The concept that regularization methods improve DG is interesting (at least numerically). \n- The paper is well-written and I enjoyed reading it. \n- The numerical results are interesting. \n\nCons:\n- 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. \n- 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. \n- 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. \n- 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. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "bLBUrOySXT4", "reviewer": "Reviewer_XhyC", "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.", "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)).\n2. 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?\n", "limitations": "The limitations are addressed in Section 3.", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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:\n\n1. The theory part is very well written and easy to understand. It nicely builds a bridge between DP and distributional robustness.\n2. The algorithms make a lot of sense, and they show that noisy gradients can be a better regularizer than standard L2 regularization.\n\nThe 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "M2jaVdqaPJF", "reviewer": "Reviewer_QRKD", "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.", "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?\n\n\n* 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.\n\n* 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.\n\n* 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.\n\n\n[1] Bagdasaryan, Eugene, Omid Poursaeed, and Vitaly Shmatikov. \"Differential privacy has disparate impact on model accuracy.\" Advances in neural information processing systems 32 (2019).  \n[2] Pujol, David, et al. \"Fair decision making using privacy-protected data.\" Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency. 2020.  \n[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.   \n[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.  \n[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.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n\n* 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.\n* 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.\n\nWeakness\n\nI 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.\n\n* To show applications of the framework, the claims to experiment on   \n  i. Group Distributionally Robust Optimisation and   \n  ii. mitigate the disparate impact of DP.   \n  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.\n\n\n* 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.\n\n\n[a] Steinke, Thomas, and Lydia Zakynthinou. \"Reasoning about generalization via conditional mutual information.\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "EKnVtUeH21R", "reviewer": "Reviewer_4obB", "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. \n", "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. ", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \nI 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”. \n\nWeaknesses: \nI 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. \n\nIn 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. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept