How does overparametrization affect performance on minority groups?
Authors: Subha Maity
Saptarshi Roy
Songkai Xue
Mikhail Yurochkin
Yuekai Sun
Venue: Submitted to ICLR 2023 (2023)

Abstract: The benefits of overparameterization for the overall performance of modern machine learning (ML) models are well known. However, the effect of overparameterization at a more granular level of data subgroups is less understood. Recent empirical studies demonstrate encouraging results: (i) when groups are not known, overparameterized models trained with empirical risk minimization (ERM) perform better on minority groups; (ii) when groups are known, ERM on data subsampled to equalize group sizes yields state-of-the-art worst-group-accuracy in the overparameterized regime. In this paper, we complement these empirical studies with a theoretical investigation of the risk of overparameterized random feature models on minority groups. In a setting in which the regression functions for the majority and minority groups are different, we show that overparameterization always improves minority group performance.

Under review as a conference paper at ICLR 2023
HOW DOES OVERPARAMETRIIATION AFFECT PERFORMANCE ON MINORITY GROUPS?
Anonymous authors Paper under double-bling review
ABSTRACT
The benefits of overparameterization for the overall performance of modern ma- chine learning (ML) models are well known. However, the effect of overparam- eterization at more granular level of data subgroups is less understood. Recent empirical studies demonstrate encouraging results: (i) when groups are not known, overparameterized models trained with empirical risk minimization (ERM) perform better on minority groups; (ii) when groups are known, ERM on data subsampled to equalize group sizes yields state-of-thee arrt worst-group-accuue rameterized regime. In this paper, we complement these empirical studies with a theoretical investigation of the risk of overparameterized random feature models minority groups. In a setting in which the regression functions for the majority and minority groups are different, show that overparameterization always improves minority group performance.
in the overpa-
INTRODUCTION
Traditionally, the goal of machine learning (ML) is to optimize the average or overall performance of ML models. The relentless pursuit of this goal eventually led to the development of deep neural networks, which achieve state of the art performance in many application areas. A prominent trend in the development of such modern ML models overparameterization: the models are so complex that they are capable of perfectly interpolating the data. There is a large body of work showing overparameterizztion improves the performance of ML models in variety of settings (e.g. ridgeless least squares Hastie et al. (2019), random feature models Belkin et al. (2019); Mei and Montanari (2019h) and deep neural networks Nakkiran et al. (2099))
However, as ML models find their way into high-stakes decision-making processes, other aspects of their performance (besides average performance) are coming under scrutiny. One aspect that is particularly relevant to the fairness and safety of ML models is their performance on traditionally disadvantaged demographic groups. There troubling line of work showing ML models that perform well average may perform poorly minority groups of training examples. For example, Buolamwini and Gebru (2018) show that commercial gender classification systems, despite achieving low classification error average, tend misclassify dark-skinned people. In the same spirit, Wilson et al. (219)) show that pedestrian detection models, despite performing admirably on average, have trouble recognizing dark-skinned pedestrians.
The literature examines the effect of model size on the generalization error of the worst group. Sagawa al. 2020) find that increasing model size beyond the threshold of zero training error can have negative impact on test error for minority groups because the model learns spurious correlations. They show that subsampling the majority groups far more successful than upweighting the minority groups in reducing worst- grrst error. Pham et al. (202T) conduct more extensive experiments to investigate the influence of model size on worst-group error under various neural network architecture and model parameter initialization configurations. They discover that increasing model size either improves or does not harm the worst-group test performance across all settings. Idrissi et al. (202I) recommend using simple methods, i.e. subsampling and reweighting for balanced classes or balanced groups, before venturing into more complicated procedures. They suggest that newly developed robust optimization approaches for worst-group eтror control (Sagawa et al. 2019 Liu et al. 20211) could be computationally demanding, and that there is no strong (statistically significant) evidence of advantage over those simple methods.

---

Under review as a conference paper at ICLR 2023
In this paper, provide theoretical justification for the empirical results in Sagawa et al. (020);; Pham et al. (201); Idrissi et al. (2021) by studying how overparameterization affects the performance of ML models minority groups in an idealized regression problem. Our investigation shows that overparamateriatton generally improves or stabilizes the performance of MI. models on minority groups. Our main contributions are:
1. develop simple two-group model for studying the effects of overparameterizaaton (sub)groups. This model has parameters controlling signal strength, majority group fraction, overparameterization ratio, discrepancy between the two groups, and error term variance that display a rich set of possible effects.
2. we develop comprehensive picture of the limiting risk of empirical risk minimization in high-dimensional asymptotic setting (see Sections
we show that majority group subsampling provably improves minority group performance in the overparameterized regime.
Some of the technical tools that we develop in the proofs may be of independent interest.
PROBLEM SETUP
2.1 DATA GENERATING PROCESS
Let X' Rd be the feature space and y C R. be the output space. To keep things simple, consider a two group setup. Let Po and P1 be probability distributions on x V. We consider Po and P1 as the distribution of samples from the minority and majority groups respectively. In the minority group, the samples (æ, y) E X x y are distributed as
x~ Px, y I -11=30I1 JJ 6~ ~O,77)"
(2.1)
where Px is the marginal distribution of the features, fo E Rd is vector of regression coefficients, and 72 > is the noise level. The normality of the error term (2.
important; our theoretical
results remain valid even if the error term is non-Gaussian.
In the majority group, the marginal distribution of features identical, but the conditional distribution of the output is different:
x = 3 x + ~~ NO,
(2.2)
where 31 E Rd is vector of regression coefficients for the majority group. We note that this difference between the majority and minority groups a form concept drift or posterior drift: the marginal distribution of the feature is identical, but the conditional distribution of the output is different. We focus on this setting because it not only simplifies our derivations, but also isolates the effects of concept drift between subpopulations through the difference 5 a 3, - Sn. If the covariate distributions between the two groups different, then overparameterized model may be able to distinguish between the two groups, thus effectively modeling the groups separately. In that sense, by assuming that the covariates are equally distributed, we consider the worst case.
Let 9t E {0, 1} denote the group membership of the i-th training sample. The training data {Xri, Vis g: Pi consists of mixture of samples from the majority and minority groups:
9i Ber(*)
(2.3)
(aa vs) ~ Pg:
where π E [ 1] is the (expected) proportion of samples from the majority group in the training data. We denote 71 as the sample size for majority group in the training data.
2.2 RANDOM FEATURE MODELS
Here, consider a random feature regression model (Rahimi and Recht, 2007 Montanari al. 2020
f(z, f)= (0)
(2.4)
2

---

Under review as a conference paper at ICLR 2023
where a--) is non-linear activation function and N is the number of random features considered in the model. The random feature model is similar to a two-layer neural network, but the weights 8j's 's of the hidden layer are set at some (usually random) initial values. In other words, random feature model fits a linear regression model on the response y using the non-linear random features 00, v/vd)'s is instead of the original features zy's. This type of models has recently been used Montanari et al. (2020) to provide theoretical explanation for some of the behaviors seen in large neural network models.
We note that at first we analyzed the usual linear regression model hoping to understand the effect of overparameterization. Specifically, we considered the model
f(r, = = aTxz
(2.5)
However, we found that the linear model suffers in terms of prediction accuracy for minority group in overparameterized regime. In particular, in the case of high signal-to-noise ratio, the prediction accuracy for the minority group worsens with the overparameterization of the model. This is rather unsatisfactory as the theoretical findings do not echo the empirical findings in Le Pham et al. (202T), suggesting that a linear model is not adequate for understanding the deep learning phenomena in this case. We point the readers to Appendix A for the theoretical analysis of overparameterezied linear models.
2.3 TRAINING OF THE RANDOM FEATURE MODEL.
We consider two ways in which learner may fit the random feature model: empirical risk minimiza- tion (ERM) that does not require group annotations; subsampling that does require group annotations. The availability of group annotations highly application dependant and there is a plethora of prior works considering either of the scenarios (Hashimoto et al. 2018 Zhai et al. 2021
Pham et al. 2021
Sagawa et al.
2019 2020: Idrissi et al. 2021).
2.3.1
EMPIRICAL RISK MINIMIZATION (ERM)
The most common way to a predictive model is to minimize the empirical risk on the training data:
à arg min - n Σ [ s( a, 0))² arg min ! n E Σÿ= a, x: V aER
aER
(2.6)
where we recall that the weights 0 's of the first layer are randomly assigned. The above optimization (2.6) has unique solution when the number of random features neurons are less than the sample size (N < n)) and we call this regime as underparameterized. When the number of neurons is greater than the sample size (N >> n), which call the overparameterized regime, is not unique in (2.6)
as there are multiple a E R N that interpolate the training data, i.e., y/- = Σソ= a,o (0] xx),, i E [n]
N
resulting in zero training error. In such a situation we set â at a specific a E R which (1) interpolates the training data and (2) has minimum fo-nrrm. This particular solution is known as the minimum norm interpolant solution (Hastie et al. 2019: Montanari et al. (020) and is formally defined as
E arg min ||aaa : y: = EE
ie [m] = (ZT y,
(2.7)
where Z E RO with Zi,, = a0. and A is the Moore-Penrose inverse of A. The minimum norm interpolant solution (2.7) has an alternative interpretation: it is the limiting solution to the ridge regression problem at vanishing regularization strength.
1 En - 2./ + NA
à = lim âΛ, âة E arg min aERN
(2.8)
X-+0+
In fact the conclusion in 2.8 continues to hold in the underparameterized (N < n)) regime. Hence, we combine the two regimes (N < n and N > 72) and obtain the ERM solution as (28). In Hastic et al. (2019) is known the ridgeless solution. Finally, having estimator à of the parameter in the random feature model (24), the response of an individual with feature vector x is predicted as:
((x) f(x, à, +) Ej á50 2/va)
(2.9)
3

---

Under review as a conference paper at ICLR 2023
2.3.2 MAJORITY GROUP SUBSAMPLING
is known that model trained by ERM often exhibits poor performance on minority groups (Sagawal ct al. 2019). One promising way to circumvent the issue is majority group subsampling: a randomly drawn subset of training sample points are discarded from majority groups to match the sample sizes for the majority and minority groups in the remaining training data. This emulates the effect of reweighted-FRee -RRM,, where the samples from minority groups are upweighted in the ERM.
In underparameterizee case the reweighting is preferred over the subsampling due to its superior statistical efficiency. On contrary, the overparameterized case, reweighing may not have the intended effect the performance of minority groups (Byrd and Lipton 2019), but subsampling does (Sagawa et al. 2020, Idrissi et al. 2021). Thus we consider subsampling as a way of improving performance in minority groups in overparameterized regime. We note that subsampling requires the knowledge of the groups/sensitive attributes, so its applicability is limited to problems in which the group identities are observed in the training data.
RANDOM FEATURE REGRESSION MODEL
In this paper we mainly focus on the minority group performance, which we measure as the mean squared prediction error for the minority samples in the test data:
(3.1) where is independent of the training data, and is identically distributed as 's and for generic a by the notation E, we mean that the expectation is taken over the randomness in a. One may alternatively study (( Po [f, θ) y}2 the mean square prediction error for the minority group, but for a fixed noise level 7 it has the same behavior as [31 as suggested by the following:
Ro(â)= Ex [[f a, θ) - B7 x) P. HE
((e,)))r((( (z, θ) y Px [[f(s) a, θ) 30 x}² + ?
A finite sample study of (ā) (3.1 is dif- ficult, in this paper we study 's limiting behavior in high-dimensional asymptotic setup. Specifically, recalling the notations from Table [ we consider N/d 1/1 > O, n/d + 3 > 0 and ni n1/n + т E [1/2, 1J. The problem is underparameterized 2/ 01/122 lim (No [N/n] < and overpa- rameterized y
Table 1: Table of notations
Notations
Descriptions
Total sample size
no. 11
Sample-sizes minority and majority groups
if y
N
Number of neurons Covariate dimension N/d n/d Overparameterivaaion N/n Majority group proportion Regression coefficients for
d
To study the minority risk we first decom- pose it into several parts and study each of them separately. The first decomposition
1/
2/2
follows:
Lemma 3.1. We define the bias 2(30, 5) = [[E,x[(EE[faaa à, O) 9 2 and the variance y (30,8, 8, Exp [ar. à, O)H}
So. B1
minority and majority groups
where (E)) are the errors in the data generating model, i.e. & Yi x BB and Var, denotes the variance with respect to The minority risk decomposes as
B1 80
7
Noise variance
11 0) - x] 8, 7 (
(3.2)
The proof is realized by decomposing the square in [f à, θ) Br x]2 = Hffz, a, θ)] [ a, 0))) [Er[S(x, à, θ)] - 3g =r]/2. We now provide an interpretation for the variance term.
The variance term Firstly we notice that the variance Y ( 6, 7) captures the average variance of the prediction rule ((x, a, +) in terms of the errors in training data. To look closely define
4

---

Under review as a conference paper at ICLR 2023
0.6
4-45"
Variance
90
Blas
Figure Trends for bias and variance in the minority ERM risk for varying overparameterization ? Left: variances for varying y. Middle: biases for different y and 0, where 0 is the angle between fo and B1. Here the majority group proportion π is set 0.8. Right: biases for different v a's when 0 is set at 180". The solid lines are the theoretical predictions and the points with error-bars represent the empirical predictions over 10 random runs.
== = vd) as the random feature for new covariates x and realize that the variance of the predictor with respect to c, and thus (Su,, 5, r), do not depend on the values of Bu or as shown in the following display:
Var. a, θ)} Var, (2 a} Var f2 (z" (2'2)""" y) Var, {z (Z) e).
Hence we drop f0 and 5 from the notation and write the variance term as (r)). Since G;' have variance 72 we realize that the exact dependence of the variance term with respect to T the following:
= 1). This also implies that the variance term ((() teases out the contribution of data noise level r in the minority risk.
The bias term We notice that the bias term 3 (30. 8, r) in decomposition (32) is the average bias in prediction for the minority group. We further notice that it does not depend on the noise level r (both E. [f[ a, θ)] and 3g do not depend on 7) and denote it as 3 (Ba. 6) by dropping r. Next, separate out the contributions of Bg and in the bias term via a decomposition. For the purpose we recall, {zi,j JEN E R is the matrix of random features and define the following (1) X [ ..... x., ...,,,,,... I is the covariate matrix in training data, (2) X1 is the covariate matrix consisting only the samples from majority group, and (3) Zi is the random feature matrix for the majority group.
The decomposition for the bias term follows:
L (So. 8) = Px (2 T (Z Z)'Z T x x )), + T2 Z) x,
x
(3.3)
+2(2 (2 2 x 3)08 Zi 2)'2|.
Next, we make some assumptions on 100 and 8 vectors:
Assumption 3.2. There exists some Fg. Fs and F3,6 E R such that the following holds: |1:6.112 F3. ||013 F and (Bo. 6) Fg.s-
Here, F3 and F5 are the & signal strengths of 80 and ō. The decomposition in the next lemma separates out the contributions of 3o and in B(B. 6).
- Lemma 3.3. Define the followings: Bp Ex Px - B,
Ex [|| T (Z (22222Z X1 x111 d) and EzS5 2E
( (Z 22)
Then we have (B0, 5) P3 BB F3 Bs FR.668,4.
In Lemma 3.3 we see that F? BB F3.5 E, quantifies the contribution of the model misspecification in the two-group model, and call this misspecification error term. For the other terms in the decomposition we utilize the results of Montanari et al. (2020) who studied the effect of overpa- rameterization the overall performance (i.e., in single group model), thus the misspecification enror term does not appear their analysis. Our theoretical contribution in this paper is studying the exact asymptotics of the misspecification error terms. Before we present the asymptotic results we introduce some assumptions and definitions. First we make a distributional assumption on the covariates 2;'s 's and the random weights 0, 's which allow an easier analysis for the minority risk.
Assumption 3.4. We assume that { and {0, N are iid (nif(gd-1(Va)) i.e uniformly over the surface of a d-dimensional Euclidean ball of radius vd and centered at the origin.
5

---

Under review as a conference paper at ICLR 2023
Next assumee that activation function has some properties, which are satisfied by any commonly used activation functions, e.g. ReLU and sigmoid activations.
Assumption 3.5. The activation function o R - R is weakly differentiable with weak derivative o' and for some constants co, C₁ > 0 holds (a())), [o'( Coe
Both assumptions 3.4 and 3.5 also appear in Montanari al. (2020). Below we define some quantities which we require to describe the asymptotic results.
Definition 3.6. I. For the constants
Ao = ({a(G)), A1 A1=
1 =²=B(((G)))) - rg -u9,
(3.4)
where the expectation is taken with respect to G N(O, 1) we assume that 0 < Ho,/M1, 14 < oo and define { = p1/p..
2. Recall that N/d 1b1 0, n/d 1/2 0 and n / - [1/2,1] We set v min( 1/23 and define
x 12 25
3. We furthermore define the following:
60 = -x + +xx + - 1/1 1/2 + -
(1/1
- -2x2g4-3x
+ (+11 + - 32/ + +)x²² +2x"5² +x² + +331122x - 11122
8 5- -/222²² + 01 -//1/2
6 55 - 3x + (11 5) +2 +3x + (- 1)x² - 2x²6² -x2
Equipped with the assumptions and the definitions we're now ready to state the asymptotics for each of the terms in the minority group prediction errors. The following lemma, which states the asymptotic results for Bg and (T). has been proven in Montanari et al. 2020))
Lemma 3.7 (Theorem 5.7, Montanari et al. (2020)) Let the assumptions 3.2 3.4 and 3.5
hold.
Define D / &8g and x 83 & where &G. of and &g are defined in Definition the following hold:
3.6
Then
lim B[Bo] B", lime =[ 7zy,
where the expectation taken over {x,)² {0, 1N 8o and 6.
Trend in the variance term We again recall that the variance term V(77 (7) teases out the contributions of noise in the minority group prediction error. Here, the trend that we'r re most interested in is the function of y /
effect of overparameterizatton:: how does the asymptotic // behave
lim (N/n) when the lim (n/c)) (n/d) is held fixed, and y > 1. Although it is difficult to
understand such trends from the mathematical definitions of 7 we notice in the Figure I (left) that the variance decreases in overparameterrized regime (y 1) with increasing model size (7).
Next we study the asymptotics of Mg and 63,8 which, as discussed lemma 3.3 of the minority group prediction risk that comes from the model misspecification in the two group
quantify the part
model 2.3
Lemma 3.8 (Misspecification error terms). Let the assumptions/ 3.2 definitions of L and */* in lemma 3.7 we further define V
3.4 and 3.5 hold. Following the
2 1)), where x and vb
are defined in Definition 3.6 Then
lim E B
11, x(1 x)y=* + 2 lim E[G = Mr 4 n (
1 11
d
where in lemma 3.7 the expectation E is is taken over {x, {r.) (0, 10) Bu and 6.
Below describe the observed trends in the bias term in the minority risk.

---

Under review as a conference paper at ICLR 2023
Trends in the bias term Here, study the asymptotic trend for the bias term 8 6). We see from the bias decomposition in Lemma 3.3 and the term by term asymptotics in Lemmas 3.7 and 3.8 that the bias term asymptotically converges to F 88 + FJ + FA We mainly study The trend of this bias term in overparameterized regime with respect to the three parameters: (1) the overparametrization parameter 7, (2) the majority group proportion and (3) the angle between the vectors S and 3i, which is denoted by 0. The middle and right panels in Figure D give an overall understanding of the trend of the bias term with respect to the aforementioned parameters. In both of these figures we set ||3 2| = || = 1. In the middle panel, we see that for fixed angle 8, the bias generally decreases with overparameterizztion. In contrast, for a fixed level of overparameterriztion 7, the bias increases as the angle 0 increases. This is not surprising as intuitively, as the angle 0 grows, the separation between 90 and 31 becomes more prominent. As a consequence, the accuracy of the model worsens and that is being reflected in the plot of the bias term.
Similar trend can also be observed when the majority group proportion x varies for a fixed angle 0 (right most panel of Figure []. Here we set 31 - i.e., the angle 0 180 As expected, the bias increases with parameter æ for a fixed y because of higher imbalance in the population. Whereas, for a fixed the bias decreases with increasing y. Thus, in summary we conclude that overparameterization generally improves the worst group performance of the model for fixed instances of 0 and r.
The following theorem summarizes the asymptotic results in Lemmas 3.7 and 3.8 and states the asymptotic for minority group prediction error.
Theorem 3.9. Let the assumptions 3.2 3.4 and 3.3 hold. Following the definitions of 8 V Mr
and Msz in Lemmas 3.7 and 3.8
we have the term by term asymptotics:
lim El = B", lim ( 72, d-+00
lim E[ss] - and lim E E66, { = M6i. d
d
d
and the minority group prediction error has the following asymptotic
[[Ro(a]] = F ز] + F3 + Fa + (
- F3 ~0 F3 11 + Fs.8-M4 + 22y=
A complete proof of the theorem is provided in Appendix B
Trend in minority group prediction error for ERM To understand the trends in minority group prediction error we combine the trends in the bias and the variance terms. We again recall that we're interested in the effect of overparameterization,, i.e. growing Y when 7 > 1. In the discussions after Lemmas 3.7 and 3.8 (and in Figure D we notice that both the bias and variance terms decrease or do not increase with growing overparametcrization for any choices of the majority group proportion π and the angle 0 between 3 and B, Since the minority risk decomposes to v terms (3.2). we notice that similar trends hold for the overall minority risk. In other words, overparaneterization improves or does not harm the minority risk. These trends agree with the empirical findings in Pham et al. (021))
3.1 LIMITING RISK FOR MAJORITY GROUP SUBSAMPLING
Though overparameterization of ML models does not harm the minority risk for ERM, they generally produce large minority risk Pham et al. (202T). To improve the risk over minority group Sagawa et al. (2020); Idrissi et al. 22021) recommend using majority group subsampling before fitting ERM and show that they achieve state-of-the-a
minority risks. Here, we complement their empirical finding with thcoretical study on the minority risk for random feature models in the two group regression setup 2..3. We recall from subsection 2.3.2 that subsampling discards a randomly chosen subsample of size no from the majority group (of size n1) to match the sample size (no) of the minority group, and then fits an ERM over the remaining sample points. Here, we repurpose the asymptotic results for ERM (Theorem 3.9 to describe the asymptotic behavior for subsampling by carefully reviewing the changes in the parameters 1/1, th2 and æ. First we notice that the total sample size after subsampling is nş 2no (both the majority and minority groups have sample size no.s = f1,s ny) which means the new majority sample proportion is Rs = no.s/ns = 1/2. We further notice that 1i remains unchanged, ie., 1/1.8 = 1/1 whereas 4/2 lim n/d changes to t/2.5
7

---

Under review as a conference paper at ICLR 2023
6=0
n- 0.6
4m45
Subsampiing EAM
Subsampping FRM
m=08
-35
Figure 2: Difference in minority risk between subsampling and ERM. Left: the differences in minority risks for several values of I (the angle between 30 and (1) and overparameterzation y where majority proportion i is set at 0.8. Right: the minority risk differences for several values of π and y when 0 is 180"
lima- ng/ oo 2no/ /d limma 2(no/n) (n/d) 2 =)) The subsampling t/2. 103.s-7:: (2
setup is underparameterrize when n 2no > N 7s /1.5/
x)) < and
overparameterized when 7s > 1. Rest of the setup in subsampling remains exactly the same as in the ERM setup, and the results in Lemmas 3.7 3.8 and Theorem 1.t.mm....oooo continue to hold with the new
parameters: 4/1,s, 122,5 and TT.
ERM vs subsampling We compare the asymptotic risks of ERM and majority group subsampling in overparameterized setting. shows the trend of the error difference between subsampling and ERM. Similar to the previous discussion, denote by 0 the angle between B1 and Sg. and set ||3 = 118oll 2 = In the left panel, we fix the majority group parameter π 0.8 and vary 0. generally observed that subsampling improves the worst group performance consistent with the empirical findings in Sagawa et al. (2020) and Idrissi et al. (2021). Moreover, the improvement is prominent when the group regression coefficients large. Intuitively, when 0 is very large, the distinction between majority and minority groups is more prominent. As a consequence, the effect of under representation on minority group becomes more relevant, due to which the worst group performance of ERM is affected. Whereas, subsampling alleviates this effect of under representation by homogenizing the group sizes. On the other hand, the effect of under representation becomes less severe when fo and 31 are close by, i.e., A is small. In this case, we see subsampling does not improve the worst group performance significantly. In fact, for larger values of y, subsampling performs slightly worse compared to ERM. This is again not surprising, as for smaller separation, the population structure of the two groups becomes more homogeneous. Thus, full sample ERM should deliver better performance compared to subsampling.
ERM, which is
well separated, i.e., is
Similar trend also observed in the right panel where we fix = 180 and vary я. Again, improvement due to subsampling most prominent for larger values of which corresponds to greater imbalance in the data. Unlike the previous case, the subsampling always helps in terms of worst group performance but the improvement becomes less noticeable with decreasing as overparameterization grows.
RELATED WORK
Overparameterized ML models The benefits of overparameterizzttion for average or overall performance of MI. models is well-studied. This phenomenon is known as "double descent", and asserts that the (overall) risk of ML models decreasing as model complexity increases past a certain point. This behavior has been studied empirically (Advani and Saxe 2017 2017,Belkin et al. 2018
Nakkiran et al. 2019; Yang et al.] 2020 and theoretically (Hastie et al., M Montanari et al. 2020
Mei and Montanari 2019b Deng et al. 2020). All these works focus the average performance of
ML models, while we focus on the performance of ML models on minority groups. The most closely
related paper in this line of work Pham et al. 2021 where they empirically study the effect of
8

---

Under review as a conference paper at ICLR 2023
model overparameteriizaion minority risk and find that the model overparamterization generally helps or does not harm minority group performance.
Improving performance on minority groups There is long line of work improving the per- formance of models on minority groups. There are methods based on reweighing/subsapiing (Shi 2019) and (group) distributionally robust optimization (DRO) (Hashimoto et al.] 2018 Duchi et al. 2020 Sagawa et al., 2019). In the overparameterized regime, methods very effective (Byrd and Lipton 2019), while subsampling has been empirically shown to improve performance on the minority groups (Sagawa et al. 2020; Idrissi et al.,
modaira 2000 Cui et al.
based reweighing
202Tp. Our theoretical results confirm the efficacy of subsampling for improving performance on the minority groups and demonstrate that it benefits from overparameterization.
Group fairness literature proposes many definition of fairness (Chouldechova and Roth, (018))
some of which require similar accuracy on the minority and majority groups (Hardt et al. 2016). Methods for achieving group fairness typically perform ERM subject to some fairness constraints
(Agarwal et al. (2018). The interplay between these constraints and overparametrization is beyond the scope of this work.
SUMMARY AND DISCUSSION
In this paper, we studied the performance of overparameterized ML models on minority groups. We set up a two-group model and derived the limiting risk of random feature models in the minority group (see Theorem 3.9.. In our theoretical finding we generally see that overparameterzation improves or does not harm the minority risk of ERM, which complements the findings in |Pham et al. (2021). We also show theoretically that majority group subsampling is an effective way improving the performance of overparamterized models in minority groups. This confirms the empirical results on subsampling overparameterized neural networks given in Sagawa et al. (2020) and Idrissi et al. (2021).
What about classification? We observe that the trend of minority group generalization error in the random feature regression model is qualitatively distinct from its classifi- cation counterpart (see Appendix for the model details). Figure B demonstrates that although overparameterizatioo always reduces the majority error, whether or not it ben- efits the minority group depends on the angle between the coefficients of the two groups: overparameterzation helps the minority group generalization error if the angle acute, while it harms the minority error if the angle is obtuse. This is different from those trends in Figure The disagreement can be explained in part by the fact that the signal-to-noiss ratio in classification problems is difficult to tune explicitly because the signal and noise are coupled due to the model's setup. The effect of overparametriza- tion on minority groups under the random feature classi- fication model open to research by interested readers. Recent developments of convex Gaussian min-max The- orem (CGMT) and related techniques (Montanari et al., 2020
group Minortty group
180
Classiiiation error
0.5
Figure 3: Classification error against overparamterization level of the majority and minority group for various angles 0 between the coefficients of two groups under the random feature classification model.
Bosch et al. 2022) could be technically useful.
Practical implications One of the main conclusion of this paper that overparamaterization generally helps or does not harm the worst group performance of ERM. In other words, using overparametrized models unlikely to magnify disparities across groups. However, we warn the practitioners that overparametrization should not be confused with a method for improving the minority group performance. Dedicated methods such as group distributionally robust optimization (Sagawa et al. (2019) and subsampling (Sagawa et al.] 2020 Idrissi al. 2021 are far more effective. In particular, subsampling improves worst-group performance and benehts from overparametrization demonstrated in prior empirical studies (Sagawa al. 2020) Idrissi et al. 2021) and in this paper.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Madhu S. Advani and Andrew M. Saxe. High-dimensionas dynamics of generalization error in neural networks. arXiv:1710.03667 [physics, q-bio, stat], October 2017.
Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach. Reductions Approach to Fair Classification. wrXiv:1803022455 [cs], July 2018.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine learning practice and the bias-variance trade-off. arXiv:1812.11 11118 [es, stat), December 2018.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. 1903.077777 [cs, stat), March 2019.
David Bosch, Ashkan Panahi, Ayca Özcelikkale, and Devdatt Dubhash. Double descent in random feature models: Precise asymptotic analysis for general convex regularization. arXiv preprint arXiv:2204.02668, 2022.
Joy Buolamwini and Timnit Gebru. Gender Shades: Intersectional Accuracy Disparities in Com- mercial Gender Classification. In Proceedings of Machine Learning Research, volume 87, pages 77-91, 2018.
Jonathon Byrd and Zachary Lipton. What is the Effect of Importance Weighting in Deep Learning? In International Conference on Machine Learning, pages 872-881. PMLR, May 2019.
Alexandra Chouldechova and Aaron Roth. The Frontiers of Fairness in Machine Learning. 18X0000100 [cs, stat], October 2018
Y. Cui, M. Jia, T. Lin, Y. Song, and S. Belongie. Class-Balanced Loss Based on Effective Number of Samples. In 2019 IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), pages 9260-926666 9269, June 2019. doi: 10. 10.1109//P..2009.00004
Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A Model of Double Descent for High- dimensional Binary Linear Classification. arXiv:1911.05822 [cs, eess, stat], May 2020.
John Duchi, Tatsunori Hashimoto, and Hongseok Namkoong. Distributionally Robust Losses for Latent Covariate Mixtures. 1oXiv:2007.33982 fcs, stat], July 2020.
Moritz Hardt, Eric Price, and Nathan Srebro. Equality of Opportunity in Supervised Learning. arXiv:1610.02413 [cs], October 2016.
Tatsunori B. Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness Without Demographics in Repeated Loss Minimization, a8X6v: 10001800000000 [cs, stat], June 2018.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in High- Dimensional Ridgeless Least Squares Interpolation. arXiv:1903.0856 [cs, math, stat), November 2019.
Badr Youbi Idrissi, Martin Arjovsky. Mohammad Pezeshki, and David Lopez-Paz. Simple data balancing achieves competitive worst-group-accuracy arXiv preprint arXiv:2110.14503. 2021.
Alan Le Pham, Eunice Chan, Vikranth Srivatsa, Dhruba Ghosh, Yaoqing Yang, Yaodong Yu, Ruiqi Zhong, Joseph E Gonzalez, and Jacob Steinhardt. The effect of model size worst-group generalization. In NeurlPS 2021 Workshop on Distribution Shifts: Connecting Methods and Applications, 2021.
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. International Conference on Machine Learning, pages 6781-6792. PMLR, 2021.
Song Mei and Andrea Montanari. The generalization enror of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 2019a.
10

---

Under review as a conference paper at ICLR 2023
Song Mei and Andrea Montanari. The generalization enror of random features regression: Precise asymptotics and double descent curve. arXiv: 00355 [math, stat), August 2019b.
Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization error of max-margin linear classifiers: High-dimensional asymptotics in the overparametrized regime. arX1v:1911.01544 [math, staf], July 2020.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and llya Sutskever. Deep Double Descent: Where Bigger Models and More Data Hurt. arXiv:1912.02299 [cs, stat), December 2019.
Alan Pham, Eunice Chan, Vikranth Srivatsa, Dhruba Ghosh, Yaoqing Yang. Yaodong Yu, Ruiqi Zhong. Joseph E Gonzalez, and Jacob Steinhardt. The effect of model size on worst-group generalization. arXiv preprint uxXiv22112.04094, 2021.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Proceedings of the 20th International Conference on Neural Information Processing Systems, NIPS 07, pages 1177-1184, Red Hook, NY, USA, December 2007. Curran Associates Inc. ISBN 978-1-60566 352-0.
Shiori Sagawa, Pang Wei Koh, Tatsunori B. Hashimoto, and Percy Liang. Distributionally Ro- bust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization. arXiv:1911.087 [cs, stat], November 2019.
Shiori Sagawa, Aditi Raghunathan, Pang Wei Koh, and Percy Liang. An Investigation of Why Overparameterization Exacerbates Spurious Correlations. 04X4v:2005.04345 [cs, stat], August 2020.
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of Statistical Planning and Inference, 90(2):227-244, October 2000. ISSN 0378-3755 doi: 00011///000788755000000000 15-4.
Benjamin Wilson, Judy Hoffman, and Jamie Morgenstern. Predictive Inequity in Object Detection. arXiv: [cs, stat), February 2019.
Zitong Yang, Yaodong Yu, Chong You. Jacob Steinhardt, and Yi Rethinking Bias- Variance Trade- off for Generalization of Neural Networks. In International Conference on Machine Learning, pages 10767-10777. PMLR, November 2020.
Runtian Zhai, Chen Dan, Zico Kolter, and Pradeep Ravikumar. Doro: Distributional and outlier robust optimization. In International Conference on Machine Learning, pages 12345-12355, PMLR, 2021.
A RIDGELESS REGRESSION
Similar to Section Bl here describe analysis the linear regression model in overparameteriize regime. The learner fits a linear model
f(x) A g
to the training data, where 3 E Rd is a vector of regression coefficients. We note that although the linear model well-specified for each group, is misspecified for the mixture of two groups The learner fits a linear model to the training data in one of two ways: (1) empirical risk minimization (ERM) and (2) subsampling.
A.1 MODEL. FITTING
Empirical risk minimization (ERM) least squares (OLS):
The most common way of fitting linear model is ordinary
Bols arg gin EL [ 3T 2 arg min 1 X
11

---

Under review as a conference paper at ICLR 2023
where the rows of X E Rexd the r;'s and the entries of RR are the ys's. We note that ERM does not use the sensitive attribute (even during training), so it is suitable for problems in which the training data does not include the sensitive attribute.
In the overparameterized case (n < d), Poos is not well-defined because there are many linear models that can interpolate the training data. In this case, we consider the minimum & norm (min-norm) linear model with zero training error:
Amin E arg migmin ly yy= = X53 = (X"X)
where (X"X) denotes the Moore-Penross pseudoinverse of X The min-norm least squares estimator is also known as the ridgeless least squares estimator because Bmin limx o 3x. where
Bx E arg minpers - X + A1131
We note that if X has full column rank (i.e. X X is non-singular), then Amin is equivalent to Bols-
Majority group subsampling It known that models trained by ERM may perform poorly on minority groups Sagawa et al. (2019). One promising way of improving performance on minority groups is majority group subsampling-randee until the two groups are equally represented in the remaining training data. This achieves an effect similar that of upweighing the loss minority groups in the underparameterized regime.
discarding training samples from the majority group
In the underparameterized case (n > d), reweighing is more statistically efficient (it does not discard training samples), so subsampling reweighing may not have the intended effect on the performance of overparameterized models in minority groups Byrd and Lipton (2019), but[Sagawa et al. (2020) show that subsampling does. Thus we also consider subsampling here as way of improving performance in minority groups. We note that reweighing requires knowledge of the sensitive attribute, so its applicability is limited to problems in which the sensitive attribute is observed during training.
rarely used. On the other hand, in the overparameterized case,
(Byrd
A.2 LIMITING RISK OF ERM AND SUBSAMPLING
We are concerned with the performance of the fitted models on the minority group. this paper, we measure performance on the minority group with the mean squared prediction error test sample from the minority group:
Ro(B) & E E(((3 T0) | E[(3 T 30) [
(A.1)
We note that the definition of (A.I is conditional on X; i.e. the expectation is with respect to the error terms in the training data and the features of the test sample. Although it is hard evaluate Ro exactly for finite n and d, it is possible to approximate it with its limit in a high-dimensional asymptotic setup. In this section, we consider asymptotic setup in which n, d that 7 + E (0, oo). If 7 < 1, the problem is underparameterized: if y > 1, it is overparameterized.
in a way such
To keep things simple, first present our results in the special case of isotropic features. We start by formally stating the assumptions on the distribution of the feature vector Px-
Assumption A.1. The feature vector x ~ Px has independent entries with zero mean, unit variance, and finite 8 + moment for some >
A.3 EMPIRICAL RISK MINIMIZATION
We start by decomposing the minority risk A.I of the OLS estimator BOLS and the ridgeless least squares estimator 3min- Let no and n, be the number of training examples from the minority and the majority groups respectively. Without loss of generality, we arrange the training samples so that the first ni examples are those from the minority group:
X
x =
X1
y =
91
12

---

Under review as a conference paper at ICLR 2023
Lemma A.2 (ERM minority risk decomposition), Let B be either Bols Buin- We have
(5) = E (B - -B)) To (3)- -8o)
= 30 (Ia [1 + (mE1)+57)
72
Ongxd X1 (
(S)
Ongxd
/njo (A.2)
X1
+ +887 [Onxxd X1
{ {(xxre
T
(51)
where 1Ix A X is the projector onto ran(X 8 - Bo - 3r, and & a 1 covariance matrix of the features in the training data.
X is the sample
n
Inductive bias We recognize the first term the right side of (A.2) squared bias term. This term reflects the inductive bias of ridgeless least squares: it is orthogonal to ker(X), so it cannot capture the part of B0 in ker(X). We note that this term is only non-zero in the overparameterized regime: BolS has no inductive bias.
Lemma A.3 Hastie et (2019). Lemma 2). addition to Assumption A.I assume || = so for all n, d. We have
2 (1a - 11x)30 & (so - (1- V as n, 0o, d +
Variance
The second term the right side of A.2 is variance term. The limit of this term in the high-dimensional asymptotic setting is known.
Lemma A.4 (Hastie et al. (2019), Theorem 1, Lemma 3), Under Assumption A.1
we have
as n, d + cc, d +
Tr
P
Approximation error The third and forth terms in (A.2) reflects the approximation error of BotS and Bmin because the linear model is misspecified for the mixture of two groups. Unlike the inductive bias and variance terms, this term does not appear in prior studies of the average/overall risk of the ridgeless least squares estimator Hastic et al. (2019).
Lemma A.5. In addition to Assumption A.1 we have
assume |00122 and 8 Bo cforr all n, d. As d + oo
+ x2 2x)
O Onoxd {
X/n {113(
XT
Onaxe X1
/n3o B r I--g
? <<>
X1
x (n-2)
? >>1
7(7
and
O Ongxd xd X1
8T
X/n) (Et)) B cm((1/}A11)
Before moving on, we note that (the limit of) the approximation error term the only term that depends on the majority fraction æ. Though the inductive bias may increase at overparameterizze regime (7 > 1) with growing 7 when the SNR (= |1:0 is large, we notice that the approxi- mation error terms always decrease with growing overparameterization. In fact they tend to zero as 7 20.
We plot the (the limit of) the minority risk prediction enror (MSPE) in Figure 4 In both overparame- terized and underparameterized regimes, the MSPE increases as π increases. This is expected: as the fraction of training samples from the minority group decreases, expect ERM to train model that aligns more closely with the regression function the majority group.
We also notice that in the overparameterized regime (Y 1) when the SNR (1132113/ (13//// ) is high the MSPE increases with growing y if the two groups are aligned (the angle between Bn and B is 0). This trend is also observed in Hastie et al. 20099)
13

---

Under review as a conference paper at ICLR 2023
n= 0.6
0 0
-= 0.7
0 45
== 0.8
8 90
ERM
== 0.9
ERM
6 135
0 180'
2-
1-
10
10a
10
Y
Y
Figure 4: Minority group prediction error for the ridgeless least square ERM in the isotropic features case. The left plot considers the setup with varying æ when the angle between Bn and 81 is set at θ = 180 The right plot sets 0.8 and considers different values of 0. Here the SNR is set at
||3011//2 =
1 1/11//72 10.
A.4 INADEQUACIES RIDGELESS LEAST SQUARES
There is one notable disagreement between the asymptotic risk of the ridgeless least squares estimator and the empirical practice Pham et al. (2021) in modern ML: the risk the ridgeless least squares estimator increases as the overparamettriizttio ratio increases, while the accuracy of modern MI. models generally improves with overparameterization. This has led MI. practitioner to train overparameterized models whose risks exhibit double-descent phenomenon Belkin et al. (2018) & Inspecting the asymptotic risk ridgeless least squares reveals the increase in risk (as 7 increases) is due the inductive bias term (see A.3). For high SNR problems (so >> -2), the increase of the inductive bias term dominates the decrease of the variance term seee..4). which leads the overall risk increase. This is consequence of the fact that problem dimension (the dimension of the inputs) and the degree of overparameterization are tied ridgeless least squares. In order to elucidate behavior (in the risk) that more closely matches empirical observations, we study the random features models, which allows us to keep the problem dimension fixed while increasing the overparameterization by increasing the number of random features.
A.5 MAJORITY GROUP SUBSAMPLING
We note that the (limiting) minority risk curve of majority group subsampling the (limiting) minority risk curve of ERM after change of variables. Indeed, it is not hard check that discarding training sample from the majority group until the groups are balanced in the training data leads to reduction total sample size by factor of 2(1 π (recall E [ 1]). In other words, if the (group imbalanced) training data consists of n samples, then the (group balanced) training data will have 2(1 T) training samples. In the n, + x0,
7 limit, this equivalent to increasing ? by a factor of 21- The limiting results in ERM can be reused with the following changes: under subsampling (1) changes to 1/2, (2) 7 changes to 7/(2 2Tr, and (3) rest of the parameters for the limit remains same.
In Figure 5 where we plot the differences between subsampling and ERM minority risk, we observe that subsampling generally improves minority group performance over ERM. This aligns with the empirical findings in (Sagawa et al. (2020) Idrissi et al. (2021). The only instance when subsampling has worse minority risk than ERM is when the angle between Bu and 31 is zero, i.e. Bg = 31. This perfectly agrees with intuition: when there is no differnce between the distributions of the groups then subsampling discards some samples for majority group which are valuable in learning the predictor for minority group, resulting an inferior predictor for minority group.
14

---

Under review as a conference paper at ICLR 2023
Subsampling ERM
ERM
n= 0.6
0
==7
0=
n= 0.8
8 90
0=9
Subsampling
135"
0 = 180
Figure 5: Minority error differnce between subsampling and ERM for the ridgeless least square in the isotropic features case. The left plot considers the setup with varying when the angle between 9o and 31 is set at 0 = 180 The right plot sets æ at 0.8 and consider different values of 9, Here the SNR set at |1 7 = | / 5.
A.6 PROOFS OF LEMMAS A.2 AND A.5
A.6.1 PROOF OF LEMMA A.2
Denoting U = (X X/n)² X/n we note that the estimation error 3 - :o is
Ongxd X1
Ong xd Xi
- 30 U(X30 +
8 + e) Bo (IIx 12)30 + U
8 + Ue,
we have the following decomposition of ERM minority risk
Ro(3)
-E (3 Bo) -Bo]
=E
{ (TXx Ta)B0 U
Onaxd X1
5 Je}
(
Ta)3o U
Ongxd Xi
8 Ue
Onoxd] X1
Ono xd X1
5 (IIx -I) + E[c (U) Uc| +8T
(U)
5+
T Ongxd]] X1
{ (uxx (ux- - 1a) (a)
Onoxd
(U) (11x - 1a)30 + 2E
+
Ue
X1
The term is equal to B (Ilx 1a)30 because 11x La is projection matrix. By the linearity of expectation and trace operator, the term is equal to
E Tr(( (U)
(UT) (U) Ue)] Tr
S Elee T] = Tr 1 n
72
(tt)).
n
n
By properties of Moore Penrose pseudoinverse, the term III and IV are equal to [
o Onoxd] X1
X/n x/n
T
Ono X1
/m and 28T
{
T [Onoxd
X/n (St)2888888
respectively. The term V is 0 since E(e] O. Hence we complete the proof.
A.6.2 PROOF OF LEMMA A.5
We first prove for the cross term that
37 (0,
E E E(E))² X (0,
8
xT,
(A.3)
d n
15

---

Under review as a conference paper at ICLR 2023
To realize the above notice that for any orthogonal matrix O it holds
El BIg E(STt) _ x (0, (0, (0X 12
n
where X is replaced by Xo XO and the replacement in X changes the covariance matrix to Eo and it's Moore-Penrose inverse to Eg_ Noticing that X _ Xo. Σ $ Eo and Đt - Eg we conclude
Ei8y OEo xx x0,,) = Eig 0S (0,
We now let O be uniformly distributed over the set of all d x d orthogonal matrices (distributed according to Haar measure) which results in
n EB - X (0, E E(St) X (0.
E م()) x (6"To/d)) b)/d))
To calculate the term
BIT 2(5))2 x " ||T X
we notice that
B E(ST)( ( XII
1 d
Σ T E(Et)(( )H
x=
and each of the terms Tr ( ) are identically distributed. We appeal to exchangability argument to conclude
Σ B (( 1}
Σ E Tr
H
+=
where we notice that ΣEt is a projection matrix and conclude
1 E[Tr E(Et)$)) = E ΣΣEH)
If < n i.e. < then Σ is invertible and and it holds ΣSt = Ig. If > then there are exactly many non-zero eigen-values in Σt and it holds Tr( ΣΣ n. Combining the results obtain
E E = (1/7) A1
Now, to calculate the term
we first use similar argument to
A.3 and obtain
x X1 (5 25 x yl
E (00, (100xx (0, (0, = |01 - E(Tr(
We rewrite
E|Tr(
XT
(ttz
XI X1
= F1. + +1 - 112
where we define
Fi.1 A
Tr
E
F1
A
E(
St
2
16

---

Under review as a conference paper at ICLR 2023
To calculate 11111 notice that
nF = E Tr 31æ1 (SSty
s }
d
n
1 01
Ti (E1)221
7
Denoting 4 as the L1 convergence we notice that u 4 i.e. 21 7) - 0. We now
calculate the convergence limit for ="()))² Noticing that
=T lim -2 ( + zlIa) 2
2-04 n
we write Σ + 2lIa- = ( /n) + Az, where A, = x X 1/nz + zId. decomposition
Using the Woodbery
A- (x) 1 /n)A=
[ /n) + A-]-1= = A7
1 + x AZ
we obtain that
1 A
2 [ 2Ta)
2x1
(1 + _ A x1)²
In Lemma A.6 we notice that
- 22 A m1
7
7 << 1
E
1
A
m1]
[1-
? < 1
as d - xc.
n
7>1
n
[ύ-133
?> 1
1 T A A 211
var
- T A=1x11
x1
var
-2
+0
which implies nFi,1 converges
<<1
167-1)
9>1
Noticing that
Tr [ }] B(Tr E((T))$5)) = nFi, + nnnn 11
1 d
we obtain the convergence of n(n - 1) as
1-27
9<1 1
4
I-p
7-2
7>1
7(7-1)
which finally yields
X,X, X1
(Stj2 X1 X1
E Tr
1| = n1 F1,1 + m1(m1 - 1122
n
x mn an + + - 11
A1-21)
<<1
(
<>1
Lemma A.6. As z + 0+ and d + 0o we have
1
E
T
A
[x1]
n
7-1
7>1
T-ン 9<1
E n1
A 2
x1
-
>>1
1x-1)3
and
1 varl
1 Ar
rıl.
varl
-
A x1
+
n
17

---

Under review as a conference paper at ICLR 2023
Proof of Lemma A.6 To prove the results about variances we first establish that for any symmetric Raxd holds
matrix B ((bi)) E
var(w] BaT) S <TT(BB),
(A.4)
for some
Writing 21 (ui...., ud)) we see that
var(z) Bri) = var Eis ucubbis)
= Σ bybb:covuuuu, wz4)
Noticing that
cov(u,uy, u.u1) (uauyunu
E Clu,u E u
we see that
1. one of i, kr is distinct from the others then cov(uu ug44) = O.
2. If i and k = 1 and + lc then
E [uuuyuuu E(u,u,) [u = E(u
E E E
O.
3. If j k then cov(u; u. var(u?)-
If (i and j = and i j} or (i = and j = le and * j) then we have E Blu,u, [[mum][[uun]] var(u,uy) = var(u)u2).
E (enu,
Gathering the terms we notice that
var(z] Bx2)
Σ var(u +
bi varuue,) Σ itj
$ Σ
b = cTr[B²}
where c = 2(var(u?] var(unu2)).
Using
A.4
notice that
lim var( var(oTA,221111 --0
Tr((S1,))) 24
(+())))) + 0.
1
n2
We notice that
E
-
1 21
1
Tr
71
n
which appears in the variance term in Lemma A.4
and we conclude that
7
2
A
31
+
1-7
d + co.
7 >>
To calculate
1
E
2
A
x1
Tr(A,
consider case by case.
For y < we see that
Tr((E))2)
= 1 (T((
+ 1
dF)
18

---

Under review as a conference paper at ICLR 2023
The Stieltjes transformation of Hly is
(2 = d1 (x)
7 v(1 - 2)2
472
v7].
2712
For |2| < V7
82(2)
(x)(())
I
1 1
duc (x)
2/x8
(2/x))ddpy)
k=0
Hence, we have
d
lim 2-0 d=
(s,(:)) = E|1/X3].
Now,
1 1-7 2 4/2
= -1---2-
(1+
- 2yz 472) 1/2
=1 =1-7 (1=
- -2y2)
2/2)"1 1/2
1 = 22 2/2
(2² 22 -222)2
x1 x1-7-2 (1 (1-9)) 7)
for 2 - 0-
2(1-7)²
8(1 - 7)
2- 2% 2//2
22 + 7)
x1-7-2 (1 7)
for 2 + 0-
2(1 - 7)
2(1 - 7)
21+22)
2 4/2
2(1 7)3
2(1 - 7)
2
27z
(1 7) 1-7
which implies
87(2) x (1 733 1-
z
+
1
This establish that
[T(( lim
(s,(2))
2-0 dz
(1 71-
For > we notice that
1 Σ
where s;'s are non-zero eigen-values of X X/n. This also equal to
1 a
PP
where t are the eigen- values of the invertible matrix XXT /d. Hence we have
ITH 1 -
-2
72 -0 de (s1) =
lim -f
n
(7 1)3
19

---

Under review as a conference paper at ICLR 2023
We combine the limits for y and y to write to write
E - 1 A A,2x1
m1
[1-7)
as d + 00.
1ύ-1)3 1j3
> 1
B PROOF OF THEOREM 3.9
Before diving into the main proof give rough sketch of the whole proof. Essentially, the proof has three major components.
1. In the first part, we establish the limiting risk where we treat 30 and 6 as uncorrelated random variables. (Section[Bs [B.]]
2. In the second part of the proof we establish the necessary bias-variance decomposition under orthogonality of the fixed parameters Bg and (Section B.2
In the final part, we use the results of previous two parts to establish the limiting risk result for So and 8 in general position. (Section B.3 and B.4
B.1 LIMITING RISK FOR UNCORRELATED PARAMETERS
We start this section with some definitions of some important quantities.
Definition B.1. Let the functions V1, V2 : C+ - C+ be uniquely defined by the following conditions:
(i) V1, 1/2 are analytic on C+. (ii) For Im([) > 0, v2(() and vz(C) satisfy the equations
8222
P1 111
( 1/2
E2
52
(-S- 1/1
V2 1/1
222
(ii) (M)( v2(S)) is the unique solution of these equations with |v((S) S /2/Im((), [p2(C)| S (2/Im(() for Im(() > C,
with C sufficiently large constant.
Let
x ==
and
60(5, 1,,,,,,,,,,, A) -x 3x + (W1322 - 1)x² 2x35 -3x352
(b/1 + 12 - 30 +0x 1)x
x2 30/4/2x2 01822,
(5, wh, 0/. A) 3² -222 + 22 1/44/,
(E Un, 22 2) = 55 - -xx + (1/1 1)x + +2x + +3x 352 + (- - -x262 x2
We then define
Bridge 11, 222 A) = 61 Uh, U2z A)
(B.1)
E0 vi, 12, A)
Vridge (E, 1/,, 1/2, A) = EG 11, U/2 ))
(B.2)
LE th, (b2,
The quantities derived above can be easily derived numerically. But for our interest, we need to focus on the limiting case when x - 0. It can be shown that when À - 0, the expressions of Beidge and Vridge reduces to the form of 8 and / defined in Lemma 3.7 respectively. For details we refer to Section 5.2 in Mei and Montanari 2019a).
20

---

Under review as a conference paper at ICLR 2023
Now are ready to present the proof of the main result. Recall that
2
a(A) == arg DERN
R
y1
Σ ajo( 2//Va)
NA
d |all
7
By standard linear algebra it immediately follows that
1 ( + 212,,022, Z y.
a(A)
(B.3)
Vd
where Z
1 (XOT/VV dn à and 122 3. Also, define the square error loss va
RRE (z, x,,, = (x Bu - f(z; à 0))? where is new feature point.
For brevity, we denote by I the tuple (X, θ 3o. 8). Recall that we are interested in the out-of sample risk By (ar, X, O. A)],, where is feature point from minority group. The main recipe of our proof is the following:
We first do the bias birs-variance decomposition of the expected out-of-sample-risk.
We analyze the bias and variance terms separately using techniques from random matrix theory.
Finally, we obtain asymptotic limit of the expected risk by using the asymptotic limits of bias and variance terms.
BIAS VARIANCE DECOMPOSITION
The expected risk new point coming from the minority group be decomposed into following way:
ErE, RRF (z. O,) = E, fi T Bo - f(z;
= E, x [x T 8o Exf (A)) E,E, Var (fr(()(rr(())))))
term
(B.4)
The above fact follows from Lemma 3.3 which basically uses the uncorrelatedness of 3o and 8. Now define the matrix
(Z Z + 2
(B.5)
In the next couple of sections we will study the asymptotic behavior of the bias and variance terms by analyzing several terms involving V. In order to obtain asymptotic limits of those terms, we will be borrowing results of random matrix theory in Mei and Montanari (2019a).
DECOMPOSITION OF BIAS TERM
We focus the bias
B(,, Ey { [ 30 [=)()=(())))))
(B.6)
2 X + Vz x16) [
= Er (B80o(er/Vd)
(ZZ Vd
It turns out that it is rather difficult to directly analyze the bias term B A). The main difficulty lies in the fact that the terms involving 3n and are coupled in the bias term and poses main difficulty in applying well known random matrix theory results directly. Hence, in order to decouple the terms look at the following decomposition:
B(5 A) B(8, A) B(0, A) B(O.
(n)
(TT)
It is fairly simple to see that term (II) is only a function of 3g. Next, we will show that term (I) does not contain So. To this end, We define the matrices Ú,U E NNN follows:
O.y o0, (0, x/Vo)o(0 s/Va), U. B(ŪOg) V(i,)) [N] x (N].
(B.7)
21

---

Under review as a conference paper at ICLR 2023
Next, due to Assumption 3.2
it easily follows that
B(6, - 2) ()
Er
TT Bo o(Ox/V())
1
(VZ (V X + x10))
Vd
Er
(180-o(ex/Va))
Vd
(B.8)
(TXTZNNÜUZTXX
[T(
E
F? d2
E
Above display shows that term (I) does not contain fo- In the subsequent discussion, will now focus on obtaining the limits term (I) and (II) separately.
Next, by the property of trace, we have the following:
}
Tr(X] ZU X1) Tr
Σ
2424
DU
Σ 2,07
iimig
W1
i
j=
Σ
Σ
I Tr (1
< 1 +1
1. T
Σ
aJ&:Tr Tr (VUVzzzz
notisijjnn
(B.9) and
Thus,
exchangeability of the fxj v, (2 2, T) Ioottsissgn we have
by
terms
(TVVW ]een)
1 Tr (X] Z VU x.)) fl, mi(11 (1),1,,,,, 1),(
(B.10)
where f(i.j) = E ( x: Tr (UV2 2,,, x) /d and < i,j < 2. Hence, together with Equation
B.8 and Equation B.10
follows that
B(6, X) - B(0, A)
+ n (mi (1,
(B.11)
Furthermore, from Equation (8.10), Equation (8.25), Lemma 9.3 and Lemma 9.4 of Mei and Monta nari (2019a), get
B(0, A) = Bridoo (5, 11, 2/, 2/12) + oa(1),
(B.12)
where Bridge (E, 1/, 2/2,, A/p2) is defined as in Equation B. Thus, it only remains to calculate the limit of B(,,, A) B(0, X) in order to obtain the limit of the bias term B(5, A)-
ANALYSIS OF VARIANCE TERM
Now we briefly deffer the calculation of term (I) in Equation BI.1 and shift our focus to variance term. The reason behind this is that is hard to directly calculate the limits of the quantities appearing in the right hand side of Equation (B.IT). We obtain these limiting quantities with the help of the limiting variance.
22

---

Under review as a conference paper at ICLR 2023
Note that for the variance term, have
V(A) Er Var,
Er Var. [(0x/Va)] T
Vil
Br IT/DUZZ 27/r2
(B.13)
7²
(P[Tr(UUUZ) 2)}
where 13 = E (Tr (WU' ] /d. Again by exchangeability argument, we have the following:
I n (QUVZRz))
nf(1, =
12
Tr ( (VU
(as x; 2 1)
(B.14)
1=1
Tr (VUNZTZ)
Thus, in the light of Equation (B.II) and Equation (.14). we reemphasize that is essential to understand the limiting behavior of f(i, j) in order to obtain the limit of expected out-of-sample risk.
OBTAINING LIMIT OF VARIANCE TERM:
To this end, we define the matrix E MRMxM, M = N + with parameters q (81, 82, 41, (2, E R in the following way:
A = A(q) = sT + 8 ZT +
[ 12+pW
4I + +
where
1 T H. J XXT W #1 X d
Q L0e
d
For Ç E C++, we define the log-determinant of A G(g. 9)
Σ Log (Ax(A) - -MTr) Here
Log is the branch cut on the negative real axis and (A{(A) ke([Ar] denotes the eigenvalues of A in non-increasing order.
Define the quantity
1 Tr TT(DUZZ 2).
From Equation B.14), it trivially follows that (E( 11, The key trick lies in replacing the kernel matrix by the matrix A Q IN By (Mei and Montanari] 2019a Lemma 9.4), we know that the asymptotic error incurred the expected value of V by replacing U in place of A is od(1). ). To elaborate, first define
3 Tr [T((AAZZZ))
Then by (Mei and Montanari
2019a
Lemma 9.4), we have
E E
Vzl oa(1).
(B.15)
Thus, instead of J. will focus V. By Mei and Montanari 2019a Proposition 8.2) we know
V3 -1300 Ga(i(1b1122)) 0) pro Ga((((1
(B.16)
23

---

Under review as a conference paper at ICLR 2023
Also by (Mei and Montanari, 2019a
Proposition 8.5), for any fixed R4, have the following:
lim E
Ga 0) Viuiiu 1llppp) 0.
(B.17)
(22 As 33 is a bi-linear form of Ga((( 12 22 A) 0) (See Equation (B.16), together with (Mei and
Montanari 2019a Equation (8.26)), follows that
lim E V (S th, 1/2, A/p2]] - 0, d-000
(B.18)
where Vridge (S. 1, 22, 2/12)) is as defined in Equation Equation B.18) yields that
B.2 Thus, both Equation (B.15) and
lim E L Vridgo 11, 1/2 A/11) 1 O. d'+oo
(B.19)
Hence, by Equation B.13
we get the following:
V(A) = (S 11, 22,2A/1/77 oz()).
(B.20)
OBTAINING LIMIT OF BIAS TERM:
Now we revisit the term Bí6, X) - B(O, A). We will study the terms n, f1, and nı (ni - (1, in Equation [..I separately.
First, we focus on the term /n [1,, 1). Equation that
Equation (B.55 and Equation (B. show
n f1, 1) = Vidge (5, 11, 22 a/p²) + o1()).
(B.21)
Next, in order to understand the limiting behavior of [[1, 2). we define
12 - Tr (WUVZ HZ),
1/2 d Tr (VAVZ HZ).
Again due to (Mei and Montanari
2019a Lemma 9.4), we have
43 V/l oa()).
Hence, we only focus on V/ A calculation similar to B.9 shows that
(B.22) Let g(E: q) be the analytic function defined in (Mei and Montanari 2019a Equation (8.19)). Using (Mei and Montanari 2019a Proposition 8.5), we get
E (12 = (1) - (1, + o1(1).
2 = - (( 1/2
1e (0)+((11)) =: V 1/ t2 A M1. Ho)
This along with (B.21) and (B.22) show that
n(n 1 1), (5 1/,, 122, A, fl, p1) Vridge(E, 1/, 4/2, a/p2) od(1).
(B.23)
Thus, finally using Equation (B.1T). Equation 1. and the fact ni/n n n, conclude that
B(5 Bidge 11, 2/2,, A/p²) F3 ( x) (S, 1/2, 2/2,, A/p²) + x 1 1/1, 1h2 p., pn +oa((1).
(B.24)
Lastly, using Equation (B.20). Equation (.24 and plugging the values in Equation B.4 we get
lim Ex,e,,, (Rr X, θ, A] d=000
BriBrd (5, 1h 1/2, A/p2) + F3 Vidgo 4/, 2/2, a/p3) x 2 thi 12, A, pv. M2)]
+ =" (5, (5, 11, 2/, X/)²).
(B.25)
RIDGELESS LIMIT
Finally, for ridgeless limit we need to take + 0+ on both sides of Equation (B25). Following similar calculations as the proof of (Mei and Montanari] 2009a| Theorem 5.7), or more specifically using Mee and Montanari] 2019a Lemma 12.1), we ultimately get
lim lim Ex.,,,, [nr(x, X-0+
X, 0, (Rnr F3 + FF 22..
This completes the proof.
24

---

Under review as a conference paper at ICLR 2023
B.2 BIAS- VARIANCE DECOMPOSITION UNDER ORTHOGONALITY OF PARAMETERS
In this section we will demonstrate that the same bias-variance decomposition in Lemma 3.3 continues
to hold rather weaker assumption than Assumption 3.2 Specifically, in thi section we only assume the parameter vectors Po and are orthogonal, i.e., Po ē = O. The following Lemma shows that under this orthogonality condition, the desired bias-variang variance decomposition still holds.
Lemma B.2. Define the followings: BB Ex [|| (2 2) 2 x [//dd and B,
Bx- Ff
2 X11l//. Also assume that 8o 8 = 0. Then, we have A (S0. 6) = F3.
Proof.
Similar to Equation [B.4 her also we have
B(B,, 8) = Px l1(x T
(2"=T(22) 2) 2 x x - x ))0 (2 (2 (=
(B.26)
+2(= (Z 2)'2 - x )3,5 x 21 (2 (2
The only difference in Equation (B.4) compare to Equation (B.26) is that Bo and 8 are now fixed vectors in IRd instead of being random. To this end we define the space of d x orthogonal matrices as follows:
((d) = {0 E Rdxd, o 00 = Id].
Now consider the following change of variables for matrix 0 E Od))
X - XOT X,
- θ0 2
(B.27)
Bu 0 - Bo.
8 08
x Or E.
The key thing here is to note the following
a /xxXX0///////VX/ (xo /V)/Va=
Thus, the expression of a(A) in Equation (B.) remains unchanged. Finally, due to distributional assumption on and Lemma C.1. we have ã ~ Uni (Vd)) for every O E Od). Finally, note that x 30 T B, which entails that (8, 5)
(o. 8) for all (d), where
# (Bo. 8) = Ez-Py [[ 2 Z) 2 X x } + (2 Z) X,8
+ 2 (2 2) 2T X x 330 X (Z 2
This motivates us to consider the change variables in Equation (B.27). when O is sampled from Haar measure Ha on (d) and independent of X, O, c. Also, note that due Lemma C.1 and Lemma C.2 the random vectors fo and 8 satisfy the setup of Section B.1 Thus the result follows immediately by noting the fact that
D(3, 8) EO~H, (3.,
5)] |
Bg + Fg D,
where the last inequality follows from taking x + 0 in Equation (B.11) and Equation B.12
B.3 LIMITING RISK FOR GENERAL 30 AND 5
Unlike the previous section, this section studies the general property of the asymptotic risk Ro when the parameters Ag and 8 are in general position. Specifically, in this section we relax the assumption that 8 5 + O. Thus, the only difficulty arise in analysing the cross-covariance term 2E [(= (zT Z)iz Z X/Vd x 3,0 XT (Z hytz/VCl in Equation (3.3) as it does not vanish under the absence of orthogonality assumption. Thus, essentially boils down to showing the results in Lemma 3.3 and Lemma 3.8
B.3.1 PROOF OF LEMMA 3.3
We begin with proof of Lemma
3.3
We recall the right Equation
3.3 i.e,
(S0. 8) = Ex [((2
(ZT Z)1Z - x
x TT ) + {2 (z 2) 10,12xxpx X1882
+2(x T (Z 2) x - x )806 x 2i (zT))t)
25

---

Under review as a conference paper at ICLR 2023
Apart from the cross-correlation term, The first two-terms of the equation does not depend on the interaction between Sn and To be precise, the first two terms are only the functions of Po and 5 individually and does not depend on the orthogonality of in and d. Thus, an analysis similar to Section B.2 yields that
(Bo. 6) =
2 (Z" x 3000 x (z(22))22)
Thus, it only remains to analyze the cross-covariance term
6,,5 - P Px [( Z) - ==
(1 2)1 x, -
To get the desired form as in Lemma 3.3 again introduce that random variables Bo, 8, X. X1, 2,2r and 2 as in Section B.2 Also, define the quantity
6,5 - px [( (2 2)1Z X
=) x, 2)T22))
Following, similar argument in Section B.2 have 69 Bo- H. (6 (,88).
Next, note that,
6,56 = 23 [T (2 2) 2(2 (Z) 2) x )80 ).
Thus condition on 7 and and applying Lemma C.2 the result follows, i.e..
6 = F3.6
(B.28)
B.3.2 PROOF OF LEMMA
Following the same arguments of Section B.1 and Section B.2 it can be shown that the limiting values of E Bel. B and [T)( remains the same, i.e.. the results of Lemma 3.7 and first part of Lemma 3.8 remains true. Thus, it only remains to analyze the cross-covariance term
63,6 2x [(= T (Z" Z)!Z x - x =')00"' x, (z ()
fully characterize the asymptotic risk asymptotically. To begin with, the vector can be written as a direct sum of two components ó and 82, where ó2 is the orthogonal projection of 8 on (3)o( In particular we have
5 + 82, and 82 (T. 30.30 / 1)
Thus, there exists E R such that 61 = uBo Thus, E5,5 can be decomposed in the following way:
63,6 2uTEn Px 11 x 1 Z)1 (Z" Z)1 z X1 2μBBrry 11% x, Z1 2) 2x Bo)
(1.2)
+ 2E [(2 (Z Z)tZ x T BOOJ Xi 21 2)tz].
As /3 82 = 0, following the arguments in Section B.2 we have 6/3) = 0. To analyze the terms (1.1)
3,6 and (1.1))
3,8 we will gain analyze their corresponding ridge equivalents
((1.1) (
(2) (A):= = 244 E. (3) Zx
d
(1122)
3,5 (A) = 24 En (30
X, Zi Vux (o)
Vd
where v and are defined in Equation B.5) and Equation B.7 respectively and Vdz. We focus on these terms separately. To start with, by an application of exchangeability argument we note that
= 2FF3 d²
E
(1.6 3,5
(2)
[T {x
= -21Fg + mm 1)f(1,2) + non (1,2)(
26

---

Under review as a conference paper at ICLR 2023
Using Equation (B.21) and Equation (B.23) it can be deduced that
3 (A)) 2 3 (E 1/1 t22, A, Mas 11) oa(1).
(B.29)
Let us denote by V the matrix B(urT) ). This shows that
B (A)) (A))
24 E 2V
vd
Again by exchangeability argument we get
E(G
(1.) (A)) n1
2p
E (g) x ZVVV3..
vd
Let define Ti (201a),, we can also conclude that
V E (g) X ZVVBB) Bo). By the arguments of Section 9.1 in Mei and Montanari
T = Op (,00 + oz(1),
the function is defined in (Mei and Montanari 2019a Equation (8.19)). Thus we have E (A)) =
3,6
n ((1 0) (1)) This along with Equation (B.29) yields the following: (1.1)
E(6o,s)
lim (6 3,6 (A)) E
8.8 (A)) + oa(1)
x-0
lim um F 22 1/,, 222 p1) 0p (10(((11122)) + oa((1)
x
F ( + ) + oa(1).
Finally, by simple algebra it follows that
Fa. cos 02 where
(3.0) 5)
Φ =arcos
F Fs
This shows that 3F3 = F2F's cos (03,)) = BJ = F3,8- Now recalling Equation B.28 have
lima-soo [[GR,s] fI* 12). This finished teh proof of Lemma 3.8
B.4 FINAL FORM LIMITING RISK
Finally, Gathering all the results from Section B.1
B.2 and B.3
we have
lim = d
=
Mi + Fg, +
2
with 6+
(I0 V This concludes the proof of Theorem 3.9
C UNIFORM DISTRIBUTION ON SPHERE AND HAAR MEASURE
In this section we will discuss some useful results related to Uniform distribution sphere and the Haar measure Ha on (d).
Lemma C.1. Let U Unif(Sd-((a))) and O O(d). Then OU ~ Unif(s Also, if O ~ Ha and is independent of U, then also OU Unif(sdd (Vd)).
Proof. Note that U L V/G/ || where G N(O, Ta). Next define & = OG. By property of Gaussian random vector have G G. Now the result follows from the following:
OU va OG va Ô
vā G U.
|G||2
|G1|2
G
27

---

Under review as a conference paper at ICLR 2023
Next, let O Ha be independent random matrix from U. Thus conditional on O, we have
OU 10 (Vd))
Thus, unconditionally we have OU Unif{
Lemma C.2. Let B, 3 Rd such that 8 8 = FB, 8. Also, define the random vectors 3 03 and
5 O6, where O Hds Then the followings are true:
FB.6 Ia
B(3ōT)
d
B(33T) =|81|== 1(00
= Ia-
1
Proof. Let = (01, 02. .2....,o.. T i.e, o, the ith row O. Let T E(35T) = E(O OT).
Also, by property of Haar measure, we have IIO d for any permutation matrix II. This shows that jo are exchangeable. As consequence we have
B(o,0,) Ed B(oxo)) B(OTO)
1 d for all E [d].
d
Now we are equipped compute matrix T. Note that
Tr E(o, 38 0.) ES8" 00; (} 5T 3/d= Fo.s/d.
Also, for i + j. we similarly get
Ts = E(0 0, 3}.
Now again by property of Haar measure we know O (I. 2ese, ),, where denotes the ith canonical basis of Idd This implies that 0, _ -0,0 Using, this property of Ha. we also get B(o,o,) = 0. Thus, we get Taf = O and this concludes the proof for uncorrelatedness.
Next, we define V = E(ō By a similar argument, it also follows that
(V (V)),, |1 A.j.
where Aiy is the Kronecker delta function. The result for can be shown following exactly the same recipe.
[
D RANDOM FEATURE CLASSIFICATION MODEL
In this section, consider overparameterizee classification problem. We consider two group setup: g E {0, 1}. Without loss of generality, we assume π (so the = group is the majority group). The data generating process of the training examples { ys) )
gi Ber(m)
24 ((0
(D.1)
y: 2, 9i < { +1, w.p. o3 1}
-1, w.p. 1 f(x Bo) = - B1)1(9 1}
where Bo, 31 E Rd are vectors of coefficients of the minority and majority groups respectively, and - (1+ is the sigmoid function.
Consider a random feature classification model, that is, for a newly generated sample (#n+1s Bn+1), the classifier which predicts label fn+1 for the new sample
N Σ ajo (0J0(1 (ofant1/Va) 1=1
9 = sign
28

---

Under review as a conference paper at ICLR 2023
where a--) is mon-linear activation function and N is the number of random features considered in the model. In the overparameterized setting (n S N), we train the random feature classification model by solving the following hard-margin SVM problem:
arg arg BER
|all
a E
subject to
yi a 2 M
where 2; = (2i,1....., N,,N) with Fi, =
for i [m], E [N].
We wish to study disparity between the asymptotic risks (i.e., test-time classification errors) on the minority and majority groups, that is, comparing
Ro(@) E[1( # yn+1 H9 0] and R Ej1 # 3n+1H9t++1 = 1]
asymptotically. Moreover, we consider a high high-dimensional asymptotic regime such that
d0 Nod 1/1 0, n/d 2/2 and 7 = w1/1/22
d lim (N/n) 2 1.
Therefore, encodes the level overparameterrizatio...
In the simulation for Figure g we let (-) be the ReLU activation function and 8 be IID standard normal distributed. Moreover, we let π = 0.95, 3u = 10e1, 81 = 10 cos (0)e1 + (0))n(0)) = 400, d 200, N yn where E and 62 are the first two standard basis of Rd. We tune hyperparameters 0 E {00, 45%, 909, 135%, 180") and E (1, 1.5, 2, 3, report test errors averaged over 20 replicates.
3, 3.5, 4, 4.5, 5.5, 6), then
29


Reviews:
[{"review_id": "wYSwffom5nT", "reviewer": "Reviewer_y1cp", "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": "The paper studies the effect of overparametrization on minority groups from a theoretical perspective. Building upon existing works, the authors study the asymptotic performance of overparametrized methods in minority groups in a stylized model and show that their results are consistent with empirical observations. ", "summary_of_the_review": "The paper is well-written and the message is clear; more justifications are needed in terms of the choice of model.", "strength_and_weaknesses": "- **Strength**:\nThe paper is well-written and the simulations are well-designed. The message is clearly conveyed.\n\n- **Major concern**:\nOn page 3, it is remarked that the paper adopts the random feature model instead of the linear model because results in the latter model do not coincide with the empirical findings. I am confused in that (1) what is the model in general used in empirical works (it seems to me should be the latter)? (2) if both models are approximations of the models used in practice, then why are there inconsistencies? Choosing the model that exhibits the desired performance feels a bit like cherry-picking to me---but I could be wrong!\n\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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "k5J1NpAtXT", "reviewer": "Reviewer_1vd9", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the effect of overparameterization under the existence of minority groups. The paper provides theoretical characterizations based on existing work, and ran experiments on the fixed point equations to show that the overparamterization does reflect recent empirical findings in this high dimensional setup.", "summary_of_the_review": "See above.", "strength_and_weaknesses": "The paper is easy to follow and well-written. The numerical experiments are abundant.\n\nHowever, I find the paper lacks theoretical novelty as the main results are direct applications of previous work. In the abstract the authors claim that they show overparameterization always improves minority group performance, but I found no such theorem is stated instead of numerical solutions to the fixed-point equations characterizing the asymptotic behavior. I would expect a theorem that says the effective bias and variance on the minority group is monotone if it is claimed that this is shown.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "M4sGRx6pSDc", "reviewer": "Reviewer_2EGb", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 1, "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 develops a simple two-group model to study the effects of overparameterization on groups. It provides a theoretical justification for the empirical results in the existing work and shows that the overparameterization improves or does not harm the minority risk of ERM. The majority group subsampling improves minority group performance in the overparameterization regime. ", "summary_of_the_review": "see above.", "strength_and_weaknesses": "It provides a theoretical justification for the effect of overparameterization on minority groups. \nThe paper is easy to follow.\n\nThe application scenario of overparameterization and underparameterization in machine learning is not well explained. \n\nIt mentions that the proposed two-group model has parameters for controlling signal strength, majority group fraction and many terms. I would like to see how the signal strength is used in classification, regression or other machine learning task. \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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "GDFkWcakdS", "reviewer": "Reviewer_Fo6C", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of how overparametrization affects the ERM's performance on minority groups theoretically. To be more specific, this paper theoretically shows that under the overparametrazation condition and ERM algorithm, the minority groups will tend to have worse performance on the regression tasks, and also shows that subsampling majority groups can improve the performance of the minority groups. The theoretical results are consistent with the empirical studies observed in previous works. ", "summary_of_the_review": "This paper has three key limitations stated in section \"strength and weakness\" and lacks the novelty and impacts to the community. So I tend to vote a reject to this paper. ", "strength_and_weaknesses": "Strength: This paper is well written, easy to follow, and has solid results.\n\nI think the paper has the following key weakness\nThe results seem to be very straightforward when compared to under-parametrized cases, but this paper is lacking the comparison of over-parametrized cases and over-parametrized cases, including the clarifications/justifications whether and why the conclusions made for under-parametrized cases can or cannot apply the over-parametrized cases. If the results for over-parametrized cases do not differ from the under-parametrized cases, the novelty and necessity of this paper may be problematic. \n\nAlso, while this paper is discussing the over-parametrized ML, its analysis and/or conclusions do not cover how the minority groups' performance change with the number of parameters from under-parametrized cases to over-parametrized cases. \n\nFinally, the two key conclusions drawn from the paper (minority groups perform worse and sub-sampling can help) are pretty intuitive and within the expectation of most people. This paper does not show great novelties of the methods, so the contribution of this paper to the community does not seem high.", "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": "1sV3ZbFtbT", "reviewer": "Reviewer_BTHL", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Recently, it has been empirically observed that overparameterization helps to improve performance on both the majority and minority subgroups of the data. Few works have also proposed methods to improve the performance on minority subgroups like group distributionally robust optimization and data subsampling. This paper confirms these findings theoretically by studying this using a random features linear regression model which takes into account the difference between the true predictors of the subgroups, the ratio of the data and the signal to noise ratio.", "summary_of_the_review": "The main concern I have with this paper is the concept shift model that this paper assumes for the subpopulation setting and lack of citations and comparison to previous theoretical works. ", "strength_and_weaknesses": "The problem that this work studies of how overparameterization affects subpopulations is important for the fairness and safety of machine learning and has gained widespread interest. \n\nI think that the model that this work studies is different from the practical setting that this work motivates. In particular, this work assumes that the subgroups have same feature distribution and only differ in their true conditional output distribution. I don’t see why that assumption is correct because the different subgroups would have different feature distribution. In fact, they assume that the two groups have different output distribution conditional on the features which is not clear if it is true because we can think of both the populations having the same true predictor. The setting that this work considers there does not exist a single good predictor which is not true in the empirical papers that they cite. This is also what was considered in the original paper [1] which first studied this using a toy model.\n\nThe paper misses important citations and comparisons to previous works which have studied similar problems [2,3,4 ].\n\n[1] An investigation of why overparameterization exacerbates spurious correlations\n[2] Covariate Shift in High-Dimensional Random Feature Regression\n[3] Undersampling is a minimax optimal robustness intervention in nonparametric classification\n[4] Throwing away data improves worst-class error in imbalanced classification", "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": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject