Understanding Why Generalized Reweighting Does Not Improve Over ERM
Authors: Runtian Zhai
Chen Dan
J Zico Kolter
Pradeep Kumar Ravikumar
Venue: NeurIPS 2022 Submitted (2022)
Keywords: Distributional Shift
Generalization
Algorithmic Fairness
Class Imbalance

Abstract: Empirical risk minimization (ERM) is known in practice to be non-robust to distributional shift where the training and the test distributions are different. A suite of approaches, such as importance weighting, and variants of distributionally robust optimization (DRO), have been proposed to solve this problem. But a line of recent work has empirically shown that these approaches do not significantly improve over ERM in real applications with distribution shift. The goal of this work is to obtain a comprehensive theoretical understanding of this intriguing phenomenon. We first posit the class of Generalized Reweighting (GRW) algorithms, as a broad category of approaches that iteratively update model parameters based on iterative reweighting of the training samples. We show that when overparameterized models are trained under GRW, the resulting models are close to that obtained by ERM. We also show that adding small regularization which does not greatly affect the empirical training accuracy does not help. Together, our results show that a broad category of what we term GRW approaches are not able to achieve distributionally robust generalization. Our work thus has the following sobering takeaway: to make progress towards distributionally robust generalization, we either have to develop non-GRW approaches, or perhaps devise novel classification/regression loss functions that are adapted to the class of GRW approaches.

Understanding Why Generalized Reweighting Does Not Improve Over ERM
Anonymous Author(s)
Affiliation
Address
email
Abstract
Empirical risk minimization (ERM) is known to be non-robust in practice to distributional shift where the training and the test distributions different. A suite of approaches, such as importance weighting, and variants of distributionally robust optimization (DRO), have been proposed to solve this problem. But line of recent work has empirically shown that these approaches do not significantly improve over ERM in real applications with distribution shift. The goal of this work is obtain a comprehensive theoretical understanding of this intriguing phenomenon. We first posit the class of Generalized Reweighting (GRW) algorithms, as a broad category of approaches that iteratively update model parameters based on iterative reweighting of the training samples. We show that when overparameterized models are trained under GRW, the resulting models are close to that obtained by ERM. We also show that adding small regularization which does not greatly affect the empirical training accuracy does not help. Together, our results show that a broad category of what we term GRW approaches are not able to achieve distributionally robust generalization. Our work thus has the following sobering takeaway: make progress towards distributionally robust generalization, we either have to develop non-GRW approaches, or perhaps devise novel classffication/rerrsssoo loss functions that are adapted to the class of GRW approaches.
10
11
12
14
16
18
Introduction
19
20
has now been well established that empirical risk minimization (ERM) can empirically achieve high test performance on variety of tasks, particularly with modern overparameterized models where the number parameters much larger than the number of training samples. This strong performance of ERM however has been shown degrade under distributional shift, where the training and test distributions are different (HST5) BGO16, [Tt17]. There are two broad categories of distribution shift: domain generalization where the test distribution contains new environments not in the training distribution like in domain adaptation, and subpopulation shift where the two distributions have the
21
22
24
25
26
27
same set of subpopulations but their mixture weights differ like in algorithmic fairness applications.
28 People have proposed various approaches to learn models that are robust to distributional shift. The most classical approach is importance weighting (IW) [Shi00], which reweights training samples; in 30 the context of subpopulation shift these weights are typically set so that each subpopulation/ /goopp has the same overall weight in the training objective. The approach most widely used today is Distributional Robust Optimization (DRO) [DN88 HSNLI8]. in which we assume that the test 33 distribution belongs a certain set of distributions that are close the training distribution (called
32
34 the uncertainty set), and train the model on the worst distribution in that set. Many variants of DRO
35 have been proposed and are used in practice HNSSTT SKHI.11 20 XDKR20 ZDKR21 ZDS+21
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

36
While these approaches have been developed for the express purpose of improving ERM for distri- bution shift, line of recent work has empirically shown the negative result that when used train overparameterized models, these methods do not improve over ERM. For IW, [BLI9] observed that its effect under stochastic gradient descent (SGD) diminishes over training epochs, and finally does not improve over ERM. For variants of DRO, [SKHL220 found that these methods overfit very easily,
37
38
39
40
41 ie. their test performances will drop to the same low level as ERM after sufficiently many epochs no regularization is applied. [GLP21 2SM+ compared these methods with ERM on number of real-world applications, and found that in most cases none of these methods improves over ERM.
43
44
This line of empirical results has also been bolstered by some recent theoretical results. [SRKL20] constructed synthetic dataset where linear model trained with IW is provably not robust to subpopulation shift. [XYR2I] further proved that under gradient descent (GD) with a sufficiently small learning rate, a linear classifier trained with either IW or ERM converges to the same max- margin classifier, and thus upon convergence, are no different. These previous theoretical results are limited to linear models and specific approaches such as IW where sample weights are fixed during training. They are not applicable to more complex models, and more general approaches where the sample weights could iteratively change, including most DRO variants.
45
48
47
48
49
51
52 Towards placing the empirical results on a stronger theoretical footing, we define the class of generalized reweighting (GRW), which dynamically assigns weights to the training samples, and iteratively minimizes the weighted average of the sample losses. By allowing the weights to vary 55 with iterations, we cover not just static importance weighting, but also DRO approaches outlined earlier; though of course, the GRW class is much broader than just these instances.
53
54
56
57 In this work, we prove the comprehensive result that in both regression and classification, and for both overparameterized linear models and wide neural networks, the models learnt via any GRW approach and ERM are similar, in the sense that their implicit biases are (almost) equivalent. We note that extending the analysis from linear models to wide neural networks is non-trivial since it requires the result that wide neural networks can be approximated by their linearized counterparts hold uniformly throughout the iterative process of GRW algorithms. Our results extend the analysis in LXS 19). but as we show, the proof in the original paper had some flaws, and due which we have to fix the proof by changing the network initialization (Eqn. (.. see Appendix E).
58
59
60
61
62
63
64
Overall, the important takeaway is that distributionally robust generalization cannot be directly achieved by the broad class of GRW algorithms (which includes popular approaches such as impor- tance weighting and most DRO variants). Progress towards this important goal thus requires either going beyond GRW algorithms, or devising novel loss functions that are adapted to GRW approaches. In Section 6 we will diseuss some promising future directions well as the limitations of this work.
66
68
69
2 Preliminaries
70
71 Let the input space be X C IRd and the output space be y C I We assume that X' is a subset of the
unit L2 ball of Rdd so that any x E X satisfies | < 1. We have training set {z, (x,, U/ J
73 i.ddd sampled from underlying distribution P over X' x V Denote X x==( (x ... 2x,) E IR Bd
74 and Y (y). yn) E R", For any function 9 : X² +> RT, we overload notation and use
75 g(X)= = (o(=)), _)(,,)) )) E R (except when = 1, X) is defined as column vector).
76 Let the loss function be E: y x y + [0, 1]. ERM trains a model by minimizing its expected risk
77 R(;; P) - Ex_ v)] via minimizing the empirical risk R(()- = 1. ΣT ((f(()) 9:).
78 In distributional shift, the model is evaluated not on the training distribution P. but different test
79 distribution PRSst so that we care about the expected risk R(J: Pua)). A large family of methods
80 designed for such distributional shift is distributionally robust optimization (DRO), which minimizes
81 the expected risk over the worst-case distribution Q < H in a ball w.r.t. divergence D around the training distribution P. Specifically, DRO minimizes the expected DRO risk defined as:
Rp. P)= = sup {Eqle((()), v)] D(Q || Q&P
5}
(1)
83 for p >0 0. Examples include CVaR, x 2DDR HSNL18), and DORO [DKR21 among others.
1 Our results can be easily extended to the multi- class scenario (see Appendix
FFrr distributions P and Q. Q is absolute continuous to P. or Q & P. means that for any event A.
P(A) 0 implies ((A) 0.
2

---

84
A common category of distribution shift is known as subpopulation shift. Let the data domain contain the distribution over all groups, and the test
85 K groups D..... Dx- The training distribution distribution Pies is the distribution over one of the groups. Let Pz(z) = P(z conditional distribution over group k. then Pies can be any one of Pi..... Pk- The goal is to train a
86
E Dz) be the
87
88 model f that performs well over every group. There are two common ways to achieve this goal: one
89 is minimizing the balanced empirical risk which is an unweighted average of the empirical risk over each group, and the other is minimizing the worst-group risk defined as
Rmax (f: P)
max R(S: Px) = max EZ ( ((][())) y)1= E D&)
k= KK
k= K
3 Generalized Reweighting (GRW)
91
Various methods have been proposed towards learning models that are robust to distributional shift. 93 In contrast to analyzing each of these individually, we instead consider a large class of what we call Generalized Reweighting (GRW) algorithms that includes the ones mentioned earlier, but potentially 95 many others more. Loosely, GRW algorithms iteratively assign each sample a weight during training (that could vary with the iteration) and iteratively minimize the weighted average risk. Specifically, at iteration I, GRW assigns a weight L; to sample 2;, and minimizes the weighted empirical risk:
94
(t)
97
Rit (f)
(0) ([(()) 2
98
where q()) = (ql
and +
1.
99
Static GRW assigns to each 2; = (a, Vi) a fixed weight q that does not change during training, i.e. 4 qr A classical method is importance weighting [Shi00] where 2; E DD and the size of Dx is nu. then qi (Knz)=1 Under importance weighting, (3) becomes the balanced empirical risk in which each group has the same weight. Note that ERM also a special case of static GRW.
100
101
102
On the other hand, in dynamic GRW, gtt) changes with t. For instance, any approach that iteratively upweights samples with high losses in order to help the model learn "hard" samples, such as DRO, an instance of GRW. When estimating the population DRO risk R.D.p(s;: P) in Eqn. ②.. if P is set to the empirical distribution over the training samples, then Q < P implies that Q is also distribution over the training samples. Thus, DRO methods belong to the broad class of GRW algorithms. There are two common ways to implement DRO. One uses Danskin's 's theorem and chooses Q as the maximizer of [e[ y)] in each epoch. The other one formulates DRO as bi-level optimization problem, where the lower level updates the model to minimize the expected risk over Q. and the upper level updates Q to maximize it. Both can be seen as instances of GRW. As one popular instance of the latter, Group DRO was proposed by [SKL220] to minimize Q Denote the empirical risk over group k by (f),)), and the model at time i by f() Group DRO iteratively sets
104
105
106
108
109
110
111
112
113
114
q. ge /ng for all z; E D& where g
(t) is the group weight that is updated as
(t) (1-1) exp (vRA(((t-1)) (Vk 1,-.. ,K)
Jk x 9h
(8) for some v > O, and then normalized so that 91 + +... + In 1. (KHL20 then showed (in their Proposition 2) that for convex settings, the Group DRO risk of iterates converges to the global minimum with the rate O(2-1/2) if is sufficiently small.
115
116
117
4
Theoretical Results for Regression
118
119
In this section, we will study GRW for regression tasks that use the squared loss
1 ( v) 2 2
(5)
120
We will prove that for both linear models and sufficiently wide fully-connected neural networks, the implicit bias of GRW is equivalent to ERM, so that starting from the same initial point, GRW and ERM will converge to the same point when trained for an infinitely long time, which explains why GRW does not improve over ERM without regularization and early stopping. We will further show that while regularization can affect this implicit bias, must be large enough to significantly lower the training performance, or the final model will still be similar to the unregularized ERM model.
121
122
123
124
3

---

Nerm ot moH Hentel
0.04
0.00
Hi Ra-ll Pase-Rends
0.62
9.50
BRM
GDRO
NV
weight
6.8
0.32
8.00
0.25
0.00
0.21
2003
4900
2000
4000
0
2003
4030
2002
4000
Epocrs
Epects
Epochs
Epochs
(a) Weight Difference
(b) Norm of ERM Model
(c) Training Loss
(d) Group Weights
Figure I: Experimental results of ERM, importance weighting (IW) and Group DRO (GDRO) with
the squared loss on six MNIST images with linear model. All norms are L2 norms.
126
4.1
Linear Models
127
We first demonstrate our result on simple linear models to provide our readers with a key intuition; later, we will apply this same intuition to neural networks. This key intuition draws from results
128
129 of [ Let the linear model be denoted by f(x:) = (0, æt), where E Rd. We consider the
130
overparameterized setting where d > n. The weight update rule of GRW under GD is the following:
((++1) = g(0)
L
Vol(((((())))))))
(6)
where 1) > 0 the learning rate. For a linear model with the squared loss, the update rule is 131
0(++1) = 0 Σ 4i x; (f v.)
132
For this training scheme, we can prove that if the training error converges to zero, then the model converges to an interpolator 6 (s.t. Vi, (0", = =.)) independent of q." (proofs in Appendix Dj: Theorem 1. af.1.... In are linearly independent, then under the squared loss, for any GRW such that the empirical training risk R(f(t)) + 0 as + oc, it holds that ((t) converges to an interpolator (t)
133
134
135
8r that only depends ((0) and . In. but does not depend q,
The proof is based on the following key intuition regarding the update rule 7 ((++1) g(t) is linear combination of .i.-.. In for all I, so ((0) ((0) always lies in the linear subspace span pa
139
LnJ, which is an re-dimensional linear subspace if 21, ... Fn are linearly independent. By Cramer's rule, there is exactly one in this subspace such that we get interpolation of all the data (0 + g(0) x = ys for all E {1....,,b) n}. In other words, the parameter 6* = Ø + g this subspace that interpolates all the data is unique. Thus the proof would follow if were to show that g(t) (00), which lies in the subspace, also converges to interpolating the data.
140
141
144
We have essentially proved the following sobering result: the implicit bias of any GRW that achieves zero training error is equivalent to ERM, so GRW does not improve over ERM. While the various distributional shift methods discussed in the introduction have been shown to satisfy the precondition of convergence to zero training етrоr with overparameterized models and linearly independent inputs [SKHL20] we provide the following theorem that shows this for the broad class of GRW methods. Specifically, we show this result for any GRW satisfying the following assumption with sufficiently small learning rate:
145
146
147
148
150
Assumption 1. There are constants Q1,-.. In S.t. Vi, g.
q. as co. And min; q. = = 0. Theorem 2. If x1.... Ln are linearly independent, then there exists no > 0 such that for any GRW satisfying Assumption 7 with the squared loss, and any y) S To., the empirical training risk (() > as oc.
152
153
154
155 Finally, we use simple experiment to demonstrate the correctness of this result. The experiment is conducted on a training set of six MNIST images, five of which are digit 0 and one digit 1. We use a 784-dimensional linear model and run ERM, importance weighting and group DRO. The results are presented Figure [ and they show that the training loss of each method converges to O, and the gap between the model weights of importance weighting, Group DRO and ERM converges to 0, meaning
156
157
158
160
that all three model weights converge to the same point, whose To2 norm about 0.63. Figure id also shows that the group weights in Group DRO empirically satisfy Assumption !

---

162
4.2
Wide Neural Networks (Wide NNs)
163
Now we study sufficiently wide fully-connected neural networks. We extend the analysis in LXS* + 19 in the neural tangent kernel (NTK) regime [JGH88] In particular we study the following network:
184
W x + 3b
h 4+
and x =-1=o(h"
(1=0.-. ....... L)
(8)
where a is a non-linear activation function, W E Rd xd and W. E Rixdz, Here do = d. The 166 parameter vector 0 consists of W ,... WL and bo ... _b (0 is the concatenation of all flattened
165
weights and biases). The final output is f(x) = h L+1, And let the neural network be initialized as
167
1. 10)
((0)
W 1(0) 0
(1=0,-.. ... L 1)
and
(9)
6/00 10.
6/100 (0,,
188
We also need the following assumption on the wide neural network:
169
Assumption 2. o is differentiable everywhere. Both a and its first-order derivative ā are Lipschitz
170
Difference from [GH18). Our initialization (9 differs from the original one in [IGH88 in the last (output) layer, where we use the zero initialization w/100) 0 instead of the Gaussian initialization W0 (0, 1). This modification permits us accurately approximate the neural network with its linearized counterpart (1) as we notice that the proofs in LXS+19] (particularly the proofs of their Theorem 2.1 and their Lemma 1 in Appendix G) are flawed. In Appendix (E we will explain what goes wrong in their proofs and how we manage to fix the proofs with our modification.
171
172
175
175
Denote the neural network time t by (x) {x: (()) which is parameterized by g(t) TRP where p is the number of parameters. We use the shorthand Vo ( (w) [af 1e The Vo (0) (x) T (())), and the Gram matrix is (0) (0) (X, X) E RR For this wide NN, we still have the following NTK theorem:
176
177
neural tangent kernel (NTK) of this model is @ (æ, æ²)
179
Lemma 3. If is Lipschitz and d, oc for -=,............................. L sequentially, then ( (z, x') converges in probability to a non-degenerate deterministic limiting kernel (xx, x²).
181
The kernel Gram matrix ② O(X,X) E R is a positive semi-definite symmetric matrix. Denote its largest and smallest eigenvalues by A and A Note that θ is non-degenerate, so we can assume that Amin > O (which is almost surely true when d, > n.). Then we have:
183
184
Theorem 4. Let ((0 be wide fully-connected neural network that satisfies Assumption 2 and is trained by any GRW satisfying Assumption / with the squared loss. Let f(() be the same model
185
186
trained by ERM from the same initial point. d =... dr = d. V of (0() (a.)..... of (0) (x. are linearty independent, and X Amin > O, then there exists a constant m >> 0 such that: in S m) then for any 8 > 0, there exists D > 0 such that as long as d 2 D, with probability at least (1 - 5) over random initialization we have: for any test point x E _Rd such that |0||| S as d oc.
187
188
189
190
lim sup (z) - (z)) (0--1/4) - +0
(10)
Note that for simplicity, in the theorem we only consider the case where d = ... d2 = d oc. but in fact the result can be very easily extended to the case where d. - ay for 1 = 2, ... L for
192
198 some constants 02 ,a, and dj - do. Here we provide proof sketch for this theorem. The key to consider the linearized neural network of (z))
( x = (0) (x: (x) + (0()) g10), (o
(11)
195 which is linear model with features (0) Thus V (0) ... Vof (0) (a.,) are linearly independent, then the lincarized NN converges to the unique interpolator. Then we show that the
o is Lipschitz if there exists constant L > 0 such that for any æ1, 22 [f(=1) f(=2) S L ||= x ll.. 4 -onndeegeee means that O(xr, x²) depends on x and x' and is not a constant.
For ease of understanding, later will write this condition as "with sufficiently small learning rate".
5

---

197
wide neural network can be approximated by its linearized counterpart uniformly throughout training. which is considerably more subtle our case due the GRW dynamics. Here we prove that the gap bounded by (dd-1/4) but in fact we can prove that it is bounded by Odd-1/2+e) for any c. > O:
198
199
Lemma 5 (Approximation Theorem). For a wide fully-connected neural network f(l) satisfying Assumption 2 and is trained by any GRW satisfying Assumption / with the squared loss, let Jin be its linearized neural network trained by the same GRW (i.e. qi are the same for both networks for any with a sufficiently small learning rate, for any 8 >> 0, there exist constants D > 0 and C > 0 such that long d 2 D, with probability at least (1 5) over random initialization we have: for any test point I E R such that |>||| S 1,
200
202
i and t). Under the conditions of Theorem +
205
((() (x) - (x) s că-1/4
sup t20
(12)
206
Theorem 4 shows that at any test point æ within the unit ball, the gap between the outputs of wide NNs trained by GRW and ERM from the same iniiill point is arbitrarily close to O. So we have shown that for regression, with both linear and wide NNs, GRW does not improve over ERM.
208
209
4.3
Wide Neural Networks, with L2 Regularization
210
Previous work such as [SKHL20) proposed to improve DRO algorithms by adding L2 penalty to the objective function. In this section, we thus study adding L2 regularization to GRW algorithms:
211
RS gio (f) = Σ 19 e(f((z))) v.) + 1 100
(13)
212
From the outset, it easy to see that under L2 regularization, GRW methods have different implicit biases than ERM. For example, when f is a linear model, convex and smooth, then R (/) with
213
214 static GRW is a convex smooth objective function, so under GD with a sufficiently small learning rate, the model will converge to the global minimizer (see Appendix D.IIp Moreover, the global optimum 0r satisfies VoR. q(o (z: 0*) )) 0, solving which yields 0 ~ (XQX +
216
(()) (X)), which depends on Q diag(g1, ... , 9n). so adding Le regularization at least seems to yield different results from ERM (whether it improves over ERM might depend on qı, ...).
218
219
However, the following result shows that this regularization must be large enough to significantly lower the training performance, or the resulting model would still be close to the unregularized ERM model. We still denote the largest and smallest eigenvalues of the kernel Gram matrix @ by X max and
220
221
miin We use the subscript "reg" to refer to a regularized model (trained by minimizing (13).
222
Theorem 6. Suppose there exists Mo > s.t. f (x) S MM for all ||œ|||2 I 1. If > 0
223
2 and any GRW minimizing the squared loss and μ > O, then for wide NN satisfying Assumption
225
with sufficiently small learning rate n, if = d2
dj = d, o (xr)), ... /of(0) (xxm)
226 are linearly independent, and the empirical training risk of r satisfies
lim R( <e
(14)
1-xx
227 for some >> O, then with sufficiently small learning rate, as d - oc, with probability close to I
228 over random initialization, for any x such that ||x||| I 1 we have
lim sup t-000
Joy (x)
(a:) -(d 1/4
(15)
<(t) 229 where frog is trained by regularized GRW and JERM by unregularized ERM from same initial points.
(tt)
230
The proof again starts from analyzing linearized neural networks, and showing that regularization does not help there (Appendix D.4.2). Then, we need to prove a new approximation theorem for L regularized GRW connecting wide NNs to their linearized counterparts uniformly through the GRW
232
training process (Appendix 1. Note that with regularization, we no longer need Assumption
234
to prove the new approximation theorem, because previously Assumption is used to prove the convergence of GRW, but with regularization GRW naturally converges.

---

Korm of ffrrenc
0.00
Pase -Radd
Traying
0.4
NV
CD-1
0.06-
iPa-Ramll
Traiiing Ludg
0.04
GDRG
IWV
0.04
IRM
0.04
ERM
0.
0.2
0.22
0.92
2203
4300
0.0
2000
4000
2000
4020
0.0
2003
4000
Epocrs
Epocts
Epocto
Epochs
(a) Weight Difference (b) Training Loss
(c) Weight Difference
(d) Training Loss
Figure 2: Experimental results of ERM, importance weighting (IW) and Group DRO (GDRO) with
L2 regularization with the squared loss. Left two: μ = 0.1; Right two: μ = 10.
236
Theoremp shows that if the training error can go below e, then the gap between the outputs of the [wo models on any lest point x within the unit ball will be most (vv)). Thus, if very small, regularized GRW yields a very similar model to unregularized ERM, and thus makes improvement.
237
238
To empirically demonstrate this result, we run the same experiment in Section 4.1 but with Le regularization. The results are presented in Figure We can see that when the regularization is small, the training losses still converge O, and the three model weights still converge to the same point. On the contrary, with a large regularization, the training loss does not converge to 0, and the three model weights no longer converge to the same point. This shows that the regularization must be large enough to lower the training performance in order to make a significant difference to the implicit bias.
240
242
244
Theoretical Results for Classification
245
246
Now we consider classification where = ++11-11, The big difference is that classification losses don't have finite minimizers. A classification loss converging to zero means that the model weight "explodes" to infinity instead of converging to a finite point. We focus the canonical logistic loss:
247
E(g. y) = log(1 + exp(-9t))
(16)
249
5.1
Linear Models
250
We first consider training the linear model f(z) = (0, x)) with GRW under gradient descent with the
logistic loss. As noted earlier, in this setting, [LI19] made the empirical observation that importance weighting does not improve over ERM. Then, XYR21 proved that for importance weighting algorithms, as -> oo, ||0(0)| ||2 + oo and B()) /I 112 converges to a unit vector that does not depend does not improve over ERM. To extend this theoretical result the broad class of GRW algorithms, we will prove two results. First, in Theorem we will show that under the logistic loss, any GRW algorithm satisfying the following weaker assumption:
252
253
on the sample weights,
255
256
257
Assumption 3. For all i, lim inf gi >
258
the training error converges to O, and the direction of the model weight converges to fixed unit vector, then this unit vector must be the max-margin classifier defined as
0MM =
arg max
min yi (0, ax)) i=
(17)
0:1(01|,=1
260
Second, Theorem & shows that for any GRW satisfying Assumption ! the training error converges to O and the direction of the model weight converges, so it does not improve over ERM.
261
262
Theorem 7. If x.,,...
... , In are linearly independent, then for the logistic loss, we have: for any GRW satisfying Assumption if i - ca the empirical training risk R( converges to 0 and g(t) / ||002000 > u for some unit vector u, then u 8MM-
264
(t) This result an extension of [SHN+18) Note that Ôv does not depend on q so this result shows that the sample weights have no effect the implicit bias. Thus, for any GRW method that only satisfies the weak Assumption as long as the training error converges to and the model weight direction converges, GRW does not improve over ERM. We next show that any GRW satisfying Assumption I does have its model weight direction converge, and its training error converge to 0.
265
287
269
Theorem 8. For any loss l that is convex, L-smooth in új and strictly monotonically decreasing to zero as yi > +0C, and GRW satisfying Assumption 1 denote F(0) = Σn= qel((p a.)).1)) If 31, In are linearly independent, then with a sufficiently small learning rate n, we have:
271
7

---

273
(i) F(O()) - 0 as + 0c.
(ii)
|0(0)
2 + 00 as cC.
(ii)) Let On = arg ming ( 10 S R]. On is unique for any R such that min F()) <
min; q,e(O, v.). And if Rim on exists, then lime->oo R
g(s) | also exists and they are equal.
This result is extension of Theorem of [JDT220]. For the logistic loss, it is easy to show that it satisfies the conditions of the above theorem and lim R-oc H logether imply that all GRW satisfying Assumption | (including ERM) have the same implicit bias
Og M Thus, Theorems and 7
277
278
(see Appendix D.5.3 We also have empirical verification for these results (see Appendix C
279
Remark, It is impossible to extend these results to wide NNs like Theorem because for a neural network, if ||0(0//2 goes to infinity, then ||Vefl2 will also go to infinity. However, for a linear model, the gradient is a constant. Consequently, the gap between the neural networks and its linearized counterpart will "explode" under gradient descent, so there can be no approximation theorem like Lemma that can connect wide NNs to their linearized counterparts. Thus, we consider regularized GRW, for which (1+) converges to finite point and there is an approximation theorem.
280
282
285
5.2
Wide Neural Networks, with L2 Regularization
286
Consider minimizing the regularized weighted empirical risk (13 with é being the logistic loss. As in the regression case, with L2 regularization, GRW methods have different implicit biases than ERM
287
208
for the same reasons as in Section 4.3] And similarly, we can show that in order for GRW methods to
289
be sufficiently different from ERM, the regularization needs to be large enough to significantly lower
290
the training performance. Specifically, in the following theorem we show that if the regularization
is too small to lower the training performance, then wide neural network trained with regularized
292
GRW and the logistic loss will still be very close to the mar-ia linearized neural network:
[x) (bum: (o)()( where
δMM arg max min yi (0, Vo ( (18)
||0||==1
293
Note that fMM does not depend on g. Moreover, using the result in the previous section we can show that linearized neural network trained with unregularized ERM will converge fMM:
Theorem 9. Suppose there exists Mo such that [ f (a:) (x)]] S Mo for all test point æ. For
295
296
wide NN satisfying Assumption 2 and for any GRW satisfying Assumption 7 with the logistic loss, dg = d and ee (xx1).... (0x))),, Nel (0) (xxx) are linearly independent and the learning rate sufficiently small, then for any > there exists a constant C >> O such that: with probability at least (1 -1-6) 8) over random initialization, as d co we have: for any E (0, 4), if R( < then for any test point such that the empirical training error satisfies lim sup;
287
if d, = d2 =
298
299
[m)) > C 2- 2c) 112 s112 (x:) has the same sign as fmus(=) when t is sufficiently large. 301
302
This result says that any test point margin of 22(- log 2e) -1/2), the neural network has the same prediction. And as decreases, the confidence threshold also becomes lower. Similar to Theorem 6 this theorem provides the scaling of the gap between the regularized GRW model and the unregularized ERM model w.z.t
which the max-margin linear classifier classifies with
304
306
This result justifies the empirical observation in [SKHL20) that with large regularization, some GRW algorithms can maintain a high worst-group test performance, with the cost of suffering significant drop in training accuracy. On the other hand, the regularization is small and the model can achieve nearly perfect training accuracy, then its worst-group test performance will still significantly drop.
307
308
309
Discussion
311
6.1
Distributionally Robust Generalization and Future Directions
312 A large body of prior work focused on distributionally robust optimization, but we show that these methods have (almost) equivalent implicit biases as ERM. other words, distributionally robust optimization (DRO) does not necessarily have better distributionally robust generalization (DRG).
313
8

---

315
Therefore, we argue that it is necessary to design principled ways to improve DRG, which is what people really want in the first place. Here we discuss three promising approaches to improving DRG.
316
317
The first approach is data augmentation and pretraining on large datasets. Our theoretical findings suggest that the implicit bias of GRW is determined by the training samples and the initial point, but not the sample weights. Thus, to improve DRG, we can either obtain more training samples, or start
318
319
320
from a better initial point, as demonstrated in two recent papers [WGS+2] $ 22 SKL
321
The second approach (for classification) is to go beyond the class of (iterative) sample reweighting based GRW algorithms, for instance via logit adjustment (MJR 22], which makes classifier have larger margins on smaller groups to improve its generalization on smaller groups. An early approach
322
323
by IWGG 19] proposed to add an O(ne additive adjustment term to the logits output by the
325
classifier. Following this spirit, [MJR 21 proposed the LA-loss which also adds an additive adjust-
326
ment term to the logits. [YCZC20] proposed the CDT-loss which adds a multiplicative adjustment
327
term to the logits by dividing the logits of different classes with different temperatures. [KPOT2I] proposed the VS-loss which includes both additive and multiplicative adjustment terms, and they showed that only the multiplicative adjustment term affects the implicit bias, while the additive term only affects optimization, a fact that can be easily derived from our Theorem 8 Finally, 21 proposed AutoBalance which optimizes the adjustment terms with a bi-level optimization framework.
328
329
330
332
The third approach is to stay within the class of GRW algorithms, but to change the classifica- tion/regression loss function to be suited to GRW. A recent paper [WCHH222 showed that for linear classifiers, one can make the implicit bias of GRW dependent on the sample weights by replacing the exponentially logistic loss with the following polynomially-tailed loss:
333
334
335
(in)
if gy < 3
la ((,,0)))
(19)
if tv 2 8
[oy - (B 1)}-
336
And this result can be extended to GRW satisfying Assumption I using our Theorem 8 The reason why loss 19 works is that it changes 1im f/8 and the new limit depends on the sample weights.
337
338
6.2
Limitations
329
Like most theory papers, our work makes some strong assumptions. The two main assumptions are:
The model is a linear model or sufficiently wide fully-connected neural network.
341
The model is trained for sufficiently long time, iee. without early stopping.
342
Regarding (i), [COB19 argued that NTK neural networks fall in the "lazy training" regime and results might not be transferable to general neural networks. However, this class of neural networks has been widely studied in recent years and has provided considrable insights into the behavior of general neural networks, which is hard analyze otherwise. Regarding (ii), in some easy tasks, when early stopping is applied, existing algorithms for distributional shift can do better than ERM SKHL.20 However, as demonstrated in [GLP2T KSM+211 in real applications these methods still cannot significantly improve over ERM even with early stopping, so early stopping is not the ultimate universal solution. Thus, though inevitably our results rely on some strong assumptions, we believe that they provide important insights into the problems of existing methods and directions for future work, which are significant contributions to the study of distributional shift problems.
343
344
345
347
319
351
Conclusion
352
353
In this work, we posit broad class of what we call Generalized Reweighting (GRW) algorithms that include popular approaches such as importance weighting, and Distributionally Robust Optimization (DRO) variants, that were designed towards the task of learning models that are robust to distributional shift. We show that when used to train overparameterized linear models or wide NN models, even this
354
355
356
357
very broad class of GRW algorithms does not improve over ERM, because they have the same implicit biases. We also showed that regularization does not help if it not large enough to significantly lower the average training performance. Our results thus suggest to make progress towards learning models that are robust to distributional shift, we have to either go beyond this broad class of GRW algorithms, or design new losses specifically targeted to this class.
358
360
9

---

References
362
383
[BGO16]
Su Lin Blodgett, Lisa Green, and Brendan O' O'Connor Demographic dialectal variation in social media: A case study of African-American English. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 1119- 1130, Austin, Texas, November 2016. Association for Computational Linguistics.
364
365
366
367
[BL19] Jonathon Byrd and Zachary Lipton. What is the effect of importance weighting in deep learning? In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 872-881. PMLR, 09-15 Jun 2019.
388
370
371
[COB19]
Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Bus Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
372
373
374
375
[CWG+ + 19] Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with aabll-distribution-awaaa margin loss. Advances in Neural Information Processing Systems, 32:1567-1578, 2019.
377
378
[DN18] John Duchi and Hongseok Namkoong. Learning models with uniform performance via distributionally robust optimization. arXiv preprint arXiv:1810.08750 2018.
379
380
[GLP21] Ishaan Gulrajani and David Lopez-Paz. In search of lost domain generalization. In International Conference on Learning Representattons, 2021.
382
[GLSS18]
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In Jennifer Dy and Andreas Krause, editors. Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1832- 1841. PMLR, 10-15 Jul 2018.
383
384
385
[HNSS18] Weihua Hu, Gang Niu, Issei Sato, and Masashi Sugiyama. Does distributionally robust supervised learning give robust classifiers? In International Conference on Machine Learning, pages
387
388
PMLR, 2018
389
[HS15] Dirk Hovy and Anders Søgaard. Tagging performance correlates with author age. In Proceedings of the 53rd annual meeting the Association for Computational Linguisties and the 7th international joint conference on natural language processing (volume 2: Short papers), pages 483 483-488. 488, 2015.
390
391
392
[HSNL18] Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fair- ness without demographics in repeated loss minimization. In Jennifer Dy and Andreas Krause, editors, International Conference on Machine Learning, volume 80 of Proceed- ings of Machine Learning Research, pages 1929-1938, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR
394
396
387
398
[JDST20] Ziwei Ji, Miroslav Dudík, Robert E. Schapire, and Matus Telgarsky. Gradient descent follows the regularization path for general losses. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 2109-2133 109--1136 136. PMLR, 09-12 Jul 2020.
389
400
401
403
[JGH18] Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Conver- gence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa BisacBianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
404
405
406
407
[KPOT21] Ganesh Ramachandra Kini, Orestis Paraskevas, Samet Oymak, and Christos Thram- poulidis. Label-imbalanced and group-sensitive classification under overparameteriza- tion. In Thirty-Fifth Conference Neural Information Processing Systems, 2021.
408
10

---

410
[KSM 21]
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani. Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, Tony Lee, Etienne David, Ian Stavness, Wei Guo, Berton Earnshaw, Imran Haque, Sara M Beery, Jure Leskovec, Anshul Kundaje, Emma Pierson, Sergey Levine, Chelsea Finn, and Percy Liang. Wilds: A benchmark of in-the-wild distribution shifts. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5637-5664. PMLR, 18-24 Jul 2021.
411
412
413
414
415
417
418
[LXS 19] Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak. Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. Advances in neural information processing systems, 32:8572 8583, 2019.
420
[1] Mingchen Li, Xuechen Zhang, Christos Thrampoulidis, Jiasi Chen, and Samet Oymak. Autobalance: Optimized loss functions for imbalanced data. In Thirty- Fiith Conference on Neural Information Processing Systems, 2021.
423
425
[MJR 21] Aditya Krishna Menon, Sadeep Jayasumana, Ankit Singh Rawat, Himanshu Jain, An- dreas Veit, and Sanjiy Kumar. Long-tail learning via logit adjustment. In International Conference on Learning Representations, 2021.
426
427
428
[Shi00]
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log-likeling likelihiiood function. Journal of statistical planning and inference, 90(2):227-2) -444, 2000.
429
430
431
[SHN+ + 18] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro.
432
The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1) 2878, 2018.
433
434
[S
Shiori Sagawa, Pang Wei Koh, Tatsunori Hashimoto, and Percy Liang. Distribution- ally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. In International Conference on Learning Representations, 2020.
435
436
[SKL +22] Shiori Sagawa, Pang Wei Koh, Tony Lee, Irena Gao, Sang Michael Xie, Kendrick Shen, Ananya Kumar, Weihua Hu, Michihiro Yasunaga, Henrik Marklund, Sara Beery, Etienne David, Ian Stavness, Wei Guo, Jure Leskovec, Kate Saenko, Tatsunori Hashimoto, Sergey Levine, Chelsea Finn, and Percy Liang. Extending the WILDS benchmark for unsupervised adaptation. In International Conference on Learning Representations, 2022.
439
441
443
444
[SRKL20] Shiori Sagawa, Aditi Raghunathan, Pang Wei Koh, and Percy Liang. An investigation of why overparameteriizatoon exacerbates spurious correlations. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 8346-8356. PMLR, 13-18 Jul 2020.
446
447
448
449
[Tat17] Rachael Tatman. Gender and dialect bias in youtube's 's automatic captions. In Proceed- ings of the First ACL Workshop on Ethics in Natural Language Processing, pages 53-59, 2017.
450
451
452
[WCHH22]
Ke Alexander Wang, Niladri Shekhar Chatterji, Saminul Haque, and Tatsunori Hashimoto. Is importance weighting incompatible with interpolating classifiers? In International Conference on Learning Representationss 2022.
453
454
455
[WGS+22] Olivia Wiles, Sven Gowal, Florian Stimberg, Sylvestre-Alvise Rebuffi, Ira Ktena, Krish- namurthy Dj Dvijotham, and Ali Taylan Cemgil. A fine-grained analysis on distribution shift. In International Conference on Learning Representations, 2022.
456
457
[XDKR20] Ziyu Xu, Chen Dan, Justin Khim, and Pradeep Ravikumar. Class- weighted classifi- cation: Trade-offs and robust approaches. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference Machine Learning, volume 119
459
11

---

461
of Proceedings of Machine Learning Research, pages 10544-10554, PMLR, 13 18 Jul 2020.
462
463
[XYR21] Da Xu, Yuting Ye, and Chuanwei Ruan. Understanding the role of importance weighting for deep learning. In International Conference on Learning Representations, 2021.
464
465
[YCZC20] Han-Jia Ye, Hong- You Chen, De-Chuan Zhan, and Wei-Lun Chao. Identifying and
466
compensating for feature deviation in imbalanced deep learning. arXiv preprint arXiv:2001.0138. 2020.
467
[ZIDR21]] Runtian Zhai, Chen Dan, Zico Kolter, and Pradeep Ravikumar. Doro: Distributional and outlier robust optimization. Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 12345-12355. PMLR, 18-24 Jul 2021.
469
471
472
[ZDS+21] Runtian Zhai, Chen Dan, Arun Suggala, Zico Kolter, and Pradeep Kumar Raviku- mar. Boosted CVar classification. In Thirty-Fifth Conference Neural Information
474
Processing Systems, 2021.
Checklist
476
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A]. You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
478
480
Did you include the license to the code and datasets? [Yes] See Section.
481
Did you include the license the code and datasets? [No] The code and the data are proprietary.
483
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
485
486
1. For all authors...
488
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
489
490
(b) Did you describe the limitations of your work? [Yes] See Section 6.2
491
(c) Did you discuss any potential negative societal impacts of your work? [No] Not
relevant.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
494
495
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
487
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix D
3. If you ran experiments..
489
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
500
501
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
502
(c) Did you report error bars (e.g., with respect the random seed after running experi-
504
ments multiple times)? [No] The experiments are only for demonstration.
505
(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 the code.
508
4. If you using existing assets (c.g., code, data, models) or curating/releasing assets...
12

---

508
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [N/A]
511
512
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
513
514
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
517
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
519
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals. if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
522
13


Reviews:
[{"review_id": "yKDPpj1sv-9", "reviewer": "Reviewer_85jH", "summary": "This manuscript demonstrates that the popular approaches, such as importance weighting, and Distributionally Robust Optimization (DRO) variants, cannot really improve the distributional drift problem over Empirical risk minimization (ERM). To achieve this goal, this manuscript presents a Generalized Reweighting (GRW) (the above popular algorithms are its special cases). When training overparameterized linear models or wide NN models, the result for GRW is very close to that for ERM. Moreover, it also demonstrates a small regularization that needs to not greatly affect the empirical training accuracy does not help.", "questions": "The theoretical analysis is built on linear models. To extend to neural networks, the manuscripts utilizes existing the neural tangent kernel (NTK) theory to take networks as an approximately linear model. It is known that there is a gap between NTK networks and the practical networks. The width of NTK networks should be infinite; the NTK networks are commonly simple fully-connected networks;  he optimization algorithms should be simple stochastic gradient descent (SGD). All these conditions cannot be satisfied in real-world tasks. Moreover, Assumption assumes the first-order of the active function is Lipschitz continuous. We know it is common to apply ReLU as the active function in the modern networks, which is not satisfied this assumption. In summary, these ideal assumptions will influence the validity of the theoretical analysis. ", "limitations": "There is no potential negative societal impact for this manuscript.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Observing that some works uncovered the popular approaches that aim to address distributional drift do not significantly improve over ERM, the authors try to theoretically prove this empirical phenomenon. Moreover, according to the theoretical conclusion, the authors also provide some potential approaches that can alleviate the distributional drift problem.  and it might fundamentally change this direction for distributionally robust approaches.", "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": "nQqRl1cPmDC", "reviewer": "Reviewer_8VCe", "summary": "This paper shows that Generalized Reweighting (GRW), dynamically weighting each loss term of the empirical risk, used for training a model that is robust to distribution shift has almost no impact on the result of the optimization compared with the ordinary Empirical Risk Minimization (ERM) for regression and classification with linear models or wide neural networks. This implies that despite being a popular approach, GRW fails to improve over ERM in the cases that the authors consider.\nThe authors also prove that even with regularization that compromise the training loss by $\\epsilon$, GRM only brings a change of $O(\\sqrt{\\epsilon})$ to the minimizer compared to ERM.\nTheir results suggest that learning robustly to distribution shift may need approaches other than GRM.\n", "questions": "- [HNSS18] also provides some theoretical, negative results similarly to this paper. Could the authors discuss the difference?\n- Do the authors have any thoughts about how much difference we should expect in the result of optimization, $f^{(t)}$, from that of ERM in order to be distributionally robust? If we only need a small change from ERM to achieve robustness, the result for regularization in the paper may not be a negative one.\n", "limitations": "The paper clearly discusses limitations of the work about the theoretical assumptions.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n- The paper is well-written and provide intuitive explanations even for technical part.\n- The paper provides theoretical evidence supporting previously reported empirical observations for failures in training distributionally robust models with the weighting approach.\n- While existing theoretical work only handles linear models, the paper consider wide neural networks.\n- As a technical contribution, the authors analysis corrects and extends that of Lee et al. (2019).\n- Although the main results are negative ones for the GRW approach, the paper discusses implications about other possible approaches.\n\n# Weaknesses\n- The paper does not provide concrete algorithms that can avoid their negative results.\n- The paper analyzes the asymptotic behavior of wide neural networks when the widths go to infinity, which may not reflect the behavior of neural networks commonly used in reality.\n- The results with regularization are hard to interpret because the paper does not analyze how much change we need for truly robust training and we do not know the $O(\\sqrt{\\epsilon})$ impact is insufficient or not.\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": "aBn5REnsxC", "reviewer": "Reviewer_XtEr", "summary": "As a theoretical work, this paper aims to understand why generalized reweighting does not improve over ERM in the setting of distribution shift. Specifically, it considers the overparameterized linear model and wide neural networks under gradient descent, and prove the same solution between generalized reweighting and ERM methods via the implicit bias of the gradient descent algorithm.  Then, it claims that these two method families should share the same performance empirically. Technically, it mainly utilizes the neural tangent kernel theory for the wide neural networks. ", "questions": "1. The authors mentioned that the reweighting and ERM algorithms converge to the unique interpolator. But which one? Does the interpolator have some special property? \n2. Although this paper mainly considers the distribution shift problem, I haven't seen its key difference or point with the classical setting. Please give more explanations why ERM is not suitable for this case.\n3. When theoretically comparing with empirical performance of two or many learning algorithms, generalization analysis is preferred. While this paper focuses on the optimization properties via implicit bias of gradient descent, implicit bias can also offer insight for generalization. Thus, what is the generalization performance of the learning algorithms considered in this paper?", "limitations": "The authors have mentioned some limitations in this paper. But, I still have the following suggestions.\n1. The generalization analysis can provide more insights into the empirical performance.\n2. More experiments in real settings can support the theoretical results.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This work is motivated by the empirical results that the reweighting methods often have no superiority over ERM in the distribution shift problem. In my view, its theoretical investigation is valuable.\n2. The claim is partially supported by formal theoretical results.\n\nWeaknesses:\n1. The considered setting is rather limited as previous work has considered the linear model case. Besides, although this paper considers the wide neural networks via the connection between the kernel method and neural networks (i.e., neural tangent kernel theory), it still has a large gap in practice. \n2. The results are not surprising and interesting as mentioned in 1. The key reason why generalized reweighting and ERM converge to the same solution is the implicit bias of the optimization algorithms (i.e., gradient descent in this paper) for overparameterized models. However, this paper does not highlight the key effects of the overparameterized model case. Thus, I am concerned that the authors may overclaim the results.\n3. In practice, regularization and early stopping are usually used to improve the generalization performance. However, this paper neglects them.\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": "UliqQCtlW9a", "reviewer": "Reviewer_sLyL", "summary": "Focused on understanding the effect of reweighing strategy on improving the robustness of ERM to distributional shift, this paper demonstrates notably that iteratively updating the sample weights does not improve over ERM in an overparametrized setting. With similars results already derived for the method of fixed weights, the main contribution of this work is to confirm, in a more general setting, the fact that the solution obtained by gradient descent in the overparametrized regime converges to an interpolator independent of the samples weights. ", "questions": "As the main contribution of this work concerns the generalization to the iterative reweighing setting, it would help to clarify the originality of this work to discuss the technical challenges brought by the iteratively updated sample weights in obtaining the theoretical results. \n\nFurthermore, the interest of this study would be significantly increased by adding deeper results in the regularized case to shed light on the impact of the iteratively reweighed samples on the improvement of robustness.", "limitations": "The limitations of this work are well discussed. There does not seem to be any negative societal impact.\n\nThe contribution of this paper would be greatly enhanced if the authors could go further in exploring one of the directions mentioned in the article where the robustness is likely to improve.", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: Theoretical understanding of reweighing strategy under a more general framework that allows iterative updating of sample weights.\n\nWeaknesses : As previous work already explained the ineffectiveness of sample reweighing in the overparametrized regime with the convergence of the gradient descent solution to an interpolator independent of the sample weights, the generalized results given in this paper do not seem to provide further insight into the effect of the reweighing approach.", "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: Reject