Understanding Why Generalized Reweighting Does Not Improve Over ERM
Authors: Runtian Zhai
Chen Dan
J Zico Kolter
Pradeep Kumar Ravikumar
Venue: ICLR 2023 poster (2023)
Keywords: Distribution shift
Subpopulation shift
Implicit bias
Generalization
Overparameterization

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

Published as a conference paper at ICLR 2023
UNDERSTANDING WHY GENERALIZED REWEIGHTING DOES NOT IMPROVE OVER ERM
Runtian Zhai, Chen Dan, Zico Kolter, Pradeep Ravikumar Carnegie Mellon University Piusburgh, PA, USA 15213 (rzhai, cdan, zkolter pradeepr)@cs... Cs cmw. cat.eppprecc..cm.ee..
ABSTRACT
Empirical risk minimization (ERM) known be non-robust in practice to dis- tributional shift where the training and the test distributions are different. A suite approaches, such as importance weighting, and variants of distributionally ro- bust optimization (DRO), have been proposed to solve this problem. But line recent work has empirically shown that these approaches do not significantly improve ERM in real applications with distribution shift. The goal of this work is to obtain a comprehensive theoretical understanding of this intriguing phenomenon. We first posit the class of Generalized Reweighting (GRW) algo- rithms, as a broad category of approaches that iteratively update model parameters based on iterative reweighting of the training samples. We show that when over- parameterized models are trained under GRW, the resulting models are close to that obtained by ERM. We also show that adding small regularization which does not greatly affect the empirical training accuracy does not help. Together, our re- sults show that a broad category of what we term GRW approaches are not able to achieve distributionally robust generalization. Our work thus has the following sobering takeaway: to make progress towards distributionally robust generaliza- tion, we either have to develop non-GRW approaches, or perhaps devise novel classiiication/regression loss functions that are adapted to GRW approaches.
INTRODUCTION
It has now been well established that empirical risk minimization (ERM) can empirically achieve high test performance on a variety of tasks, particularly with modern overparameterized models where the number of parameters is much larger than the number of training samples. This strong performance of ERM however has been shown to degrade under distributional shift, where the train- ing and test distributions are different (Hovy & Søgaard 2015 Blodgett et al. 2016: Tatman 2017). There are two broad categories of distribution shift: domain generalization, defined as the scenario where the test distribution contains samples from new domains that did not appear during training; and subpopulation shift, defined as the scenario where the training set contains several subgroups and the testing distribution weighs these subgroups differently, like in fair machine learning.
People have proposed various approaches to learn models robust to distributional shift. The most classical one is importance weighting (IW) (Shimodaira) 22000) Fang et al. (020). which reweights training samples; for subpopulation shift these weights are typically set so that each subpopulation has the same overall weight in the training objective. The approach most widely used today is Distributional Robust Optimization (DRO) (Duchi & Namkoong 2018 Hashimoto et al.) 2018), which assumes that the test distribution belongs a certain uncertainty ser of distributions that are close to the training distribution, and train on the worst distribution in that set. Many variants of DRO have been proposed and are used in practice (Sagawa et al. 2020a Zhai al., 2021a b).
While these approaches have been developed for the express purpose of improving ERM for distri- bution shift, line of recent work has empirically shown the negative result that when used to train overparameterized models, these methods do not improve over ERM. For IW, [Byrd & Lipton| (2019) observed that its effect under stochastic gradient descent (SGD) diminishes over training epochs, and finally does not improve over ERM. For variants of DRO, Sagawa et al. (2020a) found that these methods overfit very casily, i.c. their test performances will drop to the same low level as ERM after sufficiently many epochs if no regularization is applied. Gulrajani & Lopez-Paz (022)) Koh et al.

---

Published as a conference paper at ICLR 2023
2021 compared these methods with ERM on number of real-world applications, and found that in most cases none of these methods improves over ERM.
This line of empirical results has also been bolstered by some recent theoretical results. Sagawa ct al. (222b)) constructed a synthetic dataset where a linear model trained with IW is provably not robust subpopulation shift. Xuu et al. (021) further proved that under gradient descent (GD) with a sufficiently small learning rate, a linear classifier trained with either IW or ERM converges to the same max-margin classifier, and thus upon convergence, are different. These previous theoretical results are limited to linear models and specific approaches such as IW where sample weights are fixed during training. They are not applicable to more complex models, and more general approaches where the sample weights could iteratively change, including most DRO variants.
Towards placing the empirical results on a stronger theoretical footing, we define the class of gen- eralized reweighting (GRW), which dynamically assigns weights to the training samples, and itera- tively minimizes the weighted average of the sample losses. By allowing the weights to vary with iterations, we cover not just static importance weighting, but also DRO approaches outlined earlier; though of course, the GRW class is much broader than just these instances.
Main contributions. We prove that GRW and ERM have (almost) equivalent implicit biases, in the sense that the points they converge to are very close to each other, under a much more general setting than those used in previous work. Thus, GRW cannot improve over ERM because it does not yield a significantly different model. We are the first to extend this line of theoretical results (i) to wide neural networks, (ii) to reweighting methods with dynamic weights, (iii) to regression tasks, and (iv) to methods with L2 regularization. We note that these extensions are non-trivial technically as they require the result that wide neural networks can be approximated by their linearized counter- parts to hold uniformly throughout the iterative process of GRW algorithms. Moreover, we fix the proof in a previous paper (Lee et al. 2019) (see Appendix E which also a great contribution.
Overall, the important takeaway is that distributionally robust generalization (DRG) cannot be di- rectly achieved by the broad class of GRW algorithms (which includes popular approaches such as importance weighting and most DRO variants). Progress towards this important goal thus requires either going beyond GRW algorithms, or devising novel loss functions that are adapted to GRW approaches. In Section O we will discuss some promising future directions and the case with non- overparameterizeed models and early stopping. Finally, we want to emphasize that while the models we use in our results (linear models and wide neural networks) are different from practical models, they are general models most widely used in existing theory papers, and our results based on these models provide explanations to the baffling observations made in previous empirical work, well as valuable insights into how to improve distributionally robust generalization.
2 PRELIMINARIES
Let the input space be X C dd and the output space be y C K We assume that X' is a subset of the unit L2 ball of Rdd so that any x E X satisties ||>||2 < 1. We have training set {z; (æ,, V1 ) )
i..d sampled from an underlying distribution P over X' x y. Denote X = X=
(xx1 ...)) E Rdxn yn) E R". For any function g : X² + RT, we overload notation and use
and Y = (y), g(X) = (g(=1), ((x,,, E m (except when m = 1, (XX) is defined as column vector). Let the loss function be E y x y + [0, 1]. ERM trains a model by minimizing its expected risk P) - E())())) v)] via minimizing the empirical risk R(()= = ΣT ((f()))
In distributional shift, the model is evaluated not on the training distribution P. but different test distribution Piest, so that we care about the expected risk R(;: Pies). A large family of methods designed for such distributional shift is distributionally robust optimization (DRO), which minimizes the expected risk over the worst-case distribution Q < + in ball w.r.t. divergence D around the training distribution P. Specifically, DRO minimizes the expected DRO risk defined as:
RD,((J: P) = sup (E)(((((=),v)) D(Q || QEP
P) s}
(1)
for p Examples include CVaR, 2D-DRO Hashimoto et al. 2018), and DORO Zhai et al., 2021a), among others.
Our results can be easily extended to the multi-class scenario (sce Appendix
For distributions P and Q, Q is absolute continuous to P, Q <<< P. means that for any event A,
P(A) 0 implies ((A) O.
2

---

Published as a conference paper at ICLR 2023
A common category of distribution shift is known subpopulation shift. Let the data domain contain K groups D.,..., Dr. The training distribution P is the distribution over all groups, and the test distribution Pies is the distribution over one of the groups. Let (z) P( be the conditional distribution over group k, then Piea can be any one of Pq, ..... Pk- The goal is to train model f that performs well over every group. There are common ways achieve this goal: one is minimizing the balanced empirical risk which is an unweighted average of the empirical risk over each group, and the other is minimizing the worst-group risk defined as
D
Rimxx (f: kml,,,,
max Px):Pp) max Ez-r(((((x). v) D&] k=
(2)
GENERALIZED REWEIGHTING (GRW)
Various methods have been proposed towards learning models that are robust to distributional shift. In contrast to analyzing each of these individually, we instead consider a large class of what we call Generalized Reweighting (GRW) algorithms that includes the ones mentioned earlier, but potentially many others more. Loosely, GRW algorithms iteratively assign each sample weight during training (that could vary with the iteration) and iteratively minimize the weighted average risk. Specifically, iteration f, GRW assigns a weight q; to sample 2,, and minimizes the weighted empirical risk:
(1)
n
R R100 (f) Σ ((f((a)))))
(3)
where (0) (41" ...........
) and (t)
qi +
qn 1.
Static GRW assigns to each z; = (æx, v/) a fixed weight that does not change during training, i.e.
q, qi A classical method is importance weighting (IW) (Shimodaira) 2000), where if z; Dx and the size of DA is Yık, then = (Knz)= Under IW, 3 becomes the balanced empirical risk in which each group has the same weight. Note that ERM is also special case of static GRW.
On the other hand, in dynamic GRW, (d)) changes with t. For instance, any approach that iteratively upweights samples with high losses in order to help the model learn "hard" samples, such as DRO, an instance of GRW. When estimating the population DRO risk RD P) in Eqn. T.. if P is set to the empirical distribution over the training samples, then Q < P implies that Q is also distribution over the training samples. Thus, DRO methods belong to the broad class of GRW algorithms. There are two common ways to implement DRO. One uses Danskin's 's theorem and chooses Q as the maximizer of [o(((((x) y)] in each epoch. The other one formulates DRO as a bi-level optimization problem, where the lower level updates the model to minimize the expected risk over Q, and the upper level updates Q to maximize Both can seen as instances of GRW. As one popular instance of the latter, Group DRO was proposed by (Sagawa et al. (2020a) to minimize 2). Denote the empirical risk over group & by RJ),), and the model at time by f(, Group DRO iteratively sets q. = 9% (t) /ny for all 2; E Di where gt is the group weight that is updated as
g 9k (1-1) exp (UR (4k = 1, K)
(4)
for some V/ O, and then normalized so that qi +... (1) Sagawa et al. (020a) then showed (in their Proposition 2) that for convex settings, the Group DRO risk of iterates converges to the global minimum with the rate ((t-1/2) if v is sufficiently small.
4 THEORETICAL RESULTS FOR REGRESSION
In this section, we will study GRW for regression tasks that use the squared loss
1 - 2
( v)
(5)
We will prove that for both linear models and sufficiently wide fully-connected neural networks, the implicit bias of GRW is equivalent to ERM, which means that starting from the same initial point, GRW and ERM will converge to the same point when trained for an infinitely long time. Thus, GRW cannot improve over ERM as it produces the exact same model as ERM. We will further show that while regularization can affect this implicit bias, it must be large enough significantly lower the training performance, or the final model will still be similar to the unregularized ERM model.
3

---

Published as a conference paper at ICLR 2023
Morm of Cafference
0.26
Re -Buelt Pass feedl
Momm of Mrecdl)
0.62
Panng L33
0.75
0.8
0.04
2.30
CERO
Go
0.6
3.60
0.25
0.4
0.00
0.00
2003
4000
2002
4020
2003
4000
(a) Weight Difference
(b) Norm of ERM Model
(c) Training Loss
(d) Group Weights
Figure/ I: Experimental results of ERM, importance weighting (IW) and Group DRO (GDRO) with
the squared loss on six MNIST images with linear model. All norms are L2 norms.
4.1 LINEAR MODELS
We first demonstrate our result on simple linear models to provide our readers with a key intuition which we will later apply to neural networks. This key intuition draws from results of Gunasekar ct al. (2018). Let the linear model be denoted by f(x) = (8, x) where 0 E R4. We consider the overparameterizeed setting where d > n. The weight update rule of GRW under GD is the following:
(((+1) = 0(*)
(1) ( 9i
(6)
where 17 > 0 is the learning rate. For a linear model with the squared loss, the update rule is
n
g((+1) 0(0) 17 4 xz (f(0
ys)
For this training scheme, we can prove that if the training error converges to zero, then the model converges to an interpolator H" (s.t. Vi, (0", -0",""" x.) = ys) independent of qe (proofs in Appendix D): Theorem 1. ".,.... Fn are linearly independent, then under the squared loss, for any GRW such that the empirical training risk R(((()) + as t co, it holds that ((t) converges interpolator 6 that only depends on g(0) and xı,
an, " En. but does not depend on qi
(t)
The proof is based on the following key intuition regarding the update rule 7 g(++1) o00 is a linear combination of ...-.. Un for all t, so Ot ((0) always lies in the linear subspace span ( J. which is an ve-dimensional linear subspace if æ1,-.. Dn are linearly indepen- dent. By Cramer's rule, there is exactly one 0 in this subspace such that get interpolation of all the data (Ø (10), .x.) Ys for all i E [1....,n] n). In other words, the parameter 6* = 0 + ((0) in this subspace that interpolates all the data is unique. Thus the proof would follow if we were to data. Moreover, this proof works for any first-order optimization method such that the training risk converges to O.
show that g(t) - g which lies in the subspace, also converges to interpolating the
We have essentially proved the following sobering result: any GRW algorithm that achieves zero training error exactly produces the ERM model, so it does not improve over ERM. While the various distributional shift methods discussed the introduction have been shown to satisfy the precondi- tion of convergence to zero training error with overparameterized models and linearly independent inputs (Sagawa et al. 2020a),, we provide the following theorem that shows this for the broad class of GRW methods. Specifically, we show this result for any GRW method that satisfies the following assumption with a sufficiently small learning rate:
(t) -> 9s as co. And min; qi q" 0. Assumption 1. There are constants q1.-.. In Vi, qi
Theorem 2. If x1.... En are linearly independent, then there exists To > O such that for any GRW satisfying Assumption I with the squared loss, and any n S n7,, the empirical training risk R(((t))
oc.
Finally, we use a simple experiment to demonstrate the correctness of this result. The experiment is conducted on a training set of six MNIST images, five of which are digit 0 and one is digit 1. We use a 784-dimensional linear model and run ERM, importance weighting and group DRO. The results presented in Figure [] and they show that the training loss of each method converges to O, and the gap between the model weights of importance weighting, Group DRO and ERM converges to O. meaning that all three model weights converge the same point, whose Le norm is about 0.63. Figure adla shows that the group weights in Group DRO empirically satisfy Assumption
4.2 WIDE NEURAL NETWORKS (WIDE NNs)
Now we study suffiiently wide fully-comnected neural networks. We extend the analysis in Lee et al. (2019) in the neural tangent kernel (NTK) regime (Jacot et al. 2018). In particular study
4

---

Published as a conference paper at ICLR 2023
the following network:
1+1 W n +/ and ='-1=a ah(412)
01=0,... L.)
(8)
vdi
where a is a non-linear activation function, W E BRd and Wh E Rixd2, Here du d. The parameter vector 0 consists of W :... wo...., WL and 60 ..... bt (0 is the concatenation of all flattened weights and biases). The final output is f(x) = hh' h And let the neural network be initialized as
W 10
W 0 j.j
(1-, .. 1-11 and
by (() 100,
(()) b
10,,
We also need the following assumption on the wide neural network: Assumption 2. a is differentiable everywhere. Both a and its first-order derivative å are Lipschitz 3
Difference from Jacot et al. 2018). Our initialization
9 differs from the original one in Jacot
al. 2018) in the last (output) layer, where we use the zero initialization
W-410) instead of the (.
Gaussian initialization w ~V 1). This modification permits us to accurately approximate the NN with its linearized counterpart (IT) as we notice that the proofs in [ee et al. (2019) (partic- ularly the proofs of their Theorem 2.1 and their Lemma I in Appendix G) are flawed. Appendix we will explain what went wrong in their proofs and how we fix it with this modification.
Denote the neural network at time by (x)) f(z; o(t) which is parameterized by 0(0) E R where p is the number of parameters. We use the shorthand Ve (z) (z) == Vof( 0) 0=0.- The neural tangent kernel (NTK) of this model is e(0) (xx x') = f (z) T V (=))) and the Gram matrix is (0) = (0) (X E Rax=n For this wide NN we still have the following NTK thcorem: Lemma 3. If Lipschitz and d + 0o 1 It sequentially, then e (x. x²) converges in probability to a non-degenerate deterministic limiting kernel O(x, x²).
The kernel Gram matrix θ 0(X,X) E Raxa is a positive semi-definite symmetric matrix. Denote its largest and smallest eigenvalues by X and Amin Note that + is non non-degenerate, so we can assume that Ain > 0 (which almost surely true when d₁ >> n2). Then we have:
Theorem 4. Let f(t) be a wide fully-conmected neural network that satisfies Assumption and is
trained by any GRW satisfying Assumption [ with the squared loss. Let f((). be the same model
trained by ERM from the same initial point. If =... dr. = d, Vos(0) (Z1),... VoI(0) (æc.) are linearly independent, and A > 0, then there exists constant 1/1 > such that: if S m then for any ō O, there exists δ > such that as long as d Z D, with probability at least (1 8) over random initialization we have: for any test point x E I2d such that |<=1|2 S as d + oc.
lim sup (()()))) rlt (a) = ((ā-1/4) +0
(10)
6+00
Essentially this theorem implies that any test point æ in the unit ball, the GRW model and the ERM model produce almost the same output, so they have almost the same performance. Note that for simplicity, we only prove for d1 = ... = dp = d - oo, but the result can be very easily extended to the case where dı/d1 as for = 2,... L for some constants a.,..., ,a,, and dj + co. The key to proving this theorem is to consider the linearized neural network of (()(
1 (z) f(0) (x) + (0(0) - 0 Vef f0) (x))
(11)
which is linear model w.r.f (o)( If V (0) dent (which is almost surely true when the model is overparameterized so that 0 has a very high dimension), then our key intuition tells us that the linearized NN will converge to the unique inter- polator. Then we show that the wide NN can be approximated by its linearized counterpart uniformly throughout training. which is considerably more subtle in our case due to the GRW dynamics. Here we prove the upper bound 1d/4) but in fact the upper bound can be (dd-1/2+e) for any e > 0:
(zx)) are linearly indepen-
is Lipschitz, if there exists constant L > 0 such that for any æ1, 22. [s(=))(())))))))( - (==2) S L ||ær w2ll2- -on-degeeerate means that O(x, x') depends on æ and x' and is not a constant. 5 For ease of understanding, later we will write this condition as "with sufficiently small learning rate".
5

---

Published as a conference paper at ICLR 2023
Lemma 5 (Approximation Theorem). For wide fully-connected neural network f(t) satisfying Assumption 2 and trained by any GRW satisfying Assumption / with the squared loss, let fim be its linearized neural network trained by the same GRW (i.e. 9; are the same for both networks for any i and t). Under the conditions of Theorem + with a sufficiently small learning rate, for any
> 0, there exist constants D > and C > O such that as long as d 2 D. with probability at least
(1 1-5 5) over random initialization we have: for any test point R such that | S 1,
sup t20
f (x) - (z) S Cd-1/4
(12)
This lemma essentially says that throughout the GRW training process, on any test point æ in the unit ball, the linear NN and the wide NN produce almost the same output. So far, we have shown that in a regression task, for both linear and wide NNs, GRW does not improve over ERM.
4.3 WIDE NEURAL NETWORKS, WITH L2 REGULARIZATION
Previous work such as Sagawa et al. (020a) proposed to improve GRW by adding L2 penalty to the objective function, In this section, we thus study adding L2 regularization to GRW algorithms:
10 g(t) (1) = Σ Oi ((I(a))) + 1 000)
(13)
At first sight, adding regularization seems to be natural approach and should make a difference. Indeed, from the outset, we can easily show that with L22 regularization, the GRW model and the ERM model are different unlike the case without regularization. As an concrete example, when f is a linear model, é is convex and smooth, then R. (f) with static GRW is convex smooth objective function, so under GD with sufficiently small learning rate, the model will converge the global minimizer (see Appendix D.I. Moreover, the global optimum 8 satisfies V VoR q(o) (z;20))) = 0, solving which yields 0 g²0) (XQX + p diag(?), ..... (n), so adding L2 regularization at least seems to yield different results from ERM (albeit whether improves over ERM might depend on ......)).)))
- - (X)), which depends on
However, the following result shows that this regularization must be large enough to sigmificantly lower the training performance, or the final model would still be close the unregularized ERM model. We still denote the largest and smallest eigenvalues of the kernel Gram matrix θ by A max and A min We use the subscript "reg" to refer a regularized model (trained by minimizing (13).
Theorem 6. Suppose there exists Mo > s.t. ( (a) S Mo all ||>|| 1. If X min and p > O, then for wide NN satisfying Assumption 2 and any GRW minimizing the squared loss with sufficiently small learning rate if d1 d2
= di = d, (x1), (of(")
are linearly independent, and the empirical training risk of f satisfies
lim sup R( <c
(14)
for some e >> then with sufficiently small learning rate, as d + oo, with probability close over random initialization, for any x such that ||0||| I 1 we have
lim t-
f (x) f(RM(()) (2)) = 1 vv)) +((e
(15)
where (tt) is trained by regularized GRW and F by unregularized ERM from same initial points.
This theorem essentially says that if the regularization too small and the training error close to zero, then the regularized GRW model still produces output very close to that of the ERM model on any test point æ in the unit ball. Thus, a small regularization makes little difference.
The proof again starts from analyzing linearized NNs, and showing that regularization does not help there (Appendix D.4.2p. Then, we prove a new approximation theorem for L2 regularized GRW connecting wide NNs to linearized NNs uniformly throughout training (Appendix D.4.I). With regularization, we no longer need Assumption T to prove the new approximation theorem which was used to prove the convergence of GRW, because with regularization GRW naturally converges.

---

Published as a conference paper at ICLR 2023
Comeroifeee
Pi -Rall 19aa - Swell
Trining Latt
0.4
CD-R0 BM
0.06-
1B - Sawld
19pa - Baedl
0.04
GDRO ERM
0.04
Tointng
0.2-
0.32
0.02
0.20
0
2000
4000
0.0
2000
4090
0
2000
4000
0.0
2000
4000
Spochs
Epochs
Epects
Epochs
(a) Weight Difference
(b) Training Loss
(c) Weight Difference
(d) Training Loss
Figure 2: Experimental results of ERM, importance weighting (IW) and Group DRO (GDRO) with L2 regularization with the squared loss. Left two: μ 0.1; Right two: μ 10.
To empirically demonstrate this result, we run the same experiment as in Section 4.1 but with L regularization. The results are presented in Figure - We can see that when the regularization is small, the training losses still converge to O, and the three model weights still converge to the same point. On the contrary, with a large regularization, the training loss does not converge to O, and the three model weights converge different points. This shows that the regularization must be large enough to lower the training performance to make significant difference to the implicit bias.
5 THEORETICAL RESULTS FOR CLASSIFICATION
Now we consider classification where y= (+1,-11 -1). The big difference is that classification losses don't have finite mininizers. A classification loss converging to zero means that the model weight "explodes" to infinity instead of converging to a finite point. We focus on the canonical logistic loss: {(ū v) log(1 + exp(-Uu)
(16)
5.1 LINEAR MODELS
We first consider training the linear model [(x) (0, x) with GRW under gradient descent with the logistic loss. As noted earlier, in this setting, Byrd & Lipton (2019) made the empirical observation that importance weighting does not improve over ERM. Then, Xu et al. (2021) proved that for importance weighting algorithms, as f + oc, ||e(1) 1| + oc and (C0) / |l2 converges to a unit vector that does not depend on the sample weights, so it does not improve over ERM. To extend this theoretical result to the broad class of GRW algorithms,, we will prove two results. First, in Theorem 7 we will show that for the logistic loss and any GRW algorithm satisfying the weaker assumption:
Assumption 3. For all i, lim inf 9: > O.
if the training error converges to O, and the direction of the model weight converges to fixed unit vector, then this unit vector must be the max-margin classifier defined
ÓRM
arg max
min y: (0, or.)
(17)
0:]0011==1 (==ا."
Second, Theorem 8 shows that for any GRW satisfying Assumption I the training error converges to and the direction of the model weight converges, so it does not improve over ERM.
Theorem 7. !f at,,.. ,n are linearly independent, then for the logistic loss, we have: for any GRW satisfying Assumption 3 if as t + oo the empirical training risk R(((() converges to 0 and /(0//1100011 + for some unit vector u, then u 0MM-
This result is an extension Soudry al. 20188) and says that all GRW methods (including ERM) make the model converge to the same point OxM that does not depend on (t) In other words, the samples weights do not affect the implicit bias. Thus, for any GRW method that only satisfies the weak Assumption 3 as long as the training error converges to 0 and the model weight direction converges, GRW does not improve over ERM. We next show that any GRW satisfying Assumption [ does have its model weight direction converge, and its training error converge to 0.
Theorem 8. For any loss that is convex, L-smooth in ÿ and strictly monotonically decreasing to zero as yn + +oc, and GRW satisfying Assumption [ denote F(O) = Em q; æi), yi). If 21, In are linearly independent, then with a sufficiently small learning rate n7, we have:
(i) F(B(t) - 0 as t - x0.
(ii)
[[(())
11
as oc.
(iii) Let 0n arg ming ( F(0): |10112 R). On is unique for any R such that mingon F(0)
min,g,(() y.). And if lim 6n exists, then lime-xo0 Toco also exists and they equal.
git)
7

---

Published as a conference paper at ICLR 2023
This result is extension of Theorem of et al. (2020). For the logistic loss, it is easy show 6n that it satisfies the conditions of the above theorem and n-m R 0 Thus, Theorems imply that all GRW satisfying Assumption | (including ERM) have the same implicit bias (see Appendix D.5.3). We also have empirical verification for these results (see Appendix C
Remark. It impossible extend these results wide NNs like Theorem because for a neural network, if ||00 2 goes to infinity, then f will also go infinity. However, for linear model, the gradient is a constant, Consequently, the gap between the neural networks and its linearized counterpart will "explode" under gradient descent, so there can be no approximation theorem like Lemma that can connect wide NNs to their linearized counterparts. Thus, we consider regularized GRW, for which ((t) converges to finite point and there is an approximation theorem.
5.2 WIDE NEURAL NETWORKS, WITH L2 REGULARIZATION
Consider minimizing the regularized weighted empirical risk 13 with being the logistic loss. As in the regression case, with L2 regularization, GRW methods have different implicit biases than ERM for the same reasons as in Section 4.3 And similarly, we can show that in order for GRW methods to be sufficiently different from ERM, the regularization needs to be large enough to sig- nificantly lower the training performance. Specifically, in the following theorem we show that if the regularization is too small to lower the training performance, then a wide neural network trained with regularized GRW and the logistic loss will still be very close the max-margin linearized neural network:
(a)(())= (ŌNM; Vol (x)) where
δMM = arg max min yE (0, Vo (w.))) [10]|==1 i=1,-.,,
(18)
Note that /MM does not depend on oi Moreover, using the result in the previous section we can show that linearized neural network trained with unregularized ERM will converge to fMM:
Theorem 9. Suppose there exists Mo > such that | (a=) (a>) S Mo for all test point æ. For wide NN satisfying Assumption 2 and for any GRW satisfying A Assumption [with the logistic loss, f are linearly independent and the
if d1 = d2 = = d2 = d and f (xz), learning rate is sufficiently small, then for any ō > O there exists a constant C > such that: with probability at least (1 - 8) over random initialization, as d -> Do we have: for any e E (0, 2), if the empirical training error satisfies sup R(F((E) ) e, then for any test point such that [f)M(()) > C- (- 2c) 1/2 1/2 ((t) (x) has the same sign as fmua()) when t is sufficiently large.
This result says that at any test point æ on which the max-margin linear classifier classifies with a margin of (2( 2c) -1/2), the neural network has the same prediction. And as decreases, the confidence threshold also becomes lower. Similar Theorem 6 this theorem provides the scaling of the gap between the regularized GRW model and the unregularized ERM model w.r.t. e.
This result justifies the empirical observation in Sagawa et al. (2020a) that with large regularization, some GRW algorithms can maintain a high worst-group test performance, with the cost of suffering a significant drop in training accuracy. On the other hand, if the regularization is small and the model can achieve nearly perfect training accuracy, then its worst-group test performance will still significantly drop.
DISCUSSION
6.1 DISTRIBUTIONALLY ROBUST GENERALIZATION AND FUTURE DIRECTIONS
large body of prior work focused on distributionally robust optimization, but we show that these methods have (almost) equivalent implicit biases as ERM. In other words, distributionally robust optimization (DRO) does not necessarily achieve better distributionally robust generalization (DRG). Our results pinpoint critical bottleneck in the current distribution shift research, and argue that a deeper understanding in DRG is crucial for developing better distributionally robust training algorithms. Here we discuss three promising future directions to improving DRG.
8

---

Published as a conference paper at ICLR 2023
The first approach is data augmentation and pretraining on large datasets. Our theoretical findings suggest that the implicit bias of GRW is determined by the training samples and the initial point, but not the sample weights. Thus, to improve DRG, can either obtain more training samples, or start from a better initial point, as proposed in two recent papers (Wiles et al. 2022 Sagawa et al. 2022).
The second approach (for classification) is go beyond the class of (iterative) sample reweighting based GRW algorithms, for instance via logit adjustment (Menon et al.] 2021), which makes a classifier have larger margins on smaller groups improve its generalization on smaller groups.
An early approach by Cao et al. (2019) proposed to add an O 1/4) additive adjustment term to the logits output by the classifier. Following this spirit, Menon al. (2021) proposed the LA-loss which also adds an additive adjustment term to the logits. Ye et al.] (020) proposed the CDT-
which adds a multiplicative adjustment term to the logits by dividing the logits of different classes with different temperatures. Kini et al.] (2021) proposed the VS-loss which includes both additive and multiplicative adjustment terms, and they showed that only the multiplicative adjustment term affects the implicit bias, while the additive term only affects optimization, fact that can be easily derived from our Theorem & Finally, [i et al. (2021a) proposed AutoBalance which optimizes the adjustment terms with bi-level optimization framework.
The third approach is to stay within the class of GRW algorithms, but to change the classifica- tion/regression loss function to be suited to GRW. A recent paper (Wang et al.] (022) showed that for linear classifiers, one can make the implicit bias of GRW dependent on the sample weights by replacing the exponentially-tailed logistic loss with the following polynomially-tailer loss:
Een (iv)
if ÚV < 3
la la.
(19)
if fy 2
juy (B 1]]a
And this result can be extended to GRW satisfying Assumption I Jusing our Theorem g The reason why loss 19p works is that it changes lim f and the new limit depends on the sample weights.
6.2
LIMITATIONS
Like most theory papers, our work makes some strong assumptions. The two main assumptions are:
The model is a linear model or sufficiently wide fully-connected neural network.
iii) The model is trained for sufficiently long time, i.e. without early stopping.
Regarding (i), Chizat et al. 2019) argued that NTK neural networks fall in the "lazy training" regime and results might not be transferable to general neural networks. However, this class of neural networks has been widely studied in recent years and has provided considerable insights into the behavior of general neural networks, which hard to analyze otherwise. Regarding (ii). in some easy tasks, when early stopping is applied, existing algorithms for distributional shift can do better than ERM (Sagawa et al.) (2200)). However, as demonstrated in GGulajaai & Lopez- Paz (202T): Koh et al. (222)) real applications these methods still cannot significantly improve over ERM even with early stopping, so early stopping is not the ultimate universal solution. Thus, though inevitably results rely on some strong assumptions, we believe that they provide important insights into the problems of existing methods and directions for future work, which are significant contributions to the study of distributional shift problems.
7 CONCLUSION
In this work, we posit a broad class of what we call Generalized Reweighting (GRW) algorithms that include popular approaches such as importance weighting, and Distributionally Robust Opti- mization (DRO) variants, that were designed towards the task of learning models that are robust to distributional shift. We show that when used to train overparameterized linear models or wide NN models, even this very broad class of GRW algorithms does not improve over ERM, because they have the same implicit biases. We also showed that regularization does not help if it is not large enough to significantly lower the average training performance. Our results thus suggest to make progress towards learning models that are robust to distributional shift, we have to either go beyond this broad class of GRW algorithms, design new losses specifically targeted to this class.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
We acknowledge the support of NSF via OAC-1934584, IIS-1909816, DARPA via 1200112020006, and ARL.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. International Conference on Machine Learning, pp. 242 442-252. PMLR, 2019.
Martin Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint wwt.v::97.0088900 2019.
Su Lin Blodgett, Lisa Green, and Brendan O'Connor. Demographic dialectal variation in social American English. In Proceedings of the 2016 Conference on
media: A case study of African-American Empirical Methods in Natural Language Processing, pp. 1119-1130, Austin, Texas, November 2016. Association for Computational Linguistics. doi: 10.
Jonathon Byrd and Zachary Lipton. What is the effect of importance weighting in deep learning? In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp- 872-881. PMLR, 09-15 Jun 2019.
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with label sineelddtiibuiion-aae -warre margin loss. Advances in Neural Information Processing Systems, 32:1567-1578, 2019.
Lénaïc 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. In 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.08750, 2018.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science confer- ence, pp. 214 226, 2012.
Tongtong Fang, Nan Lu, Gang Niu, and Masashi Sugiyama. Rethinking importance weighting for deep learning under distribution shift. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Bal- can, and H. Lin (eds.), Advances in Neural Information Processsing Systems, volume 33, pp. 11996- 12007. Curran Associates, Inc., 2020. URL /ttppe///orooceee.ggg..... mewrriinsn.nnnnnns............ neurips. 2tt.2///S..222222275055122222222
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Domsainadveesarrill training of neural net- works. The journal of machine learning research, 17(1):299-20300 2016.
Ishaan Gulrajani and David Lopez-Paz. In search of lost domain generalization. In International Conference on Learning Representations, 2021.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1832-1841.
PMLL, PMLR, 10-15 Jul 2018.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In D. Lee, M. Sugiyama, U. Luxburg. I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 29, pp. 3315-3323. Curran Associates, Inc., 2016.
10

---

Published as a conference paper at ICLR 2023
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 Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1929-1938, Stockholnsmässan, Stockholm Sweden, 10-15 Jul 2018. PMIR.
Dirk Hovy and Anders Søgaard. Tagging performance correlates with author age. In Proceedings of the 53rd anmual meeting of the Association for Computational Linguistics and the 7th interna- tional joint conference natural language processing (volume 2: Short papers), pp. 483-488, 2015.
Weihua Hu, Gang Niu, Issei Sato, and Masashi Sugiyama. Does distributionally robust supervised learning give robust classifiers? In International Conference on Machine Learning, pp. 2029- 2037. PMLR, 2018.
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.
Ziwei Ji, Miroslav Dudik, Robert E. Schapire, and Matus Telgarsky. Gradient descent follows the regularization path for general losses. In Jacob Abernethy and Shivani Agarwal (eds.), Proceed- ings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 2109-2136. PMLR, 09-12 Jul 2020.
Byungju Kim and Junmo Kim. Adjusting decision boundary for class imbalanced learning. IEEE Access, 8:81674-81685, 2020.
Ganesh Ramachandra Kini, Orestis Paraskevas, Samet Oymak, and Christos Thrampoulidis. Label- imbalanced and group-sensitive classification under overparameterization. Thirty-Fifth Con- ference Neural Information Processing Systems, 2021.
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsub- ramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, Tony Lee, Etienne David, Ian Stavness, Wei Guo, Berton Earnshaw, Imran Haque, Sara M Beery. Jure Leskovec, Anshul Kundaje, Emma Pierson, Sergey Levine, Chelsea Finn, and Percy Liang. Wilds: A bench- mark of will distribution shifts. 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. 5637-5664. PMLR, 18-24 Jul 2021.
Matt J Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness. In Advances in neural information processing systems, pp. 4066-4076, 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-8558 2019.
Haoliang Li, Sinno Jialin Pan, Shiqi Wang, and Alex C Kot. Domain generalization with adver- sarial feature learning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 5400-5409, 2018
Mingchen Li, Xuechen Zhang, Christos Thrampoulidis, Jiasi Chen, and Samet Oymak. Autobal- ance: Optimized loss functions for imbalanced data. In Thirty-Fifth Conference on Neural Infor- mation Processing Systems, 2021a.
Tianhao Li, Limin Wang, and Gangshan Wu. Self supervision to distillation for long-tal tailed visual recognition. In Proceedings of the IEEE/CVF international Conference on Computer Vision, pp- 630-639, 2021b.
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.
11

---

Published as a conference paper at ICLR 2023
Hong Liu, Jeff Z. HaoChen, Adrien Gaidon, and Tengyu Ma. Self-supervised learning is more robust to dataset imbalance. In International Conference on Learning Representations, 2022.
net Eorumm21d
Mingsheng Long, Han Zhu, Jianmin Wang, and Michael Jordan. Unsupervised domain adaptation with residual transfer networks. Advances in neural information processing systems, 29, 2016.
Aditya Krishna Menon, Sadeep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, and Sanjiv Kumar. Long-tail learning via logit adjustment. In International Conference on Learning Representations, 2021.
Sacid Motüan, Marco Piccirilli, Donald A Adjeroh, and Gianfranco Doretto. Unified deep super- vised domain adaptation and generalization. Proceedings of the IEEE international conference on computer vision, pp. 5715-5725, 2017.
Yonatan Oren, Shiori Sagawa, Tatsunori Hashimoto, and Percy Liang. Distributionally robust lan- guage modeling. In Proceedings of the 2019 Conference on Empirical Methods Natural Lan- guage Processing and the 9th International Joint Conference Natural Language Processing (EMNLP-HJCNLP), pp. 4227-4233 Hong Kong, China, November 2019. Association for Com- putational Linguisties. doi: 10.18653/v//D19-144
John Rawls. Justice fairness: A restatement. Harvard University Press, 2001.
Elan Rosenfeld, Pradeep Kumar Ravikumar, and Andrej Risteski. The risks of invariant risk mini- mization. In International Conference on Learning Representations, 2021.
Shiori Sagawa, Pang Wei Koh, Tatsunori B. 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. 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. 5346-8350 PMLR, 13-18 Jul 2020b.
Shiori Sagawa, Pang Wei Koh, Tony Lee, Irena Gao, Sang Michael Xie, Kendrick Shen, Ananya Kumar, Weihua Hu, Michihiro Yasunaga, Henrik Marklund, Sara Beery, Etienne David, Ian Stavness, Wei Guo, Jure Leskovec, Kate Saenko, Tatsunori Hashimoto, Sergey Levine, Chelsea Finn, and Percy Liang. Extending the WILDS benchmark for unsupervised adaptation. In Inter- national Conference on Learning Representations, 2022.
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.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19 (1):2822-2878, 2018.
Baochen Sun and Kate Saenko. Deep coral: Correlation alignment for deep domain adaptation, 2016.
Rachael Tatman. Gender and dialect bias in youtube's 's automatic captions. In Proceedings of the First ACL Workshop on Ethics in Natural Language Processing, pp. 53-59, 2017.
Eric Tzeng, Judy Hoffman, Trevor Darrell, and Kate Saenko. Simultaneous deep transfer across domains and tasks. In Proceedings of the IEEE international conference computer vision, pp. 4068-4076, 2015.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010.
Ke Alexander Wang, Niladri Shekhar Chatterji, Saminul Haque, and Tatsunori Hashimoto. Is im- portance weighting incompatible with interpolating classifiers? In International Conference on Learning Representations, 2022.
12

---

Published as a conference paper at ICLR 2023
Peng Wang, Kai Han, Xiu-Shen Wei, Lei Zhang, and Lei Wang. Contrastive learning based hybrid networks for long-tailed image classification. In Proceedings of the IEEE/CVE conference on computer vision and pattern recognition, pp. 943-952, 2021.
Olivia Wiles, Sven Gowal, Florian Stimberg, Sylvestre-Alvise Rebuffi, Ira Ktena, Krishnamurthy Dj Dvijotham, and Ali Taylan Cemgil. A fine-grained analysis on distribution shift. In International Conference on Learning Representations, 2022.
Yu Xie and Charles Manski. The logit model and response-bane based samples. Sociological Methods & Research, 17(3):283-302, 1989.
Da Xu, Yuting Ye, and Chuanwei Ruan. Understanding the role of importance weighting for deep learning. International Conference on Learning Representations, 2021.
Han-Jia Ye, Hong- You Chen, De-Chuan Zhan, and Wei-Lum Chao. Identifying and compensating for feature deviation in imbalanced deep learning. arXiv preprint arXiv:2001 Sttt:20001.018855 2020.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna 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. PMIR, 18-24 Jul 2021a
Runtian Zhai, Chen Dan, Arun Suggala, Zico Kolter, and Pradeep Kumar Ravikumar. Boosted CVar classification. In Thirty-Fifth Conference Neural Information Processing Systems, 2021b.
13

---

Published as a conference paper at ICLR 2023
A RELATED WORK
A.1 SUBPOPULATION SHIFT
In this work, we mainly focus on the subpopulation shift problem, which has two main applications: group faireess and long-tailed learning (learning with class imbalance). In both applications, the dataset can be divided into several subgroups, and this work considers minimizing the worst-group risk, defined the maximum risk over any group.
Group Fairness. Group fairness refers to the scenario where the dataset contains several "groups" (such as demographic groups), and model is considered fair if its per-group performances meet certain criteria (a "fairness" notion). Group fairness 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. Many previous papers proposed number of fairness notions, such as equal opportunity, statistical parity, etc. Among them, Hashimoto et al. (2018) studied another type of group fairness called Rawlsian max-min fairness Rawls] (2001), which does not require equal performance but rather requires high performance on the worst-off group. The subpopulation shift problem we study in this paper is naturally connected to the Rawlsian max-min fairness. A large body of recent work have studied how to improve this g performance Duchi & Namkoong 20: Oren et al. (2019) Liu al. (022I; ): Zhai et al. (2021a). Recent work however observe that these approaches, when used with modern overparameterized models, easily overfit SSgawa et al. (2020a bj. Apart from group faimess, 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.
Long-tailed Learning. Long-tailed learning refers to the scenario where different classes have different sizes, and usually there are some "minority classes" with extremely few samples that are much more difficult learn than the other classes. Using GRW such as importance weighting for long-tailed learning is a very old idea which dates back to Xie & Manski (1989). However, recently Byrd & Lipton (019) found that the effect of importance weighting for long-tailed learning dimin- ishes as training proceeds, which leads to line of recent work on how to improve the generalization in long-tailed learning (Cao et al. 2019 Menon et al.) 2021 Ye et al., 2020 Kim Kim| 2020) Kini et al. )) Most of these papers share a common idea: Forcing the model to have larger margins on smaller groups, so that its generalization on smaller groups can be better. Self-supervised learn- ing is also used in long long-tailed learning. For instance, [iu et al. (2022) found that self-supervised learning can achieve good performances in long-tailed learning, Wang et al. (2021) used contrastive learning for long-tailed learning, and Li al. 2021b) used seff-disiillatin.
A.2 DOMAIN GENERALIZATION
Domain generalization is the second common type of distribution shift. In domain generalization and the related domain adaptation, a model is tested on a different domain than what it is trained The most common idea in domain generalization is invariant learning, which learns feature extractor that is invariant across domains, usually by matching the feature distribution of different domains. Since we have no access to the target domain, in invariant learning we assume that we have access to multiple domains in the training set, and we learn a feature extractor with small variance across these domains. Examples include CORAL (Sun & Saenko 2016), DANN (Ganin et al. 2016). MMD (Li et al. 2018) and IRM (Arjovsky et al. 2019). However, Gulrajani & Lopez- Paz (2021) Koh et al. (2021) empirically showed that most these methods cannot do better than standard ERM, and Rosenfeld et al. (202T) theoretically proved that IRM cannot do better than ERM unless the number of training domains is greater than the number of independent features.
One problem of invariant learning methods is that they do not necessarily align the classes. For a source domain P and a target domain Q, even if we have successfully learned a feature extractor & such that ((P) ss (QQ), there is no guarantee that & can map the samples in P and Q from the same class to the same location in the feature space. In the worst case, can map the positive samples in P and the negative samples in to the same location and vice versa, in which case 100% accuracy over P means 0% accuracy over Q. The goal of class aligmment is to make sure that samples from the same class mapped together, and far away from the other classes. For
14

---

Published as a conference paper at ICLR 2023
example, Tzeng et al. (2015) used soft labels to align the classes, Long al. (2016) minimized the class-based cross entropy on the target domain while keeping the source and target classifiers close with residual block, and Motiaan al. (2017) adopted a similarity penalty to keep samples from different classes away from each other.
A.3 IMPLICIT BIAS UNDER THE OVERPARAMETERIES SETTING
For overparameterizee models, there could be many model parameters which all minimize the train- ing loss. In such cases, it is of interest to study the implicit bias of specific optimization algorithms such as gradient descent i.e. to what minimizer the model parameters will converge to Duu et al. (2019): ; Allen-Zhu et al. (2019). Our results use the NTK formulation of wide neural networks Jacot al. (0188), and specifically we use linearized neural networks to approximate such wide neural networks following Lee et al. (2019). There is some criticism of this line of work, c.g. Chizat al. (2019) argued that infinitely wide neural networks fall the "lazy training" regime and results might not be transferable to general 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 to analyze otherwise.
A.4 COMPARISON WITH HU ET AL. 20188
prior work Hu et al. 2018) also proved that GRW equivalent to ERM under certain conditions. However, we would like to point out that this work is substantially different from Hu et al. (2018). Hu et al. 2018) proved that in classification that uses the zero-one loss, GRW methods such as DRSL are equivalent to ERM, in the sense that the minimizer of the DRSL risk is also the minimizer of the average risk. However, this does not mean that DRSL and ERM will always converge to the same point, as there could be multiple minimizers. Their result relies on the zero-one loss, which leads to a monotonic linear relationship between the DRSL risk and the average risk. Moreover, their result is only about the relationship between two minimizers, and they did not prove that DRSL and ERM can actually converge to these global minima.
On the other hand, in our results, first show that without regularization, GRW and ERM will converge to the exact same point, so that they have equivalent implicit biases, which is a much stronger result. Then we show that even with regularization, if the regularization is not large enough, GRW will still converge to a point that is very close to the point ERM converges to. Our results do not depend on the loss function, and work for both the squared loss for regression and the logistic loss for classification (and can be extended to other losses). Instead, our results depend on the optimization method (must be first-order or gradient-based or wide NN), since we need to explicitly prove that both GRW and ERM can reach the global minima trained under a small learning rate for sufficienlly long. equivalence between GRW and ERM under the zero-one loss with a monotonic relationship between the two risk functions, while our results focus on the optimization and training dynamics, and prove that GRW and ERM have almost equivalent implicit biases.
as well the model architecture (linear
word, Hu et al. (2018) proves the
B EXTENSION TO MU.II-DIMMENIONNL. REGRESSION / MULTI-CLASS CLASSIFICATION
In our results, we assume that f : Rd R for simplicity, but our results can be very easily extended to the case where f IRd - R** For most of our results, the proof consists of two major com- ponents: (i) The linearized neural network will converge to some point (interpolator, max- max-mnn classifier, etc.); (ii) The wide fully-connected neural network can be approximated by its linearized counterpart. For both components, the extension is very simple and straightforward. For (i), the proof only relies the smoothness of the objective function and the upper quadratic bound it en- tails, and the function is still smooth when its output becomes multi-dimensional: For (ii), we can prove that sup, (z) fim (x) l|2 = o(d-1/4) in exactly the same way. Thus, all of our results hold for multi-dimensional regression and multi-class classification.
Particularly, for the multi-class cross- cross-entropy loss, using Theorem X we can show that under any the direction of the weight of a linear classifier will converge the
GRW satisfying Assumption |
15

---

Published as a conference paper at ICLR 2023
0.6
0.22
Nom Nom of
Hi -Brrd?
Taiiie Lnn
18oo Amels
Group
GDRO
0.28
0.002
Nomm
0.06
230
500
750
1000
0.000
x10000 apochs
x10000
x10000
K10000
(d)
Group
Weights
(a) Weight Difference
(b) Norm of ERM Model
(c) Training Loss
GDRO
Nom Dittewens
0.275
Norm Mase
0.10-
0250
1F, Bundi
10
GBRO
18ga Buob
0.05
0.4
0.255
x10000 esecha
1800
1000
K10000
(h)
Group
Weights
(e) Weight Difference
(I) Norm of ERM Model
Training Loss
GDRO)
Figure 3: Experimental results ERM, importance weighting (IW) and Group DRO (GDRO) with the logistic loss and the polynomially-tailee loss. First row: Logistic loss; Second row: Polynomially-taiie loss. All norms are L2 norms. O is unit vector which is the direction of
following max margin classifier:
:101|2 = 1
θMM = arg min
min
f(wi).. - -max f(x))y v7t
(20)
which is still independent of qe.
C MORE EXPERIMENTS
We run ERM. importance weighting and Group DRO the training set with 6 MNIST images which we used I wiih with the logistic loss and the polynomially-taleed loss (Fqn. 19 with 1 = 0 and Gen being the logistic loss shifted make the overall loss function continuous) this dataset for 10 million epochs (note that we run for much more epochs because the convergence very slow). The results are shown in Figure 3 From the plots we can see that:
For either loss function, the training loss of each method converges to O.
In contrast to the theory that the norm of the ERM model will go to infinity and all models will converge the max-margin classifier, the weight of the ERM model gets stuck at some point, and the norms of the gaps between the normalized model weights also get stuck. The reason is that the training loss has got so small that becomes zero in the floating number representation, so the gradient also becomes zero and the training halts due limited computational precision.
still observe a fundamental difference between the logistic loss and the polynomially-tailed loss. For the logistic loss, the norm of the gap between importance weighting (or Group DRO) and ERM will converge to around 0.06 when the training stops, while for the polynomially-taile growing, which
However,
loss, the norm will be larger than 0.22 and will keep shows that for the polynomially-taiee do not converge to the same point.
loss the normalized model weights
For either loss, the group weights of Group DRO still empirically satisfy Assumption
D PROOFS
In this paper, for any matrix A, we will use ||A]]2 to denote its spectral norm and || e to denote its Frobenius norm.
16

---

Published as a conference paper at ICLR 2023
D.1 BACKGROUND ON SMOOTHNESS
first-order differentiable function / over D is called L-smooth for L > Of
f(y) - f(x) (Vf(x), - x) + 1 x12
Va, y E D
(21)
which is also called the upper quadratic bound. If f is second-order differentiable and is a convex set, then f is L-smooth is equivalent
{(x) v|ll|2 1, Vo E D
(22)
classical result convex optimization the following:
Theorem 10. If (x) is convex and L-smooth with a unique finite minimizer x", and is minimized
by gradient descent D++1 = 1/V f(x)) starting from to where the learning rate 1j S T. then we have
f(xT) S f(x'
200 x= x²1
(23)
1/T
which also implies that ær converges x² T - cc.
D.2 PROOFS FOR SUBSECTION
D.2.1 PROOF OF THEOREM II
Using the key intuition, the weight update rule 7 implies that ((++1) g(t)) span ... .x for all which further implies that ((t) g10) s Fn for all By Cramer's rule, in this n-dimensional subspace there exists one and only one l" such that 0- g(0) e spanf 2n and (0", ()) for all i. Then we have
x T (0(+) 00) |1,
(X g(0) 0x -111 s xT000 -11,+
|
0(1)
+ x
111 0
(24)
because | 8- 9-Y B-Y (f 0)). On the other hand, let min be the smallest singular value of X. Since is full-rank, gmin > O, and X (0(1) 0" 101 2 g ||0(0) 0=112 This shows
that ||0(0 0-1) 0. Thus, ((*) converges to this unique l*
D.2.2 PROOF OF THEOREM 2
To help readers understand the proof more easily, we will first prove the result for static GRW
where q; (9) = for all f, and then we will prove the result for dynamic GRW that satisfy qi - q as t co.
(t)
Static GRW. We first prove the result for all static GRW such that min, 9 q" > 0.
We will use smoothness introduce in Appendix D.1 Denote A = Σm= || 1| The empirical risk of the linear model f(x) (0, x) is
n
F(0) Σ
a (x y1)
(25)
whose Hessian
Vir(0)) 2 Σ g:00.00
(26)
So for any unit vector v E Rd, we have (since E [0, 1))
V=F(0)== Σ (x) v)2
< 2 >
q:
22 < 2A
(27)
i=1
17

---

Published as a conference paper at ICLR 2023
which implies that F()) is 2m-smooth. Thus, we have the following upper quadratic bound: for any 81,05 02 E R..
F(02)= - F(01) + (VoF(01), 01) + 1 - 01112
(28)
Denote )(f(t)) (X ((A) - Y) R". We can that [[Qg )|2 F F(B(1)), where where vQ = diag(v/n. V Thus, VF((()) = 2xQ)( The update rule static GRW
with gradient descent and the squared loss is:
0(++1) = 0(0)
Σ
g -y)) y-) 0 11.Xx1QQ Qg(0(())
(29)
Substituting 01 and 0g in 28 with g(a) and g(++1) yields
F(0(++1)) s F(O())) ) T TQ= x xQg(0 A = 10
(30)
linearly independent, X X is a positive definite matrix. Denote the smallest eigenvalue of X X by A Amin > O. And [|Qg(0())122 Z v (1g(0()) / F((t)), so have )(((0) T Q X (Qg(o()) 2 o² A F(O(0). Thus,
; Fn Since .....
2n9 A F(O(0)) An2 < F(B(0) F(g((+1))
x XVQ
S F((D 2n7 X min F(O(1)) )+ + An²
x XQ F(O()
(31)
S F()(9) 2njy" X min F(((()) + Ar2
XI] F(O(1))
(1 2nq Amin + A7'12)
Amin A For any 17 S No. we have F(g(t+1)) I (1- 77 min ((B()) for all t, which implies that lim F(B(0) = 0. This implies that the empirical training risk must converge to O.
Let 170
Dynamic GRW. Now we prove the result for all dynamic GRW satisfying Assumption | Assumption for any > 0, there exists b, such that for all i 2 l, and all i,
By
q: E (g. - E, + +
(32)
This is because for all i, there exists t, such that for all t 2 t,, (1) E (q. - c, + E). Then, we can
define t, = max(t), J. Denote the largest and smallest eigenvalues of X X by A m and
Amin and because X is full-rank, we have min 0. Define min 4- (q" Aminya }. and then t,
is also fixed.
We still denote Q diag(?), ............ (n). When & 2 le, the update rule of a dynamic GRW with gradient descent and the squared loss is:
g(++1) g x g(t) Y)
(33)
where Q!"h = Q(t), and we use the subscript e to indicate that Q -Q
(1)
@111 <. Then, note that we
can rewrite Q! as Q! V
Q 3c VQ as long as S 9 /3. This is because qi + S V(a. + +eegq
and 9; - 2 V(g. 3e)q, for all S 9:/3, and qi 2 n Thus, we have
0(++1) = 0(0) n
3e V QQ((()) where Q!"h = V@@ .QQ
(34)
Again, substituting 0, and Og in 28 with ((t) and (++1)) yields
/ 11) (0())) + +A +a/l1x V
F(1(+)))) < F(009) 2ng(
x
(35)
18

---

Published as a conference paper at ICLR 2023
Then, note that
-Qoh-va v vQg(oro)
0(010) x
Q x x (VO00 - v@)
| Qg((ctt)
2
(36)
<
X T x11 212
t0
o@
| 29 1
2
<S max ((())
where the last step comes from the following fact: for all E < 9:/3,
v 4: + 36 V S V3e and vi V 36 S v3c
(37)
And as proved before, we also have
s(0(0) T x (Qg()())) 2 (0Am1FF(((0))
(38)
(0 Xmima 1 we have
Since c <
( x x V 2 Qg(((()) 2 (000(((1000 (g-mmin - \max v30) F(B(1))
2 1 -/aa min p(Bl0) (39)
Thus,
F(0(+22) < F()(0) "1'" A min Amim)()(()) + An² x @
g6 0000
(40)
< (1 17 X min + 21 (((()
$ (1 - nq x min + )
for all 6 < 1/3. Let 1/0 = 4A- For any 1 S To. we have F(B(t+1)) < (1 - (2)
5'Am'
for all L 2 4, which implies that lim F()())) = 0. Thus, the empirical training risk converges to O.
D.3 PROOFS FOR SUBSECTION 4.2
D.3.1 PROOF OF LEMMA
Note that the first / 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 11 (Proposition in Jacot et al. (018)). If is Lipschitz and di - oo for 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:
E'( 1
x:
x + 32
dn
(41)
x'xxxx')= = [o (x (x)) (f(2'))+++ 32
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
① = = ([)=)) 8
(42)
Consider the output layer h L+1 the output layer,
Wr
Va (hh) + Sb" We can see that for any parameter 8, before
WL. Vd.. Vo = 0
V 1+1 = diag(o
(43)
19

---

Published as a conference paper at ICLR 2023
And for W and b", we have
V Wirh 1+1 1
Vdl. o
ohh")
and
Voch
(44)
Then we can achieve (42) by the law of large numbers.
D.3.2 PROOF OF LEMMA 5
We will use the following short-han in the proof:
g( = f() Y
J(0(0)) = Vof(X; ((0)) E 12x=
(45)
( -(((()) T(((())
For any 6 >> 0, there exists t. such that for all 2 t. and all i, di (q. E, 9: + E). Like what we have done (34), we can rewrite Q(1) Q! o Q, where Q diag(0: ( ... In).
The update rule of GRW with gradient descent and the squared loss for the wide neural network is:
((++1) = o00) - - g(0())
(46)
and for t 2 fc, it can be rewritten as
0(++1) = 0 - ( [Vocooos)]
(47)
First, will prove the following theorem:
Theorem 12. There exist constants M > and 6n > such that for all E (0, 60). n of" and
any 8 > O, there exist Rg > 0, ò > and B 1 such that for any d > D the following (i) and (ii) hold with probability at least 5) over random initialization when applying gradient descent with learning rate np.
(i) For all S Le, there is
|0(000)) < BBRoo
(48)
2
MB Ro
Σ (0()) -0(5-1)|
S SMMRi Ro Σ B
(49)
B-1
j=1
(ii) For all 2 ter we have
| @gooor) 1011111100 179 A t-t,
B
(50)
(1-
174" miin j-t.
(06) - 0
< / 3rM Ro
Σ
(1-
3
+1
jot+l
(51)
3 3 3cM Ro
9" Amin
Proof. The proof is based on the following lemma:
Lemma 13 (Local Lipschitzness of the Jacobian). Under Assumption 2 there is constant M
such that for any Co 0 and any 5 > 0, there exists D) such that: d 2 D) then with probability
20

---

Published as a conference paper at ICLR 2023
at least (1 5) over random initialization, for any such that | S 1.
Vo Vol(<;;) -o 0/11 -
M
0
0
Vd
Vo/(ar; 0)122 - M
v0,0 B(8 Co)
(52)
||(0 - (10)) P - Vd
M
0
|1(0)) S M
where B(0(0), Rt) = 10: - 110- 1000 < RJ.
The proof of this lemma can be found in Appendix D.3.3 Note that for any æ. (() 3b where bc is sampled from the standard Gaussian distribution. Thus, for any d > 0, there exists constant Rg such that with probability least (1 6/3) over random initialization,
|11000) ||g <
Ro
(53)
And by Proposition there exists D2 2 0 such that for any 2 D2. with probability at least (1 5/3).
q" A min
e (
(54)
3
Let M be the constant in Lemma
13 Let co
(4" X
Let B 1y and C. M MB + B-1
108M
3 3*I+3eB' Ro, By Lemma 13 there exists D1 > such that with probability at least (1 8/3),
q Qmmm
for any d> D1. 52 true for all 0,0 B(0 Co).
By union bound, with probability at least (1 8). 52 53 and 54 are all true. Now we assume
that all of them are true, and prove (48) and (49) by induction. (48) IS true for due to (53), and 49 is always true for / = 0. Suppose
48 and (49 are true for l, then for /. we have
|oactt) g(0) ||g - 17 T( q |00000
1/1 s $011000000)) 9
|00000111
(55)
s n | ||p
|o(orc))1 I MMB'B. Ro
So 49 is also true for t + And we also have
(((()+)))
0(0(e+1)) g(0(0)) + 0(010)11
2
T( - ((0) + ((0(0))
n msiio ((00))
(o00)) + (((
100 66 (0000)
< I
(56)
$ 1 + cu (on0i
1.) |600111
< 1 + ((
| |
< (1 (1+ M²) |
- BC+1 Ro
Therefore, (8 and (9) are true for all t < fc, which implies that || (g((((t))) >|1 S ||((0(()))| <
Bt Ro. 50 is true for t.. And (51) is obviously true for t t.. Now, let prove (ii) by
induction. Note that when 2 t,, we have the alternative update rule 447 If (50) and (5T) are true for i, then for + 1, there is
21

---

Published as a conference paper at ICLR 2023
-000 sn [000:__s[[0000 =1111000//
| | s =1|1000)//
|ve
112
179" Amin
tnte
23 S In 3e | (0000
S SMMI++ 3e
B²r Ro
F
3
(57)
So 51 is true for t + 1. And we also have
(Qg(o(et1))
-
QJ(01O) -(0) + + @Q((O1))
" ( g((())) veg(0
(58)
< ny / Q1(((1))))
o @ 1/12
3c
I ny / (((1)) J(O(1)) (((())))))))))))))))))))))))))
V @!!0
1
n7 Amin
Ro
where (11) is some linear interpolation between ((1) and ((++1), Now we prove that
I I-NQJJ0eSTT00 _ S n A Ain
(59)
3
For any unit vector v E IR", we have
v. (I n. R0//Q//Q10 1- 1o0 -0 VQe/Qu
(60)
||vQul12 E IV 1]. so for any 7 S n u (I (I=n/Qe/)) E (0, 1 (a) which implies
that I NQQO@Q/ - 1 -11nd mmming q² Thus,
I - nV (C T ((0())) Q
< T/ Q 1 + 1 ((0) 10
2 +
((00o -1(00) ((000)0000)))0)
2
<1 "nmrrr q- + 1) /Q o (0oe VQ +n | (Q([(0))) (( (( ((
<1 amtin 9² + 17 - 610/ ||, + T - ((01)) |(00)) -
n7 A min
n1
(1000) -000
/ 11, + 000) 9(0) 000),) s
179" X min
<1 nm
Vd
2
(61)
for all d max
Dr, D2,
12M*c, q- Ami
1) )d).
which implies that
I- (J(Vu) T( /
<1 n/ min
1/ Q ((Oro))
(VQS
(1) - vQ)
(62)
<1 17" > min
ng Amin
2 m/2 < 11-
(due to 37
3
for all cp. Thus, 50) is also true for t + 1. In conclusion,
50
and
51 true with probability
at least (1 - 5) for all d 2 ò = max {
C2M'Co Aumm
D1, D2,
22

---

Published as a conference paper at ICLR 2023
Returning back the proof of Lemma 5
Choose and fix such that
q"Amin min(fo: (Amas+q A Amii
}. where eo defined by Theorem 12 Then, le also fixed. There
exists D 2 0 such that for any d 2 D, with probability at least (1 6). Theorem 12 and Lemma 13
are true and
||0 0 /
q Amin
(63)
3
which immediately implies that
max q'Amin
| | - 110112 + 1- 9100
(64)
3
We still denote B = =1+ 1 2 and Co
MB Ra B-1
3/1+36MB's An Theorem
12 ensures that for
9"' Xmmi
all t, git) E BB000), Co). Then we have
1- 1- v - ||r - [ + +1
(65)
170" A
2n1g" Amin
< 1 17d min q"
3
so it follows that
|/Q0000 (Vo%²
( - -V2)
I - n/ nVQQ
(t)
< I nI Q0 (0) VQ +
(66)
2n1 X X
a*Amin
3e
3
Thus, for all 6 <
q" Amniu
there is
3xmax + Xmi
77 Amin
I- 1- Q0 (0)
(t)
< 1
(67)
2
The update rule of the GRW for the linearized neural network is:
(1+1) = 0 LH ()(0) Q(()) (0(1))
(68)
lin
where we use the subscript "lin" to denote the linearized neural network, and with a slight abuse of notion denote Gun (f(1)) (.)
First, let us consider the training data X. Denote A, -iin((()) - -((())). We have
9tm 9um (((t+))) 9tm (b(1)) ( T (( )Q (((()
(69)
g(0(+2))) g((()) = ( ((OCe)) g((()))
where g(1) is some linear interpolation between ((+) and 1(++1) Thus.
A - A. = [ ((((0) - )( )(o(o)) g((((()))
(70)
(( ((11))
By Lemma
13
we have
(100))T(000) - (((()) ](ooo)
(J(0L) -(00)))-(00)) T 2(010/ ( (J(0()) -(0
(71)
<2M22o0
23

---

Published as a conference paper at ICLR 2023
which implies that for all t < <tc,
|1441ll2 - - (
10112 + 1|1 [( J( (1000))-((00)) )( ((000s] 900 (0000 (000)))
||Alll2 + + [ - ((000) J (000) || (0000)
< - T Q
F
(1 + M || + My CoB'Rad Rod-1/4
< B 1 + M B² Rnd
(72)
Therefore, we have
B (--1- ||,,-112 S B S + C
(73)
Since Ao 0, it follows that for all l Lo.
| S Bo
(74)
and particularly we have
Vosu S 1l1,,112 S 2t. Rod 1/4
(75)
For 2 le we have the alternative update rule (47 Thus,
QQA+1--QA - =
J( ((0 - ((0(0) T s(O(0)) VQ! ( [vQg(o(tt)
(76)
-1 T
( 3c
[QQA
Let A I // (Q
Q0000 II n/Q0 AA +1
(c)
Then, we have
((0(0)) ((((o) - -(0(0)) J s (1)0) Vo!2 (veg(on)) (77)
V QQ = QA
Let = 1 no umin
1. Combining with Theorem 12 and 67 the above leads to
|/ |
-1 $|A 2
Q
2 + +1 V@ (( T(B(()) - -(B(o)) T ]]
(
|| (Qocoro)
3c
5> QA,
+ -100) J(((0) - ((0(0)) ]/ v1 + 30y t, B² Ro
<> QQ
Bt Rnd
(78)
This implies that -(++1 (QAai ST / + 2 Bdx Rod
(79)
Combining with (75). it implies that for all t 2 ter
||@a, 1|2 s 2n
B Ro [- + /1 3ey -e 1.5-t,) tc)] d
(80)
Next, we consider an arbitrary test point x such that || S 1. Denote &, flm (x) Then we have
(1)
f(1)
Aim (()+)(())= - (x) = Vof 011)) (B(t)) Q (1) g(((1))
((+1)( (x) 1 (x) (2; ((00)) Qt gin (o(t))
(())))
(81)
which yields
844 8c =n Vof T(0)))(((1)) Vef (01)) [( a0 g
(82)
Vef 0(0)) ((0 ( Q(1) A,
24

---

Published as a conference paper at ICLR 2023
Fort t S te, we have
Vos (2; (60))) (os ) -( 1l00e |(c0oa1
| Sn
Vot [of(=; )(((0)))()) |اممl2
V Vaf(x; )(06)) ((0)) (((0)) |/ |
(83)
Vo (ar; (ar 1000 ](000) 1|
1-1 Σ R + n
f-1
22M 1/4
Σ
C 1/2)
So we can see that there exists a constant C₁ such that || 112 S Cjd-1/4,
1/4, Then, for / > le we have
||be|l2 - 16 51
Σ
- - [ v V (+)
V
(og(8())) /
1=
[of(a; T -
|QA.
+ 17
t-1
2MnM Cod 1/4 VI 3E
Σ y--
Br Ro
szt.
m1 VT 38
2 M B* Ro [L,B- + v1 + 3ey (ss -t,] d-1/4)
1/4)
(84)
Note that Ei by finite as long as 7 E 1). Therefore, there is constant C' such that for any t, 116ell2 < Cd 1/4 with probability at least (1 5) for any > D.
D.3.3 PROOF OF LEMMA
We will use the following theorem regarding the eigenvalues of random Gaussian matrices:
Theorem 14 (Corollary 5.35 in Vershynin 2010)). If A Rpxq is a random matrix whose entries are independent standard normal random variables, then for every t 2 0, with probability at least
1 2 exp(-tt) (2),
VP V- t min (A) S mAx (A) S vP+ V +
(85)
By this theorem, and also note that W is a vector, we can see that for any 6, there exist D > 0 and Mj > 0 such that if d 2 D, then with probability at least (1 - 6), for all E B(8 Co). we have
|| < 3vV (vO 1 and
| s C. c 33Va
(86)
well
||ab||| S Mi Vivá (MI=0, ,,....
(87)
25

---

Published as a conference paper at ICLR 2023
Now assume that (86) and (87 are true. Then, for any such that |||||| S 1,
112
1
W x + 36"
1
|
||0||| + ||3b0|
11 ( + Mi) Mi)VV
3
ddo
vdo
Vdo
2
|
W'' + -336
1| |<||| 112 + || 1| (4
(88)
vd d
Vd
|
112
|1a(hh) - (00) + +
- Lo
| +
(M21)
where La is the Lipschitz constant of a and (00) = (o(()), (O)),,,),,0()))) E R By induction, there exists an M2 > 0 such that ||a0||2 S M2 d and || |b' 11 S M2 d for all I = 1, L.
Denote a' = Vnif(x) = ht1. For all / 1, L. we have a' = diag(o(h')) WiT +1
Vi
where (xx) S Lo for all x R since Lu-Lipschitz T 1 and ||a"|2
diag(ò )h²)) WhT
S
3 Lo- Then, we can easily prove by induction that there exists an
Vd
Vd"
2
Ms > 1 such that because a L++ = 1).
|a'||2 s Ms/ Vā for all l = 1,... L (note that this is not true for L + 1
For l = 0, f(o)
va, V x IT, so (wif(e)ll2 S Ja |000 2 a
11
S
1 M2/ Vd. And
for any 1 = 1, ... L, fwi((x = 1 J
a'altl, +1 so ff))l2 S V ||
112 a 4+1 1| S M2
Vd
(Note that if M3 > 1, then | || I M3; and since d 2 1, there is ||a'||2 S M2 for 1 < L.) Moreover, for 1 = 0, ... L, Vo fax) = Bal+1, so
S BM3. Thus, if (86) and 87 are
true, then there exists an M4 > 0, such that [oof(l) S Ma/Vn. And since ||>:l|2 S 1 for all i, so | I M1
Next, we consider the difference in (of between 0 and 0. Let f, W. b, ã. h ā be the function and the values corresponding to 0. There is
122
h
1
(Wo_
-w0 + +,3(6- -80)
v
do
1
WO
/. ||00||2 + 1000 80 5 (v/
Ciyy +13 100 0
0-00
v
d
h141
1
Wl
(so'
-x') +
1
(W
Wh + 3(b'= か²)
2
Vd
Vd
(89)
<
1
111
|0' x 112 + Vd
W w. 2 | + 1 |6'
Vā
< 3 ||o'
|||
+ (M2 + (3)
0-000
0
1
||' - t'112- ((hh)) -o o
< Lo |/' - -h'11
1
By induction, there exists an M3 such that ||a' - 2²1122 s M3 10
0
for all
26

---

Published as a conference paper at ICLR 2023
For a', we have a f+t = = 1, and for all / 2 1,
WiT
WIT
||a á') 12
diag(
a diag(d(h'))
à'+1
Vd
vd
2
WiT
(W' WOT
x (ia)(
(a
+1 )
+
(oag()())))
141
Vd
Va
1
WiT
diag ( - -((h))))
1+1
Vd
s 3L0 ||||t - 2l2 + (MaLod + 3.MgM |10 -
(90)
where L1 is the Lipschitz constant of c. Particularly, for | L, though ā 1++ = 1, since
W
5
// (90) is still true. By induction, there exists an Mg > 0 such that ||o ā') S
Mr
0
Va
for all 2 (note that this is also true for 1 = I. + 1). Thus, (6) and (87 are true, then for all 0, E B(O Co), any æ such that ||0||| S 1, we have
Vwo f(x) V [w)
IT
1T
dg
S
|a
ā
(91)
dd
Ms
0 0
v
do
Vd
and for 1 -,... L, we have
[w: - V F())
Vd | - +'a'411
(1121 ||a -2/+1/1 + +|/22 T
| 12)
(92)
M2 Vd +
MsMaa vd
||000|
Moreover, for any 1= 0.-... there is
Vv(((x) - V V (xx) 11 =
|||ltt1 a't1/12 112 <
3Mc
|0 0
(93)
Vd
Overall, that there exists constant M7 > 0 such that |oo)(a)) - vol(w)
Vn- Va 00 0 so that ||0] 1(0)- J
<
Mr Vd
0 0
D.3.4 PROOF OF THEOREM 4
First of all, for linearized neural network 11). if view of (x.) as the inputs and (y: (00 (xx) ) + (0(%), (o) (xx))) as the targets, then the model becomes linear model. So by Theorem 2 we have the following corollary:
Corollary 15. If (0) such that for any GRW satisfying Assumption and any S 7h- g() converges to the same interpolator 0r that does not depend qc.
(o (x,,) are linearly independent, then there exists too >
27

---

Published as a conference paper at ICLR 2023
Let 7)1 min 77", where To is defined in Corollary 15 and 1f" is defined in Lemma Let
e(tt) ( (x) and (it) (x) the linearized neural networks of (()(()) and (x)) respectively. By
Lemma 5 for any ö > 0, there exists D and constant C such that
lin (x)) (1) I Cd-11/4
sup
t20
(94)
((t) (I)ERM(x)) SERMN( S Cd-1/4 1/4
sup r20
By Corollary 15
we have
lim
(x) f
finERM (2)) =0
(95)
Summing the above yields
lim sup (() - p(() FERM(() S 220d11/1
(96)
t1+0
which is the result we want.
D.4 PROOFS FOR SUBSECTION 4.3
D.4.1 A NEW APPROXIMATION THEOREM
Lemma 16 (Approximation Theorem for Regularized GRW). For a wide fully-connected neural network S, denote ((0 (of(X;0) 0) Rpx= and g(0) Vge(J(X; ;),), Y) E RR. Given that the loss function E satisfies: Vog(O) = J(O)U(0) for any 0, and (0) is a positive semi-definite diagonal matrix whose elements are uniformly bounded, we have: for any GRW that minimizes the regularized weighted empirical risk (13) with a sufficiently small learning rate T, there is: for sufficiently large d, with high probability over random initialization, on any test point x such that |
sup Finio (x) (x) S Cd-1/4 t00
(97)
(10) where both Jinneg and freg are trained by the same regularized GRW and start from the same initial point.
First of all, with some simple linear algebra analysis, we can prove the following proposition:
Proposition 17. For any positive definite symmetric matrix H E Raxn, denote its largest and smallest eigenvalues by max and minn Then, for any positive semi-definite diagonal matrix Q diag(q (oog(41.... .n.). HQ has eigenvalues that all lie in min; % m max; 9: Amax
Proof. H is positive definite symmetric matrix, so there exists A E Rax such that H = AT A, also an eigenvalue of A AQ, because for any eigenvalue À of AQA we have some * 0 such that AQA Xv. Multiplying both sides by A on the left yields A AQ(ATA v) = A(A v) which implies that À is also an eigenvalue of A AQ because A" + 0 as Xu + 0.
and is full-rank. First, any cigenvalue of AQAT
Second, by condition we know that the eigenvalues of A A are all in [xmin _=mx] where min > 0, which implies for any unit vector v, v. A Av [Amin X X which is equivalent to || [VAmin, Amaax. Thus, we have v A A TTQu E [Amin min; qs A max max; qı). which implies that the eigenvalues of A QA are all in [ min; qi, X max max; qil-
Thus, the eigenvalues of HQ = A AQ are all in [Amin min; qs A max max, qıl.
By the condition & satisfies, without loss of generality, assume that the ele- ments of (()) are in [0, 1] for all 0. Then, let n < (p + X min + Amax)-! (If the elements of U()) are bounded by [0, CJ. then we can let I (μ C' min + C and prove the result in the same way.)
Proof of Lemma 16
28

---

Published as a conference paper at ICLR 2023
With La penalty, the update rule of the GRW for the neural network is:
g(++1) (( (())
m)((()) )(0))
(98)
And the update rule for the linearized neural network is: f - T) Q g( m )
(
(99)
By Proposition
11 f(= 0) converges probability to zero-meat Gaussian process. Thus, for any
5 > 0, there exists a constant Rg > 0 such that with probability at least (1 - 6/3), ( 112 < Ro-
Let M be as defined in Lemma 13 Denote A = ryM Ro, and let Co 44 in Lemma
13 By Lemma
ays
13 there exists Dj such that for all > D1, with probability at least (1 - 5/3). (52) is true.
Similar to the proof of Proposition 17 we can show that for arbitrary 0, all non-zero eigenval-
ues of (((()) ) (0) are eigenvalues of J ( Q (T)). This is because for any À * O, if J(o )( (())()))
= An, then J( J(O QQ (()00)
)(J(O()) v). and )(0()) To * 0 since Au + 0. so À is also an eigenvalue of J )( (((())) (00)). On the other hand, by Proposition 3 ((
(( ((00))) con-
verges in probability (()) whose eigenvalues are all in [0, Amaa] by Proposition 17 So there exists D2 such that for all d 2 D2, with probability at least (1 8/3), the eigenvalues of (( Q (() are all in [0, Amax + A Amin] for all
By union bound, with probability at least (1 - 5). all three above are true, which we will assume in the rest of this proof.
First, we need to prove that there exists Do such that for all d 2 Do. supr2o ||00) Ø(0) |12 is
bounded with high probability. Denote = (()) - 8()) By 98) we have
a++1 =(1 mu)ar T)(((()) -((()) )Q (+) g(0())
(100)
(0(0) QQ 10 (g(0()) ((0(0)) 15(000) ) g(0
which implies
|attilla S (1 (1-1) --nii T Q (1) 2 ( ||ell2
(101)
-((B | ||| + ||
|
+n
where ((9) is some linear interpolation between 01 and ((0), Our choice of v ensures that mn < 1. Now we prove by induction that ||ae|l2 < Co It is true for = O, so we need to prove that if ||aell2 < Co. then ||a,+1|| < Co.
For the first term the right-hand side of (101, we have (1 mn) - 10
<(1 - mmu) I 1 1 1-n
" J( ((()) J(B()))
+ | | | -(
(102)
Since n/(1- 10m-mp m/4) S (Amin Xmax)-1 by our choice of 17, have
I
[( Q (0 (((0)) I((())
1
(103)
2
On the other hand, can use
52 since ||arll2 Co. so || -
((8(0))
2² Co- Therefore, there exists D3 such that for all 2 D3. Vā
(0-m))1- - ( 100
<
np 2
(104)
6 'Noe that Lemma 13 only depends on the network structure and does not depend on the update rule, so we use this lemma here.
29

---

Published as a conference paper at ICLR 2023
For the second term, we have
| |11010) -9(00))) 111 |
(105)
| [ ((((0) 111 000) (10)
Ro MCD Ra
And for the third term, have
" | |1(00))1| < <nMRo
(106)
Thus, we have
|| 11 - (1-
/ 2
nM(M + Ro)
|aell2 +
+
(107)
Vd
So there exists D1 such that for all 2 D4, ||u+1lll - (1 ) ||0112 + 2A. This shows that ||ae|12 2 < Co is true, then ||a+tll2 Co will also be true.
In conclusion, for all d 2 Do max D2, D3, Da}. ||0(0)00000) -100 C. is true for all This also implies that for C = MC + Ro, we have [g(((()) ||| S C1 for all by (055. Similarly, we
can prove that [ - 0(00 1|2 < Co for all t.
Second, let A, = g(t) Then we have
A A. 7(J((()) QQ g(0 - g(( vA,)
(108)
which implies
A.11 = -10000--10000 ((((O)) A. + (()((())))))))) (( 1) g((())
(109)
where g()) is some linear interpolation between 800) and 0 By 104 (1 - 5) for all d Do. we have
with probability at least
|At11l S (1- I- - ( QQ 1010(10))))0000 |Arll2 + || - -(OOU)) (0(000)
$ (11-2) 2 || + " M
TH44
CoC
(110)
Again, as Ag 0, we can prove by induction that for all f,
2MC0C1 1/1
|Arl12
(111)
/
For any test point such that ||0:|| S 1, we have
((t) (x) ((())
(x)
f(x; 000) - fin(x; o
f(x; 0(0) - fun (x; g(0))
+ fun (2; 0(1)) - fin(a:; (
(112)
[wx 010) - Ain (2;; 01013
+ Vos(a; 0101) /11 |C0) - -
1000000-0000
(xx 0(0) - fin o(1)))
+ M ||ell2
For the first term, note that
{
f(x; Sin(ar; ((0)) - fim (z: g(0))
f(z;0())) o(t))
- f(x; ((0)) Vef(æ; o()) (0(0) ((0))
(113)
= Vof /10) (g(()) B(0))
30

---

Published as a conference paper at ICLR 2023
where ((t) is some linear interpolation between ((+) and (10) Since f(:; ((x:((0)) = =fin (x; 8(0))
[(x; 010) fin (z;; 060) = Vol(x;00)) Vaf(æ; 010) || |00) - 0(0) 11
M
c
(114)
d
Thus, we have shown that for all d Do. with probability least - 6) for all and all m
flince (x)) - *AIC3+ + 2M0C 8-1/4 - 0
reg
(x)
(115)
which is the result we need.
D.4.2 RESULT FOR LINEARIZED NEURAL NETWORKS
Lemma 18. Suppose there exists Mo > O such that || (x) I Mo for all test point æ. Ife gradients (o (x)).... " ( (I) are linearly independent, and the empirical training risk of Sineg satisfies
lim lumsup R(Jinnee) <E, t0:00
(116)
for some c > 0, then for x. such that ||2:|22 S 1 we have
Slinee (x)) ( O((e). (
lim lim
(117)
t b-oa
First, we can see
that under the new weight update rule, g(0) g(0)
span Vo ( (21), ... (of (.,)) is still true for all Let be the interpolator in span Vof (x1). Vof (In)), then the empirical risk of is 2n Σi= (6
8", of (0(())))))) (x:))² 2n Vol (0) (X)T(0 10) Thus, there exists T > such that for any 2 T,
(x) ( (000) - 00) 2ne
(118)
Let the smallest singular value of
Vn (o) (X) be gmin and we have g O. Note that the
column space of ( (X) exactly span V s f f (æ1)..... of (x,)). Define
Rxxx
such that its columns form an orthonormal basis of this subspace, then there exists G E πunx such that oo (X) = HG, and the smallest singular value of G is also s Since g(t) ((0) va
is also in this subspace, there exists v R" such that ((t) 0- = Hv. Then we have v 2nc 2
G H Hollz - G |Tuulll Thus, || S
v2c gmin
which implies
/2e
(00) 0r
(119)
min
We have already proved in previous results that if we minimize the unregularized risk with ERM, then 0 always converges to the interpolator 0". So for any > T and any test point such that ||ا||| $ 1, we have
Mo 2c
(1) (a:)
p()) [inERM (a)) = (((()) 0", (0) S
(120)
smin
which implies 117
D.4.3 PROOF OF THEOREM 6
Given that R² (( < for sufficiently large f, Lemma 16 implies that
R$ R((l( R = o/
(121)
31

---

Published as a conference paper at ICLR 2023
So for fixed there exists D > O such that for all d 2 D, for sufficiently large
R(S < = RR < 2c
(122)
By Lemma and Lemma
16
we have
(() linERM (x) - - (x) = =O(d 1/4)
sup
r20
(123)
linreg (x) - S/l =O
sup 120
Combining Lemma 18 with (23 derives
lim sup
fig (x))
S (RMM = - 1/4 Vt)
(124)
t-000
Letting d + 2o leads to the result need.
Remark. One might wonder whether (x=)l2 will diverge as d + In fact, in Lemma 13 we have proved that there exists a constant M such that with high probability, for any à there is of (f))) M for any æ such that ||>||2 S 1. Therefore, it is fine to suppose that there exists
such an Mo-
D.5 PROOFS FOR SUBSECTION 5.1
D.5.1 PROOF OF THEOREM 7
First we need to show that @NM is unique. Suppose both 0, and 02 maximize min;- . yi
as) and 0, + 02. ||0, [|2 = 02112 = 1. Then consider On 0/1|0||2 where 0 = (0) + /2) Obviously, ||0||2 < 1, and for any i, yt (0, xx)) = (y:- (0,, vz) + y: (02, x22) so y: (0,, xz. >
min(3 2.), y1 (02, x.)) }. which implies that min V4 (0o. x.) min m Vo
(01, x.), min, 8/ (02, }.)). contradiction!
Now start proving the result. Without loss of generality, let (x1, v1), (mm, Bmm) be the sam- ples with the smallest margin to u, i.e.
arg min yi (u, æ.)) = {1, , , 1si5n
(125)
Um (u, Rm) Yu. Since the training error converges O, Tu > O. Note that for the logistic loss, if y (0, xx) < yj (0, æz), then for any M >> 0, there exists
And denote V/1 - (u, 21)
an Rai > such that for all R 2 RM.
V VoL((RO, xz), v1) V VoE((RO, az), Ug)
M
(126)
which can be shown with some simple calculation. And because the training error converges to O, we must have ||o|o||| + oo. Then, by Assumption 3 this means that when & gets sufficiently large, the impact of (z,, U/) to g(() where j > m is an infinitesimal compared to (æx, y/) where i I m (because there exists positive constant such that 9; (1) > for all sufficiently large by Assumption 3. Thus, we must have u E span( --. }m
Let u a1y1 21 +... Omdynmm Now we show that a; 0 for all i i= 1,... m. This is because when / is sufficiently large such that the impact of (æt),y;) to ((0) where j > m becomes infinitesimal, we have
g((+1) g(t) n 9i exp(y: (0(t), mz))
exply: (0(1) xx,) y:
(127)
and since ||e(t]]| + oc as t + oc, we have
T 80 exp(y: (0(t), (g(t),,))) lim a;(T)
a4 T
lim
(128)
1 exp(y) (8(1), xx)) T-000
32

---

Published as a conference paper at ICLR 2023
where To is sufficiently large. Here the notion a, o limp-+co a, (T(T) means that limy-sso 0.(7) ae for any pair of i and 0j # O. Note that each term the sum non-negative. This implies that ay
(y(T)
all on, 1 Om have the same sign (or equal to O). On the other hand,
Σ aaau
agys (u, (2e, u)
(129)
Thus, a₂ 2 for all and at least one of them is positive. Now suppose u o 0MM. which means that Th is smaller than the margin of fMM. Then, forall = 1, m, there is yo (u, mx) < ye ye mt)- This implies that
(u, u) = Σ a.l (u, xz) <
astli (BNNA x;) = (8MM. u)
(130)
which is contradiction. Thus, we must have 0MM-
D.5.2 PROOF OF THEOREM g
Denote the largest and smallest eigenvalues of X X by X and Amin, and by condition we have
Amin > 0. Let 6 = min { q (g" Ammn ym Then similar to the proof in Appendix D.2.2. there exists te
3 102A
such that for all 2 L. and all i, Ci
E (/
6 + <). Denote Q diag(n, ... .qa), then for all
t2 te. Q (t) Q! vQV Qee where we use the subscript to indicate that Q Q 2
First, we prove that F(0) is L-smooth long
|æ5l12 S for all i. The gradient of F is
VF(0) Σ a E((( a;), y/
(131)
Since E(g. y) is L-smooth in ÿ. we have for any 01, 02 and any i,
E((02, M)) (((1,, v1)
< Vgl((0),, 21), w/) (102, x;) - (0,, x;)) ) + _ (102, xzi) -001, xxi))
2
L ((02 - 01,x,))
(132)
= (V)E((0), (1)00,,,)),,))) De, 02 01) +
2
L
S (V AV 2.) wi, 02 01)
2 100 0, l1
Thus, have
F(12) F(01)
qi [1( 2.). w1) e((01, 2.),
L n
(V VV ((( x.)),:) ()) x; O2 - 01) +
Σ
a 1|0g
-0111
(133)
2
i=1
(VF(()) 02 - 01) + 2
1/0 - 0111
which implies that F(I) is L-smooth
Denote 5()) V V 0), E RR" then VF(O())) = XQT()()), and the update rule is
g(++l) = (()) - - g()())
(134)
So by the upper quadratic bound, we have
I
F(o(t-1) s F(O(1) n XQ" +
xQ x(0))(
(135)
2
33

---

Published as a conference paper at ICLR 2023
Let 771 2L 3-
9' A
Similar what we did in Appendix D.2.2 (Eqn. (4
we can prove that
for all 17 S 7/. 135
implies that for all 2 te. there is
F(D(+))) < F(O(0)
179" A
Amin
Qo(olo)
2
L²L
X V
(1) 3x
||
2
2
179 Amin S F(O())
|V
n²²L
|| 11 (1 3E)
Q2(000)
2
(136)
S F(((0)
77 A min
||Q
4 "n
22 xmin
|
S F(O(0)-
This shows that F((()) is monotonically non-increasing. Since F(0) 2 0, F(O(t)) must converge as - 0o, and we need to prove that it converges to O. Suppose that F(B()) does not converge to O, then there exists a constant C' > 0 such that F(O(1)) 2 2C' for all t. On the other hand, it is easy to see that there exists 0* such that {( xx4, y1) < C for all (136) also implies that ||(()()) -
as t + oo because we must have F(o(t)) F(o(++1)) +0. 0.
Note that from (34) we have
[oltt) 0r
1
2 = 0000
0-
1|
2 + 217 (((()((((())))))))))))))))))))) -0000))0---00)) -00) +1? xQ g(00)) (137)
||²
Denote
4 10 (e(((, vi) F((0)= Σ
(138)
Then Fe is convex because é is convex and q, are non non-negative, and FF(((())) = x((()((()))
By the lower linear bound F1(y) 2 (a( (V (z),, y x²), we have for all 1,
4C
(XQ g(o()) 0- - ((0) - ((())) - (((((() S Fr (0)) 3 =(O(t) S SC
(139)
=
3
3
because gf 2 q:- 2 3 and Σ (+) = 1. Since || ||2 + 0. there exists T > 0 such
(t)
that for all 2 T and all n) n/0.
| 0- 1| S (000) 0r 0-13- n
(140)
3
which means that |0000 0- 1|2 0o because DC 3 is a positive constant. This is a contradiction!
Thus, F(O(t)) must converge to O which is result (i).
(i) immediately implies (ii) because l is strictly decreasing to 0 by condition.
Now let's prove (iii). First of all, the uniqueness of 0g can be easily proved from the convexity of F(0). The condition implies that y R&, xx) > 0, i.e. 0g must classify all training samples correctly. If there are two different minimizers On and On in whose norm is at most R, then consider 0% (On 0zz)) By the convexity of F, we know that 0%2 must also be minimizer, and |10 < R.
Thus, F( | 1 0% < F(0%) and || 10 1/ R, which contradicts with the fact that 0% is a minimizer.
To prove the rest of (iii), the key consider 135 On one hand, similar to 36 we can prove that for all / > le, there is
X (((())))) X(Q ())()())) max /3e
V QQQ 0 g(00))
(141)
Since we choose min C. ig 2mina
1 }, this inequality implies that
XQQ (t) g(o(1>))
|2 2 min |0000000)) 12 A (g" xniin - (e Q0
pummx
\Q 2 4
2
(142)
34

---

Published as a conference paper at ICLR 2023
On the other hand, if S 7/2
21. we will have
2 x """
L
(143)
Combining all the above with (155) yields
F(B(+t)) - F(B(0)) - - 2 (B(())
2
(144)
Denote u lim
0g [a >> 0, there exists a constant p(a) > 0 such that for any 0 subject to |1012 2 p(a), there is
Similar to Lemma Ji et al. 2020 we can prove that: for any
Fr((1 - a (1012 = Eo(()
(145)
for any 1. Let la 2 le satisfy that for all 1. 2 lax |2 2 max() 1). By the convexity of Ft, for all 2 to.
(VF,(0())) 000) (1 + +=)00000))))) 2 F.(0(0) F1 + a)) 122) 2 0
(146)
Thus, we have
(0(++1) g(0), 2) = (-n) u)
,(0)
2 (-n)FF g(0)
(1 xx)
0 2
(147)
(0(++1) (()) )(
(+a)) aa)10(0) 2
{ 2
1 | |
|
[oc-1) - -000|(
=
2
2
2
(1 2ll8811)e
By 3 (1(0(+))))))
1122111-- (+) 122 2 2 0, we have
(1 ||o(--1
||0(o]]]] /1200001111 |
> =||oc+1>/| 1|
Moreover, by (144) we have
[|o(t+1)
g(0) 12 <
||0(t+]) ||0((t))800)(2 1
2
2 S (F(O(O) F(B((+1)))
(148)
2(1 + a)]l 1|
2
Summing up [17 from ta to we have
||000|| ||
|((taa]
1l2 +ny (F(0()))-F(81))))
[0(+)
2 ||0((t.)))
g(t)) u)
- F(B((t)))
F F(((t)))
+
1 1+a a
(149)
which implies that
|
000)
1
2
1 + a
1
[(()) 2
(Dlt)), u)
| 112
1 1+a
(o((t)))))
(150)
Since lim ||0(0) ||2 = 0o, we have
((t)
1
lim inf
2-000
|
u
2
1
a
(151)
Since a is arbitrary, we must have lim
g(0
u as long as 1 S min(m, 92).
Toco
|
D.5.3 COROLLARY OF THEOREM 8
We can show that for the logistic loss, it satisfies all conditions of Theorem 8 and lim 6n
y² âM.- First of all, for the logistic loss have Vi((ū.v) v) -w max; E is smooth.
35

---

Published as a conference paper at ICLR 2023
Then, prove that limg- 8s exists and is equal dNM- For the logistic loss, it is easy to show it that for any 0' + OMM. there exists an R(O")= > and an 8(0") > 0 such that F(R 0) > F(R MMM) for all R 2 R((") and 0 E B(0", 8(6').
Let 5 = {0= |10112 = 1}. For any > 0, S B(êMM: c) is compact set. And for any A e S B(fMM, <), there exist R(0) and 5(0) defined above. Thus, there must exist 01, Om
S B(@MM. c) such that S (BMMM c) - U. B(e,, 8(0,)). Let R(c) ma()))())..... R( }
then for all 2 R(e) and all E - B(MM. e), F(R- 0) > F(R OMM)), which means that Pg E B (f <) for all R 2 R(c). Therefore, lim f exists and is equal to 6MM-
Therefore, by Theorem 8 any GRW satisfying Assumption makes a linear model converge to the max-margin classifier under the logistic loss.
D.6 PROOF OF THEOREM 9
We first consider the regularized linearized neural network limeey Since by Proposition 11 ((0) (ar is sampled from a zero-mean Gaussian process, there exists a constant M > 0 such that f()) (xx;) < M for all i with high probability. Define
F(O)= = Σ 9: (0, (xx)) + ( (3x)).
(152)
Denote 0R- = m 8) |0012 < 1}. when the linearized neural network is trained by GRW satisfying Assumption with regularization, since this is convex optimization and the objective function is smooth, we can prove that with a sufficiently small learning rate, as & - oc, g(t) + R- On + ((0) where R = lim [|0(0) - 000) (which is the minimizer). And define
min Yi (OMM. vof (x:)) 7 i=
(153)
First, we derive the lower bound of R. By Theorem 16 with sufficiently large d, with high probability R(((g) < e cimplies R( < 2c. By the convexity e, we have
(-1 Σ
((R0R. ox)) + (() (c))))l)) )
(
2e
((RŌRR xτ) + f(() (xx)) v1) 2 log 1 + +xep
n
1=1
Σ R(ŌR. R,)8i M )
2 log
1 exp
(154)
which implies that R = 22 log 2c) for all E (0, }).
Denote 8 = || Let 0' = bnttun, then we can see that 10'1|2 = /1- S. Let
8'
101
By the definition of ÓwM. there exists j such that yj (0' ( (xz)) S which implies
0MM + 0R
8j
(x) S
(155)
2
6
Thus, we have
82
Vj (0. V (xx,)
S 2
1
yj (0MM. (2)(0(
4
82
2
?
4
(156)
82
1)
(since vI- S x )
2(1
82
(1
>
4
36

---

Published as a conference paper at ICLR 2023
On the other hand, we have
qj log(1 + exp(-y) Vj (R 12, (0,(0(2;))) - M)) s F(R Qn)
(157)
<F(R BNM) S log(1 + exp( -ey + M))
which implies that and this leads to which is equivalent to
q² log 1 [ (-11 4) Ry M )1 s log + exp(- + M))
82
(158)
[ Ry MM 3m 21 21+9 exp ((11
82
82
-x) 1 exp (-(1-
Ry M
4
4
(159)
8²
Rr + M -(1 x) RRy M log(a")
(160)
Thus, have
= O = O((-log 26)-113)
(161)
So for any test point since
S Mo. we have
K0 ( fof (z)) S 8M,
(162)
Combined with Theorem 16. have: with high probability,
lim sup [MM((x)) - (() (x)) = O(R (- log 26) d-1/4) 8- t-000
(163)
So there exists a constant C > 0 such that: As d - co, with high probability, for all c (0, 1) if [x)] > C 2o) then fig (a:) will have the same sign as fMM(2> for a sufficiently large t. Note that this C only depends n, q", % M and Mo. is constant independent of
Remark. Note that Theorem 9 requires Assumption while Theorem does not due to the fun- damental difference between the classification and regression. In regression the model converges to a finite point. However, classification, the training loss converging to zero implics that either (i) The direction of the weight is close to the max- margin classifier or (ii) The norm of the weight is very large. Assumption is used to eliminate the possibility of (ii). If the regularization parameter
is sufficiently large, then small empirical risk could imply small weight norm. However, in theorem we do not assume anything on μ,, so Assumption necessary.
E A NOTE ON THE PROOFS IN LEE ET AL. (0119)
We have mentioned that the proofs in Lee et al. 2019), particularly the proofs of their Theorem 2. and Lemma in their Appendix G, flawed. order to fix their proof, we change the network initialization to (9). In this section, we will demonstrate what goes wrong in the proofs in Lee et al. (2019) and how we manage to fix the proof. For clarity, we are referring the following version of the paper: https: arxiv. org/ hdtpppff/i/ 19922 06720v4 pdf
To avoid confusion, in this section we will still use the notations used in our paper.
E. THEIR PROBLEMS
Lee al. 2019) claimed in their Theorem 2.1 that under the conditions of our Lemma for any 5 > there exist Î > 0 and constant C such that for any d ' Î, with probability at least (1 - -))
37

---

Published as a conference paper at ICLR 2023
the gap between the output of sufficiently wide fully-commected neural network and the output of its linearized neural network at any test point a can be uniformly bounded by
sup t20
((0 (2)
Jin (x) s Cd-1/2
(claimed)
(164)
where they used the original NTK formulation and initialization in Jacot al. 20188:
ht = W x' +
W ~N(001) 1 N(0,1)
Vdl
and
( = 0.... L)
(165)
1+ = =
where Ey = x and f(x)) = h 1,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 W' + Bb alt1 =
W
NN 1 7/2
and
-V1=0, 0, LL
(166)
((0) 100
See their Appendix for the definition of their standard formulation. In the original formulation, they also included two constants ow and for standard deviations, and for simplicity omit these constants here. Note that the outputs the NTK formulation and the standard formulation at initialization actually the same. The only difference is that the norm of the weight W and the gradient of the model output with respect to 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 n/' n/d,, where is learning rate in JJan also their learning rate in their Theorem 2.1, then (164) is true for this network, 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 of to the standard formulation is equivalent applying the following learning rates
di
Th
and
vbb
(167)
duuax
dmnax
W and b' of the NTK formulation, where dmax max (do.
d
To avoid confusion, in the following discussions we will still use the NTK formulation and initial- ization if not stated otherwise.
Problem 1. Claim 167) is true, but it leads to two problems. The first problem is that r/ = (d since 7 = OTT, while their Theorem 2.1 needs the learning rate to ( Nevertheless, this problem can be simply fixed by modifying their standard formulation l+1 W + d. where [(0) ~ ((,,d=)). The real problem that is non-trivial to fix is that by 167 there is U do
dmes 17. However, note that dp is a constant since it is the dimension of the input space, while dmax goes to infinity. Consequently, in (167) they were essentially using a very small learning rate for the first layer 4/0 but normal learning rate for the rest of the layers, which definitely does not match with their claim in their Theorem 2.1.
Another big problem is that the proof of their Lemma in their Appendix G is erro- neous, and consequently their Theorem 2.1 is unsound as it heavily depends on their Lemma 1. In their Lemma I, they claimed that for some constant M O, for any two models with the parameters and 0 such that 0, 0 E B(O()), Co) for some constant Co, there is
Problem 2.
[(O] -
M
S
(claimed)
(168)
Vā
2
Note that the original claim their paper was they were proving this result for their standard formulation. Compared to the standard formulation,
[(0) |(0
S M
0 This because
38

---

Published as a conference paper at ICLR 2023
in the NTK formulation is vá times larger, while the Jacobian ((0) is v times smaller. This also why here we have 0, A E B(B instead of 0.0 E B(O Cyd-1/3) for the NTK formulation. Therefore, equivalently they were claiming (168) for the NTK formulation.
However, their proof of (688) in incorrect. Specifically, the right-hand side of their inequality (S86) incorrect. Using the notations in our Appendix D.3.3 their (S86) essentially claimed that
M
|| val-
0
(claimed)
(169)
for any 0,0 Co). where a' = Vn h-1 and a' is the same gradient for the second model. Note that their (S86) does not have the vd the denominator which appears in (169). This because for their standard formulation, 0 is v times smaller than the original NTK formulation, while ||a'||| has the same order in the two formulations hecause all ht are the same.
However, it is actually impossible prove (69.. Consider the following counterexample: Since 0 and are arbitrarily chosen, can choose them such that they only differ in bf for some 1 < < L.
Then, | 0 =|1
b/ 8 We can see that h++1 and h++1 only differ in the first element, and
h/41 h/41 = ||((1 b Moreover, we have W W so there is
WL+T a att1 =diag(((h(+1)) Vd
WHIT àlt2
a+2 diag(o(h(+1)
Vd
W1+1 Vd
=(diag(((h'+1) diag(o(h(
a l+2
(170)
WI+1T
diag(o
(a o2!22)
Vd
Then can lower bound ||att - - by
W1+1
||a|t1 - //t1111² 2 diag(( (h (1(+1) - diag(o(h(t)))
a 12
Vd
(171)
(diag(((((-1)) WIIIT
(a - xz+2)
Vd
The first term on the right-hand side is equal to [
- ò (b/+1) (W/+1 a/ where
wi-1 is the first row of W+++1 We know that ||w|+'|l2 θ (vd) with high probability as its elements are sampled from (000 1), and in their (S85) they claimed that ||a/+2|1 O(1), which is true. addition, they assumed that Lipschitz. Hence, we can see that
WL+IT Vd
(diag(((h'+)) diag(E (h(+)))
a 1+2
= =0
= n1411
(10 =
-
2
(172)
On the other hand, suppose that claim (169) is true, then | - x/t2/| = 0 ( 1/2
0 0
Then can that the second term on the right-hand side is O (d 1d2 1/2 0 0
because
|wl 1|, ((V)) and (x) is bounded by a constant as is Lipschitz. Thus, for very large d, the second-term is an infinitesimal compared to the first term, so we can only prove that
a (+1 a a/+1 O (
(173)
which is different from (69 because it lacks critical /-1/2 and thus leads contradiction. Hence, cannot prove 169 with the d-1/2 factor, and consequently cannot prove (168) with
39

---

Published as a conference paper at ICLR 2023
the Vå in the denominator on the right-hand side. As a 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 0 and 8 only differ in the first row of some W
E.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
Vwo ddo
xaa
ddo xa
(174)
For all 1, we have ||a|||| = O However, for O, we instead have | 0(1) Thus, we can prove that the norm of w fxx) has the same order as the gradient with respect to any other layer, so there is no need to use a smaller learning rate for the first layer.
Regarding Problem in our formulation (8) and initialization (9, the initialization of the last layer of the NTK formulation is changed from the Gaussian initialization W -0, 1) to the zero initialization W ((0) 0. Now we show how this modification solves Problem 2.
The main consequence of changing the initialization of the last layer that (86) becomes different: instead of |WL|| S 3vd, d. we have ||W*.| ||, Co s 3 3 d. In fact, for any (0. 1/2),
can prove that || ll2 I 3d" for sufficiently large d. In our proof we choose r = 1/4.
Consequently, instead of ||a||| M3. now prove that ||a²) ||g S M2dd-112 1/2 for all - L by
induction. So now we can prove ||a' 0'112 = 0 ( (dr 1/2 0 0 ))) instead of O (1 0 [
because
For 1 < L. we now have | || = O(dr-1/2 instead of O(1), so we can have the additional d/2 factor in the bound.
For 1 L, although ||a=+1|, ll Odd)/2) so again we can decrease the bound by a factor of 1/2
note that ||W4|2 now becomes O(d") instead of
Then, with this critical 1/2, we can prove the approximation theorem with the form
sup (00 (z) f (z) S Cd/-1122 1/2 220
(175)
for any r E (0, 1/2). though we cannot really prove the ( bound as originally claimed in 164). So this is how we solve Problem 2.
One caveat of changing the initialization to zero initialization whether we can still safely assume that Amin > 0 where Ain is the smallest eigenvalue of O the kernel matrix of our new formulation. The answer is yes. In fact, in our Proposition 3 we proved that θ is non-degenerated (which means that (z æ') still depends æ and æ'), and under the overparameterized setting where di >> n, chances are high that is full-rank. Hence, we can still assume that min > O.
As final remark, one key reason why need to initialize L as zero is that the dimension of the output space (i.e. the dimension of h [++ is finite, and in our case it 1. Suppose we allow the dimension of l L+1 to be d which goes to infinity, then using the same proof techniques, for the NTK formulation we can prove that sup, h I++1 hin I+t))) I C, i.e. the gap between two vectors of infinite dimension is always bounded by finite constant. This is the approximation theorem need for the infinite-dimensional output space. However, when the dimension of the output space is finite, sup; h (+((()
2
h ((t)
< C' longer suffices, so we need decrease the order of the norm of W L in order to obtain smaller upper bound.
40


Reviews:
[{"review_id": "Y1sAPZjB-3G", "reviewer": "Reviewer_ZGFE", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies whether generalized reweighing algorithms can improve out-of-distribution generalization.\n\nFirst, it defines \"generalized reweighting\", and then shows that generalized reweighting algorithms have the same implicit bias as ERM, meaning the model converges to the same parameters given the same initial training point. \n\nThis paper proves this result for both regression and classification with overparameterized linear models (including L2 regularization) and wide neural networks.\n\nFor linear models, the theorems are more straightforward.\n\nThe theorems for the wide neural nets are based on the theoretical results of neural tangent kernels. ", "summary_of_the_review": "This paper provides a theoretical analysis of why some DRO algorithms do not improve over ERM. There is a good motivation for the problem and it is an important one;  the main paper is somewhat clear.  The main problem is that the paper does not provide intuitive explanations but instead relies only on technical theorems to answer the motivating questions.", "strength_and_weaknesses": "Strength\n\n- This is a very important and interesting problem.\n\n- the introduction is well-written. \n\n- The paper clearly states what it contributes and how it relates to existing papers.s.\n\n- The paper clearly states its limitations.\n\nMain weakness\n\n- After reading this paper, I don’t think I gained an intuitive understanding of why generalized reweighting does not improve over erm.\nIt would make the paper more accessible to a wider audience if parts of the paper were devoted to explaining these technical descriptions in plain English.\n\nMinor points\n\n- Currently, the related work section appears to be an afterthought. It appears in the appendix and does not explain how this work fits into existing literature.\nAs an example, in the section on group fairness, it is unclear how the subpopulation shift problem in this paper is related to group fairness. It does not specify how this work relates to these papers.\n\n- Furthermore, there is a large literature on distribution generalization, which is not included in this paper. Of course, there is no need for the authors to cite every paper in a  growing field. However, I would like to see some examples of what constitutes a generalized reweighing algorithm and what does not.\n\n- Some jargons are not well defined (e.g., sub-population shift, implicit bias)\n\nOverall, I like the motivating problem and think this could be a high-impact piece of work. The paper could be improved if some of the issues outlined above were addressed.\n\nI am willing to change my score if the issues mentioned are addressed.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "UqnTKev3gn", "reviewer": "Reviewer_cgwJ", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "From a theoretical viewpoint, this paper studied Generalized Reweighting (GRW) algorithms that include importance weighting and Distributionally Robust Optimization (DRO) variants, which were designed for learning with a distributional shift. The authors showed that when used to train overparameterized linear models or wide NN models, GRW algorithms do not improve over ERM due to the existence of implicit biases. It is also shown that adding small regularization which does not greatly affect the empirical training accuracy cannot help. Based on the theoretical results, it is concluded that to pursue distributionally robust generalization, one needs to develop non-GRW approaches or devise novel classification/regression loss functions that are adapted to GRW approaches.", "summary_of_the_review": "See above.", "strength_and_weaknesses": "Strength:\n\n1. The authors conducted a systematic study to theoretical understand why generalized reweighting does not improve over ERM. The results may apply to various existing reweighting schemes. \n2. The conclusion of the paper is useful and inspiring. It may lead to more future work on addressing the related robust learning problems.\n\n\nWeaknesses:\nNone identified.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Qja3DmbwBT", "reviewer": "Reviewer_NJFN", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the phenomenon that Generalized Reweighting (GRW) and distributionally robust optimization (DRO) do not significantly improve over ERM in real applications with distribution shift. This paper shows for a linear model or an NTK\nneural network trained with GRW, the resulting models are close to that obtained by ERM. This paper also shows that L2 regularization only works when it is large enough to lower the training performance. The empirical results verify the arguments in this paper.\n", "summary_of_the_review": "This paper has shown that the general reweighting algorithm does not necessarily achieve better robustness than ERM. The analysis of GRW framework is novel to me, and the results are solid. My main concern is that the paper has made strong assumptions about the linear or wide NN model. It is unclear whether the results still hold when extended to the DNN (please see the first point of the weaknesses for more details). Besides, the significance of Theorem 6 is unclear to me (second point of the weakness). I will raise my score if the authors can provide a convincing response to the concerns. ", "strength_and_weaknesses": "### Strengths:\n- Distribution shift is common in real-world applications and reweighting is a popular method to deal with this problem. Thus, understanding whether GRW is useful and why is of great importance.\n- This work extends the previous theoretical results to the settings: (1) wide neural networks. (2) general reweighted algorithm (3) both regression and classification tasks. The extensions are non-trivial.\n- The results are well-supported and instructive, which deepen our understanding of GRW.\n\n### Weaknesses:\n- About the strong assumption: as the authors have discussed in Section 6.2, the results of this paper are established on assumptions that the models are linear or wide NN. Based on the assumption, GWR is shown to share similar implicit bias with ERM. I am concerned that these assumptions are too strong to explain the empirical observations for DNN. For example, the proposed GRW also takes the importance weighting algorithm as an example, but with the DNN model, the method is shown to be empirically effective for distribution shift problems by updating the weight dynamically [1]. In this sense, the significance of the proposed theorems seems limited to me.\n\n- About the GRW with L2 regularization: I am not sure whether Theorem 6 can support the claim that GRW does not achieve better DRG than ERM. Then theorem has shown that with a small regularization, the GWR will have a similar testing performance as ERM. But, when the regularization is large, the performance GWR could be different from ERM. Although the training error of GWR (with large regularization) could be worse than ERM, the comparison of their testing performance is still unclear.\n\n- A similar conclusion that DRO will perform just like ERM has also been drawn by the previous work [2]. Their analysis is independent of the model. I think it would be important to provide a discussion on the difference between the two works.\n\n[1] Rethinking Importance Weighting for Deep Learning under Distribution Shift. T Fang, N Lu, G Niu, M Sugiyama.\n[2] Does Distributionally Robust Supervised Learning Give Robust Classifiers? W Hu, G Niu, I Sato and M Sugiyama.\n\n", "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": "FZC3DM4UGUr", "reviewer": "Reviewer_Zc4T", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper provides a detailed and comprehensive theoretical analysis to the problem that existing DRO approaches do not bring significant performance gain over ERM. The analysis focus on the GRW framework that minimizes the weighted empirical risk. The authors show that for linear models and wide neural networks, the resulting model yielded by GRW is closed to that obtained by ERM on both regression and classification tasks, namely, GRW does not improve over ERM. The authors further show that the effect of adding small regularization is of no help on alleviating this problem. With the theoretical results, principal ways are presented to improve DRG.", "summary_of_the_review": "This paper studies a vital problem that existing DRO approaches do not bring significant performance gain over ERM from theory perspective. The authors provide detailed analysis of two representative models, linear models and wide neural networks, on regression and classification tasks. Experiments are also provided to support the results. My major concern is the relation between this work and previous work (See weaknesses). The authors are encouraged to provide detailed comparison and explain the differences.", "strength_and_weaknesses": "Strength: The theoretical analysis is comprehensive and convincing, which I believe could bring new insights to the community in designing DRO methods. The authors also conduct experiments to support their theoretical results.\nWeaknesses: As the authors have pointed out, the analysis relies on some strong assumptions, which could be the major weakness of this work. Besides, previous work [1] has the similar results that minimizing the weighted empirical risk is equivalent to minimizing the vanilla empirical risk. The author should make comparison and explain the differences in detail. I also wonder whether the linearly independent gradients assumption in Theorem 4 could be satisfied in real applications.\n\n[1] Does Distributionally Robust Supervised Learning Give Robust Classifiers? Weihua Hu, Gang Niu, Issei Sato and Masashi Sugiyama.\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster