Understanding Overfitting in Reweighting Algorithms for Worst-group Performance
Authors: Runtian Zhai
Chen Dan
J Zico Kolter
Pradeep Kumar Ravikumar
Venue: ICLR 2022 Submitted (2022)
Keywords: Reweighting algorithms
Worst-group performance
Implicit bias
Fairness

Abstract: Prior work has proposed various reweighting algorithms to improve the worst-group performance of machine learning models for fairness. However, Sagawa et al. (2020) empirically found that these algorithms overfit easily in practice under the overparameterized setting, where the number of model parameters is much greater than the number of samples. In this work, we provide a theoretical backing to the empirical results above, and prove the pessimistic result that reweighting algorithms always overfit. Specifically we prove that with reweighting, an overparameterized model always converges to the same ERM interpolator that fits all training samples, and consequently its worst-group test performance will drop to the same level as ERM in the long run. That is, we cannot hope for reweighting algorithms to converge to a different interpolator than ERM with potentially better worst-group performance. Then, we analyze whether adding regularization helps fix the issue, and we prove that for regularization to work, it must be large enough to prevent the model from achieving small training error. Our results suggest that large regularization (or early stopping) and data augmentation are necessary for reweighting algorithms to achieve high worst-group test performance.

Under review as a conference paper at ICLR 2022
UNDERSTANDING OVERFITTING IN REWEIGHTING ALGORITHMS FOR WORST-GROUP PERFORMANCE
Anonymous authors Paper under double-blind review
ABSTRACT
Prior work has proposed various reweighting algorithms to improve the worst- group performance of machine learning models for faimess, However, [Sagawa] al. (2020a) empirically found that these algorithms overfit easily practice un- der the overparameterized setting, where the number of model parameters is much greater than the number of samples. In this work, we provide theoretical back- ing to the empirical results above. and prove the pessimistic result that reweighting algorithms always overfit. Specifically we prove that with reweighting, an over- parameterized model always converges to the same ERM interpolator that fits all training samples, and consequently its worst-group test performance will drop to the same level as ERM in the long run. That is, we cannot hope for reweighting algorithms to converge to a different interpolator than ERM with potentially better gorst-group performance. Then, we analyze whether adding regularization helps fix the issue, and we prove that for regularization to work, it must be large enough prevent the model from achieving small training error. Our results suggest that large regularization (or early stopping) and data augmentation are necessary for reweighting algorithms to achieve high worst-grous test performance.
INTRODUCTION
It has been well established by prior work that overparameterized models, whose number of pa- rameters is much larger than the number of training samples, can empirically achieve high test performance on variety of tasks, in contrast to the theory that models with too many parameters could have large generalization error.
This high performance however is on average; large body of prior work (Hovy & Sogaard 2015 Blodgett et al. 2016 Tatman 2017) showed that these models tend to learn spurious features, such as learning the background in image classification instead of the object, and learning keywords like "not" in language sentiment analysis instead of really understanding the sentences. Consequently, these models unfair, i.e. they fail certain minority groups (such as positive sentences con- taining "not") while still having high average-case performance. To solve this problem, people have proposed various reweighting algorithms improve the model's worst-group performance, such as upweighting the minority groups or using distributionally robust optimization (DRO) based methods (Shimodaira) 2000 Hashimoto et al. 2018 Duchi & Namkoong 2018 Sagawa et al. 2020a).
While reweighting algorithms in principle can improve the worst-group performance compared to vanilla empirical risk minimization (ERM), previous work empirically found that when applied to modern overparameterized models, these methods could overfit very easily, so that they have poor test worst- group performance. For example, [Sagawa al. (2020a) studied a reweighting algorithm called group DRO. They found that compared to ERM, group DRO does improve the worst-group test accuracy by a large margin at the early stage of training. However, no regularization applied, then as training goes on, the worst-group test accuracy of group DRO will drop signifi- cantly and eventually to a level almost the same as ERM. Some previous work tried to explain why reweighting algorithms
overfit easily. For instance, [Sagawa et al.) (200bb) argued that with these algorithms, an overparameterized model would typically memorize all training samples in the minority groups while still learning the spurious features from the majority groups
In this work, we aim to understand the overfitting phenomenon in reweighting algorithms by study- ing their implicit biases. Specifically, we prove for family of overparameterized neural networks

---

Under review as a conference paper at ICLR 2022
that for almost all reweighting algorithms, the model always converges to the same interpolator that fits all training samples, no matter the reweighting. Since ERM is a special case of such reweight- ing algorithms (where each sample receives the same weight), this means that the implicit biases of all reweighting algorithms are equivalent to that of ERM. Consequently, the model trained by any reweighting algorithm always overfits the ERM interpolator, so we cannot hope for its worst- group test performance to be better than ERM. In short, reweighting algorithms always overfit.
Given this pessimistic result, we analyze whether regularization can help mitigate overfitting, as pro- posed by (Sagawa et al. (2020a). We find that a necessary condition for regularization to work is that considerably lowers the training performance. Specifically, we prove that if the overparameterized model trained by a reweighting algorithm with regularization can still perform almost perfectly on the training set, then overfitting is still inevitable. This explains why in practice we need very large regularization that prevents the model from achieving nearly zero training error to avoid overfitting.
Our results have two important consequences for practice: (i) We should always use large regular- ization early stopping when optimizing for worst-group performance; (ii) We should always try to obtain more training samples, e.g. with strong data augmentation or semi-supervised learning.
1.1 RELATED WORK
Group fairness. Group fairesss in machine learning was first studied in Hardt et al. (2016) and Zafar et al. (2017), where they required the model to perform equally well over all groups Later, Hashimoto et al. (2018) studied another type of group fairesss called Rawlsian max-min fairness (Rawls] 2001). which does not require equal performance but rather requires high performance on the worst-off group. The problem we study in this paper is most closely related to Rawlsian max min fairness. A large body of recent work in machine learning have studied how to improve this worst- group performance (Duchi & Namkoong, 2018 Oren et al. 2019 Xu et al.] 2020 Liu et al. 2021] Zhai et al. 202I). Recent work however observe that these approaches, when used with modern overparameterized models, easily overfit (Sagawa al. 2020a b). Apart from group fairness, there are also other notions of fairness, such as individual fairness (Dwork et al. 2012 Zemel et al. 2013) and counterfactual fairness (Kusner et al.) 2017), which we do not study in this work.
Implicit bias under the overparameterizee setting, For overparameterized models, there could be many model parameters which all minimize the training loss. In such cases, of interest to study the implicit bias of specific optimization algorithms such as gradient descent i.e. to what train- ing loss minimizer the model parameters will converge to (Du et al., 2019) Allen-Zhu et al.. 2019). Our results use the NTK formulation of wide neural networks (Jacot et al. 2018), and specifically we use linearized neural networks to approximate such wide neural networks following Lee et al. (019). There is some criticism of this line of work, e.g. Chizat et al. (2019) argued that infinitely wide neural networks fall in the "lazy training" regime and results might not be transferable to gen- eral neural networks. Nonetheless such wide neural networks are being widely studied in recent years, since they provide considerable insights into the behavior of more general neural networks, which are typically intractable analyze otherwise.
2 PRELIMINARIES
Consider a data domain X' x y C Rdd x R that consists of K groups (subdomains | where each data point belongs to one of the group We assume that the input space X' a subset of the unit ball of Rd, such that any x E X satisfies ||æ||| < 1. We are given training set ((x;; yi) }))² i.idd sampled from some underlying distribution P over X x y. Let the K groups be Di.... DDx where
each D, is a subset of X x y. Let Px(z) P(z|= E Dx) be the conditional data distribution over DR. where z = (æ, y). Denote X = (ZI,.... xx,) E Rddn and Y = ( ... vn) E R"; (9(21).... g(xn)) Let the loss function be l : y x y + [0. 1]. In vanilla training, the goal is to minimize the expected risk denoted by R(;; P) Ez- ((([ which is done by minimizing the empirical risk R(J) = : ((f(m))
for any function g X + R.
overload notation and use gXX)
We prove our results for y C R. but our results can be easily extended to the multi-class scenario y C R.". Thii is the non-overlapping setting. There is also the overlapping setting where groups can overlap with each other. We focus on the non-overlapping setting in this paper.
2

---

Under review as a conference paper at ICLR 2022
For tasks requiring high worst-group performance, the goal is train model X' + y that performs well over every Pk, which can be achieved by minimizing the worst worst-group risk defined as
Runxx (f:P)
max R(f:P()=
= max E Ea-rl((((o) Ex] k= K
(I)
k=I,-KK K
2.1 REWEIGHTING ALGORITHMS
Most existing methods that minimize the worst-group risk are reweighting algorithms that assign each sample with a weight during training and minimize the weighted average risk. time we assign a weight 9.² to sample 2,, and minimize the weighted empirical risk:
1
(
9i
(4) [(f().))
i=1
= where q0)= (ql".... ...) and qi
qn
A static reweighting algorithm assigns to each z; (æ,, v/) a fixed weight q that does not change during training, i.e. y.') = 9i famous example is Importance Weighting (IW, Shimodaiaa (200 in which if 2; E DD and the size of DD is ny, then 9: (Kn+) ) Under IW, each group has the same weight, and the reweighted empirical risk a simple (unweighted) average of the empirical risk over each group, so that each group has an equal contribution to the overall risk objective. Note that ERM is also a special case of static reweighting algorithms: by assigning Q1 =... ln 1/n.
On the other hand, in a dynamic reweighting algorithm, qd changes with t. Specifically, it up- weights samples over which the model has high risk in order to help the model learn "hard" samples. A popular dynamic reweighting algorithm Group DRO (Sagawa et al. 2020a). De- note the empirical risk over group & by (f),), and the model at time by f()) Group DRO sets (t) (t)
(4) q 9t /ng for all 2; DR where 9% is the group weight that is updated by
9 gk
(t) (t-1) exp (1)
(Vk: 1,... K)
(3)
(4) 1. Sagawa et al. (020a) proved for some >> O, and then normalized so that di .... On
(1)
convergence rate theorem (their Proposition 2) showing that the convex setting, the worst-group training risk of Group DRO converges to the global minimum with the rate (t-1/22..
There are many other reweighting algorithms. Particularly, all variants of DRO and DRO-based methods like CVaR and 2DR are reweighting algorithms. See Appendix A for more examples.
2.2 REWEIGHTING ALGORTHTS CAN EASILY OVERFIT
In this section, we will empirically demonstrate that while IW and Group DRO can achieve higher worst-group test performances than ERM at the early stage of training, they can easily overfit after number of training epochs.
Following Sagawa et al. (2020a), we conduct the experiment on two datasets: Waterbirds and CelebA. Each dataset contains a binary confounding variable and binary target variable di- viding the dataset into four groups (four combinations of (a, y)). In Waterbirds y is the type of the bird and is the background; In CelebA y whether the person has blond hair and is whether the person is male. On each dataset, a model trained by ERM always exhibits a very strong empirical correlation between y and a, its performance is to make the model perform well on every group. See Appendix C.I of Sagawa et al. (2020a) for detailed information of these datasets.
of the groups is extremely poor. The goal
On each dataset, we use the ResNet18 8 model as the classifier and optimize it with momentum SGD. We run each of the three algorithms: ERM, IW and group DRO (GDRO), for 500 epochs Wa- terbirds and 200 epochs on CelebA, and plot the average training/test and worst-grouu (WG) train- ing/test accuracy curves throughout training in Figure] From the plots we can conclude that:
All algorithms can achieve and maintain high average training/test accuracy throughout training, i.e. there is almost overfitting in the average test accuracy.
3

---

Under review as a conference paper at ICLR 2022
WArt Goog Tep Acuuacy
26
Ave 00
Wind gooeogoo
16
PR0
300
400
100
500
102
200
200
Epochs
Eocoho
(a) Avg train acc.
(b) Avg test acc.
(c) WG train acc.
(d) WG test acc.
Windggge Torderg wadggkann
Wost G000 Tox Aouuayy
Avorgo Nounde
0:25
2.0
0.7
20.
10
0.23
200
(c) Avg train acc.
(f) Avg test acc.
g WG train acc.
(h) WG test acc.
Figure I: Performances of ERM, IW and Group DRO. First row: Waterbirds. Second row: CelebA.
Regarding the worst-group test accuracy, while the two reweighting algorithms outperform ERM by a large margin at the early epochs, they overfit very quickly. On CelebA after roughly 100 epochs, the worst-group test accuracies of the two reweighting algorithms become the same as ERM. On Waterbirds, the worst-group test performances of IW and Group DRO drop significantly after around 30 epochs though they still better than ERM.
IMPLICIT BIASES REWEIGHTING ALGORITHMS
In the previous section, we empirically demonstrated that the worst-group test performances of reweighting algorithms converge to the same level as ERM. To theoretically understand why this happens in practice, we analyze the implicit biases of reweighting algorithms. Our main theorem (Theorem(6) states that almost all reweighting algorithms (including ERM) have equivalent implicit biases, in the sense that they converge to the same interpolator. Mcanwhile, it is observed in practice that the ERM interpolator has a poor worst-group test performance. This leads to the pessimistic result that reweighting algorithms always overfit. All proofs can be found in Appendix B
3.1 LINEAR MODELS
We first demonstrate this pessimistic result on simple linear models to provide our readers with a key intuition, and later we will apply this same intuition to neural networks. Let the linear model be f(x) = (0, x). where 0 E Rd. In the overparameterized setting, we have d > n. Consider using the squared loss f(j. v) 1 (ū- y)², and minimizing the weighted empirical risk with gradient descent:
g(++1) = =(()
9
Vol(f()(x)) y:)
(4)
where 7) >> 0 is the learning rate. For a linear model with the squared loss, the update rule is
n
g(++ = g(t) 17
xz (zx) - ys)
(5)
It is a well known result that under the overparameterization setting where d > n, if Φ1,-... Cn are linearly independent, then with a sufficiently small n, linear model trained by ERM can always converge an interpolator which fits all training samples (i.e. g(t) - 0" such that (0", ,0=) V for all i). Here the linear independence is necessary, because otherwise in the extreme case where 31 x2 but y1 * y/, the model cannot fit (æ1.31 and (x2, 92) simultaneously.
In this section, we aim to extend this ERM convergence analysis to general reweighting algorithms. Our results require the following assumption:
Assumption 1. There exist constants q1 ".. In such that for all i, q. - as + co. And min; 9: = = 0.
4

---

Under review as a conference paper at ICLR 2022
(6) This assumption avoids the scenario where there is some such that q; ~ 0 for all I, in which case the model could never fit Z₁. Assumption [ emmpirically holds for Group DRO on Waterbirds and
CelebA (see Appendix D.2p. Under this assumption, we can prove that the model always converges to an interpolator:
Theorem 1. For any reweighting algorithm satisfying Assumption 7 $1 In are linearly independent, then there exists an no > such that for any 17 S 77. as t - co, (0) converges to some interpolator 0 such that for all i, (0", .x)) = Vs-
We now make the following key observation regarding the update rule (5) ((++1) g is lin- ear combination of æ1,". En for all and thus g(0 ((0) always lies in the linear subspace span( (z1.- ................................ T..) Note that this is an n--iimensional linear subspace if #1,-. In are linearly in- dependent, and by Cramer's 's rule, there is exactly one ê in this subspace such that (0)) x3) = y: for all i, which implies that l = + g(0) is unique. Together with Theorem | this leads to:
Theorem 2. If ,i. In are linearly independent, then there exists To > O such that for any reweighting algorithm satisfying Assumption / and any n S n0. (00) converges to the same interpo- lator 8 that does not depend on q,"
(6)
Note that ERM is also a reweighting algorithm satisfying Assumption tially proved the following result: The implicit bias of any reweighting algorithm satisfying Assump- tion 1 is equivalent to ERM, so reweighting algorithms always overfi
1 Therefore, we have essen-
The key intuition here is that matter what reweighting algorithm use, 0(0) - ((0) always lies in a low-dimensional subspace, in which the interpolator is unique. Therefore, as long as a model trained by the algorithm converges to some interpolator, it must converge to that unique interpolator, which means that the implicit bias of the algorithm is equivalent to ERM.
3.2 LINEARIZED NEURAL NETWORKS
Now we prove the same result for neural networks. Of course it would be very hard to prove for all neural networks. However, we can prove the result for family of overparameterized neural networks that can be approximated by their linearized counterparts Lee et al. (2019). Denote the neural network at time by (x) = f(x; g(t) which is parameterized by g(d) E IP where is the number of parameters. The linearized neural network of (x) is defined as
1 (z) = 1 (xx (0(0) 000), Vo Vol (0) (x))
(6)
where we use the shorthand V (0) = Vol (a; 0) 0= Consider training _(( (xx) via gradient
descent on the reweighted risk (as in (4) using the squared loss. Given training set {(x,, y:) Fi
we can construct a new training set { (f)(((()))))))))))))())()))) yi - (() (x:)) (<:)))²= so that training a linearized neural network on the original training set equivalent training a linear model on the new training set. Based on this observation, we have the following corollary of Theorem 2
Corollary 3. If (z))) (o (mx)) are linearly independent, then there exists no such that for any reweighting algorithm satisfying Assumption and any vj S 1/o, ((0) converges to the same interpolator 0" that does not depend on qi-
Here we are still using the key intuition: g(t) - g(() always lies in the n-dimensional linear subspace
span ( (V, (0) (x1). .... (xx,) By Cramer's rule, there is a unique interpolator H* such that 0" - (00) E span (Ver (x))), .... (e (xx,)). and g(0) always converges to that 0" Thus, we have essentially proved that for linearized neural networks, reweighting algorithms always overfit.
Now let us delve deeper into the training dynamics of lincarized neural network. Note that Volle (6)
(x) vo (X) E IR the change in the training function value vector is Jin (((+1) (X) Jlin
(t) V V (X) (X) = Vo (X) /o
'y overfit, we saying that the training error of the model trained by the reweighting algorithm will converge zero, hut the gorst-group test performance will converge to the same low level ERM.
5

---

Under review as a conference paper at ICLR 2022
where Q diag(1) (-) .... ,9 The function value vector moves along the kernel gradient with
(t)
respect to θ (0)
= (a () (X) Va. (x)@() Meanwhile, the neural tangent kernel (NTK,
glt)
Jacot et al. (0088) is ( (zz x') = Vof (x) (x) Vof(0) and the Gram matrix is ( =
( (x, Xx) so θ (()) @ Q(t))))) We can thus extend our result for gradient descent on lincarized
((
neural networks to a kernel gradient descent algorithm as above.
3.3 WIDE FULLY-CONNECTED NEURAL NETWORKS
Now prove the result for sufficiently wide fully-connected neural networks, which can be ap- proximated by the linearized neural networks. First we define fully-connected neural network with L hidden layers (we always assume L 1 so there is at least one hidden layer). Let h' and æ' be the pre- and post-activation outputs of layer 1, and di be the width of layer 1. Let x" = æ and
dn d. Define the neural network as
h Wi
di x' 3b'
01-0,...
(8)
x x' = oh
where is a non-linear activation function, W Rd and W Rixd,, The parameters 0 consist of W W ... W and 10,- ... .1²' (0 is the concatenation of all flattened weights and biases). The final output of the neural network is fxx h4+1, And let the neural network be initialized as
W (0) NO, (00) 1)
W [(0) 0 b ((0)
(1=0, ... --0,,..,,-11 and
10,
We also need the following assumption for approximation theorem: Assumption 2. is differentiable everywhere, and both and à are Lipschitz
Difference from Jacot et al. (2018). Our initialization p is different from the original one in Jacot et al. (2018) in the last (output) layer. For the output layer, use the zero initialization {j = instead of the Gaussian initialization w ~ (0, 1). This modification enables us notice that the proofs in [ee et al.) (2019) (particularly the proofs of their Theorem 2.1 and their Lemma 1 in Appendix G) are flawed. In Appendix C we will explain what goes wrong in their proofs and how we manage to fix the proofs with our modification.
to accurately approximate the neural network with its linearized counterpart (6).
For our new initialization, still have the following NTK theorem:
Theorem 4. If a is Lipschitz and 5o for 1..... ,L sequentially, then (0) xx) converges in probability to non-degenerated deterministic limiting kernel O x').
The kernel Gram matrix θ = 0(X,X) E RaxR is a positive semi-definite symmetric matrix. Denote its largest and smallest eigenvalues by A and Amin, Note that O is non-degenerated, so we assume that A > (which holds almost surely in the overparameterized setting where dz n). Then, we can prove the following approximation theorem:
Theorem (Approximation Theorem). Let 1ÿ" (Amin Amax)-1. For fully-connected neural network f(t) that satisfies Assumption 2 and trained by any reweighting algorithm satisfying Assumption let e(t) be its linearized neural network which is trained by the same reweighting dr. d and
algorithu (i.e. Vi,t, gi are the same for both networks). If d, d2 there exists Ú and constant C such that as long as 17 11" and
min > 0, then for any d 2 for any test point x E IRd such that ||>||| $ 1, with probability at least 8 over random initialization,
sup
(x) (z) S Cd--144
(10)
'f is Lipschitz, if there exists constant I. > 0 such that for any æ 22, 1 (f()) S [|æ] Non-degenerated means that (ax, xx) depends x and xr' and is constant.
x2

---

Under review as a conference paper at ICLR 2022
Remark. We can easily extend this theorem the case where there exists as for each of 1 2. such that di/d1 + aj and d1 - SC.
Combining all the above results altogether, we achieve our main theorem:
Theorem 6. Under the conditions of Theorem [ there exists an Tn1 > 0 such that if L S Ti and
Val (ar ), f
(arn) ) are linearly independent, then as d - oo, any test point a R
such that [ S 1, with probability close to 1 over random initialization,
lim limsup (10 M1 (a) -0()-1/4) (1:00
(11)
where f()) is trained by the reweighting algorithm and JERM is trained by ERM.
The main theorem shows that at any test point æ, the gap between the function values of the two models converges to an infinitely small term, so the worst-group test performance the reweighting algorithm will converge to the same level as ERM. Therefore, we have proved that for sufficiently wide fully-connected neural networks, reweighting algorithms always overfit.
Our key intuition tells us that the change in the model parameters always lies in an n-dimensional subspace. Thus, one possible way to improve the worst-group test performance to enlarge this subspace by adding more training samples, e.g. via data augmentation semi-supervised learning. However, even if we have more training samples, as long as the model is still overparameterized, and all ( (x;; are linearly independent, then our result still says that no reweighting algorithm can do better than ERM in the long run (though the performance of ERM itself might be improved).
Moreover, our theoretical results can explain the surprising empirical observation in [Saaaaa et al.) (2220b) that removing some samples from the majority groups to match the group sizes some- times achieve even higher worst-group test performance than reweighting even though it wastes lots of data (see their Section 6). When training samples removed, the model will converge to in- terpolator of the smaller training set which different from the interpolator the original training set, so there chance that the performance of the new interpolator is actually higher.
4 DOES REGULARIZZTION REALLY HELP?
In the previous section, we proved the pessimistic result that reweighting algorithms always overfit, iee in the long run their worst-group test performances always drop to the same level as ERM. And even if we use strong data augmentation or semi-supervised learning, reweighting algorithms still cannot outperform ERM if the training set is not sufficienlly enlarged.
Sagawa et al. (2220a) proposed to tackle the overfitting problem of reweighting algorithms via regu- larization, In particular, they empirically demonstrated with experiments that large regularization is required to prevent reweighting algorithms such group DRO from overfitting. With a large regu- larization, the model can maintain a high test worst-group performance, but cannot obtain perfect training accuracy, in contrast the case where no regularization is applied.
In this section, we study the necessary conditions for regularization to maintain high worst-group group test performance. Specifically, we will show that regularization will not work if it is not large enough to prevent the model from obtaining nearly zero training error. In other words, lowering the training performance the key to keeping high worst-group test performance. Note that the results in this section do not require Assumption 7 so the results hold for all reweighting algorithms.
4.1 THEORETICAL ANALYSIS
Consider a reweighting algorithm with sample weights q; (c) consider adding L2 penalty to the weighted empirical risk
Following Sagawa al. (020a), we
RH (1
(f)
d 19 ((f(()) vi) +
/ I|e g(0) | 2
(12)
Given that sufficiently wide neural networks can be approximated by linearized ones, we first focus on linearized neural networks. We will use the subscript "reg" refer regularized model (which

---

Under review as a conference paper at ICLR 2022
trained trained by minimizing the regularized risk 12)). Let f be regularized linearized e(e) neural network trained by some reweighting algorithm, and fiiEERM be an unregularized linearized neural network trained by ERM. As before, we consider training the models with gradient descent under the squared loss ((Ú. v) (0 y)²- The following result shows that these two models are very close if f can achieve low training error:
Theorem 7. If there is constant Mo > 0 such that (of S Mo for all ||0| I 1, (of(")(a)) (x))) are linearly independent, and the empirical training risk of Jinreg
satisfies
lim limsup R(Jinnee) <,
(13)
(-400 for some c > 0, then for any test point such that || S we have
limsup
Tinreg (2) (I)EM(())) O(VE).
(14)
2-000
The proof of this theorem also follows the key intuition: we can show that even with the L2 penalty added, g(+) - g(0) is still limited in a low-dimensional subspace. And although we cannot prove that ((+) always converges to the ERM interpolator, we can prove that it can get very close to that interpolator if its training error is very low, so the resulting model is very close to the ERM model.
Then, we can extend this result to sufficiently wide fully-connected neural networks:
Theorem 8. If A Aim and μ O, then let 1)" (u+A*mi + A mmx) -1 For a wide fully- fully-connected
p(t) neural network freg defined by 8 and (9) and satisfying Assumption dr 1) n1,, (o (x1), .., Vos (m)) are linearly independent,
2 and any reweighting algo-
rithm, di d2
and the empirical training risk of flly satisfies
limsup R( <
(15)
1-XX
for some >> O, then as d -> co, with probability close to I over random initialization, for any test point x such that || S 1 we have
lim t-000
( (x=) ( (20) = - V +0V=
(16)
The result shows that a regularized model trained by any reweighting algorithm will get very close to unregularized ERM model at any test point æ if the training error of the former is nearly zero Thus, regularization only helps when it is large enough to keep the training error of the model away from zero by margin.
Our results explain the empirical observation of Sagawa et al. (2020a) that by using large regular- ization, the model can maintain high worst-group test performance, but it cannot achieve perfect training accuracy. If smaller regularization is applied and the model can achieve nearly perfect training accuracy, then its worst-group test performance will still significantly drop.
4.2 EMPIRICAL STUDY
In this section, we validate our theoretical results above with experiments on Waterbirds and CelebA. We run ERM, IW and group DRO under different levels of weight decay for 500 epochs on Water- birds and 250 epochs on CelebA. Note that we do not strictly follow our L22 penalty formulation [2.. but we study the T-2 weight decay regularization which most widely used in practice. We re- peat each experiment five times with different random seeds and report the 95% confidence interval of the mean average training and worst-group test accuracies of the last 10 training epochs in Table also report the mean accuracies of epochs 11-20 with no
To compare with early stopping, regularization in blue. Moreover, we plot the average training and worst-group test accuracy curves throughout training for IW and Group DRO with of the random seeds in Figure 2
On both datasets, early stopping achieve the best performances. Particularly, on Waterbirds, there is no clear sign that regularization could help prevent overfitting. When the regularization is small,
8

---

Under review as a conference paper at ICLR 2022
Table 1: Mean average training accuracy and worst-group test accuracy (%) of the last 10 training epochs of ERM, IW and Group DRO under different levels of weight decay (WD). Each entry is Average training accuracy Worst-group test accuracy. Blue entries are mean accuracies of epochs 11-20 with no weight decay. Each experiment is repeated five times with different random seeds.
Dataset
WD
ERM
IW
Group DRO
0
100.0 + 0.0/56.3 + 1.8
100.0 0.0/67.6 1.1
100.0 + 0.0/641.5 + 1.6
(11-20)
(Early stopping)
92.4 0,483.7
92.9 = 0.4/79.9 + 2.1
Waterbirds
0.05
100.0 0.0/1.0 1.9
100.0 + 0.0/63.5 + 2.6
0.1
100.0 0.067.77
100.0 0.0/5..774 2.7
0.15
99.0 2.753...7..
99.4 0.6/52.5 + 2.5
0.2
91.6 2.0335.
94.8 0.9/38.0 7.5
0
99.0 + 0.2/40.2 5.6
99.4 1.14
99.4 0.1/49.5 1.9
(11-20)
(Early stopping)
92.1 0.378.2
90.5 + 0.5/85.2
CelebA
0.01
2.2
96.5 - 0.5/67.2 1.7
0.03
95.0 + 0.2/62.8 2.4
88.9 + 1.1/83.1 + 2.2
0.1
89.4 - 2.0/76.0 2.4
75.1 = 9.5/50.6 + 15.9
Wort grou Tea hoourt
0a
N2- 0.00
23
yc: D.00
2.53
222
250
100
200
250
100
20C
250
100
150
252
Ecooha
Eppcis
Epochra
Epocts
(a) IW: Avg Train Acc.
(b) IW: WG Test Acc.
(c) GDRO: Avg Train Acc. (d) GDRO: WG Test Acc.
Figure 2: Average training accuracy and worst-group (WG) test accuracy of IW and Group DRO
(GDRO) under different L2 weight decay levels on CelebA.
the training accuracy is still 100% and the algorithm continues to overfit. However, when the regu- larization is large enough to lower the training accuracy, the worst-group test accuracy drops more because the model cannot learn the samples well under such a large regularization. Thus, perhaps not surprisingly, a lower training performance is only necessary condition but not sufficient.
On CelebA, regularization does help mitigate overfitting, but a useful regularization must be large enough to lower the training accuracy. We observe that Group DRO overfits more slowly than IW, as it still has over 70% worst-group test accuracy after 70 epochs. However, as Figure 2d clearly shows, its worst-group test aceuracy will still drop to the ERM level at 200 epochs. We also notice that Group DRO requires a smaller regularization than IW: for IW we need the weight decay level to be as large as 0.1 to achieve similar performance early stopping, but for Group DRO it only needs to be 0.01, and using 0.1 is actually harmful.
Overall, we find that early stopping achieves markedly better performance. On the other hand, using large regularization could result in training instability, as well as loss in overall performance, and there may or may not be a small band for the regularization parameter where the worst-group test performance is better.
5 CONCLUSION
In this work, we theoretically studied why reweighting algorithms overfit in practice by analyzing their implicit biases. Specifically, we proved the pessimistic result that reweighting algorithms al- ways overfit. Our proof was based on the key intuition that the change in model parameters always lies in a low-dimensional subspace, so that even with reweighting, the model still converges to the same unique interpolator. When regularization is applied, we proved that the regularization must be large enough to keep the model from achieving nearly zero training error in order to prevent overfitting. We empirically validated our theoretical results on real datasets, and our results can also explain the empirical observations in previous work. Our results are especially important for large-scale machine learning tasks, where early stopping is not always possible in order to achieve high performances. Practitioners shooting for high worst-group performances in those tasks must be very careful about to what extent overfitting affects reweighting algorithms.

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
To guarantee the reproducibility of all our empirical results, in all our experiments use fixed set of random seeds, and we run some of the experiments twice with the same random seed to make sure that the outputs are the same. See Appendix [.I for experiment details. After this paper is deanonymized, we will provide a GitHub repository that contains all the codes, datasets, hyperparameters. random seeds, machine speculations and anaconda environment speculations that are sufficient to exactly reproduce our empirical results.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In International Conference Machine Learning, pp. 242-252. PMLR, 2019.
Su Lin Blodgett, Lisa Green, and Brendan 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, pp. 1119-1130, Austin, Texas, November 2016. Association for Computational Linguisties. doi: 10. 11883611/D166 1120.
Lénaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. International Conference on Machine Learning, pp. 1675- 1685. PMLR. 2019.
John Duchi and Hongseok Namkoong. Learning models with uniform performance via distribution- ally robust optimization. arXiv preprint arXiv:1810.08755 2018.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations theoretical computer science confer- ence, pp. 214-226, 2012.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In D. Lee, M. Sugiyama, U. Luxburg. I. Guyon, and Garnett (eds.), Advances Neural Information Processing Systems, volume 29, pp. 2315-3323 Curran Associates, Inc., 2016.
Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness with- out demographics in repeated loss minimization. In Jennifer Dy and Andreas Krause (eds.), International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1929-1938 Stockholmsmässan. Stockholm Sweden, 10 15 Jul 2018. PMLR.
Dirk Hovy and Anders Søgaard. Tagging performance correlates with author age. In Proceedings of the 53rd annual meeting of the Association for Computational Linguistics and the 7th interna- tional joint conference on natural language processing (volume 2: Short papers), pp. 483-488, 2015.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Matt Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness. In Advances in neural information processing systems, pp. 4066-4077 2017.
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- 2019.
Evan Z Liu, Behzad Haghgoo, Annie S Chen, Aditi Raghunathan, Pang Wei Koh, Shiori Sagawa, Percy Liang, and Chelsea Finn. Just train twice: Improving group robustness without training group information. In International Conference on Machine Learning, pp. 6781-6792. PMLR, 2021.
10

---

Under review as a conference paper at ICLR 2022
Yonatan Oren, Shiori Sagawa, Tatsunori Hashimoto, and Percy Liang. Distributionally robust lan- guage modeling. In Proceedings of the 2019 Conference on Empirical Methods in Natural Lan- guage Processing and the 9th International Joint Conference Natural Language Processing (EMNLP-IJCNIPP), pp. 4227-4233 Hong Kong, China, November 2019. Association for Com- putational Linguisties. doi: 10.18653/v//D1911433
John Rawls. Justice as fairness: restatement. Harvard University Press, 2001
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. In International Conference on Learning Representations, 2020a.
Shiori Sagawa, Aditi Raghunathan, Pang Wei Koh, and Percy Liang. An investigation of why over- parameterization exacerbates spurious correlations. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceed- ings of Machine Learning Research, pp. 8346-8356. PMLR, 13-18 Jul 2020b.
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.
Rachael Tatman. Gender and dialect bias in youtube's automatic captions. In Proceedings of the First ACL Workshop on Ethics in Natural Language Processing, pp. 53-59, 2017.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint 101 101 2010.
Ziyu Xu, Chen Dan, Justin Khim, and Pradeep Ravikumar. Class-weighted classification: Trade- offs and robust approaches. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 1 119 of Proceedings of Machine Learning Research, pp. 10544-10554. PMLR, 13-18 Jul 2020.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P Gummadi. Fair- ness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment. In Proceedings of the 26th international conference on world wide web, pp. 1171- 1180, 2017.
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In International Conference on Machine Learning, pp. 325-333, 2013.
Runtian Zhai, Chen Dan, Zico Kolter, and Pradeep Ravikumar. Doro: Distributional and outlier ro- bust optimization. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 12345-12355. PMLR, 18-24 Jul 2021.

---

Under review as a conference paper at ICLR 2022
A OTHER REWEIGHTING ALGORITHMS
In this section, we will review some other previously proposed reweighting algorithms. First, we will look at DRO-based methods, where DRO stands for Distributionally Robust Optimization.
DRO is designed for tasks with distributional shift, where the training distribution and the test distri- bution are different, and there are some constraints on the distance between these two distributions (typically described by a divergence function D). Since the real test distribution is unknown, DRO minimizes the model's 's risk over the worst distribution that satisfies the distance constraints, which is an upper bound of the model's real test error. Formally speaking, given a training distribution P. DRO minimizes the expected risk over the worst-case distribution Q in ball w.r.t divergence D around the training distribution P. For group shift problems which require high worst- worst-group per- formance, Q also needs to be absolutely continuous with respect to P, i... Q < P. Overall, DRO minimizes the following expected DRO risk:
(0,,00; P) sup (RQ]e(0; Z)]: D(Q |1 P) s QEP
(17)
The expected DRO risk is typically minimized in the following way: for each epoch 6, we first find the worst Q that maximizes EE [f( 2)] and satisfies D(Q P) S p. Q & P. and then minimize the model's expected risk over this Q with gradient descent. The rationale behind this algorithm is the famous Danskin's 's Theorem, which says that if F(x) is the maximum of a family of functions, then its gradient at point & is equal to the gradient of the function that attains the maximum value at
Note that in practice we only have a finite set of training samples {z1, {z ,z,,, so P is always chosen as the empirical distribution, i.e. uniform distribution over ž1, , Then, note that Q < P. which implies that the support of Q must be a subset of the support of P. which is {21. .z.. This means that Q must be distribution over 21, ....... Zn. i.c. is reweighting over the training samples. Thus, we have essentially showed that DRO is reweighting algorithm, and in fact almost all methods based on DRO are reweighting algorithms.
Zn.
Two widely used variants of DRO are CVaR (Conditional Value at Risk) and 2-DDO.. In CVaR, for a fixed a E (0, 1), we let D(Q P) sup log 4Q an integer, then CV&R will assign weight _ to an training samples that incur the highest losses, and weight to the rest of the samples, so we can easily see that CVaR is a reweighting algorithm. -DRO was first used in Hashimoto et al. 2018 deal with fairness tasks where the group labels are unknown, where reweighting algorithm.
dP and - log a. As a result, suppose that an
2 [dQ
dP and (2 1)?. x2 2-DRO is also a
There are many other previously proposed methods of maximizing the worst-group performance that also reweighting algorithms. For instance, Xu al. (2000) studied the imbalanced class problem where a standard trained model always has high performance over classes with many train- ing samples and low performance over minority classes. They proposed balance the classes with Label CVaR, which is based on DRO and is a reweighting algorithm.
Liu et al. 202T) proposed two-stage training process called JTT: in the first identification stage they trained a model with ERM to identify training samples that are hard to learn, and in the second upweighting stage they trained new model with the hard samples upweighted, so that the model could learn all samples equally well. As the process itself suggests, JTT is reweighting algorithm.
Finally, Zhai et al.] (2021) argued that DRO-based methods are very sensitive to outliers in the training set because they upweight training samples with high losses and outliers tend to incur high losses. They proposed the DORO algorithm which at each iteration removes the samples with the highest losses, and then performs DRO on the rest of the samples. DORO is reweighting algorithm.
B PROOFS
Notations. In all of the proofs, for a matrix A, we will use ||A]]] to denote its spectral norm and A p denote its Frobenius norm.
12

---

Under review as a conference paper at ICLR 2022
B. PROOF OF THEOREM !
To help our readers understand the proof more easily, we will first prove the result for static reweight- ing algorithms where q;
(t) qi for all t, and then we will prove the result for dynamic reweighting
algorithms that satisfy Ca
(*) - Ti as t -> xc.
B.1.1 STATIC REWEIGIITING ALGORITIIMS
We first prove the result for all static reweighting algorithms such that min, 9; = q" >
We will use a standard optimization proof technique called smoothness. Denote The empirical risk of the linear model f(x) (0,x)) is
Σx=
|
F(0)
Σ
(, 0 y1)
(18)
i=1
whose Hessian
(Or( = 2 Σ
q:a.a.0
(19)
1=1
So for any unit vector v E Rd. have (since qi E [0,1])
V}F(0)== = Σ (1 v)² s v)
m S 24
(20)
which implies that F(0) is 24-smooth. Thus, we have the following upper quadratic bound: for any 01,65 02 E Rdd
F(02)= S F(01) + (VoF(01), 02 01) + A 02 0111
(21)
Denote (((()) = VX g(t) Y) E Th' where /Q- = diag( TTi ... VTx). We can see that
[g(00)) 2 F(B(")), so that (F(((() = 2X (g(((()) The update rule of a static reweighting
algorithm with gradient descent and the squared loss is:
g(++1) =(() n
q: gx - yi) -(() - V
(22)
Substituting 01 and 0g in 21 with ( and ((++1) yields
F(o(++1) F(O(t)) - )
( + 1|11x @ococo))
(23)
Since 1 Inn are linearly independent, X X is a positive definite matrix. Denote the smallest eigenvalue of X T X by Amin > 0. And || (0(0)))))) | 2 / [|9(0()))] F(OW)), so have (0(0)) T VQ x x (Qg(o(0) 2 g" min (((())) Thus,
F(g(++1)) =((((() 2719" uii F(O(()) ) An²
X X
(((()))
122
2
s F(((()) 2ng"" min F(O(1)) + An2
x / F(O(1))
(24)
S F(B(0) 2n99* min X F(B(0)) + An?
| F(((o))
(1 2114" A + ((((t))
Let noo mmn - For any 17 no. we have F(o(++1) S (1 11= Amiu F()()) for all t, which
implies that ro F(O(()) 0. Moreover, v F(O0++1) < (1 120 m vi - x/2.
F(O()) due to
13

---

Under review as a conference paper at ICLR 2022
The convergence in F(6) implies the convergence in 8. This is because
[olt)) - 8(0) |
||= = n² X Ro(oco)
11
|
x
(25)
S 1² || g(0(0))
which implies that for any 17 S 1/0.
|
- o(0) ||
S v Ar
F(O() < F(O(F)
2A q-' Amin
(26)
t=
Therefore, lim to some interpolator.
Ei= |1(0+1) - -000| = 0, which means that (00) converges, and it converges
B.1.2 DYNAMIC REWEIGHTING ALGORIHTM
Now prove the result for all dynamic reweighting algorithms satisfying Assumption By As- sumption I for any c <> 0, there exists te such that for all 2 te and all i,
q E (q: - c, c,++t)) +
(27)
This is because for all i, there exists &s such that for all t 2 t,. d0 E (q: -q- + c). Then, we can define te max(t1,-.. .. Denote the largest and smallest eigenvalues of X X by A and Amin, and because X is full-rank, we have Amin > O. Select and fix an e such that 0 0<E max : (q" ( J, and then L, is also fixed.
We still denote Q = diag(gı,' ... (2)- When 2 fer the update rule of a dynamic reweighting algorithm with gradient descent and the squared loss is:
g((+1) = g(t) x (X) g(t) Y)
(28)
where Q ((t), and we use the subscript to indicate that 0
00 -e// <. Then, note that
we can rewrite o² as Q! V 3e vQ for all < 4²/3. This is because yi te < v (q: + 3e );)
and qi e > Vla 3e)g: for all < /:/3, and 2 g Thus, we have
g(++1) p(1) - -000 nxx v g(((t)) where Q. = (0)
(t)
.QQQ/QQ
(29)
Again, substituting 0, and Oz in 21 with ((0) and ((++1) yields
1111x V (etor //2 1 (30)
F(g(++1)) S F(((0) - (T)( QQ x x
12) g(())) + A n
Then, note that
90(10) V x x ( (V 1@100 - -vQ) ((r0o)
(VOS. (1) - -vQ) | |
5 x x
2
(31)
Q
X 112 / Q v@
2
< max (((())
where the last step comes from the following fact: for all e < 91/3,
96 + 36
V
and Va Vu: 3c - V36
(32)
14

---

Under review as a conference paper at ICLR 2022
And as proved before, also have
9(0(0)) (T x x x X'x Qg((())) 2 qmmm F(B(1)
(33)
(9 Xminn 12Amax
Since e _
we have
0(0(0)) vQ x
x x x ((0(0)) (9 A Amax /36)
/3E) F(B(C)) 2 29 Amin )mbuF(((())
(34)
Thus,
744 min P(0(() + An" x xVO.00
|
< F(0(0) F(0(++2))
(35)
(1 71" X min A21 3c))
$ (1- 179" min + -2421)2)
minر For any 7) S 7/a, we have F(A(++1) S (1-799 A min (2 for all t 2 fe, which implies that lim; F(B(t) = 0. As before, we can prove that the convergence Thus, converges to some interpolator.
for all < 1/3. Let = 2- 4A= For
F(0) implies the convergence
B.2 PROOF OF THEOREM 4
Note that the first I layers (except the output layer) of the original NTK formulation and our new formulation are the same, so we still have the following proposition:
Proposition 9 (Proposition in Jacot al. 2018)). If Lipschitz and di -+ oo for 1, L sequentially, then for all 1 I..... L., the distribution of single element of h' converges in probability to zero-mean Gaussian process of covariance E! that is defined recursively by:
1
Σ 3z (1) = x
x'
+ 32
do
(36)
('x, = ( [o[ (x) (f(x'))) g²
where f is sampled from zero-mean Gaussian process of covariance 1(-1)
Now we show that for an infinitely wide neural network with L 2 1 hidden layers, ( converges in probability to the following non-degenerated deterministic limiting kernel
= E (f(((=)) 8²
(37)
Consider the output layer h the output layer,
Wr (hh)) + 9bb. We can see that for any parameter 0 before Vā Vā
WLT
Vg h h+1 diag(o(h"))
V Vo = 0
(38)
ddr.
And for W. and bz, we have
V Vw h+1 1+1
(h2")
and
4tth-1== =3
(39)
Vdl
Then we can achieve 37 by the law of large numbers.
B.3 PROOF THEOREM 5
We will use the following short-hand in the proof:
g(0(#)) = (x) - -Y
_((())) vof(X; (((0) E BR
(40)
( = -(((()) ((((0)
15

---

Under review as a conference paper at ICLR 2022
For any 0, there exists such that for all 2 and all i, qi (0) (q: 9: e). Like what
have done in p we can rewrite Q(+) = Q! V @ VQ, where Q = diag((1.") ... ,9n).
The update rule of a reweighting algorithm with gradient descent and the squared loss for the wide neural network is:
g((+1) = 0 - (7() Q g(0(0)
(41)
and for t 2 fe, it can be rewritten
g(++ = g(0) nu ( Q (Qg(o())
(42)
First, we will prove the following theorem:
Theorem 10. There exist constants M 0 and en > O such that for all (0) n S 1"" and
any 8 > there exist Ro > D > and B 1 such that for any d z D, the following (i) and (ii) hold with probability at least (1 5) over random initialization when applying gradient descent with learning rate np
(i) For all S tor there is
|o(000)) S SB'M &B'Ro Ro
(43)
Σ 0000 -0(-11) S SnMRo
Σ
Bá-1
MB Ro
(44)
B 1
j=1
(ii) For all 2 tor we have
012 5(1 1 <11-199 "1q"Amin 1-4
B
(45)
174" 1/0" A
5-4,
Σ j=t++1
(B6) -0(-11)
3 Ro
Σ
1
3
j=t+t
(46)
3 BcMB Ro
9"' Amin
Proof. The proof is based on the following lemma:
Lemma 11 (Local Lipschitzness of the Jacobian). Under Assumption 2 there is constant M
such that for any Co > O and any 8 > O, there exists D such that: If d 2 D, then with probability at least (1 5) over random initialization, for any x such that | l2 S 1,
8) 1|1 -vof(;))Voo(;
- Vof(2x
- Vd
M
0
0
Vof(<z 0)11 $ M
VO,0 B(0
(47)
(100)-10 [[(()-((0)) _10 - M
00-00
Vd
[|](0)) < M
where B(O(o), Ry) = (0 1::0000:1:-0000000000100000 -(0) < R).
The proof can be found in Appendix B.4 Note that for any x, f(0) 36 where b is sampled from the standard Gaussian distribution. Thus, for any > O, there exists a constant Rd such that with probability at least (1 5/3) over random initialization.
|0(0
Ro
(48)
And by Theorem there exists D2 2 0 such that for any d 2 D2, with probability least (1 - 18/3)
< q" \ min
|| -
||e-0001 0
(49)
3
16

---

Under review as a conference paper at ICLR 2022
Let M be the constant in Lemma
11 Let 6o
(a y
108 Let B = 1+ and Co M Ra +
B-1 11 there exists D1 > such that with probability at least (1 6/3),
4/1+3rM1' Ra, By Lemma
9- Ammin
for any 2 DI. is true for all 0,0 E B(00)) Co).
By union bound, with probability at least (1 8). (47 48 and 49) are all true. Now we assume
that all of them are true, and prove (43) and (44) by induction. (43) is true for = due to (48). and
44 is always true for & = O. Suppose
and (44) are true for t, then for t + we have
|| |
g(0) || - 17 [ Q( 1(000))
0/2 S 1010000000 (
|00000)
(50)
$ 17 [ |00ocoN11 I MTBB' R
So 44 is also true for t + 1. And we also have
9(0()+1)) - (((())) + 1looogi ((11)))((1112)) - (000 )
((((
+ -oe---oeeee
((000)
1 (
= nr (ooiin
+
< I Mool//
(51)
2
1 (.) 1 |00000111
< 11 + (a
< + / (
| (0(000))
$ (1 n1+ M²2 |000 /11 - B Ro
Therefore, (43) and (44) are true for all t < t., which implies that || [vQg(((())))
s ||9(0())) =
Bt. Ro. so (45) is true for = te. And (46) is obviously true for t = t.. Now, let us prove (ii) by
induction. Note that when 2 te, we have the alternative update rule 42 If and (46) are true
for t, then for t + 1, there is
|0te11) 1000111 sn <n sn|1ooo 3z
|Veeoocc0// // 1100 |Venracon 1|
1/4"' > Amin t-te
((o(tt)) /| F /11 S MMN1++3
1 (1_79"
S <nVI+3e 3e
B Ro
(52)
So 46 is true for t + 1. And we also have
V (Qg(o(+t))
/ - (Q((
2
2
(Q)(01O)((0ttt)) 0(0) + Q0(0(()) |1/
IV (QQ ((00)) 11000)00100000000000000000 (0(()) + (Q
(53)
< n. /VQ
//1
34
7V QJ J(O(I)
/
i 3e
(1 n7 A min
Ru
3
where (19) is some linear interpolation between (10) and 0(++1), Now we prove that
n A min
- TVQ
<
(54)
3
17

---

Under review as a conference paper at ICLR 2022
For any unit vector RR,, we have
v (I - NVQVV/QQQQ@@.. = 1
- 1 /QQ/Qu -000-/00--0
(55)
||v@el1, e [VTT, , 11, so for any 7 S nn v (I - (1-1/Q9/Q) E |0, "))ming"), which implies
that | - nVQ0/0l1 - - n q²' Thus,
I - (2 J 1(0(0)) [0 WQ 1
< nM Qo Q 2 + 1 V -0-000000))
2 + [ -((00)) [(00)))
< "nming" q-' + 1/ 0 (0oo ( VOol + I (Q(]00)) (( - -(0O)) ((00)))
1 nmtTr n-' + 0 - 1001/ + [(0(0)] (1 - (((1))
<1 nnminng
110" Amin n
(1010)
(00) -000
100 0(0) (1) s
174" A min
Vd
2
(56)
)
for all d 2 max (r, D2,
Co
which implies that
q" Aunin
--nv nV ( (( V
<1 179" Amin
| (VQ(( ((((()))
(Vo!'
(57)
2
<1 77 Ami
nM < 174 Amin
(due 32
for all e S 60- Thus, (45) is also true for l + 1. In conclusion.
(45 and 46 are true with probability
least (1 - 5) for all d D max D1, D2. (12M2co
Returning back to the proof of Theorem Amin min 3x Xmiin }. where Eo defined by Theorem 10. Then, t, is also fixed. There
Choose and fix an such that
exists δ 2 0 such that for any d 2 D. with probability at least (1 6), Theorem 10 and Lemma 11 true and
q" Amin
|
(58)
3
which immediately implies that
|000| < 11011 + -
g10l|
< max + Ammm
(59)
3
We still denote B 1+1 11" 2 and Cu
MB B-1
+
3/1+3eMB's Ra Theorem 9" Amnin
10 ensures that for
all t, g(t) E B(0()) Co). Then we have
I - V
/ 1 Φ
-- T-n/QQX neQQQ/
+n -10)
<
2
(60)
< 1 - min q² + 179" = m
2179" A
3
so it follows that
I -/
(1)
< I 1/ QQ@ VQ
/
(VQ% vQ)l
(61)
2nq" ) min
min
+ ( max
v 3e
3
3
18

---

Under review as a conference paper at ICLR 2022
Thus, for all
q- A 3xmaxx Amin
there is
1/7" Amin
I 1-nvQ0 (0)
VQ%
(
1
(62)
The update rule of the reweighting algorithm for the linearized neural network is:
g(++1) = 0 r) q(()) (in(((())
(63)
lin
where we use the subscript "lin" to denote the linearized neural network, and with a slight abuse of notion denote Pün ( ) ).
First, let consider the training data X. Denote A, (in(((t)) - g(((t)). We have
ginn 9in (0(++1)) 9tnn (0(0) ( ((((0)))))))))))) _(0(0)) gin (0l()
(64)
g(0(+11)) - g(((1) ( (((()))))((())))) 1100 g(((t) g(0(((()))
where ((1) is some linear interpolation between g(+) and ((++1), Thus,
A4+1 - A. =n ((0(0) )( - Q g((())
(65)
By Lemma
we have
((((0) -((()) )(.00)) /
-J((O)) T -1010) Cod
(( ((((())-((00)))
(66)
which implies that for all t < t..
|1+1112 -i-nJ(0000 ()((00)) (( - (0)
A ||, + |/ ( ((000)
- (o000l J
< 1 7)((00)0) (( (1))
|| + +n||s(000) ((000) -
J (oooo) (000 10000000
< (1 + ? | + SyM Roddd
< B 1 122 + MyM2C,BB Rod-
(09)
Therefore, we have
(t- ||--l < B 1A + 2n Rod-
(68)
Since Ag 0, it follows that for all te.
| & M R
(69)
and particularly have
VoA. I1A,,12 S Co -R
1/4 11/4
(70)
For 2 fc, we have the alternative update rule 42 Thus,
-QA411- - VQa.=v//V/
- J(0(0)] (((00))T((((0))) V [VQy(o(tt]
(71)
- ((001) 2 [VQA.
19

---

Under review as a conference paper at ICLR 2022
Let A -----------@00 1==----/0100000000000000 II = -00 /v@ /0 (0) Then, we have
(( J(O(o)- (( Vo!2 (VQg(ol))) (72)
Lety 1
19" m
1. Combining with Theorem 10 and 62
the above leads
|| /QA++1
$|Al|12 V Q | + + V (( - I(Bl0)) [( V I1 |VQooccon/
5> QQ, | + +. ](0 J(B(O) - ((o(o)) )/(o))))) v1 v1+ 30y B²* Ro
<> VQ
+ +2 30y Bd Rod 1/4
(73)
This implies that
y- y-1ht [VA
ST
+ +2 3ey -1-4 B*h Rnd Rod-1/4
(74)
Combining with (70). it implies that for all f 2 te.
|v ||, " Ro [B vI 367 -17 (1 - -b]] /-1/4
(75)
Next, we consider an arbitrary test point such that ||0||2 S 1. Denote & s (xx) - (x))
Then we have
A 1llt1) (ar) - (x)) = V ((0) ) 9in (A(1))
(76)
(()) - (x) = (o) 011) J (( (2) ((0
which yields
8441 6 =1 ((0) Vof(z; ( (()g((()))
(() -0000000000000000000000000000000 Q())))
For t S te, we have
| Sn
V (x; J(())))))))))))))))))))))))))
vef(x; ) ](00))))))))))))) q |0(06)))1
V V0, )(0()))(()) ||r.l2
Val(ar J(((o)) (() |
|
51
(78)
+
|| 2
|(000) P
|l1.l12
1-1 Σ B + 92 Σ
1-1
2on 1/4
Ro
==0
s=0
20

---

Under review as a conference paper at ICLR 2022
So can see that there exists constant C₁ such that || - Cid-1/4 Then, fort > te, we have
Vo Vos(ar; -(0)))) [(00)))))))) v voLz
|V
| - 11 Sn
Vof(2; 0(0)) J(B(0)) T
|Q
+ 17
4-
Cod 1/4 1111/11110 + 3e
Σ
y B²a Ro
s=t
+ nM² 1 3E
MM Ro [t.B+++ + v1 + 3ey '( -te)] d
/
(79)
Note that Σt=o by finite as long as y E (0, 1). Therefore, there is constant C' such that for any t, [1óell2 I Cd Cd-1// 1/4 with probability at least (1 -6) for any d 2 D.
B.4 PROOF OF LEMMA II
We will the following theorem regarding the eigenvalues of random Gaussian matrices:
Theorem 12 (Corollary 5.35 in Vershynin 2010). If A E Rexa is a random matrix whose entries are independent standard normal random variables, then for every L 2 0, with probability at least
1- 2
VP-va-ts Ain (A) S max (A) S vp+ +t
(80)
By this theorem, and also note that WL is vector, we can see that for any 6, there exist ń > 0 and Mj > 0 such that if d > D, then with probability at least (1 -1-00 8). for all 0 E B(O(0), Co). we have
||w||l2 - 3vá
5 L 1)
and
11 S Co 33Vd
(81)
as well as
|b61|2 - M1 Vd
(A] = 0, ................................ L)
(82)
Now we assume that
81 and
82) are true. Then, for any x such that ||>=||2 S 1,
| 112
1
W
x
+ 36
1
12
|x0|| + ||3601 vdg
3
+ Mi) ...iVd Vd
ddo
ddg
1
W' + +,3
< Vd
W || |0 1ll + -|13611 112
(4121)
(83)
Vd
||~|||| = (la) - σ (0') + (00))l S Lo ||h 11, + (0)
(4l 1)
where Lu is the Lipschitz constant of and (00) = (o),
Rd By induction, there exists an M2 > such that ||a|||2 S V and | M₁ d for all l 1,.... L.
(0)) (o(())....
Denote a' VNf(x) Vithet, For all I 1, ... L, we have a' diag(o(h')) wiT a+ Va
where o(x) S Lo for all x E R since a is Lo Li-Lsshhi a = 1 and ||a" = diag (hh)) WLT
S 3 Lo- Then, can easily prove by induction that there exists an Vā
Vā
2
M3 > such that because a L+1 =1) 1).
||a|||2 s Ma/ Vā for all = 1,... T. (note that this is not true for +
For l = 0, V f(x)
Van IT, so (wrf(=)ll= S 1ل0 |a'l1
a
S Va
/ Vd. And
for any / = 1,... L. vwif(x) = Jao' so //)1 S J ||=|||| |||||||111 1|2 s MzM3
21

---

Under review as a conference paper at ICLR 2022
(Note that if M3 1, then || | || S My; and since d 2 1, there is || 12 _ M3 for 1 < L.)
Moreover, for 1 = 0, ... L. fo)(z) = Balt1. so V fx))ll S BM3. Thus, if (81) and (82 are
true, then there exists an M4 0, such that [[Va[())l2 I Ma/ Vn. And since | S 1 for all so | I M1
Next, we consider the difference in (x) between 0 and Ó. Let f, W. b, T. h, ā be the function and the values corresponding to 0. There is
1
12
h'
(Wo-
-W0 + 3(6 - -89)
do
1
W /. ||2 ||اد|| + 8 8O 8
+ 3
11e 8
v do
do
12/41
h/41
1
Wl (xe - -=') + Vd
(W
)at + 3(b' B')
1
Vd
(84)
<
1
|| | - Ez|12 + Vd
W' w | + 8
b' b'
Vd
S 3 ||
21112 + +M2 + +33 100- 0-000 0
(11
||ae - 0o'-='1l-- 2 10h0) o (hh)) 111 s Lo | -
-h'l( 16'112
(
By induction, there exists Ms 0 such that ||a| x 112 s Ms |00
0
for all I.
For a', we have LL11 aL+1_ 1, and for all 2 1,
WiT
WIT
||a' - á' 122 (h')(d(h'))
a 1+1 - (i))(
a
Vd
Vd
WIT
<
(at 1+1 - a
+ diag(o(h'))
ā
Vd
Vd
17/1
diag((O -((((())))(((h))) -(hh)))
ā 141
Vd
3Lo ||/41 - a't1112 + (MaLod 1/2 3.MMM, |10
(85)
where L1 is the Lipschitz constant of ā. Particularly, for | L, though ā 4+1 = 1, since
W L
S
// /4 (85) is still true. By induction, there exists an Mg > 0 such that ||a! - -''l S
Mr
0
Vi
for all /> 1 (note that this is also true for 1 I. + 1).
Thus, if 81 and (82) are true, then for all 0,0 E B(O()), Co), any such that ||0||| S 1, we have
Vwof(x) - V Virof(()))))
IT
xā²
= ddy
1
|od ā² 1g
(86)
/
dg
Mg
<
0
do
V
and for 1 - -,.... L., we have
22

---

Under review as a conference paper at ICLR 2022
[wif(z) - /
|
41T -
vd
(1201 ||aet1 - -a'+111
+
ot
à 1+1 (2)
(87)
M2Mo Vd
MsM1a
|0-0
+
vd
Moreover, for any / = 0, L, there is
Vor((z) Varf(z)) 3 ||alt1 a S
BMc
|0 8
(88)
Vd
Overall, we can see that there exists a constant M7 > 0 such that ||Vos(e) - Vo5(m)
S
Mr
0 0 that |](] J(0)
Mr 0 0
/n- Va
B.5 PROOF OF THEOREM 6
Let 1/ = min Nu. 17" ). where 1J is defined in Corollary 3 and vn" defined Theorem
Let
( (a:) and JIEERM (x:) be the linearized neural networks of f( and F respectively. By Theorem for any 5 0, there exists D and a constant such that
lin (x) (x) s Cd-1/41
sup
t20
(89)
JinERM (z) - ,(()) (2) S Cd-1/44 1/4
sup 120
By Corollary 3
we have
lim ( (x) (())
( =0
(90)
Summing the above yields
lim sup (() - (Z))(())) s 2cd-11/4 100
(91)
which is the result we want.
B.6 PROOF OF THEOREM 7
To minimize the regularized risk 12 with gradient descent, the update rule
((++1) = (())
(
m)(((t) - o(0))
(92)
(x for all I. Let 0" be the interpolator in span V. (0) (x1): (o) (x.,.) then the empirical risk
We can see that under the new rule, ((0) ((0) E span V (0)
Val (xx)) still true
(0 8*, (of((())))) such that for any T.
of 0 is 2n
1 Σi
2n
1 V x) T(p 8*) 102 Thus, there exists T > 0
T)((B
Vo ( (0) (X) (x) (0( - 0r) l S 2nc
(93)
Let the smallest singular value of 1 Vo (0) column space of (0) (X) is exactly span V, (00 (x1)..... (of (xx)). Define H Rexx
(X) be min and we have mmin 0. Note that the
vn
23

---

Under review as a conference paper at ICLR 2022
such that its columns form an orthonormal basis of this subspace, then there exists G E R such that (of (X) = HG, and the smallest singular value of G is also smin, Since 010) O(0)
/n
is also in this subspace, there exists v R such that (()) 0" Hv. Then we have v 2ne 2
G H Hellz - =| Thus, || S
v'c gmin
which implies
V2E
g(l) 0r
(94)
s
By Corollary
if we minimize the unregularized risk with ERM. then A always converges to the interpolator 6" So for any t 2 ' and any test point x such that ||ا||| S 1,
Mo Mov
Vinie (z) - IinERM = |(g(t) 8", Vof (x)))
(95)
g
which implies
14
B.7
PROOF OF THEOREM H
First of all, with some simple linear algebra analysis, we can prove the following proposition:
Proposition 13. For any positive definite symmetric matrix H E R denote its largest and smallest eigenvalues by max and Amin. Then, for any q E TR and Q = diag(qı, Q1, ... "..,..",,,0 ,(n), HQ has n positive eigenvalues that are all in [min; Amiin max; A Amax
Proof. H is a positive definite symmetric matrix, so there exists A E = such that H A A. and A is full-rank. First, any eigenvalue of AQAA is also an eigenvalue of A AQ and vice versa, because for any eigenvalue Multiplying both sides by A on the left yields A AQ (A v) = A(A v) which implies that X also an eigenvalue of A T AQ because A (Ta: v / as Au # O. We can prove the other direction similarly.
of AQA we have some & such that AQA
Av.
Second, by condition we know that the eigenvalues of A A are all in [Xmin, x where A > 0, which implies for any unit vector v. ''AT Au E [Amin, Amax], which is equivalent to ||Av|l2 e [VAmin, V / Thus, we have e A ATQA E [Amin min; qs X max max; qi). which implies that the eigenvalues of A QA are all in [mmin min; Gi, A max max; 4:)-
Thus, the eigenvalues HQ A AQ are all in [Xmin min; qs A Max max; qi)-
Now return back to the proof of Theorem 8 We still use the shorthand (40). With Lg penalty, the update rule of the reweighting algorithm for the neural network is:
((++1) p( m7 (((())))) g(((()) m)((())) 0(0))
(96)
And the update rule for the linearized neural network is:
e(l-1) = =ff00 ()(()()))) glin (0(()) ( ((0))
(97)
First, need to prove that there exists Do such that for all d 2 Do sup ||((t) -000 is bounded with high probability. Denote a; = g(1) - g(0) By (96) we have
a++1 =(1 ma)a - ())()()))
(1
(98)
()(()))) (0)00))0(0000)
(o()(0)) (0000())
,(0(0)) ) (0)) ((010))
which implies
|0141112 S (1(1 ( -) (1))))())))))))))))) T ||a1l22
(99)
+n ( |0 || + +n
where g()) is some linear interpolation between g()) and ((0) Our choice of r ensures that np < 1. Similar to 48 we can show that for any > 0, there exists a constant Ry > 0 such that with
24

---

Under review as a conference paper at ICLR 2022
probability at least (1 6/3), |9(0
Ro- Let M be defined in Lemma
Denote
A = TMM and let C. - in Lemma
By Lemma there exists D₁ such that for all
d 2 D1. with probability at least (1 6/3). is true.
Now we prove by induction that ||ee||2 < Cu- It is true for t = 0, so we need to prove that if | < Co. then ||ar=1ll2 < Co.
For the first term on the right-hand side of (99) we have
(1 mp) - ) J((())
<(1 mu1)
1
" (0000000)000000
1 m
(100)
+ 1 ((00)))))
| -
Like what we have done before, show that all non-zero eigenvalues of (( (()) I(B cigenvalues of ((())) (((()))(() This is because for any À * 0f (( ((())(((()))) ((())) T Au, then )(0(0)) J (( (O(0)) = (((0())) v), and ((O())) v o 0 since Au 0, so À is also an eigenvalue of ( ((((0) J( Q(1) On the other hand, by Theorem ( Q(i) converges in probability to iQ!!) whose eigenvalues are all in [0, Xmax
by Proposition 13 So there exists D2 such that for all d D2, with probability at least
are all in [0, Amax + Amin] for all t. Since 7/(1 - I (Amin + Amax)- by our choice of 17, we have
(1 8/3). the eigenvalues of (())))))))
1(0(0)) 1(000)) <
(101)
np
On the other hand, we can use 447 since ||ael12 < Co. so ||)00())||
|| -
2 Co. Therefore, there exists D3 such that for all d z D3.
Va
| mo) -
$
(102)
2
For the second term, we have
|ococo) - -
+ ( ||||||/(00000)
(103)
10100 ((0)
+ Ro S MC + Ro
2
And for the third term, have
m
||
|
S nM
(104)
Thus, we have
||a+1 122 5 (1-
T74 2
||ar|12 + MMC + Ro)
+ +A
(105)
Vd
So there exists DA such that for all d d2 D1, ||art1l22 < (1 n ||æel22 + 2A. This shows that if ||arll2 < Co is true, then [|ae+1llz < Co will also be true.
In conclusion, by union bound, have proved that for any 8 > 0. with probability at least (1 8)
for all d Do max(D,, D2, D3, Dz). ||0() g( lg Co is true for all This also implies
that for C = MCO + Ro. we have (l()) ||, < C, for all by 103)
NNoe that Lemma 11 only depends on the network structure and does not depend on the update rule, so use this lemma here.
25

---

Under review as a conference paper at ICLR 2022
Second, let A,
0 000. Then we have
Aet1 A 7)1(00)) g(0(0) - J( ) gin (1n(00)))))00 -ude)
(106)
which implies
A (1 mu)l - ((((0)))))) T
A, + ((](())) (( )2 g(0(0))
(107)
By 102 with probability at least (1 - 5) for all d 2 Do. we have
(0(( A++1 la S (11 mp) (1-np))
Q -
(()t)) T || ||Arlla + -(00 J |00000)
$ (1- / ||+ +
M
CoC1
Vd
(108)
Again, as Ag O, we can prove by induction that for all 6,
2MCc01 d 1/4
|
(109)
1
For any test point æ such that ||~:1| I 1, we have
(x))
linreg (x:)
f( 0(0) - fin fxn )
[ac 010)
fin (2:; 0
fii [in 0(+)) Sinn(x (((0))
(110)
fla; 0(0)
fin(2; (
Vof(a: (ace;000)) /11 | (000)-891 (
f(x; 010) - fin (o; g
+ M Leell2
For the first term, note that
f(x; f()) - f(x; (an(::; ((t)) fin (a:; ((0)) Vof(æ; (0) (Q(()) ((0))
0(0)) fxx;0(0)
= vef(æ; ( - ((0))
(111)
where ((9) is some linear interpolation between (10) and (10), Since (ax 0(01) = fin (a;; 0(0)).
((x;0(() - fin (x:; o(0) s Vof(x;0(0) Vef(z; (()) |11 p(0) - g S M
C
(112)
dd
Thus, have shown that for all d 2 Do. with probability least 8) for all and all x.
(()) (x) Jiileg (x) s (MCB + 2M J- d-1/4 (d-1/4)
(113)
Given that (((()g)))))) < e for sufficiently large t, this also implies that
R R R((())) O 1/1 /e d-1/2)
(114)
So for a fixed e, there exists D such that for all d 2 D. for sufficiently large R(S(1) < R((( 2e
(115)
By Theorem we have
sup (()) H (a:) JRRM (z:) (1/11/1)
(116)
Combining Theorem 7 with (113) and (166) derives
lim sup
p(t) reg (x:) (x)) = 0 +V)
(117)
2-+00
Letting d - xo leads to the result need.
26

---

Under review as a conference paper at ICLR 2022
C A NOTE ON THE PROOFS IN LEE ET AL. (2019)
We have mentioned that the proofs in Lee et al. 2019), particularly the proofs of their Theorem 2.1 and Lemma in their Appendix G, flawed. In order to fix their proof, we change the network initialization to ( In this section, we will demonstrate what goes wrong in the proof's in Lee et al. (2019), and how we manage to the proof. For clarity, we are referring the following version of the paper: https:: arxiv. wwtpp/dpg//////////// /9909/2//9922.../////2 06 226204..... pdf
To avoid confusion, in this section we will still use the notations used in our paper.
C.I THEIR PROBLEMS
Lee al. (019)) claimed in their Theorem 2.1 that under the conditions of our Theorem for any
5 > there exist D 0 and constant C' such that for any d > D, with probability at least (1 6). the gap between the output of a sufficiently wide fully-connected neural network and the output of its linearized neural network at any test point
be uniformly bounded by
sup 20
- 1 (z))
cd-
(claimed)
(118)
where they used the original NTK formulation and initialization in Jacot al. (2018)
hh+1 W
Vd xt +
W ~ 1)), 1 N(0,1)
and
(Al 0, ... L)
(119)
x 1+1 = =o (1
where By = x and f f(x) = h,4+1 However, in their proof in their Appendix G, they did not directly prove their result for the NTK formulation, but instead they proved another result for the following formulation which they called the standard formulation:
h h+tt= W ! + 9b' r/411 -041=
Wi
and
(4l = 0.... 0.......... L)
(120)
100) 1(0.1)
See their Appendix F for the definition of their standard formulation. In the original formulation, they also included two constants ou and a for standard deviations, and for simplicity we omit these constants here. Note that the outputs of the NTK formulation and the standard formulation initialization are actually the same. The only difference is that the norm of the weight W and the gradient of the model output with respect W are different for all I.
In their Appendix G, they claimed that if network with the standard formulation is trained by minimizing the squared loss with gradient descent and learning rate T/' r/d,, where is our learning rate in Theorem and also their learning rate their Theorem 2.1, then (118) true for this network, so it is also true for network with the NTK formulation because the two formulations have the same network output. And then they claimed in their equation (S37) that applying learning rate 7/ to the standard formulation is equivalent applying the following learning rates
di
T/
and
(121)
d
dmax
to W and b' of the NTK formulation, where dmax = max ( (do. ... dr)--
To avoid confusion, in the following discussions will still use the NTK formulation and initial- ization if not stated otherwise.
Problem Claim 121) is true, but it leads to two problems. The first problem is that vá O(dmlx) since y = OTT, while their Theorem 2.1 needs the learning rate to be O(1). Nevertheless, this problem can be simply fixed by modifying their standard formulation as h++1 = W' +d/d
where (.(0) (o The real problem that is non-trivial to fix is that by (21). there is
27

---

Under review as a conference paper at ICLR 2022
7i dma. 77. However, note that do is constant since is the dimension of the input space, while dmax goes infinity. With that being said, in (12I) they were essentially using very small learning rate for the first layer 8 but a normal learning rate for the rest of the layers, which definitely does not match with their claim in their Theorem 2.1.
Problem 2. Another big problem is that the proof of their Lemma in their Appendix G is emro- neous, and consequentl their Theorem 2.1 unsound it heavily depends on their Lemma In their Lemma I, they claimed that for some constant M >> O, for any two models with the parameters I and 9 such that 0, 0 E B(O Co) for some constant Co, there is
|T(0) (1(0)-Jp (000)-J(0) ([10)_(00] S
M
(claimed)
(122)
Vd
2
[ - 1001 (10))-(0)1|- - Mv 811 This is because
Note that the original claim their paper was they were proving this result for their standard formulation. Compared to the standard formulation, in the NTK formulation is v times larger, while the Jacobian [() is v times smaller. This is also why here have 0, A B(0("), Co) instead of 0.0 (() Cod-1/2) for the NTK formulation. Therefore, equivalently they were claiming (122) for the NTK formulation.
However, their proof of [22 in incorrect. Specifically, the right-hand side of their inequality (S86) is incorrect. Using the notations in our Appendix B.4 their (S86) essentially claimed that
a'l12 M
(claimed)
(123)
for any 0,0 B(B()), Co). where a' = Vn h model. Note that their (S86) does not have the Vā in the denominator which appears in (23).. This is because for their standard formulation, 9 is v d times smaller than the original NTK formulation, while ||a'|l Il2 has the same order in the two formulations because all h' are the same.
1+1 and á' is the same gradient for the second
However, it is actually impossible to prove 123). Consider the following counterexample: Since 0 and are arbitrarily chosen,
choose them such that they only differ in b' for some 1 < l < L. b) - 8) We can see that h++1 and h only differ in the first element, and
Then,
0-0
| 10-0) 0
h1411 h1+1 B0b Bi} Moreover, we have W W there is
WI+I Vd
WTITT Vd
a+ a4t1 =dia((((h*)))
a 1+2 diag(o(h'+1)
xlt2
WI+IT
=(dia(((hh+11) diag diag(o(h!+t)) (1(
122
(124)
Vd
WI+IT
+ diag (6 (h))
(a x2222
Vd
Then we can lower bound ||a - a by
WH+1
|a - - 2
|diag( C7 ((((t)( - diag(o(h(41))
l+2
Vā
(125)
W1+1
diag(o (h'
12 a222
Vd
[ - o (b/tt1)]
The first term on the right-hand side is equal to w|-1 is the first row of W1+1, We know that || θ ( (vd) with high probability as its
where
28

---

Under review as a conference paper at ICLR 2022
elements are sampled from (0, 1), and in their (S85) they claimed that ||a | 312 O(1), which
true. In addition, they assumed that is Lipschitz. Hence, we can see that
diag(o (
W a ++2
=0
hit =0
010 -
2
(126)
On the other hand, suppose that claim (123) is true, then |a - ad 0
(d-1/2 (a-0(=a)))
8
Then we can see that the second term on the right-hand side is O 0 (d-1/2 1/2 0 8
because
1 ((v)) and ò (xr) is bounded by a constant as a is Lipschitz. Thus, for very large d, the second-term is infinitely small term compared the first term, so we can only prove that
la - = - (
(127)
which is different from 123 because it lacks a critical d-1/2 and thus leads to a contradiction.
Hence, we cannot prove 123 with the d' 1/2 factor, and consequently we cannot prove (22)) with
the v in the denominator on the right-hand side. As result, their Lemma 1 and Theorem 2.1 cannot be proved without this critical d/1/2, Similarly, we can also construct a counterexample where f and 0 only differ in the first row of some W
C.2 OUR FIXES
Regarding Problem 1, we can still use an O(1) learning rate for the first layer in the NTK formulation given that ||>||| I 1. This is because for the first layer, we have
[wof(x) dd
x 2T
ddo xa
(128)
For all 2 1, we have ||~||| = Odd/2). However, for = 0, we instead have ||00||2 O()) has the same order as the gradient with respect to
Thus, we can prove that the norm of V any other layer, there is need to smaller learning rate for the first layer.
Regarding Problem 2, in our formulation (8) and initialization 99, the initialization of the last layer of the NTK formulation is changed from the Gaussian initialization w (0, 1) to the zero initialization L() O. Now we show how this modification solves Problem 2.
The main consequence of changing the initialization of the last layer that (8T) becomes different: instead of | 3vd, d, we have ||w2]] Co & <VV.. In fact, for any (0, 1/2),
can prove that || < 3d for sufficiently large d. In our proof we choose r y= 1/4.
Consequently, instead of ||al|| S Ms, we can now prove that | || S M 1/2 for all < by
induction. So now we can prove ||a' a'll, = 112 because
1/2
8 instead of O (1e - 0 ).
For 1 < L. we now have |a ||2 = O instead of O(1), so we can have the additional 1/2 factor in the bound.
For 1 T., although ||o_++||| l| note that |W41|2 now becomes Oid") instead of 0())2), so again we can decrease the bound by a factor of 1/2
Then, with this critical 1r2 we can prove the approximation theorem with the form
sup 20
( (x:
(a)) (())
112
(129)
for any r E (0, 1/2). though we cannot really prove the ( 1/2) bound as originally claimed in 118.. So this is how we solve Problem 2.
29

---

Under review as a conference paper at ICLR 2022
One caveat of changing the initialization to zero initialization is whether that Amin > where Aminn is the smallest eigenvalue of I, the kernel matrix of our new formulation. The answer is yes. In fact, in our Theorem 4 we proved that è is non-degenerated (which means that (xx, æ²) still depends on x: and x'), and under the overparameterized setting where dr. > n, chances high that @ is full-rank. Hence,
still safely assume
still assume that A O.
As a final remark, one key reason why we need to initialize W as zero that the dimension of the output space (i.e. the dimension of h h=+1) is finite, and in our case it 1. Suppose we allow the dimension of h4+1 to be d which goes infinity, then using the same proof techniques, for the NTK formulation can prove that sup, //2+((()) L+1(()
S C, i.e. the gap between two vectors of infinite dimension is always bounded by finite constant. This is the approximation theorem we need for the infinite-dimensional output space. However, when the dimension of the output space is finite, sup; h4+1(0) - [+)(()) S C' no longer suffices, so we need to decrease the order of the
norm of W in order to obtain smaller bound.
D EXPERIMENT DETAILS AND ADDITIONAL EXPERIMENTS
D. EXPERIMENT DETAILS
All experiments are conducted on a Ubuntu 18.04.6 machine with NVIDIA Geforce GTX 1080ti GPUs. Each model is trained with one GPU. On each of Waterbirds and CelebA, we use ResNet18 as the model. The model is trained with SGD) with momentum = 0.9. On Waterbirds the learning rate is 10 and on CelebA it 10-3 For Group DRO, // selected as 0.01 (see the definition of in 33. The batch size used for Waterbirds is 128, and for CelebA it is 400. Data augmentation
including random cropping, random horizontal flip and normalization is performed on both datasets.
D.2 SAMPLE WEIGHTS CONVERGE IN GROUP DRO
The results in Section require Assumption which states that each sample weight q; converges to some positive value as t + oc. Our readers might wonder how strong this assumption is, and whether reweighting algorithms satisfy this assumption in practice. In this section we empirically demonstrate that for Group DRO, the dynamic reweighting algorithm we experiment on, this as- sumption satisfied on Waterbirds and CelebA.
Recall that in Section 2.2 we empirically showed that reweighting algorithms could easily overfit without regularization. Here using the same experimental settings, we keep track of the weight of each group 9h during training, and plot the group weight curves in Figure 3 We also train the models longer (1000 epochs on Waterbirds and 300 epochs on CelebA), Clearly we can see that as the training accuracy converges 100%, the group weights also converge to equilibrium. Note that q:
(t) = gk /ng for all 2; E DR. so the sample weights also converge.
0.5
0.6
Group Weight
0.4
Group Weightt
0.3
0.2
0.2
0.1
200
1000
Epoche
Epoche
Waterbirds.
(b) CclebA.
Figure 3: Weights of each group in Group DRO on Waterbirds and CelebA. The four curves corre- spond to the four groups.
30


Reviews:
[{"review_id": "xcFEt5HnoG1", "reviewer": "Reviewer_M2hT", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "\nI enjoyed reading this paper. It is written in a very clear way and it addresses a very timely and important problem. I also enjoyed that it combined both theoretical results and simulations.\n\nBelow are some questions that I have and some suggestions that perhaps can be helpful to the authors in improving their paper.\n\n1) If I understand correctly from equation (4) and Assumption 1, the framework of the present paper only applies to training updates based on the full dataset, and not to batch or stochastic updates. If this is the case, then this should be highlighted more prominently in the text and in the abstract. Would it be possible to generalize the analysis?\n\n2) \"Each $\\mathcal{D}_i$ is a subset of $\\mathcal{X} \\times \\mathcal{Y}$\": Is this condition required for the theoretical results? If so, it should be discussed at more length. Can it be relaxed? For example, in my mind often the notion of worst-case performance relates to multiple environmentsl as in e.g, the conceptual framework of Rothenhäusler et al (2021, JRSSB) or to protected attributes that are not directly included in the model. These may not be perfectly recoverable through subsets of predictors and response variables (though of course they may be strongly correlated).\n\n3) Maybe in the high-level statement after Theorem 2 one could clarify that this statement depends on identical initialization $\\theta^{(0)}$ for all involved methods?\n\n4) Last paragraph of Section 3, \"Moreover our theoretical results can explain the surprising empirical observation\": I think this paragraph is not sufficiently justified (i.e., it does not really explain the observation, at most it hints at the plausibility of it). Can the authors make a stronger case for their argument? Otherwise my suggestion would be soften the claim (or even remove the paragraph).\n\n5) I like the experiments since they bring the main point of the paper across very clearly. One additional result I would have liked to see is an empirical illustration of whether the theoretical arguments hold, e.g., are the final solutions of ERM, DRO, and IW initialized at the same $\\theta^{(0)}$ very similar (and more similar than solutions of the same method initialized at different $\\theta^{(0)}$)? By similarity here I refer to similarity of actual model fits, rather than accuracy/performance.\n \n\n\n# Typographical errors\n\n* Equation (5), $f^{(t)}$ instead of  $f$\n* Page 8: \"trained trained\" (repeated twice)\n* Reproducibility statement: I think speculation should be \"specification\" (note: the word speculation appears twice in this sentence). Anaconda should be capitalized.\n\n", "summary_of_the_paper": "This work studies the problem of training for worst-case subgroup performance. This has been a very prominent research avenue in the past few years and provides a natural approach towards learning fair and \"causal\" models (that do not perform too badly for any pre-specified subgroup). In practice however there have been some difficulties with existing approaches, and e.g., in the overparameterization regime, these methods do not perform well in terms of  worst-case performance on test sets. This paper provides a theoretical explanation for this fact (using linear models and linearized neural networks) and also illustrates it using numerical experiments on two datasets. Furthermore, the authors assess the role of $L_2$ regularization in training. The practical takeaway is that existing approaches based on reweighting require substantial regularization or early stopping to perform well in terms of test accuracy (in the overparamerized regime).\n", "summary_of_the_review": "\nI think this is an interesting contribution on the theoretical and practical study of worst-case subgroup performance and therefore I would like to see this work accepted. I also think the paper could be improved a bit further by adding experiments that more closely validate the theoretical results (point 5), and by clarifying limitations/shortcomings to this work.\n", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ibnluxojGfV", "reviewer": "Reviewer_wG4N", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "- The paper is studying an important problem about the effect of importance reweighing in overparameterized models which has attracted a lot of interest recently and thus, would be of interest to the community.\n- However, the paper has many serious flaws. First of all, the paper is studying squared loss for its analysis and does not include a discussion about the choice of loss function. Loss function used in the previous works cited in this paper was cross entropy loss. So, there is this discrepancy between the works/experiments that this work is replicating and the theoretical results that are included.\n - This work is missing important citations for example [1] which initiated this study of importance reweighing methods in deep learning to the best of my knowledge.  Moreover, this has already been studied theoretically for cross entropy and other general losses by [2] which has not been cited in this work. So, it is not even clear if studying this paper for the squared loss brings out any new idea or insight on top of what was already known before. The point about regularization being necessary has already been made in previous works.\n\n[1] What is the Effect of Importance Weighting in Deep Learning? Byrd et. al. \n[2]  UNDERSTANDING THE ROLE OF IMPORTANCE WEIGHTING FOR DEEP LEARNING, Xu et al.", "summary_of_the_paper": "This paper theoretically proves the empirical observation that has been made in a lot of recent works regarding the role of importance reweighing in overparameterized deep networks. For squared loss and independent data points, it theoretically proves that reweighing the data points has no effect on the final model learned for linear models and linearized neural networks. This work also analyzes the role of regularization in preventing this behavior and proves that regularization has to be large enough to prevent small training error to have any effect. This work also has supporting empirical results on two datasets- celeba and waterbirds.", "summary_of_the_review": "- However, the paper has many serious flaws. First of all, the paper is studying squared loss for its analysis and does not include a discussion about the choice of loss function. Loss function used in the previous works cited in this paper was cross entropy loss. So, there is this discrepancy between the works/experiments that this work is replicating and the theoretical results that are included.\n - This work is missing important citations for example [1] which initiated this study of importance reweighing methods in deep learning to the best of my knowledge.  Moreover, this has already been studied theoretically for cross entropy and other general losses by [2] which has not been cited in this work. So, it is not even clear if studying this paper for the squared loss brings out any new idea or insight on top of what was already known before.\n\nI would like to make recommendation for rejecting this paper. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "iAploHg20T", "reviewer": "Reviewer_hLzT", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "Understanding worst-group performance is an important and interesting topic. The paper is relatively easy to read, and provides valuable insights about this problem. However, there are some issues that need to be addressed\n\n+ The abstract and introduction are quite misleading. For example, we see strong statements in the abstract such as \"we cannot hope for reweighting algorithms to converge to a different interpolator than ERM...\" or \"we prove that for regularization to work, it must be large enough to prevent the model from achieving small training error.\" Such blanket statements without any hint that these are based on important assumptions (that are somewhat scattered in the paper) are misleading for the readers (of course unless if they dig deeper)\n\n+ The first row of figure 1 is a good example of an overparametrized model, where the training accuracy of all models become 1 at some point in training. However, we still clearly see that even after than point, the test accuracies of different approaches are not the same. This is in contrast with the theoretical result by the authors that all of those methods would converge to the same result. The only explanation for this discrepancy is that the assumptions that the authors have made do not make sense for this experiment. For the second row (CelebA) the algorithms do not reach training error zero, and are effectively outside the regime of interest for the theoretical results of this paper. In conclusion, the the theoretical results do not really support the empirical results in this case; they really show different things. \n\n+ Given the discrepancy between the theoretical and empirical results, it becomes more important for the authors to make the abstract/intro/.. more accurate. For example, someone that reads the abstract will conclude that there is no way for the reweighting to help unless the average accuracy drops significantly, whereas the experiments show otherwise. \n\n+ The observation in section 3.1 that for linear models, the change in the parameters is always in the span of the data points is quite useful. I believe this is a standard observation that has been made before but I may be wrong. Can the authors comment about this? Are they the first to discover this? If not, they should at least add a citation.\n\n+ More generally, are the other proofs (e.g, for the wide networks) similar to the analyses performed in previous work? If so, can you explicitly name those papers?\n\n+ Is the theoretical analysis specific to the squared loss (e.g., in Thm 4, 5, 6)? If so, this must be clearly indicated as an extra assumption. \n\n+ Can you elaborate on assumption 1? Why is it intuitively a reasonable assumption (aside from the empirical study)? \n\n+ It looks like some of your experiments is similar to Sagawa et al. (2020a). Can you elaborate on the differences?\n\n+ In Table 1, I believe you have left out the performance of ERM for early stopping. I think it is quite important to have those to be able to compare with the other methods.\n\n+ As a side-comment, the practice of reporting 95% confidence intervals just based on running the method on a number of  random seeds is not necessarily valid. (usually you need to do cross-validation, or if not, argue that the test set is large enough...)", "summary_of_the_paper": "The authors study the problem of improving the worst-group accuracy in the over-parametrized setting. They offer theoretical and empirical evidence that reweighting does not affect the final solution in this setting; in other words, the algorithm would converge to the same interpolators as that of basic ERM. The theoretical analysis is done for linear models, linearized networks, and wide fully connected networks. \n\nThe authors also argue that the solution does not change unless a considerable amount of regularization is incorporated, so much so that it affects the training error. Again, some theoretical and empirical evidence is provided.\n\n", "summary_of_the_review": "The paper studies an important problem. The theoretical analysis is interesting though it has its own limitations. It will help if the authors comment about the novelty of the proof techniques compared to the previous work. \n\nMany statements of the paper are misleading and should be addressed. The empirical study and the theoretical study do not necessarily support each other and this discrepancy has not been discussed in the paper.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Y9xflRrwbqt", "reviewer": "Reviewer_fZgx", "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": "Strengths:\n1.\tThe paper provides good proof for linear models via the intuition that the change in model parameters always lies in a low-dimensional subspace. \n2.\tThe conclusion gives new insight for designing algorithms, which shows reweighting algorithms without any repair methods may not be better than ERM for the worst-group performance.\n3.\tThe paper writing is generally of high quality.\n\n\nWeaknesses:\n1.\tMy feeling is that the conclusion is somewhat overclaimed. In both abstract and conclusion, it is emphasized that this work proves the pessimistic result that reweighting algorithms always overfit. However, the paper only proves that this conclusion might be true for some **specific** situations. For example, the reweighting algorithms need to satisfy Assumption 1 and Assumption 2, which means not all reweighting algorithms are considered. The overparameterized models need to be linear models, linearized neural networks or wide fully-connected neural networks, which are not commonly used in practice. Besides, the squared loss needs to be used to confirm the update rule is linear. All those assumptions are not quite mild for me. \n2.\tThe analysis of neural networks contributes less. With the existing NTK theorem, the extension from linear models to wide fully-connected neural networks is trivial (Section 3.2, 3.3). The work bypasses the core problem of overparametrized neural networks and only considers the easy wide fully-connected neural networks. \n3.\tThe theoretical results and experiments do not match. The theoretical proof considers wide fully-connected neural networks, while the experiments utilize a ResNet18 as the model, which is quite different.\n4.\tSome key steps are empirical, although the paper claims that it provides a theoretical backing in the abstract. For example, this paper only proves that reweighting algorithms will converge to the same level as ERM, but the conclusion that ERM has a poor worst-group test performance is summarized through observation in practice. Besides, the paper can only empirically demonstrate that commonly used algorithms satisfy Assumption 2.\n", "summary_of_the_paper": "This paper mainly focuses on the reweighting algorithms (e.g. Importance Weighting, Group DRO) for the worst-group performance. It tries to theoretically explain why overfitting problems always appears in reweighting algorithms. Specifically, the authors prove that under several conditions (e.g. assumptions for algorithms, wide fully-connected neural networks, squared loss), the worst-group test performance of the reweighting algorithm will converge to the same level as ERM.", "summary_of_the_review": "The actual main contribution of this paper is proving that for linear overparameterized models, the current reweighting algorithms almost always overfit. It provides a possible way of analyzing overfitting problems by reducing a family of algorithms to the commonly used ERM. However, the analysis of neural networks contributes less, and some key steps are still empirical results. Besides, there is a gap between theoretical results and experiments. In summary, the conclusion of the paper is somewhat overclaimed, and there is still a lot of room for improvement. ", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the effect of importance weighting in three model classes: linear models, linearized networks, and wide fully connected networks, and show that under certain assumptions, gradient descent for training an overparameterized model converges to the same ERM interpolator regardless of the reweighting scheme. The reviewers acknowledge that this paper had good exposition and writing in general, but they were in consensus that the initial version of this paper includes many inaccurate overclaiming statements. In summary, after discussions, the reviewers would like the authors to:

- revise the abstract and the introduction, specifically, adding appropriate qualifiers on the neural networks, losses, full gradient descent training, etc (Reviewers hLzT, M2hT, fZgx)
- address the discrepancy between theory and experiments, e.g. the inconsistency of the loss chosen in theory and experiments, the requirement that the widths of the neural networks need to large (Reviewers wG4N, fZgx)
- add experimental results for early stopping (Reviewer hLzT)
- empirically verify that the final solutions of ERM, DRO, and IW initialized at the same \theta^0 are very similar (Reviewer M2hT)
- discuss the novelty compared to Sagawa et al in the paper (Reviewer wG4N)

thus, this submission needs a major revision, and is not ready for acceptance in its current form. We encourage the authors to revise accordingly, and resubmit in the future.
Decision: Reject