Limits of Algorithmic Stability for Distributional Generalization
Authors: Neha Hulkund
Vinith Menon Suriyakumar
Taylor W. Killian
Marzyeh Ghassemi
Venue: Submitted to ICLR 2023 (2023)
Keywords: Distribution Shift
Robustness
Evaluation

Abstract: As machine learning models become widely considered in safety critical settings, it is important to understand when models may fail after deployment. One cause of model failure is distribution shift, where the training and test data distributions differ. In this paper we investigate the benefits of training models using methods which are algorithmically stable towards improving model robustness, motivated by recent theoretical developments which show a connection between the two.  We use techniques from differentially private stochastic gradient descent (DP-SGD) to control the level of algorithmic stability during training. We compare the performance of algorithmically stable training procedures to stochastic gradient descent (SGD) across a variety of possible distribution shifts - specifically covariate, label, and subpopulation shifts. We find that models trained with algorithmically stable procedures result in models with consistently lower generalization gap across various types of shifts and shift severities. as well as a higher absolute test performance in label shift. Finally, we demonstrate that there is there is a tradeoff between distributional robustness, stability, and performance.

Under review as a conference paper at ICLR 2023
LIMITS OF ALGORITHMIC STABILITY FOR DISTRIBU- TIONAL GENERALIZATION
Paper under double-blind review
ABSTRACT
As machine learning models become widely considered in safety critical settings, it is important to understand when models may fail after deployment. One cause of model failure is distribution shift, where the training and test data distributions differ. In this paper we investigate the benefits of training models using methods which are algorithmically stable towards improving model robustness, motivated by recent theoretical developments which show a connection between the two. We use techniques from differentially private stochastic gradient descent (DP-SGD) control the level of algorithmic stability during training. We compare the perfor- mance of algorithmically stable training procedures stochastic gradient descent (SGD) across a variety of possible distribution shifts specifically covariate, label, and subpopulation shifts. We find that models trained with algorithmically stable procedures result in models with consistently lower generalization gap across vari- ous types of shifts and shift severities as well as a higher absolute test performance in label shift. Finally, demonstrate that there is there is tradeoff between dis- tributional robustness, stability, and performance.
INTRODUCTION
As machine learning (ML) is applied in several high-stakes decision making situations such as healthcare (Ghassemi et al. 2017 Rajkomar et al. 2018 ZZang et al. 2021a) and lending (Liu et al.) 2018 Weber et al./ (020)), are trained with empirical risk minimization (ERM), which assumes that the training and test data are sampled i.i.d from the same underlying distribution [Vapnik 1999). Unfortunately. this assump- tion means that ERM is susceptible to performance degradation under distribution shift (Nagarajan al.] (222T). Distribution shift occurs when the data distribution encountered during deployment different, or changes over time while the model is used. In practice, even subtle shifts can signifi- cantly affect model performance (Rabanser et al., 2019). Given that distribution shift is significant source of model failure, there has been much work directed toward improving model robustness to distribution shifts TTooi et al. 2020 [ohhen et al. 2019 Engstrom et al. 2019 Geirhos et al.) 2018
important to consider scenarios when models fail. Typically, models
Zhang al.
2019 Zhang 2019).
One concept recently introduced to improve model robustness is distributional generalization (Ku-
lynych et al. 2022 Nakkiran & Bansal 2020: Kulynych al.] (220). Distributional generalization
(DG) extends classical generalization to encompass any evaluation function (instead of just the loss objective) and allows the train and test distributions to differ. Kulynych al. (2022) prove that al- gorithms which satisfy total variation stability (TV stability) bound the gap between train and test metrics when distribution shift is present, i.c., algorithms which satisfy TV stability are also satisfy DG. This motivates the use of techniques from differentially private (DP) learning to satisfy DG, since DP implies TV stability (Kulynych et al. 2022). We know from other works that DP learning often comes at cost to accuracy (Bagdasaryan et al.) 2019, (Suriyakumar et al.) 2021 Jayaraman & Evans 2019). Unfortunately these works don't it thoroughly explore the empirical implications of their theorems across wide variety of settings except for positive result in Suriyakumar et al. 20221) Because robustness to new settings is an important question for deployments of models, important to understand how the theory of distributional robustness will work practically when facing different types and severities of shifts. Furthermore, it is hard to understand from the current theory how practitioners should tune the level of stability as achieve high performing models.

---

Under review as a conference paper at ICLR 2023
In this paper we conduct extensive empirical study on the impact of using algorithmically sta- ble learning strategies for robustness when facing distribution shift. Stable learning (SL) refers to approaches that constrain the model optimization objective
learning algorithm to improve model stability. We focus on two questions regarding the use of SL. for DG in practice: (i) Under what types of shift is SL more robust and accurate than ERM? (ii) Are SL. trained models consistently robust across all hyperparameters, model architectures, and shift severities? We target four common
examples of shift: covariate (Shimodaira) 2000), label (Lipton et al. 2018 Storkey 22009, subpop- ulation (Duchi & Namkoong [222]] Koh et al.) (021), and natural shifts Taori et al. (2020). We use state of the art models and large benchmark datasets focusing on realistic prediction tasks in object recognition, satellite imaging, biomedical imaging. and clinical notes (see Table [ with details in Section (.2). The primary comparison we make is through the generalization gap, defined as the dif- ference in model performance between training and testing (Zhang et al. [202Tb). Under extensive cnerimennaaiionnncopprrn
32 distinct types of distribution shift and 5 severity levels-we find:
1. SL improves both accuracy and robustness for label and natural shifts.
2. SL has a robustness caassttneesscccracyy tradeoff for covariate and subpopulation shift.
3. The tradeoff's of SL are consistent across different shift severities, model architectures, and hyperparameter settings.
2 RELATED WORK
Many approaches have been developed in pursuit of robustness distribution shift, including: domain adaption (Wang & Deng, 2018), out-of-distributin sarial training (Madry et al., 2018 [lyas et al. 2019), as well as through algorithmic improve- ments (Sagawa et al., (019). To solve the distribution shift problem, many recent techiques for distributionally robust optimization (DRO), such as risk averse learning (Curi et al. 2020), have
detection (Yang et al. (021). adver-
been developed. However, many of these methods do not perform better than ERM Pfohl et al. 2022) and involve complex implementations, making them difficult to use.
Algorithmic stability has also been explored to improve distributional robustness. It is often easier to implement, with simpler methods such as: & regularization (Wibisono et al.) 2009), early stop- ping (Hardt et al., 2016), and differentially private stochastic gradient descent (DP:SGD) AAbadi et al. 2016). Early stopping and l2 regularization have already been studied for their potential to improve distributional robustness (Sagawa et al. 2019). However, it's difficult to conduct fine- grained analyses into improved robustness with these methods because their stability is not directly controllable. This motivates our use of DP-SGD to investigate the limits of stability for DG since we can control the level of stability by adjusting the noise multiplier a in DP-SGD. While algorithmic stability has been explored theoretically in previous works (see Section B in this paper across various synthetic and natural distribution shifts.
we explore it empirically
3 BACKGROUND AND NOTATION
We provide an overview of the connections between algorithmic stability, DP, and different forms of generalization in this section. It is well-established that algorithmic stability implies generalization in the traditional ERM setup (Bousquet & Elisseeff 2002). Additional work has proven that DP implies stability and thus, implies generalization (Bassily et al. 2016; Dwork al. 2015). In this section we define these concepts and draw connections between them. This is done to clarify the theoretical implication that DP leads improved distributional robustness.
Notation We assume there is a training dataset Dirain = {(x,, }i) of labeled examples ,)) such that Devain D and testing dataset Dtest = {xx, 9:) pm of labeled examples such that Drest ~ D'. Given Drrain: we use a randomized learning algorithm M(Drrain) to learn parame- ters 0 O of a model relating the datapoints (2r.) to their corresponding label (v)).
Now we will describe differential privacy and its links to stability.
Definition 1 (Differential Privacy (Dwork et al. 2006)). Suppose we have two datasets D. D' which have a Hamming distance (the number of examples which the two databases differ by) of 1, then an algorithm M(D) is (c, 5) -iifferrentilll private if:
2

---

Under review as a conference paper at ICLR 2023
Pr(M(D) O exp(E)Pr(M(())) e -
where θ C Ra)ge(M).
By definition, DP guarantees privacy by bounding the effect that any individual datapoint has on the output of M. This leads DP implying strong forms of stability such as TV stability (Bassily al.) 2016) and uniform stability (Wang et al. (016). Next, we will define these notions of algorithmic stability and show how DP implies them both.
Definition (TV Stability), Suppose we have two datasets D, D' which have a Hamming distance of I, then an algorithm M(D) is (5)-TV stable if:
Pr(M(D) E 0) Pr(M(D)) +
We can also write this as the upper bound on the total variation distance between two distribu- tions P and Q where ~ P and D' Q between M(D) and M(D'). Where drv (P,Q) =
supr (P(T) - Q(T),, then TV stability is (D, D') < 6.
Definition (Uniform Stability (Bousquet & Elisseeff 2002)). ). Suppose we have two datasets D, D'
which have Hamming distance of 1, then an algoritim M (D) is (8)-uniformly stable if:
VD, D' D'I
(((():((D) - EE(D: 8
(3)
If the loss function 8 is bounded between [0.1] then TV stability implies 5-uniform stability (Ku- lynych al. 2022). All of these definitions assume we are sampling D and D' from the same underlying distribution. When distribution shift ocurrs, this is no longer true. Thus, will present the results of Kulynych et al. (2022) who demonstrate that TV-stable algorithms satisfy a notion of generalization that captures distribution shift known distributional generalization.
Definition (Distributional Generalization (Kulynych et al. 2022 Nakkiran Bansal 2020 Ku-
lynych et al. 2020)), Given two datasets D and D' sampled from two different distributions P and Q, an algorithm M(D satisfies 6-distributional generalization (DG) for all d; x θ [0,
E E d(D; D' D' ~Q D
M(D: 8
(4)
DNP
Kulynych et al. (2022) prove that any algorithm which is 8-TV stable is 8-DG. Thus implying that algorithmic stability improves robustness to distribution shift. The level of TV stability and DG which are parameterized by are directly correlated with level of noise a we use DP-SGD. Throughout the rest of the paper, the larger a is the more stable the algorithm is (i.e. the lower ō is).
4 METHODS
To better understand the potential and limits for using algorithmic stability improve model ro- bustness we conduct a thorough empirical study across several datasets, types of shifts, and shift severities. We explore both synthetic and natural distribution shifts that arise due differences in the covariate, label, and subpopulation distributions between training and testing (Table [T]. Our empirical investigation covers more than 200 experiments, incorporating 32 distinct forms distri- bution shift with varying levels of severity.
In each of our experiments-giiv given training dataset Dtrain and test dataset Diest with known dis- tribution shift-we compare the difference in generalization gap (Definition 5) of models with and without algorithmic stability ("stable learning" (SL)) and ERM respectively. Characterizing this gap is important step to determine how well the theoretical guarantees of DG hold in practice.
We aim to provide answers to the following critical questions about practical use of SL for DG, motivating its use beyond theory: (i) Under what types of shift is SL more robust and accurate than ERM? (ii) Are SL trained models consistently robust across all hyperparameters, model architec- tures, and shift severities?
3

---

Under review as a conference paper at ICLR 2023
Shift Type
Size Dataset
Prediction Task
Performance
CIFARIOCC
Synthetic Covariate
105,000
end to-end CNN
Classification
Accuracy
Imbalanced CIFARIO
Synthetic Label
115,000
end eend-to-edddd CNN
Classification
Accuracy
Waterbirds
Synthetic Subpopulation
4,795
Logistic Regression
Classification
Woost-rrup Accuraey
COOS
Natural Covariate
cad-lo-end ResNett8 132,209
Classificttion
Accuracy
PovenyMap
Natural Subpopulation Label
end
Regression
Peunson Coefficient
MIMIC-III III
Natural Subpopulation & Label
25,879
Logistic Regression
Mortality
Worst Group AUC
Table 1: The datasets, prediction tasks, and model architectures used throughout the paper to evalu- ate the relationship between algorithmic stability and distribution shift.
4.1 DISTRIBUTION SHIFT
We present and define the three different kinds of distribution shifts that we explore in empirical study.
Consider joint distribution DD between features X and labels Y, D X x Y, with training data Dtrain and testing data Drest. We define distribution shift to be any change to the marginal, condi- tional, or joint distributions of X and Y between Derain and Drest, based on prior work (Quionero- Candela et al., 2009 Rabanser et al. 2019: Duchi & Namkoong 2018). We explain the three types of shift below:
Covariate shift occurs when the features X change between training and testing, but the pre- diction given a feature stays the same, such that P(Xtrain) # P(Xtest), P(Y (train) P(Ytest tesst). A natural example of covariate shift arises when datasets of MRI images are recorded by different machines, providing different features but not changing disease prevalence.
Label shift is when the distribution of labels changes, but the class-conditional densities are con- stant, such that P(Yerain) * P(Ytest), P(Xerain| (trai)) = P(XeesalYesst This shift occurs when one class is overrepresented in the dataset, but the underlying feature distribution is conditionally cquivalent.
Subpopulation shift is when the distribution of subpopulations (e.g. subgroups defined by the intersection of sex and race) changes. Define G be a discrete random variable representing mem- bership in subpopulation. Subpopulation shift occurs when 3g E G s.t. P(Xirains Ytrain G 9) * P(Xtest, Yreet|Ge G = g). For example, when we move between rural and urban medical centers the proportion of subpopulations changes where minority populations are less represented in rural settings.
Natural shift are those where the training and test distributions different from real-world data collection, without additional manipulation of data. These natural shifts can be combinations of covariate, label, subpopulation, and other types of shifts.
4.2 DATASETS
We investigate synthetic covariate, label, and subpopulation shifts, as well as naturally occurring instances of covariate and subpopulation shifts. We use the definition of natural and synthetic shift from Taori et al. (2020). Synthetic shifts are those where the data originally is all from the same distribution but is manipulated such that the training and test distributions are different. Meanwhile, natural shifts are those where the training and test distributions are already different.
Synthetic datasets: For covariate shift, we use the CIFAR10 1 dataset, created by shifting CI- FAR10's test set with 19 types of algorithmically generated corruptions of 5 different severities for a total of 95 different synthetic covariate shifts (Hendrycks & Dietterich) 2019). For synthetic la- Cwwelaaned--IFAFEER
bel shift, we use
which we created by inducing class imbalance in CIFAR1O to create shift in P(Y). These shifts were created randomly, where the percentage of of samples in the shifted dataset from the original test dataset 10 100%. To explore synthetic subpopulation shifts, we use the Waterbi dataset (Sagawal al. 2019 made up of bird images with synthetic backgrounds.
chosen randomly from
4

---

Under review as a conference paper at ICLR 2023
Natural datasets: Our natural covariate shifts derived from the Lalss-Outoo--ammppee (COOS) dataset, which consists of mouse cell images of 7 biological classes, with separate test sets of increasing degrees of covariate shift (Lu et al. 2019). We also explore natural subpopulation and label shifts with the FovertyMap dataset predicting poverty levels from satellite imagery (Koh et al.
202T), and MIMIC-III clinical notes predicting mortality (Johnson et al., 2016).
For more detailed information about the datasets used in this paper, please refer to Appendix A.2
4.3 MODEL TRAINING
We train models using DP-SGD (with varying levels of noise and clipping as a way to modify the amount of stability, as detailed in Appendix(A.I.2 Appendix A.3) A..3) and ERM for each dataset and type of shift. Each model is trained with early stopping on the validation loss to prevent overfitting. The scale of the hyperparameter search and noise levels used for determining the best performing models can be found in Appendix|A.3] For all experiments, we use the Opacus package (Yousefpour al. 2021) Tensorflow Privacy package (McMahan & Andrew 2018 to implement DP-SGD. Models and data references are given in T Note that the models used for the CIFAR dataset (Tramer & Boneh, 202I) in covariate and label shift are small models created for differential pri- vacy, to mitigate the dimensional dependence of DP-SGD Yu et al. (2017). Thus, the reported ERM test accuracy is lower than state-of-the- thht--rrt performance using larger model architectures such as the ResNet (He et al.) (016) on the same dataset. When we compare against distributionally robust op- timization (DRO) results, we use the conditional value risk (CVaR) optimization algorithm (Lévy
al. 2020
4.4
EXPERIMENTAL PROCEDURE
For each pair of Dtrain and Drest in an experiment, we perform the following procedure:
Train set of models {M1 My..... (performing hyperparameter search) on Dtrain with DP-SGD using different noise multiplier values {ar, .2.... as varying levels of algorith- mic stability. We also train ERM (not stable) and DRO (another stable algorithm) models as comparative baselines. SL. models are trained with DP-SGD, detailed in Appendix Appenddi(AA1.2]
Test each model in the sets [M1, M2,...} } on shifted testing datasets {D', D'.... While covariate and subpopulation shift have shifted test datasets, label shift has shifted training dataset, as practitioners would see in a scenario of class-imbalanced training data.
Measure the generalization gap G. the difference between training and testing accuracy for SL and ERM models, Gst. and GERM. To measure the improvement SL has over ERM, we report the difference in generalization gap Ag as defined in Definition below.
4.5 EVALUATION
We design our empirical investigation to answer the two previous questions posed at the outset of Section on the limits of using SL for distributional robustness. We address them as follows:
(i) The metric we use to primarily compare the robustness of models is the difference in generaliza- tion gap, AG (Definition [5) If Ag > this indicates that the model trained with a stable learning algorithm has lower generalization gap and is therefore more robust than ERM trained models. As mentioned in Section 4.4 we test across various levels of stability to find the optimal value.
Definition 5 (Difference Generalization Gap). Given the training and D and D' sampled from two different distributions P and Q an ERM model M MERM (D) and alternate training algorithm A with model (D) and metric Φ: D x > R we define the generalization gap as:
Sa
B (D: D-P.D - DDD MERM p D~p
E (D::
E D-P.D aa
(D' Ma())
(5)
We calculate Ag for SL/DRO compared to ERM, referred SL /DROO Ag-
(ii) We investigate if stability holds over different shift severities using the synthetic datasets by evaluating for which shifts is Ag > Shift severity is characterized as the distance between Dirain
5

---

Under review as a conference paper at ICLR 2023
Sknn Severy
mntn
1800 MC
T800 a00
Acamcy Gin
St.Ac
DR0 Aoceccy Gann
DR0 Ag:
Neer
2,33 0J0ILL
0,773 0.0004
IL768 8L165
(L710) 0,115
0,700 0.002
1U0T & 0.115
0001
0.113
0.119 2 11167
.0000 2 0.01
0004
0002
2/121 0112
5472
6,229
0,202
D.021
0.100 (161
10061 Ca1
0012 BC13
0/819 11880
0.8661100000
BLtt 30090
0.844
11002
-0001
HANT
-0I 14055
B.08 0.M1
0,837 0.09
0.619 0.007
5130
0.321
0.00
0.558
-0.33 0.005
0.055
-0.01 4-55
-0001
0.688:-0.007
0.788 8:120
0.000 0.104
0.886 0.085
0:904200.00
-0.00:2:00000
0.000 0.000
-0854
000 0,000
01644200111
Table 2: SL demonstrates an accuracy-robustness tradeoff in the CIFAR-C dataset representing synthetic covariate shifts. We observe that for all shifts, SL Ag 0, indicating that each SL model is more robust than ERM. However, there is consistent loss in accuracy for both SL. We present results across five shift severities for a 0.1. We observe similar tradeoff for the DRO CVaR algorithm, indicating that these algorithms cannot improve both robustness and accuracy with covariate shift.
Shift Severity
ERM train ace
ERM test acc
SL train
SL test acc
Accuracy Gain
Ag
None
0.913 0.002
0.861 + 0.020
0.852 = 0.093
0.796 + 0.123
-0.068 + 0.089
0.007 : 0.084
0.817 0.202
+ 0.232
0.790
0.748
-0.031 0.009
-0.004
0.900 0.267
0.777 + 0.282
0,812 = 0.120
0.749 + 0.161
-0.028 + 0.121
0.054 + 0.025
0.897 0.250
0.773 + 0.251
0.812 + 0.109
0.742 + 0.157
-0.031 + 0.094
0.054 + 0.048
0.870 + 0.197
0.715 +: 0.207
0.813 + 0.134
0.7331 :: 0.155
0.018 + 0.052
0.074 + 0.011
5
0.937 + 0.265 0.765 + 0.200
0.850 + 0.000 0.731 + 0.160
-0.034 + 0.041
0.053 + 0.154
Table 3: SL demonstrates accuracy-robustnes tradeoff in the Waterbirds datasets represent- ing synthetic subpopulation shifts. We observe that for all shifts, Åg >> O, indicating that each SL model is more robust than ERM. However, there is consistent loss in accuracy. We present results across five shift severities for = 0.1.
and Deest. We use the Optimal Transport Dataset Distance (OTDD) (Alvarez-Melis & Fusi 2020). We choose this metric as opposed to other dataset distances for its provable guarantees and that it allows for completely disjoint datasets to be compared. We categorize our synthetic datasets by shift severity by first normalizing the computed OTDD and sorting them into quintiles 1-5.
(iii) To explore the tradeoff between robustness and accuracy, we also report model performance throughout the paper and compare it to Ag. Model performance is reported as accuracy except for MIMIC-III III and PovertyMapy where area under the curve (AUC) and Pearson Correlation Coef- ficient are used, respectively, due to change in classification task (See Table In MIMIC IIII lated work focuses on AUC because it the standard metric used for diagnostics. Thus, we use AUC since it is the standard for evaluating clinical prediction models for mortality. In Povert yMap, predicts a real-valued composite asset wealth index from satellite images, and thus, the models are evaluated on the Pearson correlation (r) between their predicted and actual asset wealth indices.
STABILITY HAS POOR ROBUSTNESS TOBUSTNESS-ACCURACYY TRADEOFFS FOR COVARIATE AND SUBPOPULATION SHIFTS
In this section, we examine results from our synthetic covariate and subpopulation experiments seen in Table and Table 3 We investigate potential sources of why this tradeoff exists.
We observe that for all shift severities in covariate CIFAR-C and subpopulation naterbirds. SL has increased robustness as compared to ERM, with ÅG > O. However, for both shifts there is tradeoff between robustness and accuracy, seen by the consistent negative accuracy gains, which increases with shift severity.
We also find that SL is more robust on the natural covariate shifted COOS but at the expense of accuracy (Table[). We find that this result holds across all values of stability we tried. This negative finding not surprising because each of the shifts in COOS covariate shifts.

---

Under review as a conference paper at ICLR 2023
Shift Severity
SL train acc
SL acc
ERM train ace
ERM test acc
Accuracy Gain
AG
1
0.872
0.840
0.907
0,852
-0. 012
0.022
2
0.872
0.843
0.907
0.853
-0.010
0.024
3
0.872
0.810
0.907
0.706
0.166
0.033
4
0.872
0.467
0.907
0.559
-0.092
-0.056
Table 4: SL is more robust to most natural shifts found in COOS except for the most severe. This is most likely due lower model accuracy. These results are for 0.1. Standard deviations not provided because of computational constraints.
To gain insight into the nature this robustness-accurage tradcoff, we compare SL to a DRO algo- rithm that optimizes conditional value at risk (CVaR). Through empirical investigation that both methods fail on covariate shift (see Table 2 More interestingly, these methods are failing for different reasons. Investigation into the underlying cause has led to the formulation of follow- ing conjecture: We believe that SL mimics learning under a transformation of P(X) such that becomes closer the uniform distribution as increase the level of stability.
uncover
With enough uniform stability, P(X) would be the Uniform distribution, equivalent to eliminating all signal from the covariates and predicting randomly. Similar to covariate shift, as SL approaches the uniform distribution, information about the changed P(X [G) during subpopulation shift is lost. In contrast, the DRO CVaR optimization focuses on the tails of the distribution Levy al. (2020) providing limited utility for most covariate/subpooulatii shifts which oftentimes apply the same transform to every point the distribution (Shimodaira) 2000, Duchi Namkoong 2018).
These results and the corresponding conjecture lead to the conclusion that SL under uniform stability not a good candidate for improving robustness under covariate or subpopulation shift, comes at major cost to accuracy.
STABILITY IMPROVES ROBUSTNESS AND ACCURACY TO LABEL SHIFT AND NATURAL SHIFTS
In this section, demonstrate that stability improves both robustness and accuracy to label shifts and natural shifts. Furthermore, we investigate potential sources this improvement compared to ERM. We draw similarities between importance weighting, distributionally robust optimization, and stable learning to help understand these improvements.
We demonstrate these results first variety of label shifts Imbalanced-CIPA (Table 5 Even as the shift severity increases, SL outperforms ERM, with Ag > 0 and a positive accuracy gain. However, these improvements occur specific level of stability a 0.1 (i.e. the amount of noise in DP-SGD), At stronger levels of stability we find that robustness is better than ERM at the expense of accuracy (Table This the first result of many throughout our work which indicates that level of stability is hyperparameter which should be tuned to find the best level of robustness and accuracy.
We demonstrate similar improvements when testing against natural distribution shifts. SL improves both robustness and accuracy on MIMIC-III and yovertyMap (Table(6). Specifically, we see an increase in accuracy of 2.9% and and 1 11.3% and increase in robustness of 4.2% and 0.8% respec- tively. Similar to our label shift results we had to une the level of stability, again supporting the observation that it is a hyperparameter that must be tuned.
We first investigate why stability outperforms ERM on both robustness and accuracy on label shifts. We demonstrate that stable learning (especially those that satisfy uniform stability like DP-SGD) mimics training that we would see if our training label distribution was uniform over all labels. We show this by showing similar results when training with DRO (to mimic uniform label distribution) (Talle3). We show both of these methods also improve accuracy and robustness to a similar degree that SI. does.
7

---

Under review as a conference paper at ICLR 2023
skn Seortyy
aor
In8 aor
Annrnyy Gals
St.Ae
D60 Acninay Cats
TRD Age
0.776 0.342
0,57 0.177
0/83 4 0.985
0.300 0.081
0.31
0.886 0.00
0.13 = 0,62
0/099 4: 0,091
0.007 0.00
0.563 0.09
5824
0,88
0.0022
0.00
0.088
0035 0.121
11300
11:18
0083
0.000
0106 10104
01301
6469911000
IUMS 0.106
0.001 0.064
0.09 C.15
0/044
0000 0.200
0:500
0.178
4-0.33
0.311
+-0.111
0.655
0.191 0.117
0.864
0.186 0.003
0100
0.07
0004
3415
0.670
0.502
0,644-00022
Table 5: SL improves robustmess and accuracy models to label shift in Imbalanced-CIFAR, We present results across five shift severities for a 0.1. We observe that for all shifts, Ag O, indicating that each SL model is more robust and accurate than ERM in the presence of label shifts. We observe improvements both robustness and accuracy for the DRO CVaR algorithm. indicating that there is no tradeoff between the two.
Dataset
ERM train perf
ERM test perf
SL train pert
SL test perf
Performance Guin
AG
MIMIC-III Notes
0.840 0.008
0.039
0.827
0.000
0.843
0.035
0.029
+
PavertyMap
0.626 0.152
0.138
0.727 0.085 0.602
0.113 0.046
0.008 0.004
Table 6: SL improves robustness and performance of models in the presence of natural subpopula- tion shifts. Here we use 0.1 for MIMIC-III and 0.001 for PovertyMap.
Natural shifts more difficult to accommodate than synthetic shifts because they are usually com- posed of multiple shifts. It is more difficult to train models to be robust against combinations of shifts because most methods are developed deal with single type of shift. Given that natural shifts are much harder than synthetic shifts we investigate why it is that SL is more accurate and robust. We identify that the datasets we considered contain combination of shifts which make up the natural shift. Both MIMIC-III and PovertyMap contained both subpopulation and label shift. Thus, we believe that the improvement in performance and robustness is in part due SL. being a much better learning algorithm for dealing with label shift.
CONSISTENCY OF STABLE LEARNING
a)
Covariate Shift
b)
Label Shift
C)
Subpopulation Shift
1.0
DP
0.8
1.0
DP
Testing accuracy
Testing acuracy
0.7
Testing accuracy
0.8
0.8
0.6
0.5
0.4
0.3
0.2
0.2
0.2
0.0
0.0
1.0
Training accuracy
Training accuracy
Training accuracy
Figure 1: Stability is consistent across hyperparameters. We plot the training vs. testing accu- racy across representative examples of a) covariate, b) label, and c) subpopulation shift from the CTFAR10-G6 Imba 1 www.ndncFFFaa and Waterbi rds datasets, respectively. Fach point in the graph represents different hyperparameter experiment for the dataset. SI follows the y x line more closely than ERM, indicating that the generalization gap of SL is lower than ERM and consis- tent across hyperparameters.
In this section, investigate answers to query (ii) in Section We explore to what level of stability is needed and how consistent the results of the above two sections are across different model architectures and hyperparameters.
8

---

Under review as a conference paper at ICLR 2023
Rooustness Accuracy in CIFAR Covariete Shift
Robustness Vs Accuracy CIFAR Label Shift Accuracy
Rohundness
Robuss
2.03
St. a..ggrmmm
0.33
Fefferece Gan Gapl
fefeerncc Dach
3.92
0.4
LAM
2.53
6005
605
23
232
816
0.5
04
03
12
04
26
58 Nultoler
22
Nutpler
Nose
(a) Accuracy and Ag of covariate shift across stability (b) Accuracy and Ag of label shift across stability lev- levels
cls
Figure 2: Robustness to distribution shift and accuracy are at odds for covariate shift and label shift when stable learning for models trained on CIFAR-C and Imbalanced-CIT respectively. This tradeoff worsens as the level of stability is increased.
7.1 Low LEVELS OF STABILITY ARE NEEDED TO IMPROVE ROBUSTNESS
Overall, low levels of stability are required improvements over ERM. From Table 8 Table I1 and Fig. 2 observe that while increasing stability leads to a lower generalization gap. decreases performance. Over all settings, We find that for larger values because stability is guaranteed by use of noise in DP-SGD this results in much worse accuracy. In practice, the amount of stability needed balance this tradeoff is model and dataset dependent. As such, stability can be treated as hyperparameter to be tuned for robustness (similar to regularization), rather than a guaranteed solution.
found that < 0.5 best balances securacy-robustnes tradeoff'.
7.2 BENEFITS STABLE LEARNING ARE CONSISTENT ACROSS ARCHITECTURES AND HYPERPARAMETERS
In our experiments we consistently observed lower generalization gaps across all hyperparameter settings of SL models. This indicates that the robustness improvements provided by SL hold across different model settings, and are not simply a result of well-chosen hyperparameters. In Fig. [ we examine three representative covariate, label, and subpopulation shifts. We find that the SL models more closely follow the ideal generalization trendline (in black) where the train set performance is equal the
performance.
Additionally, we find that our results hold across a variety of commonly used model architectures. Specifically,
variety of CNNs and logistic regression models across tasks and find that the findings do not change based on the model architecture. This is expected since algorithmic stability agnostic architecture and hyperparameter choices by definition.
CONCLUSION
Our study investigates the utility of stability as tool for improving both robustness and accuracy to different distribution shifts. We find that by design, stability improves robustness at the expense of accuracy for both covariate shift and subpopulation shift. Meanwhile, also by design, stability improves both robustness and accuracy to label and natural shifts. We determine that this is be- cause of the equal importance that uniform stability places on every data point in the training set. Finally, we show that these results are consistent across hyperparamters, model architectures, and shift severities.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 308-318, 2016.
David Alvarez-Melis and Nicoló Fusi. Geometric dataset distances via optimal transport. ArXiv, hass/2002002923, 2020.
Eugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov. Differential privacy has disparate impact on model accuracy. Advances in Neural Information Processing Systems, 32, 2019.
Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman. Algorithmic stability for adaptive data analysis. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 1046-1059, 2016.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learn- ing Research, 2:499-526, 2002.
Irene Chen, Fredrik D Johansson, and David Sontag. Why is my classifier discriminatory? In Advances in Neural Information Processing Systems, pp. 3539-3550, 2018.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. International Conference on Machine Learning. pp. 1310-1320, PMLR, 2019.
Sebastian Curi, Kfir Levy, Stefanic Jegelka, and Andreas Krause. Adaptive sampling for stochastic risk-averse learning. Advances in Neural Information Processing Systems, 33:1036-1047, 2020.
Agatha CH de Mattos, Gavin McArdle, and Michela Bertolotto. Mapping slums with medium resolution satellite imagery: comparative analysis of multi-spectral data and grey-level co- occurrence matrix techniques. arXiv preprint (tti::2006.11999)) 2021.
John Duchi and Hongseok Namkoong. Learning models with uniform performance via distribution- ally robust optimization. arXiv preprint arXiv:/810.08750, 2018.
John C Duchi and Hongseok Namkoong. Learning models with uniform performance via distribu- tionally robust optimization. The Annals of Statistics, 19(3):1378-11) 1406, 2021.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. Theory of cryptography conference, pp. 265 284. Springer, 2006.
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toni Pitassi, Omer Reingold, and Aaron Roth. Gen- eralization in adaptive data analysis and holdout reuse. Advances in Neural Information Process- ing Systems, 28, 2015.
Logan Engstrom, Brandon Tran, Dimitris Tsipras, Ludwig Schmidt, and Aleksander Madry. Ex- ploring the landscape of spatial robustness. In International Conference on Machine Learning, pp. 1802-1811. PMLR, 2019.
Robert Geirhos, Patricia Rubisch, Claudio Michaelis, Matthias Bethge, Felix Wichmann, and Wieland Brendel. Imagenet-trained cnns are biased towards texture; increasing shape bias im- proves accuracy and robustness. In International Conference on Learning Representations, 2018.
Marzyeh Ghassemi, Mike Wu, Michael C Hughes, Peter Szolovits, and Finale Doshi-Velez, Pre- dicting intervention onset in the icu with switching state space models. AMIA Summits Trans- lational Science Proceedings, 2017:82, 2017.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochas- tic gradient descent. In Maria Florina Balcan and Kilian Q Weinberger (eds.). Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learming Research, pp. 1225- 1234, New York, New York, USA, 20-22 Jun 2016. PMLR. URL htttps://proceeee
mlr. p.eess / v48 8/ http//arrtt...... html
Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
10

---

Under review as a conference paper at ICLR 2023
Dan Hendrycks and Thomas G. Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. CoRR, abs/1903.12200 2019. URL attp://arxiv.or
29s//193..12611
Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry. Adversarial examples are not bugs, they are features. In Advances in Neural Information Processing Systems, pp. 125-136, 2019.
Bargav Jayaraman and David Evans. Evaluating differentially private machine learning in practice. In 28th {USENIX} Security Symposium ((USENIX) Security 19). pp. 1895-1912, 2019.
Alistair E. W. Johnson, Tom Pollard, Lu Shen, Li-wei H. Lehman, Mengling Feng, Mohammad Ghassemi, Benjamin Moody, Peter Szolovits, Leo Anthony Celi, and Roger G. Mark. MIMIC-
III, a freely accessible critical care database. Scientific Data, 3(1):1 May 2016. ISSN
2052-4463. doi: 10. 10300//dataa.2116.35.. URL httpp:://wwt http:://wwwwaaate..mmm
nature. www.:ttrree.oorortteeeeeeee www.ariaiaatts...../o/o....
sdat
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 International Conference on Machine Learning. pp. 5637-5664. PMLR, 2021.
Bogdan Kulynych, Mohammad Yaghini, Giovanni Cherubin, and Carmela Troncoso. Disparate vulnerability: on the unfairness of privacy attacks against machine learning. In 22nd Privacy Enhancing Technologies Symposium (PETS 2022), volume
2020. http:
//arxiv.org/aaaaa..v. abs 00389
Bogdan Kulynych, Yao-Yuan Yang, Yaodong Yu, Jaroslaw Blasiok, and Preetum Nakkiran. What you see is what you get: Distributional generalization for algorithm design in deep learning. arXiv preprint arXiv:2204. 20..200.0 03230, 2022.
Daniel Lévy, Y. Carmon, John C. Duchi, and Aaron Sidford. Large-scale methods for distribution- ally robust optimization. ArXiv, abs/2010.05893, 2020.
Daniel Levy, Yair Carmon, John C Duchi, and Aaron Sidford. Large-scale methods for distribution- ally robust optimization. Advances in Neural Information Processing Systems, 33:8847-8860, 2020.
Zachary Lipton, Yu-Xiang Wang, and Alexander Smola. Detecting and correcting for label shift with black box predictors. In International conference machine learning, pp. 3122-31 3130. PMLR, 2018.
Lydia T Liu, Sarah Dean, Esther Rolf, Max Simchowitz, and Moritz Hardt. Delayed impact of fair machine learning. International Conference on Machine Learning, pp. 3150-3158. PMLR, 2018.
Alex X. Lu, Amy X. Lu, Wiekke Schormann, David W. Andrews, and Alan M. Moses. The cells of sample (COOS) dataset and benchmarks for measuring out-of-sample generalization of image classifiers. CoRR, abs/1906.07282, 2019.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
H. B. McMahan and Galen Andrew. A general approach to adding differential privacy to iterative training procedures. ArXiv, abs/1 /bb//182..06210 2018.
Vaishnavh Nagarajan, Anders Andreassen, and Behnam Neyshabur. Understanding the failure modes of out-of-distribution generalization. In International Conference on 1 Learning Repre- sentations, 2021. URL
b
Preetum Nakkiran and Yamini Bansal. Distributional generalization: A new kind of generalization. arXiv preprint 20Xv:22009.08092. 2020.
11

---

Under review as a conference paper at ICLR 2023
Barak Oshri, Annie Hu, Peter Adelson, Xiao Chen, Pascaline Dupas, Jeremy Weinstein, Marshall Burke, David Lobell, and Stefano Ermon. Infrastructure quality assessment in africa using satel- lite imagery and deep learning. In Proceedings of the 24th ACM SIGKDD International Confer- ence on Knowledge Discovery & Data Mining, pp. 616-625, 2018.
Stephen R Pfohl, Haoran Zhang, Yizhe Xu, Agata Foryciarz, Marzyeh Ghassemi, and Nigam H Shah. A comparison of approaches improve worst-case predictive model performance over patient subpopulations. Scientific reports, 12(1):1-13, 2022.
Joaquin Quionero-Candela, Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence. Dataset shift in machine learning. The MIT Press, 2009.
Stephan Rabanser, Stephan Günnemann, and Zachary Chase Lipton. Failing loudly; An empirical study of methods for detecting dataset shift. In NewrlPS, 2019.
Alvin Rajkomar, Michaela Hardt, Michael D Howell, Greg Corrado, and Marshall H Chin. Ensuring fairness machine learning to advance health equity. Annals of internal medicine, 169(12):8665 872, 2018.
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 generaliza- tion. arXiv preprint arXiv: /9/ /. 1.08731, 2019.
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of statistical planning and inference, 90(2):227-244, 2000.
Amos Storkey. When training and test sets different: characterizing learning transfer. Dataset
shift in machine learning, 30:3-28, 2009.
Vinith M Suriyakumar, Nicolas Papernot, Anna Goldenberg, and Marzyeh Ghassemi. Chasing your long tails: Differentially private prediction in health care settings. In Proceedings of the 2021 ACM Conference on Fairness, Accountabiliry, and Transparency, pp. 723-734, 2021.
Rohan Taori, Achal Dave, Vaishaal Shankar, Nicholas Carlini, Benjamin Recht, and Ludwig Schmidt. Measuring robustness to natural distribution shifts in image classification. Advances in Neural Information Processing Systems, 33:18583-18599 2020.
Florian Tramèr and Dan Bonch. Differentially private learning needs better features (or much more data). ArXiv, abs/201 1.11660, 2021.
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 1999.
C. Wah, S. Branson, Welinder, P. Perona, and Belongie. Caltech-uesd 20rd2-200-2011 dataset. Technical Report CNS-TR-2011-001, California Institute of Technology, 2011.
Mei Wang and Weihong Deng. Deep visual domain adaptation: A survey. Neurocomputing, 312: 135-153, 2018
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, 17(1):6353-639 6392, 2016.
Mark Weber, Mikhail Yurochkin, Sherif Botros, and Vanio Markov. Black loans matter: Distribu- tionally robust fairness for fighting subgroup discrimination. arXiv preprint arXiv:2012.01193, 2020.
Andre Wibisono, Lorenzo Rosasco, and Tomaso Poggio. Sufficient conditions for uniform stability of regularization algorithms. Computer Science and Artificial Intelligence Laboratory Technical Report, CITT-SSII--R.. TR-ALL----200--006 2009-060, 2009.
Michael Xie, Neal Jean, Marshall Burke, David Lobell, and Stefano Ermon. Transfer learning from deep features for remote sensing and poverty mapping. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
12

---

Under review as a conference paper at ICLR 2023
Jingkang Yang. Kaiyang Zhou, Yixuan Li, and Ziwei Liu. Generalized out-of-distribution detection: A survey. ArXiv, abs/21 11334, 2021.
Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Gosh, Akash Bharadwaj. Jessica Zhao, Graham Cormode, and Ilya Mironov. Opacus: User-friendly differential privacy library in pytorch. ArXiv, abs/2109. 12298, 2021.
Yu, Ma, Gronsbell, T. Cai, A.N. Ananthakrishnan, V.S. Gainer, S.E. Churchill, Szolovits, S.N. Murphy, L.S. Kohane, et al. Enabling phenotypic big data with phenorm. Journal of the American Medical Informatics Association, 25(1):54-66 2017.
Haoran Zhang, Natalie Dullerud, Laleh Seyyed-Kalantee Kalantari, Quaid Morris, Shalmali Joshi, and Marzyeh Ghassemi. An empirical framework for domain generalization in clinical settings. Pro- ceedings of the Conference on Health, Inference, and Learning, 2021a
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International conference on machine learning, pp. 7472-7482. PMLR, 2019.
Richard Zhang. Making convolutional networks shift-invariant again. In International conference on machine learning, pp. 7324-7334. PMLR, 2019.
Shufei Zhang, Zhuang Qian, Kaizhu Huang, Qiufeng Wang, Rui Zhang, and Xinping Yi. Towards better robust generalization with shift consistency regularization. In ICMI. 2021b.
Bolei Zhou, Agata Lapedriza, Aditya Khosla, Aude Oliva, and Antonio Torralba. Places: A 10 mil- lion image database for scene recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2017.
13


Reviews:
[{"review_id": "zkcGJ9TgoCI", "reviewer": "Reviewer_iJTD", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper investigates applying differentially private stochastic gradient descent (DP-SGD) for training models towards achieving high robustness against distributional shift. Experiments are done on datasets with covariate, label, or subpopulation shift using various noise multipliers in DP-SGD. The resulting performance is compared with models trained with empirical risk minimization (ERM) in terms of test accuracy and generalization gap.", "summary_of_the_review": "I am familiar with DP-SGD and algorithmic stability, but I have not followed (and did not have time to do so during the short review period) the closely related works by Kulynych et al.. Hence, I might be misunderstanding the contributions. \n\nThe title of the paper is \"limits of algorithmic stability for distributional generalization.\" After reading the paper, I am not sure I got an answer to what those limits are. ", "strength_and_weaknesses": "Strengths:\n- The authors have conducted lots of experiments on various datasets and distribution shift types\n- The experimental details are well documented\n\nWeaknesses:\n- The paper is lacking a message and is unclear what the conclusion from these experiments should be. The authors makes some attempts to justify the use of SL methods for robustness based on their results, but (a) there is quite large variability in the findings (eg whether SL improves both robustness and accuracy, (b) the standard deviations are large in many occasions making the comparisons even more obscure.\n- Overall, I am concerned about the impact of this work given the insufficient justification and explanation of experimental results. What is the reason for different tradeoffs between robustness and accuracy observed for different types of shift? Is it because of the use of the chosen evaluation metric or something else?\n- There is too much variation in the generalization gap for different shift severity levels. For example, for the Imbalanced-CIFAR, it seems strange that at shift severity level 3, the generalization gap is one order of magnitude smaller than others. And for most of them, the standard deviation is large.\n- The experiment results are not conclusive and consistent across datasets. For example,  for label shift with Imbalanced-CIFAR, it seems that there is some improvement in both accuracy and generalization gap of DP-SGD over ERM. However, the improvement in accuracy is not observed when covariate and subpopulation shifts are considered. Again, for natural datasets, no concrete conclusions can be drawn as different shift severity gives different results. \n- The test accuracy on CIFAR appears far from the current state of art. Why not use a larger model to evaluate all metrics?\n- It is not made clear what the novelty is compared to Kulynych et al. 2020,2022?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "gNupogA18a", "reviewer": "Reviewer_JhgW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper praises the training of learning algorithms by incorporating differential privacy techniques. In doing so, the idea is to be able to explicitly control the level of stability in order to be more efficient against perturbations of the data distribution. The results are essentially experimental, through a handful of real database and distribution shift settings.", "summary_of_the_review": "“Unfortunately these works don’t provide any guidance on practical tradeoffs with robustness, except for a small positive result in Suriyakumar et al. (2021).” It seems a bit rude to qualify such a result as “small”.\n“current theory provides no insight into the relationship between the level of stability and other model performance metrics, such as accuracy”. This seems a bit strong, most of the work on algorithmic stability, if not all, explicitly discuss the relation between stability and generalization (and so accuracy).\n\nThe authors raise some key questions in section 4. For example, what level of stability is needed to observe a positive difference between ERM and learning with stability.\n\nHowever, I do not see any clear, unambiguous, quantitative answers to these questions. This is the main criticism of the previous contributions. This seems to depend, of course, on the model used, the current data, the settings of the hyperparameters etc... At most, three algorithms have been tested (CNN, LR, ResNet18).\nThe title seems to be too strong for the content of the article. No theoretical results on the limits of stability are presented, nor a vast and diverse numerical experimentation to support their claim. \n\nTypos: \n- \"was was\" in section 4.2\n- \"it is important\" in section 7\n- \"the the\" in section 4.1\n", "strength_and_weaknesses": "The topic of the paper is very interesting and highly relevant for the AI/ML community. It proposes well-chosen numerically experiments to illustrate the main claim. However, I believe that the questions being tackled cannot be answered robustly without a very large sets of experiments, varying hyperparameter, significantly larger sets of data etc. Or propose a solid theoretical analysis.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "cD4rrrkznb", "reviewer": "Reviewer_weZZ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper empirically investigates the distributional generalization in the context of distribution shift. More specifically, the authors studies the performance of models trained with differentially private stochastic gradient descent (DP-SGD) under different types of distribution shifts---including covariate shift, label shift, and subpopulation shift. Through extensive experiments, the authors identify three interesting findings about stable training: (1). models trained with DP-SGD achieve smaller generalization gap across different types of distribution shifts; (2). Stable training (i.e., DP-SGD training) can serve as an effective way to boost model performance (test accuracy) under certain distribution shifts; (3). Under distribution shifts, there exists a trade-off between stability, model generalization gap, and model performance.", "summary_of_the_review": "This paper studies an important problem in distributional generalization under distribution shifts and obtains interesting and strong empirical results, I would recommend acceptance.", "strength_and_weaknesses": "Strength:\n\n1. The connection between algorithmic stability and model generalization is an interesting topic and has not been extensively studied in the context of distribution shifts empirically. \n\n2. This paper studies three types of distribution shifts, which extends previous work [KYY+2022] and cover a wide range of interesting and practical distribution shifts in practice.\n\n3. The finding on the effectiveness of stable training boost generalization performance under certain distribution shifts (label shifts and natural shifts) is very interesting, which is practically interesting.\n\nWeakness:\n\n1. [minor] The related work section can be further improved, for example, including more related work on the 'robustness to distribution shift' part.\n\nTypos:\n\n1. Typo in Eq. (4), should be $D^{\\prime} \\sim P$.\n\n\n[KYY+2022] Bogdan Kulynych, Yao-Yuan Yang, Yaodong Yu, Jarosław Błasiok, and Preetum Nakkiran. What you see is what you get: Distributional generalization for algorithm design in deep learning. arXiv preprint arXiv:2204.03230, 2022.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "AwkVDLIpuT", "reviewer": "Reviewer_6xKr", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper experimentally investigates the effect of differentially private stochastic gradient training on robustness against three types of distribution shifts. The experiments involve data with synthetically generated distribution shifts as well as natural ones.", "summary_of_the_review": "I believe that the current paper attempts a worthy exploration of an important subject, however it neither states the problem sufficiently clearly nor explore the implications of its results thoroughly.", "strength_and_weaknesses": "The main strength of the paper is that it investigates a potential mitigating algorithmic approach to an important problem; robustness under distribution shift. Although the paper does not have any novel theoretical contributions, I think papers that exhaustively and empirically investigate the implications of novel theoretical output in the field are important contributions, and as such should be encouraged.\n\nHowever I do not believe this paper clears the bar in terms of making a thorough exploration of the questions at hand. The paper examines the implications of research by Kulynych et al. 2022 in three specific forms of distribution shift. First main weakness of the paper is the description of the problem setting. The authors' exposition is confusing rather than clarifying, and I will go more into the details of this in the next section.\n\nMy other main concern is that the authors' investigation falls short of answering the questions posed by their empirical results. Given the paper makes no theoretical or methodological contributions, it would be fair to expect more investigation - at least speculation - regarding the implications of their findings. Some examples of unfollowed leads are:\n\n- That the most severe shifts favor ERM is very important finding in this context, that should have been investigated more - the authors' conclusion \"stability has a limit\" falls short of answering the questions that are provoked by this.\n- Why might the results for synthetic and real distribution shift datasets differ so much?\n- Why do we not observe a robustness - accuracy trade-off consistently?\n- Why should differentially private training confer more robustness to distribution shifts vs. distributionally robust optimization?\n\nWhen I started reading this paper, I thought these would be the exact types of questions investigated by the paper - in absence of this I find the paper's publication hard to justify.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject